Floyd Sampling Correctness
Context
Jaffray2026 - Floyd’s Sampling Algorithm explains Floyd’s exact subset-sampling procedure and gives two proof intuitions: a combinatorial preimage count and an equivalence to the final swaps of Fisher-Yates. This annex keeps the correctness argument separate from the concept note while leaving Floyd’s Sampling Algorithm with the executable rule.
Formal Statement
For integers 0 <= k <= n, initialize S = \varnothing. For each
sample t uniformly from {1,\dots,i} and update
After the final iteration, S is uniformly distributed over all k-subsets of {1,\dots,n}:
for every A \subseteq {1,\dots,n} with |A|=k. The procedure performs k iterations and stores O(k) selected elements.
Derivation / Construction
Let m = i - (n-k) be the sample size after processing index i. The inductive invariant is:
for every m-subset B of {1,\dots,i}.
Assume the invariant holds before processing i, so the previous set is uniform over (m-1)-subsets of {1,\dots,i-1}. Fix an m-subset B of {1,\dots,i}.
If i in B, the only previous set is C = B \setminus \{i\}. The update reaches B when t=i or when t in C, giving m successful choices among i equally likely values:
If i notin B, the update reaches B by choosing one element t in B and using previous set B \setminus \{t\}. There are again m successful predecessor-choice pairs:
Thus every m-subset is equally likely at each step, and the final step gives uniformity over k-subsets of {1,\dots,n}.
The Fisher-Yates view gives the same result operationally: Floyd’s rule can be read as computing only the last k effective placements of an upward shuffle, then returning the tail set without materializing the full permutation.
Implications
- The branch on
t in Sis what preserves both distinctness and uniformity. - Floyd sampling is exact rather than approximate, even though it avoids a full shuffle.
- The method is most useful when
k << nand the returned object is an unordered subset.