Probability Theory
The Probabilistic Method
Ramsey numbers $R(k,k)$ - the smallest $n$ such that any 2-coloring of $K_n$ contains a monochromatic $K_k$ - are known only for small $k$: $R(3,3)=6$, $R(4,4)=18$. Erdos proved in 1947 that $R(k,k) > 2^{k/2}$ without constructing a single explicit coloring - by showing that a random coloring works with positive probability.
- Sparse hash functions: the probabilistic method proves the existence of hash functions with few collisions - the basis of Cuckoo Hashing and Bloom filters.
- Derandomization: the Lovász Local Lemma (LLL) enables constructive search for objects whose existence is proved by the probabilistic method. The Moser-Tardos algorithm (2010) achieves polynomial time for LLL.
- Random graphs (Erdos-Renyi $G(n,p)$): thresholds for connectivity ($p = \log n / n$) and triangle appearance ($p = 1/n$) are all derived via first and second moment methods.
Цели урока
- Apply the first moment method (naive probabilistic method) for lower bounds on combinatorial quantities
- Use the second moment method for phase transition thresholds in random graphs
- State and apply the Lovász Local Lemma (LLL)
Предварительные знания
- Linearity of expectation and indicator variables
- Discrete probability: inclusion-exclusion formula
- Graph theory: colorings, cliques, independent sets
First moment method: existence via expectation
First moment method: $\mathbb{E}[X] > 0 \Rightarrow P(X > 0) > 0 \Rightarrow$ there exists an outcome with $X > 0$. Application to Ramsey numbers: $P(K_n$ has no monochromatic $K_k) > 0$ for $n < 2^{k/2}$. Computation: $\mathbb{E}[\text{number of mono-cliques}] = \binom{n}{k} 2^{1-\binom{k}{2}}$. When $\mathbb{E} < 1$, with nonzero probability there is no monochromatic clique - so such a coloring exists. This proves $R(k,k) > 2^{k/2}$.
Lovász Local Lemma (LLL): let $A_1, \ldots, A_m$ be events, each depending on at most $d$ others, with $P(A_i) \leq p$. If $ep(d+1) \leq 1$ (where $e = 2.718...$), then $P(\bigcap \bar A_i) > 0$ - all bad events can be simultaneously avoided. Application: existence of a $(k,2)$-coloring for $n < k^2 \cdot 2^{k-3}$ (stronger than the naive method).
The probabilistic method proves existence but does not give a construction. For algorithmic purposes, derandomization is needed. The Moser-Tardos algorithm (2010) constructively realizes LLL in polynomial time: it resolves violations iteratively, and the correctness analysis itself uses the probabilistic method.
Paul Erdos and Alfred Renyi founded the theory of random graphs in 1959-1960, st
Paul Erdos and Alfred Renyi founded the theory of random graphs in 1959-1960, studying threshold phenomena. Erdos had been applying the probabilistic method since 1947. The Lovász Local Lemma was proved by Erdos and Lovász in 1975. The constructive version of LLL (Moser-Tardos, 2010) was a breakthrough in algorithmic theory of random structures.
First-moment argument and Ramsey numbers
Pál Erdős published a 3-page note in 1947 that proved the lower bound $R(k,k) > 2^{k/2}$ via a random coloring, with no explicit graph constructed. The note founded probabilistic combinatorics: 78 years later, the best known lower bound for $R(k,k)$ remains within a constant factor of Erdős's original result.
The probabilistic method gives $R(4,4) > 2^2 = 4$. What exactly does this mean?
Second-moment method and graph thresholds
Erdős and Rényi studied the model $G(n,p)$ in 1959 and discovered sharp threshold phenomena: the fraction of graphs containing a triangle jumps from 0 to 1 in a window of width $\Theta(1/n)$ around $p = 1/n$. Modern Internet topology graphs of 4.6 billion IP nodes display the same picture: connectivity appears at a critical $p_c$ as a near step function.
In $G(n,p)$ the triangle count $X$ has $E[X] = c$ and $\mathrm{Var}(X)/(E[X])^2 \to 0$. What does the second-moment method conclude?
The Lovász Local Lemma
László Lovász proved the local lemma in 1975, sidestepping the weakness of the union bound when many bad events are weakly dependent. In 2010, Robin Moser and Gábor Tardós built an algorithmic version: for 3-SAT with each variable occurring in at most 3 clauses, a satisfying assignment is found in $O(n)$ expected steps.
Symmetric LLL: bad events with $P(A_i) \le 0.01$, each depending on at most $d = 4$ other events. Does the lemma apply?
Second moment method: triangle threshold
In $G(n,p)$ let $X$ be the number of triangles. $\mathbb{E}[X] = \binom{n}{3}p^3 \sim n^3 p^3/6$. Threshold: $\mathbb{E}[X] = 1$ at $p = n^{-1}$. Second moment: $\mathbb{E}[X^2] = \mathbb{E}[X]^2 + O(n^3 p^4 + n^4 p^5)$. By the Paley-Zygmund inequality: $P(X > 0) \geq (\mathbb{E}[X])^2/\mathbb{E}[X^2]$. For $p \gg n^{-1}$: $P(X>0) \to 1$. This proves a sharp threshold: at $p = cn^{-1}$, a triangle appears with probability $\to 1-e^{-c^3/6}$.
Итоги
- First moment method: $\mathbb{E}[X] < 1$ at suitable parameters proves the existence of the desired object.
- The second moment method gives lower bounds on probability.
- LLL handles dependent events under weak dependence.
- All three methods found algorithmic applications through derandomization.
Connections to other topics
Discrete probability (dm-17) is the source of ideas for the probabilistic method. Concentration of measure (prob-22) strengthens it by giving deviation estimates. In cryptography, the probabilistic method justifies the existence of hash functions with small collision probability.
- Dm 17 — related
- Prob 22 — related
Вопросы для размышления
- LLL states $P(\bigcap \bar A_i) > 0$ when $ep(d+1) \leq 1$. Build an example with $d = 100$ bad events and verify the LLL condition. How does the LLL condition degrade to the naive union bound when $d = 0$ (independent events)?