Chapter 22: The Probabilistic Method

Can a random object certify that a rare-looking structure exists?

Suppose we want to color every pair among six vertices red or blue without creating four vertices whose six pairs all have one color. Trying examples can find a witness, but how can we prove that some witness exists before finding it? The probabilistic method places a distribution on candidate objects and proves that the desired outcomes have positive probability. Any such outcome must exist.

Only elementary finite probability is needed initially. An event is a set of outcomes; its probability is the sum of their weights. A random variable assigns a number to each outcome, and its expectation is the weighted average of those numbers. We introduce each tool as it becomes necessary, so a separate probability course is useful background rather than an entry requirement.

Randomness serves several different purposes. It can certify existence without producing a witness, guide a search, or support a deterministic construction after the random choices are replaced by conditional expectations. These conclusions should not be conflated.

22.1 Probability spaces and random variables

A finite probability space consists of an outcome set $\Omega$ and weights $p(\omega)\ge0$ summing to 1. For an event $A\subseteq\Omega$ and a random variable $X:\Omega\to\mathbb R$,

$$ \Pr(A)=\sum_{\omega\in A}p(\omega),\qquad \mathbb E X=\sum_{\omega\in\Omega}p(\omega)X(\omega). $$

The indicator $\mathbf1_A$ is 1 on $A$ and 0 outside it, so $\mathbb E\mathbf1_A=\Pr(A)$. Indicators convert a combinatorial count into a sum whose expectation is often easy to evaluate.

If $\Pr(B)\gt0$, define conditional probability by $\Pr(A\mid B)=\Pr(A\cap B)/\Pr(B)$. Events are independent when $\Pr(A\cap B)=\Pr(A)\Pr(B)$. A collection is mutually independent when this product identity holds for every subcollection, not merely for pairs. A product space samples its coordinate variables independently; events depending on disjoint coordinate sets are then independent as whole collections.

Solved example. Flip two independent fair bits, giving outcomes 00,01,10,11, each with probability $1/4$. Let $A$ mean that the first bit is 1 and $B$ that the second is 1. Then $\Pr(A)=\Pr(B)=1/2$ and $\Pr(A\cap B)=1/4$. Let $C$ mean that the two bits agree. Each pair among $A,B,C$ is independent, but

$$ \Pr(A\cap B\cap C)=\frac14\ne\frac18=\Pr(A)\Pr(B)\Pr(C). $$

This example explains why pairwise independence is insufficient for the local lemma's dependency hypothesis.

For a real random variable, its variance is

$$ \operatorname{Var}(X)=\mathbb E[(X-\mathbb E X)^2] =\mathbb E[X^2]-(\mathbb E X)^2. $$

The covariance of $X,Y$ is $\operatorname{Cov}(X,Y)=\mathbb E[XY]-\mathbb E X\mathbb E Y$. It records a particular numerical dependence; zero covariance does not generally imply independence.

Exercise. Let $X$ count the 1s in the two fair bits. Find its distribution, mean, and variance. Hint: its values on the four outcomes are $0,1,1,2$. Solution: the probabilities for values $0,1,2$ are $1/4,1/2,1/4$; $\mathbb E X=1$ and $\operatorname{Var}(X)=1/2$.

22.2 Linearity of expectation

For finitely many random variables $X_1,\ldots,X_m$ and constants $a_1,\ldots,a_m$,

$$ \mathbb E\left[\sum_i a_iX_i\right]=\sum_i a_i\mathbb E X_i. $$

Proof. Expand the finite weighted average and interchange the sums:

$$ \sum_{\omega}p(\omega)\sum_i a_iX_i(\omega) =\sum_i a_i\sum_{\omega}p(\omega)X_i(\omega). $$

No independence appears. This makes the identity particularly useful when configurations share vertices or edges.

Solved example: fixed points. Choose a uniformly random permutation of $[n]$, and let $I_i$ indicate that position $i$ is fixed. There are $(n-1)!$ permutations fixing $i$ out of $n!$, so $\mathbb E I_i=1/n$. The number $F$ of fixed points satisfies $\mathbb E F=\sum_i1/n=1$. Knowing that one position is fixed changes the distribution of the others, but this does not invalidate the calculation. The conclusion is an average, not a claim that every permutation has one fixed point.

A useful averaging consequence. At least one outcome has $X\ge\mathbb E X$, and at least one has $X\le\mathbb E X$. Otherwise every value would be strictly on one side of its own average. If $X$ is integer-valued, the first statement supplies a value at least $\lceil\mathbb E X\rceil$.

Exercise. For a graph with $m$ edges, assign each vertex independently to one of two sides with equal probability. Compute the expected number of crossing edges. Hint: each pair of endpoint bits differs with probability $1/2$. Solution: the expectation is $m/2$, so some cut has at least $\lceil m/2\rceil$ crossing edges.

22.3 First-moment method

The first moment is the expectation. For a nonnegative random variable $X$ and $t\gt0$, Markov's inequality states

$$ \Pr(X\ge t)\le\frac{\mathbb E X}{t}. $$

Proof. Pointwise, $X\ge t\mathbf1_{\{X\ge t\}}$. Taking expectations gives the inequality. No independence is required.

If $X$ is a nonnegative integer counting defects, then

$$ \Pr(X=0)\ge1-\mathbb E X. $$

Thus $\mathbb E X\lt1$ proves that some defect-free outcome exists. The integer assumption is essential: the constant real variable $X=1/2$ has expectation below 1 but never equals zero. When counting bad events $A_i$, the same bound is the union bound $\Pr(\bigcup_i A_i)\le\sum_i\Pr(A_i)$.

Solved example. The opening graph has $\mathbb E X=15/32$, so at least a $17/32$ proportion of its uniformly sampled colorings avoid monochromatic $K_4$. This lower bound on the success probability is stronger information than mere existence, but it need not equal the exact proportion.

For a 3-uniform hypergraph with $m$ edges, independently color its vertices with two fair colors. An edge is monochromatic with probability $2^{1-3}=1/4$. Therefore $m/4\lt1$ is a sufficient condition for a proper weak two-coloring. In general uniformity $r$, the corresponding condition is $m2^{1-r}\lt1$.

The diagram exhausts the eight vertex-bit assignments for a single three-vertex edge. Only 000 and 111 are defects. Here the bad-count variable is itself an indicator, so $\mathbb E X=1/4$ and the success probability is exactly $3/4$.

Exercise. If a bad-count variable has expectation 2, must every candidate have a defect? Hint: an average does not determine the minimum. Solution: no. For example, values 0 and 4, each with probability $1/2$, have expectation 2. The first-moment zero-defect test is sufficient, not necessary.

22.4 Alterations and deletion arguments

An alteration samples a candidate and then repairs it, commonly by deleting one item from each defect. The key is to track both the useful quantity and the repair cost. A sample need not be defect-free if its defects can be removed cheaply.

Independent-set bound. Let $G$ be a simple graph with $n$ vertices and $m$ edges. Include each vertex independently in $S$ with probability $p\in[0,1]$. Let $Y=|S|$ and let $Z$ count edges with both endpoints in $S$. Then

$$ \mathbb E Y=np,\qquad\mathbb E Z=mp^2,\qquad \mathbb E(Y-Z)=np-mp^2. $$

Delete one endpoint of each surviving edge until none remains. There were initially $Z$ internal edges, and deleting vertices cannot create an edge, so at most $Z$ vertices are removed. The remaining set is independent and has size at least $Y-Z$. Averaging therefore proves

$$ \alpha(G)\ge np-mp^2. $$

If $m\ge n/2$ and $m\gt0$, choose $p=n/(2m)$ to obtain $\alpha(G)\ge n^2/(4m)$. For smaller $m$, use the endpoint $p=1$, giving $\alpha(G)\ge n-m$. The optimized parameter must remain in $[0,1]$.

Solved trace. In the cycle on $[6]$, take $S=\{1,2,3,5\}$. Its internal edges are 12 and 23, so $Y=4$, $Z=2$. Deleting vertex 2 removes both defects, leaving the independent set $\{1,3,5\}$ of size three, better than the generic guarantee $Y-Z=2$. With $p=1/2$, the expected guarantee is $6/2-6/4=3/2$, which certifies an independent set of size at least two. It does not assert optimality; this cycle has an independent set of size three.

Hypergraph coloring repair. If a two-colored hypergraph has $X$ monochromatic edges, choose one vertex from each such edge and delete the chosen vertices. Every originally bad edge loses a vertex, while no originally good surviving edge becomes monochromatic. The induced hypergraph on the remaining vertices is properly weakly colored and has at least $n-X$ vertices. If $\mathbb E X=\mu$, some outcome can therefore be repaired while retaining at least $\lceil n-\mu\rceil$ vertices. This changes the object by deletion; it does not color every vertex of the original hypergraph properly.

Exercise. A sampled graph has 12 vertices and five internal edges. What independent-set size does one-endpoint deletion guarantee? Hint: subtract an upper bound on the repair cost. Solution: at least seven vertices. Shared endpoints may make the actual repair cheaper.

22.5 Second-moment method

The second moment $\mathbb E[X^2]$ measures how unevenly a count is distributed. If $X\ge0$, $\mathbb E X\gt0$, and its second moment is finite, Cauchy–Schwarz gives

$$ \mathbb E X=\mathbb E[X\mathbf1_{\{X\gt0\}}] \le\sqrt{\mathbb E[X^2]\Pr(X\gt0)}. $$

Consequently

$$ \Pr(X\gt0)\ge\frac{(\mathbb E X)^2}{\mathbb E[X^2]}. $$

Here $X$ usually counts desired configurations, and the goal is their presence. This differs from using a bad-count variable and seeking $X=0$.

For $X=\sum_i I_i$, expanding the square gives

$$ \mathbb E[X^2]=\sum_i\mathbb E I_i+2\sum_{i\lt j}\mathbb E[I_iI_j]. $$

Classify pairs by their overlap before computing the joint probabilities. Covariances similarly give $\operatorname{Var}(X)=\sum_i\operatorname{Var}(I_i)+2\sum_{i\lt j}\operatorname{Cov}(I_i,I_j)$.

Solved example: triangles in a random graph. In $G(4,1/2)$, each of the six possible edges is present independently with probability $1/2$. Let $X$ count its four potential triangles. Then $\mathbb E X=4/8=1/2$. Each pair of distinct triangles shares one edge, so together they require five edges, with joint probability $1/32$. There are six unordered triangle pairs. Hence

$$ \mathbb E[X^2]=\frac12+2\cdot6\cdot\frac1{32}=\frac78, \qquad\Pr(X\gt0)\ge\frac{1/4}{7/8}=\frac27. $$

Exact enumeration gives 23 triangle-containing graphs among the 64 outcomes, so the actual probability is $23/64$. The second-moment estimate is a lower bound, not an exact count. In a larger random graph, triangles sharing only a vertex still have independent indicators because their edge-coordinate sets are disjoint; sharing an edge is the relevant overlap.

Applying Markov to $(X-\mathbb E X)^2$ yields Chebyshev's inequality,

$$ \Pr(|X-\mathbb E X|\ge t)\le\frac{\operatorname{Var}(X)}{t^2}. $$

In particular, $\Pr(X=0)\le\operatorname{Var}(X)/(\mathbb E X)^2$. If that ratio tends to zero in a sequence of models, the desired configuration is present with probability tending to 1. The finite triangle example has ratio $5/2$, so this particular Chebyshev bound is uninformative despite the useful Cauchy–Schwarz estimate.

Exercise. Let $X=M$ with probability $1/M$ and 0 otherwise, for an integer $M\ge1$. Compute the second-moment bound. Hint: $\mathbb E X=1$. Solution: $\mathbb E[X^2]=M$, so $\Pr(X\gt0)\ge1/M$, exactly its actual probability. A positive mean alone does not make success frequent.

22.6 Conditional expectation and derandomization

Suppose random choices construct an object with score $Y$ and $\mathbb E Y\ge a$. After some choices are fixed, the current conditional expectation is a weighted average of the values obtained by the next possible choices. At least one choice preserves or increases it. Repeating that choice rule finishes with an actual score at least $a$.

For binary choices with conditional probabilities $p$ and $1-p$, the identity is

$$ \mathbb E[Y\mid\text{prefix}] =p\,\mathbb E[Y\mid\text{prefix},0] +(1-p)\,\mathbb E[Y\mid\text{prefix},1]. $$

To minimize a nonnegative defect count, choose a branch whose conditional expectation does not increase. If its initial expectation is below 1, the terminal integer count is zero. This is the method of conditional expectations. It becomes an efficient derandomization only when the required conditional quantities can be computed efficiently; the averaging identity by itself makes no runtime promise.

Solved deterministic max-cut trace. Use graph edges 12,13,23,34. Random fair vertex sides give expected cut size $4/2=2$. Fix vertex 1 on side 0; this preserves the expectation by symmetry.

The final sides are $(0,1,0,1)$. Edges 12,23,34 cross and 13 does not, giving score 3. During the trace, an edge with both endpoints fixed contributes either 0 or 1; an edge with at least one free independent fair endpoint contributes $1/2$. These local contributions make all entries directly computable.

Proof of the maintained guarantee. Each chosen branch is at least the current average, so the conditional expected score never falls below its initial value. Once all bits are fixed, no randomness remains, and the conditional expectation equals the score of the constructed cut. This proves the guarantee independently of the example's particular tie-breaking rule.

An upper bound on conditional expected defects that can be updated efficiently is often called a pessimistic estimator. To replace exact expectation, its update rule must still guarantee a nonincreasing branch and must certify that a terminal value below 1 excludes defects. An arbitrary heuristic score need not satisfy either condition.

Exercise. A fair next bit gives conditional expected scores 4 and 7. Which branch preserves the maximization guarantee? Hint: compare both values with their average. Solution: the current value is $11/2$; choose the branch with value 7. For minimizing defects, choose 4 instead.

22.7 Chernoff, Hoeffding, and Azuma–Hoeffding inequalities

Concentration inequalities control deviations from a mean. Their hypotheses differ: Chernoff exploits independent Bernoulli summands, Hoeffding uses independent bounded summands, and Azuma–Hoeffding uses bounded increments of a martingale. Independence of all summands should not be assumed merely because each summand is individually bounded.

Chernoff bounds. Let $S=\sum_{i=1}^n B_i$, where the $B_i$ are independent Bernoulli variables, with possibly different success probabilities, and let $\mu=\mathbb E S\gt0$. For $\delta\gt0$,

$$ \Pr(S\ge(1+\delta)\mu) \le\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu. $$

Useful simpler forms, for $0\lt\delta\le1$, are

$$ \Pr(S\ge(1+\delta)\mu)\le e^{-\mu\delta^2/3},\qquad \Pr(S\le(1-\delta)\mu)\le e^{-\mu\delta^2/2}. $$

Proof mechanism. For $\lambda\gt0$, apply Markov to $e^{\lambda S}$ and use independence:

$$ \mathbb E e^{\lambda S} =\prod_i\bigl(1+p_i(e^\lambda-1)\bigr) \le\exp\bigl(\mu(e^\lambda-1)\bigr). $$

Choosing $\lambda=\log(1+\delta)$ proves the first displayed upper bound. Negative exponential parameters give the lower-tail counterpart; elementary logarithm estimates yield the simplified constants. The logarithm here is natural.

Hoeffding's inequality. Let independent real variables $Y_i$ satisfy deterministic bounds $a_i\le Y_i\le b_i$ almost surely, and put $S=\sum_iY_i$. For $t\gt0$ and $L=\sum_i(b_i-a_i)^2\gt0$,

$$ \Pr(S-\mathbb E S\ge t)\le e^{-2t^2/L},\qquad \Pr(|S-\mathbb E S|\ge t)\le2e^{-2t^2/L}. $$

The lower one-sided bound is identical. The deterministic case $L=0$ has no positive deviation. A primary source is Hoeffding, Probability inequalities for sums of bounded random variables.

Why the exponential estimate holds. For a bounded $Y\in[a,b]$, write $\psi(\lambda)=\log\mathbb E e^{\lambda(Y-\mathbb E Y)}$. Its second derivative is the variance under an exponentially tilted distribution, still supported on $[a,b]$. That variance is at most $(b-a)^2/4$, since squared distance from the interval's midpoint is at most this number and variance minimizes mean squared distance over centers. With $\psi(0)=\psi'(0)=0$, integrating twice gives

$$ \mathbb E e^{\lambda(Y-\mathbb E Y)}\le e^{\lambda^2(b-a)^2/8}. $$

Multiply these estimates for independent variables, apply exponential Markov, and choose $\lambda=4t/L$. This proves the upper tail; negate the variables and use the union bound for the other forms.

Azuma–Hoeffding. A filtration $\mathcal F_0\subseteq\cdots\subseteq\mathcal F_n$ represents increasing information. An integrable adapted sequence $M_i$ is a martingale if $\mathbb E[M_i\mid\mathcal F_{i-1}]=M_{i-1}$. If deterministic $c_i$ satisfy $|M_i-M_{i-1}|\le c_i$ almost surely and $C=\sum_i c_i^2\gt0$, then

$$ \Pr(|M_n-M_0|\ge t)\le2\exp\left(-\frac{t^2}{2C}\right). $$

Its proof applies the bounded-variable exponential estimate conditionally to each centered increment in $[-c_i,c_i]$, then iterates conditional expectation. The increments need not be independent. For a function of independent coordinates, exposing them one by one gives the Doob martingale $M_i=\mathbb E[f\mid\mathcal F_i]$. If changing coordinate $i$ changes $f$ by at most $c_i$, then the increment is at most $c_i$ in absolute value. Extensions where worst-case influence is too large are studied in Warnke, On the method of typical bounded differences; no such extension is needed here.

Solved comparison. For 100 independent fair bits, $\mu=50$. The simplified Chernoff upper bound at $S\ge65$, with $\delta=0.3$, is $e^{-1.5}$. Hoeffding gives the sharper $e^{-4.5}$, about $0.0111$, for this event and $2e^{-4.5}$ for $|S-50|\ge15$. In the exposure martingale, each increment is exactly $\pm1/2$, so $C=100/4=25$ and Azuma gives the same two-sided $2e^{-4.5}$. These are bounds, not exact binomial-tail probabilities.

Exercise. For 200 independent variables in $[0,1]$, bound the probability that their sample average exceeds its expected value by at least $0.1$. Hint: the sum's deviation is 20 and $L=200$. Solution: Hoeffding gives $e^{-2\cdot20^2/200}=e^{-4}$.

22.8 Lovász local lemma

The union bound pays for every bad event globally. The Lovász local lemma can exploit a sparse pattern of dependence even when that global sum is too large.

Let $A_1,\ldots,A_m$ be bad events. A dependency graph connects events so that each $A_i$ is independent of the entire collection of its nonneighbors, meaning the information generated jointly by that collection, not just each event separately. Write $\Gamma(i)$ for its neighbors. In a product space, connecting events whenever they share an underlying coordinate gives a valid graph, even if some connected pairs happen to be independent.

Asymmetric local lemma. If numbers $x_i\in(0,1)$ satisfy

$$ \Pr(A_i)\le x_i\prod_{j\in\Gamma(i)}(1-x_j)\quad\text{for every }i, $$

then

$$ \Pr\left(\bigcap_i A_i^c\right)\ge\prod_i(1-x_i)\gt0. $$

Proof mechanism and conditional bound. Induct on the number of events being avoided to establish

$$ \Pr\left(A_i\mid\bigcap_{j\in S}A_j^c\right)\le x_i\qquad(i\notin S). $$

Split $S$ into neighboring indices $S_1$ and nonneighboring indices $S_2$. Joint independence makes $\Pr(A_i\mid\bigcap_{j\in S_2}A_j^c)=\Pr(A_i)$. Avoiding neighbors can increase this probability, but the chain rule and the induction hypothesis lower-bound the relevant denominator by $\prod_{j\in S_1}(1-x_j)$. Consequently

$$ \Pr\left(A_i\mid\bigcap_{j\in S}A_j^c\right) \le\frac{\Pr(A_i)}{\prod_{j\in S_1}(1-x_j)}\le x_i. $$

Each chain-rule factor uses a smaller conditioning set; simultaneously those factors show that all avoidance conditioning events have positive probability. The empty-set base follows from $\Pr(A_i)\le x_i$. Finally, multiplying the conditional probabilities of avoiding each event gives the displayed positive product bound.

Symmetric sufficient condition. If $\Pr(A_i)\le p$ and the dependency graph has maximum degree at most $D$, then

$$ e\,p(D+1)\le1 $$

is sufficient. For $D\ge1$, take $x_i=1/(D+1)$ and use $(1-1/(D+1))^D\ge e^{-1}$. For $D=0$, mutual independence directly gives a positive avoidance probability whenever $p\lt1$; the stated sufficient inequality implies this.

Solved hypergraph example. Independently color the vertices of a 7-uniform hypergraph with two fair colors. For each edge, let its bad event be monochromaticity, with $p=2^{1-7}=1/64$. If each edge meets at most 12 other edges, use their intersection graph as the dependency graph. Then $ep(D+1)=13e/64\lt1$, so every vertex can be properly weakly two-colored. This remains true regardless of the number of edges.

For a concrete family, take $V=\mathbb Z/128\mathbb Z$ and the 128 edges

$$ e_i=\{i,i+1,\ldots,i+6\}\pmod{128},\qquad0\le i\le127. $$

An edge intersects precisely those starting at offsets $\pm1,\ldots,\pm6$, so $D=12$. The global first-moment count is $128/64=2$ and does not certify zero defects; the local lemma does. Alternating bits supply a simple explicit witness in this particular family. The value of the lemma is that its same overlap hypothesis applies to families lacking that cyclic symmetry.

Exercise. A 6-uniform hypergraph has each vertex in at most two edges. Does the symmetric lemma certify a weak two-coloring? Hint: an edge meets at most $6(2-1)$ other edges. Solution: $p=1/32$, $D\le6$, and $7e/32\lt1$, so it does. Counting the same neighboring edge twice would only make the degree estimate more conservative.

22.9 Moser–Tardos constructive local lemma

Optional advanced elective. The local lemma is an existence theorem; a construction needs access to the variables and a way to repair violations. In the variable model, finitely many underlying random variables are mutually independent, every bad event is determined by a specified subset of them, and dependency edges connect events sharing variables.

The Moser–Tardos algorithm samples all variables once, then repeatedly chooses a currently true bad event and resamples every variable on which it depends, independently from its original distribution. It stops when no bad event remains. Fresh draws are essential; deterministically flipping a bit is a different algorithm.

Constructive theorem. Under the asymmetric condition of Section 22.8, the expected number of resamplings of event $A_i$ is at most $x_i/(1-x_i)$; the total is at most $\sum_i x_i/(1-x_i)$. Thus termination occurs with probability 1. Efficient running time additionally requires efficient sampling and violation detection. The primary source is Moser and Tardos, A constructive proof of the general Lovász Local Lemma.

Solved repair trace. Use vertex bits on $[8]$ and edges $e_1=\{1,\ldots,7\}$, $e_2=\{2,\ldots,8\}$. Start at 00000001. The following fresh samples are one possible trace:

The first repair leaves its selected event bad and creates another violation. This is allowed. The second repair resolves both. Each specified seven-bit sample has probability $2^{-7}$; the theorem does not require every repair to reduce the number of defects.

For the cyclic family on 128 vertices, take $x_i=1/13$. The required inequality holds because

$$ \frac1{64}\le\frac1{13}\left(\frac{12}{13}\right)^{12}. $$

The expected total resampling count is at most $128/12=32/3$. This counts event-resampling operations, not individual bit draws or the time spent scanning for violated edges. Each operation redraws seven bits, and the initial assignment uses 128 draws.

Proof sketch, with prerequisites omitted. Record overlapping resamplings in witness trees. Independence of the fresh variable samples bounds the probability of each compatible tree by a product of event probabilities. A branching-process calculation under the local-lemma condition bounds the sum over those trees. The witness-tree bookkeeping and branching-process proof are omitted; a successful short trace does not establish the theorem's expected bound.

Exercise. If ten events all have an admissible value $x_i=1/5$, what total resampling bound follows? Hint: add $x_i/(1-x_i)$. Solution: at most $10\cdot(1/4)=5/2$ in expectation. A particular run may take more than this average.

22.10 Janson inequalities, correlation inequalities, and concentration

Optional advanced elective. Independent coordinates can produce dependent configuration counts. Correlation inequalities control the direction of this dependence, while Janson inequalities control lower tails for particular monotone events. A small dependency degree by itself is not the only relevant structure.

In a product space of independent bits, an event is increasing if changing coordinates from 0 to 1 cannot destroy it. Presence of a triangle in a random graph is increasing in the edge-presence bits. Monochromaticity in a two-color assignment is not increasing: changing one bit of 000 to 1 destroys the event, while completing 111 creates it.

Harris correlation inequality. For increasing events $A,B$ in an independent-bit product space,

$$ \Pr(A\cap B)\ge\Pr(A)\Pr(B). $$

Two decreasing events also correlate nonnegatively; an increasing and a decreasing event correlate nonpositively. General refinements appear in Kalai, Keller, and Mossel, On the Correlation of Increasing Families.

Proof mechanism. More generally, increasing real functions have nonnegative covariance. Induct on the number of coordinates, conditioning on the last bit $Z$. The conditional covariances are nonnegative by induction. If $f_z=\mathbb E[f\mid Z=z]$ and $g_z=\mathbb E[g\mid Z=z]$, the remaining covariance is

$$ \Pr(Z=1)\Pr(Z=0)(f_1-f_0)(g_1-g_0)\ge0. $$

The covariance decomposition sums these two contributions. Taking indicators proves Harris; complementing one or both indicators yields the other directions. Independence of the underlying coordinates is essential to the induction.

Janson setup. Independently include each element of a finite ground set, with arbitrary inclusion probabilities. Fix nonempty subsets $S_1,\ldots,S_m$, and let $A_i$ be the event that every element of $S_i$ is included. Put $X=\sum_i\mathbf1_{A_i}$ and define

$$ \mu=\mathbb E X,\qquad \Delta=\sum_{\substack{i\ne j\\S_i\cap S_j\ne\varnothing}}\Pr(A_i\cap A_j). $$

This sum uses ordered pairs and excludes diagonal terms. With this convention, Janson inequalities give

$$ \Pr(X=0)\le\exp(-\mu+\Delta/2) $$

and, for $\mu\gt0$ and $0\le t\le\mu$,

$$ \Pr(X\le\mu-t)\le\exp\left(-\frac{t^2}{2(\mu+\Delta)}\right). $$

The primary paper Riordan and Warnke, The Janson inequalities for general up-sets gives these forms and extends their scope. We use the elementary subset-containment setup here. An unordered-pair definition would change the factor attached to $\Delta$.

Mechanism for the zero-count bound. Expose whether the events occur in an order. Under avoidance of earlier nonoverlapping events, $A_i$ retains its original probability. Harris bounds the joint occurrence of $A_i$ and an overlapping event after this decreasing conditioning. Subtracting the earlier overlapping intersections gives a lower bound on the next conditional occurrence probability. Multiplying the conditional avoidance probabilities and using $1-u\le e^{-u}$ yields the displayed exponent. The lower-tail extension uses an exponential-moment argument; its detailed proof is omitted and supplied by the cited paper.

Solved example. For triangles in $G(4,1/2)$, the ground elements are the six graph edges and each $S_i$ contains the three edges of a triangle. As in Section 22.5, $\mu=1/2$. All 12 ordered pairs of distinct triangles share an edge and have joint probability $1/32$, so $\Delta=3/8$. Therefore

$$ \Pr(X=0)\le e^{-1/2+3/16}=e^{-5/16}. $$

Harris applied to the four decreasing no-triangle events gives the lower bound $(7/8)^4$. Exact enumeration supplies a check:

$$ \left(\frac78\right)^4\le\frac{41}{64}=\Pr(X=0)\le e^{-5/16}. $$

Both inequalities hold but are not exact. Janson need not improve every second-moment estimate for a small instance; here Section 22.5 also gives $\Pr(X=0)\le5/7$.

Connection with concentration. Chernoff treats sums of independent indicators; Janson allows overlapping increasing configurations with a specified overlap correction. For a general function of independent bits, an exposure martingale may instead be suitable. In the cyclic 7-uniform example, changing one vertex bit affects at most seven monochromatic-edge indicators, so the bad-count function has coordinate influence at most seven. Azuma applies to its exposure martingale, but Janson's increasing-event assumption does not apply to those monochromaticity events as stated. Checking the event structure is part of choosing a theorem.

Exercise. Two triangles share only a vertex in $G(n,p)$. Do their events contribute to $\Delta$ when the ground elements are graph edges? Hint: compare the sets of edge coordinates. Solution: no. Their edge sets are disjoint, so the events are independent. Sharing one graph edge instead gives joint probability $p^5$ and contributes in each ordered direction.

Compare first moments, alterations, and a local-lemma construction

The comparison uses the cyclic 7-uniform hypergraph from Section 22.8. Its probability space is 128 independent fair vertex bits, and each bad event concerns seven specified coordinates. The methods share that model, but their conclusions differ. The optional concentration work explicitly checks whether the same event indicators satisfy the monotonicity hypotheses from Section 22.10.

Worked comparison. Each edge is monochromatic with probability $1/64$, and $\mathbb E X=2$. Every vertex has degree seven, giving the incidence check $128\cdot7=7\cdot128$.

The failure of the first test is not a nonexistence conclusion. The alternating assignment works, because the cycle length is even and every seven-position edge contains consecutive opposite bits, including at the wraparound.

Explicit alteration and resampling solutions. In the prescribed starting assignment, the only runs of seven equal bits begin at 0 and 64; their neighboring bits at 127,7,63,71 are 1. Everywhere else the original alternating pattern remains. Deleting vertices 0 and 64 removes those bad edges and retains 126 vertices with the original bits. Here an induced edge is retained only if all its original vertices remain; it is not shortened to the surviving intersection.

Alternatively, retain all vertices and use these possible fresh seven-bit draws in cyclic order:

These assignments can be checked by scanning each consecutive block, with indices reduced modulo 128. They are one possible Moser–Tardos execution, not a claim that every run takes two repairs. Each fresh specified block has positive sampling probability. The resampling theorem provides the general expected-cost guarantee, while the scan certifies this particular witness.

A reproducible implementation outline. Store the 128 bits and, for each start $i$, test whether its seven cyclic bits all agree. While a defect remains, choose one bad start by a specified rule, independently redraw its seven coordinates, and rescan the affected edges or all edges. Record the chosen start and fresh values. Stop only after verifying that the bad-start list is empty. An iteration limit may be used for an experiment, but reaching it means the run is unfinished, not that no coloring exists.

Application. Suppose vertices are tasks and each hyperedge is a group that must not all receive the same one of two resource pools. A weak two-coloring meets all those group constraints. Alteration can model postponing a few tasks; local resampling instead reallocates a violated group. The probabilistic proof requires that the stated constraints capture the intended problem: pairwise incompatibilities, load limits, or unequal assignment probabilities would need their own model and event calculations.

Optional concentration extension. For the same family, construct the exposure martingale of $X$. Its 128 increments are bounded in absolute value by seven, so Azuma gives

$$ \Pr(|X-2|\ge t)\le2\exp\left(-\frac{t^2}{2\cdot128\cdot49}\right). $$

This bound can be very weak at small $t$ and does not replace the local-lemma argument for avoiding every event. In contrast, for triangle-presence counts in a random graph, use increasing edge-presence events and compute $\mu,\Delta$ before applying Janson. These two models both use independent bits, but their event structures call for different tools. Further experiments may vary uniformity and overlap degree; report which sufficient criterion actually holds rather than labeling an unverified parameter regime impossible or unresolved.