Lesson · Randomised Algorithms · Randomness as a resource

Uniform Sampling, and the Shuffle That Is Not

A shuffle that looks right and is wrong is the cleanest introduction to this course, because the distribution it produces is small enough to write down completely. The naive swap on four items has 256 equally likely runs and 24 possible answers, and 24 does not divide 256. That single remainder refutes uniformity before any run happens, and the enumeration then shows exactly how far off it is.

Open the interactive lesson Practice

a TAPE is one complete run: the sequence of draws the algorithm made Fisher–Yates draws j in 0..i going down n! tapes, one per permutation the naive swap draws j in 0..n−1 every time nⁿ tapes, n! permutations n = 4: 256 tapes, 24 permutations, 256 = 24·10 + 16 so some permutation gets more tapes than another, whatever a sample shows total variation from uniform: 25/384, exactly

Two shuffles, and the counting argument that separates them

Core ideas

What this lesson establishes

One hard idea: a run is a tape, and the distribution is over tapes. The other two are what that buys — a proof of uniformity for one shuffle and a refutation of it for the other.

A run is a tape, and the tapes are what you count

Fix the algorithm and fix the input, and the only thing that can still vary is the sequence of random draws it makes. Call that sequence a tape. Every draw is uniform and independent, so every tape of the same length is equally likely, and the probability of an outcome is the number of tapes producing it divided by the number of tapes there are. That reduces a probability question to a counting question, and the lab answers it by listing all of them: 256 tapes at n = 4 for the naive swap, 24 for Fisher–Yates.

Fisher–Yates is uniform because the map is a bijection

Fisher–Yates draws j in 0..i at step i, counting down, so a tape is one choice out of n, then one out of n − 1, and so on: n! tapes in all. Each produces a different permutation and there are n! permutations, so the correspondence is one to one and every permutation has probability exactly 1/n!. The lab prints 1/24 in every row at n = 4 and a total variation distance from uniform of 0.

Divisibility refutes the other one without a single run

The naive swap draws j in 0..n − 1 at every step, so it has nⁿ tapes. If it were uniform, each of the n! permutations would come from exactly nⁿ/n! tapes — and that has to be a whole number. At n = 4 it is 256/24, which is 10 with 16 left over. There is no arrangement of 256 tapes into 24 equal piles, so the shuffle is not uniform, and nothing about that argument mentions a sample.

The material

Every tape, and the remainder that settles it

Two shuffles that differ by one character, a proof for one, a refutation of the other, and a sample that can establish neither.

Definition · A tape, and the distribution over tapes

A tape for a randomised algorithm on a fixed input is the sequence of values its random draws returned. If every draw is uniform over k values and independent of the others, then each tape of t draws has probability 1/kᵗ, and the probability that the algorithm produces a given output is the number of tapes producing it over the number of tapes there are. Both halves are integers, so the probability is a fraction.

This is the whole of the lab's method, and it is what lets a page print probabilities rather than estimates. It only works while the tapes can be listed — 3125 of them at n = 5, 46656 at n = 6 — which is why the panel refuses above n = 6 for the naive swap and above n = 7 for Fisher–Yates. Those are different limits because the two shuffles have different numbers of tapes, and the refusal says which.

Definition · The two shuffles

Both start from the identity and walk the array once. Fisher–Yates, going down from i = n − 1, draws j uniformly from 0..i and swaps positions i and j. The naive swap, going up from i = 0, draws j uniformly from 0..n − 1 — the whole array, every time — and swaps positions i and j. The second is the one people write from memory, and it is the one that is wrong.

Theorem · Fisher–Yates produces every permutation with probability 1/n!

The map from tapes to permutations is a bijection, so each of the n! permutations arises from exactly one of the n! equally likely tapes.

Injective. Run two different tapes. Let i be the largest index at which they differ, and consider the state just before step i, which is the same for both because every earlier step agreed. Step i places the element then at position j into position i, and positions 0..i still hold distinct elements, so two different j put different elements at position i. Nothing after step i touches position i, so the two outputs differ.

Surjective, and therefore bijective, by counting: there are n! tapes and n! permutations, and an injection between two finite sets of the same size is a bijection. Every permutation therefore has exactly one tape, and every tape has probability 1/n!.

□

That proof is the reason the lab's Fisher–Yates column reads 1/24 in all 24 rows and the total variation distance is 0 exactly rather than a small number. The measured column beside it still wanders — 120 seeds at n = 4 produced 23 of the 24 permutations, and one of them never appeared. That is what a sample from a uniform distribution looks like.

Theorem · The naive swap cannot be uniform for any n ≥ 3

The naive swap has nⁿ equally likely tapes and n! possible outputs. If it were uniform, n! would divide nⁿ. It does not for any n ≥ 3, so it is not uniform.

Suppose the shuffle were uniform. Every tape is equally likely and produces exactly one permutation, so the nⁿ tapes are partitioned by the permutation they produce, and uniformity says every part has the same size s. Then n! · s = nⁿ, so n! divides nⁿ.

It does not. Take any prime p with n/2 < p < n, which exists for n ≥ 3 by Bertrand's postulate. Then p divides n!, since p ≤ n. But p < n < 2p, so n is not a multiple of p, and p does not divide nⁿ either. A divisor of n! that is not a divisor of nⁿ is a contradiction, so no such s exists.

□

The lab does not take Bertrand's postulate on trust and it does not need to: it computes nⁿ and n! as arbitrary-precision integers and prints the remainder for the n on screen. The slider reaches 3, 4 and 5, where the remainders are 3, 16 and 5; the repository's arithmetic check runs the same function as far as n = 7, where they come out 576 and 2023. Any one of those is a complete refutation for that n, and none of them is a measurement.

What the enumeration adds once uniformity is already refuted

The divisibility argument says the shuffle is not uniform. It does not say how far off it is, which permutation is favoured, or whether the bias matters. For that the lab enumerates. At n = 4 the most likely permutation is 1032 with 15 of the 256 tapes, probability 15/256; the least likely has 8 tapes, probability 1/32, and two permutations are tied at that value. The spread of tape counts is 8, 9, 10, 11, 14, 15 — the favoured outcome is almost twice as likely as the neglected one.

The single number for that is the total variation distance from uniform: half the sum of |p(σ) − 1/n!| over all n! permutations. At n = 4 it is 25/384, exactly, and it is 0 for Fisher–Yates. It is the largest amount by which the two distributions can disagree about the probability of any event, so it is the right single summary of how wrong the shuffle is.

More swaps do not wash the bias out

The intuition that a longer shuffle mixes better predicts that the bias shrinks with n. It grows. The total variation distance is 1/18 at n = 3, 25/384 at n = 4, and 3157/37500 at n = 5 — about 0.056, 0.065 and 0.084. Move the slider and watch it climb. The extra swaps are extra opportunities for the same asymmetry rather than a correction of it.

And the measurement becomes less useful as n grows, in the other direction. At n = 4, 120 seeds cover 23 of the 24 permutations and the counts are already too noisy to rank; at n = 5 they cover 80 of the 120 and forty permutations have no evidence at all. A sample large enough to detect a total variation distance of 0.084 across 120 outcomes is much larger than a lesson can run in a browser, and this is the general shape of the problem: refuting uniformity by sampling is expensive, and refuting it by counting costs one division.

Interactive

Two shuffles, every tape enumerated

Fisher–Yates gives each permutation exactly one tape; the naive swap has n^n of them and n! does not divide it

Set n, choose the shuffle, and read the exact column against the measured one

The exact column enumerates every tape, so the probabilities are fractions rather than estimates. The measured column runs the shuffle over the seeds the slider names. They disagree, and the disagreement is the point: a sample cannot establish uniformity, and the counting argument below can refute it.

Worked example

How many items, n4

Which shuffle

Seeds to measure over120

Tapes, exactly—

Permutations reached—

Uniform over every tape—

Most likely permutation—

Least likely permutation—

Total variation from uniform—

n to the n, against n factorial—

Measured: distinct permutations—

A tape is one sequence of random draws — one complete run. Fisher–Yates draws j in 0..i going down, so it has n! tapes; the naive swap draws j in 0..n−1 every time, so it has n^n. The table below enumerates all of them, which is why the probabilities are fractions and not estimates.

Method

Reading a distribution you can see all of

Do the arithmetic before the experiment. The experiment is the part that cannot settle it.

Count the tapes before you count anything else

How many independent draws does the algorithm make, and how many values can each take? The product is the number of tapes, and every probability on the page is a count of tapes over that number. Get it wrong and every fraction after it is wrong by the same factor.

Divide, and look at the remainder

Number of tapes over number of outcomes. If the division is not exact, uniformity is already refuted and nothing else on the page can rescue it. If it is exact, you have learned nothing either way — which is worth knowing, because the counting argument is one-directional.

Read the exact column and the measured column as different things

The exact column is the enumeration and will not move when the seed slider does. The measured column is a sample and will. If a claim you are about to make changes when you move the seeds, it was a claim about the sample.

Change n before generalising

The bias of the naive swap is not a quirk of one size. Run n = 3, n = 4 and n = 5 and watch the total variation distance grow rather than shrink; the direction of that movement is the thing most readers guess wrong, and it takes two slider positions to settle.

Tapes, counting, and what a sample settles

Score 0 / 0

Choose the answer you can justify.

All 27 tapes of the naive swap at n = 3

Three items, three draws, three choices each: 27 tapes, and six permutations to share them between. 27 divided by 6 is 4 with 3 left over, so the shuffle is already refuted. Here is what the enumeration finds.

permutation tapes the tapes themselves probability 012 4 012 021 102 210 4/27 021 5 011 022 101 120 200 5/27 102 5 002 112 121 201 220 5/27 120 5 001 020 111 122 202 5/27 201 4 000 110 211 222 4/27 210 4 010 100 212 221 4/27 -- ---- 27 27/27 three permutations at 5/27 and three at 4/27 total variation from uniform = 1/18 Fisher-Yates on the same three items: 6 tapes, one each, 1/6

The split is three and three, not four and two: three permutations get five tapes and three get four, and 3·5 + 3·4 = 27. Any other split of 27 into six parts with two distinct sizes would have to add to 27 as well, which is the only arithmetic check this table needs and the one worth doing before trusting any table like it.

Notice what the bias is not. It is not that one item is stuck at the front, and it is not visible in the first few draws. 012, the identity, is one of the less likely outcomes. A reader looking for a pattern in the output will not find one; the asymmetry lives in the tape counts, and only the enumeration sees it.

For a faded rehearsal, predict the Fisher–Yates row before switching the lab over. The supplied first move is this: Fisher–Yates at n = 3 makes two draws, one from {0, 1, 2} and one from {0, 1}, so it has six tapes. Say what each permutation's probability must be and what the total variation distance has to be, then switch and check — and then say why the same argument gives nothing at all about the naive swap at n = 2.

Common mistakes

Testing uniformity by shuffling a lot and looking at the countsA sample from a uniform distribution is uneven, and a sample from a distribution 25/384 away from uniform is uneven in a way that looks the same at 120 runs. The lab shows both columns side by side precisely so this is visible: Fisher–Yates over 120 seeds reaches 23 of 24 permutations with lopsided counts, and it is provably uniform. The sample cannot separate the two hypotheses at any sample size a lesson can run.

Reading the bias off the output rather than the tape countsNobody can look at 1032 and see why it is favoured, and the identity permutation is one of the less likely outcomes at n = 3, not the most likely. The asymmetry is a property of how many tapes lead where, and the only way to see it is to count them — which is why the lab prints the tape count in its own column beside the probability.

Assuming more randomness makes a biased procedure fairerThe naive swap makes n draws from n values, which is more raw randomness than Fisher–Yates uses, and it is the one that is wrong. What matters is whether the number of equally likely runs is compatible with the number of answers, and adding draws multiplies the tape count by n while the number of permutations does not move.

Check your understanding

✓

Finish when you can refute a sampling procedure on paper, before running it once.

You should be able to count the tapes of a procedure from its loop, divide by the number of outcomes, and say what a nonzero remainder proves and what a zero remainder does not; and you should be able to say why the measured column of a provably uniform shuffle still looks uneven.

Note: Everything after this is the same distinction applied to a quantity rather than to an outcome. “The Cost Is a Distribution” enumerates every execution of a sorting algorithm instead of every tape of a shuffle, and gets a distribution over comparison counts; the enumeration is the same idea and the recursion that performs it is the only new machinery.