Randomized Algorithms

Las Vegas vs Monte Carlo

Simple Fundamental Explanation

Imagine you need to find a specific needle in a giant haystack.

• Deterministic Algorithm: You start at the top left corner. You pick up a piece of hay. You check if it’s a needle. You put it in a pile. You repeat this for millions of pieces. It is extremely slow, but you are 100% guaranteed to find the needle if it’s there.
• Randomized Algorithm: You close your eyes, plunge your hand into the haystack at a completely random location, and grab a handful. You check it. You do this 10 times. You might not find the needle, but if the haystack actually has 1,000 needles scattered inside it, this random plunging is incredibly fast and highly likely to succeed.

A Randomized Algorithm intentionally injects randomness (coin flips, random sampling) into its logic. It sacrifices either guaranteed correctness or guaranteed runtime to solve problems that deterministic algorithms find mathematically impossible to solve efficiently.

Deep Dive: How It Works Under the Hood

There are two primary families of randomized algorithms:

1. Las Vegas Algorithms

These algorithms always return the correct answer, but their runtime is a random variable. Example: Quicksort. To sort an array, you pick a “pivot” element, put smaller items on the left, and larger items on the right. If you always pick the first element as the pivot, an already-sorted array will cause the algorithm to hit its worst-case scenario ($O(N^2)$). If you pick the pivot randomly, the algorithm breaks the worst-case structure, guaranteeing an expected runtime of $O(N\log N)$ regardless of the input. It is always correct, and almost always fast.

2. Monte Carlo Algorithms

These algorithms always run fast (fixed runtime), but their answer has a small probability of being wrong. (See MONTE_CARLO_SYSTEMS.md). Example: Karger’s Min-Cut Algorithm for network topology. Example: Bloom Filters. You always get an answer instantly, but there is a 1% chance it’s a false positive.

Visual Diagram: Testing Primality

Is 7919 a prime number?

Deterministic Way (Trial Division):
Check if 7919 % 2 == 0
Check if 7919 % 3 == 0
...
Check every number up to sqrt(7919). (Extremely slow for 1024-bit RSA keys!)

Randomized Way (Fermat / Miller-Rabin):
Pick a random number 'a' (e.g., 5).
Apply a specific mathematical formula: (a^(p-1)) % p.
If the result is NOT 1, the number is DEFINITELY NOT prime.
If the result IS 1, the number is PROBABLY prime (99.9% chance).
Repeat with 3 more random numbers to achieve 99.9999% confidence in milliseconds.

Practical Example: Cryptography and RSA

Every time you log into a secure website, your browser uses RSA or Elliptic Curve Cryptography. This requires generating a massive, 2048-bit random Prime number.

How does the computer know if a randomly generated 2048-bit number is prime? A deterministic check would take longer than the age of the universe.

Instead, OpenSSL uses the Miller-Rabin Primality Test, a randomized Monte Carlo algorithm. It picks random bases and performs modular exponentiation. If the test passes 64 times in a row, the probability that the number is actually composite (a false positive) is less than $1$ in $2^{128}$. The computer accepts the number as prime and generates your encryption keys. The entire security of the internet relies on this probabilistic assumption.

The Mathematics: Equations and In-Depth Analysis

1. Expected Runtime (Las Vegas)

For a randomized Las Vegas algorithm, let $T(x)$ be the random variable representing the runtime on input $x$. We analyze the Expected Runtime $\mathbb{E}[T(x)]$. In Randomized Quicksort, the probability of comparing two elements $i$ and $j$ (where $j>i$) depends entirely on whether $i$ or $j$ is chosen as the pivot before any element between them. There are $j-i+1$ elements in that range. The probability is exactly $\frac{2}{j-i+1}$. The expected total number of comparisons is the sum over all pairs:

Using harmonic series approximations, this sums cleanly to $O(N\log N)$. The math proves that a random pivot naturally and predictably balances the recursion tree.

2. Error Amplification (Monte Carlo)

If a Monte Carlo algorithm has a high error rate, we can mathematically crush the error to zero by running it multiple times and taking the majority vote.

Let an algorithm have a probability of success $p=0.51$ (only slightly better than a coin flip). We run the algorithm $n$ times. What is the probability that the majority vote is correct? We use the Chernoff Bound, which bounds the tail of the binomial distribution. The probability that the number of correct answers $X$ is less than $n/2$ is bounded by:

If we run the algorithm $n=10,000$ times, the exponent is $-2(10000)(0.01{)}^2=-2$. The error drops to $\sim 13\%$. If we run it $n=1,000,000$ times, the error drops to $e^{-200}$, which is practically zero. Randomized algorithms leverage cheap, parallel compute to exponentially crush error rates.

Lab