Visual Proof of the Fisher-Yates Shuffle

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

What do we mean by random? One way to prove a shuffle is (uniformly) random is to show that every element has equal probability of being shuffled to every position, including the original position.

e0, ..., ei, ..., en p(i->j) = 1/n position 0, position 1, ..., position j, ..., position n-2, position n-1


While it may not be obviously random, the fisher-yates algorithm shuffles a list with the following steps:

  1. swap the last element, en, with the element ei at a random position i.
  2. repeat on elements from e0 to en-1. In software we call those remaining elements the sublist from 0 to n-1.


First Proof

In the visualization above, we are only demonstrating one possible shuffle. What if we considered all swaps and kept track of the probability each element was in each position? If a shuffle was truly random then each element (color) should occur in each position equally after shuffling.

In the visualization below, we highlight two positions before considering the swap. Colors represent elements. After an iteration we stop considering the last element, hence the diagonal shape.