Shuffle a poker deck between 4 players, with least required entropy 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:

*

*generate a number between 1 and 4, to determine which player the card goes to.

*once one of the players gets 13 cards, only generate numbers between 1 and 3 (and so on)

*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?

Let's approach this problem backward.
So shuffle the deck, deal the cards, have each player sort their hand.
From this state, how much information can we gather?
As you already pointed out, we cannot retrieve the order of the deck after shuffling, before dealing. A shuffled deck contains more information than four hands of cards.
So how much information is there?
For simplicity, we call the cards just card $1$, card $2$, etc.
Imagine, each player sorted their hands and put the cards in front of them, face down, the lowest card on top.
Then we know, that one of the top cards must be card $1$, and the probability is $1/4$ for each one. So the question "Which hand contains card $1$?" is like rolling a four-sided fair dice.
Let us say, Player 1 had card 1. We remove the card from their stack and ask "Which hand contains card 2?". Again, it must be one of the top cards, but the probabilities are no longer equal since Player 1 has just 12 cards while the others have 13. So this question is equivalent to rolling four-sided dice, where one side has a slightly lower probability.
We can continue asking for each card in turn to retrieve as much information as we can.
Reverting this process gives us a means of distributing the cards:
Take a fair four-sided dice, label the sides Player 1 to Player 4.
Roll the dice and give card 1 to the respective player.
Then adjust the probabilities of the dice to 12/51 for the player with card 1 and 13/51 for the others.
Continue rolling and adjusting until all cards have been distributed.
To sum up, we have a means of distributing the cards and a way of looking at a dealt deck containing the same information, so the distribution method should be optimal in this sense.
