Randomized Algorithms

What are randomized algorithms?

Randomized algorithms are algorithms that have access to a source of randomness. This means that their execution path and their outputs are both random. In general, we might be interested in making statements like the following:

1. \[\forall x \in \mathcal{X}, \mathbb{P}[Alg(x, r) \text{is correct}] \geq ...\]
2. \[\forall x \in \mathcal{X}, \mathbb{V}[Alg(x, r) \text{'s runtime}] \leq ...\]

Why do we care about randomized algorithms?

It turns out that there are problems for which we can find efficient and likely to be correct randomized algorithms and for which we cannot find equally efficient deterministic algorithms. There are open questions in computational complexity about what exactly randomness buys us!

What are types of randomized algorithms?

Broadly, there are 2 families of randomized algorithms:

1. Las Vegas: The output is always correct, but the runtime is random
2. Monte Carlo: The runtime is always fast, but the answer is possibly wrong

Tools & Example Problems

• Empty Pigeonholes
• Coupon Collector Problem
• Primality Testing
• Minimum Graph Cut (Kargar’s Algorithm)
• Moment Generating Functions
• Balls and Bins
• Poissonization
• Metric Embeddings
• Lovazc Local Lemma
• Algorithmic Lovazc Local Lemma
• Markov Chains
• Martingales

Useful Inequalities

• Markov’s Inequality
• Chebyshev’s Inequality
• Chernoff Bounds
• Bernstein’s Inequality
• Hoeffding’s Inequality
• Azuma-Hoeffding Bound

References

• Mary Wootter’s Stanford CS265