Randomised Ice Cream

For Employee Day, your company is offering everyone free ice cream, and you somehow find yourself at the front of the queue. The vendor manning the ice cream booth is handing out ice creams one by one in alphabetical order of flavour.

You take the first ice cream. When the vendor hands you the second one, you can choose to either:

Pass the ice cream you are holding to the next employee in line, and take the new ice cream, or
Hand the new ice cream down to the next employee in line.

This process will continue until all the ice cream is given out, but you don’t know how many flavours there are in total.

You like all flavours equally, so you want all flavours to have an equal chance of being selected. Thankfully, you have a small device in your pocket: you can enter any number $X$ , and it will generate a random number from $1$ to $X$ with equal chance.

How can you decide which flavour to keep?

Hint

We don’t know how many flavours there are until the last one has been given out. So after each ice cream has been handed out, your strategy will need you to be holding any particular ice cream with $\frac{1}{k}$ chance, where $k$ is the number of ice creams handed out so far.

Solution

Answer: When you’re handed the $k^{t h}$ ice cream, enter $k$ into your device. If it lands on $1$ , hand your current ice cream to the next employee and takes the new one. Otherwise, pass the new ice cream to the next employee.

The key idea is that your strategy must always act as if the next ice cream could be the last.

Let’s say you are holding the first ice cream, and the second one is handed to you. Your should take the second ice cream with a probability of $\frac{1}{2}$ , otherwise you should hold on to the first ice cream. This makes sure that even if there were only 2 ice creams in line, you have gotten them all at equal chance.

As the third ice cream is handed to you, you need to choose it with a probability of $\frac{1}{3}$ , and the other 2 ice creams with a probability of $\frac{2}{3}$ . And because in the previous step, you would’ve end up with the first and second ice cream at equal chance, the final probability would be $\frac{1}{3}$ for each of them.

Likewise, as the fourth ice cream is handed to you, you need to choose it with a probability $\frac{1}{4}$ , and the other 3 ice creams with a probability of $\frac{3}{4}$ . And because in the previous step, you would’ve end up with the first, second, and third ice cream at equal chance, the final probability would be $\frac{1}{4}$ for each of them.

In general, when the $k^{t h}$ ice cream is handed to you, you need to pick it with a probability of $\frac{1}{k}$ . Otherwise, you’ll end up with any of the previous $(k - 1)$ ice creams with $\frac{k - 1}{k}$ chance in total.

And since in the previous step, you would’ve ended up with any of the previous $(k - 1)$ ice creams with a probability of $\frac{1}{k - 1}$ , you’ll end up with any of the earlier ice creams with a probability of $\frac{k - 1}{k} \times \frac{1}{k - 1} = \frac{1}{k}$ .

Your device easily lets you generate a $\frac{1}{k}$ probability: simply type $k$ into the device and switch ice cream if the random number is 1.

Try These Next

Measuring Time with Hourglasses 1

Chain Link 2

Poisoned Wine (Extension)