Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 30 (Interacting Particle Systems)

Orient each edge both ways. A unit flow $j$ from $x$ to $y$ is antisymmetric, $j(u,v)=-j(v,u)$, with divergence of a flow equal to $+1$ at $x$, $-1$ at $y$ and zero elsewhere. Its energy iswhere each unoriented edge is counted once. Put $c_e=1/r_e$. The electrical unit current is $i(u,v)=c_{uv}(V(u)-V(v))$, where the potential $V$ solves the Kirchhoff node law with those source and sink divergences. Because $G$ is a connected graph, this potential is unique up to an additive constant. The effective resistance is the electric potential difference needed for unit current,Discrete summation by parts gives ${\mathcal{E}}_r(i)={\sum }_{u}V(u)\mathrm{div}i(u)=R(x,y)$.

The Thomson principle says that this current minimizes energy among all unit flows. Indeed write any other unit flow as $j=i+k$, where $\mathrm{div}k=0$. ThenConsequentlyThis also proves uniqueness of the minimizing current.

If $r_e^{\prime }\ge r_e$ for every edge, then ${\mathcal{E}}_{r^{\prime }}(j)\ge {\mathcal{E}}_r(j)$ for every admissible flow. The admissible set is unchanged, so taking its minimum proves the Rayleigh monotonicity principle:Deletion is the limiting operation $r_e\to \infty$: finite-energy flows must then carry zero current on that edge. If the terminals become disconnected, the effective resistance is infinite.

Use $T_y=\inf \{n\ge 0:X_n=y\}$ and the positive return time $T_x^{+}=\inf \{n\ge 1:X_n=x\}$. The walk has transitions $p_{uv}=c_{uv}/d(u)$, $d(u)={\sum }_v{c}_{uv}$; its transition matrix defines a reversible Markov chain, although the transition probabilities need not be symmetric.

The voltage $h(u)=P_u(T_x<T_y)$ equals one at $x$, zero at $y$, and is a harmonic function on a graph away from the terminals: $h(u)={\sum }_v{p}_{uv}h(v)$. For this unit electric potential difference the electric current isThe first-step analysis therefore proves the return probability from effective resistance identity:Finite irreducibility ensures eventual hitting of one of the terminals, so no missing escape event appears in this finite-network calculation.

For an infinite locally finite connected graph, exhaust it by finite sets and wire their exteriors to one sink. The event of exiting before the first return decreases to the event of never returning. Thuswith $1/\infty =0$. In particular recurrence is equivalent to infinite effective resistance to infinity.

After deleting an edge, consider any infinite component and choose a root $o$ away from that edge's endpoints. Its vertex degree $d(o)$ is unchanged. On every finite wired exhaustion the Rayleigh monotonicity principle makes the resistance no smaller; the limit of a sequence does too. A recurrent original network consequently leaves a recurrent component. Finite components give recurrent walks as well, with an isolated graph vertex viewed as an absorbing state. This proves that edge deletion preserves recurrence. The phrase “no less recurrent” refers to this recurrence comparison: at a deleted-edge endpoint the vertex degree factor also changes, so monotonicity of its first-return probability alone should not be inferred.

A self-avoiding walk of length $n$ is a sequence of $n+1$ distinct graph vertices joined consecutively by edges. Split a rooted self-avoiding walk of length $m+n$ after $m$ steps. There are ${\kappa }_m$ possible prefixes; each remaining segment is a self-avoiding $n$-step walk from its current graph vertex, and forbidding intersections with the prefix can only reduce its count below ${\kappa }_n$. Translation invariance therefore givesApply the Fekete lemma, proved in Question 4(a), to $\log {\kappa }_n$. It gives $\log \mu ={\inf }_n{n}^{-1}\log {\kappa }_n$ and hence existence of the connective constant. Walks using only the $d$ positive coordinate directions never revisit a graph vertex, so there are at least $d^n$. A walk has $2d$ choices for its first step and at most $2d-1$ subsequently because immediate reversal is forbidden. Thus

For independent bond percolation, let $C(0)$ be the percolation cluster of the origin, $\theta (p)=P_p(|C(0)|=\infty )$, and $p_c=\inf \{p:\theta (p)>0\}$. An infinite percolation cluster in a locally finite graph contains an open self-avoiding path of every length. The union bound givesWhen $p\mu <1$, the right-hand side tends to zero, since its $n$th root tends to $p\mu$. Hence the connective-constant lower bound for percolation is

For the upper bound in two dimensions, use the square planar dual graph. Call a dual edge available when its crossing primal edge is closed. Each dual edge is available with probability $q=1-p$, independently. The planar graph boundary lemma says that a finite primal percolation cluster is enclosed by a graph cycle consisting of such edges: its external edge boundary gives this graph cycle. We show that $q\mu <1$ guarantees positive percolation probability.

Let $N_n$ count enclosing graph cycles of length $n$. Because the origin lies inside their coordinate bounding box and their diameter is at most $n$, every such graph cycle has a graph vertex within a box of side $2n+3$. From each possible root, the first $n-1$ edges give a self-avoiding walk; the final closing edge is then determined. Dropping the closure restriction gives the convenient boundChoose $\rho$ with $q\mu <\rho <1$. The connective-constant limit of a sequence implies ${\kappa }_{n-1}{q}^n\le C{\rho }^n$. Consequently the large-circuit tailis summable.

Condition all primal edges inside a large square $[-L,L{]}^2$ to be open; this event has positive probability. The origin percolation cluster then contains that square. If it is finite, its enclosing graph cycle has length at least $L$. A proposed graph cycle using a pinned-open edge now has conditional probability zero; every other proposed graph cycle still has probability $q^n$ by independence of random variables. For $L$ large enough the union bound for the remaining graph cycles is less than one. There is therefore positive conditional probability that the origin percolation cluster is infinite. This proves the connective-constant Peierls bound without needing the exact value of $p_c$:

Order configurations coordinatewise: $\omega \le \eta$ when $\omega (e)\le \eta (e)$ for every coordinate. An increasing event $A$ is an upward-closed set: $\omega \in A$ and $\omega \le \eta$ imply $\eta \in A$.

The finite-lattice FKG inequality states that a probability mass function satisfying the FKG lattice conditionis positively associated. Here meet in a lattice and join in a lattice are coordinatewise minimum and maximum. Thus for increasing observables $f,g$,Taking indicator functions gives $\mu (A\cap B)\ge \mu (A)\mu (B)$ for all increasing events. The strictly positive version suffices for the Ising weights here; the theorem also holds for nonnegative log-supermodular weights of positive total mass.

Work edge by edge. Let $\omega ,\eta$ have two-bit restrictions to an edge. If these restrictions are comparable, taking their meet in a lattice and join in a lattice only reorders the two pairs, so their total equality indicators do not change. If they are incomparable, they are $01$ and $10$, while their meet in a lattice and join in a lattice are $00$ and $11$. In that case the sum of equality indicators increases from zero to two. ConsequentlyThe partition functions cancel from the required ratio, leavingThis is the ferromagnetic Ising lattice inequality in binary-spin normalization, so the measure satisfies the FKG lattice condition and is positively associated. If $\sigma (x)=2\omega (x)-1$, then ${\delta }_{\omega (x),\omega (y)}=(1+\sigma (x)\sigma (y))/2$: the conventional $\{-1,1\}$ coupling is $\beta /2$, which explains the factor two in the edge calculation.

With the inner boundary specified in the PDF, the Ising boundary condition pins $\omega {|}_{\partial \Lambda }=\zeta$. Explicitly ${\mu }_{\Lambda }^{\zeta }$ is ${\mu }_{\Lambda }$ conditioned on those Ising spins. Its partition function sums over unpinned interior Ising spins only; edges between two pinned sites contribute a constant that cancels on normalization.

Pinning coordinates preserves the FKG lattice condition, since meet in a lattice and join in a lattice still have the same pinned values. It also gives monotonicity in the pins. For any increasing observable $f$, positive association of random variables with an unpinned Ising spin $\omega (z)$ givesBoth conditional probabilities are positive. The same inequality holds after other Ising spins have been pinned. Changing pins one at a time proves stochastic domination of the measures as $\zeta$ increases.

Now let $\Lambda \subset {\Lambda }^{\prime }$ and take an increasing observable depending on a fixed set inside the smaller box. Given the Ising spins on $\partial \Lambda$, the larger-box measure induces precisely the smaller-box interior law with those boundary values: nearest-neighbor interactions cannot see farther once this boundary is fixed. Its conditional law is therefore between the all-zero and all-one smaller-box laws. Averaging yieldsThese are bounded monotone sequences along any increasing box exhaustion.

For every finite set $S$, the event that all Ising spins in $S$ are one is increasing, so its probability converges in both boundary sequences. Probabilities of arbitrary finite zero/one patterns are finite inclusion-exclusion combinations of these all-one probabilities, and hence converge too. The limits are consistent finite-dimensional distributions; they define measures on $\{0,1{\}}^{{\mathbb{Z}}^d}$ and give weak convergence of probability measures in the product topology. Thus both extremal infinite-volume Ising measures ${\mu }^0,{\mu }^1$ exist, with ${\mu }^0$ below ${\mu }^1$ in stochastic domination. This argument proves existence even when the two limits are different.

Set $L={\inf }_{k\ge 1}{x}_k/k$. It may be $-\infty$, but cannot be $+\infty$ because $x_1$ is finite. Fix $k$ and write $n=qk+r$, $0\le r<k$. Repeated use of the subadditive sequence inequality giveswhere $C_1=0$. Dividing by $n$ and letting $n\to \infty$ gives $\mathrm{limsup}{x}_n/n\le x_k/k$. Since this holds for every $k$, the upper limit of a sequence is at most $L$, while every ratio is at least $L$. If $L$ is finite these bounds agree. If $L=-\infty$, choose $k$ with $x_k/k$ below any prescribed real number; the same upper-limit bound proves convergence to $-\infty$. This establishes the extended-real Fekete lemma:A finite real limit of a sequence requires a lower linear bound. For example $x_n=-n^2$ satisfies the premise but has normalized limit of a sequence $-\infty$, so that qualification cannot be dropped.

Write $\varphi ={\varphi }_{p,q}^1$ and $C_n=\varphi (0\leftrightarrow e_n)$. We use these standard facts about the infinite-volume wired random-cluster measure for $q\ge 1$: it is translation invariant and invariant under coordinate reflections/permutations; it has positive association of the random-cluster model; and every conditional edge-open probability is at leastThe last bound follows because an edge either leaves its component count unchanged on opening, giving probability $p$, or merges two components, giving $p/(p+q(1-p))$. These are standard infinite-volume properties of the limit obtained from the finite wired laws by weak convergence of probability measures. Positive association of random variables applies to connection events by increasing approximation with finite-path events.

Opening the $n$ edges of the straight segment gives $C_n\ge r^n$, so its logarithm is finite. The events $A=\{0\leftrightarrow e_m\}$ and $B=\{e_m\leftrightarrow e_{m+n}\}$ are increasing, and their intersection implies connection to $e_{m+n}$. ThusThe sequence $a_n=-\log C_n$ is a subadditive sequence, with $0\le a_n\le -n\log r$. Part (a) proves the random-cluster inverse correlation length exists and is finite:Since $a_n/n\ge \alpha$ for every $n$, exponentiating yields the requested bound

Let $B_n=\varphi (0\leftrightarrow \partial {\Lambda }_n)$ and $s_n=|\partial {\Lambda }_n|$. This connection event is the union over $x\in \partial {\Lambda }_n$ of $\{0\leftrightarrow x\}$. The union bound therefore supplies a graph vertex with connection probability at least $B_n/s_n$.

Every boundary graph vertex has some coordinate equal to $n$ or $-n$. By applying a permutation and a graph automorphisms, which preserve both the law and the boundary, choose such a graph vertex in the form $x=(n,x_2,\dots ,x_d)$ while retaining its probability bound. Now $e_{2n}-x=(n,-x_2,\dots ,-x_d)$ is a reflection of $x$. Translation and reflection invariance givePositive association of random variables applied to the two connection events, whose intersection implies $0\leftrightarrow e_{2n}$, proves the reflection comparison of random-cluster connections:Also $C_n\le B_n$, since any path to $e_n$ meets the box boundary. Consequentlyand henceHere $s_n=(2n+1{)}^d-(2n-1{)}^d=O(n^{d-1})$, so $\log s_n/n\to 0$. Both outside logarithmic connection rates converge to $\alpha (p,q)$ by part (b). Squeezing gives the rate for every box size, and therefore for the requested even subsequence:

In bond percolation on ${\mathbb{Z}}^d$, edges are independently open with probability $p$ and closed otherwise. An open percolation cluster is a connected component using only open edges. In site percolation it is the graph vertices that are independently declared open. The percolation probability $\theta (p)=P_p(0\leftrightarrow \infty )$ measures the chance that the origin lies in an infinite percolation cluster, and the percolation critical probability is $p_c=\inf \{p:\theta (p)>0\}$. Monotone coupling of Bernoulli percolation by independent uniform distribution makes $\theta$ nondecreasing.

The sharpness of the percolation transition says that below $p_c$ connection probabilities on ${\mathbb{Z}}^d$ decay exponentially with distance, while above $p_c$ the percolation probability is positive. There is almost surely a unique infinite percolation cluster in the supercritical regime. On the square lattice, the Harris-Kesten theorem gives bond threshold $1/2$, and there is no infinite percolation cluster at percolation critical probability. The emergence of connections on arbitrarily large scales is the geometric meaning of the phase transition.

Several observables describe this singular behavior. The percolation susceptibility is $\chi (p)=E_p|C(0)|$ for $p<p_c$. A directional correlation length can be defined through exponential two-point decay, $\xi (p{)}^{-1}=-{\lim }_n{n}^{-1}\log P_p(0\leftrightarrow n{e}_1)$. Percolation critical exponents describe leading powers, conveniently defined logarithmically rather than requiring exact asymptotic amplitudes:The first limit of a sequence approaches from above, the other two from below. At percolation critical probability, percolation two-point connection probability is expected to have leading power $|x{|}^{-(d-2+\eta )}$, and the number per site of percolation clusters of size $s$ has leading power $s^{-\tau }$. This cluster-count probability distribution differs from the size-biased probability distribution seen by choosing a site. Scaling relations for critical exponents such as $\gamma =(2-\eta )\nu$ and $2\beta +\gamma =d\nu$ connect the exponents in their applicable scaling regime; hyperscaling relation is not valid above the upper critical dimension of percolation in ordinary mean-field regimes.

The percolation universality hypothesis predicts that dimension and large-scale symmetry, rather than microscopic graph details, determine these exponents and scaling functions. Thus square-lattice bond and triangular-lattice site models are expected to share the planar graph universality class despite different microscopic definitions. Universality does not mean identical critical probabilities, amplitudes or finite-lattice distributions. Exact values and existence of exponents require model-specific theorems, not merely this prediction.

Two dimensions have an additional structure: conformal maps preserve angles, and critical crossing probabilities are expected to be unchanged under conformal transport of the domain and its marked boundary arcs. A crossing probability then depends only on the conformal shape of that marked quadrilateral. The Cardy boundary crossing formula gives this dependence in terms of its boundary cross ratio. For critical triangular-lattice site percolation, conformal invariance and the resulting exponents are established; examples are $\beta =5/36$, $\gamma =43/18$, $\nu =4/3$, with the rigorous statements in leading-power form. These values are summarized in Smirnov and Werner's original paper. Their universality extension to arbitrary planar lattices should not be presented as the same theorem.

An exploration path separating the two colors, with opposite boundary colors on two arcs, has a domain Markov property of a percolation exploration: conditional on the explored portion, the unexplored colors retain their independent laws with the newly exposed boundary colors. Conformal invariance, this domain Markov property and suitable regularity lead to Schramm–Loewner evolution. In the upper half-plane its chordal equation iswhere $B_t$ is standard Brownian motion and time is normalized by half-plane capacity. Critical percolation corresponds to $\kappa =6$. Thus the complicated discrete interface becomes a conformally natural random curve driven by one real Brownian motion. Its crossing and arm probabilities supply critical exponents and, through scaling relations for critical exponents, near-critical singularities. This makes conformal methods predictive tools for the transition, rather than only descriptions of an interface's appearance.

In the voter model on ${\mathbb{Z}}^2$, each site has a rate-one Poisson process clock; when it rings, that site copies one of its four neighbors, chosen uniformly. States are zero or one. For a cylinder function $f$, the local infinitesimal generator iswhere ${\eta }^{x\leftarrow y}$ agrees with $\eta$ except that the voter model opinion at $x$ is replaced by the voter model opinion at $y$. Only sites in the support of $f$ contribute, so this infinitesimal generator sum is finite.

The voter-model duality comes from independent Poisson processes of copying arrows of rate $1/4$ on each ordered neighboring pair. Trace the ancestors of specified sites backwards from time $t$: each ancestral line is a rate-one continuous-time random walk with uniform nearest-neighbor steps, and lines coalesce when they meet. The voter model opinions at time $t$ are the initial voter model opinions at those ancestral locations. This construction also explains the general duality theorem being used.

Two ancestral walks on ${\mathbb{Z}}^2$ meet almost surely. Until their meeting, their difference is a rate-two symmetric nearest-neighbor walk, and simple random walk in two dimensions is recurrent. If ${\tau }_{xy}$ is their meeting time, this givesfor every initial law $\nu$. If $\nu$ is invariant, the left side is the fixed probability $\nu (\eta (x)\ne \eta (y))$, so it is zero. This holds for every pair. Countability then implies that $\nu$ is concentrated on configurations with all voter model opinions equal. Both constant configurations are absorbing state. Thus the invariant measures of the two-dimensional voter model are exactlyNo translation-invariance assumption on $\nu$ was used.

For the last assertion, let the initial set of one-valued opinions $F$ be finite. Single-line duality givesEach transition probability tends to zero. One direct verification is the Fourier transform for the rate-one walk:The integrand has modulus at most one and tends to zero except at the single point $k=0$; dominated convergence proves the claim. For any finite observation set $K$, the union bound now givesTherefore every finite voter model opinion pattern converges in law to the all-zero pattern. These cylinder distributions determine weak convergence of probability measures in the compact product topology, proving finite-seed local extinction in the voter model and