Admin: Replaced em dashes with regular dashes (via update-page on MediaWiki MCP Server)

2026-06-24T17:42:44Z

Replaced em dashes with regular dashes (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 17:42, 24 June 2026
Line 3:		Line 3:
	\|problem=		\|problem=

	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.		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'''?		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)		(Source: Donald Knuth, ''The Art of Computer Programming, Volume 2: Seminumerical Algorithms'' - Algorithm R, Reservoir Sampling)

	\|solution=		\|solution=
Line 42:		Line 42:
	</math>		</math>

	Since this holds for every <math>k</math>, all <math>N</math> vials have an equal probability <math>\tfrac{1}{N}</math> of being selected — regardless of the unknown total <math>N</math>.		Since this holds for every <math>k</math>, all <math>N</math> vials have an equal probability <math>\tfrac{1}{N}</math> of being selected - regardless of the unknown total <math>N</math>.

	=== Why this is remarkable ===		=== Why this is remarkable ===

Admin: Created FMM22: The Cautious Alchemist's Vial (Reservoir Sampling / Algorithm R) (via create-page on MediaWiki MCP Server)

2026-06-24T17:38:37Z

Created FMM22: The Cautious Alchemist's Vial (Reservoir Sampling / Algorithm R) (via create-page on MediaWiki MCP Server)

New page

{{FMM
|title=The Cautious Alchemist's Vial
|problem=

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 <math>N</math> (unknown to the alchemist ahead of time). Label the vials <math>1, 2, \dots, N</math> in the order they appear.

=== Strategy (Algorithm R for <math>K=1</math>) ===

When the <math>k</math>-th vial appears, the alchemist keeps it with probability <math>\tfrac{1}{k}</math>, discarding whatever vial he was holding previously. Otherwise (with probability <math>1 - \tfrac{1}{k}</math>), he ignores it and keeps whatever he is already holding.

=== Proof that every vial is equally likely ===

We claim that each vial <math>k</math> (where <math>1 \leq k \leq N</math>) ends up as the final chosen vial with probability exactly <math>\tfrac{1}{N}</math>.

For vial <math>k</math> to be the final choice, two things must happen:

# The alchemist must '''keep''' vial <math>k</math> when it appears, which happens with probability <math>\tfrac{1}{k}</math>.
# He must '''not keep''' any subsequent vial <math>k+1, k+2, \dots, N</math>.

The probability of '''not''' keeping vial <math>k+1</math> is <math>1 - \tfrac{1}{k+1} = \tfrac{k}{k+1}</math>.

The probability of not keeping vial <math>k+2</math> is <math>\tfrac{k+1}{k+2}</math>, and so on.

Thus, the probability that vial <math>k</math> is the final choice is:

<math>
P(k) = \frac{1}{k} \cdot \frac{k}{k+1} \cdot \frac{k+1}{k+2} \cdot \dots \cdot \frac{N-1}{N}
</math>

Every numerator cancels with the denominator of the following fraction (a telescoping product), leaving:

<math>
P(k) = \frac{1}{N}
</math>

Since this holds for every <math>k</math>, all <math>N</math> vials have an equal probability <math>\tfrac{1}{N}</math> of being selected — regardless of the unknown total <math>N</math>.

=== Why this is remarkable ===

The alchemist achieves a perfectly uniform random sample from a stream of '''unknown length''' using only <math>O(1)</math> memory (a single vial slot). This is the <math>K=1</math> case of '''Reservoir Sampling''', which generalizes to selecting <math>K</math> items uniformly from a stream of unknown size.

}}

FMM22 - Revision history

Admin: Replaced em dashes with regular dashes (via update-page on MediaWiki MCP Server)

Admin: Created FMM22: The Cautious Alchemist's Vial (Reservoir Sampling / Algorithm R) (via create-page on MediaWiki MCP Server)