Percolation III: Some Lemmas

The next chapter of Bollobas is a collection of probabilistic tools used throughout the book; this post presents two of these results that will be key to our proof of the Harris-Kesten theorem. Both of these results are set in the framework of weighted hypercubes, which we now introduce.

Take a set {S} and its power set {\mathcal{P}(S)}. This power set can be identified with the set of functions {f: S\rightarrow \{0,1\}} by identifying {A\in \mathcal{P}(S)} with its characteristic function. In the case where {S} is finite (and this is the case we care about), we can think of {S} as {\{1,\cdots, n\}} and {\mathcal{P}(S)=\mathcal{P}(n)} as the cube {Q^n=\{0,1\}^n.} This cube is the set of binary sequences of length {n}, where a subset {A\subset S} is associated to a sequence that has a 1 in position {i} if {i\in A} and a 0 otherwise.

More geometrically, we can think of {Q^n} as a graph whose vertices are {\mathcal{P}(n)}. Two sets {A, B} are connected in this graph if {|A\Delta B|=1} (i.e. {A} and {B} differ at one entry in their sequences). Put yet another way, if {\mathbf{a}, \mathbf{b}\in \{0,1\}^n} are two vertices, they are connected if {a-b=\pm \mathbf{e}_i}, where {\mathbf{e}_i} is a standard basis vector. We can make {Q^n} a directed graph by saying the edge {\mathbf{a}\mathbf{b}} is oriented from {\mathbf{a}} to {\mathbf{b}} if {\mathbf{b}-\mathbf{a}=\mathbf{e}_i}. We write this as {\mathbf{a}\leq \mathbf{b}}.

Now, shifting gears, the points of {Q^n} are associated with the outcome of a sequence of {n} coin tosses. If {\mathbf{p}=(p_1,\cdots, p_n)} is the sequence of probabilities of success for these {n} coin tosses, then { \mathbf{p}} induces a natural probability measure on {Q^n}.

For example, if {\mathbf{p}=(0.5,\cdots, 0.5)} we obtain the uniform measure, and if {\mathbf{p}=(p,\cdots, p)}, we obtain {\mathop{\mathbb P}(A)=p^{|A|}(1-p)^{n-|A|}}. We write {Q_p^n} for the cube with this measure, and it is equivalent to the standard percolation models.

We write {Q_{\mathbf{p}}^n} for the probability space {(\mathop{\mathbb P}_{\mathbf{p}}, Q^n)} and distinguish two kinds of events. A subset {U\subset Q^n} is an up-set if {a,b\in Q^n, a\leq b\implies b\in U}. Similarly, {U} is a down-set if {a,b \in Q^n, a\geq b\implies b\in U}. (Keep in mind that {U} is a subset of {Q^n}, which is identified with {\mathcal{P}(S)}, so {a, b} are subsets of the original set {S}.) The corresponding events are referred to as increasing and decreasing respectively.

With that set up out of the way, we can state our first lemma.

1. Harris’s Lemma

This lemma is the intuitive fact that increasing events are positively correlated. Let’s do a bit more set up.

For a set {A\subset Q^n} and {t=0,1} we can define

\displaystyle A_t=\{(a_i)_{i=1}^{n-1}\mid (a_1,\cdots, a_{n-1}, t)\in A\}\subset Q^{n-1}.

If {A} is an up-set, {A_0\subset A_1}, and if {A} is a down-set, {A_1\subset A_0} (because {A_1, A_0} always differ at only one position, so their difference is always a basis vector, so it’s just a matter of sign).

If we write {\mathop{\mathbb P}} for the probability measure on both {Q_{(p_1,\cdots, p_n)}^n} and {Q_{(p_1,\cdots, p_{n-1})}^{n-1}}, we have

\displaystyle \mathop{\mathbb P}(A)=(1-p_n)\mathop{\mathbb P}(A_0)+p_n\mathop{\mathbb P}(A_1).

Finally, the result:

Lemma 1. Let {A, B} be subsets of {Q_{\mathbf{p}}^n}. If they are both up-sets or both down-sets, then {\mathop{\mathbb P}(A\cap B)\geq \mathop{\mathbb P}(A)\mathop{\mathbb P}(B)}. If {A} is an up-set and {B} is a down-set, then {\mathop{\mathbb P}(A\cap B)\leq \mathop{\mathbb P}(A)\mathop{\mathbb P}(B)}.

(This implies the correlation statement, since the first condition rearranges to {\mathop{\mathbb P}(A\mid B)\geq \mathop{\mathbb P}(A)} and similarly for the second.)

Proof: We induct on {n}. The case {n=1} is trivial, so suppose the result holds for {n-1}.

If {A} and {B} are both up-sets or both down-sets, then either {A_0\subset A_1} and {B_0\subset B_1} or {A_1\subset A_0} and {B_1\subset B_0}. This means that

\displaystyle (\mathop{\mathbb P}(A_0)-\mathop{\mathbb P}(A_1))(\mathop{\mathbb P}(B_0)-\mathop{\mathbb P}(B_1))\geq 0.

Our argument will rely on the equivalent fact that

\displaystyle \mathop{\mathbb P}(A_0)\mathop{\mathbb P}(A_1)+\mathop{\mathbb P}(B_0)\mathop{\mathbb P}(B_1)\geq \mathop{\mathbb P}(A_1)\mathop{\mathbb P}(B_0)+\mathop{\mathbb P}(A_0)\mathop{\mathbb P}(B_1).

Now we write

\displaystyle \mathop{\mathbb P}(A\cap B)=(1-p_n)\mathop{\mathbb P}(A_0\cap B_0)+p_n \mathop{\mathbb P}(A_1\cap B_1)

which is

\displaystyle \geq (1-p_n)\mathop{\mathbb P}(A_0)\mathop{\mathbb P}(B_0)+p_n\mathop{\mathbb P}(A_1)\mathop{\mathbb P}(B_1).

We cleverly rewrite this as

\displaystyle (1-p_n)^2\mathop{\mathbb P}(A_0)\mathop{\mathbb P}(B_0)+p_n^2\mathop{\mathbb P}(A_1)\mathop{\mathbb P}(B_1)+(1-p)p(\mathop{\mathbb P}(A_0)\mathop{\mathbb P}(B_0)+\mathop{\mathbb P}(A_1)\mathop{\mathbb P}(B_1)),

(yes, they’re really equal!) and use our earlier inequality to see that this is

\displaystyle \geq (1-p_n)^2\mathop{\mathbb P}(A_0)\mathop{\mathbb P}(B_0)+p_n^2\mathop{\mathbb P}(A_1)\mathop{\mathbb P}(B_1)+(1-p)p(\mathop{\mathbb P}(A_0)\mathop{\mathbb P}(B_1)+\mathop{\mathbb P}(A_1)\mathop{\mathbb P}(B_0).

But this last line is equal to

\displaystyle \left[(1-p_n)\mathop{\mathbb P}(A_0)+p_n\mathop{\mathbb P}(A_1)\right]\left[(1-p_n)\mathop{\mathbb P}(B_0)+p_n\mathop{\mathbb P}(B_1)\right]=\mathop{\mathbb P}(A)\mathop{\mathbb P}(B),

so we conclude.

From this first piece, the other inequality follows easily: if {A} is an up-set and {B} is a down-set, then {B^c} is an up-set, so

\displaystyle \mathop{\mathbb P}(A\cap B)\leq\mathop{\mathbb P}(A)-\mathop{\mathbb P}(A\cap B^c)\leq \mathop{\mathbb P}(A)-\mathop{\mathbb P}(A)\mathop{\mathbb P}(B^c),

from the previous result. This then is

\displaystyle \mathop{\mathbb P}(A)-\mathop{\mathbb P}(A)(1-\mathop{\mathbb P}(B))=\mathop{\mathbb P}(A)\mathop{\mathbb P}(B),

as desired. \Box

2. The Russo-Margulis Lemma

Take an event {A} in the weighted cube {Q_{\mathbf{p}}^n}. We want to understand how {\mathop{\mathbb P}(A)} varies with {\mathbf{p}}.

For a point {\omega\in Q^n}, we say that entry {i}, {\omega_i}, is pivotal for {A} if only one of {\omega} and {\tilde{\omega}} are in {A}, where {\tilde{\omega}} is {\omega} with the entry at {\omega_i} flipped. Then, we define the influence of entry {i} as

\displaystyle \beta_i(A)=\mathop{\mathbb P}(\omega_i\text{ is pivotal for } A)=\mathop{\mathbb P}(\{\omega\mid \omega_i\text{ is pivotal for }A\}).

Lemma 2. Let {A} be an increasing event in {Q_{\mathbf{p}}^n} where {\mathbf{p}=(p_1,\cdots, p_n)}. Then

\displaystyle \frac{\partial}{\partial p_i} \mathop{\mathbb P}(A)=\beta_i(A)\implies \frac{d}{dp}\mathop{\mathbb P}(A)=\sum_{i=1}^n \beta_i(A).

Proof: Assume without the loss of generality that {i=n}. If we have {\mathbf{x}=(x_1,\cdots, x_k)\in Q^k} for {k\leq n}, write {\mathbf{p}^{\mathbf{x}}} for the probability of {x} in the measure induced by {Q_{\mathbf{p}}^n} on {Q^k}. In particular, if {k=n}, then {\mathbf{p}^{\mathbf{x}}=\mathop{\mathbb P}(\{x\})}.

Also, for {\mathbf{x}\in Q^{n-1}}, let {\mathbf{x}_+} and {\mathbf{x}_-} be the events formed by extending {\mathbf{x}} with a 1 or 0 in the last slot, respectively. We have

\displaystyle \mathbf{p}^{\mathbf{x}_+}+\mathbf{p}^{\mathbf{x}_-}=\mathbf{p}^{\mathbf{x}}

by construction.

Now take an up-set {A}, and let {A_a} be the set of {\mathbf{x}\in Q^{n-1}} such that {\mathbf{x}_+} and {\mathbf{x}_-} are both in {A}, and {A_b} be the same set but such that only {\mathbf{x}_+} is. Then,

\displaystyle \mathop{\mathbb P}(A)=\sum_{\mathbf{x}\in A_a} \left(\mathbf{p}^{\mathbf{x}_+}+\mathbf{p}^{\mathbf{x}_-}\right)+\sum_{\mathbf{x}\in A_b}\mathbf{p}^{\mathbf{x}_+},

which, by our earlier observation, becomes

\displaystyle \sum_{\mathbf{x}\in A_a} \mathbf{p}^{\mathbf{x}}+p_n\sum_{\mathbf{x}\in A_b} \mathbf{p}^{\mathbf{x}}.

It’s clear now that

\displaystyle \frac{\partial}{\partial p_n} \mathop{\mathbb P}(A)= \sum_{\mathbf{x}\in A_b} \mathbf{p}^{\mathbf{x}},

but since {A_b} is exactly the set of {\mathbf{x}} for which {n} is pivotal, this sum is {\beta_n(A)}. \Box

That proof is a notational mess, but the idea is simple: think of an element of {Q^n} as an element of {Q^{n-1}}, plus a bit of information that tells you whether it is pivotal, and then use this decomposition to directly take the derivative.

Of course, this result is only useful if you actually understand things about the {\beta_i(A)}. I won’t prove it, but we have this bound: if {\mathop{\mathbb P}(A)=t} and {\beta_i(A)\leq \delta} for each {i}, then

\displaystyle \sum_{i=1}^n \beta_i(A)\geq ct(1-t)\log(1/\delta).

This bound will be the second ingredient necessary in our proof of Harris-Kesten, which we will finally begin with in the next post.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s