FMM22

Friday Morning Math Problem

The Cautious Alchemist's Vial

An alchemist encounters a stream of vials produced one by one from a magical spring. He may carry exactly one vial home, and once he passes on a vial, it is gone forever. He has no idea how many vials the spring will produce in total - the stream could stop at any moment.

What strategy should the alchemist follow so that, no matter how many vials appear, every vial has an equal probability of being the one he carries home?

(Source: Donald Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms - Algorithm R, Reservoir Sampling)

Solution

Let the total number of vials be $ N $ (unknown to the alchemist ahead of time). Label the vials $ 1, 2, \dots, N $ in the order they appear. Strategy (Algorithm R for $ K=1 $) When the $ k $-th vial appears, the alchemist keeps it with probability $ \tfrac{1}{k} $, discarding whatever vial he was holding previously. Otherwise (with probability $ 1 - \tfrac{1}{k} $), he ignores it and keeps whatever he is already holding. Proof that every vial is equally likely We claim that each vial $ k $ (where $ 1 \leq k \leq N $) ends up as the final chosen vial with probability exactly $ \tfrac{1}{N} $. For vial $ k $ to be the final choice, two things must happen: The alchemist must keep vial $ k $ when it appears, which happens with probability $ \tfrac{1}{k} $. He must not keep any subsequent vial $ k+1, k+2, \dots, N $. The probability of not keeping vial $ k+1 $ is $ 1 - \tfrac{1}{k+1} = \tfrac{k}{k+1} $. The probability of not keeping vial $ k+2 $ is $ \tfrac{k+1}{k+2} $, and so on. Thus, the probability that vial $ k $ is the final choice is: $ P(k) = \frac{1}{k} \cdot \frac{k}{k+1} \cdot \frac{k+1}{k+2} \cdot \dots \cdot \frac{N-1}{N} $ Every numerator cancels with the denominator of the following fraction (a telescoping product), leaving: $ P(k) = \frac{1}{N} $ Since this holds for every $ k $, all $ N $ vials have an equal probability $ \tfrac{1}{N} $ of being selected - regardless of the unknown total $ N $. Why this is remarkable The alchemist achieves a perfectly uniform random sample from a stream of unknown length using only $ O(1) $ memory (a single vial slot). This is the $ K=1 $ case of Reservoir Sampling, which generalizes to selecting $ K $ items uniformly from a stream of unknown size.