= Uniform balanced binary sequence sampling
A balanced <binary sequence> of length $2n$ has $n$ entries of each kind. Uniformly sample an $n$-element <subset> of the positions and place the first kind there. If $2n$ is a power of two, repeatedly draw uniform positions using $\log_2(2n)$ fair random <bits>, reject previously selected positions, and stop after $n$ distinct positions. Each new position is uniform among those remaining, making every $n$-element <subset> equally likely. The expected number of draws is $\sum_{s=0}^{n-1}2n/(2n-s)<2n$, giving $O(n\log n)$ expected random <bits>.
Back to article page
