Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 214 (Percolation and Random Walks on Graphs)

For bond percolation, the Harris-FKG inequality states that any two increasing events $A,B$ satisfyThe same inequality holds for two decreasing events, either by reversing the coordinate order or by taking complements in the two-event identity. Intersections of decreasing events are decreasing events, so induction givesWrite $a={\mathbb{P}}_p(A_1)=\cdots ={\mathbb{P}}_p(A_n)$ and $u={\mathbb{P}}_p({\bigcup }_j{A}_j)$. Then $1-u\ge (1-a{)}^n$. Taking the nonnegative $n$-th root and rearranging yields the square-root trick for positively associated events:No independence among the events is needed.

Put $I=\{x:|C(x)|=\infty \}$, the union of all infinite percolation clusters. Since $p>p_c$, the percolation probability $\theta (p)$ is positive. The translation ergodicity of Bernoulli percolation makes $\{I\ne \varnothing \}$ a zero-one event; it has positive probability because ${\mathbb{P}}_p(0\in I)=\theta (p)>0$, hence it occurs almost surely.

Let $D_m=\{B(m)\cap I\ne \varnothing \}$. These events increase to $\{I\ne \varnothing \}$, so continuity from below of a measure gives ${\mathbb{P}}_p(D_m)\to 1$. On $D_m$, some vertex of $B(m)$ has an infinite open path in a graph. For every $N\ge m$, the segment up to its first visit to $\partial B(N)$ lies entirely in $B(N)$. Thus even with this restriction on the connecting path in a graph,This proves the requested uniformity and supplies the version needed for crossings later.

For each of the $2d$ coordinate faces $F$ of $B(N)$, define the increasing event $A_F(m,N)$ that an open path in a graph lying in $B(N)$ joins $B(m)$ to $F$. Their union is exactly the event of connection from $B(m)$ to $\partial B(N)$ within $B(N)$. The bond percolation law and the centered boxes are invariant under coordinate permutations and sign changes, so all $2d$ events have the same probability.

Apply the square-root trick for positively associated events from part (a), with $2d$ in place of the number of events. If ${\delta }_m=1-{\mathbb{P}}_p(D_m)$, part (b.i) gives, for every $N=m+n$,In particular this holds for the left and right faces, and it proves the stronger statement in which each connecting path in a graph stays inside the outer box.

We use the uniqueness of the infinite percolation cluster on ${\mathbb{Z}}^d$: for $p>p_c$, there is almost surely exactly one infinite percolation cluster, denoted $I$. Fix $m$ and let $N>m$. Two observations account for the possible distinct endpoints of the face connections.

First, the probability that some finite percolation cluster meeting $B(m)$ reaches $\partial B(N)$ tends to zero as $N\to \infty$. There are only finitely many vertices in $B(m)$, and each of their finite percolation clusters has finite radius; apply the union bound and continuity from above of a measure.

Second, all vertices of $I\cap B(m)$ are joined to one another inside $B(N)$ with probability tending to one. On each configuration, this is a finite set of vertices of one connected percolation cluster. Choose a finite open path in a graph from one such vertex to each of the others; the union of these finitely many paths is contained in some finite box. The assertion is vacuous if the set is empty.

By part (b.ii), each of the two face-connection events within $B(N)$ fails with probability at most ${\delta }_m^{1/(2d)}$. Outside the two exceptional events just described, their endpoints in $B(m)$ belong to $I$ and can be joined inside $B(N)$. Concatenating the left-face path, that joining path, and the right-face path produces a crossing of $B(N)$. ConsequentlyNow let $m\to \infty$. Since ${\delta }_m\to 0$,The order of limits matters: $m$ is fixed while the finitely many relevant percolation clusters are connected inside increasingly large boxes.

Write $N_m=|B(m)|$ and $\theta =\theta (p)>0$. By translation invariance and linearity of expectation,Let $r={\mathbb{P}}_p(R(m)\ge \theta N_m/2)$. Since $0\le R(m)\le N_m$, splitting the expectation at the threshold givesRearranging produces the slightly stronger estimateOnly the mean and boundedness of the random variable are used; independence of the vertex-membership events is unnecessary.

For $m\ge 1$, let $S_m$ be the set of vertices of $B(m)$ connected to $\partial B(m)$ by an open path in a graph using only edges of $B(m)$. Every infinite-cluster vertex of $B(m)$ belongs to $S_m$, by stopping an infinite open path in a graph at its first boundary visit. Hence the increasing eventhas probability at least $\theta (p)/2$ by part (a). Importantly, $E_m$ depends only on the edges with both endpoints in $B(m)$.

Open all $8m$ perimeter edges joining successive vertices of $\partial B(m)$. They form a cycle in a graph, and opening them joins every vertex of $S_m$ into one percolation cluster, containing the specified perimeter vertex $v_m=(m,0)$. The Harris-FKG inequality bounds the probability of this event together with $E_m$ below by $p^{8m}\theta (p)/2$.

Close all $8m+4$ edges in the edge boundary of $B(m)$. These edges are distinct from the internal edges already considered, so their states are independent of those events. The resulting percolation cluster of $v_m$ is finite, contained in $B(m)$, and has at least $|S_m|$ vertices. Therefore, by translating $v_m$ to the origin,For $n\ge 1$, choose $m=\lceil \sqrt{n/(2\theta (p))}\rceil$. Then the threshold is at least $n$, and $m\le (1+(2\theta (p){)}^{-1/2})\sqrt{n}$. Put $A=-\log p$ and $B=-\log (1-p)$; both are positive. The preceding lower bound is at least $e^{-c_1\sqrt{n}}$ with, for example,The construction modifies only order-$m$ boundary edges while trapping order-$m^2$ vertices, which explains the stretched exponential scale. Here $\mathbb{N}$ is interpreted as the positive integers; the proposed lower bound at $n=0$ would be false because $\theta (p)>0$.

Declare an edge of the planar dual graph open exactly when its crossed primal edge is closed. This dual bond percolation has parameter $q=1-p<1/2=p_c$, using the Harris-Kesten theorem. We use the standard exponential tail of subcritical cluster size: for some $K,a>0$, uniformly in the dual vertex $v$,This is decay of the number of vertices in the percolation cluster, not merely its radius.

On $\{|C|=n\}$, the geometric fact allowed in the paper supplies a simple dual cycle in a graph surrounding $C$, with length $\ell \ge \alpha \sqrt{n}$. Every crossed edge is in the edge boundary of $C$ and is therefore closed, so the dual cycle is open. Its $\ell$ distinct vertices lie in one dual percolation cluster of size at least $\ell$.

A dual cycle in a graph of length $\ell$ surrounding the origin has all its vertices within sup-norm distance $\ell +1$ of the origin: its coordinate spans are at most $\ell$, and the origin lies between each pair of extreme coordinates. There are at most $K_0(\ell +1{)}^2$ possible dual vertices there. The union bound over lengths and possible vertices yieldsfor some $K_1,b>0$, since a polynomial factor can be absorbed into a slower exponential decay.

To remove the constant prefactor for all $n\ge 1$, first choose $n_0$ so that the bound is at most $e^{-(b/2)\sqrt{n}}$ for $n\ge n_0$. For the remaining finitely many $n$, use ${\mathbb{P}}_p(|C|=n)\le 1-\theta (p)<1$ and chooseFor $1\le n<n_0$, the chosen $c_2$ ensures $e^{-c_2\sqrt{n}}\ge 1-\theta (p)$.

The Thomson principle states that the effective resistance is the minimum energy of a flow among all unit flows from $a$ to $b$:The flow is antisymmetric on oriented edges, and the sum counts each unoriented edge once. The Rayleigh monotonicity principle states that increasing edge resistances, including deleting edges by setting their resistance to infinity, cannot decrease the effective resistance. Decreasing resistances or identifying vertices cannot increase it.

Take a shortest path in a graph from $a$ to $b$, of length $d=d_G(a,b)$, and send one unit of flow along it, with zero flow on all other edges. Its energy of a flow is $d$ because each edge resistance is one. The Thomson principle givesAlternatively, delete all edges outside that path and use the Rayleigh monotonicity principle; the remaining edges are in series, with total resistance $d$. When $a=b$, both quantities are zero.

Choose a spanning tree $T$ of $G$, rooted at $a$. A depth-first traversal of a tree gives a deterministic closed walkthat traverses each edge of $T$ once in each direction and visits every vertex. Define stopping times $S_0=0$ andThe simple random walk is at $v_j$ at time $S_j$. All these hitting times have finite mean on the finite connected graph. By the Strong Markov property,The cover time is no larger than $S_{2(n-1)}$. Grouping the summands by the two traversals of each tree edge and applying the commute time identity givesThe effective resistances are measured in the original graph, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, soFor the one-vertex graph, the cover time is zero and the same bound is immediate.

Let $d=d_G(a,b)>0$, and for $i=1,\dots ,d$ putEach edge cutset ${\Pi }_i$ separates $a$ from $b$. Adjacent vertices have graph distances from $a$ differing by at most one. Hence an edge can cross at most one of these level boundaries, so the edge cutsets are pairwise edge-disjoint. Write $k_i=|{\Pi }_i|\ge 1$; then ${\sum }_i{k}_i\le |E|$.

The Nash-Williams inequality for unit conductances giveswhere the middle inequality is the Cauchy-Schwarz inequality. One can also derive the first inequality directly: every unit flow has signed net flux one through each ${\Pi }_i$, so its energy of a flow on that cut is at least $1/k_i$; sum over the disjoint cuts and use the Thomson principle.

Combining with the commute time identity yieldsThe case $a=b$ is trivial. A path graph, with $a,b$ its endpoints, attains equality.

Use the usual implicit convention that the infinite connected graph is a locally finite graph. This is needed for the simple random walk and the finite wired constructions to be defined. Choose finite vertex sets $V_1\subset V_2\subset \cdots$ exhausting $V$, with each induced subgraph $G[V_k]$ connected.

For the free uniform spanning forest, sample a uniform spanning tree of $G[V_k]$, using only the internal edges. Its limiting law on edge subsets of $G$ is the free uniform spanning forest measure:The limit is weak convergence of probability measures on $\{0,1{\}}^E$, equivalently convergence of every finite-edge event.

For the wired uniform spanning forest, form $G_k^{\mathrm{w}}$ by identifying every vertex outside $V_k$ to one boundary vertex ${\partial }_k$. Retain all edges with at least one endpoint in $V_k$, preserve parallel edges, and discard loops at ${\partial }_k$. Sample a uniform spanning tree of this finite multigraph and restrict it to the original internal edges. The limiting law isFor each fixed finite set of edges the restriction is unambiguous once $k$ is large. The standard exhaustion theorem guarantees that both limits exist and do not depend on the chosen connected exhaustion. Both are random spanning forests; despite their names, they need not be connected.

Fix a root $r$. On a recurrent graph, a simple random walk started at any vertex hits $r$ almost surely. Run Wilson's algorithm with root $r$: successively attach the loop-erased random walk from each new starting vertex, stopped when it hits the existing tree. Every walk terminates almost surely, because that tree already contains $r$.

To compare the two finite approximations, fix a finite set of edges $K$ and put all their endpoints first in the ordering of starting vertices. In the infinite graph, these finitely many Wilson's algorithm walks have finite lengths almost surely. Their visited vertices, together with their neighbors, are therefore contained in $V_k$ for all sufficiently large $k$ on each realization.

Couple the walks in $G[V_k]$, in $G_k^{\mathrm{w}}$, and in $G$ using the same neighbor choices while they are in the interior of $V_k$. On the event just described, they encounter neither boundary, so the walks, their chronological loop erasures, and the resulting partial trees agree. Once every endpoint of $K$ has entered the partial tree, later walks cannot add any edge of $K$: they stop on their first hit of the existing tree. Thus the indicators of membership for all edges of $K$ agree in the free and wired uniform spanning trees, with probability tending to one.

The two limiting measures agree on every finite-edge event, and thereforeThis argument also shows that the common uniform spanning forest is a single spanning tree on a recurrent graph. The equality refers to probability measures, not to independently sampled forests being identical.

Assume first that deleting an edge leaves two transient graph components. One component supports a finite-energy unit flow from its endpoint to infinity by the finite-energy flow criterion for transience. Extend that flow by zero across the deleted edge and throughout the other component. It remains a finite-energy unit flow on the whole tree, so the tree is a transient graph.

Conversely, root a transient tree at $o$ and take its finite-energy unit electrical flow to infinity. On a tree this flow can be chosen nonnegative in every direction away from the root: it is obtained as the limit of the currents to wired boundaries, each of which sends nonnegative current into descendant subtrees. At each nonroot vertex its incoming current equals the sum of its outgoing currents, by flow conservation.

If every vertex reached by positive current had exactly one positive-current child, the unit current would run along a single infinite ray. Every edge of that ray would carry current one, so its energy of a flow would be ${\sum }_{j\ge 1}1=\infty$, a contradiction. Thus there is a vertex $v$ with two positive-current child edges, say $(v,x)$ and $(v,y)$.

The restricted flow below $x$, rescaled by its incoming current, is a finite-energy unit flow from $x$ to infinity; hence the component below $x$ is a transient graph. After removing $(v,x)$, the other component contains $v$, the edge $(v,y)$, and the descendant subtree below $y$. Send unit current along $(v,y)$ and then use the rescaled descendant flow below $y$, with zero current elsewhere. Its energy of a flow is finite, so this component is a transient graph too. ThereforeUnit edge resistances are essential here: an infinite ray with sufficiently rapidly decreasing resistances can be transient without any such splitting edge.

On a tree, every finite connected induced subgraph is itself a tree, and its only spanning tree contains all its edges. Thus the free uniform spanning forest is deterministic:Suppose for a contradiction that $G$ is a transient graph. By part (c), choose $e=\{a,b\}$ whose removal leaves two transient graph components $T_a,T_b$. Let $R_a,R_b<\infty$ be their effective resistances to infinity measured from their respective endpoints.

In a wired finite exhaustion, the edge $e$ of resistance one is in parallel with the route from $a$ through $T_a$ to the wired boundary and back through $T_b$ to $b$. The latter route has resistance $R_{a,k}+R_{b,k}$, converging to $R_a+R_b$. Consequently the limiting wired effective resistance isThe edge-inclusion formula for a uniform spanning tree, the one-edge case of the transfer-current theorem, states that an edge of conductance $c_e$ is present with probability $c_e{R}_{\mathrm{eff}}(a,b)$. Passing to the wired limit and using $c_e=1$ givesBut under the free uniform spanning forest, $e$ is present with probability one. This contradicts $\mathrm{WSF}=\mathrm{FSF}$. Therefore the tree is recurrent. Combined with part (b), this characterizes equality of the free and wired uniform spanning forests on locally finite unweighted trees.