In a shuffle, why is swapping each element with a uniformly random index biased?
answer
- count the random draws, not the swaps
- each draw picks from all n slots
- how many orderings exist at all?
- divide n^n by n! and look
- unequal buckets of paths, by pigeonhole
basics
~10 sThe naive loop has n^n equally likely execution paths but only n! orderings, and n! does not divide n^n. Some orderings therefore come out more often than others, however good the random source is.
solid answer
~50 sCount the paths, not the swaps. Looping over every position and swapping it with a uniformly random index drawn from the whole array makes n independent choices among n options, so the procedure has exactly `n^n` equally likely execution paths. There are only `n!` orderings, and for n above two `n!` never divides `n^n` evenly, so the paths cannot be shared out equally — some permutations are strictly more likely than others. With n = 4 the counts run from 8 to 15 out of 256, close to a factor of two. The fix is Fisher-Yates: walk the index from the last position down to the first and swap it with a uniform choice from the shrinking prefix `[0, i]`. That yields exactly `n!` paths, one per ordering, in the same O(n) time and O(1) extra space. The bias is not a rounding artefact; it is systematic and users notice the repeated orderings.
code
pseudocode · 9 lines// naive: partner drawn from the whole array, every step
for i in 0..n-1:
j = random_int(0, n-1)
swap(a[i], a[j])
// Fisher-Yates: partner drawn from the shrinking unsettled prefix
for i = n-1 downto 1:
j = random_int(0, i) // inclusive, j == i is allowed
swap(a[i], a[j])go deeper
Be ready to write the correct loop and say what makes it correct: each step chooses from the positions not yet fixed. Know that swapping every position with an index drawn from the whole array is the classic wrong version.
Expect to give the counting argument out loud: n independent draws over n options make n^n paths, orderings number n!, and n! does not divide n^n above n = 2. Be able to work the three-element case by hand.
Show how you would catch this in review or in production: tally whole orderings at small n rather than checking one element's landing spot, and treat the shuffle as testable code with an injectable, recorded seed.
Own where uniformity actually matters. A prize draw or an experiment assignment needs an auditable uniform shuffle; a play queue may deliberately be non-uniform to avoid clustering. Name which contract the product is buying, and write it down.
## What "uniform" actually claims A shuffle is uniform when every one of the `n!` orderings of the input is equally likely. That is a statement about **whole orderings**, not about where any single element lands. Nearly every broken shuffle in the wild survives because its author checked the second thing and concluded the first. ## The two loops The naive version walks every position and swaps it with a random index chosen from the entire array: ``` for i in 0..n-1: j = random_int(0, n-1) swap(a[i], a[j]) ``` Fisher-Yates walks from the end and draws only from the part that is not yet settled: ``` for i = n-1 downto 1: j = random_int(0, i) swap(a[i], a[j]) ``` They differ in one character's worth of range, and that range is the whole argument. ## The counting argument The naive loop makes `n` independent draws, each with `n` outcomes, so it has `n^n` equally likely execution paths. Every path produces some ordering, and there are `n!` orderings. If the result were uniform, each ordering would be produced by exactly `n^n / n!` paths — an integer. But `n!` does not divide `n^n` for any n above two: by Bertrand's postulate there is a prime p strictly between n/2 and n, so p divides `n!` while p does not divide n and therefore does not divide `n^n`. The division is not exact, so the paths cannot be shared out equally. Some orderings get more paths than others, and no improvement to the random source can repair it — the defect is arithmetic, not statistical. Small cases make it concrete. For n = 3 there are 27 paths over 6 orderings, distributed as 4, 4, 4, 5, 5, 5 — one ordering arrives 25% more often than another. For n = 4 there are 256 paths over 24 orderings, with counts ranging from 8 to 15, so the most likely ordering is nearly twice as likely as the least. The skew does not politely fade as n grows. ## Why Fisher-Yates is exactly uniform Run the loop downward and hold this invariant: when the index reaches position i, positions above i already hold their final occupants, and every one of the remaining i+1 elements is equally likely to be sitting in each of the remaining slots. The step draws one of those i+1 candidates uniformly and fixes it into position i. The draw sizes are n, n-1, ..., 2, so the number of execution paths is exactly `n!` — and distinct paths produce distinct orderings, because each path pins down a different sequence of "which element ends up here". A bijection between equally likely paths and orderings is precisely uniformity. The mirrored version walking upward and drawing from the suffix `[i, n-1]` is equally correct; the invariant is the same, only the settled end moves. One boundary matters: the draw must include the possibility of no move, `j == i`. Excluding it — drawing from `[0, i-1]` — is a different, also-famous algorithm (Sattolo's), which is uniform over the `(n-1)!` **cyclic** permutations only. Every element moves, no element stays put, and if you wanted a fair shuffle you have quietly shipped a biased one. ## Why "it looks random" survives review The cheap test is to shuffle many times and check that a chosen element lands in each position about equally often. The naive loop passes that test perfectly for the first element — in the exhaustive n = 3, 4 and 5 cases the first element's landing index is *exactly* uniform, while whole orderings differ by up to a factor of two. A marginal distribution constrains one row of the picture; uniformity is a claim about the whole thing. To test a shuffle honestly, pick a small n where all `n!` orderings are observable, tally full orderings across many runs, and compare against the expected count. ## Cost and consequences Both loops are O(n) time, O(1) auxiliary space, one random draw per step. The bias is not bought with speed — it is free of charge and buys nothing, which is what makes it a pure defect. Where it bites depends on what the ordering means: a non-uniform prize draw or experiment assignment is a fairness and audit problem, while a non-uniform play queue is a user complaint about hearing the same run of tracks. Two further sources of non-uniformity sit underneath the algorithm. Reducing a raw random value into a range with a plain remainder skews the low end of the range unless you reject and redraw. And a generator whose internal state is smaller than `n!` outcomes cannot possibly reach every ordering — for a 52-element deck, `52!` is about 8 × 10^67, so a 32-bit seed reaches a vanishing fraction of the orderings no matter how correct the shuffle loop is.
- How would you detect this bias empirically, without proving anything?Pick an n small enough that all n! orderings are observable — three or four elements — run the shuffle a few hundred thousand times and tally complete orderings, then compare the counts against the uniform expectation. Do not check where a single element lands: the naive loop gives an exactly uniform marginal for the first element while whole orderings differ by nearly a factor of two.
- Does Fisher-Yates still work if you walk forward instead of backward?Yes. The mirrored form walks the index from the first position to the second-to-last and draws the partner from the suffix `[i, n-1]`. The invariant is unchanged — each step picks the occupant of the current position from the elements not yet placed — so it is also exactly uniform. The broken variant is the one that draws from the whole array regardless of where the index sits.
- Where does the random source itself become the weak point?Uniformity assumes independent uniform draws. Reducing a raw random value into a range with a plain remainder over-weights part of the range unless you reject and redraw. And a generator whose state space is smaller than n! simply cannot produce every ordering — for a 52-element deck there are about 8 x 10^67 orderings, far beyond what a 32-bit seed can index.
It is the difference between stirring a deck n times and dealing it out: stirring can pick up the same card again and again, while dealing removes each card from the pool the moment its final place is fixed.
saying these in an interview costs you the question
- Both versions look random, so both are fine
- A better random generator removes the bias
- Every element can reach every position, so it is uniform
- Handing a sort a comparator that returns random results shuffles correctly
- The bias is theoretical and never visible in production