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

Write $w_{xy}=w_{yx}>0$ for an edge conductance and $w_x={\sum }_{y\sim x}{w}_{xy}$. Take $s\ne t$, as implicit in a unit source-to-sink electrical network. An oriented current flow is antisymmetric, $i_{yx}=-i_{xy}$. Kirchhoff's first law is conservation of current: ${\sum }_y{i}_{xy}=0$ at every vertex other than the source and sink, with the divergences there equal to the prescribed total flow and its negative. Kirchhoff's second law says that the sum of oriented voltage drops around any closed cycle is zero. Ohm's law isThus the resistance of an edge is $1/w_{xy}$, and the cycle law reads ${\sum }_{j=0}^{m-1}{i}_{x_j{x}_{j+1}}/w_{x_j{x}_{j+1}}=0$ for $x_m=x_0$.

Let $\tau =\inf \{n\ge 0:X_n=t\}$. Its expectation is finite. Indeed, from each state there is a path to $t$ of length at most $|V|-1$ with positive probability; finiteness gives a common lower bound $a>0$ on reaching $t$ within that many steps. The Markov property then gives $\mathbb{P}(\tau >k(|V|-1))\le (1-a{)}^k$, proving the assertion. Define the expected occupation count before absorptionConditional expectation at every pre-stopping visit to $x$ gives ${\mathbb{E}}_s{N}_{xy}=G(s,x)p_{xy}$ for the number $N_{xy}$ of directed traversals. Hence the expected signed count isThis proves Ohm's law with voltage $v_x=G(s,x)/w_x$, grounded at $v_t=0$. Summing its voltage drops along a cycle telescopes, proving Kirchhoff's second law.

For Kirchhoff's first law, count entrances and exits on each stopped path. Their net difference at $x$ is the initial indicator minus the final indicator. Taking expectations,Thus the source emits exactly one unit, the sink receives one unit, and all other vertices conserve current.

We also establish the uniqueness required for the conclusion. The cycle law implies that edge voltage drops are differences of vertex potentials: define a potential by summing drops along a path to $t$, and cycle sums make this independent of the path. If two unit flows obey both laws, their difference has the form $j_{xy}=w_{xy}(h_x-h_y)$ with zero divergence at every vertex. ThereforeStrict positivity of the conductances and connectedness force $h$ to be constant, so $j=0$. We conclude the electrical current from stopped random-walk traversals identity

Order configurations coordinatewise: $\omega \le \eta$ means that every open edge of $\omega$ is open in $\eta$. An increasing event $A$ satisfies $\omega \in A,\omega \le \eta \Rightarrow \eta \in A$. For $K\subseteq E$, let $1_K$ be the configuration with exactly the edges of $K$ open. For increasing events,The disjoint sets $K,L$ are open witnesses: fixing those edges open forces the respective events whatever happens elsewhere. This is disjoint occurrence of increasing events. The BK inequality states that under the independent density-$p$ product measure,Disjoint occurrence means disjoint witnesses, not disjoint events.

Now take the lattice rectangle with width $2n$ and height $2n-1$. Make the dual bonds open exactly when the primal bonds they cross are closed. A primal open left-right crossing and a dual open top-bottom crossing cannot coexist: the two curves must intersect, requiring a bond and its crossing dual bond both to be open. Conversely, if no primal left-right crossing exists, the boundary separating vertices reachable from the left side from the right side contains a closed-bond dual top-bottom path. One obtains it by tracing the interface of the left-reachable set; it cannot terminate in the interior, and it separates the two vertical boundary sides. Thus exactly one of the two crossing events occurs.

For the precise dual dimensions, its vertices have coordinatesThe top and bottom rows are the terminals of dual edges crossing the primal boundary horizontal bonds. Initially no horizontal bonds along these two terminal rows are needed. Adding independent density-$(1-p)$ horizontal bonds there does not change a top-bottom crossing event: an initial run along the top row can be removed by starting at its last vertex, and a final run along the bottom row can be removed similarly. The completed dual rectangle has width $2n-1$ and height $2n$. Rotate it through a right angle and translate it: its top-bottom crossing has exactly the law of the original left-right event at density $1-p$. Therefore

Write $R_n(v)=\{v\leftrightarrow \partial (v+[-n,n{]}^2)\}$ and $r_n={\mathbb{P}}_{1/2}(R_n(0))$. This event is determined by finitely many bonds, since a path can be stopped on first hitting that boundary. On $A$, erase loops from a crossing path and choose a vertex $v=(n,y)$ where it meets the middle column. Its two portions run to the left and right boundary respectively, each reaching distance at least $n$ from $v$. Stop each portion at its first radius-$n$ boundary hit. The two portions have no common edges, giving disjoint witnesses for $R_n(v)$ twice. HenceThere are exactly $2n$ relevant middle-column vertices. The additional hinted vertex at $y=2n$ is outside this rectangle and need not be included. Translation invariance, the union bound and the BK inequality yieldThe cluster radius is its maximum distance in the ${\ell }_{\infty }$ norm, taking value $\infty$ for an unbounded cluster; thus $R_n(0)=\{\mathrm{rad}(C)\ge n\}$. Taking square roots proves the square-lattice one-arm lower bound from disjoint occurrence

Let $o(\omega )$ be the number of open edges, $k(\omega )$ the number of connected components in the open subgraph, counting isolated vertices, and $m=|E|$. Summing the joint weight over spins requires a constant spin on every open component. There are exactly $q^{k(\omega )}$ choices. Thus the edge marginal isThis is the random-cluster measure, and the joint normalizing constant is $Z_{\mathrm{RC}}$.

Summing instead over edge configurations factors independently over edges. For a fixed spin configuration the resulting weight issince $1-p=e^{-\beta }$. The factor $e^{-\beta m}$ is independent of the spins. Hence the spin marginal is exactly the ferromagnetic Potts measure in the conventionIts partition function satisfies $Z_{\mathrm{RC}}=e^{-\beta m}{Z}_{\mathrm{P}}$.

Conditionally on $\sigma$, edge states are independent: an edge with different endpoint spins is closed with probability one, while one with equal endpoint spins is open with probability $p$. Conditionally on $\omega$, color its $k(\omega )$ open components independently and uniformly from $\{1,\dots ,q\}$. Equivalently, every compatible spin configuration has conditional probability $q^{-k(\omega )}$, and all incompatible configurations have probability zero. These are the two conditional laws of the Edwards-Sokal coupling.

If $x,y$ belong to the same open component, their colors agree surely; otherwise the two independent component colors agree with probability $1/q$. ThereforeRearranging proves the spin-connectivity identity for the Potts model:

Phase transitions refer to infinite-volume limits, not a single finite graph. The identity shows that connectivity is exactly the excess spin agreement above its independent-color baseline. More directly, use a wired random-cluster boundary condition and fix the corresponding boundary spin to color $1$. Its component has color $1$, while every finite component has a uniform color. In the compatible infinite-volume coupling,Consequently normalized spontaneous magnetization isThe onset of a wired infinite cluster and the onset of spontaneous magnetization in the Potts model are the same transition under $p=1-e^{-\beta }$, giving ${\beta }_c(q)=-\log (1-p_c(q))$. This also transfers any jump or continuity of that order parameter between the two descriptions; it makes no assumption about behavior exactly at the critical point.

On the coordinatewise ordered configuration space, ${\mu }_1$ stochastically dominates ${\mu }_2$ when $\int fd{\mu }_1\ge \int fd{\mu }_2$ for every increasing real function $f$. Equivalently, ${\mu }_1(A)\ge {\mu }_2(A)$ for every increasing event. The Holley condition is the sufficient cross-lattice inequalityHere join and meet are coordinatewise maximum and minimum. This condition implies ${\mu }_1{\ge }_{\mathrm{st}}{\mu }_2$ by the Holley inequality; it is not asserted to be necessary. It can be checked on unnormalized weights, since their normalization constants cancel.

Use the weightsFor the upper bound, take ${\mu }_1={\varphi }_{p,1}$ and ${\mu }_2={\varphi }_{p,q}$. Since open-edge count is modular, the Bernoulli factors cancel in the Holley ratio, leavingThe last inequality uses $q\ge 1$ and the fact that removing edges cannot reduce the number of components. Thus ${\varphi }_{p,q}{\le }_{\mathrm{st}}{\varphi }_{p,1}$.

For the lower bound, let $p^{\prime }=p/[p+q(1-p)]$. Its odds satisfySet $a=o(\omega \vee \eta )-o(\omega )=o(\eta )-o(\omega \wedge \eta )$, the number of edges added to $\omega$ in the union. For ${\mu }_1={\varphi }_{p,q}$ and ${\mu }_2={\varphi }_{p^{\prime },1}$, the corresponding ratio isAdding one edge either merges two components or leaves the count unchanged. Therefore adding $a$ edges reduces $k$ by at most $a$, proving the exponent nonnegative. This also proves the hinted monotonicity of $k(\omega )+o(\omega )$ rather than assuming it. The Holley condition now proves both Bernoulli bounds for the random-cluster model:

The same argument holds with wired boundary conditions: identify the wired boundary vertices first and count components on that quotient graph. Taking finite-volume wired limits preserves every increasing cylinder-event inequality. Approximating $\{0\leftrightarrow \infty \}$ by the decreasing events $\{0\leftrightarrow \partial [-n,n{]}^d\}$ consequently givesLet $a=p_c(1)$. For $p<a$, the upper bound makes the wired percolation probability zero, so $p_c(q)\ge a$. If $a<1$ and $p^{\prime }>a$, the lower bound makes it positive. Solving this strict inequality,Taking infima provesFor $a=1$, the lower bound and the trivial upper bound $p_c(q)\le 1$ give the same conclusion. No assumption about percolation at the critical parameter is required.

For the graphical representation of the contact process, put independent death marks on each vertical time-line $\{x\}\times [0,\infty )$ at rate $\delta$, and independent infection arrows $x\to y$ at rate $\lambda$ for every ordered nearest-neighbour pair. A time-directed path moves vertically upward, cannot pass a death mark, and may follow an infection arrow. From an initial set $A$, the infected set ${\xi }_t^A$ consists of sites reachable at time $t$ from $A\times \{0\}$. Thus infected sites recover at rate $\delta$, and a healthy site with $k$ infected neighbours becomes infected at rate $k\lambda$. Rates here are per ordered edge, fixing the normalization of $\lambda$.

With $\delta =1$, writeCouple two infection rates by adding independent arrows of rate ${\lambda }_2-{\lambda }_1$ to the rate-${\lambda }_1$ construction, retaining the same deaths. Every path available at the lower rate remains available at the higher rate. Hence ${\theta }_d(\lambda )$ is nondecreasing.

For the lower bound, dominate the infection population by a linear birth-death branching process $Z_t$, started from one particle, with per-particle birth rate $2d\lambda$ and death rate $1$. Assign one branching particle to every infection; allow an offspring at every attempted transmission, including attempts into an already infected site, and let the extra particles continue independently. Matched deaths remove their infection. This constructs $|{\xi }_t|\le Z_t$. The linear birth rate is nonexplosive, so in particular the contact process from a finite initial set is well-defined with finite population at finite times. Its branching mean solvesConsequentlyIf $2d\lambda <1$, let $t\to \infty$ to obtain ${\theta }_d(\lambda )=0$. This proves the branching bound for contact-process survival

For the upper bound use the dimension comparison for the contact process. Define the height $h(x)=x_1+\cdots +x_d$. Construct an auxiliary infected set ${\eta }_t\subseteq \mathbb{Z}$ together with an infected representative $r_n(t)\in {\xi }_t$ of height $n$ for every $n\in {\eta }_t$. Initially ${\eta }_0=\{0\}$ and $r_0=0$. Use the original graphical marks as follows.

This rule maintains a live representative for every auxiliary infection. Conditional on the full past, each active representative has death rate $1$ and outgoing-arrow rate $d\lambda$ in each of the two height directions. Representatives at distinct heights are different sites, using distinct death clocks and distinct outgoing ordered-edge clocks. Independence and memorylessness of the underlying Poisson processes give exactly the one-dimensional contact-process generatorThus $\eta$ has the law of the one-dimensional contact process with infection rate $d\lambda$, even though the representatives themselves depend on the higher-dimensional history. Since ${\eta }_t\ne \varnothing$ implies ${\xi }_t\ne \varnothing$ at every time,Every $\lambda$ for which $d\lambda >{\lambda }_c(1)$ is therefore supercritical whenever the one-dimensional survival set is nonempty; if that critical value were infinite the inequality would be trivial. Taking infima gives

Let $m=|V|\ge 1$ and put $H(\sigma )={\sum }_{\{x,y\}\in E}{\sigma }_x{\sigma }_y$, counting each edge once. If only the spin at $x$ changes from $-1$ to $+1$, the change in $H$ is $2N(x)$, soThe given opposite transition probabilities have the same ratio. More explicitly,For pairs differing at more than one site both sides vanish, and for equal configurations balance is automatic. This proves detailed balance, hence the chain is reversible with stationary law $\pi$. All single-spin changes have positive probability, so the finite chain is irreducible; it also has positive holding probability and is aperiodic.

Its random-map version is a heat-bath Markov chain. Choose a vertex $I$ uniformly and a uniform $U\in [0,1]$, independently, and set its spin to $+1$ whenand to $-1$ otherwise, leaving all other spins unchanged. This also specifies the holding probabilities omitted from the off-diagonal formulas. The conditional Ising law at $I$ is exactly this Bernoulli choice.

Order spin configurations coordinatewise with $-1<+1$. Since both the neighbour sum and $h$ are increasing, every map defined by a fixed $(I,U)$ preserves this order. For monotone coupling from the past, generate one two-sided independent sequence of such maps $F_n$, $n\in \mathbb{Z}$, and, for a horizon $T$, apply $F_{-T},\dots ,F_{-1}$ to the all-minus and all-plus states at time $-T$. If their time-zero images agree, every initial state has that same image by monotonicity. Return it. Otherwise enlarge $T$, for example by doubling it, retaining all maps already generated at existing negative times. Any earlier starting configuration is also forced to the same output once a horizon coalesces, so the result is consistent under further backward extension.

To prove termination, let $D={\max }_x\mathrm{deg}(x)$ andList the vertices $v_1,\dots ,v_m$. A block of $m$ updates choosing them in that order and having every uniform less than $a$ sets every vertex to $+1$, regardless of the starting configuration. Each choice has probability $1/m$, and every uniform condition has probability $a$. Thus a block is a universal reset with probabilityIndependent disjoint blocks in the past giveOnce such a block occurs, later maps preserve agreement. Therefore the backward search terminates in finite time almost surely, including the doubling implementation.

Finally we prove that the common output $Y$ has law $\pi$. For a deterministic horizon $T$, independently start another chain at time $-T$ with initial law $\pi$ and use the same maps. Its time-zero state $Z_0^{(T)}$ has law $\pi$ by stationarity. On the event that this deterministic horizon coalesces, $Z_0^{(T)}=Y$, so for every event $B\subseteq \Sigma$,Letting deterministic $T\to \infty$ provesThis argument justifies exact sampling without treating a random, data-dependent horizon as a deterministic stationary run.