Floyd’s Sampling Algorithm

Summary

This partial ingest is based on a clipped newsletter post by Justin Jaffray. It explains Floyd’s sampling algorithm for selecting a uniformly random k-subset of {1,\dots,n} without shuffling the whole range, and gives two intuitions for why the branching rule preserves uniformity.

Key Claims

• Floyd’s algorithm samples a uniformly random subset of size k from {1,\dots,n} using only k iterations and O(k) stored elements.
• The algorithm’s branch if t in s: add(i) else add(t) looks unintuitive but still yields the correct uniform distribution over k-subsets.
• One proof intuition is a counting argument that each (k+1)-subset has exactly (k+1) preimages under the incremental update.
• Another intuition is that the algorithm is equivalent to executing only the last k swaps of an upward Fisher-Yates shuffle and then taking the tail.

Methods / Formalism

• Initialize an empty set S.
• For i = n-k+1, \dots, n, sample t uniformly from {1,\dots,i}.
• If t \in S, insert i; otherwise insert t.
• Return S, which has size k and is uniformly distributed over all k-subsets of {1,\dots,n}.
• See Floyd Sampling Correctness for the reusable induction argument and Fisher-Yates equivalence.

Evidence / Experiments

• The post is explanatory rather than empirical and focuses on proof intuition.
• Its value is in the two complementary derivations: a combinatorial preimage-count argument and a reduction to the final swaps of Fisher-Yates.
• It does not benchmark runtime or memory formally, but the algorithmic advantage is clear when k \ll n and a full shuffle would be unnecessary.

Connections

• Core source for Floyd’s Sampling Algorithm.
• Floyd Sampling Correctness records the formal uniformity argument without overloading this source note.
• Fits under Algorithms and Data Structures as a compact randomized algorithm for exact subset sampling.
• Useful next to other sampling and shuffling procedures because it shows how a non-obvious local branch can still implement a globally uniform distribution.

Open Questions

• When is Floyd’s algorithm preferable to reservoir sampling, rejection sampling, or partial Fisher-Yates in practice?
• Which proof style is most reusable for explaining other randomized algorithms that disguise a permutation argument?
• Should the wiki add a broader note on randomized sampling algorithms once more examples accumulate?

Citation

Jaffray, J. (2026). Floyd’s Sampling Algorithm. NULL BITMAP.