Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 204 (Percolation and Related Topics)

Let $\alpha ={\inf }_{r\ge 1}{a}_r/r$. The inequality $a_n/n\ge \alpha$ gives ${\mathrm{liminf}}_n{a}_n/n\ge \alpha$. Fix $r$ and write $n=qr+s$, where $0\le s<r$. Repeated subadditivity gives $a_n\le q{a}_r+a_s$ when $s>0$, with the evident omission when $s=0$. Since the finitely many remainders $a_s$ are bounded,Taking the infimum over $r$ proves the Fekete lemma:

Splitting any $(m+n)$-step self-avoiding walk after $m$ steps and translating its remaining segment to the origin injects it into an ordered pair of an $m$-step and an $n$-step self-avoiding walk. Hence $b_{m+n}\le b_m{b}_n$. The sequence $a_n=\log b_n$ is subadditive, so the Fekete lemma givesExponentiating proves existence of the connective constant $\kappa ={\lim }_n{b}_n^{1/n}$.

After the first of the four possible steps, a self-avoiding walk has at most three choices at every stage because it cannot immediately reverse its preceding step. Thus $b_n\le 4\cdot 3^{n-1}$ and $\kappa \le 3$. On the other hand, every sequence of $n$ north or east steps is self-avoiding, so $b_n\ge 2^n$ and $\kappa \ge 2$.

Consider walks assembled from blocks $E$, $E{N}^k$, and $E{S}^k$ with $k\ge 1$. Their horizontal coordinate increases once in every block, and within each vertical line they move monotonically, so every such walk is self-avoiding. If $c_n$ counts these walks by total length, its ordinary generating function isIts positive dominant singularity is $z=\sqrt{2}-1$, so ${\lim }_n{c}_n^{1/n}=1+\sqrt{2}$. Since $b_n\ge c_n$,

In site percolation on the three-dimensional cubic lattice, each vertex $v\in {\mathbb{Z}}^3$ is independently open with probability $p$ and closed with probability $1-p$. Thus ${\mathbb{P}}_p$ is the Bernoulli product measure on $\{0,1{\}}^{{\mathbb{Z}}^3}$, and open paths are nearest-neighbour paths all of whose vertices are open.

The percolation probability and percolation critical probability are

The events $A_n$ decrease, and an open path from $0$ reaches every $\partial {\Lambda }_n$ exactly when the open cluster of $0$ is infinite. Therefore continuity from above of a measure givesEach $A_n$ depends on finitely many sites, so $p\mapsto {\mathbb{P}}_p(A_n)$ is a polynomial and hence continuous. Given $\epsilon >0$, choose $n$ with ${\mathbb{P}}_p(A_n)<\theta (p)+\epsilon$. For $p^{\prime }\downarrow p$, monotonicity and the finite-event continuity yieldThus $\theta (p^{\prime })\to \theta (p)$ from the right.

For every $v\in {\mathbb{Z}}^3$, sample independent $U_v\sim \mathrm{Unif}[0,1]$ and set ${\eta }_p(v)=1_{\{U_v\le p\}}$. Then each ${\eta }_p$ has the required Bernoulli product law and ${\eta }_p\le {\eta }_{p^{\prime }}$ whenever $p\le p^{\prime }$. This is the monotone coupling of Bernoulli percolation.

Within the monotone coupling, $I_p$ increases with $p$ andTaking a countable cofinal sequence $p^{\prime }\uparrow p$ and using continuity from below of a measure givesSince $\{M<p\}\subseteq I_p$, subtraction from $\theta (p)=\mathbb{P}(I_p)$ proves

Use the standard theorem that supercritical Bernoulli percolation on ${\mathbb{Z}}^3$ has a unique infinite open cluster almost surely. Fix $p>p_c$ and choose $q\in (p_c,p)$. Almost surely ${\eta }_q$ has an infinite cluster somewhere. On $I_p$, the origin and that cluster lie in the unique infinite ${\eta }_p$-cluster, so a finite ${\eta }_p$-open path joins them. Almost surely every label on this finite path is strictly below $p$; increasing $q$ to some $r<p$ above those finitely many labels makes the origin percolate in ${\eta }_r$. Hence $I_p\subseteq \{M<p\}$ up to a null event, and part e gives left continuity at $p$. Together with part c, $\theta$ is continuous on $(p_c,1]$.

For $\omega \in \{0,1{\}}^E$, write $o(\omega )=|\eta (\omega )|$ and $c(\omega )=|E|-o(\omega )$. The random-cluster model isFor $0\le p\le 1$ and $q\ge 1$, its positive association of the random-cluster model states that increasing functions $f,g$ satisfy ${\varphi }_{p,q}(fg)\ge {\varphi }_{p,q}(f){\varphi }_{p,q}(g)$.

For the two parallel edges $e_1,e_2$, the four unnormalized weights for $00,10,01,11$ are respectivelyFor the increasing events $A=\{e_1\text{ open}\}$ and $B=\{e_2\text{ open}\}$, positive association is equivalent to $w_{00}{w}_{11}\ge w_{10}{w}_{01}$, which reduces to $q\ge 1$. It therefore fails whenever $p,q\in (0,1)$.

At $p=1/2$, all factors involving the number of open edges are equal, so the weight is proportional to $q^{k(\omega )}$. The smallest possible component count is one. Dividing numerator and denominator by $q$ and sending $q\downarrow 0$ leaves equal weight precisely on connected spanning subgraphs, proving the stated uniform connected-subgraph limit of the random-cluster model.

Finally let $p,q\downarrow 0$ with $q/p\to 0$, and let $N=|V|$. Fix a spanning tree $\tau$. The ratio of the weight of $\omega$ to that of $\tau$ iswhere $d(\omega )=o(\omega )+k(\omega )-N\ge 0$. Equality $d=0$ means that the open graph is a forest. The ratio tends to zero unless $d=0$ and $k=1$, which means precisely that $\omega$ is a spanning tree. All spanning trees have equal weight, so the limiting law is the uniform spanning-tree limit of the random-cluster model:where $\mathcal{T}$ is the set of spanning trees of $G$.

The contact process on $\mathbb{Z}$ has states ${\xi }_t(x)\in \{0,1\}$. Each infected site recovers at rate $\mu$, and infection passes across each oriented nearest-neighbour edge at rate $\lambda$. For the graphical representation of the contact process, put independent rate-$\mu$ recovery marks on each vertical time line and independent rate-$\lambda$ infection arrows on each oriented nearest-neighbour edge. Then $y\in {\xi }_t^A$ exactly when a forward path from some $(x,0)$ with $x\in A$ reaches $(y,t)$ by moving upward, following arrows, and avoiding recovery marks.

If $A\subseteq B$, every path starting in $A$ also starts in $B$, so ${\xi }_t^A\subseteq {\xi }_t^B$. A path starts in $A\cup B$ exactly when it starts in one of the two sets, which proves additivity of the contact process:The event ${\xi }_t^A\cap B\ne \varnothing$ says that a graphical path runs from $A\times \{0\}$ to $B\times \{t\}$. Reflecting the time interval about $t/2$ and reversing every arrow preserves the joint law of the independent Poisson processes, and the path now runs from $B$ to $A$. This proves duality of the contact process:

The survival probability of the contact process isand ${\lambda }_c(\mu )=\inf \{\lambda :\theta (\lambda ,\mu )>0\}$. By duality and translation invariance,The events on the right decrease with $t$ because the empty state is absorbing, and their intersection is eternal survival. Therefore