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

PutFix $k\ge 1$ and write $n=qk+r$ with $0\le r<k$. Repeated subadditivity givessoThe finitely many values $x_0,\dots ,x_{k-1}$ are bounded, henceTaking the infimum over $k$ gives $\mathrm{limsup}{x}_n/n\le \alpha$, while the definition of $\alpha$ gives $x_n/n\ge \alpha$ for every $n$. ThereforeThis is Fekete lemma.

LetThe events $\{0\leftrightarrow e_n\}$ and $\{e_n\leftrightarrow e_{n+m}\}$ are increasing events of bond percolation. The FKG inequality and translation invariance giveThus $(a_n)$ is a subadditive sequence. Since every probability is positive for $p>0$, Fekete lemma applies and gives

By the union bound,Hence some $z\in \partial B(n)$ has connection probability at least the left side divided by $|\partial B(n)|$. Some coordinate of $z$ equals $n$ or $-n$. A coordinate permutation and reflection of ${\mathbb{Z}}^d$ sends that face to the face $x_1=n$ and preserves the bond percolation law. Its image $x$ therefore satisfies

WriteSince $e_n\in \partial B(n)$, $q_n\ge a_n$, and thereforeFor the opposite inequality, choose $x=(n,x_2,\dots ,x_d)$ as in part (ii). Reflection about $x$ sends $0$ to $2n{e}_1$ and preserves the lattice. Thus the increasing events $\{0\leftrightarrow x\}$ and $\{x\leftrightarrow 2n{e}_1\}$ have the same probability. The FKG inequality yieldsConsequentlyThe polynomial boundary-size estimate makes the last term tend to zero, while the first tends to $\varphi (p)$. Hence

Because $p<p_c={\tilde{p}}_c$, choose a finite set $S\ni 0$ with ${\varphi }_p(S)=\rho <1$. Let $L$ exceed the ${\ell }^{\infty }$-distance from $0$ to every endpoint of an edge in $\partial S$, and putOn the one-arm event to distance $n>L$, take the first oriented boundary edge $(x,y)\in \partial S$ used by an open self-avoiding path. The connection $0\stackrel{S}{\leftarrow }x$, the open edge $(x,y)$, and the remaining connection from $y$ to $\partial B(n)$ occur disjointly. The van den Berg-Kesten inequality and translation invariance therefore giveIteration yields $q_n\le {\rho }^{\lfloor n/L\rfloor }$ up to an inessential finite-scale adjustment. Since $p<1$, each of the finitely many remaining $q_n$ is strictly below one, so reducing the exponent if necessary produces a constant $c>0$ valid for every $n\ge 1$:This is the finite-size proof of exponential decay of subcritical percolation.

By Tonelli theorem,If $p<p_c$, part (a) bounds the summand by $e^{-c\Vert x{\Vert }_{\infty }}$. There are only polynomially many vertices at each radius, so the series converges and $\chi (p)<\infty$.

Conversely, suppose $\chi (p)<\infty$. Then $p<1$. Choose $q>p$ so close to $p$ thatUse the standard sprinkling coupling for Bernoulli percolation: first expose the $p$-open clusters, then independently open each remaining edge with probability $\alpha =(q-p)/(1-p)$. Explore the $q$-cluster of the origin cluster by following sprinkled edges. Each discovered $p$-cluster has at most $2d$ times its number of vertices as many incident edges, so the exploration is dominated by a Galton-Watson process of mean at most $2d\alpha \chi (p)<1$. This process dies out almost surely, and hence there is no infinite $q$-open cluster. Thus $q\le p_c$, and $p<q$ implies $p<p_c$. Therefore

A voltage with boundary values $u(a)$ and $u(b)$ is a function $u:V\to \mathbb{R}$ that is harmonic at every other vertex:A current flow is an antisymmetric function $i(x,y)=-i(y,x)$ satisfying Kirchhoff's node law ${\sum }_{y}i(x,y)=0$ away from its source and sink. Voltage and current are related by Ohm's law,The effective resistance is the voltage drop divided by the total current from $a$ to $b$. Equivalently, it is the voltage drop generated by a unit current flow:

Put $A=\{a,b\}$ and let ${\tau }_x^{+}=\min \{t\ge 1:X_t=x\}$. The conductance-hitting identity for an electrical network iswhere the vertices of $D$ are wired together. It follows by taking the hitting probability of $D$ before returning to $x$ as a voltage and computing its total current out of $x$.

Split the walk into successive excursions from $x$. The first excursion that hits $A$ determines whether $a$ or $b$ is hit first. Its conditional probability of hitting $a$ is at most the probability that an arbitrary excursion hits $a$, divided by the probability that it hits $A$. Hence

Let $v$ be the voltage with $v(a)=1$, $v(b)=0$, and harmonic values at every other vertex. For any other admissible $f$, write $f=v+g$, where $g(a)=g(b)=0$. Its discrete Dirichlet energy expands asDiscrete summation by parts turns the cross term intobecause $v$ is harmonic in the interior and $g$ vanishes at the boundary. Thus $v$ minimizes the energy. Under a unit voltage drop, its energy equals the total current from $a$ to $b$, namely the effective conductance $1/R_{\mathrm{eff}}(a,b)$. Therefore the Dirichlet principle gives

A spanning tree of a finite connected graph $G$ is a connected acyclic subgraph containing every vertex. A uniform spanning tree is a random spanning tree chosen uniformly from the finite set of all spanning trees of $G$.

For an infinite locally finite recurrent connected graph, take an increasing exhaustion by finite connected subgraphs and sample a uniform spanning tree in each. The restrictions to any fixed finite edge set converge in distribution; on a recurrent graph the free and wired limits coincide and form one tree. This infinite-volume law is called the uniform spanning tree of the recurrent graph.

It can be generated by Wilson's algorithm. Fix a root and an enumeration of the remaining vertices. Starting with the root, run a random walk from the first vertex not yet in the tree until it hits the existing tree, erase its loops chronologically, and add the resulting path. Recurrence ensures every walk hits the finite tree almost surely. Repeating this operation produces the infinite uniform spanning tree, independently of the enumeration.

Exhaust ${\mathbb{Z}}^2$ by finite boxes $G_n$ and let $T_n$ be a uniform spanning tree of $G_n$. Every finite tree satisfies the handshaking lemma, soChoose the root uniformly from $V(G_n)$. The proportion of roots within any fixed distance of the boundary tends to zero, and the rooted trees converge locally to the uniform spanning tree $T$ of ${\mathbb{Z}}^2$. Since every degree is at most four, expectations also converge. Translation invariance therefore givesThe four edges incident to $0$ have equal inclusion probability by the rotations and reflections of the square lattice. If that common probability is $r$, then $4r=\mathbb{E}{\mathrm{deg}}_T(0)=2$. Consequentlyfor every edge $e$ by translation invariance.