1 Percolation (on Z^{2} and Z^{d})- part 1

The process of percolation was introduced by Broadbent and Hammersley in 1957, as a model for flow through porus rock:

1.1 Definitions and basic facts

Definition. (bond) Percolation on a graph G is a random subgraph H_{p} of G attained by keeping each edge of G with probability p, independently of all other edges. Sometimes we will call the edges in H_{p} open, while the edges in G H_{p} will be called closed.

The random subgraph (H_{p})percolates (or the event of percolation is said to occur) if it contains an infinite connected cluster.

Doing the same process to the vertices of G is called site percolation A lot of applications in Physics, disease spreading, networks or a simpli-

fication or tool for studying more complex systems (ising model etc..)

From now on we will concentrate on Z^{d}, and even Z^{2} unless otherwise stated.

The basic question we will want to answer is when does percolation occur. i.e. when is there an infinite cluster. Claim. The following is true for Z^{d} (and actually for any connected graph G):

1. Percolation is a 0 − 1 event.

2. Percolation occurs with probability 1 iff θ(p) > 0.

3. θ(p) is an increasing function of p, and the probability for percolation is increasing in p.

4. There exists a critical probability p_{c} (depending on the graph), 0 ≤ p_{c} ≤ 1 s.t. for any p < p_{c} no percolation occurs (a.s.) and for any p > p_{c} percolation occurs (a.s.).

Proof. 1. Percolation is a tail event (i.e. changing a finite number of edges (from open to close or vice versa) does not change whether or not percolation occurs), and by Kolmogorov’s 0-1 law, any tail event has probability 0 or 1.

2. The probability of percolation is at least θ(p), so if θ(p) > 0 then by the previous clause percolation occurs with probability 1. If θ(p) = 0 then by the probability of percolation is bounded by a countable union of 0 probability events and is therefore 0.

3. Couple using uniform variables.

4. At p = 0 no percolation occurs, at p = 1 percolation does occur. define p_{c} = inf_{p}ℙ(percolation > 0). The rest follows from monotonicity.

Remark: We will show that in Z^{2}, no percolation occurs at p_{c}. This is not always the case (example?)

Examples: d-regular trees. (No percolation at p_{c} = \frac{1}{d−1}) Next we will prove that p_{c} is non trivial (i.e. 0 < p_{c} < 1)

Lemma. \frac{1}{3} ≤ p_{c}(Z^{2}) ≤ \frac{2}{3}

Proof. 1. p_{c} > \frac{1}{3} Let C(x) denote the connected component of vertex x. Then if percolation occurs, then with probability ≥ θ(p) there is an open self avoiding path of length n from the origin. The number of self avoiding paths of length n from 0 is at most 4 ∗ 3^{n}, and each such path is open with probability p^{n}. Therefore the expected number of self avoiding open paths of length n from 0 is ≤ 4 ∗ 3^{n}p^{n} and this converges to 0 if p < \frac{1}{3}, ensuring θ(p) = 0. Therefore p_{c} ≥ \frac{1}{3}

2. p_{c} < \frac{2}{3}:

Dual lattice L^{2∗}: Dual of a planar graph, explicit description. Edge open iff croses an open edge. Closed if crosses a closed edge of L^{2}. It is easy to see that L^{2} ≈ L^{2∗} (isomorphism). If the connected component of 0 is finite, then there exists a closed circuit in the dual lattice around 0. In a similar manner, the union of the connected components of all vertices in the box [−n, n]x[−n, n] is finite iff there exists a circuit of closed edges in the dual lattice circling [−n, n]x[−n, n]. Each such a path is of length ≥ n, and there are at most m ∗ 3^{m} such circuits of length m. Each circuit of length m is closed with probability (1 − p)^{m}, so the expected number of closed circuits around [−n, n] × [−n, n] in the dual lattice is ≤ ∑_{m} = n^{∞}m ∗ (3(1 − p))^{m} and this converges to 0 as n → ∞ for any p ≥ \frac{2}{3}. So there is an n for which there are no closed circuits around [−n, n] × [−n, n] in the dual lattice with positive probability. And by translation invariance θ(p) > 0 for any p > \frac{2}{3}.

Remark: p_{c}(Z^{d}) ≤ p_{C}(Z^{2}) (and actually, a strict inequality holds) The proof of the lower bound can be adapted easily to give a lower bound on p_{c}(Z^{d}). so 0 < p_{c}(Z^{d}) < p_{c}(Z^{2}) for d ≥ 2.

Exercise: Show that p_{c}(Z^{4}) < p_{c}(Z^{2}). exercise: Build a graph with p_{c} = 0. (p_{c} = 1 is easy). exercise*: Build a graph that has percolation at p_{c}. Hint - use galton-watson trees as building blocks.

remark: Conjecture: Any vertex-transitive graph with p_{c} < 1 does not percolate at p_{c}. Known for Z^{2} and Z^{d} for d ≥ 19 open for Z^{3}.

1.2 Bond and Site percolation

Theorem. For any bounded degree graph G we have p_{c}(bond) ≤ p_{c}(site).

Proof. We define a coupling between bond and site percolation (for a given p) such that the C_{bond}(0) ⊃ C_{site}(0) for each instance of the coupling.

Coupling: Exploration process.

1.3 Uniqueness of the infinite component in Z^{d}

We will show the proof of Burton and Keanes (1989)

Proof. Stage 1: Show that for any 0 < p < 1 the number of infinite components is constant (a.s.). proof: N_{p}(w) is translation invariant, and any translation invariant function on Ω_{p}(Z^{d}) is a.s. constant.

Stage 2: Assume N_{p}(x) ≡ c a.s. then c ∈ 0, 1, ∞.

Proof: If there are two or more infinite clusters, then there is a finite box B(n) s.t. with positive probability q B(n) intersects 2 or more infinite clusters. Then, changing the configuration of edges inside B(n) can connect two components, and happens with positive bounded below probability, so the number of connected components is not constant, contradicting (1).

Stage 3: We assumed p > p_{c} so N_{p} ≥ 1, so it remains to show N_{p} ≠ ∞.

Assume N_{p} ≡ infty. We define the notion of a trifurcation point: (drawing:)

(a): Let T_{x} denote the event that x is a trifurcation point then P (T_{x}) > 0 proof: Again take big enough box. It intersects 3 infinite components. with positive probability. Changing the configuration inside can insure 0 is a trifurcation point.

(b):Let B(n) denote the d-dimensional box of length n. Then the expected number of trifurcation points inside B(n) is n^{d} ∗ P (T_{x}) i.e. grows proportional to n^{d}.

(c): We will show that the number of trifurcation points in B(n) cannot exceed |∂B(n)| ≤ dn^{d−1} (Boundary) contradicting (b).

(d): It is enough to show that for any infinite component K intersecting B(n), the number of trifurcation points on B(n) ∩ K is bounded by |∂B(n) capK|.

(e) Compatible partitions, compatible family of partitions

lemma: If P is a compatible family of partitions of Y then |P | ≤ |Y | − 2. proof: induction on Y. clear for |Y | = 3 for |Y | = n + 1 divide

(f): (Drawing) : The trifurcation points of K ∩ B(n) induce a family of compatible partitions of K ∩ ∂B(n).

Conclusion - contradiction. → N_{p} ≡ 1 a.s.

remark: In trees there are an infinite number of connected components.

1.4 Useful tools and inequalities

Let Ω = {0, 1}^{Ł^{d}} denote the space of all possible edge configurations on L^{d}. i.e. in the configuration w ∈ Ω the edge e ∈ Ł^{d} is open iff w(e) = 1, and closed iff w(e) = 0.

We denote by Ω_{p} the space endowed with the product measure where each edge e is open with probability p, independently of all other edges. (We could also consider other product measures, where each edge is open with a different probability p_{e} etc..)

We impose a partial order on Ω by setting ω ≤ ω′ ⟺ ω(e) ≤ ω′(e) ∀e ∈ Ł^{d}. (i.e. every edge open in w is open in w′ as well).

An event A is called (monotone) increasing if I_{A}(w) ≤ I_{A}(w′) whenever w ≤ w′. (Where I_{A} is the indicator function of A) We call A decreasing if it’s complement Ā is increasing.

More generally, a random variable N on Ω is called increasing if N(w) ≤ N(w′) whenever w ≤ w′. (and N is called decreasing if −N is increasing)

Examples: The existence of an open path from x to y is an increasing event. The number of such open paths is an increasing function.

Claim. If N is an increasing function on Ω, A an increasing event, and p_{1} ≤ p_{2} then

1. E_{p_{1}}(N) ≤ E_{p_{2}}(N). Assuming these mean values exist.

2. ℙ_{p_{1}}(A) ≤ ℙ_{p_{2}}(A)

Proof. standard coupling using uniform variables.

FKG(Harris lemma) The following useful theorem, proved in various forms by harris (1960) and others (FKG), deals with the positive correlation between monotone increasing events.

Theorem. 1. Let X, Y be two increasing (or decreasing) random variables on Ω_{p} such that E_{p}(X^{2}) < ∞ and E_{p}(Y^{2}) < ∞ then

E_{p}(XY) ≥ E_{p}(X)E_{p}(Y)

2. If A and B are increasing (or decreasing) events, then

P_{p}(XY) ≥ E_{p}(X)E_{p}(Y)

Proof. We will only prove (a) for random variables which depend only on a finite number of edges. Suppose X and Y depend only on the states of e_{1}, .., e_{n}. We proceed by induction on n. Step 1: Suppose n = 1. Then X and Y depend only on w(e_{1}), which is 1 with probability p and 0 with probability 1 − p.

Step 2: Assume the result holds for all n < k, and assume X and Y depend only on w(e_{1}), ..., w(e_{k}). then

E_{p}(XY) = E_{p,w(e_{1}),...,w(e_{k−1})}(E_{p,w(e_{k})}(XY | w(e_{1}), ..., w(e_{k−1}))) ≥

≥ E_{p,w(e_{1}),...,w(e_{k−1})}(E_{p,w(e_{k})}(X | w(e_{1}), ..., w(e_{k−1}))E_{p,w(e_{k})}(Y | w(e_{1}), ..., w(e_{k−1})))

Since given w(e_{1}), ..., w(e_{k−1}) X and Y are increasing in the single random variable w(e_{k}). Now E_{p,w(e_{k})}(X | w(e_{1}), ..., w(e_{k−1})) is an increasing function of the states of e_{1}, ..., e_{k−1}, (and same for Y), so by the induction hypothesis

E_{p}(XY) ≥ E_{p,w(e_{1}),...,w(e_{k−1})}(E_{p,w(e_{k})}(X | w(e_{1}), ..., w(e_{k−1})))
×E_{p,w(e_{1}),...,w(e_{k−1})}(E_{p,w(e_{k})}(Y | w(e_{1}), ..., w(e_{k−1}))) =
= E_{p}(X)E_{p}(Y)

Proving the case when X and Y depend on infinitely many edges requires approximating X and Y by variables depending only on a finite number of edges, and using a convergance theorem for martingales with bounded variance.

(b) follows from (a) by taking indicator functions.

remarks:

1. Since the intersection of increasing events is an increasing event, we

can conclude

P_{p}(⋂_{i=1}^{k} A_{i}) ≥ ∏_{i=1}^{k} P_{p}(A_{i})

for increasing events A_{i}.

2. The proof works for any product measure on any countable set (We can use a different p_{e} for each edge e ∈ G, and any countable graph G)

3. The theorem actually holds in a much wider setting.

4. VERY USEFUL

1.5 The BK inequality

The FKG inequality gave us positive correlation between increasing events. Sometimes we will want an inequality in the opposite direction, giving us an upper bound on the probability of two increasing events happening at once. It turns out the correct approach is instead of looking at A ∩ B, to look at a new event, the disjoint occurrence of A and B, denoted A ∘ B. In the case of bonds percolation and paths, the disjoint occurrence of paths between a and b, and between x and y just means the existence of two edge disjoint paths one joining a and b and one joining x and y. The BK inequality will then give ℙ(A ∘ B) ≤ P (A)P (B). We will now formalize and extend this definition, and state and proof the relevant inequality.

We restrict ourselves to a finite state space Ω = {0, 1}^{m}.

Definition. Given a configuration w ∈ Ω and a subset I ⊂ [m], we define the cylinder [w]_{I} by [w]_{I} = {w′ ∈ Ω : w′(i) = w(i) ∀i ∈ I}.

Definition. Given events A, B ⊂ Ω we define the ”disjoint occurrence” of A and B by

A ∘ B = {w ∈ Ω : ∃I ⊂ [m], [w]_{I} ⊂ A, [w]_{I^{c}} ⊂ B}

Theorem (BK inequality, after Kesten and Van den Berg, 85). Let m ∈ ℕ, let Ω = {0, 1}^{m}, endowed with the product measure ℙ_{p}, then for any increasing events A, B ⊂ Ω

ℙ_{p}(A ∘ B) ≤ ℙ_{p}(A)ℙ_{p}(B)

Proof. (We follows Dana Randall’s lecture notes) Let Ω^{2} = Ω×Ω , and endow it with the probability measure ℙ^{2} = P_{p} × P_{p}. For an element < x, y >∈ Ω^{2}, < x, y >=< x_{1}, .., x_{m}; y_{1}, .., y_{m} >, we define < x, y >_{0}=< x, y >=< x_{1}, ..., x_{m}; y_{1}, ..., y_{m} > < x, y >_{1}=< y_{1}, x_{2}, ..., x_{m}; x_{1}, y_{2}, ..., y_{m} > < x, y >_{k}=< y_{1}, y_{2}, .., y_{k}, x_{k+1}, .., x_{m}; x_{1}, x_{2}, ..x_{k}, y_{k+1}, ..., y_{m} > for any k ≤ m.

We define events A′, B′_{k} for 0 ≤ k ≤ m as follows: < x, y >∈ A′ ⟺ x ∈ A. ∀k ≤ m < x, y >∈ B′_{k} ⟺ [< x, y >_{k}]_{[m]} ∈ B. (i.e. iff < y_{1}, ..., y_{k}, x_{k+1}, ..., x_{m} >∈ B) Then the events A′ ∘ B′_{k} are defined by < x, y >∈ A′ ∘ B′_{k} ⟺ ∃I_{1}, I_{2} ⊂ [m], I_{1} ∩ I_{2} ∩ {k + 1, ..., m} = ∅ such that [< x, y >]_{I_{1}} ∈ A′ (i.e. [x]_{I_{1}} ⊂ A) and [< x, y >]_{I_{2}} ∈ B′_{k} (i.e. [< y_{1}, .., y_{k}, x_{k+1}, ..x_{m} >]_{I_{2}} ∈ B).

Remark. Note connection to edge splitting!!! If A is the event of a path between u and v, and B the event of a path between α and β, then < x.y >∈ A′∘B′_{k} iff there exist disjoint paths connecting u to v and α to β after splitting the first k edges.

We make 2 observations:

1. < x, y >∈ A′ ∘ B′_{m} ⟺ x ∈ A and y ∈ B. But since x and y share no bits together, we get that ℙ^{2}(A′ ∘ B′_{m}) = ℙ_{p}(A)ℙ_{p}(B).

2. < x, y >∈ A′ ∘ B′_{0} ⟺ x ∈ A ∘ B,so ℙ^{2}(A′ ∘ B′_{0}) = ℙ(A ∘ B).

So if we can show that ℙ^{2}(A′ ∘ B′_{k−1}) ≤ ℙ^{2}(A′ ∘ B′_{k}) for any 1 ≤ k ≤ m, we would reach the desired inequality.

To prove this, we define e_{k} to be the vector with 1 in the k’th place, and 0 everywhere else, and define ⊕ to be bitwise xor (symmetric difference) between configurations.

We will prove the inequality ℙ^{2}(A′ ∘ B′_{k−1}) ≤ ℙ^{2}(A′ ∘ B′_{k}) by constructing a function Φ : (A′ ∘ B′_{k−1}) → (A′ ∘ B′_{k}), which will be 1 − 1 and measure preserving (in Ω^{2}, ℙ^{2}).

For < x, y >∈ (A′ ∘ B′_{k−1}) we define Φ(< x, y >) according to one of two cases:

Case 1: < x, y >∈ (A′ ∘ B′_{k}). In this case we simply define Φ(< x, y > ) =< x, y >. Note that if x_{k} = 0, or x_{k} = y_{k} = 1 then this is the case.

Case 2: < x, y >∉ (A′∘B′_{k}). This implies x_{k} = 1, y_{k} = 0. By the definition of (A′ ∘B′_{k−1}) there exist I_{1}, I_{2} ⊂ [m] such that I_{1} ∩I_{2} ∩{k, ..., m} = ∅ and [< x, y >]_{I_{1}} ⊂ A′ and [< x, y >]_{I_{2}} ⊂ B′_{k−1}. Then k ∈ I_{2} (otherwise, exchanging x_{k} and y_{k} would not change membership in B), and therefore k ∉ I_{1}. So < x ⊕ e_{k}, y ⊕ e_{k} >∈ (A′ ∘ B′_{k}). We define Φ(< x, y >) =< x ⊕ e_{k}, y ⊕ e_{k} >.

It is easy to see that Φ is 1−1 and measure preserving, so we are done.

Remark. The inequality actually holds for any events, not just increasing. Riemer proved this in 1996. In that formulation it also generalizes the FKG inequality for product measures.

1.6 Russo’s Formula

Given an increasing event A, how does it’s probability change when we change p? We already know ℙ_{p}(A) is non-decreasing in p. One way to approach the problem, is to think what happens when we change p by a small amount. For this it is best to use the standard uniform variable coupling, that allows us to couple percolation with various probabilities. (put a uniform (0, 1) r.v. U_{e} on each e ∈ G, and for given p call the edge open if U_{e} ≤ p). We give an ”informal” idea: Given a configuration of the uniform underlying space, when we change p by a very small amount δ, (and the space state is finite), with high probability we will add at most 1 edge. This edge will change the event of A happening only if the edge added is essential for A. Thus we will get

ℙ_{p+δ}(A) − ℙ_{p}(A) ≈ δ ∑_{e} ℙ_{p}(e is ”essential” for A)

Dividing by δ and taking the limit will give

\frac{∂}{∂p}ℙ_{p}(A) = ∑_{e} ℙ_{p}(e is ”essential” for A)

We will next formalize and prove this statement.

Definition. An edge e is called pivotal for an event A and a configuration w ∈ Ω if I_{A}(w) ≠ I_{A}(w′) where w′(f) = w(f)∀f ≠ e and w′(e) = 1 − w(e). i.e. If changing w(e) changes the event of A happening.

Note that if A is an increasing event, and e is pivotal for (A, w) then A does not occur when e is closed, and does occur when e is open. (and the rest of the edges remain unchanged)

Theorem (Russo’s Formula). Let A be an increasing event defined in terms of the states of only finitely many edges of Ł^{d},then

\frac{∂}{∂p}ℙ_{p}(A) = E_{p}(N(A))(= ∑_{e} ℙ_{p}(e is pivotal for A))

where N(A) is the number of edges which are pivotal for A.

Proof. Let M = {e_{i}}_{i=1}^{m} be the (finite) set of edges on which A depends, and let {U_{e}}_{e∈M} be i.i.d. uniform variables. For a given set of probabilities ρ = {ρ(e)}_{e∈M} we construct a configuration w_{ρ} ∈ Ω = {0, 1}^{M} by letting w(e) = 1 if U_{e} ≤ ρ(e), and w_{ρ}(e) = 0 otherwise. Writing ℙ_{ρ} for the probability measure on Ω where the state of the edge e is open with probability ρ(e), we have

ℙ_{ρ}(A) = ℙ(w ∈ A)

as usual. Now we will change the probabilities on one edge at a time: Choose an edge f ∈ M and define ρ′ by ρ′(e) = ρ(e) for e ≠ f and ρ′(f) = p′. thus ρ and ρ′ differ only on one edge at most. Now if ρ(f) ≤ ρ(f) then

ℙ_{ρ′}(A) − ℙ_{ρ}(A) = ℙ(w_{ρ} ∉ A, w_{ρ′} ∈ A) =
= (ρ′(f) − ρ(f))ℙ_{ρ}(f is pivotal for A)

Dividing by ρ′(f) − ρ(f) and taking the limit as ρ′(f) − ρ(f) → 0 gives

\frac{∂}{∂ρ(f)}ℙ_{ρ}(A) = ℙ_{ρ}(f is pivotal for A)

Changing the probability of each edge e_{i} from p to p + δ one at a time, and taking a limit gives(using the chain rule) :

\frac{∂}{∂p}ℙ_{p}(A) = ∑_{i=1}^{m} \frac{∂}{∂p(e_{i})}ℙ_{ρ}(A)|_{ρ≡p} =

= ∑_{i=1}^{m} ℙ_{p}(e_{i} is pivotal for A) = E_{p}(N(A))

Corollary. If A is increasing and depends only on m edges, then for any 0 < p1 ≤ p_{2}

ℙ_{p_{2}}(A) ≤ (\frac{p_{2}}{p_{1}} )^{m}ℙ_{p_{1}}(A)