1 Probability and Computing 1.5 Balls, Bins, and Random Graphs 1.7 Markov Chains and Random Walks

1.6 The Probabilistic Method

1.6.1 A few things I should have noted about factorial

We bounded around factorial in corollary 1.5.5. We can derive a tighter lower bound from following lemmas.

Lemma 1.6.1.

For any integer $k\geq 1$ , by concavity of $\ln x$ ,

\ln k\geq\int^{k+\frac{1}{2}}_{k-\frac{1}{2}}\ln xdx.

Lemma 1.6.2.

n!\geq\sqrt{2n}\left(\frac{n}{e}\right)^{n}.

Proof.

Since $\ln n!=\sum_{i\in[1,n]}\ln i$ , and we have the following from lemma 1.6.1

	$\displaystyle\sum_{i\in[1,n]}\ln i$	$\displaystyle\geq\int^{n+\frac{1}{2}}_{\frac{1}{2}}\ln xdx=\left(x\ln x-x% \right)\bigg{\|}^{n+\frac{1}{2}}_{\frac{1}{2}}$
		$\displaystyle=\left(\left(n+\frac{1}{2}\right)\ln\left(n+\frac{1}{2}\right)-% \left(n+\frac{1}{2}\right)\right)-\left(\frac{1}{2}\ln\frac{1}{2}-\frac{1}{2}\right)$
		$\displaystyle\geq\left(n+\frac{1}{2}\right)\ln n-n+\frac{1}{2}\ln 2=n\ln n-n+% \frac{1}{2}\left(\ln\left(2n\right)\right),$

which completes the proof by exponenting over $e$ on both sides. ∎

Corollary 1.6.3.

By lemma 1.5.4 and lemma 1.6.2, we have

\sqrt{2n}\cdot\left(\frac{n}{e}\right)^{n}\leq n!\leq e\sqrt{n}\cdot\left(% \frac{n}{e}\right)^{n}\text{ and }\frac{1}{e\sqrt{n}}\cdot\left(\frac{e}{n}% \right)^{n}\leq\frac{1}{n!}\leq\frac{1}{\sqrt{2n}}\cdot\left(\frac{e}{n}\right% )^{n}.

Lemma 1.6.4.

By corollary 1.6.3, we have

\binom{2n}{n}=\Theta\left(\frac{1}{\sqrt{n}}\cdot 2^{2n}\right).

Proof.

Since $\binom{2n}{n}=(2n)!/(n!)^{2}$ , then we have

	$\displaystyle\binom{2n}{n}$	$\displaystyle\leq e\sqrt{2n}\cdot\left(\frac{2n}{e}\right)^{2n}\cdot\left(% \frac{1}{\sqrt{2n}}\cdot\left(\frac{e}{n}\right)^{n}\right)^{2}=\frac{e}{\sqrt% {2n}}\cdot 2^{2n}$
	$\displaystyle\binom{2n}{n}$	$\displaystyle\geq 2\sqrt{n}\cdot\left(\frac{2n}{e}\right)^{2n}\cdot\left(\frac% {1}{e\sqrt{n}}\cdot\left(\frac{e}{n}\right)^{n}\right)^{2}=\frac{2}{e^{2}\sqrt% {n}}\cdot 2^{2n},$

which completes the proof. ∎

Lemma 1.6.5.

For $s=O(\sqrt{n})$ , $(n-s)!\cdot(n+s)!=\Theta(1)\cdot(n!)^{2}$ .

Proof.

\frac{(n-s)!}{n!}\cdot\frac{(n+s)!}{n!}=\prod_{i\in[1,s]}\frac{n-s+i}{n+i}=% \prod_{i\in[1,s]}\left(1-\frac{s}{n+i}\right)=\Theta\left(\exp\left(-\frac{s^{% 2}}{n}\right)\right)=\exp(-\Theta(1)).

∎

Corollary 1.6.6.

Immediate from lemma 1.6.5, for $s=O(\sqrt{n})$ ,

\binom{2n}{n+s}=\Theta(1)\cdot\binom{2n}{n}.

Corollary 1.6.7.

Immediate from lemma 1.6.5, for $s=O(\sqrt{n})$ ,

\binom{2n+s}{n}\binom{2n-s}{n}=\Theta(1)\cdot\binom{2n}{n}^{2}.

Exercise 1.6.8 (Exercise 6.16.b [MU17]).

Let $\{Y_{i}\}_{i\in[1,2n]}$ be independent random variables uniform over $\{0,1\}$ . Show that there exists a positive constant $c$ such that, for sufficiently large $n$ ,

\Pr\left[\left|\sum_{i\in[1,n]}Y_{i}-\sum_{i\in[n+1,2n]}Y_{i}\right|>c\sqrt{n}% \right]>\frac{1}{2}.

Proof.

Let $Y=\sum_{i}Y_{i}$ , $A=\sum_{i\in[1,n]}Y_{i}$ , and $B=\sum_{i\in[n+1,2n]}Y_{i}$ . Let $E_{t}$ be the event $\left|A-B\right|>c\sqrt{n}$ when $Y=t$ .

Let $k$ be a positive constant. By conditional probability (similar to lemma 1.5.38),

\Pr\left[\left|A-B\right|>c\sqrt{n}\right]\geq\Pr\left[\left|A-B\right|>c\sqrt% {n}\mid\left|Y-n\right|\leq k\sqrt{n}\right]-\Pr\left[\left|Y-n\right|>k\sqrt{% n}\right],

where $\Pr\left[\left|Y-n\right|>k\sqrt{n}\right]<2\exp\left(-k^{2}/3\right)$ by Chernoff bound.

We continue by conditional probability, that

	$\displaystyle\Pr\left[\left\|A-B\right\|>c\sqrt{n}\mid\left\|Y-n\right\|\leq k% \sqrt{n}\right]$	$\displaystyle=\sum_{t}\Pr\left[E_{t}\mid Y=t\right]\cdot\Pr\left[Y=t\mid\left\|% Y-n\right\|\leq k\sqrt{n}\right]$
		$\displaystyle=1-\sum_{t}\Pr\left[\neg E_{t}\mid Y=t\right]\cdot\Pr\left[Y=t% \mid\left\|Y-n\right\|\leq k\sqrt{n}\right].$

Event $\neg E_{t}$ is equivalent to $A\in\left[(t-c\sqrt{n})/2,(t+c\sqrt{n})/2\right]=R_{t}$ when $Y=t$ . Therefore,

	$\displaystyle\Pr\left[\neg E_{t}\mid Y=t\right]$	$\displaystyle=\sum_{a\in R_{t}}\Pr\left[A=a\mid Y=t\right]$
		$\displaystyle\leq(c\sqrt{n}+1)\cdot\max_{a}\Pr\left[A=a\mid Y=t\right]$
		$\displaystyle=(c\sqrt{n}+1)\cdot\max_{a}\binom{n}{a}\binom{n}{t-a}\binom{2n}{t% }^{-1}=(c\sqrt{n}+1)\cdot p(a).$

By $p(a+1)/p(a)$ ,

\frac{p(a+1)}{p(a)}=\frac{(a+1)(n-t+a+1)}{(n-a)(t-a)},

$p(a)$ peaks at $a=\left\lfloor\frac{t}{2}\right\rfloor$ giving $\binom{n}{\left\lfloor\frac{t}{2}\right\rfloor}^{2}\binom{2n}{t}^{-1}$ . On the other hand, by lemma 1.6.4, the following is immediate

p\left(\frac{n}{2}\right)=\binom{n}{\frac{n}{2}}^{2}\binom{2n}{n}^{-1}=\Theta% \left(\frac{1}{\sqrt{n}}\right).

By corollary 1.6.6, for $t\in[n-k\sqrt{n},n+k\sqrt{n}]$ , we have $p(a)=\Theta\left(\frac{1}{\sqrt{n}}\right)$ .

Choose $c$ sufficiently small such that $\Pr\left[\neg E_{t}\mid Y=t\right]\leq 1/2$ for all $t\in[n-k\sqrt{n},n+k\sqrt{n}]$ , then

\sum_{t}\Pr\left[\neg E_{t}\mid Y=t\right]\cdot\Pr\left[Y=t\mid\left|Y-n\right% |\leq k\sqrt{n}\right]\leq\frac{1}{2},

which completes the proof. ∎

Exercise 1.6.9 (Exercise 6.16.c [MU17]).

Let $\{Y_{i}\}_{i\in[1,2n]}$ be independent random variables uniform over $\{0,1\}$ , and let $\{b_{i}\}_{i\in[1,2n]}$ each be either $+1$ or $-1$ . Show that there exists a positive constant $c$ such that, for sufficiently large $n$ ,

\Pr\left[\left|\sum_{i\in[1,2n]}b_{i}Y_{i}\right|>c\sqrt{n}\right]>\frac{1}{2}.

Proof.

We claim that either the $\{b_{i}\}$ are inbalanced, that $\left|B\right|=\left|\sum_{i}b_{i}\right|>\ell\sqrt{n}$ ; or they are balanced. WLOG let $B>0$ .

For the inbalanced case, let $Z=\sum_{i}b_{i}Y_{i}$ . By linearity of expectation, $\operatorname*{\mathbb{E}}\left[Z\right]=B/2$ . Since $\{Y_{i}\}$ are independent, by Hoeffding’s bound

\Pr\left[Z\leq\operatorname*{\mathbb{E}}\left[Z\right]-\sqrt{2n}\right]\leq% \exp\left(-\frac{2(\sqrt{2n})^{2}}{\sum_{i}b_{i}^{2}}\right)=\exp(-2),

as $\sum_{i}b_{i}^{2}=2n$ . Since $\Pr\left[Z\leq\operatorname*{\mathbb{E}}\left[Z\right]-\sqrt{2n}\right]\leq e^% {-2}$ , then for $\ell\geq 2\left(c+\sqrt{2}\right)$ ,

\Pr\left[Z\geq c\sqrt{n}\right]\geq\Pr\left[Z\geq\operatorname*{\mathbb{E}}% \left[Z\right]-\sqrt{2n}\right]>1-e^{-2}>1/2

the inbalanced base is proved.

Now for the balanced case, we reuse the structure and notion in 1.6.8 (the same window argument) that

	$\displaystyle\Pr\left[\neg E_{t}\mid Y=t\right]$	$\displaystyle\leq(c\sqrt{n}+1)\cdot\max_{a}\Pr\left[A=a\mid Y=t\right]$
		$\displaystyle=(c\sqrt{n}+1)\cdot\max_{a}\binom{n+B/2}{a}\binom{n-B/2}{t-a}% \binom{2n}{t}^{-1}=(c\sqrt{n}+1)\cdot p(a).$

By $p(a+1)/p(a)$ ,

\frac{p(a+1)}{p(a)}=\frac{(n+B/2-a)(t-a)}{(a+1)(n-B/2-t+a+1)},

where $p(a)$ peaks at $\left\lfloor t\cdot\frac{2n+B}{4n}\right\rfloor$ .

On the other hand, by corollary 1.6.6 and corollary 1.6.7, the max of $p(a)$ is still $\Theta\left(\frac{1}{\sqrt{n}}\right)$ , completing the proof. ∎

1.6.2 Basic Counting Argument

Exercise 1.6.10 (Exercise 6.10 [MU17]).

A family of subsets $\mathcal{F}$ of $[1,n]$ is called an antichain if there is no pair of sets $A$ and $B$ in $\mathcal{F}$ satisfying $A\subset B$ .

•

Let $f_{k}$ be the number of sets in $\mathcal{F}$ with size $k$ . Show that

$\sum_{k\in\left[0,n\right]}f_{k}\cdot\binom{n}{k}^{-1}\leq 1.$
•

Argue that $\left|\mathcal{F}\right|\leq\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}$ for any antichain $\mathcal{F}$ .

Proof.

We start choosing a random permutation of $[1,n]$ . Let $X_{k}=1$ if the first $k$ numbers in the permutation yield a set in $\mathcal{F}$ , and let $X=\sum_{i\in[1,n]}X_{i}$ . Then $X$ is at most 1 by antichain property, as no larger subset containing all prior elements, and $X$ can be 0 as no element in $\mathcal{F}$ exists on the random enumeration starting from 0.

Therefore, for a $\mathcal{F}$ , when we are iterating over all permutations, if a $k$ sized subset is in $\mathcal{F}$ , we will encounter $k!(n-k)!$ permutations containing such subset, and we derive

\sum_{k\in[0,n]}f_{k}\cdot k!(n-k)!\leq n!,

as a permutation can have at most 1 element in $\mathcal{F}$ , and the first result is immediate.

Since $\binom{n}{k}\leq\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}$ for all $k\in[0,n]$ , then

\left|\mathcal{F}\right|=\sum_{k\in[0,n]}f_{k}\leq\sum_{k\in[0,n]}\binom{n}{% \left\lfloor\frac{n}{2}\right\rfloor}\cdot f_{k}\cdot\binom{n}{k}^{-1}\leq% \binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}.

∎

Remark 1.6.11.

This is a result from [Spe28] with a Lubell [Lub66] flavored proof.

Another way of seeing it is, a $k$ sized subset in $\mathcal{F}$ appears in a random permutation over $[1,n]$ with probability $k!(n-k)!/n!=\binom{n}{k}^{-1}$ . By linearity of expectation,

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{k\in[0,n]}\operatorname*{% \mathbb{E}}\left[X_{k}\right]=\sum_{k\in[0,n]}\frac{f_{k}}{\binom{n}{k}}.

On the other hand, $X$ is a 0-1 random variable, hence $\operatorname*{\mathbb{E}}\left[X\right]\leq 1$ , which completes the proof.

1.6.3 The Expectation Argument and Derandomization by Conditional Expectation

Lemma 1.6.12 (The Expectation Argument).

For random variable $X$ with $\operatorname*{\mathbb{E}}\left[X\right]=\mu$ , $\Pr\left[X\geq\mu\right]>0$ and $\Pr\left[X\leq\mu\right]>0$ .

Lemma 1.6.13.

Let $\{X_{i}\}_{i\in[1,n]}$ be 0-1 random variables, $X=\sum_{i}X_{i}$ with $\operatorname*{\mathbb{E}}\left[X\right]=m\cdot 2^{-k}$ for some integer $m\geq 1$ and $k\geq 0$ . Then for all $X<\operatorname*{\mathbb{E}}\left[X\right]$ , $X\leq\operatorname*{\mathbb{E}}\left[X\right]-2^{-k}$ ; for all $X>\operatorname*{\mathbb{E}}\left[X\right]$ , $X\geq\operatorname*{\mathbb{E}}\left[X\right]+2^{-k}$ .

Lemma 1.6.14.

Let $\{X_{i}\}_{i\in[1,n]}$ be 0-1 random variables, $X=\sum_{i}X_{i}$ with $\operatorname*{\mathbb{E}}\left[X\right]=m\cdot 2^{-k}$ for some integer $m\geq 1$ and $k\geq 0$ . Then

	$\displaystyle\Pr\left[X\geq\operatorname*{\mathbb{E}}\left[X\right]\right]$	$\displaystyle\geq\frac{1}{2^{k}(n-\operatorname*{\mathbb{E}}\left[X\right])+1},$
	$\displaystyle\Pr\left[X\leq\operatorname*{\mathbb{E}}\left[X\right]\right]$	$\displaystyle\geq\frac{1}{2^{k}\operatorname*{\mathbb{E}}\left[X\right]+1}.$

Proof.

Let $p=\Pr\left[X\geq\operatorname*{\mathbb{E}}\left[X\right]\right]$ . By conditional expectation and lemma 1.6.13,

	$\displaystyle\operatorname*{\mathbb{E}}\left[X\right]$	$\displaystyle=\sum_{i<\operatorname{\mathbb{E}}\left[X\right]}i\Pr\left[X=i% \right]+\sum_{i\geq\operatorname{\mathbb{E}}\left[X\right]}i\Pr\left[X=i\right]$
		$\displaystyle\leq(\operatorname*{\mathbb{E}}\left[X\right]-2^{-k})(1-p)+np,$

yielding $p\geq 1/(2^{k}(n-\operatorname*{\mathbb{E}}\left[X\right])+1)$ .

Let $p=\Pr\left[X\leq\operatorname*{\mathbb{E}}\left[X\right]\right]$ . By conditional expectation and lemma 1.6.13,

	$\displaystyle\operatorname*{\mathbb{E}}\left[X\right]$	$\displaystyle=\sum_{i\leq\operatorname{\mathbb{E}}\left[X\right]}i\Pr\left[X=% i\right]+\sum_{i>\operatorname{\mathbb{E}}\left[X\right]}i\Pr\left[X=i\right]$
		$\displaystyle\geq(\operatorname*{\mathbb{E}}\left[X\right]+2^{-k})(1-p),$

yielding $p\geq 1/(2^{k}\operatorname*{\mathbb{E}}\left[X\right]+1)$ . ∎

Exercise 1.6.15 (Exercise 6.1 [MU17]).

Consider an SAT instance with $m$ clauses and each clause has exactly $k$ literals. Give a Las Vegas algorithm that finds an assignment satisfying at least $m(1-2^{-k})$ clauses, and its expected runtime. Give a derandomization of the randomized algorithm using the method of conditional expectation.

Proof.

For a $k$ -literal SAT clause, it is satisfied with probability $1-2^{-k}$ . Let $X_{i}$ be the 0-1 random variable indicating if the $i^{\mathrm{th}}$ clause is satisfied, and $X=\sum_{i}X_{i}$ be the random number of satisfied clauses. By linearity of expectation, $\operatorname*{\mathbb{E}}\left[X\right]=m(1-2^{-k})$ .

The Las Vegas algorithm searching for assignment satisfying at least $m(1-2^{-k})$ clauses works by keep sampling assignments in $O(km)$ time, and checks if the assignment satisfies sufficient number of clauses in $O(km)$ time.

By lemma 1.6.14, $\Pr\left[X\geq\operatorname*{\mathbb{E}}\left[X\right]\right]\geq(2^{k}(m-% \operatorname*{\mathbb{E}}\left[X\right])+1)^{-1}$ .

The expected number of sampling is at most $2^{k}(m-\operatorname*{\mathbb{E}}\left[X\right])+1$ , and the expected runtime is $O(km2^{k}(m-\operatorname*{\mathbb{E}}\left[X\right]))$ .

Let there be $n=O(km)$ variables for the SAT instance, $\sigma$ be a random permutation of $x_{i}$ , and $x_{i}$ be the choice of the $i^{\mathrm{th}}$ variable. The derandomized algorithm from conditional expectation wants to prove

\operatorname*{\mathbb{E}}\left[X\right]\leq\operatorname*{\mathbb{E}}\left[X% \mid x_{1},\ldots,x_{n}\right],

the right hand side is the number of satisfied clauses after all $x_{i}$ are decided. We prove by induction as follows.

The base case $\operatorname*{\mathbb{E}}\left[X\right]=\operatorname*{\mathbb{E}}\left[X\mid x% _{1}\right]$ is immediate by symmetry.

The intermediate step $\operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{i}\right]\leq% \operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{i+1}\right]$ can be shown by conditional expectation, as

\operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{i}\right]=\frac{1}{2}% \sum_{x_{i+1}\in\{0,1\}}\operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{% i+1}\right]\leq\max_{x_{i+1}\in\{0,1\}}\operatorname*{\mathbb{E}}\left[X\mid x% _{1},\ldots,x_{i+1}\right].

We can greedily choose the next $x_{i+1}$ that satisfies more clauses.

The $n$ step greedy algorithm suffices to find an assignment satisfying at least $m(1-2^{-k})$ clauses by our analysis. ∎

Exercise 1.6.16 (Exercise 6.2 [MU17]).

Prove that for every integer $n$ , there exists a 2-coloring of the edges of $K_{n}$ so that the total number of monochromatic $K_{4}$ is at most $\binom{n}{4}2^{-5}$ , and show the following

•

A randomized algorithm to find a coloring with at most $\binom{n}{4}2^{-5}$ monochromatic $K_{4}$ in expected poly time in $n$ .
•

A deterministic polynomial time algorithm to find such a coloring by derandomization.

Proof.

There are $\binom{n}{4}$ copies of $K_{4}$ in a $K_{n}$ , and a $K_{4}$ is 2-colored monochromatic with probability $2^{-5}$ .

Let $X_{i}$ be the 0-1 random variable indicating the $i^{\mathrm{th}}$ $K_{4}$ being monochromatic, and $X=\sum_{i}X_{i}$ be the number of monochromatic $K_{4}$ in $K_{n}$ . By linearity of expectation, $\operatorname*{\mathbb{E}}\left[X\right]=\binom{n}{4}2^{-5}$ . Hence, the existence of 2-coloring with at most $\binom{n}{4}2^{-5}$ monochromatic $K_{4}$ is immediate by the expectation argument.

We can keep randomly sampling 2-coloring $K_{n}$ until we see at most $\operatorname*{\mathbb{E}}\left[X\right]$ copies of monochromatic $K_{4}$ .

By lemma 1.6.14, $\Pr\left[X\leq\operatorname*{\mathbb{E}}\left[X\right]\right]\geq(2^{5}% \operatorname*{\mathbb{E}}\left[X\right]+1)^{-1}$ .

The expected sampling time is at most $2^{5}\operatorname*{\mathbb{E}}\left[X\right]+1$ , and expected runtime is $O\left(\binom{n}{4}^{2}\right)=O(n^{8})$ .

Let $x_{i}$ be the $i^{\mathrm{th}}$ edge’s color choice among all $N=\binom{n}{2}$ edges. The derandomized algorithm wants to show

\operatorname*{\mathbb{E}}\left[X\right]\geq\operatorname*{\mathbb{E}}\left[X% \mid x_{1},\ldots,x_{N}\right],

right hand side is the number of monochromatic $K_{4}$ after fixing all vertices’ colors. We prove by induction as follows.

The base case $\operatorname*{\mathbb{E}}\left[X\right]=\operatorname*{\mathbb{E}}\left[X\mid x% _{1}\right]$ is immediate by symmetry.

The intermediate step $\operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{i}\right]\geq% \operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{i+1}\right]$ can be shown by conditional expectation, as

\operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{i}\right]=\frac{1}{2}% \sum_{x_{i+1}\in\{0,1\}}\operatorname*{\mathbb{E}}\left[X\mid x_{1},\ldots,x_{% i+1}\right]\geq\min_{x_{i+1}\in\{0,1\}}\operatorname*{\mathbb{E}}\left[X\mid x% _{1},\ldots,x_{i+1}\right].

We can greedily choose the next $x_{i+1}$ that bring less monochromatic $K_{4}$ .

The $N$ step greedy algorithm suffices to 2-color $K_{n}$ with at most $\binom{n}{4}2^{-5}$ monochromatic $K_{4}$ by our analysis. ∎

Remark 1.6.17.

This appears in The Probabilistic Method [AS16], and uses the “pessimistic estimator” idea [Rag88].

Exercise 1.6.18 (Exercise 6.3 [MU17]).

Given a $n$ -vertex undirected graph, consider the following method of generating an independent set. Given a permutation $\sigma$ of $V$ , define $S(\sigma)\subset V$ as follows: for each vertex $i$ , $i\in S(\sigma)$ if and only if no neighbor $j$ of $i$ precedes $i$ in the permutation $\sigma$ .

•

Show $\operatorname*{\mathbb{E}}\left[\left|S(\sigma)\right|\right]=\sum_{i}1/(d_{i}% +1)$ , where $\{d_{i}\}_{i\in[1,n]}$ denotes the degree of vertices.
•

Prove that $G$ has an independent set of size at least $\sum_{i}1/(1+d_{i})$ .

Proof.

Given a random $\sigma$ , the resulting $S(\sigma)$ has each vertex with no neighbors, which is an independent set.

Let $\{X_{i}\}_{i\in[1,n]}$ be 0-1 random variables indicating if the $i^{\mathrm{th}}$ vertex is the first among all its neighbors, and $X=\sum_{i}X_{i}$ is the random variable for $\left|S(\sigma)\right|$ . The $i^{\mathrm{th}}$ vertex is the first among all $d_{i}$ neighbors and itself with probability $1/(1+d_{i})$ . Therefore, by linearity of expectation, $\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i}1/(1+d_{i})$ .

The existence of an independent set at least $\sum_{i}1/(1+d_{i})$ large is immediate by the expectation argument. ∎

Exercise 1.6.19 (Exercise 6.5 [MU17]).

We have shown using the probabilistic method that, if a graph $G$ has $n$ nodes and $m$ edges, then there exists a partition of the $n$ nodes into 2 sets such that at least $m/2$ edges cross the partition. Improve this result slightly: show that there exists a partition such that at least $mn/(2n-1)$ edges cross the partition.

Proof.

The $m/2$ result derive from 2-coloring the vertices each with probability $1/2$ , and same color vertices goes to the same set. In this way, edges with two ends colored differently are included in the cut, with a probability of $1/2$ . Existence of cut with at least $m/2$ edges is immediate by linearity of expectation and the expectation argument.

On the other hand, $n$ vertices can be partitioned into sets with $\left\lfloor\frac{n}{2}\right\rfloor$ and $\left\lceil\frac{n}{2}\right\rceil$ vertices each, and improve by the expectation argument. Let the event of choosing 2 vertices with different colors be $E$ , the probability is

\Pr\left[E\right]=\frac{2\left\lfloor\frac{n}{2}\right\rfloor\left\lceil\frac{% n}{2}\right\rceil}{n(n-1)}.

•

When $n$ even, the probability is $n/(2n-2)>n/(2n-1)$ .
•

When $n$ odd, the probability is $(n+1)/2n>n/(2n-1)$ .

By linearity of expectation, the expected size of the cut is $m\Pr\left[E\right]\geq mn/(2n-1)$ . Hence, the existence of a cut with at least $mn/(2n-1)$ is immediate by the expectation argument. ∎

Exercise 1.6.20 (Exercise 6.6 [MU17]).

A $k$ -cut is a partition of the vertices into $k$ disjoint sets, and the value of a cut is the weight of all edges crossing from one of the $k$ sets to another. Show that any graph $G$ with $m$ edges has a $k$ -cut with value at least $(k-1)m/k$ . Show how to use derandomization to deterministically find such a cut.

Proof.

We assign one out of the $k$ colors to each of the $n$ vertices with probability $1/k$ . The probability of 2 vertices having same color is $1/k$ , and therefore an edge being included into a $k$ -cut has probability $(k-1)/k$ .

By linearity of expectation, the expected $k$ -cut size is $m(k-1)/k$ . Hence, the existence of $k$ -cut with size at least $m(k-1)/k$ is immediate by the expectation argument.

When it comes to the derandomized deterministic algorithm for finding a $k$ -cut that is larger than $m(k-1)/k$ , we let $\{S_{i}\}_{i\in[1,k]}$ be the sets of partitioned vertices, and we write $C(\{S_{i}\}_{i\in[1,k]})$ for size of the $k$ -cut. We pick an arbitrary emulation of all vertices $\{v_{i}\}_{i\in[1,n]}$ , and write $\{x_{i}\}_{i\in[1,n]}$ for each vertex’s color choice. We prove by induction for

\operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\right]\leq% \operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\mid x_{1},\ldots,x_{n% }\right],

where the right hand side is the $k$ -cut size determined by the derandomized algorithm, where the color choices are $\{x_{i}\}_{i\in[1,n]}$ , hence the algorithm gives a cut whose size is at least $\operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\right]=m(k-1)/k$ .

The base case $\operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\right]\leq% \operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\mid x_{1}\right]$ is immediate by symmetry.

The intermediate step

\operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\mid x_{1},\ldots,x_{i% }\right]\leq\operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\mid x_{1}% ,\ldots,x_{i+1}\right]

can be shown by conditional expectation, that

	$\displaystyle\operatorname*{\mathbb{E}}\left[C(\{S_{i}\}_{i\in[1,k]})\mid x_{1% },\ldots,x_{i}\right]$	$\displaystyle=\frac{1}{k}\sum_{x_{i+1}\in[1,k]}\operatorname*{\mathbb{E}}\left% [C(\{S_{i}\}_{i\in[1,k]})\mid x_{1},\ldots,x_{i+1}\right]$
		$\displaystyle\leq\max_{x_{i+1}\in[1,k]}\operatorname*{\mathbb{E}}\left[C(\{S_{% i}\}_{i\in[1,k]})\mid x_{1},\ldots,x_{i+1}\right].$

In fact, we greedily find the next $x_{i+1}$ without computing all conditional expectations on $x_{i+1}$ ’s choice. We choose the $x_{i+1}$ such that $v_{i+1}$ contribute most edges to the $k$ -cut. Equivalently, we put $v_{i+1}$ to the partition with the fewest $v_{i+1}$ ’s colored neighbors, such that $v_{i+1}$ introduces most $k$ -cut edges with colored neighbors.

This $n$ steps greedy searching algorithm suffices to determine a $k$ -cut at least $m(k-1)/k$ large by our analysis. ∎

Exercise 1.6.21 (Exercise 6.9 [MU17]).

A tournament is a graph on $n$ vertices with exactly one directed edge between each pair of vertices. If vertices represent players, then each edge can be thought of as the result of a match between the two players: the edge points to the winner. A ranking is an ordering of the $n$ players from best to worst (ties are not allowed). Given the outcome of a tournament, one might wish to determine a ranking of the players. A ranking is said to disagree with a directed edge from $y$ to $x$ if $y$ is ahead of $x$ in the ranking.

•

Prove that, for every tournament, there exists a ranking that disagrees with at most $50\%$ of the edges.
•

Prove that, for sufficiently large $n$ , there exists a tournament such that every ranking disagrees with at least $49\%$ of the edges in the tournament.

Proof.

Fix a tournament, and let $X_{i}$ be the 0-1 random variable indicating if a random ranking disagrees with the $i^{\mathrm{th}}$ of all $\binom{n}{2}$ edges of the tournament, then $X=\sum_{i}X_{i}$ is the total number of disagreement.

For any unordered pair $(x,y)$ , each ordering is equally likely in a random ranking. Therefore, $\Pr\left[X_{i}=1\right]=1/2$ . By linearity of expectation,

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i}\operatorname*{\mathbb{E}}% \left[X_{i}\right]=\frac{1}{2}\binom{n}{2}.

By the expectation argument, there exists a ranking disagreeing at most $50\%$ of the edges, proving the first part.

Fix a ranking. Let $Y=\sum_{j}Y_{j}$ be the random variable for the number of disagreement with a random tournament, and $Y_{j}$ be the 0-1 random variable indicating if the ranking disagrees with the $j^{\mathrm{th}}$ edge of the random tournament.

Let the fixed ranking be the $k^{\mathrm{th}}$ among all $n!$ ranking, and let $E_{k}$ be the event that the fixed $k^{\mathrm{th}}$ ranking has at most $49\%$ of disagreement against a random tournament, namely $Y\leq(1-\delta)\operatorname*{\mathbb{E}}\left[Y\right]$ , where $\delta=1/50$ . Since $\{Y_{j}\}$ are independent, we can use concentration inequality like Chernoff bound to upper bound the lower tail of $Y$ as follows

\Pr\left[Y\leq(1-\delta)\operatorname*{\mathbb{E}}\left[Y\right]\right]\leq% \exp\left(-\delta^{2}\mu/2\right)=\exp\left(-\frac{1}{50^{2}}\cdot\frac{1}{2}% \binom{n}{2}\cdot\frac{1}{2}\right).

Union bounding over all rankings yields

\Pr\left[\bigcup_{k\in[1,n!]}E_{k}\right]\leq\sum_{k\in[1,n!]}\Pr\left[E_{k}% \right]=n!\cdot\exp\left(-\frac{1}{100^{2}}\binom{n}{2}\right)\leq n^{n}\cdot% \exp\left(-\frac{1}{100^{2}}\binom{n}{2}\right)=\exp\left(n\ln n-\frac{1}{100^% {2}}\binom{n}{2}\right),

and the bound is less than 1 if $n$ is sufficiently large. Thus, for a tournament, the probability of existing a ranking permutation with at most $49\%$ disagreement is strictly less than 1. Hence,

\Pr\left[\bigcap_{k\in[1,n!]}\neg E_{k}\right]=1-\Pr\left[\bigcup_{k\in[1,n!]}% E_{k}\right]>0.

∎

1.6.4 Sample and Modify

Exercise 1.6.22 (Exercise 6.7 [MU17]).

A Hypergraph $H=(V,E)$ , where $V$ is the set of vertices and $E$ is the set of hyperedges, and every hyperedge in $E$ is a subset of $V$ . In particular, $r$ -uniform hypergraph is one where the size of each hyperedge is $r$ . A standard graph is a 2-uniform hypergraph. A dominanting set in a hypergraph $H$ is a set of vertices $S\subset V$ such that $e\cap S\neq\varnothing$ for every $e\in E$ , namely $S$ hits every hyperedge in $H$ .

Let $\left|V\right|=n$ and $\left|E\right|=m$ , show that there is a dominanting set $S$ with size at most $np+(1-p)^{r}m$ for $0\leq p\leq 1$ .

Proof.

Given a hypergraph $H=(V,E)$ with $\left|V\right|=n$ and $\left|E\right|=m$ , we first sample across $V$ with each vertices to be chosen with probability $p$ , then check if any hyperedges are not covered, choose a vertex from each of the hyperedge. The sampling stage has expected chosen vertices $n p$ , leaving expected unchosen hyperedges $m(1-p)^{r}$ to be fixed. ∎

Exercise 1.6.23 (Exercise 6.8 [MU17]).

Prove that, for every integer $n$ , there is a way to 2-color the edges of $K_{x}$ such that there is no monochromatic cliques of size $k$ when

x=n-\binom{n}{k}2^{1-\binom{k}{2}}.

Proof.

We start 2-coloring $K_{n}$ , keep removing vertices and attached edges until there is no monochromatic $K_{k}$ .

Let each edge in $K_{n}$ be 2-colored with probability $1/2$ , and let $X_{i}$ be the 0-1 random variable indicating the $i^{\mathrm{th}}$ $K_{k}$ being monochromatic. There are $\binom{n}{k}$ $K_{k}$ ’s in a $K_{n}$ , hence $X=\sum_{i}X_{i}$ is the number of monochromatic $K_{k}$ ’s in the $K_{n}$ .

For a $K_{k}$ , the probability of being monochromatic is $2^{1-\binom{k}{2}}$ as it can be one of 2 colors. By linearity of expectation,

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i}\operatorname*{\mathbb{E}}% \left[X_{i}\right]=\binom{n}{k}2^{1-\binom{k}{2}}.

By expectation argument, there exists a 2-coloring such that $X\leq\operatorname*{\mathbb{E}}\left[X\right]$ .

To modify up to no monochromatic $K_{k}$ , we can remove a vertex and the attached edges in each $K_{k}$ , therefore we need to remove at most $X$ vertices from $K_{n}$ . Since there exists a 2-coloring for $K_{n}$ containing at most $\operatorname*{\mathbb{E}}\left[X\right]$ $K_{k}$ ’s, then there exists a 2-coloring with no monochromatic $K_{k}$ for $K_{m}$ that $m\geq n-\operatorname*{\mathbb{E}}\left[X\right]$ .

“no monochromatic $K_{k}$ ” is a monotonely decreasing graph property, therefore any subgraph of such 2-colored $K_{m}$ has this property. Therefore, a $K_{x}$ in this $K_{m}$ has no monochromatic $K_{k}$ , which completes the proof. ∎

1.6.5 The Second Moment Method and the Conditional Expectation Inequality

Theorem 1.6.24 (The Second Moment Method (Chebyshev’s version)).

Let $X$ be a random variable, then

\Pr\left[X=0\right]\leq\frac{\mathrm{Var}\left[X\right]}{\operatorname*{% \mathbb{E}}\left[X\right]^{2}}.

Proof.

Since

\Pr\left[X=0\right]\leq\Pr\left[\left|X-\operatorname*{\mathbb{E}}\left[X% \right]\right|\geq\operatorname*{\mathbb{E}}\left[X\right]\right]\leq\frac{% \mathrm{Var}\left[X\right]}{\operatorname*{\mathbb{E}}\left[X\right]^{2}},

which is immediate by Chebyshev’s inequality. ∎

Lemma 1.6.25.

For integer valued non-negative random variable $X$ , $\Pr\left[X>0\right]\leq\operatorname*{\mathbb{E}}\left[X\right]$ by Markov’s inequality.

Theorem 1.6.26 (Cauchy-Schwarz).

For random variables $X$ and $Y$ (that may not be independent),

\operatorname*{\mathbb{E}}\left[XY\right]^{2}\leq\operatorname*{\mathbb{E}}% \left[X^{2}\right]\cdot\operatorname*{\mathbb{E}}\left[Y^{2}\right].

Proof.

Let $Z=X-t\cdot Y$ , then the second moment of $Z$ is

\operatorname*{\mathbb{E}}\left[Z^{2}\right]=\operatorname*{\mathbb{E}}\left[X% ^{2}\right]+t^{2}\cdot\operatorname*{\mathbb{E}}\left[Y^{2}\right]-2t\cdot% \operatorname*{\mathbb{E}}\left[XY\right]\geq 0,

which holds for any $t$ . Minimizing over $t$ , and we have $\operatorname*{\mathbb{E}}\left[X^{2}\right]\cdot\operatorname*{\mathbb{E}}% \left[Y^{2}\right]\geq\operatorname*{\mathbb{E}}\left[XY\right]^{2}$ . ∎

Corollary 1.6.27.

For random variable $X$ with $\operatorname*{\mathbb{E}}\left[X\right]\geq 0$ , $0\leq t\leq\operatorname*{\mathbb{E}}\left[X\right]$ , and $1_{t}=1$ if and only if $X\geq t$ , by theorem 1.6.26

\Pr\left[X\geq t\right]\geq\frac{\operatorname*{\mathbb{E}}\left[X\cdot 1_{t}% \right]^{2}}{\operatorname*{\mathbb{E}}\left[X^{2}\right]}.

Theorem 1.6.28 (The Second Moment Method (Cauchy-Schwarz’s version)).

For random variable $X\geq 0$ ,

\operatorname*{\mathbb{E}}\left[X\right]\geq\Pr\left[X>0\right]\geq\frac{% \operatorname*{\mathbb{E}}\left[X\right]^{2}}{\operatorname*{\mathbb{E}}\left[% X^{2}\right]}.

Proof.

Let $1_{+}=1$ if and only if $X>0$ , then by theorem 1.6.26 and corollary 1.6.27,

\operatorname*{\mathbb{E}}\left[X^{2}\right]\operatorname*{\mathbb{E}}\left[1_% {+}^{2}\right]\geq\operatorname*{\mathbb{E}}\left[X^{2}\right]\Pr\left[X>0% \right]\geq\operatorname*{\mathbb{E}}\left[X\cdot 1_{+}\right]^{2}\geq% \operatorname*{\mathbb{E}}\left[X\right]^{2},

and the last inequality holds by non-negativity of $X$ . ∎

Remark 1.6.29.

A weaker version of theorem 1.6.28 is in 1.3.10. We can relax non-negative $X$ to $\operatorname*{\mathbb{E}}\left[X\right]\geq 0$ .

Theorem 1.6.30 (Paley-Zygmund).

For random variable $X\geq 0$ with finite $\operatorname*{\mathbb{E}}\left[X^{2}\right]$ , and $0\leq\alpha<1$ . Then

\Pr\left[X\geq\alpha\operatorname*{\mathbb{E}}\left[X\right]\right]\geq(1-% \alpha)^{2}\cdot\frac{\operatorname*{\mathbb{E}}\left[X\right]^{2}}{% \operatorname*{\mathbb{E}}\left[X^{2}\right]}.

Proof.

Let $1_{\alpha}=1$ if and only if $X\geq\alpha\operatorname*{\mathbb{E}}\left[X\right]$ , and $1_{\overline{\alpha}}=1$ if and only if $X<\alpha\operatorname*{\mathbb{E}}\left[X\right]$ , then

	$\displaystyle\operatorname*{\mathbb{E}}\left[X\right]$	$\displaystyle=\operatorname{\mathbb{E}}\left[X\cdot 1_{\alpha}\right]+% \operatorname{\mathbb{E}}\left[X\cdot 1_{\overline{\alpha}}\right]$
		$\displaystyle\leq\operatorname{\mathbb{E}}\left[X\cdot 1_{\alpha}\right]+% \alpha\cdot\operatorname{\mathbb{E}}\left[X\right],$

and therefore $\operatorname*{\mathbb{E}}\left[X\cdot 1_{\alpha}\right]\geq(1-\alpha)\cdot% \operatorname*{\mathbb{E}}\left[X\right]$ . By theorem 1.6.26 and corollary 1.6.27, we have

\operatorname*{\mathbb{E}}\left[X\cdot 1_{\alpha}\right]^{2}\leq\operatorname*% {\mathbb{E}}\left[X^{2}\right]\cdot\operatorname*{\mathbb{E}}\left[1_{\alpha}% \right]=\operatorname*{\mathbb{E}}\left[X^{2}\right]\cdot\Pr\left[X\geq\alpha% \operatorname*{\mathbb{E}}\left[X\right]\right].

Hence, the result is immediate by

\Pr\left[X\geq\alpha\operatorname*{\mathbb{E}}\left[X\right]\right]\geq\frac{% \operatorname*{\mathbb{E}}\left[X\cdot 1_{\alpha}\right]^{2}}{\operatorname*{% \mathbb{E}}\left[X^{2}\right]}\geq(1-\alpha)^{2}\cdot\frac{\operatorname*{% \mathbb{E}}\left[X\right]^{2}}{\operatorname*{\mathbb{E}}\left[X^{2}\right]}.

∎

Remark 1.6.31.

The theorem 1.6.30 can be relaxed from non-negative $X$ to $\operatorname*{\mathbb{E}}\left[X\right]\geq 0$ .

Exercise 1.6.32 (Exercise 6.11 [MU17]).

Prove a threshold for the existence of triangles in the $G_{n,p}$ . Let $\{X_{i}\}$ each be the random value for the $i^{\mathrm{th}}$ triangle appearing in the graph among the $\binom{n}{3}$ triplets of vertices, and let $X=\sum_{i}X_{i}$ .

•

Show $\operatorname*{\mathbb{E}}\left[X\right]$ , and show if $pn\to 0$ , then $\Pr\left[X>0\right]\to 0$ .
•

Show $\mathrm{Var}\left[X_{i}\right]\leq p^{3}$ .
•

Show that $\mathrm{Cov}\left[X_{i},X_{j}\right]=p^{5}-p^{6}$ for $O(n^{4})$ pairs of triangle triplets $i\neq j$ , otherwise $0$ .
•

Show $\mathrm{Var}\left[X\right]=O(n^{3}p^{3}+n^{4}(p^{5}-p^{6}))$ .
•

Show if $pn\to\infty$ then $\Pr\left[X=0\right]\to 0$ .

Proof.

By linearity of expectation, $\operatorname*{\mathbb{E}}\left[X\right]=\binom{n}{3}p^{3}=O(n^{3}p^{3})$ . If $pn\to 0$ , then $\operatorname*{\mathbb{E}}\left[X\right]\to 0$ .

For variance, we have $\mathrm{Var}\left[X_{i}\right]=\operatorname*{\mathbb{E}}\left[X_{i}^{2}\right% ]-\operatorname*{\mathbb{E}}\left[X_{i}\right]^{2}=p^{3}-p^{6}\leq p^{3}$ .

For covariance, when the triplets overlap up to 1 vertex, no edges are shared, and $\operatorname*{\mathbb{E}}\left[X_{i}X_{j}\right]=\operatorname*{\mathbb{E}}% \left[X_{i}\right]\operatorname*{\mathbb{E}}\left[X_{j}\right]$ , hence $\mathrm{Cov}\left[X_{i},X_{j}\right]=0$ . Otherwise, when 2 vertices are shared, $\operatorname*{\mathbb{E}}\left[X_{i}X_{j}\right]=p^{5}$ , and there are in total $\binom{n}{2;1;1}$ csaes.

Therefore, the variance for $X$ is derived as

	$\displaystyle\mathrm{Var}\left[X\right]$	$\displaystyle=\sum_{i}\mathrm{Var}\left[X_{i}\right]+\sum_{i\neq j}\mathrm{Cov% }\left[X_{i},X_{j}\right]=\binom{n}{3}\left(p^{3}-p^{6}\right)+\binom{n}{2;1;1% }\left(p^{5}-p^{6}\right)$
		$\displaystyle=O(n^{3}p^{3}+n^{4}(p^{5}-p^{6})).$

When $pn\to\infty$ , by theorem 1.6.24, $\Pr\left[X=0\right]\leq O((pn)^{-1})\to 0$ . ∎

Exercise 1.6.33 (Exercise 6.12 [MU17]).

Use 1.3.1 to derive the variance of the number of $K_{4}$ in $G_{n,p}$ .

Proof.

Let $\{X_{i}\}$ be the 0-1 random variable for the existence of the $i^{\mathrm{th}}$ $K_{4}$ among all possible $\binom{n}{4}$ $K_{4}$ , and let $X=\sum_{i}X_{i}$ . By 1.3.1,

\operatorname*{\mathbb{E}}\left[X^{2}\right]=\sum_{i}\operatorname*{\mathbb{E}% }\left[X\mid X_{i}=1\right]\Pr\left[X_{i}=1\right].

We know $\Pr\left[X_{i}=1\right]=p^{6}$ , and among all $\binom{n}{4}$ possible $K_{4}$ , if $X_{i}=1$ ,

•

If there are no vertex overlap, then $\binom{n-4}{4}$ $K_{4}$ with probability $p^{6}$ .
•

If there is 1 vertex overlapped, then $\binom{n-4}{3}\binom{4}{1}$ $K_{4}$ with probability $p^{6}$ .
•

If there are 2 vertices overlapped, then $\binom{n-4}{2}\binom{4}{2}$ $K_{4}$ with probability $p^{5}$ .
•

If there are 3 vertices overlapped, then $\binom{n-4}{1}\binom{4}{3}$ $K_{4}$ with probability $p^{3}$ .
•

If there are 4 vertices overlapped, then it has to be $i^{\mathrm{th}}$ $K_{4}$ with probability 1.

By summation,

\operatorname*{\mathbb{E}}\left[X\mid X_{i}\right]=\binom{n-4}{4}p^{6}+\binom{% n-4}{3}\binom{4}{1}p^{6}+\binom{n-4}{2}\binom{4}{2}p^{5}+\binom{n-4}{1}\binom{% 4}{3}p^{3}+1,

therefore,

	$\displaystyle\operatorname*{\mathbb{E}}\left[X^{2}\right]$	$\displaystyle=\binom{n}{4}p^{6}\left(\binom{n-4}{4}p^{6}+\binom{n-4}{3}\binom{% 4}{1}p^{6}+\binom{n-4}{2}\binom{4}{2}p^{5}+\binom{n-4}{1}\binom{4}{3}p^{3}+1\right)$
		$\displaystyle=\binom{n}{4;4}p^{12}+\binom{n}{3;3;1}p^{12}+\binom{n}{2;2;2}p^{1% 1}+\binom{n}{3;1;1}p^{9}+\binom{n}{4}p^{6},$

hence

	$\displaystyle\mathrm{Var}\left[X\right]$	$\displaystyle=\left(\binom{n}{4;4}+\binom{n}{3;3;1}-\binom{n}{4}^{2}\right)p^{% 12}+\binom{n}{2;2;2}p^{11}+\binom{n}{3;1;1}p^{9}+\binom{n}{4}p^{6}$
		$\displaystyle=O(n^{7}p^{12})+O(n^{6}p^{11})+O(n^{5}p^{9})+O(n^{4}p^{6}).$

When $p=o(n^{-2/3})$ , by lemma 1.6.25, that $\Pr\left[X\geq 1\right]\leq\operatorname*{\mathbb{E}}\left[X\right]=o(1)$ .

When $p=\omega(n^{-2/3})$ , by theorem 1.6.24 and $\operatorname*{\mathbb{E}}\left[X\right]^{2}=O(n^{8}p^{12})=\omega(1)$ , we have

\Pr\left[X=0\right]\leq\frac{\mathrm{Var}\left[X\right]}{\operatorname*{% \mathbb{E}}\left[X\right]^{2}}=o(1).

∎

Theorem 1.6.34 (Conditional Expectation Inequality).

Let $\{X_{i}\}_{i\in[1,n]}$ be 0-1 random variables, and $X=\sum_{i}X_{i}$ . Then

\Pr\left[X>0\right]\geq\sum_{i\in[1,n]}\frac{\Pr\left[X_{i}=1\right]}{% \operatorname*{\mathbb{E}}\left[X\mid X_{i}=1\right]}.

Proof.

Let $Y=1/X$ when $X\neq 0$ , and 0 otherwise. Then $\operatorname*{\mathbb{E}}\left[XY\right]=\Pr\left[X>0\right]$ , and

	$\displaystyle\operatorname*{\mathbb{E}}\left[XY\right]$	$\displaystyle=\sum_{i\in[1,n]}\operatorname*{\mathbb{E}}\left[Y\mid X_{i}=1% \right]\Pr\left[X_{i}=1\right]$
		$\displaystyle\geq\sum_{i\in[1,n]}\frac{\Pr\left[X_{i}=1\right]}{\operatorname*% {\mathbb{E}}\left[X\mid X_{i}=1\right]},$

where the first equality holds from 1.3.1, and the last inequality holds from theorem 1.2.5. ∎

Remark 1.6.35.

Previous 1.6.33 $p=\omega(n^{-2/3})$ case can be solved with theorem 1.6.34 by

	$\displaystyle\Pr\left[X>0\right]$	$\displaystyle\geq\sum_{i}\frac{\Pr\left[X_{i}=1\right]}{\operatorname*{\mathbb% {E}}\left[X\mid X_{i}=1\right]}$
		$\displaystyle=\frac{\binom{n}{4}p^{6}}{\binom{n-4}{4}p^{6}+\binom{n-4}{3}% \binom{4}{1}p^{6}+\binom{n-4}{2}\binom{4}{2}p^{5}+\binom{n-4}{1}\binom{4}{3}p^% {3}+1}.$

When $p=\omega(n^{-2/3})$ , both $\binom{n}{4}p^{6}$ and $\binom{n-4}{4}p^{6}$ are $\omega(1)$ , while the others are $o(1)$ , proving the second part of the proof.

Exercise 1.6.36 (Exercise 6.13 [MU17]).

Consider the problem of whether graphs in $G_{n,p}$ have $K_{k}$ of constant size $k$ . Suggest a threshold function and generalize the argument for $K_{4}$ using either theorem 1.6.24 or theorem 1.6.34, to prove that your threshold function is correct for $K_{5}$ .

Proof.

We reuse notions in 1.6.33, let $X_{i}$ be the random variable for the existence of the $i^{\mathrm{th}}$ $K_{k}$ in $G_{n,p}$ , and let $X=\sum_{i}X_{i}$ . We guess the threshold $p=n^{-2/(k-1)}$ , which balances both the dominanting numerator and denumerator terms in theorem 1.6.34, and convert $\operatorname*{\mathbb{E}}\left[X\right]=\binom{n}{k}p^{k(k-1)/2}=O(n^{k}p^{k(% k-1)/2})$ into constant for lemma 1.6.25.

When $p=o(n^{-1/2})$ , by linearity of expectation, $\operatorname*{\mathbb{E}}\left[X\right]=\binom{n}{5}p^{10}=o(1)$ . By lemma 1.6.25, $\Pr\left[X>0\right]\leq\operatorname*{\mathbb{E}}\left[X\right]=o(1)$ .

When $p=\omega(n^{-1/2})$ , we apply the theorem 1.6.34. Among all $\binom{n}{5}$ possible $K_{5}$ , conditioned that $X_{i}=1$ ,

•

If there are no vertex overlap, then $\binom{n-5}{5}$ $K_{5}$ with probability $p^{10}$ .
•

If there is 1 vertex overlapped, then $\binom{n-5}{4}\binom{5}{1}$ $K_{5}$ with probability $p^{10}$ .
•

If there are 2 vertices overlapped, then $\binom{n-5}{3}\binom{5}{2}$ $K_{5}$ with probability $p^{9}$ .
•

If there are 3 vertices overlapped, then $\binom{n-5}{2}\binom{5}{3}$ $K_{5}$ with probability $p^{7}$ .
•

If there are 4 vertices overlapped, then $\binom{n-5}{1}\binom{5}{4}$ $K_{5}$ with probability $p^{4}$ .
•

If there are 5 vertices overlapped, then it has to be the $i^{\mathrm{th}}$ $K_{5}$ with probability 1.

By summation,

\operatorname*{\mathbb{E}}\left[X\mid X_{i}=1\right]=\binom{n-5}{5}p^{10}+% \binom{n-5}{4}\binom{5}{1}p^{10}+\binom{n-5}{3}\binom{5}{2}p^{9}+\binom{n-5}{2% }\binom{5}{3}p^{7}+\binom{n-5}{1}\binom{5}{4}p^{4}+1.

Since $\binom{n-5}{5}p^{10}$ and $\binom{n}{5}p^{10}$ are $\omega(1)$ , while all other terms are $o(1)$ , therefore by theorem 1.6.34, $\Pr\left[X>0\right]\to 1$ . ∎

Exercise 1.6.37 (Exercise 6.14 [MU17]).

Consider $G\in G_{n,p}$ with $p=c\ln n/n$ . Use theorem 1.6.24 or theorem 1.6.34 to prove that if $c<1$ then, for any constant $\varepsilon>0$ and for $n$ sufficiently large, the graph has isolated vertices with probability at least $1-\varepsilon$ .

Proof.

Let $X_{i}$ be random variable for the $i^{\mathrm{th}}$ vertex being isolated in the graph, and $X=\sum_{i}X_{i}$ .

By theorem 1.6.34, among $n$ vertices, conditioned that $X_{i}=1$ ,

•

If a vertex is not the $i^{\mathrm{th}}$ vertex, it has probability $(1-p)^{n-2}$ to be isolated.
•

Otherwise, the $i^{\mathrm{th}}$ vertex is isolated with probability 1 by conditioning.

By summing,

\lim_{n\to\infty}\operatorname*{\mathbb{E}}\left[X\mid X_{i}=1\right]=\lim_{n% \to\infty}1+(n-1)(1-p)^{n-2}=1+\frac{n}{n^{c}}.

Since $\Pr\left[X_{i}=1\right]=(1-p)^{n-1}$ , which is $1/n^{c}$ as $n\to\infty$ , therefore by theorem 1.6.34,

\lim_{n\to\infty}\Pr\left[X>0\right]\geq\frac{n/n^{c}}{1+n/n^{c}}=\frac{n}{n^{% c}+n},

which approaches $1$ if $c<1$ . ∎

Exercise 1.6.38 (Exercise 6.15 [MU17]).

Consider a graph in $G_{n,p}$ where $p=1/n$ . Let $X$ be the number of triangles in the graph. Show that

\Pr\left[X\geq 1\right]\leq\frac{1}{6},

and that

\lim_{n\to\infty}\Pr\left[X\geq 1\right]\geq\frac{1}{7}.

Proof.

There are $\binom{n}{3}$ triangles in $K_{n}$ , while a triangle exists with probability $p^{3}$ . Let $\{X_{i}\}$ be the set of 0-1 random variables indicating if the $i^{\mathrm{th}}$ triangle exists in the graph, then $X=\sum_{i}X_{i}$ . By linearity of expectation,

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i}\operatorname*{\mathbb{E}}% \left[X_{i}\right]=\binom{n}{3}p^{3}=\frac{(n-1)(n-2)}{6n^{2}}\leq\frac{1}{6}.

On the other hand, by lemma 1.6.25

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{x\in\left[0,\binom{n}{3}\right]% }x\Pr\left[X=x\right]\geq\sum_{x\in\left[1,\binom{n}{3}\right]}\Pr\left[X=x% \right]=\Pr\left[X\geq 1\right],

which completes the proof for the first part.

On the other hand, by theorem 1.6.34 we have

	$\displaystyle\lim_{n\to\infty}\Pr\left[X\geq 1\right]$	$\displaystyle\geq\lim_{n\to\infty}\sum_{i\in\left[1,\binom{n}{3}\right]}\frac{% \Pr\left[X_{i}=1\right]}{\operatorname*{\mathbb{E}}\left[X\mid X_{i}=1\right]}$
		$\displaystyle=\lim_{n\to\infty}\frac{\binom{n}{3}p^{3}}{\operatorname*{\mathbb% {E}}\left[X\mid X_{i}=1\right]}.$

For all $\binom{n}{3}$ possible triangles,

•

If there are no vertex overlap, then $\binom{n-3}{3}$ triangles with probability $p^{3}$ .
•

If there are 1 vertex overlap, then $\binom{n-3}{2}\binom{3}{1}$ triangles with probability $p^{3}$ .
•

If there are 2 vertex overlap, then $\binom{n-3}{1}\binom{3}{2}$ triangles with probability $p^{2}$ .
•

If there are 3 vertex overlap, then 1 triangle with probability 1.

Summing, we have

	$\displaystyle\operatorname*{\mathbb{E}}\left[X\mid X_{i}\right]$	$\displaystyle=\sum_{j\in\left[1,\binom{n}{3}\right]}\operatorname*{\mathbb{E}}% \left[X_{j}\mid X_{i}=1\right]$
		$\displaystyle=1+\binom{n-3}{1}\binom{3}{2}p^{2}+\binom{n-3}{2}\binom{3}{1}p^{3% }+\binom{n-3}{3}p^{3}.$

When $n\to\infty$ , $\binom{n}{3}p^{3}\to 1/6$ and $\operatorname*{\mathbb{E}}\left[X\mid X_{i}=1\right]\to 7/6$ , which proves the second part. ∎

Remark 1.6.39.

We attempted 1.6.8 from theorem 1.6.30, which is inspired by [AS16] to use the second/fourth moment method, just to avoid the bounding over binomial coefficients, but it did not bound as good.

Let $\{Y_{i}\}_{i\in[2n]}$ be independent Bernoulli trials from even coins, $\{Z_{i}\}_{i\in[n]}$ each be $Y_{i}-Y_{i+n}$ , and $Z=\sum_{i}Z_{i}$ . Since $Z$ is symmetric over 0, then event $\left|Z\right|>c\sqrt{n}$ is equivalent to $Z^{2}>c^{\prime}n$ .

For random variable $Z^{2}$ , we want to prove $\Pr\left[Z^{2}>c^{\prime}n\right]\geq 1/2$ for some constant $c^{\prime}>0$ , which fits theorem 1.6.30:

•

The second moment is $\operatorname*{\mathbb{E}}\left[Z^{2}\right]=\sum_{i}\operatorname*{\mathbb{E}% }\left[Z_{i}^{2}\right]=n/2$ .
•

The fourth moment is $\operatorname*{\mathbb{E}}\left[Z^{4}\right]=\sum_{i}\operatorname*{\mathbb{E}% }\left[Z_{i}^{4}\right]+\sum_{i\neq j}\operatorname*{\mathbb{E}}\left[Z_{i}^{2% }Z_{j}^{2}\right]=\sum_{i}\operatorname*{\mathbb{E}}\left[Z_{i}^{4}\right]+% \sum_{i\neq j}\operatorname*{\mathbb{E}}\left[Z_{i}^{2}\right]\operatorname*{% \mathbb{E}}\left[Z_{j}^{2}\right]=n/2+\binom{n}{2}\binom{4}{2}/4$ .

Therefore, even when $\Pr\left[Z^{2}>0\right]<1/3$ by Paley-Zygmund theorem 1.6.30, which is too loose.

1.6.6 Lovász Local Lemma

The symmetric Lovász Local Lemma requires that the bad events are all upper bounded by a probability $p$ , and each bad event depends on at most $d$ others.

By definition, an event $E_{n+1}$ is mutually independent of $\{E_{i}\}_{i\in[1,n]}$ , if for any subset $S\subseteq[1,n]$ ,

\Pr\left[E_{n+1}~{}\middle|~{}\bigcap_{i\in S}E_{i}\right]=\Pr\left[E_{n+1}% \right].

Onwards, we denote $E_{S}$ for $\bigcap_{i\in S}E_{i}$ , and $\overline{E}_{S}$ for $\bigcap_{i\in S}\neg E_{i}$ .

Definition 1.6.40 (Dependency Graph).

A dependency graph for events $\{E_{i}\}$ is a graph $G=(V,E)$ , such that $E_{i}$ is independent of the events $\{E_{j}\mid(i,j)\not\in E\}$ . The degree of the dependency graph is the maximum degree of any vertex in the graph.

Lemma 1.6.41 (Symmetric Lovász Local Lemma [EL75]).

Let $\{E_{i}\}_{i\in[1,n]}$ be a set of events, and the following holds:

•

$\Pr\left[E_{i}\right]\leq p$ for all $i\in[1,n]$ ,
•

The degree of the dependency graph given by $\{E_{i}\}$ is at most $d$ ,
•

$4dp\leq 1$ ,

then $\Pr\left[\overline{E}_{[1,n]}\right]>0$ .

Proof.

The proving strategy is proving by induction the following lemma for all possible $S\subseteq[1,n]$ .

Lemma 1.6.42.

For all $S\subseteq[1,n]$ with $k\not\in S$ , we have both following being true

\Pr\left[E_{k}~{}\middle|~{}\overline{E}_{S}\right]\leq 2p\text{ and }\Pr\left% [\overline{E}_{S}\right]\geq(1-2p)^{\left|S\right|}.

Proof.

We prove by induction over all possible $\left|S\right|$ .

When $\left|S\right|=0$ , this is vacuously true.

When $\left|S\right|=1$ , let $S=\{i\}$ . Then $\Pr\left[\neg E_{i}\right]\geq 1-p\geq 1-2p$ . For $\Pr\left[E_{k}\mid\neg E_{i}\right]$ :

•

If $E_{k}$ and $E_{i}$ mutually independent, namely $(i,j)\not\in E$ , then

$\Pr\left[E_{k}\mid\neg E_{i}\right]=\Pr\left[E_{k}\right]\leq p\leq 2p.$
•

Otherwise $(i,k)\in E$ , then

$\Pr\left[E_{k}\mid\neg E_{i}\right]=\frac{\Pr\left[E_{k}\bigcap\neg E_{i}% \right]}{\Pr\left[\neg E_{i}\right]}\leq\frac{\Pr\left[E_{k}\right]}{\Pr\left[% \neg E_{i}\right]}\leq\frac{p}{1-p}\leq 2p,$

where the last inequality holds as $4dp\leq 1$ , meaning $p\leq 1/4$ .

WLOG let $S^{\prime}=[1,s-1]$ , $S=[1,s]$ , and $s\geq 2$ . Supposing the lemma holds for $S^{\prime}$ with $\left|S^{\prime}\right|=s-1$ , then for $S$ ,

	$\displaystyle\Pr\left[\overline{E}_{S}\right]$	$\displaystyle=\Pr\left[\neg E_{s}~{}\middle\|~{}\overline{E}_{S^{\prime}}\right% ]\cdot\Pr\left[\overline{E}_{S^{\prime}}\right]$
		$\displaystyle=\left(1-\Pr\left[E_{s}~{}\middle\|~{}\overline{E}_{S^{\prime}}% \right]\right)\cdot\Pr\left[\overline{E}_{S^{\prime}}\right]$
		$\displaystyle\geq(1-2p)\cdot(1-2p)^{s-1}=(1-2p)^{s},$

where the lower bound follows immediately from the induction hypothesis.

Remark 1.6.43.

Alternatively, we have

	$\displaystyle\Pr\left[\overline{E}_{S}\right]$	$\displaystyle=\Pr\left[\neg E_{s}~{}\middle\|~{}\overline{E}_{S^{\prime}}\right% ]\cdot\Pr\left[\overline{E}_{S^{\prime}}\right]$
		$\displaystyle=\Pr\left[\neg E_{s}~{}\middle\|~{}\overline{E}_{S^{\prime}}\right% ]\cdot\prod_{i\in[1,s-1]}\Pr\left[\neg E_{i}~{}\middle\|~{}\overline{E}_{[1,i-1% ]}\right]$
		$\displaystyle=\prod_{i\in[1,s]}\left(1-\Pr\left[E_{i}~{}\middle\|~{}\overline{E% }_{[1,i-1]}\right]\right)$
		$\displaystyle\geq(1-2p)^{s},$

where the last inequality holds from induction hypothesis.

Let $A\subseteq S$ such that $\forall i\in A$ , $(i,s+1)\in E$ , and $B=S\setminus A$ . If $B=S$ , then $E_{s+1}$ is mutually independent of $\{E_{i}\}_{i\in S}$ ,

\Pr\left[E_{s+1}~{}\middle|~{}\overline{E}_{S}\right]=\Pr\left[E_{s+1}\right]% \leq p\leq 2p.

Otherwise, by Bayes’ rule,

	$\displaystyle\Pr\left[E_{s+1}~{}\middle\|~{}\overline{E}_{S}\right]$	$\displaystyle=\frac{\Pr\left[E_{s+1}\bigcap\overline{E}_{S}\right]}{\Pr\left[% \overline{E}_{S}\right]}=\frac{\Pr\left[E_{s+1}\bigcap\overline{E}_{A}\bigcap% \overline{E}_{B}\right]}{\Pr\left[\overline{E}_{A}\bigcap\overline{E}_{B}% \right]}$
		$\displaystyle=\frac{\Pr\left[E_{s+1}\bigcap\overline{E}_{A}~{}\middle\|~{}% \overline{E}_{B}\right]}{\Pr\left[\overline{E}_{A}~{}\middle\|~{}\overline{E}_{% B}\right]}.$

For numerator, since $E_{s+1}$ is mutually independent of $\{E_{i}\}_{i\in B}$ by the dependency graph, we have

\Pr\left[E_{s+1}\cap\overline{E}_{A}~{}\middle|~{}\overline{E}_{B}\right]\leq% \Pr\left[E_{s+1}~{}\middle|~{}\overline{E}_{B}\right]=\Pr\left[E_{s+1}\right]% \leq p.

For denumerator,

	$\displaystyle\Pr\left[\overline{E}_{A}~{}\middle\|~{}\overline{E}_{B}\right]$	$\displaystyle=1-\Pr\left[\bigcup_{i\in A}E_{i}~{}\middle\|~{}\overline{E}_{B}\right]$
		$\displaystyle\geq 1-\sum_{i\in A}\Pr\left[E_{i}~{}\middle\|~{}\overline{E}_{B}\right]$
		$\displaystyle\geq 1-d\cdot 2p$
		$\displaystyle\geq\frac{1}{2},$

where the first inequality holds from union bound, the second inequality holds from the induction hypothesis, and $\left|A\right|\leq d$ by the degree of the dependency graph, and the last inequality holds from the lemma’s requirement. Hence, $\Pr\left[E_{s+1}~{}\middle|~{}\overline{E}_{S}\right]\leq 2p$ . ∎

Since lemma 1.6.42 holds for any $S$ , which finishes the proof immediately. ∎

Exercise 1.6.44 (Exercise 6.17 [MU17]).

Use lemma 1.6.41 to show that, if

4\cdot\binom{k}{2}\binom{n}{k-2}\cdot 2^{1-\binom{k}{2}}\leq 1,

then it is possible to 2-color the edges of $K_{n}$ so that it has no monochromatic $K_{k}$ subgraph.

Proof.

Let $E_{i}$ be the bad event that the $i^{\mathrm{th}}$ $K_{k}$ being monochromatic.

To upper bound the dependency degree $d$ , we can pick an edge from the $i^{\mathrm{th}}$ $K_{k}$ , then uniformly randomly sample the rest of the vertices from all possible vertices. Hence

d\leq\binom{k}{2}\binom{n}{k-2}.

The probability of $K_{k}$ being monochromatic is $2^{1-\binom{k}{2}}$ . Therefore by lemma 1.6.41, if

4\cdot\binom{k}{2}\binom{n}{k-2}\cdot 2^{1-\binom{k}{2}}\leq 1,

then it is possible to 2-color $K_{n}$ edges such that there is no monochromatic $K_{k}$ . ∎

The symmetric Lovász Local Lemma lemma 1.6.41 works best when all events are upper bounded equally, and the dependency degrees are also upper bounded equally. The asymmetric Lovász Local Lemma has likely or rare events, where likely events have smaller dependency degrees, while rare events could depend on many other events.

Onwards we denote $\Gamma_{i}=\{j\mid(i,j)\in E\}$ for all the neighbors of $E_{i}$ in the dependency graph.

Lemma 1.6.45 (Asymmetric Lovász Local Lemma [EL75]).

Let $\{E_{i}\}_{i\in[1,n]}$ be a set of events. If $\{x_{i}\}_{i\in[1,n]}$ in $[0,1]$ has

\Pr\left[E_{i}\right]\leq x_{i}\cdot\prod_{j\in\Gamma_{i}}(1-x_{j}),

then

\Pr\left[\overline{E}_{[1,n]}\right]\geq\prod_{i\in[1,n]}\left(1-x_{i}\right).

Proof.

The proving strategy is similar to lemma 1.6.41 by introducing following lemma for all possible $S\subseteq[1,n]$ .

Lemma 1.6.46.

For all $S\subseteq[1,n]$ with $k\not\in S$ , we have both following being true

\Pr\left[E_{k}~{}\middle|~{}\overline{E}_{S}\right]\leq x_{k}\text{ and }\Pr% \left[\overline{E}_{S}\right]\geq\prod_{i\in S}\left(1-x_{i}\right).

Proof.

We prove by induction over all possible $\left|S\right|$ .

When $\left|S\right|=0$ , this is vacuously true.

When $\left|S\right|=1$ , let $S=\{i\}$ . Then

\Pr\left[\neg E_{i}\right]\geq 1-x_{i}\cdot\prod_{j\in\Gamma_{i}}\left(1-x_{j}% \right)\geq 1-x_{i}.

For $\Pr\left[E_{k}~{}\middle|~{}\neg E_{i}\right]$ ,

•

If $E_{k}$ and $E_{i}$ are mutually independent, namely $(i,k)\notin E$ , then

$\Pr\left[E_{k}~{}\middle|~{}\neg E_{i}\right]=\Pr\left[E_{k}\right]\leq x_{k}% \cdot\prod_{j\in\Gamma_{k}}\left(1-x_{j}\right)\leq x_{k}.$
•

Otherwise $(i,k)\in E$ , then

$\Pr\left[E_{k}~{}\middle|~{}\neg E_{i}\right]=\frac{\Pr\left[E_{k}\bigcap\neg E% _{i}\right]}{\Pr\left[\neg E_{i}\right]}\leq\frac{\Pr\left[E_{k}\right]}{\Pr% \left[\neg E_{i}\right]}\leq x_{k}\cdot\prod_{j\in\Gamma_{k}\setminus\{i\}}% \left(1-x_{j}\right)\leq x_{k},$

where the second inequality holds from $\Pr\left[\neg E_{i}\right]\geq 1-x_{i}$ .

WLOG let $S^{\prime}=[1,s-1]$ , $S=[1,s]$ , and $s\geq 2$ . Supposing the lemma holds for any $S^{\prime}$ with $\left|S^{\prime}\right|=s-1$ , then for $S$ ,

\Pr\left[\overline{E}_{S}\right]=\Pr\left[\neg E_{s}~{}\middle|~{}\overline{E}% _{S^{\prime}}\right]\cdot\Pr\left[\overline{E}_{S^{\prime}}\right]\geq\left(1-% x_{s}\right)\cdot\prod_{i\in S^{\prime}}\left(1-x_{i}\right)=\prod_{i\in S}% \left(1-x_{i}\right),

which is immediate from induction hypothesis. Alternatively, the same procedure in remark 1.6.43 applies.

Let $A\subseteq S$ such that $\forall i\in A$ , $(i,s+1)\in E$ , and $B=S\setminus A$ . If $B=S$ , then $E_{s+1}$ is mutually independent of $\{E_{i}\}_{i\in S}$ ,

\Pr\left[E_{s+1}~{}\middle|~{}\overline{E}_{S}\right]=\Pr\left[E_{s+1}\right]% \leq x_{s+1}\cdot\prod_{j\in\Gamma_{s+1}}\left(1-x_{j}\right)\leq x_{s+1}.

Otherwise, by Bayes’ rule,

	$\displaystyle\Pr\left[E_{s+1}~{}\middle\|~{}\overline{E}_{S}\right]$	$\displaystyle=\frac{\Pr\left[E_{s+1}\bigcap\overline{E}_{S}\right]}{\Pr\left[% \overline{E}_{S}\right]}=\frac{\Pr\left[E_{s+1}\bigcap\overline{E}_{A}\bigcap% \overline{E}_{B}\right]}{\Pr\left[\overline{E}_{A}\bigcap\overline{E}_{B}% \right]}$
		$\displaystyle=\frac{\Pr\left[E_{s+1}\bigcap\overline{E}_{A}~{}\middle\|~{}% \overline{E}_{B}\right]}{\Pr\left[\overline{E}_{A}~{}\middle\|~{}\overline{E}_{% B}\right]}.$

For numerator, since $E_{s+1}$ is mutually independent of $\{E_{i}\}_{i\in B}$ by the dependency graph, we have

\Pr\left[E_{s+1}\cap\overline{E}_{A}~{}\middle|~{}\overline{E}_{B}\right]\leq% \Pr\left[E_{s+1}~{}\middle|~{}\overline{E}_{B}\right]=\Pr\left[E_{s+1}\right]% \leq x_{s+1}\cdot\prod_{j\in\Gamma_{s+1}}\left(1-x_{j}\right).

For denumerator, let $\left|A\right|=t$ , $A=\{a_{i}\}_{i\in[1,t]}$ , and $A_{\ell}=\{a_{i}\}_{i\in[\ell,t]}$ , then

	$\displaystyle\Pr\left[\overline{E}_{A}~{}\middle\|~{}\overline{E}_{B}\right]$	$\displaystyle=\prod_{i\in[1,t]}\Pr\left[\neg E_{a_{i}}~{}\middle\|~{}\overline{% E}_{A_{i+1}}\cap\overline{E}_{B}\right]$
		$\displaystyle=\prod_{i\in[1,t]}\left(1-\Pr\left[E_{a_{i}}~{}\middle\|~{}% \overline{E}_{A_{i+1}}\cap\overline{E}_{B}\right]\right)$
		$\displaystyle\geq\prod_{i\in A}\left(1-x_{i}\right)$
		$\displaystyle\geq\prod_{i\in\Gamma_{s+1}}(1-x_{i}),$

where the first inequality holds from induction hypothesis, and the second inequality holds from $A\subseteq\Gamma_{s+1}$ . Hence $\Pr\left[E_{s+1}~{}\middle|~{}\overline{E}_{S}\right]\leq x_{s+1}$ . ∎

Since lemma 1.6.46 holds for any $S$ , we finish the proof. ∎

Lemma 1.6.47.

For integer $x\geq 0$ ,

g(x)=\left(1-\frac{1}{1+x}\right)^{x}

is monotone decreasing and lower bounded by $e^{-1}$ .

Proof.

Let $\varphi(x)=x\ln\left(1-1/(1+x)\right)$ , then the first order derivative

\varphi^{\prime}(x)=\ln\left(1-\frac{1}{1+x}\right)+x\cdot\frac{1}{1-1/(1+x)}% \cdot\left(-\frac{-1}{(1+x)^{2}}\right)=\ln\left(1-\frac{1}{1+x}\right)+\frac{% 1}{1+x}.

Let $t=1-1/(1+x)$ , then $\varphi^{\prime}(x)=\ln t+1-t$ .

Since $\ln t\leq t-1$ for all $t$ , then $\varphi^{\prime}(x)\leq 0$ , $g(x)$ is monotone decreasing. As $x\to\infty$ , $g(x)\to e^{-1}$ . ∎

Exercise 1.6.48 (Exercise 6.18 [MU17]).

Use the asymmetric LLL lemma 1.6.45 to show we can improve the symmetric LLL lemma 1.6.41 by replacing the condition $4pd\leq 1$ to $ep(d+1)\leq 1$ .

Proof.

Let each $x_{i}=1/(d+1)$ , then

x_{i}\cdot\prod_{j\in\Gamma_{i}}\left(1-x_{j}\right)\geq x_{i}\cdot\left(1-x_{% j}\right)^{d}=\frac{1}{d+1}\cdot\left(1-\frac{1}{d+1}\right)^{d}\geq\frac{1}{e% (d+1)}\geq p,

where the second inequality holds from lemma 1.6.47.

$p$ is directly applied in lemma 1.6.41, and the weakened condition is immediate. ∎

Remark 1.6.49.

Spencer proved this strengthened result in [Spe77].

Exercise 1.6.50 (Exercise 6.19 [MU17]).

Let $G=(V,E)$ be an undirected graph and suppose each $v\in V$ is associated with a set $S(v)$ of $8r$ colors, where $r\geq 1$ . Suppose, in addition, that for each $v\in V$ and $c\in S(v)$ , there are at most $r$ neighbors $u$ of $v$ with $c$ lies in $S(u)$ . Prove that there exists a coloring of $G$ assigning to each vertex $v$ a color from $S(v)$ such that, for any edge $(u,v)\in E$ , the color assigned to $u$ and $v$ are different. Hint: use $A_{u,v,c}$ to be the event that $u$ and $v$ are both colored with $c$ , then consider the family of such events.

Proof.

Let $X_{u}$ be the random number for vertex $u$ ’s color, and $c\in S(u)$ , then $\Pr\left[X_{u}=c\right]=1/8r$ .

Let $v$ be a neighboring vertex of $u$ , since $v$ is also associated with a set $S(v)$ of $8r$ colors, then $\Pr\left[X_{v}=c\right]\leq 1/8r$ , as $c$ might not be in $S(v)$ . Therefore,

\Pr\left[X_{u}=c\wedge X_{v}=c\right]=\Pr\left[A_{u,v,c}\right]\leq\frac{1}{64% r^{2}}.

For the dependency graph formed by events $\{A_{u,v,c}\}$ , fixing a color $c\in S(u)\cap S(v)$ and an edge $(u,v)\in E$ , the event $A_{u,v,c}$ is dependent on all $A_{u^{\prime},v^{\prime},c^{\prime}}$ where either $u^{\prime}=u$ or $v^{\prime}=v$ . Since $u$ has at most $8r$ colors, and at most $8r^{2}$ neighbors may share colors with $u$ , therefore the dependency graph degree $d\leq 16r^{2}$ by symmetry on $v$ side.

By lemma 1.6.41, by $4dp\leq 4\cdot 16r^{2}\cdot 1/64r^{2}\leq 1$ , there is probability that all edges are colored differently by

\Pr\left[\bigcap_{u,v,c}\neg A_{u,v,c}\right]>0.

∎

Exercise 1.6.51 (Exercise 6.20 [MU17]).

A $k$ -uniform hypergraph is an ordered pair $G=(V,E)$ , but edges consist of sets of $k$ (distinct) vertices, instead of just 2. (So a 2-uniform hypergraph is just what we normally call a graph.) A hypergraph is $k$ -regular if all vertices have degree $k$ ; that is, they are in $k$ hypergraph edges.

Show that for sufficiently large $k$ , the vertices of a $k$ -uniform, $k$ -regular hypergraph can be 2-colored so that no edge is monochromatic. What’s the smallest value of $k$ you can achieve?

Proof.

We form a dependency graph for events of a hypergraph edge being monochromatic. Since the hypergraph is $k$ -regular, then each vertex is appearing in $k$ hypergraph edges. Excluding the hypergraph edge we are discussing, there are $k-1$ other hypergraph edges for the vertex, and therefore the dependency graph degree $d\leq k(k-1)$ .

On the other hand, a $k$ -uniform hypergraph edge is monochromatic with probability $2^{1-k}$ .

•

We can try lemma 1.6.41 and by $4dp\leq 1$ , then $k\geq 10$ .
•

We can also try the Spencer result in 1.6.48 that $ep(d+1)\leq 1$ , then $k\geq 9$ .

∎

1.6.7 Algorithmic Lovász Local Lemma

Theorem 1.6.52 (Beck’s $k$ -Satisfiability Algorithm [Bec91]).

Consider a $k$ -SAT formula with $m$ clauses, where $k\geq 12$ is an even constant, and each variable appears in up to $2^{\alpha k}$ clauses for a sufficiently small constant $\alpha>0$ , then there is an algorithm finding a satisfying assignment for the formula in expected polynomial time in $m$ .

Proof.

Let $\{x_{i}\}_{i\in[1,\ell]}$ be the variables, and $\{C_{i}\}_{i\in[1,m]}$ be the $m$ clauses.

The algorithm has 2 phases: some variables are fixed in the first phase, and the remaining variables are deferred to the second phase. During the first phase variable fixing, a clause $C_{i}$ is considered dangerous if $C_{i}$ is not yet satisfied, and $k/2$ variables in the clause have been fixed.

In the first phase, the algorithm iterates through all variables, if the variable is not in any dangerous clause, assign it independently and uniformly a value from $\{0,1\}$ .

After the first phase, a clause is surviving if it is not yet satisfied, and such surviving clause has no more than $k/2$ variables fixed. A deferred variable is a variable not yet fixed in the first phase. In phase 2, we use exhaustive search to assign values to the deferred variables and so to complete a satisfying assignment for the formula.

Remark 1.6.53.

The algorithm assigns a subset of variables in the first phase, and the remaining variables are deferred to the second phase. The subset of variables with values assigned in the first phase are chosen such that

•

By the Local Lemma, the random partial solution fixed in phase 1 can be extended to a full satisfying assignment without modifying any phase 1 variable assignments.
•

The dependency graph $H^{\prime}$ defined by the deferred variables in phase 2 is with high probability containing small connected subcomponents.

When the dependency graph consists only of small connected subcomponents, a solution for the variables of one component can be found independently of the other components. Therefore, such 2 phase algorithm first breaks the problem into smaller subproblems, and each smaller subproblem can be solved independently with exhaustive search in the phase 2.

We introduce following 2 lemmas for the 2 points in the prior remark.

Lemma 1.6.54.

There is an assignment to the deferred variables such that all the surviving clauses are satisfied.

Proof.

Let $H=(V,E)$ be the dependency graph on $m$ nodes, where $V=[1,m]$ , and $(i,j)\in E$ if and only if $C_{i}\cap C_{j}\neq\varnothing$ . $H$ is the dependency graph for the original problem. Let $H^{\prime}=(V^{\prime},E^{\prime})$ be the dependency graph with $V^{\prime}\subseteq V$ , $E\subseteq E$ , with $i\in V^{\prime}$ if and only if $C_{i}$ is a surviving clause, and $(i,j)\in E^{\prime}$ if and only if $C_{i}$ and $C_{j}$ share deferred variables.

Since a surviving clause has at least $k/2$ deferred variables, then the satisfying probability is at most $2^{-k/2}$ . On the other hand, a variable appears up to $2^{\alpha k}$ clauses, then the degree of the dependency graph $H^{\prime}$ is $d\leq k2^{\alpha k}$ .

By symmetric Local Lemma lemma 1.6.41, given constant $\alpha>0$ that is sufficiently small, if $4\cdot k2^{\alpha k}\cdot 2^{-k/2}\leq 1$ , there exists an assignment that all surviving clauses are satisfied. ∎

Lemma 1.6.55.

All connected components in $H^{\prime}$ are of size $O(\log m)$ with probability $1-o(1)$ .

Proof.

We start by bounding the probability of a given clause surviving phase 1. For a given node, it is dangerous with probability at most $2^{-k/2}$ , that exactly $k/2$ variables in phase 1 are fixed but the clause is not satisfying. A clause is surviving, either itself is dangerous, or it is sharing at least a deferred variable with a dangerous clause, namely it is neighboring a dangerous clause in $H^{\prime}$ . Union bounding over the clause and its neighbors in $H^{\prime}$ , which is at most the dependency graph degree $d\leq k2^{\alpha k}$ , a given node surviving phase 1 with probability at most $(d+1)2^{-k/2}$ .

The survival of individual clauses are not independent of each other, as 2 neighboring surviving clauses share at least a deferred variable. We consider a connected component $R\subseteq H$ of $r$ vertices, then we identify a subset of vertices in $R$ such that the survival of the clauses represented by these vertices are independent events.

Definition 1.6.56.

A 4-tree $S$ of a connected component $R$ in $H$ is defined as follows:

•

$S$ is a rooted tree.
•

Any 2 nodes in $S$ is at least distance $4$ in $H$ .
•

There can be an edge in $S$ only between 2 vertices of distance exactly 4 between them in $H$ .
•

Any node in $R$ is either in $S$ or in distance at most 3 from a node in $S$ .

The motivation of introducing 4-tree is that, for any 2 clauses on $S$ , the survival of the clauses are independent. Since any 2 neighboring clauses $u,v\in S$ are of distance exactly 4 in $H$ , if both $u$ and $v$ are surviving, the clause causing $u$ to survive is at least distance 2 in $H$ from the clause causing $v$ to survive. If 2 clauses are at least distance 2 in $H$ , they are not sharing any variables, and their survival are surely independent. Supposing the survival of a large 4-tree is with low probability, this implies the survival of a large connected subcomponent with low probability.

For a 4-tree to survive, the probability is at most $\left((d+1)2^{-k/2}\right)^{\left|S\right|}$ . For a clause in a 4-tree, there are at most

d+d(d-1)+d(d-1)^{2}\leq d^{3}-1

clauses in $H$ that are within distance 3. Immediate by the expectation argument, there exists a 4-tree $S$ in $R$ with $\left|R\right|=r$ such that $\left|S\right|\geq r/d^{3}$ .

The next step is to union bound over all possible sufficiently large 4-tree, such that we can derive an upper bound for the probability of existence of a sufficiently large 4-tree. A crude way to upper bound the number of 4-trees is, for each root, traverse the 4-tree in Euler cycle by visiting each path in 2 directions. There are at most $m\left(d^{4}\right)^{2r/d^{3}}$ number of traversals by picking a vertex every 4 vertices until $2r/d^{3}$ vertices are picked, over $m$ roots.

The union bound is

md^{8r/d^{3}}\cdot\left((d+1)2^{-k/2}\right)^{r/d^{3}},

when $r\geq c\log m$ for a sufficiently large constant $c>0$ and a sufficiently small constant $\alpha>0$ , the bound is $o(1)$ . ∎

Therefore, the proof is immediate by lemma 1.6.54 and lemma 1.6.55, that phase 1 partitions the problem into subproblems with $O(k\log m)$ variables with probability $1-o(1)$ , then we just need to run constant number of times of phase 1 before we obtain a good partition. ∎

We now discuss the constructive proof by Moser [Mos09]. A simpler version was presented in his STOC’09 talk, which was based on the entropy compression argument. The following analysis follows the “entropy compression” idea, which appears explicitly in his doctoral thesis [Mos12] (see the “Incompressibility” section), rather than being the primary framing in the STOC’09 paper.

At the core of the “entropy compression” argument, it is arguing that the algorithm’s expected runtime must be small, otherwise we are able to compress the random bits used by the algorithm significantly.

We begin with a useful fact on the incompressibility of random strings.

Fact 1.6.57 (Incompressibility Principle).

For injective $f:\{0,1\}^{t}\mapsto\{0,1\}^{\ast}$ , if $\mathbf{s}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{t}$ , then for any integer $c$ ,

\Pr\left[\text{the length of }f(\mathbf{s})\leq t-c\right]\leq 2^{1-c}.

Proof.

There are in total $2^{t-c+1}-1$ binary strings of length at most $t-c$ , while there are $2^{t}$ possible inputs in $\{0,1\}^{t}$ . Hence, if $\mathbf{s}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{t}$ , then the probability of $f$ outputting at most $t-c$ bits is at most $2^{1-c}$ . ∎

There are $2^{t}-1$ binary strings of length at most $t-1$ , and the average length is

\sum_{i\in[0,t-1]}i\cdot\frac{2^{i}}{2^{t}-1}\geq\sum_{i\in[0,t-1]}i\cdot\frac% {2^{i}}{2^{t}}\geq t-2.

Therefore, the expected compression length over $\mathbf{s}\stackrel{{\scriptstyle\textsc{r}}}{{\leftarrow}}\{0,1\}^{t}$ is lower bounded by $t-2$ .

Theorem 1.6.58 (Moser’s $k$ -Satisfiability Algorithm [Mos12]).

For a $k$ -SAT formula with $m$ clauses, and each clause shares variables with at most $2^{k-3}-1$ other clauses. Then a satisfying assignment can be found in expected polynomial time in $m$ .

The “entropy compression” argument is rather clean in the specific setting of $k$ -SAT.

We let $\{x_{i}\}_{i\in[1,\ell]}$ be the $\ell$ variables, $\{C_{i}\}_{i\in[1,m]}$ be the $m$ clauses, $\Gamma_{i}$ be the set of indices of clauses sharing variables with the clause $C_{i}$ , $\Gamma^{+}_{i}$ be the inclusive neighborhood $\Gamma_{i}\cup\{i\}$ , and $V_{i}$ be the set of indices of variables in $C_{i}$ .

Informally, the algorithm picks a uniformly random assignment, then look for an unsatisfied $C_{i}$ . If such $C_{i}$ exists, we sample a new assignment for the variables in $V_{i}$ uniformly at random. Doing so may fix $C_{i}$ , but it may end up unsatisfying $C_{j}$ for some $j\in\Gamma^{+}_{i}$ . The algorithm recursively fix the neighboring clauses, and by the end of the recursion, $C_{i}$ is satisfied with no neighboring clauses damaged. Therefore, the situation is improved by satisfying at least 1 previously unsatisfied clause. Iterating through all $m$ clauses, the algorithm finishes the fixing.

This leads to the question that when will the recursion stop, and is solved by the “entropy compression” argument. We describe the algorithm formally as follows, and bound the expected runtime.

The Moser’s algorithm has 2 functions: solve and local-fix.

•
solve
- –
  
  Sample a uniformly random variable assignment for $\{x_{i}\}_{i\in[1,\ell]}$ .
- –
  While there is $C_{i}$ unsatisfied
  - *
    
    Choose the unsatisfied $C_{i}$ with the smallest $i$ .
  - *
    
    Enter $i$ into the execution log with $\left\lceil\log_{2}m\right\rceil$ bits.
  - *
    
    Call local-fix on the clause $C_{i}$ .
•
local-fix
- –
  
  Sample a uniformly random variable assignment for $\{x_{j}\}_{j\in\Gamma_{i}}$ .
- –
  While there is $k\in\Gamma^{+}_{i}$ such that $C_{k}$ is unsatisfied
  - *
    
    Choose the unsatisfied $C_{k}$ with the smallest $k$ .
  - *
    
    Enter “0” together with $k$ in $k-3$ bits into the execution log.
  - *
    
    Call local-fix on the clause $C_{k}$ .
  - *
    
    Enter “1” into the execution log.

Proof.

There are 2 distinct ways of describing how the algorithm works.

We can think of the algorithm as being described by the random string of bits it used. It takes $\ell$ bits for the initial variable assignment at random, then it takes $k$ bits to resample variables for a clause each time local-fix is called. We refer to each time local-fix is called as a round. Hence, a way to describe the algorithm’s action for $j$ rounds is with the random strings of $\ell+jk$ bits used by the algorithm.

We can also think of the algorithm as being described as the history, the bits in its execution log. It includes the list of clauses called in the main routine and recursion of local-fix. For recursion, the log starts with a bit 0 and ends with a bit 1 to mark the start and the end of of recursion calls. For the index of the clause in the recursion call, we use $k-3$ bits instead of $\left\lceil\log_{2}m\right\rceil$ bits, as $\left|\Gamma^{+}_{i}\right|\leq 2^{k-3}$ . The $\ell$ bits of final variable assignments are also included in the history, serving as an updatable state: each time a clause’s variables being resampled, the state is updated. Hence, the output execution log for the algorithm’s action for $j$ rounds takes at most $\ell+m\left\lceil\log_{2}m\right\rceil+j(k-1)$ , as a round of clause variable resampling outputs $k-1$ bits: 2 bits for start/end marking, and $k-3$ bits for clause index.

Given $\ell+kj$ resampling bits used by the algorithm, and $\ell+m\left\lceil\log_{2}m\right\rceil+j(k-1)$ bits of output execution log, we can view the algorithm as a compression algorithm over random bits. We now show how to recover the resampling bits from the execution log. The execution log determines a sequence of clauses visited by the algorithm, and each visited clause must be unsatisfied before resampling. Only 1 setting of variables unsatisfy a clause. Hence, we work backwards from the final variable assignments. On each clause, we update with unsatisfying variable assignment, such that we know the resampling variables, and therefore we recover the $\ell+jk$ bits of resampling bits.

After proving the compression is injective, now we use the compression argument to bound the expected runtime. Let $J$ be the random variable for the number of rounds in the algorithm. The algorithm takes $\ell+Jk$ uniformly random bits as inputs, outputting at most $\ell+m\left\lceil\log_{2}m\right\rceil+J(k-1)$ bits of history. By 1.6.57,

\ell+m\left\lceil\log_{2}m\right\rceil+J(k-1)\geq\ell+kJ-1,

and when $J=m\left\lceil\log_{2}m\right\rceil+1+i$ ,

\Pr\left[\text{output length}\leq\ell+m\left\lceil\log_{2}m\right\rceil+J(k-1)% \right]\leq 2^{-i}.

Therefore, $\operatorname*{\mathbb{E}}\left[J\right]$ can be bounded as follows

\operatorname*{\mathbb{E}}\left[J\right]\leq m\left\lceil\log_{2}m\right\rceil% +1+\sum_{i\geq 0}\frac{i}{2^{i}}=m\left\lceil\log_{2}m\right\rceil+3.

Therefore, the expected runtime of the algorithm is $O(m\log m)$ . ∎

Exercise 1.6.59 (Exercise 6.20 [MU17]).

In the $k$ -Satisfiability Algorithm using the algorithmic Lovász Local Lemma, we used $\left\lceil\log_{2}m\right\rceil$ bits in history to represent each clause called in the main routine. Instead, we could record in the history which clauses are initially unsatisfied with an array of $m$ bits. Explain any other changes to the algorithm to properly record a history that one can “reverse” to obtain the initial assignment, and explain how this allows one to modify the proof of theorem 1.6.58 so that only $O(m)$ rounds are needed in expectation.

Proof.

Observing each run of local-fix, the subroutine visits an unsatisfied clause, resamples its variables, then fix neighboring unsatisfied clauses recursively. The invariant is, all of the visited clauses and their neighboring clauses are satisfied by the end of the recursion.

If we put $m$ bits for the initially unsatisfied clauses, then we know the first unsatisfied clause visited by local-fix. We maintain a list of satisfied clauses by the first call to the local-fix, update the $m$ bits for unsatisfied clauses, and move on to the remaining unsatisfied clause with smallest index. Repeating $O(m)$ times, we have a full list of visited clauses from history.

Therefore, we use $m$ bits in history for visited unsatisfied clauses from the main routine rather than $m\left\lceil\log_{2}m\right\rceil$ , and therefore replacing all appearances of $m\left\lceil\log_{2}m\right\rceil$ in the argument, we have the expected runtime being $O(m)$ . ∎

The Algorithmic Lovász Local Lemma by Moser and Tardos [MT10] states that: in the variable-based LLL setting, an LLL existence proof is automatically (Las Vegas) constructive via resampling, with expected polynomial runtime. We describe the asymmetric algorithmic LLL, and the symmetric algorithmic LLL follows from 1.6.48.

Theorem 1.6.60 (Asymmetric Algorithmic Lovász Local Lemma [MT10]).

\Pr\left[E_{i}\right]\leq x_{i}\cdot\prod_{j\in\Gamma_{i}}(1-x_{j}),

then there exists an assignment $\{y_{i}\}$ such that $\overline{E}_{[1,n]}$ holds, and a resampling algorithm whose expected number of resampling $E_{i}$ in finding an assignment is at most $x_{i}/(1-x_{i})$ . Hence, the expected runtime is at most $\sum_{i}x_{i}/(1-x_{i})$ .

Corollary 1.6.61 (Symmetric Algorithmic Lovász Local Lemma [MT10]).

Let $\{E_{i}\}_{i\in[1,n]}$ be a set of events in arbitrary probability space that are determined by mutually independent random variables $\{y_{i}\}_{i\in[1,\ell]}$ , and let $G=(V,E)$ be the dependency graph for the events. Supposing the degree of $G$ is at most $d$ , $\Pr\left[E_{i}\right]\leq p$ for $i\in[1,n]$ , and $ep(d+1)\leq 1$ , then there exists an assignment $\{y_{i}\}$ such that $\overline{E}_{[1,n]}$ holds, and a resampling algorithm whose expected number of resampling $E_{i}$ in finding an assignment is at most $1/d$ . Hence, the expected runtime is at most $n/d$ .

The Moser-Tardos algorithmic LLL is even simpler than Moser’s $k$ -SAT algorithm, and the algorithm is described as follows. Onwards we say each event $E_{i}$ as bad events, and the algorithms avoids all the bad events, eventually.

•
Moser-Tardos
- –
  
  Sample a uniformly random variable assignments for $\{y_{i}\}$ .
- –
  While there is $E_{i}$ happening
  - *
    
    Randomly pick an happening $E_{i}$ .
  - *
    
    Resample all $y_{i}$ determines this $E_{i}$ .

We define $\mathbf{c}\in[1,n]^{k}$ as the execution log, where the algorithm has $k$ rounds of resampling over events $\{E_{i}\}$ , and each $c_{i}$ is an index for $n$ events $\{E_{i}\}$ . At the core of the argument is the construction and analysis of a witness tree from resampling each event $E_{c_{i}}$ in the execution log.

Definition 1.6.62 (Witness Tree).

A witness tree is constructed from execution log $\mathbf{c}$ as follows.

•

Let $c_{k}$ be the root.
•
Let $T_{j,k}$ be a witness tree from $c_{j},\ldots,c_{k}$ , and let $j$ goes backwards from $k-1$ to $1$ .
- –
  
  If $c_{j}\in\Gamma^{+}_{o}$ for some $o\in T_{j+1,k}$ , then add $c_{j}$ as the children of the deepest occurrence of such event.
- –
  
  If $E_{c_{j}}$ do not share variables with any event in $T_{j+1,k}$ , then drop $c_{j}$ and move on by $T_{j,k}\leftarrow T_{j+1,k}$ .
•

Eventually, $T_{k}\leftarrow T_{1,k}$ .

The following facts are immediate by the construction of the witness tree.

Fact 1.6.63.

For any events $E_{i}$ and $E_{j}$ sharing variables, they are appearing in the same depth of a witness tree.

Fact 1.6.64.

A variable $x_{i}$ is not appearing twice in the same depth of a witness tree.

Intuitively, a witness tree is a tree justifying how we end up selecting $E_{c_{i}}$ to resample all variables in $V_{c_{i}}$ .

We introduce an additional fact, that the witness trees from different prefixes of an execution log are different.

Fact 1.6.65.

For execution logs $\mathbf{c}_{0}$ of length $k_{0}$ and $\mathbf{c}_{1}=\mathbf{c}_{0}\parallel\mathbf{c}^{\prime}$ of length $k_{1}$ , the execution trees $T_{k_{0}}$ and $T_{k_{1}}$ are different.

Proof.

Let the roots from $\mathbf{c}_{0}$ and $\mathbf{c}_{1}$ be $r_{0}$ and $r_{1}$ .

If $r_{0}\neq r_{1}$ , then $T_{k_{0}}\neq T_{k_{1}}$ by root. Otherwise, $\mathbf{c}_{1}$ has at least one more occurrence of $r_{0}$ , resulting in $T_{k_{0}}\neq T_{k_{1}}$ . ∎

Hence, the next lemma for counting the occurrence of resampling $E_{i}$ in $\mathbf{c}$ is immediate by 1.6.65.

Lemma 1.6.66.

Let $X_{i}$ be the random variable of occurrence of resampling $E_{i}$ in $\mathbf{c}$ , and $X_{i,j}$ be the 0-1 random variable indicating the witness tree $T_{j}$ from $\mathbf{c}_{[1,j]}$ , the prefix of $\mathbf{c}$ , has root $i$ . Then

X_{i}=\sum_{j\in[1,k]}X_{i,j}.

Moreover, let $W_{i}$ be the set of witness trees rooted by $i$ , then by linearity of expectation,

\operatorname*{\mathbb{E}}\left[X_{i}\right]=\sum_{j\in[1,k]}\operatorname*{% \mathbb{E}}\left[X_{i,j}\right]=\sum_{j\in[1,k]}\sum_{T\in W_{i}}\Pr\left[T=T_% {j}\right]=\sum_{T\in W_{i}}\sum_{j\in[1,k]}\Pr\left[T=T_{j}\right].

We want to bound $\Pr\left[T_{j}=T\right]$ . We say $T$ appears in $\mathbf{c}$ , if $T=T_{j}$ for $T_{j}$ constructed from some $\mathbf{c}_{[1,j]}$ prefix of $\mathbf{c}$ . Hence, fixing a $T$ , since $\{T_{j}\}$ are all distinct by 1.6.65, $T=T_{j}$ are all independent, and

\Pr\left[T\text{ appears in }\mathbf{c}\right]=\sum_{j\in[1,k]}\Pr\left[T=T_{j% }\right].

Lemma 1.6.67.

\Pr\left[T\text{ appears in }\mathbf{c}\right]\leq\prod_{j\in T}\Pr\left[E_{j}% \right],

where the $T$ in the right hand side production is a multiset, such that we capture multiple occurrence of an event being resampled.

Proof.

If we traverse the witness tree $T$ in reverse BFS method, namely layering by depth bottom up, then we observe earlier events resampling induces later events resampling, following the Moser-Tardos algorithm’s execution order.

For variables $\{y_{i}\}$ , each resampling creates a sequence of assignments, say $y_{i}^{1},\ldots,y_{i}^{s}$ . By 1.6.64, we know that $y_{i}^{a}$ and $y_{i}^{b}$ with $a\neq b$ should be on different depth.

Hence, fixing the randomness from Moser-Tardos algorithm, which is fixing the assignment sequences $\{\{y_{i}^{s}\}_{s}\}_{i}$ , we form a checking algorithm for $T$ as follows. The check algorithm traverses in described way, and checks if events in the current layer are happening: aborts if any event is not happening. Before traversing the next depth, the check algorithm resamples all the variables of the events in the current layer, by moving each $y_{i}^{s}$ to $y_{i}^{s+1}$ .

It becomes obvious that, on input the witness tree $T$ from a successful run of Moser-Tardos algorithm, by fixing the assignment sequences for $\{\{y_{i}^{s}\}_{s}\}_{i}$ , the tree checking algorithm always passes. Therefore

\Pr\left[T\text{ appears in }\mathbf{c}\right]\leq\Pr\left[\text{check}(T)% \text{ succeeds}\right].

To bound the probability of a tree being valid in the checking algorithm, we use 1.6.63 and 1.6.64, that the events are not sharing variables in a same depth, such that events in a layer are independent, and each layer is independent of each other. Hence, a tree is valid in the checking algorithm with probability $\prod_{j\in T}\Pr\left[E_{j}\right]$ .

Thus, the inequality holds by the coupling arguments above. ∎

Now we have derived

\operatorname*{\mathbb{E}}\left[X_{i}\right]=\sum_{T\in W_{i}}\Pr\left[T\text{% appears in }\mathbf{c}\right]\leq\sum_{T\in W_{i}}\prod_{j\in T}\Pr\left[E_{j% }\right]

by lemma 1.6.66 and lemma 1.6.67, the final step would be bounding the right hand side sum of product. We derive the upper bound by Galton-Watson process, that each children of $E_{i}$ in $\Gamma_{i}^{+}$ spawns with probability $x_{i}$ independently.

Lemma 1.6.68.

Deriving $T$ rooted with $i$ with Galton-Watson process has probability

p_{T}=\frac{1-x_{i}}{x_{i}}\cdot\prod_{j\in T}\Pr\left[E_{j}\right].

Proof.

Let each node $E_{j}$ has a set $S_{j}\subseteq\Gamma^{+}_{j}$ for the indices of children in $T$ , and the probability derivation follows

	$\displaystyle p_{T}$	$\displaystyle=\prod_{j\in T}\left(\prod_{k\in S_{j}}x_{k}\cdot\prod_{k\in% \Gamma^{+}_{j}\setminus S_{j}}(1-x_{k})\right)=\prod_{j\in T}\left(\prod_{k\in S% _{j}}\frac{x_{k}}{1-x_{k}}\cdot\prod_{k\in\Gamma_{j}^{+}}(1-x_{k})\right)$
		$\displaystyle=\frac{1-x_{i}}{x_{i}}\cdot\prod_{j\in T}\left(x_{j}\cdot\prod_{k% \in\Gamma_{j}}(1-x_{k})\right)=\frac{1-x_{i}}{x_{i}}\cdot\prod_{j\in T}\Pr% \left[E_{j}\right],$

where the third equality holds from moving all the $x_{k}/(1-x_{k})$ terms for $k\in S_{j}$ from $E_{j}$ to all the children in $S_{j}$ . ∎

The proof for theorem 1.6.60 follows immediately:

Proof.

By lemma 1.6.68, we have

\operatorname*{\mathbb{E}}\left[X_{i}\right]=\sum_{T\in W_{i}}\Pr\left[T\text{% appears in }\mathbf{c}\right]\leq\sum_{T\in W_{i}}\prod_{j\in T}\Pr\left[E_{j% }\right]=\frac{x_{i}}{1-x_{i}}\cdot\sum_{T\in W_{i}}p_{T}\leq\frac{x_{i}}{1-x_% {i}},

and $\sum_{T}p_{T}\leq 1$ as we are summing over disjoint events. The rest is immediate by the linearity of expectation. ∎

	$\displaystyle\Pr\left[\overline{E}_{S}\right]$	$\displaystyle=\Pr\left[\neg E_{s}~{}\middle\|~{}\overline{E}_{S^{\prime}}\right% ]\cdot\Pr\left[\overline{E}_{S^{\prime}}\right]$
		$\displaystyle=\Pr\left[\neg E_{s}~{}\middle\|~{}\overline{E}_{S^{\prime}}\right% ]\cdot\prod_{i\in[1,s-1]}\Pr\left[\neg E_{i}~{}\middle\|~{}\overline{E}_{[1,i-1% ]}\right]$
		$\displaystyle=\prod_{i\in[1,s]}\left(1-\Pr\left[E_{i}~{}\middle\|~{}\overline{E% }_{[1,i-1]}\right]\right)$
		$\displaystyle\geq(1-2p)^{s},$

	$\displaystyle\Pr\left[\overline{E}_{A}~{}\middle\|~{}\overline{E}_{B}\right]$	$\displaystyle=1-\Pr\left[\bigcup_{i\in A}E_{i}~{}\middle\|~{}\overline{E}_{B}\right]$
		$\displaystyle\geq 1-\sum_{i\in A}\Pr\left[E_{i}~{}\middle\|~{}\overline{E}_{B}\right]$
		$\displaystyle\geq 1-d\cdot 2p$
		$\displaystyle\geq\frac{1}{2},$

	$\displaystyle\Pr\left[\overline{E}_{A}~{}\middle\|~{}\overline{E}_{B}\right]$	$\displaystyle=\prod_{i\in[1,t]}\Pr\left[\neg E_{a_{i}}~{}\middle\|~{}\overline{% E}_{A_{i+1}}\cap\overline{E}_{B}\right]$
		$\displaystyle=\prod_{i\in[1,t]}\left(1-\Pr\left[E_{a_{i}}~{}\middle\|~{}% \overline{E}_{A_{i+1}}\cap\overline{E}_{B}\right]\right)$
		$\displaystyle\geq\prod_{i\in A}\left(1-x_{i}\right)$
		$\displaystyle\geq\prod_{i\in\Gamma_{s+1}}(1-x_{i}),$