Shuffle a poker deck between 4 players, with least required entropy

Question

We are shuffling a standard poker deck of 52 cards between 4 players, each getting 13 cards. The order of cards for a particular player does not matter.

A naive algorithm is to first shuffle the whole deck, then split it into 4 parts. However, this requires $log_2(52!) \approx 226$ bits of entropy.

Combinatorics says that such a shuffle should only require $log_2(52! / 13! / 13! / 13! / 13!) \approx 96$ bits of entropy, more than half less.

What is the algorithm that would produce such an efficient shuffle, using a random generator that produces integers in a range?

I was thinking of this algorithm:

• Start with a sorted deck, for each card:
  1. generate a number between 1 and 4, to determine which player the card goes to.
  2. once one of the players gets 13 cards, only generate numbers between 1 and 3 (and so on)
  3. Stop when only one player remains, give them all undealt cards

Would such algorithm produce an unbiased deal, and if not, what is the correct one?

Answer 1

Your approach won't work because: Let's suppose that the descks have $13-a$, $13-b$, $13-c$, $13-d$ cards respectively. You can assign the rest of the cards in $\frac{(a+b+c+d)!}{a!b!c!d!}$ ways. If you assign the card to the first deck, you can assign the rest in $\frac{(a+b+c+d-1)!}{(a-1)!b!c!d!}$ ways. For the second deck, it is $\frac{(a+b+c+d-1)!}{a!(b-1)!c!d!}$. $\frac{(a+b+c+d-1)!}{a!b!(c-1)!d!}$ for third deck and $\frac{(a+b+c+d-1)!}{a!b!c!(d-1)!}$ for fourth deck. Therefore, you can't assign the next card with equal probabilities. You can easily figure out that the ratio of the probabilities has to be $a:b:c:d$. The easiest way to choose one deck with these probabilities is choosing a random integer from $1$ to $a+b+c+d$ and then look in which deck it falls. The upper bound for your random generator starts at 52 and drops by 1 each time you assign a card to a deck. Now the bits of entropy is: $\sum_{i=1}^{52}log_2(i) = log_2(52!)$. So if you fix your algorithm this way, you are back at the naive generator.

You can do it this way:

1. generate a random number $k$ between $1$ and $\frac{52!}{13!13!13!13!}$.
2. set $a,b,c,d:=13$, $u:=\frac{52!}{13!13!13!13!}$
3. if all cards are assigned to a deck, end.
4. set $g:=\frac{u}{a+b+c+d}$
5. if $k \leq ga$ put card to first deck, set $a:=a-1$, $u:=ga$, return to step 3
6. else if $k \leq g(a+b)$ put card to second deck, set $b:=b-1$, $u:=gb$, $k:=k-ga$, return to step 3
7. else if $k \leq g(a+b+c)$ put card to third deck, set $c:=c-1$, $u:=gc$, $k:=k-g(a+b)$, return to step 3
8. else put card to fourth deck, set $d:=d-1$, $u:=gd$, $k:=k-g(a+b+c)$, return to step 3

It is basically the same with the exception that you don't generate a new number in each step, but you decide according to a number which you generate at the beginning. It is basically an unrank function for permutations with repetitions.