Before Easter, the supermarket was selling Rölli suprise-eggs, announcing that
every fifth egg contained a figurine related to Rölli's universe. This made me
wonder: how many eggs you need to buy to ensure that you get at least one such
figurine?

The following formula gives the probability (*p*) of getting at least one Rölli
figurine given that one has bought *n* eggs, and that every *k* egg contains
such a figurine:

p = 1 − (1 − 1/k)^{n}

The answer to the first question is not straightforward, though. To be
absolutely sure to get at least one figurine, you need to buy 4/5 of the egg
production plus one egg, because there is always an (admitedly slim) chance that
the 4/5 of are made entirely of eggs containing something else than a Rölli
figurine, and that the 1/5 that is left is made only of eggs containing Rölli
figurines. The extra egg that you need to buy is therefore taken from this
last 1/5, and is guaranteed to contain a Rölli figurine.

If you are not willing to spend so much time and money tracking and buying most
of the egg production, you can trade time and money for a tiny bit of
uncertainty. For example, if you can accept to have only 90% chance of getting a
Rölli figurine instead of 100%, it is enough to buy 11 eggs. If you want a
better chance yet and want to go for 95%, you need to buy 14 eggs. Finally, if
you want a 99% chance, you need to get 21 eggs. These values were computed from
the formula above, setting *k* = 5 (“every fifth egg”), *p* = 0.90 or
*p* = 0.95 or *p* = 0.99, solving the equation for *n* and rounding the result
to the nearest, larger integer.

It is also worth noticing that if you decide to buy 5 eggs (because every 5th
egg contains a Rölli figurine), you have only about 2 in 3 chances of
getting a Rölli figurine.

The table below gives the minimum values of *n* for a given value of *k* and
different probability thresholds. It also gives the ratio *n* over *k*, i.e.,
given a “one in *k*” probability, how many times *k* does one need to get to
have a probability greater than the thresold. The second column also indicates,
given a “one in *k*” probability, what are you chances of getting what you
want if you get *k* items. Notice that these values grow toward a given, finite
limit when k grows larger.

k | p(n=k) | p≥0.90 (n/k) | p≥0.95 (n/k) | p≥0.99 (n/k) |

2 | 0.750 | 4 (2.000) | 5 (2.500) | 7 (3.500) |

3 | 0.704 | 6 (2.000) | 8 (2.667) | 12 (4.000) |

4 | 0.684 | 9 (2.250) | 11 (2.750) | 17 (4.250) |

5 | 0.672 | 11 (2.200) | 14 (2.800) | 21 (4.200) |

6 | 0.665 | 13 (2.167) | 17 (2.833) | 26 (4.333) |

7 | 0.660 | 15 (2.143) | 20 (2.857) | 30 (4.286) |

8 | 0.656 | 18 (2.250) | 23 (2.875) | 35 (4.375) |

9 | 0.654 | 20 (2.222) | 26 (2.889) | 40 (4.444) |

10 | 0.651 | 22 (2.200) | 29 (2.900) | 44 (4.400) |

20 | 0.642 | 45 (2.250) | 59 (2.950) | 90 (4.500) |

37 | 0.637 | 85 (2.297) | 110 (2.973) | 169 (4.568) |

50 | 0.636 | 114 (2.280) | 149 (2.980) | 228 (4.560) |

100 | 0.634 | 230 (2.300) | 299 (2.990) | 459 (4.590) |

500 | 0.632 | 1151 (2.302) | 1497 (2.994) | 2301 (4.602) |

1000 | 0.632 | 2302 (2.302) | 2995 (2.995) | 4603 (4.603) |

One can use this table to find out how many times one needs to play the roulette
in a casino to have 95% chance of winning at least once: a european roulette has
37 numbers (*k* = 37), and the limit of the n/k ratio is about 3; one
therefore needs to play about *n* ≅ 37 × 3 = 111 times (the row for k = 37
indicates the actual value is *n* = 110).

Several months ago, the leffakone infrared receiver started to misbehave. There were a lot of errors in syslog about spikes in the signal, and the problem seemed to come from the serial port on the motherboard rather than from the homebrew IR receiver, co...