Shuffling algorithm analysis

Question

I came across this following analysis of shuffling algorithms:

Q: Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely. In other words, given a deck of cards, how can you shuffle them such that any permutation of cards is equally likely?

Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time. Note that there are several possible solutions to this problem, as well as several good‐looking answers that are incorrect. For example, a slight modification to the above algorithm whereby one switches each element with any element in the array does not give each reordering with equally probability.

What I would like to know is why switching each element with any other element in the array does not produce a good shuffle as opposed to using the Knuth shuffle (which is described). Also, how does the Knuth shuffle select values with equal probability? Any math or proof is greatly appreciated.

Answer 1

The easiest proof that this algorithm does not produce a uniformly random permutation

for (int i = 0; i < 3; ++i) {
   swap(a[i], a[rand() % 3]);
}

Is that it generates 27 possible outcomes, but there are only 3! = 6 permutations. Since 6 does not divide 27, there must be some permutation is that is picked too much, and some that is picked to little.

Why is an O(n) algorithm optimal? Well, a random shuffle must touch every input sometimes (to change them), so any optimal algorithm needs to do at least O(n) work.

Why is the Knuth algorithm correct? That requires a little bit more insight. You can prove via induction that the first item is selected with the correct probability (each item is equally likely to be first), and then prove that the inductive step holds as you advance through the loop, that the second, third, etc items are also selected with the correct probability from the remaining portions of the array.