Skip to content

Randomized Algorithms

Introducing controlled randomness defeats adversarial inputs, achieves good expected performance without worst-case guarantees, and often produces simpler algorithms than deterministic alternatives.

Tension Addressed

Deterministic vs. Randomized

Recognizable As

Random pivot selection (quicksort), random sampling, probabilistic data structures (Bloom filters, skip lists), Monte Carlo vs. Las Vegas distinction.

Canonical Sources

Rabin, "Probabilistic Algorithm for Testing Primality," 1980; Motwani & Raghavan, Randomized Algorithms, 1995

Transfers To

Cryptography, load balancing, distributed consensus, machine learning, simulation

Sub-concepts: - Las Vegas: Always correct, randomized running time - Monte Carlo: Bounded time, probabilistic correctness

Randomization shifts analysis from worst-case to expected-case, often dramatically improving practical performance while maintaining theoretical guarantees probabilistically.