Katkat
Back

Prove an Incremental Shuffle Is Uniform

ModalSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Tests formal inductive reasoning on randomized algorithms by proving the uniformity of the Fisher-Yates shuffle, and evaluates practical knowledge of common implementation pitfalls like off-by-one bounds and modulo bias.

Problem Description

Consider the forward variation of the Fisher-Yates (Knuth) shuffle operating in place on an array arr of n distinct elements:

import random

def shuffle(arr: list[int]) -> None:
    n = len(arr)
    for i in range(n - 1):
        # Pick a random index j uniformly from [i, n - 1]
        j = random.randint(i, n - 1)
        arr[i], arr[j] = arr[j], arr[i]

Provide a rigorous proof of correctness and analyze two standard implementation pitfalls:

Part 1: Induction Proof

Formulate a precise loop invariant over the prefix arr[0 : i] and prove by induction that:

  1. After step i (for i = 0, 1, ..., n - 2), the prefix arr[0 : i + 1] contains a uniformly random permutation of some subset of i + 1 elements from the original array.
  2. Upon loop termination, every one of the n! possible permutations of the input array is produced with equal probability 1 / n!.

Part 2: Endpoint / Range Mistake

A common bug in naive implementations is choosing j uniformly from [0, n - 1] at every iteration instead of [i, n - 1]:

# Buggy line:
j = random.randint(0, n - 1)

Explain why this breaks uniformity. Use a counting argument (for example, with n = 3) to prove that not all permutations can have equal probability.

Part 3: Modulo Bias

Suppose randint(i, n - 1) is implemented using a standard C-style pseudo-random function as i + (rand() % (n - i)), where rand() produces an integer uniformly distributed in [0, RAND_MAX].

Explain mathematically why this introduces modulo bias when (RAND_MAX + 1) is not divisible by (n - i), and quantify which outcomes receive higher probabilities.

Hints

Hint 1

For the induction step, consider the conditional probability that a specific remaining element is selected for position i given that it was not chosen in any earlier step 0 through i - 1.

Hint 2

For the endpoint mistake, count the total number of distinct execution paths the algorithm can take (a power of n) and compare it to the number of permutations n!.

Hint 3

For modulo bias, partition the range [0, RAND_MAX] into full buckets of size (n - i) and observe what happens to the remaining leftover values.

Follow-up questions

  • How would you implement an unbiased random integer generator in range [0, k - 1] using rejection sampling given an arbitrary rand() in [0, RAND_MAX]?
  • Could a 32-bit PRNG ever produce every permutation of a standard 52-card deck, even if Fisher-Yates is implemented without bugs? Why or why not?
  • How does the proof adapt if you stream elements of unknown total size n, such as in Reservoir Sampling?