Randomized Algorithms¶

From Computability, Complexity & Algorithms — Charles Brubaker and Lance Fortnow

Introduction¶

Randomization is a fundamental algorithmic tool. Rather than always making the same deterministic choices, randomized algorithms flip coins — and often achieve better expected performance or simpler analysis than their deterministic counterparts.

Polynomial Identity Testing¶

Problem: Given two polynomial representations \(A\) and \(B\) (each of degree \(\leq d\)), determine whether \(A \equiv B\).

PITest — Polynomial identity testing: evaluate both polynomials at a random point.¶

Randomized algorithm:

Pick a random integer \(r\) uniformly from \(\{1, \ldots, 100d\}\).
Evaluate \(A(r)\) and \(B(r)\).
If \(A(r) = B(r)\), declare equal; otherwise declare unequal.

Why it works — Fundamental Theorem of Algebra:

FTA — A non-zero polynomial of degree \(d\) has at most \(d\) roots.¶

If \(A \not\equiv B\), then \(A - B\) is a non-zero polynomial of degree \(\leq d\), so it has at most \(d\) roots. The probability of a false positive is:

\[\Pr[\text{false positive}] \leq \frac{d}{100d} = \frac{1}{100}\]

Discrete Probability¶

A discrete probability space consists of:

Sample space \(\Omega\) — a finite or countably infinite set of outcomes.
Probability function \(\Pr : 2^\Omega \to [0,1]\) satisfying:

\[\Pr(E) \geq 0, \quad \Pr(\Omega) = 1, \quad \Pr\!\left(\bigcup_i E_i\right) = \sum_i \Pr(E_i) \text{ (disjoint events)}\]

For uniform distributions: \(\Pr(S) = |S| / |\Omega|\).

DiscreteProbSpace — Formal definition of a discrete probability space.¶

BoundingProbabilitiesQuiz — *Quiz:* Bound the probability of an event in a given sample space.¶

Repeated Trials¶

When running an algorithm \(k\) times independently, the probability that at least one trial succeeds (given per-trial success probability \(p\)) is:

\[\Pr[\text{at least one success}] = 1 - (1-p)^k\]

RepeatedTrialsAlg — Repeated trials algorithm pseudocode.¶

RepeatedTrials2DGrid — Two-dimensional sample space for two independent trials.¶

RepeatedTrialsRows — Event \(E_1\) as rows in the sample space grid.¶

RepeatedTrialsCols — Event \(E_2\) as columns in the sample space grid.¶

RepeatedTrialsBoth — Intersection \(E_1 \cap E_2\) for independent events.¶

Conditional Probability and Independence¶

Conditional probability:

\[\Pr(E \mid F) = \frac{\Pr(E \cap F)}{\Pr(F)}\]

CondProbDef — Venn diagram illustration of conditional probability.¶

BullseyeQuiz — *Quiz:* Dart-throwing probability exercise using conditional probability.¶

Independence: Events \(E\) and \(F\) are independent if:

\[\Pr(E \cap F) = \Pr(E) \cdot \Pr(F)\]

Monte Carlo vs. Las Vegas Algorithms¶

Monte Carlo algorithms may return incorrect answers but with bounded error probability:

One-sided error: errors only on one type of input (e.g., declaring unequal polynomials equal, never vice versa).
Two-sided error: errors possible on either type of input.

MonteCarloOneSided — One-sided Monte Carlo: never wrong when polynomials are truly equal.¶

Las Vegas algorithms are always correct; randomness only affects running time.

Example: Polynomial identity testing can be made Las Vegas by sampling without replacement from \(\{1, \ldots, 100d\}\). After choosing \(d+1\) distinct points, at least one must be a non-root if \(A \not\equiv B\).

SampleWithoutReplacementQuiz — *Quiz:* Compute the success probability when sampling without replacement.¶

Random Variables and Expectation¶

A random variable \(X : \Omega \to \mathbb{R}\) assigns a real value to each outcome.

Expectation:

\[\mathbb{E}[X] = \sum_{v \in X(\Omega)} v \cdot \Pr(X = v)\]

Linearity of expectation (holds even for dependent random variables):

\[\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y], \qquad \mathbb{E}[aX] = a\,\mathbb{E}[X]\]

This is the key tool for analyzing randomized algorithms.

Randomized Quicksort¶

QuicksortCode — Quicksort pseudocode with random pivot selection.¶

Best case (ideal pivots): \(O(n \log n)\)
Worst case (always min/max pivot): \(O(n^2)\)

MiddlePivots — Balanced recursion tree with near-median pivots.¶

UnluckyPivots — Unbalanced recursion tree when the pivot is always extreme.¶

Expected-Case Analysis¶

Let \(X_{ij} = 1\) if elements \(z_i\) and \(z_j\) (with \(i < j\)) are ever compared, and 0 otherwise.

Two elements \(z_i\) and \(z_j\) are compared if and only if one of them is chosen as the pivot before any element strictly between them. By symmetry:

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

Total expected comparisons:

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

QuicksortConcentration — Running time concentrates tightly around \(O(n \log n)\) — large deviations are exponentially unlikely.¶

Karger’s Minimum Cut Algorithm¶

Problem: Given an undirected graph \(G = (V, E)\), find the minimum-sized set of edges whose removal disconnects \(G\).

MinCutDef — Definition of a minimum cut.¶

MinCutExample — Edge contraction example — merging two vertices into one.¶

Algorithm (Karger’s contraction):

MinCutAlg — Karger’s algorithm pseudocode.¶

while |V| > 2:
    pick a random edge (u, v)
    contract u and v into a single vertex
    remove self-loops
return the remaining edges (the cut)

Success Probability¶

MinCutAnalysis — Probability analysis for Karger’s algorithm.¶

Let \(C\) be a minimum cut of size \(k\). At contraction step \(j\) (when \(n - j\) vertices remain), the probability that no edge of \(C\) is contracted is:

\[\Pr(E_{j+1} \mid E_1 \cap \cdots \cap E_j) \geq \frac{n - j - 2}{n - j}\]

Telescoping over all \(n - 2\) steps:

\[\Pr[\text{success}] \geq \prod_{j=0}^{n-3} \frac{n-j-2}{n-j} = \frac{2}{n(n-1)}\]

Amplification: Run \(n(n-1)\ln(1/\varepsilon)\) independent trials and return the smallest cut found. Failure probability drops to at most \(\varepsilon\):

\[\Pr[\text{all fail}] \leq \left(1 - \frac{2}{n(n-1)}\right)^{n(n-1)\ln(1/\varepsilon)} \leq \varepsilon\]

Maximum 3-SAT¶

Problem: Given a 3-CNF formula with \(m\) clauses, find an assignment maximising the number of satisfied clauses.

MaxSatDef — Maximum 3-SAT problem definition.¶

Theorem: Every 3-CNF formula has an assignment satisfying at least \(7m/8\) clauses.

Proof via expectation: Each clause has exactly one out of \(2^3 = 8\) assignments that fails it. For a uniformly random assignment:

\[\Pr[\text{clause } C_i \text{ satisfied}] = \frac{7}{8}\]

By linearity of expectation:

\[\mathbb{E}[\text{satisfied clauses}] = \frac{7m}{8}\]

Since the expectation is \(7m/8\), some assignment must achieve at least this.

EofY — Expected number of satisfied clauses equals \(7m/8\).¶

Derandomization via Method of Conditional Expectations¶

Instanciate — Instantiate one variable at a time, choosing the value that maximises the conditional expected number of satisfied clauses.¶

DerandomizedMaxSAT — Derandomized Max-3-SAT algorithm pseudocode.¶

for each variable x_i:
    compute E[satisfied | x_1,...,x_{i-1}, x_i = True]
    compute E[satisfied | x_1,...,x_{i-1}, x_i = False]
    set x_i to whichever gives the higher expectation

Invariant: At each step the conditional expectation \(\geq 7m/8\).

DerandomizedMaxSATAnalysis — Analysis: the greedy choice maintains \(\geq 7m/8\) satisfied clauses throughout, giving a deterministic polynomial-time \(7/8\)-approximation.¶

Hardness of Approximation and the PCP Theorem¶

Question: Can we do better than \(7/8\) for Max-3-SAT?

HardnessOfApproxSetup — Setup: what does a better approximation imply?¶

PCP Theorem: For any \(\alpha > 7/8\) there exists a polynomial-time reduction \(f\) mapping 3-CNF formulas such that:

Satisfiable formulas map to satisfiable formulas.
Unsatisfiable formulas map to instances where no assignment satisfies more than an \(\alpha\) fraction of clauses.

HardnessOfApproxCookLevin — Apply Cook-Levin to reduce an arbitrary NP language to SAT.¶

HardnessOfApproxPCP — Apply the PCP transformation, then use the approximation algorithm to distinguish the two cases — solving NP-complete problems in polynomial time.¶

Conclusion: An \(\alpha\)-approximation for Max-3-SAT with \(\alpha > 7/8\) would imply \(P = NP\). The \(7/8\) ratio is tight.

Complexity Classes¶

RP (Randomized Polynomial time): One-sided Monte Carlo algorithms; always correct on “No” instances, correct on “Yes” instances with probability \(\geq 1/2\).
BPP (Bounded-error Probabilistic Polynomial time): Two-sided Monte Carlo; correct on any instance with probability \(\geq 2/3\).
ZPP (Zero-error Probabilistic Polynomial time): Las Vegas algorithms with expected polynomial runtime.

Open question (P vs. BPP): Whether every language decidable by a two-sided Monte Carlo polynomial algorithm can also be decided deterministically in polynomial time remains unresolved.

\[P \subseteq RP \subseteq BPP, \qquad ZPP = RP \cap \text{co-RP}\]

Key Formulas¶

Polynomial identity testing error bound:

\[\Pr[\text{false positive}] \leq \frac{d}{|\text{domain}|}\]

Linearity of expectation:

\[\mathbb{E}\!\left[\sum_i X_i\right] = \sum_i \mathbb{E}[X_i]\]

Quicksort expected comparisons:

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

Karger’s success probability:

\[\Pr[\text{success}] \geq \frac{2}{n(n-1)}\]

Max-3-SAT expectation: