Exact Online Rank Recycling in Floyd's Uniform Subset Sampler

Abstract

A uniformly random $m$-subset of $[n]=\{0,\dots ,n-1\}$ has entropy ${\log }_2\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. Standard without-replacement procedures often expose an additional ordering coordinate that is absent from the returned set. We show that Floyd's subset sampler admits an exact round-local factorization of this coordinate. In round $r$, let $S$ be an $(r-1)$-subset of $[j]$, let $T\sim \mathrm{Unif}([j+1])$, and let $S^{\prime }$ be the result of Floyd's transition. If $D$ is the zero-based rank of the original draw $T$ in $S^{\prime }$, then $(S,T)\leftrightarrow (S^{\prime },D)$ is a bijection between $\left(\genfrac{}{}{0ex}{}{[j]}{r-1}\right)\times [j+1]$ and $\left(\genfrac{}{}{0ex}{}{[j+1]}{r}\right)\times [r]$. Consequently, $S^{\prime }$ and $D$ are independent and uniform on their respective spaces. The digit $D$ can therefore be merged immediately into a residual uniform random state; an induction shows that the partial subset remains independent of that state after every round. For $k=\min (m,n-m)$, the sampling phase uses $O(k\log k)$ time and $O(k)$ auxiliary space with an order-statistic tree; explicitly materializing a complement incurs the unavoidable output cost. The combinatorial layer avoids binomial-coefficient arithmetic and recovers the complete $k!$ state-space factor exactly. We also give a finite counterexample showing that analogous immediate rank recycling in a partial Fisher-Yates array is invalid because the unselected suffix retains a correlated ordering. A 64-bit Rust implementation is checked by exhaustive state-space enumeration for all $n\le 8$ and by an entropy-accounting trace for choosing $20,000$ of $30,000$ items. We make no claim of runtime superiority over existing subset samplers.

arXiv comment12 pages, 0 figures, 2 algorithms, 2 tables. Rust implementation and exact finite-state tests: https://github.com/yingqi-z20/entropy-pool/tree/v1.0.0