The Randomized Approach

A randomized algorithm uses random choices as part of its method. Run it twice on the same input and it may behave differently.

That sounds like a defect. It is often an advantage — because an adversary cannot predict what you will do, and because average behaviour can be excellent even when the worst case is terrible.

Motivations for the randomized approach

1. It defeats bad inputs. Quick sort's worst case appears when the pivot is always the smallest element — which happens on an already sorted list, a very common input. Choosing the pivot at random makes that worst case a matter of luck rather than a property of the data.

2. Simplicity. A randomized method is often far shorter than the deterministic one that achieves the same guarantee.

3. Speed on average. Accepting a small chance of being slow can buy a much better typical case.

4. Sometimes there is no deterministic alternative. Testing whether a very large number is prime is done probabilistically in practice.

5. Sampling. Where examining all the data is impossible, a random sample gives an answer with a known margin of error — the basis of every opinion poll.

Expected value

To reason about randomness we need the expected value: the average outcome over many repetitions.

For a fair six-sided die:

You will never roll 3.5. The expected value is what the average tends to over many rolls, not a prediction of any single one.

Example 1: the coupon collector

A company selling jeans gives one coupon with each pair. There are $n$ different coupons, and collecting all $n$ earns you a free pair. How many pairs do you expect to buy?

The first coupon is always new. Once you hold $k$ distinct coupons, the chance the next is new is $\frac{n-k}{n}$, so you expect to wait $\frac{n}{n-k}$ purchases for it.

Summing over all stages:

where $H_n$ is the harmonic number $1 + \frac12 + \cdots + \frac1n$.

The last coupon is the expensive one. With 10 coupons you expect 29 purchases — but around 10 of those are spent waiting for the final one alone, because each new pair has only a 1-in-10 chance of being it.

Anyone who has tried to complete a sticker album knows this result without the mathematics.

Example 2: the hat-check problem

$n$ people leave hats with an attendant. A different attendant returns them at random, one per person. How many people expect to get their own hat back?

Intuition says the answer must depend on $n$. It does not.

Each person has probability $\frac{1}{n}$ of receiving their own hat. There are $n$ people, so the expected number of matches is

Exactly one, for every $n$. Whether 5 people or 5 million, on average one person gets their own hat.

The trick is linearity of expectation: expected values add, whether or not the events are independent. Here they are clearly not independent — if the first $n-1$ people get their own hats, the last one must too — and the result holds anyway. That is what makes linearity so useful.

Two kinds of randomized algorithm

Las Vegas gambles with time, Monte Carlo with correctness.

Randomness in Python

import random

random.randint(1, 6)            # a die roll, both ends included
random.choice(["a", "b", "c"])  # one item
random.shuffle(deck)            # in place
random.random()                 # a float in [0.0, 1.0)
random.sample(pop, 10)          # 10 distinct items

Note randint includes both ends, unlike range. That inconsistency catches people.

random.seed(42) makes the sequence repeatable, which matters when you need a test to give the same answer every run.