Randomized Algorithms // Megha Bose

Prerequisite: Probability as a Language, Constraint Satisfaction & Backtracking

Las Vegas vs Monte Carlo

Las Vegas algorithms always return the correct answer; only the running time is random. Example: randomized quicksort always sorts correctly, but the pivot choices determine how long it takes.

Monte Carlo algorithms run in bounded deterministic time but may return an incorrect answer with bounded probability. Example: Miller-Rabin primality test declares a prime “probably prime” with error probability at most $4^{-k}$ after $k$ rounds.

The distinction matters: Las Vegas algorithms can be run until they terminate, obtaining a correct answer with probability 1. Monte Carlo algorithms require error probability to be driven below a tolerable threshold.

Randomized Quicksort: Expected $O(n \log n)$

Choose the pivot uniformly at random from the remaining elements. Let $z_i$ denote the $i$-th smallest element. Define indicator variables:

$$X_{ij} = \mathbf{1}[\text{element } z_i \text{ and } z_j \text{ are compared}], \quad i < j$$

Two elements $z_i$ and $z_j$ are compared if and only if one of them is chosen as pivot before any other element from ${z_i, z_{i+1}, \ldots, z_j}$. By symmetry:

$$\Pr[X_{ij} = 1] = \frac{2}{j - i + 1}$$

The expected total number of comparisons is:

$$\mathbb{E}!\left[\sum_{i < j} X_{ij}\right] = \sum_{i=1}^{n}\sum_{j=i+1}^{n} \frac{2}{j-i+1} = 2\sum_{i=1}^{n}\sum_{k=2}^{n-i+1}\frac{1}{k} \leq 2n\sum_{k=1}^{n}\frac{1}{k} = 2n H_n = O(n \log n)$$

where $H_n \approx \ln n$ is the $n$-th harmonic number. Each comparison costs $O(1)$, so expected time is $O(n \log n)$.

Karger’s Min-Cut Algorithm

Given an undirected graph $G = (V, E)$ with $n$ vertices, find a cut $(S, \bar{S})$ of minimum size.

Algorithm: Repeat until two vertices remain: pick a random edge $(u, v)$ and contract it (merge $u$ and $v$, remove self-loops, keep parallel edges). The two remaining vertices define a cut; return its size.

Analysis. Let $k$ be the min-cut size. Every vertex has degree $\geq k$, so $|E| \geq nk/2$. The probability of contracting a min-cut edge in step $i$ (when $n - i + 1$ vertices remain) is at most $\frac{k}{(n-i+1)k/2} = \frac{2}{n-i+1}$.

The probability of not contracting any min-cut edge through all $n-2$ contractions:

$$\Pr[\text{success}] \geq \prod_{i=1}^{n-2}\left(1 - \frac{2}{n-i+1}\right) = \prod_{j=3}^{n}\frac{j-2}{j} = \frac{2}{n(n-1)}$$

Repeating $O(n^2 \log n)$ times independently and returning the smallest cut found gives success with probability $\geq 1 - 1/n$ (since $(1 - 2/n(n-1))^{cn^2\ln n} \to 0$). Total time: $O(n^4 \log n)$ naively, or $O(n^2 \log^3 n)$ with Karger-Stein (recursive contraction to $n/\sqrt{2}$).

Bloom Filters

A Bloom filter represents a set $S$ of $n$ elements using a bit array $B$ of $m$ bits and $k$ independent hash functions $h_1, \ldots, h_k : U \to [m]$.

Insert $x$: Set $B[h_i(x)] = 1$ for all $i$.

Query $x$: Return “yes” if $B[h_i(x)] = 1$ for all $i$.

False negatives are impossible. The false positive probability (an element not in $S$ passes the filter) is:

$$p_{\text{FP}} \approx \left(1 - e^{-kn/m}\right)^k$$

This is minimized over $k$ by taking the derivative and solving, giving:

$$k^\ast = \frac{m}{n} \ln 2, \quad p_{\text{FP}}^\ast = \left(\frac{1}{2}\right)^{k^\ast} = 2^{-(m/n)\ln 2} \approx (0.6185)^{m/n}$$

At $m/n = 10$ bits per element, $k^\ast \approx 7$ and $p_{\text{FP}} \approx 0.82%$. Bloom filters use $O(n)$ space, $O(k)$ per operation, and no false negatives - widely used in databases and networking for set membership tests.

Skip Lists

A skip list is a randomized data structure supporting search, insert, and delete in $O(\log n)$ expected time with $O(n)$ space.

Structure: A sorted linked list augmented with $\lceil \log n \rceil$ “express lanes.” Each element at level $\ell$ is independently promoted to level $\ell + 1$ with probability $1/2$ (geometric distribution).

Search: Start at the top level; move right until the next element exceeds the target, then drop down one level. Repeat.

Analysis. The expected number of nodes at level $\ell$ is $n/2^\ell$. The backward analysis argument: tracing the search path backwards from a found node, at each step we go up with probability $1/2$ and left with probability $1/2$. The expected cost to climb $\lceil \log n \rceil$ levels is $O(\log n)$.

Reservoir Sampling

Maintain a uniform random sample of size $k$ from a stream of elements seen so far, using $O(k)$ space.

ReservoirSample(stream, k):
    reservoir = first k elements
    for i = k+1, k+2, ...:
        j = uniform random integer in [1, i]
        if j <= k:
            reservoir[j] = stream[i]
    return reservoir

Invariant: After processing $i$ elements, each of the $i$ elements is in the reservoir with probability $k/i$.

Proof by induction. Base: after $k$ elements, each is included with probability $k/k = 1$. Step: element $i+1$ is included with probability $k/(i+1)$. Each existing reservoir member survives with probability $1 - (k/(i+1)) \cdot (1/k) = i/(i+1)$. Combined probability of still being in reservoir: $(k/i) \cdot (i/(i+1)) = k/(i+1)$. QED.

Monte Carlo Integration

To estimate $\int_a^b f(x), dx$: draw $x_1, \ldots, x_n$ uniformly from $[a,b]$ and approximate:

$$\int_a^b f(x), dx \approx \frac{b-a}{n}\sum_{i=1}^{n} f(x_i)$$

By the law of large numbers, this converges to the true integral. The standard error is:

$$\text{SE} = \frac{(b-a)\sigma_f}{\sqrt{n}} = O!\left(\frac{1}{\sqrt{n}}\right)$$

where $\sigma_f^2 = \text{Var}(f(X))$. Monte Carlo integration is dimension-independent: for a $d$-dimensional integral, the error is still $O(1/\sqrt{n})$, whereas deterministic quadrature rules scale as $O(n^{-r/d})$ for $r$-th order rules, suffering the curse of dimensionality. Monte Carlo dominates for $d \gtrsim 5$.

Examples

Universal hashing. Fix a prime $p \geq |U|$ and choose $a \in {1, \ldots, p-1}$, $b \in {0, \ldots, p-1}$ uniformly at random. Define $h_{a,b}(x) = ((ax + b) \bmod p) \bmod m$. This is a universal family: for any $x \neq y$, $\Pr[h_{a,b}(x) = h_{a,b}(y)] \leq 1/m$. With $n$ keys and $m = n$ slots, expected chain length is $O(1)$, giving $O(1)$ expected lookup.

Miller-Rabin primality testing. To test if $n$ is prime, write $n - 1 = 2^s d$ with $d$ odd. Choose $a$ uniformly from ${2, \ldots, n-2}$. Compute $a^d \bmod n$. If it equals 1 or $-1$, or if any of $a^{2d}, a^{4d}, \ldots, a^{2^{s-1}d}$ equals $-1$ mod $n$, then $n$ is a “strong probable prime” to base $a$. Any composite $n$ passes this test for at most $n/4$ choices of $a$, so $k$ independent rounds achieve error probability $\leq 4^{-k}$.