Randomized Algorithms

Overview

A randomized algorithm makes some of its decisions using random bits rather than following a fully deterministic procedure, trading a small, quantifiable probability of error or a randomized running time for simplicity or speed that often beats the best known deterministic alternative. Randomized algorithms fall into two broad families: Las Vegas algorithms always produce a correct answer but have a random RUNNING TIME (e.g. randomized quicksort), while Monte Carlo algorithms always run in bounded time but have a random CHANCE OF ERROR that can be driven arbitrarily low by repetition (e.g. Freivalds' matrix-product checker, or Miller-Rabin primality testing). The complexity classes RP, BPP, and ZPP formalize these ideas, and whether randomness ever provides a genuine, provable advantage over determinism (i.e. whether BPP = P) remains an open problem closely tied to circuit lower bounds and derandomization.

Intuition

Imagine checking whether a large arithmetic identity (like whether matrix A times B equals matrix C) holds, without recomputing the whole product. Instead of that expensive recomputation, pick a random vector r and just check whether A(Br) equals Cr — a much cheaper computation. If the identity truly holds, this check always passes; if it's false, it's extremely unlikely that a random r would happen to hide the discrepancy. Repeating the random check a few times makes the chance of being fooled vanishingly small, while remaining far cheaper than a deterministic full recomputation. This is the general shape of many randomized algorithms: replace an expensive certainty with a cheap, controllable, and repeatable near-certainty.

Formal Definition

Definition

The core randomized complexity classes, and Freivalds' error-amplification bound used as the running example throughout this concept:

\text{RP} = \{L : \exists \text{ poly-time randomized } A,\ x \in L \Rightarrow \Pr[A(x)=1] \ge \tfrac12,\ x \notin L \Rightarrow \Pr[A(x)=1]=0\}

RP — one-sided error

\text{BPP} = \{L : \exists \text{ poly-time randomized } A,\ \Pr[A(x) \text{ correct}] \ge \tfrac{2}{3} \ \forall x\}

BPP — bounded two-sided error

\text{ZPP} = \text{RP} \cap \text{coRP}

Zero-error probabilistic polynomial time (Las Vegas algorithms)

\Pr[\text{Freivalds error after } k \text{ independent trials}] \le \left(\tfrac12\right)^{k}

Error amplification via independent repetition

Notation

Notation	Meaning
$\text{RP}$	Randomized polynomial time with one-sided error (false negatives never occur)
$\text{BPP}$	Bounded-error probabilistic polynomial time (two-sided error, amplifiable)
$\text{ZPP}$	Zero-error probabilistic polynomial time (Las Vegas: always correct, random running time)
$\mathbb{E}[T]$	Expected running time of a Las Vegas algorithm

Theorems

Theorem 1: Freivalds' algorithm correctness

\text{If } AB \ne C, \text{ a single random 0/1 vector } r \text{ satisfies } ABr = Cr \text{ with probability} \le \tfrac12; \text{ repeating } k \text{ times independently reduces the error to} \le 2^{-k}.

Theorem 2: Randomized quicksort expected time

\text{Randomized quicksort (random pivot each call) sorts } n \text{ elements in expected time } O(n \log n), \text{ regardless of input order.}

Theorem 3: Relationship between the classes

P \subseteq \text{ZPP} \subseteq \text{RP} \subseteq \text{BPP}, \text{ and it is a major open problem whether } \text{BPP} = P.

Applications

Randomized primality testing (Miller-Rabin) underlies practical generation of large prime numbers for RSA and other public-key cryptosystems, since deterministic primality proofs (AKS) are correct but historically much slower in practice.

Worked Examples

Each independent repetition has error probability at most 1/2 when the claim is false, and the checks are independent, so the probabilities multiply.
$\Pr[\text{all 10 checks pass} \mid AB \ne C] \le \left(\frac12\right)^{10}$
Compute 2^10.
$2^{10} = 1024$

Answer: The probability of wrongly accepting a false matrix-product claim after 10 independent checks is at most 1/1024 ≈ 0.098% — each additional repetition roughly halves the error, so error shrinks exponentially fast in the number of trials.

Practice Problems

Difficulty 6/10

What is the key difference between a Las Vegas algorithm and a Monte Carlo algorithm?

Difficulty 7/10

The Miller-Rabin primality test has, for a composite input, at most a 1/4 probability of incorrectly reporting 'probably prime' on any single round. If a program runs 20 independent rounds and the number passes all of them, what is the worst-case probability it is actually composite?

Difficulty 5/10

Randomized quicksort's expected O(n log n) running time bound holds:

Only for already-randomized (shuffled) input arraysFor every fixed input array, because the pivot choice is randomized independent of the inputOnly in the best caseOnly if the array has distinct elements in sorted order

Common Mistakes

Common Mistake

Confusing 'randomized algorithm' with 'algorithm that behaves unpredictably or unreliably.'

Randomized algorithms have precisely quantified, provable probability-of-error or expected-running-time bounds — the randomness is a deliberate design tool with rigorous guarantees, not a source of unreliability. Error probabilities can typically be driven arbitrarily low via independent repetition.

Common Mistake

Believing that repeating a Monte Carlo algorithm k times reduces the error probability by a factor of k (linearly).

Independent repetitions multiply the error probabilities, giving EXPONENTIAL decay (e.g. (1/2)^k or (1/4)^k), not linear decay — a crucial distinction, since exponential decay makes even a modest number of extra rounds extremely effective.

Quiz

Flashcards

1 / 4

Historical Background

Randomized algorithms emerged as a distinct field in the 1970s, when Michael Rabin and, independently, Gary Miller developed randomized primality tests dramatically faster than the deterministic methods known at the time, and Rusins Freivalds introduced a simple randomized algorithm for verifying matrix multiplication. Robert Solovay and Volker Strassen published a related randomized primality test in 1977. Volker Strassen's earlier fast matrix multiplication work, combined with Freivalds' verification trick, illustrated how randomness could simplify problems that seemed to need expensive deterministic computation. The formal complexity classes RP, BPP, and ZPP were developed through the late 1970s and 1980s to classify exactly what randomized polynomial-time computation could achieve, and remain central to the (still-open) question of whether randomness provides more than a constant-factor speedup over determinism.

1976
Rusins Freivalds introduces a fast randomized algorithm for checking matrix multiplication
Rusins Freivalds
1976
Michael Rabin develops a randomized primality test
Michael O. Rabin
1977
Robert Solovay and Volker Strassen publish the Solovay-Strassen randomized primality test
Robert Solovay, Volker Strassen
1980s
Complexity classes RP, BPP, and ZPP are formalized to classify randomized polynomial-time computation

Summary

Randomized algorithms use random bits to trade certainty for speed or simplicity, in a precisely quantified way.
Las Vegas algorithms are always correct but have random running time; Monte Carlo algorithms have fixed running time but a bounded error probability.
Independent repetition of a Monte Carlo check reduces error probability exponentially (e.g. (1/2)^k after k trials), not linearly.
The complexity classes RP, BPP, and ZPP formalize randomized polynomial-time computation; whether BPP = P remains a major open problem.
Practical uses include Miller-Rabin primality testing, randomized quicksort, and Freivalds' matrix-multiplication checker.