Introduction

A correct random shuffle produces every permutation of a dataset with equal probability. But what happens when the shuffle algorithm has a bug? This article examines the most common "broken" shuffle, analyzes the non-uniform distribution it produces, and explains why the Fisher-Yates algorithm is the correct approach.

What Makes a Shuffle Correct?

For a dataset of $n$ elements, there are $n!$ possible permutations. A correct shuffle gives each permutation exactly a $\frac{1}{n!}$ probability of occurring. The Fisher-Yates (Knuth) shuffle achieves this by iterating from the end of the array to the beginning, swapping each element with a randomly chosen element from the remaining unprocessed portion.

1import random
2
3def fisher_yates_shuffle(arr):
4    for i in range(len(arr) - 1, 0, -1):
5        j = random.randint(0, i)
6        arr[i], arr[j] = arr[j], arr[i]

This algorithm makes exactly $n - 1$ swaps and produces each of the $n!$ permutations with equal probability.

The Classic Broken Shuffle

The most common broken shuffle swaps each element with a random position chosen from the entire array, not just the unprocessed portion:

1def broken_shuffle(arr):
2    n = len(arr)
3    for i in range(n):
4        j = random.randint(0, n - 1)  # BUG: should be randint(i, n-1)
5        arr[i], arr[j] = arr[j], arr[i]

The subtle difference is that j ranges over all $n$ positions at every step, rather than only the positions from $i$ to $n-1$.

Why This Produces a Biased Distribution

The broken shuffle makes $n$ independent random choices, each from $n$ options, producing $n^n$ equally likely execution paths. The key problem is that $n^n$ is generally not divisible by $n!$. For example, with $n = 3$:

• Number of execution paths: $3^3 = 27$
• Number of permutations: $3! = 6$
• $27 / 6 = 4.5$, which is not an integer

Since 27 execution paths cannot be evenly distributed across 6 permutations, some permutations must be more likely than others.

Empirical Analysis for n = 3

Running the broken shuffle on [A, B, C] one million times produces results like:

The distribution is clearly non-uniform. The permutation [C, A, B] appears about 33% more often than expected, while [A, C, B] appears about 33% less often.

Exact Probabilities

For the 3-element case, we can enumerate all 27 execution paths:

Statistical Detection

Chi-Squared Goodness-of-Fit Test

To statistically verify that a shuffle is biased, use the chi-squared test:

$$\chi^2 = \sum_{i=1}^{k} \frac{(O_i - E_i)^2}{E_i}$$

where $O_i$ is the observed count of permutation $i$, $E_i$ is the expected count under a uniform distribution, and $k = n!$ is the number of permutations.

With enough trials, a broken shuffle will produce a $\chi^2$ value far exceeding the critical value, confirming non-uniformity with high confidence.

Positional Bias Matrix

Another useful diagnostic is a position-frequency matrix. For each element, count how often it lands in each position across many trials. In a correct shuffle, each element should appear in each position with probability $\frac{1}{n}$. The broken shuffle will show systematic biases, for example later elements tending to cluster toward the front.

Why Does This Matter?

Biased shuffling has real consequences in several domains:

• Online games: Card shuffles or matchmaking that favor certain outcomes create unfair play.
• A/B testing: Biased assignment of users to test groups invalidates experimental results.
• Cryptography: Non-uniform randomness weakens security protocols.
• Simulations: Monte Carlo simulations relying on uniform random permutations will produce incorrect results.

The Fix: Fisher-Yates

The Fisher-Yates algorithm avoids the bias by progressively narrowing the range from which the swap target is chosen:

1def correct_shuffle(arr):
2    for i in range(len(arr) - 1, 0, -1):
3        j = random.randint(0, i)  # j in [0, i], not [0, n-1]
4        arr[i], arr[j] = arr[j], arr[i]

This produces exactly $n \times (n-1) \times \ldots \times 1 = n!$ equally likely execution paths, one for each permutation. It runs in $O(n)$ time and $O(1)$ extra space.

Summary

The broken shuffle (swapping with a random element from the full array) produces a non-uniform distribution because $n^n$ execution paths cannot map evenly onto $n!$ permutations. The bias grows with array size. Always use the Fisher-Yates shuffle, which guarantees uniformity by restricting the swap range at each step. When in doubt, verify your shuffle with a chi-squared test on the permutation frequencies.