Skip to content
Tutorials Center
My learning

Topics

Lesson 185 of 225 ยท Math and Bit Manipulation

Randomized Algorithms

Learn randomized algorithms in Python: Fisher-Yates shuffle, reservoir sampling, randomized quickselect and the difference between Monte Carlo and Las Vegas.

Most algorithms you have met so far are deterministic: give them the same input and they do exactly the same steps every time. A randomized algorithm is allowed to flip coins while it runs. That sounds like a recipe for chaos, yet random choices are one of the most useful tools in computer science. They make simple algorithms hard to fool, they turn nasty worst cases into rare accidents, and some problems have no known fast deterministic solution at all.

In this lesson you will learn how to run randomness repeatably with random.seed, write the correct shuffle (and see why the obvious one is wrong), pick a fair sample from data you cannot store, find the k-th smallest element in expected linear time, and tell the two families of randomized algorithms apart: Las Vegas and Monte Carlo.

Randomness you can repeat

Python's random module is a pseudo-random generator: it produces a long, fixed sequence of numbers that merely looks random. The seed chooses where in that sequence you start. Same seed, same numbers. That is exactly what you want when you test or teach, because a failing run can be replayed.

Python A seed makes randomness repeatable

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In tests, create your own random.Random(seed) object and pass it into your functions. The global generator is shared by everything in the program, so a library call can silently change your sequence.

The exact numbers a seed produces are a detail of the Python version, so never write code that depends on them. Depend only on the property that the same seed repeats itself.

Fisher-Yates shuffle

Shuffling a deck should give every ordering the same chance. Here is the idea behind the correct algorithm, named after Ronald Fisher and Frank Yates and in its computer form by Richard Durstenfeld:

  1. Walk i from the last position down to 1.
  2. Pick a random position j between 0 and i (inclusive).
  3. Swap items[i] and items[j].

Each step fixes one element for good: after the step at i, position i is final.

TEXT
[A B C D]   i=3, j=1  -> swap D and B -> [A D C B]   (B is placed)
[A D C B]   i=2, j=2  -> swap C and C -> [A D C B]   (C is placed)
[A D C B]   i=1, j=0  -> swap D and A -> [D A C B]   (A is placed)
result: D A C B

There are 4 * 3 * 2 = 24 possible sequences of choices, and 24 permutations of four items, each reached by exactly one sequence. That is why every permutation is equally likely. It runs in O(n) time and O(1) extra space.

A tempting alternative is to loop over every index and swap it with a random index from the whole list. It looks just as random, but it is biased: n steps with n choices each give n^n equally likely outcomes, and n^n is not divisible by n! (for n = 3, there are 27 outcomes for 6 permutations), so some orderings must be more likely than others.

Python Correct shuffle versus the biased one

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 60,000 trials a fair shuffle puts about 10,000 in each of the six rows. Fisher-Yates stays close to that. The naive version drifts: for three items the exact chances are 4/27 or 5/27 per permutation instead of 1/6, a gap you can see in the counts.

In real programs use random.shuffle(items), which is Fisher-Yates already. For anything security related (passwords, tokens, lottery draws that matter), use the secrets module, not random.

Reservoir sampling

Suppose a log file is too big to fit in memory and you want one line chosen uniformly at random. You cannot count the lines first without reading the whole file twice. Reservoir sampling solves it in one pass:

  • Keep the first item as your candidate.
  • When the i-th item arrives (counting from 1), replace the candidate with it with probability 1/i.

Why is every item equally likely at the end? Item k must be chosen when it arrives (probability 1/k) and then survive every later round: each round i it survives with probability (i-1)/i. Multiply: 1/k * k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = 1/n. The fractions cancel like a telescope.

To keep k items, hold a reservoir of size k, fill it with the first k items, and for later item number i choose a random number r in 0..i-1; if r < k, overwrite slot r.

Python Sample k items from a stream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop uses O(k) memory regardless of the stream length and O(n) time. It never needs to know n in advance, which makes it perfect for streams. (The online and streaming lesson revisits it.)

Randomized quickselect

The k-th smallest element of an unsorted list can be found by sorting in O(n log n). Quickselect does better by borrowing the partition step of quick sort: choose a pivot, split the list into smaller, equal and larger parts, and then continue in only the one part that contains position k.

The pivot decides everything. If you always take the first element and the input is already sorted, each round removes just one element and the total work is O(n^2). A random pivot has no bad inputs, only unlucky coin flips. On average the pivot lands in the middle half of the data often enough that the work shrinks geometrically, so the expected time is O(n). The worst case is still O(n^2), but it needs astronomically bad luck.

Python Quickselect: random pivot versus first element

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first-element pivot compares against nearly every remaining item at every round and ends near n^2 / 2 comparisons, while the random pivot stays within a small multiple of n.

Building one random source from another

A classic interview puzzle: you are given a function that returns a uniform random integer from 1 to 5, and you must produce a uniform integer from 1 to 7. The trick is rejection sampling: build a bigger uniform range, throw away the part that does not divide evenly, and try again.

Two calls give 5 * (a - 1) + (b - 1), a uniform number from 0 to 24 (25 equally likely outcomes). Keep the first 21 (a multiple of 7) and map them with % 7. If the number is 21 to 24, reject it and draw again. The chance of acceptance is 21/25, so the expected number of rounds is 25/21 and the expected number of rand5 calls is 2 x 25/21, about 2.38.

The obvious shortcut, rand5() + rand5(), is not uniform: sums near 6 come up far more often than 2 or 10, as the output below shows.

A related puzzle: you have a coin that lands heads with unknown probability p, and you need a fair coin. Flip twice. HT and TH have the same probability p(1-p), so return the first flip when the two differ, and retry on HH or TT. This is von Neumann's trick; it needs no knowledge of p. The cost is about 1 / (2p(1-p)) pairs per fair flip.

Python rand7 from rand5, and a fair coin from a biased one

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that rand7 is a Las Vegas algorithm (see the next section): its output is exactly uniform, but its running time is random and has no fixed upper bound.

Las Vegas and Monte Carlo

Randomized algorithms come in two flavors, named after famous casinos.

Type Answer Running time Example
Las Vegas Always correct Random (fast on average) Randomized quickselect and quicksort
Monte Carlo Correct with high probability Fixed Freivalds' matrix check, Miller-Rabin primality test

A Monte Carlo algorithm may be wrong, but you control how often: repeating it t times with independent coins shrinks the error exponentially. A famous example is Freivalds' algorithm. To check whether A @ B == C for n by n matrices, multiplying A and B takes about n^3 steps in the simple method. Instead pick a random 0/1 vector r and compare A(Br) with Cr. Each side costs only O(n^2). If AB = C the test always passes. If AB != C, a single trial misses the error with probability at most 1/2, so t trials miss it with probability at most 2^-t.

Python Freivalds: Monte Carlo matrix product check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A "True" for the good product is certain; a "True" for the bad one would be bad luck with probability at most 2^-20. The single-round miss rate printed above stays at or below one half, as the theory promises.

Common mistakes

  • Relying on exact random values. Seeds make a run repeatable, but different Python versions may produce different numbers. Test properties (sorted result, same elements, correct count), not exact output.
  • Off-by-one in randint. random.randint(a, b) includes both ends; random.randrange(n) excludes n. Mixing them up is the classic shuffle bug.
  • Biased shuffles. Swapping with a random index from the whole list is wrong. Use Fisher-Yates or random.shuffle.
  • Using random for secrets. It is predictable once you know enough outputs. Use secrets.
  • Forgetting the expected-time wording. Randomized quickselect is O(n) expected, not worst case.

When to use randomization

Reach for it when a deterministic worst case is easy to trigger (sorted input to a naive pivot), when you need fair sampling from huge or unbounded data, or when a fast approximate check is enough (Monte Carlo). Avoid it when you need reproducible output without a seed, or when a wrong answer is never acceptable and a simple deterministic method is fast enough.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does seeding the random generator with the same value give you?

    A seed picks the starting point in the generator's fixed sequence, so the same seed repeats the same sequence in the same Python version. That is what makes randomized tests replayable.
  2. 2. In Fisher-Yates, why is the random index drawn only from 0..i and not from the whole list?

    Restricting j to 0..i makes the number of choice sequences equal to n!, one per permutation. Drawing from the whole list gives n^n outcomes, which cannot be spread evenly over n! permutations.
  3. 3. Reservoir sampling of one item replaces the candidate with the i-th item (counting from 1) with probability:

    The i-th item replaces the candidate with probability 1/i. The product of that and the survival chances of later rounds telescopes to 1/n for every item, without knowing n in advance.
  4. 4. What is the expected running time of quickselect with a random pivot?

    Each round shrinks the data by a constant fraction on average, so the work forms a geometric series that sums to O(n). The worst case is O(n^2) but it is extremely unlikely.
  5. 5. Which statement about Monte Carlo algorithms is true?

    Monte Carlo algorithms have a bounded running time and a small error chance. Las Vegas algorithms are the ones that are always correct with random running time.

Summary

  • A randomized algorithm uses random choices; random.seed (or a private random.Random(seed)) makes demos and tests repeatable.
  • Fisher-Yates shuffles in O(n) time and O(1) extra space, and every permutation is equally likely. Swapping with an index from the whole list is biased.
  • Reservoir sampling picks a fair sample from a stream in one pass with O(k) memory.
  • Randomized quickselect finds the k-th smallest element in expected O(n) time; a random pivot defeats adversarial inputs.
  • Las Vegas algorithms are always correct with random time; Monte Carlo algorithms have fixed time and a small, controllable error chance.

Next: Computational Geometry Basics