Why the Naive Shuffle Is Biased

A common interview question asks you to write a shuffle function, and a common wrong-but-plausible answer is: for each position in the array, swap it with a position chosen uniformly at random from the entire array (not just the remaining unshuffled positions). It looks reasonable — every position gets a random swap — but it does not produce a uniform distribution over all $n!$ permutations, and the bias is provable by simple counting.

The naive algorithm makes $n$ independent random choices, each with $n$ possible outcomes, so it can produce at most $n^n$ distinct execution paths. But there are only $n!$ possible permutations to land on. Since $n^n$ is not generally divisible evenly by $n!$ for $n>2$, some permutations must be reachable by more execution paths than others, meaning some orderings come out more often than others — a bias that grows quickly with $n$ and shows up clearly even for a deck as small as 3 or 4 cards if you simulate it many times.

The fix is the Fisher-Yates shuffle: for each position from the last down to the second, swap it with a uniformly random position chosen only from the remaining unshuffled prefix (positions 1 through the current one), not the whole array. That algorithm makes exactly $n, n-1, \ldots, 2$ independent choices, giving exactly $n!$ equally likely execution paths — one for every permutation, with no bias possible by construction.