Fisher-Yates Shuffle: A Visual Proof

I have found great visualization of the fisher-yates shuffling algorithm, but I have yet to find a great visualization of the proof that the fisher-yates shuffle is random.

What do we mean by a random shuffle? We mean uniformly random - that each element in the list could be shuffled into each position with equal probability.

How frequently should the element e_i be shuffled into the position j? 1 in n times. Or position k? Also 1 in n times. Each element in each position 1 out of n times.

Algorithm

The fisher-yates algorithm shuffles a list with the following steps:

1. swap the last element, e_n, with the element e_i at a random position i.
2. repeat/recurse step 1 on the sublist from e₀ to e_n-1.
3. stop when the list you are shuffling only has a single element or less.

in python the code looks like:

a = [ ... ]
for i in range(len(a) - 1, 0, -1): # n-1, n-2, n-3, ... 1
    j = random.randint(0, i)
    a[i], a[j] = a[j], a[i]

Simple, no? The animation of an example shuffle is also pretty simple. We start with the last element, swap (possibly into the same position), then fix the last element in position and move on to the next position for swapping.

Visual Proof

In the visualization above, we were only demonstrating one possible shuffle each time. What if we considered all possible swaps at each iteration and kept track of the probability each element was in each position? If a shuffle was truly random then each element, represented by color, should result in each position equally after shuffling the whole list.

In the visualization below, we highlight two positions before considering the swap. Colors represent elements. Each row represents the result of an iteration. A multicolored square means for that specific position we had a certain probability of being those elements, proportional to area of the color. After an iteration we stop considering the last element, hence the diagonal shape. After each iteration you can sort of see that the last position has equal chance to be any element. Once we are done iterating we simplify the visual probabilities in each position and collapse the diagonal. You can easily see that algorithm results in each element possibly being moved to each position with uniform probability.