<story><title>Zero Tolerance for Bias</title><url>https://queue.acm.org/detail.cfm?id=3664645</url></story><parent_chain></parent_chain><comment><author>IAmLiterallyAB</author><text>Interesting, but there&amp;#x27;s one part I&amp;#x27;m not sure I agree with.&lt;p&gt;&amp;gt; Pseudo-random number generators are useful for many purposes, but unbiased shuffling isn&amp;#x27;t one of them.&lt;p&gt;A properly seeded CSPRNG is perfectly fine at this. And if it&amp;#x27;s not, then all of our cryptography is pretty much screwed. This is why in modern kernels, &amp;#x2F;dev&amp;#x2F;random and &amp;#x2F;dev&amp;#x2F;urandom are the same (minus differences in behavior when the initialization isn&amp;#x27;t complete). As D.J. Bernstein put it, it&amp;#x27;s superstition to not trust CSPRNGs. &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.mail-archive.com&amp;#x2F;cryptography@randombit.net&amp;#x2F;msg04763.html&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.mail-archive.com&amp;#x2F;cryptography@randombit.net&amp;#x2F;msg0...&lt;/a&gt; And if it&amp;#x27;s good enough for crypto, it&amp;#x27;s good enough for card shuffling.&lt;p&gt;FYI I am not a cryptographer</text></comment>
<story><title>Zero Tolerance for Bias</title><url>https://queue.acm.org/detail.cfm?id=3664645</url></story><parent_chain></parent_chain><comment><author>orlp</author><text>Here is a trivial shuffle algorithm that is completely unbiased and only requires an unbiased coin (or random number generator giving bits):&lt;p&gt;1. Randomly assign each element to list A or list B.
2. Recursively shuffle lists A and B.
3. Concatenate lists A and B.&lt;p&gt;To prove it&amp;#x27;s correct, note that assigning a random real number to each element and sorting based on that number is an unbiased shuffle. Then we note the above does in fact do that by considering the fractional base-2 expansion of the random numbers, and noting the above is in fact a base-2 radix sort of these numbers. We can sort these random real numbers even though they have an infinite amount of random bits, as we can stop expanding the digits when the prefix of digits is unique (which corresponds to the event that a list is down to a single element).&lt;p&gt;I call the above algorithm RadixShuffle. You can do it in base-2, but also in other bases. For base-2 you can make it in-place similar to how the partition for Quicksort is implemented in-place, for other bases you either have to do it out-of-place or in two passes (the first pass only counting how many elements go in each bucket to compute offsets).&lt;p&gt;The above can be combined with a fallback algorithm for small N such as Fisher-Yates. I believe even though the above is N log N it can be faster than Fisher-Yates for larger N because it is exceptionally cache-efficient as well as RNG-efficient whereas Fisher-Yates requires a call to the RNG and invokes an expected cache miss for each element.&lt;p&gt;---&lt;p&gt;Another fun fact: you can turn any biased memoryless coin into an unbiased one with a simple trick. Throw the coin twice, if it gives HH or TT you throw away the toss, if it&amp;#x27;s HT or TH you use the first toss as your unbiased coin.&lt;p&gt;This works because if p is the probability that heads comes up we have:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    HH: p^2
    HT: p(1-p)
    TH: (1-p)p
    TT: (1-p)^2
&lt;/code&gt;&lt;/pre&gt;
Naturally, p(1-p) and (1-p)p are equiprobable, thus if we reject the other outcomes we have distilled an unbiased coin out of our biased coin.</text></comment>