Randomized Graph and Number Algorithms

CS 265/CME309: Randomized Algorithms — Lectures 2 & 3 Gregory Valiant, updated by Mary Wootters (Stanford, Fall 2020)

Table of Contents

• 1. Linearity of Expectation
  • 1.1 Statement and Basic Examples
  • 1.2 Coupon Collector Problem
• 2. Karger’s Min-Cut Algorithm
  • 2.1 Problem Definition
  • 2.2 Edge Contraction and the Algorithm
  • 2.3 Analysis: Probability of Success
  • 2.4 Boosting via Repetition
• 3. Karger-Stein Algorithm
  • 3.1 The Key Observation
  • 3.2 Modified-Karger Algorithm
  • 3.3 Analysis
• 4. Primality Testing
  • 4.1 Algebra Background
  • 4.2 Fermat’s Test
  • 4.3 Miller-Rabin Algorithm
  • 4.4 Fingerprinting with Primes
• 5. QuickSort Analysis via Linearity of Expectation
• References

1. Linearity of Expectation

1.1 Statement and Basic Examples

Theorem (Linearity of Expectation). For any random variables \(X_1, \ldots, X_n\) (not necessarily independent) and scalars \(a_1, \ldots, a_n\): \[\mathbb{E}\!\left[\sum_i a_i X_i\right] = \sum_i a_i \,\mathbb{E}[X_i].\]

📐 Geometric random variable via linearity. Let \(X\) be the number of flips of a \(p\)-biased coin until the first heads. Rather than computing \(\mathbb{E}[X] = \sum_{k=1}^\infty k(1-p)^{k-1}p\) directly, use the recurrence:

\[\mathbb{E}[X] = p \cdot 1 + (1-p)(1 + \mathbb{E}[X]) \implies \mathbb{E}[X] = \frac{1}{p}.\]

1.2 Coupon Collector Problem

💡 Setup. There are \(n\) distinct coupons. Each trial draws one uniformly at random (with replacement). How many trials until all \(n\) are collected?

Let \(X_i\) = number of additional trials to collect the \(i\)-th new coupon, given that \(i-1\) distinct coupons have been seen. At that point, the probability of a new coupon on any trial is \((n - (i-1))/n\), so \(X_i \sim \text{Geometric}\!\left(\frac{n-i+1}{n}\right)\) and:

\[\mathbb{E}[X_i] = \frac{n}{n-i+1}.\]

By linearity, the expected total trials to collect all coupons is:

\[\mathbb{E}\!\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n \frac{n}{n-i+1} = n \sum_{k=1}^n \frac{1}{k} = n H_n = \Theta(n \log n),\]

where \(H_n\) is the \(n\)-th harmonic number.

2. Karger’s Min-Cut Algorithm

2.1 Problem Definition

Definition (Cut). A cut of graph \(G = (V, E)\) is a partition \(V = S_1 \sqcup S_2\) with \(S_1, S_2 \neq \emptyset\). An edge (crosses the cut if its endpoints are on opposite sides. A min-cut minimizes the number of crossing edges.

Min-cut has applications in clustering, image segmentation, and network reliability. While efficient deterministic algorithms exist (e.g., max-flow/min-cut), Karger’s 1993 randomized algorithm is remarkably elegant and achieves competitive runtime after Karger-Stein’s improvement.

2.2 Edge Contraction and the Algorithm

Definition (Edge Contraction). Contracting edge \((u, v)\) in \(G\) merges \(u\) and \(v\) into a single supernode, keeps all non-self-loop edges, and removes the self-loop \((u, v)\).

graph LR
    subgraph Before
        A --- B
        A --- C
        B --- C
        B --- D
    end
    subgraph After contracting B-C
        A2["A"] --- BC["BC"]
        A2 --- BC
        BC --- D2["D"]
    end

Algorithm (Karger’s Min-Cut). Given \(G = (V, E)\) with \(|V| = n\): 1. Repeat \(n - 2\) times: choose a remaining edge uniformly at random and contract it. 2. Return the cut separating the two remaining supernodes.

import random

def karger_mincut(adj):
    """
    adj: dict mapping node -> list of neighbors (multigraph allowed)
    Returns: size of the cut found
    """
    # represent each supernode as a frozenset of original vertices
    nodes = {v: {v} for v in adj}
    edges = [(u, v) for u in adj for v in adj[u] if u < v]

    while len(nodes) > 2:
        u, v = random.choice(edges)
        # merge v into u
        nodes[u] |= nodes[v]
        del nodes[v]
        edges = [(a if a != v else u, b if b != v else u)
                 for a, b in edges
                 if not (a == u and b == v) and not (a == v and b == u)]

    return len(edges)  # remaining edges = cut size

2.3 Analysis: Probability of Success

Lemma (Contraction Preserves Min-Cut). If we contract an edge that does not cross a min-cut \(C = (S_1, S_2)\), then \(C\) is also a min-cut of the contracted graph.

Proof. Contracting a non-cut edge cannot decrease the min-cut value (any cut in the new graph corresponds to a cut of equal size in the old graph), and the partition \(S_1, S_2\) still exists and has the same crossing count. \(\square\)

Theorem (Karger). The probability that the above algorithm returns a specific min-cut \(C\) is at least \(\dfrac{2}{n(n-1)}\).

Proof. Let \(k\) = number of edges crossing \(C\). For the algorithm to return \(C\), none of the \(n-2\) contractions may contract a crossing edge. Let \(E_i\) = event that the \(i\)-th contraction does not cross \(C\).

Key bound on \(\Pr[E_1]\). Since \(C\) is a min-cut, every vertex has degree \(\geq k\), so \(|E| \geq nk/2\). Thus: \[\Pr[E_1] = 1 - \frac{k}{|E|} \geq 1 - \frac{k}{nk/2} = 1 - \frac{2}{n} = \frac{n-2}{n}.\]

Inductive step. Conditioning on \(E_1, \ldots, E_{i-1}\), the graph has \(n - (i-1)\) vertices and (by the Lemma) \(C\) is still a min-cut. By the same argument: \[\Pr[E_i \mid E_1, \ldots, E_{i-1}] \geq 1 - \frac{2}{n-i+1} = \frac{n-i-1}{n-i+1}.\]

Telescoping product: \[\Pr[\text{output } C] \geq \prod_{i=1}^{n-2} \frac{n-i-1}{n-i+1} = \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdots \frac{1}{3} \cdot \frac{0}{2}.\]

Wait — the last factor has numerator 0. Let’s be careful: the product runs from \(i=1\) to \(i = n-2\). The \(i\)-th factor is \(\frac{n-i-1}{n-i+1}\). At \(i = n-2\): \(\frac{1}{3}\). At \(i = n-3\): \(\frac{2}{4}\). The numerators are \(n-3, n-4, \ldots, 1\) and denominators \(n-1, n-2, \ldots, 3\). All intermediate terms cancel:

\[\Pr[\text{output }C] \geq \frac{(n-2)!/(n(n-1))\cdot \ldots}{} = \frac{2}{n(n-1)}. \quad \square\]

2.4 Boosting via Repetition

Running Karger’s algorithm \(t\) times independently and returning the smallest cut found:

\[\Pr[\text{all } t \text{ runs fail}] \leq \left(1 - \frac{2}{n(n-1)}\right)^t \leq e^{-2t/n(n-1)}.\]

Taking \(t = \frac{c \cdot n(n-1)}{2} \approx cn^2/2\) gives failure probability \(\leq e^{-c}\). With \(O(|E|)\) per run, total time is \(O(cn^2 |E|)\).

3. Karger-Stein Algorithm

3.1 The Key Observation

The success probability per step is not uniform. The \(i\)-th contraction (on a graph with \(n - i + 1\) vertices) fails with probability: \[\frac{2}{n-i+1}.\]

Early contractions are very unlikely to fail (\(\approx 2/n\)); late contractions fail with probability up to \(2/3\). Most failures happen in the last few steps.

graph LR
    A["Step 1
Pr[fail] ≈ 2/n"] --> B["Step 2
Pr[fail] ≈ 2/(n-1)"]
    B --> C["..."] --> D["Step n-3
Pr[fail] = 1/3"]
    D --> E["Step n-2
Pr[fail] = 1/2"]

Implication: Rather than restarting from scratch when a run fails, only redo the last few (high-failure) steps from a shared “checkpoint.”

3.2 Modified-Karger Algorithm

Algorithm (Modified-Karger / Karger-Stein sketch).

Given \(G\) on \(n\) vertices, parameters \(m\) and \(k\): 1. Run Karger’s from \(n\) vertices down to \(m\) vertices, producing graph \(G'\) on \(m\) supernodes. 2. Run Karger’s \(k\) more times independently on \(G'\) (each down to 2 supernodes). 3. Return the smallest cut found across all \(k\) runs.

3.3 Analysis

Failure probability of step 1 (reducing \(G \to G'\)): by the same telescoping argument as before, \[\Pr[\text{step 1 destroys } C] \leq 1 - \frac{m(m-1)}{n(n-1)}.\]

Failure probability of one run on \(G'\): by Karger’s theorem on \(m\) vertices, \(\leq 1 - \frac{2}{m(m-1)}\).

Overall failure: \[\Pr[\text{fail}] \leq \underbrace{\left(1 - \frac{m(m-1)}{n(n-1)}\right)}_{\text{step 1 fails}} + \underbrace{\left(1 - \frac{2}{m(m-1)}\right)^k}_{\text{all } k \text{ step-2 runs fail}}.\]

4. Primality Testing

4.1 Algebra Background

By the prime number theorem, the density of primes near \(n\) is \(\sim 1/\ln n\), so finding large primes is feasible by random sampling and testing. The challenge is the test itself.

Key algebraic structures:

Fact (Lagrange’s Theorem). For any group \(G\) and subgroup \(H \subsetneq G\): \(|H|\) divides \(|G|\), and \(|H| \leq |G|/2\).

Fact (Fermat’s Little Theorem). For prime \(n\) and any \(a \in \mathbb{Z}_n^*\): \[a^{n-1} \equiv 1 \pmod{n}.\]

Proof sketch: \(\mathbb{Z}_n^*\) has order \(n-1\). By Lagrange, the order of any element divides \(n-1\), so \(a^{n-1} = (a^{\text{ord}(a)})^{(n-1)/\text{ord}(a)} = 1\). \(\square\)

4.2 Fermat’s Test

Algorithm (Fermat’s Test). Given \(n\): 1. Choose \(x \in \{1, \ldots, n-1\}\) uniformly at random. 2. If \(x^{n-1} \equiv 1 \pmod{n}\): output “prime”; else output “composite.”

Runtime: \(O(\log^2 n)\) via repeated squaring (computes \(x^{n-1} \bmod n\) with \(O(\log n)\) multiplications of \(O(\log n)\)-bit numbers).

Proposition. For any composite \(n\) that is not a Carmichael number, Fermat’s test outputs “composite” with probability \(\geq 1/2\).

Proof: From Exercise 5(c) above. \(\square\)

4.3 Miller-Rabin Algorithm

Key observation. For prime \(n\), the only square roots of \(1\) in \(\mathbb{Z}_n^*\) are \(\pm 1\).

Proof: If \(a^2 \equiv 1 \pmod{n}\) for prime \(n\), then \(n \mid (a-1)(a+1)\). Since \(n\) is prime, \(n \mid (a-1)\) or \(n \mid (a+1)\), i.e., \(a \equiv \pm 1\). \(\square\)

For composite \(n = s \cdot t\) with \(\gcd(s,t) = 1\), there can be four square roots of \(1\) (via CRT). The Miller-Rabin test searches for these nontrivial roots.

Write \(n - 1 = 2^k m\) with \(m\) odd.

Algorithm (Miller-Rabin / Rabin-Miller). Given \(n\): 1. If \(n\) is even or a prime power, output “composite.” 2. Compute \(k, m\) with \(n - 1 = 2^k m\), \(m\) odd. 3. Choose \(x \in \{1, \ldots, n-1\}\) uniformly at random. Compute the sequence: \[\left(x^m,\; x^{2m},\; x^{4m},\; \ldots,\; x^{2^k m}\right) \pmod{n}.\] 4. If \(x^{2^k m} \not\equiv 1\): output “composite” (fails Fermat’s test). 5. If any \(x^{2^i m} \not\equiv \pm 1\) but \(x^{2^{i+1} m} \equiv 1\): output “composite” (nontrivial square root found). 6. Else: output “prime.”

def miller_rabin(n, trials=20):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    # write n-1 = 2^k * m
    k, m = 0, n - 1
    while m % 2 == 0:
        k += 1
        m //= 2
    import random
    for _ in range(trials):
        x = random.randrange(2, n)
        seq = [pow(x, m, n)]
        for _ in range(k):
            seq.append(pow(seq[-1], 2, n))
        if seq[-1] != 1:
            return False  # fails Fermat
        for i in range(k):
            if seq[i] not in (1, n-1) and seq[i+1] == 1:
                return False  # nontrivial sqrt of 1
    return True

Theorem (Rabin, 1976; Miller, 1976). If \(n\) is prime, Miller-Rabin always outputs “prime.” If \(n\) is composite (and not a prime power), Miller-Rabin outputs “composite” with probability \(\geq 1/2\) over \(x\).

Proof sketch. Define \(b\) = largest \(i < k\) such that \(\exists y \in \mathbb{Z}_n^*\) with \(y^{2^i m} \equiv -1 \pmod{n}\). The set \(S = \{x \in \mathbb{Z}_n^* : x^{2^b m} \equiv \pm 1\}\) is a proper subgroup of \(\mathbb{Z}_n^*\) (via a CRT-based argument that constructs an element not in \(S\)). If Miller-Rabin outputs “prime,” then \(x \in S\). By Lagrange, \(|S| \leq |\mathbb{Z}_n^*|/2\), so \(\Pr[x \in S] \leq 1/2\). \(\square\)

4.4 Fingerprinting with Primes

A beautiful application of primality testing to string comparison:

Problem. Alice has an \(n\)-bit file \(A\); Bob has \(B\). They want to check \(A \stackrel{?}{=} B\) using minimal communication.

Algorithm (Random Prime Fingerprinting). 1. Pick \(p\) uniformly at random from primes \(< N\). 2. Check if \(A \equiv B \pmod{p}\).

Proposition. If \(A \neq B\), for \(N = cn\log n\), \(\Pr[\text{false positive}] \leq 3/c\).

Proof sketch. \(|A - B| \leq 2^n\), so \(A - B\) has at most \(n\) distinct prime factors. By the prime number theorem, the number of primes \(< N\) is \(\sim N/\ln N\). Thus: \[\Pr[\text{fail}] \leq \frac{n}{\pi(N)} \leq \frac{n \cdot \ln(cn\log n)}{cn\log n} \leq \frac{3}{c}. \quad \square\]

Communication cost: Alice sends just \(\log_2 N \approx \log_2(cn\log n) = O(\log n)\) bits — a single \(O(\log n)\)-bit prime and the \(O(\log n)\)-bit fingerprint. For a 1 GB file (\(n \approx 2^{30}\)), this is about 60 bits total!

5. QuickSort Analysis via Linearity of Expectation

Algorithm (QuickSort with Random Pivot). 1. If \(|S| \leq 1\), return \(S\). 2. Pick a pivot \(x_i\) uniformly at random from \(S\). 3. Partition into \(S_{<} = \{s < x_i\}\) and \(S_{>} = \{s > x_i\}\). 4. Recurse on \(S_<\) and \(S_>\); concatenate with \(x_i\) in the middle.

Theorem. \(\mathbb{E}[\text{number of comparisons}] \leq 2n\log n + O(n)\).

Proof. Let \(z_1 < z_2 < \cdots < z_n\) be the sorted input. Define \(X_{ij} = \mathbf{1}[z_i \text{ is compared to } z_j]\) for \(i < j\).

Key observation: \(z_i\) and \(z_j\) are compared at most once. They are compared iff the first element of \(\{z_i, z_{i+1}, \ldots, z_j\}\) chosen as a pivot is either \(z_i\) or \(z_j\). (Before that, they remain in the same subarray; after, they are separated forever.)

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

By linearity of expectation:

\[\mathbb{E}[\text{comparisons}] = \sum_{i < j} \frac{2}{j-i+1} = \sum_{k=2}^{n} \frac{2(n+1-k)}{k} \leq 2(n+1)\sum_{k=2}^n \frac{1}{k} < 2n\log n + O(n). \quad \square\]

References