Saturday, August 03, 2019

[sdkrxckb] Shuffling cards using coin flips

Several possible methods:

  1. For each card, deal it into one of two stacks with a coin flip for each card.  When finished, combine the two stacks by putting one stack on top of the other in a deterministic order.  I think this is the inverse of a Gilbert-Shannon-Reeds riffle shuffle, so repeat 7 times to shuffle a standard deck.

  2. Slight sophistication: when combining the two stacks in #1, flip the coin to determine which stack goes on top.

  3. Apply recursion: first assign cards to 2 stacks with a coin flip for each card, same as the first step of #1.  Then, recursively do the same thing for each half-stack, assigning cards into 4 smaller stacks.  When down to 1 card in the leftmost stack, add it to the top of the "finished" stack.  This is equivalent to sorting cards with each card's sort key an infinite precision random real number between 0 and 1 expressed in binary, where bits are generated on demand to break ties.  Therefore, one round is enough for uniform randomness.

  4. The motivation was to improve upon naively doing the Fischer-Yates algorithm when the source of randomness is random bits.  For Fischer-Yates, one would convert random bits into a uniform random integer between 1 and N (N changes over the course of the algorithm) with first a binary-to-decimal lookup table and then rejection sampling.

  5. We also considered methods like #1 but which initially assigned cards to 2^N stacks with N coin flips per card, then various recursive ways of combining 2^N stacks into 1.  However, these methods were unwieldy compared to #3.

No comments :