Proof for Particular Fair Shuffle Algorithm

Question

I ran multiple simulations of the following function, and it seems to be fair shuffling, given that all permutations were roughly equal, but I don't understand why it works. It's just inserting at random positions within the current shuffled deck isn't it? I know about Fisher-Yates shuffling, for reference.

def shuffle_deck(deck):
    shuffled_deck = []
    for card in deck:
        r = random.randint(0, len(shuffled_deck))
        shuffled_deck.insert(r, card)
    return shuffled_deck

I was expecting that it would be uneven probability permutation.

Answer 1

One way of showing this is to consider the set of possible paths through the code. Note that at step $i$, a random number between $0$ and $i$ is chosen to determine where to insert the next card. This gives us $1\cdot2\cdot3\cdots\cdot n=n!$ different paths through the code, and each path clearly corresponds to a different permutation. Contrariwise, it's possible to run the algorithm 'in reverse'; for each $i$ from $n$ downward, look at the position of $i$ within the subpermutation of the shuffled permutation consisting of only the elements $1..i$ .

Answer 2

... I don't understand why it works. It's just inserting at random positions within the current shuffled deck isn't it?

Imagine this. You have a deck of cards kept in front of you. You spread out one of your hands so you can create a deck on it. You reach out, pick the card at the top and place it on your hand.

You reach out to the deck, and once again, pick the card on top. This time before placing the card on my hand, you think of a number (randomly) between $0$ and the $1$ (the number of cards I have already placed), both inclusive. Whatever number you think of, you place the new card below that many card(s) from the top. For example, if your number for $0$, the new card would go on top. If the number was $1$, it will be placed after the first card from the top.

You repeat this process for all the remaining cards in the original deck. In the end, you will have a well shuffled deck in your hand, no?

This is essentially what your algorithm is doing.

Answer 3

This is (almost) the same as the Fisher-Yates shuffle, but with less optimization.

The Fisher-Yates shuffle can be thought of as performing the following (high-level, conceptual) steps:

1. Make a new, empty list that will eventually be the output.
2. Repeatedly select a random element from the input list.
3. Remove the random element from the input list.
4. Add the random element to the output list (at the beginning or end).

However, Durstenfeld made a simple optimization: Instead of making a separate output list, he moves the elements to the beginning or end of the input list, and treats that portion of the input list as the output list. Then, the other optimization is to swap things instead of moving them (so that we don't have to shift everything over all the time). As a side effect, this causes whichever element was at the front or back of the input list to be moved into the position where the random element used to be. But that makes no difference to the overall shuffling algorithm (exercise for the reader: why not?).

The algorithm you demonstrate is almost the same, except instead of selecting a random element from the input list, you select a fixed element, and insert it into a random position in the output list. We can show by induction that this is fair:

1. Base case: If the input list is empty, then the output list is empty, and that's the only possible permutation, so it must be fair.
2. Inductive step: Assume the algorithm is correct for $k$ elements (with $k \ge 0$). Then, when we run it on $k+1$ elements, the first $k$ iterations of the loop are exactly equivalent to running the algorithm for the first $k$ elements of the input list. So at that point, the output list has a uniformly distributed permutation of $k$ elements, and we then insert a new element in one of the $k+1$ possible positions, uniformly at random. This produces a uniformly distributed permutation of $k+1$ elements.