Floyd’s Sampling Algorithm

Definition

Floyd’s sampling algorithm draws a uniformly random subset of size k from {1,\dots,n} without shuffling the entire range. One standard form is:

$$\text{for }i=n-k+1,\dots ,n:t\sim \mathrm{Unif}\{1,\dots ,i\},S\leftarrow \{\begin{array}{ll}S\cup \{i\}& \text{if }t\in S\\ S\cup \{t\}& \text{otherwise}\end{array}$$

starting from S=\varnothing.

Why It Matters

It gives an exact uniform k-subset using only k iterations and O(k) storage, which makes it attractive when k is much smaller than n and a full permutation or repeated rejection would be wasteful.

Formalism / Key Objects

• Input parameters: population size n and sample size k.
• State: a set S of selected items.
• Invariant: after processing up to i, the set corresponds to a uniformly random sample of the needed size from the prefix range.
• Interpretation: the procedure can be viewed as the last k swaps of an upward Fisher-Yates shuffle, with the sampled set given by the tail.
• Floyd Sampling Correctness records the induction proof and Fisher-Yates equivalence.

Connections

• Lives under Algorithms and Data Structures as a compact exact sampling primitive.
• Related to partial shuffling, reservoir sampling, and other randomized subset-selection procedures, even though the update rule looks less intuitive than those alternatives.
• Useful as a worked example of how randomized algorithms can hide a clean permutation argument behind a strange local branch.
• Floyd Sampling Correctness is the focused annex for the uniformity proof.

Common Confusions

• The branch on t in S does not bias the sample; it is exactly what preserves distinctness while maintaining uniformity.
• The algorithm samples without replacement, not a sequence with replacement.
• It avoids a full shuffle, but that does not make it approximate; the resulting subset is exact.
• The easiest proof intuition may come from Fisher-Yates rather than from direct simulation.

Key Sources

• Jaffray2026 - Floyd’s Sampling Algorithm