Neural Sync Active

Randomized Algorithms

Registry Synced

Randomized Algorithms

718 words

4 min read

Reading compass

Now · 🎯 Learning Objectives

Randomized Algorithms

🎯 Learning Objectives

Distinguish Monte Carlo vs. Las Vegas algorithms
Analyze expected running time using probability
Apply randomness to graph cut and SAT problems
Test primality using Miller-Rabin
Derive concentration bounds (Chernoff, Markov)

1. Types of Randomization

Type	Always Correct?	Always Fast?	Example
Las Vegas	Yes	Expected	Randomized quicksort
Monte Carlo	With high probability	Yes	Miller-Rabin primality

2. Randomized Min-Cut (Karger's Algorithm)

2.1 Algorithm

Contract random edges until 2 nodes remain. The edge between them = cut.


python
import random
def karger_min_cut(graph):
    vertices = list(graph.keys())
    while len(vertices) > 2:
        u = random.choice(vertices)
        v = random.choice([n for n in graph[u] if n in vertices])
        # Merge u and v
        vertices.remove(v)
        graph[u].extend(graph[v])
        # Remove self-loops
        graph[u] = [x for x in graph[u] if x in vertices]
    return len(graph[vertices[0]])

2.2 Analysis

Probability a specific min-cut survives one contraction: $\geq 1 - 2/n$
Probability it survives all $n-2$ contractions: $\geq \frac{2}{n(n-1)} = \Omega(1/n^2)$
Repeat $O(n^2)$ times → success probability $\geq 1 - 1/e$

3. Randomized MAX-SAT

3.1 Algorithm

Randomly assign each variable True/False with probability 0.5. Expected performance: Each clause with

k

literals is satisfied with probability

1 - (1/2)^k

. For 3SAT:

E[\text{satisfied}] \geq (1 - 1/8)m = 7m/8

(87.5% approximation).

3.2 Derandomization via Conditional Expectations

Process variables one by one. For each variable, try both True and False, compute expected value if remaining variables are random. Choose setting that maximizes conditional expectation. Guarantees at least

7m/8

clauses satisfied (deterministically).

4. Miller-Rabin Primality Test

4.1 Algorithm

For odd

n

, write

n-1 = 2^s \cdot d

. Choose random

a \in [2, n-2]

. Compute

x = a^d \mod n

. If

x = 1

x = -1

, declare probably prime. Otherwise, repeat

s-1

times:

x = x^2 \mod n

. If

x = -1

, declare probably prime. If no

x = -1

found,

n

is composite.

4.2 Error Analysis

Iterations	Error Bound
1	$< 1/4$
$k$	$< (1/4)^k$
10	$< 10^{-6}$

5. Concentration Bounds

Inequality	When to Use	Statement
Markov	Non-negative random variable	$P(X \geq t) \leq E[X]/t$
Chebyshev	Known variance	$P(
Chernoff	Sum of independent variables	$P(X \geq (1+\delta)\mu) \leq e^{-\delta^2\mu/3}$

6. Common Pitfalls

Pitfall: Assuming Independence Where None Exists

The mistake: Applying Chernoff bound to dependent random variables. Correct approach: Use union bound or more sophisticated concentration inequalities (Azuma, McDiarmid) for dependent variables.

7. Key Concepts Reference

Algorithm	Type	Complexity	Success
Karger min-cut	Monte Carlo	$O(n^2 \log n)$	$1 - 1/e$
Randomized MAX-SAT	Las Vegas (derandomizable)	$O(m)$	0.875-approx
Miller-Rabin	Monte Carlo	$O(k \log^3 n)$	$(1/4)^k$ error
Quickselect	Las Vegas	$O(n)$ expected	Always correct

8. 📝 Practice Questions

Q1: Run one iteration of Karger's on K₄ (complete graph on 4 vertices). What's the probability of finding the minimum cut?

Answer: Min cut of K₄ = 3. Probability a specific min-cut survives: 2/(4×3) = 1/6 per iteration. With $O(n²) = 16$ iterations, success probability ≈ $1 - (5/6)^{16} ≈ 0.94$ . Q2: For a 3SAT formula with 100 clauses, what's the expected number satisfied by random assignment?

Answer: Each clause satisfied with probability 7/8. Expected = 100 × 7/8 = 87.5 clauses. By linearity of expectation, this holds even if clauses share variables. Q3: Miller-Rabin says n is probably prime with k=5 iterations. What's the error probability?

Answer: Error probability < (1/4)^5 = 1/1024 ≈ 0.001. So there's a 99.9% chance n is prime. For cryptographic applications, 20+ iterations are used (error < 2^{-40}). Q4: Derandomize the MAX-SAT algorithm. What guarantee do we get?

Answer: Process variables sequentially. For each variable, compute expected satisfied clauses if we set it True vs. False (with remaining variables random). Choose the better setting. This guarantees at least 7/8 of MAX-SAT optimum (deterministically). This is the method of conditional expectations. Q5: Apply Markov's inequality: Expected runtime of algorithm is 1 hour. What's P(runtime > 10 hours)?

Answer: P(X > 10) ≤ E[X]/10 = 1/10 = 10%. Markov's inequality is very weak but requires no assumptions about distribution.

9. 🔗 Cross-References

Week 6 - NP-Completeness: Why randomness helps
Week 7 - Approximation: Randomized approximation
BSCS3003 (Probability): Probability foundations Join Discord PreviousApproximation AlgorithmsNextAdvanced DS