skip to content

questions

4

In a shuffle, why is swapping each element with a uniformly random index biased?

level: juniorimportance: must knowfreq 58%

answer

  1. count the random draws, not the swaps
  2. each draw picks from all n slots
  3. how many orderings exist at all?
  4. divide n^n by n! and look
  5. unequal buckets of paths, by pigeonhole

basics

~10 s

The 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 s

Count 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
pseudocode
// 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

for a junior

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.

for a middle

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.

for a senior

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.

for a principal

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.

  • 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

context

open as a page

In reservoir sampling over a stream of unknown length, why keep item i with probability k/i?

level: middleimportance: should knowfreq 44%

basics

~20 s

Keeping the i-th item with probability k/i, and evicting a uniformly chosen resident, holds the invariant that after i items each is held with probability k/i. That holds at every prefix, so the length is never needed.

open as a page

Why does choosing a partition pivot at random help when the worst case is still O(n^2)?

level: seniorimportance: should knowfreq 50%

basics

~20 s

Randomizing moves the bad case from the input to the coin. The worst-case bound is unchanged, but no fixed input triggers it reliably any more: expected cost becomes good for every input, not only for inputs assumed to be unordered.

open as a page

In a billing pipeline, when is a Monte Carlo algorithm's error probability unacceptable but a Las Vegas one's variable runtime fine?

level: principalimportance: nice to knowfreq 26%

basics

~20 s

A Las Vegas algorithm is always correct with variable runtime; a Monte Carlo one has bounded cost and a chance of being wrong. Figures that must reconcile exactly can absorb a late finish, never a wrong number.

open as a page