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

In bond percolation on the square lattice, every nearest-neighbour edge independently has state one, meaning open, with probability $p$, and state zero, meaning closed, with probability $1-p$. Thus the configuration law is the product measure ${\mathbb{P}}_p={⨂}_{e\in E}\mathrm{Bernoulli}(p)$. An open path in bond percolation uses only open edges. An increasing event $A$ satisfies $\omega \in A,{\omega }^{\prime }\ge \omega \Rightarrow {\omega }^{\prime }\in A$: opening further edges cannot destroy the event.

The Harris-FKG inequality for two increasing events isFor disjoint occurrence of increasing events, write $A\square B$ when disjoint sets of open edges separately witness $A$ and $B$, so each event is forced by its own witness regardless of the other edges. The Van den Berg-Kesten inequality statesFor events given by cylinder sets these are finite-coordinate assertions. Connection events have finite open-path witnesses; truncating to finite boxes and taking increasing limits gives the same disjoint-occurrence bound for them. Sharing a vertex between the two witness paths is permitted; sharing an edge is not.

For $1\le m<n$, take a simple open path from the origin to the radius-$n$ boundary and let $x$ be its first vertex on the radius-$m$ boundary. Its initial segment witnesses $0\leftrightarrow x$. If $z$ is its final vertex, then $\Vert z-x{\Vert }_{\infty }\ge n-m$. Consequently the remaining segment reaches $x+\partial {\Lambda }_{n-m}$, and its initial portion until that visit witnesses $x\leftrightarrow x+\partial {\Lambda }_{n-m}$. The two segments use disjoint edges. HenceThe union bound, Van den Berg-Kesten inequality and translation invariance of the product measure now give the weighted BK boundary-splitting estimateFor $m=n$ the same bound follows directly from the union bound, with $g_0=1$. With the conventional $\partial {\Lambda }_0=\{0\}$, $m=0$ gives equality.

Write $C(0)$ for the percolation cluster of the origin. By summing its membership indicators, the percolation susceptibility isIf it is finite, then $a_m\to 0$. For $0<p<1$, choose $m$ with $0<a_m=a<1$. Iterating the boundary-splitting estimate with this fixed $m$ givesFor $k\ge 2m$, $\lfloor k/m\rfloor \ge k/(2m)$, so $g_k\le \exp [-(-\log a)k/(2m)]$. To handle all smaller positive radii without an unspecified prefactor, observe that $g_k\le g_1=1-(1-p{)}^4<1$. ThereforeFor $1\le k<2m$, the second chosen rate gives $e^{-\gamma k}\ge g_1$, and for larger $k$ the first rate applies. At $k=0$ both sides equal one. The endpoint $p=0$ has $g_k=0$ for every $k\ge 1$, so any positive rate works; $p=1$ is excluded by finite susceptibility. This proves exponential one-arm decay from finite susceptibility with the required unit prefactor.

Use the contact process convention that each infected vertex recovers at rate one and sends infection arrows to each neighbour at rate $\lambda$. Starting from a finite set, the process stays finite and is nonexplosive: its total birth rate is at most $\lambda (d+1)$ times its current size, so a linear-rate branching process dominates the number of births. The bound involving $(d-1{)}^{-1}$ presupposes the branching-tree case $d\ge 2$.

For a nonempty finite infected set $A$, put $a=|A|$, let $e(A)$ count its internal edges, and let $b(A)$ count edges with exactly one endpoint in $A$. Each such boundary edge contributes infection rate $\lambda$, even when several lead to the same vacant vertex. Since the induced graph is a forest, $e(A)\le a-1$, and the edge boundary of a finite forest in a regular tree givesA recovery multiplies ${\nu }_{\rho }(A)={\rho }^a$ by ${\rho }^{-1}$, while an infection multiplies it by $\rho$. Therefore its infinitesimal generator isSubstituting the boundary lower bound givesAt the absorbing empty set the generator is zero, rather than this nonempty-set expression. If $\lambda \rho (d-1)\ge 1$, the generator is nonpositive in every state. Both ${\nu }_{\rho }$ and its generator are bounded, since $a{\rho }^a$ is bounded and $b(A)\le (d+1)a$. Applying Dynkin's formula over successive time intervals with the Markov property proves the exponential cardinality supermartingale for the contact process on a tree. In particular,If $\tau$ is the extinction time, $1_{\{\tau \le t\}}\le {\nu }_{\rho }({\xi }_t^A)$, so ${\mathbb{P}}_{\lambda }(\tau <\infty )\le {\rho }^{|A|}<1$. Choosing $\rho \in [1/(\lambda (d-1)),1)$ proves global survival whenever $\lambda >1/(d-1)$. Obtaining a strict improvement of the threshold requires an additional comparison.

Here is a two-vertex branching comparison for contact-process survival. Delete one edge incident to a starting vertex and retain its forward rooted subtree, so every vertex has $d$ children. Partition it into cells as follows: pair each cell root $u$ with one distinguished child $v$; the other $d-1$ children of $u$ and all $d$ children of $v$ become roots of child cells, and repeat recursively. Each cell thus has $2d-1$ child cells.

Suppress arrows back from a child cell into its parent, allow each child cell to be activated only once, and let infection inside each two-vertex cell evolve with the usual recoveries and reinfections until both vertices are healthy. A child cell is activated at its root by the first outgoing arrow to it while the corresponding parent vertex is infected. This process is contained in the original infection process under the graphical representation of the contact process: only infection paths have been removed. The Poisson clocks inside a child cell and on its outgoing edges have not previously been used. The Strong Markov property and independence of the clocks therefore make different cells' offspring counts independent and identically distributed. Dependence among different children of the same cell does not matter. The cell genealogy is a Galton-Watson process.

Let $a$ be the probability that a cell, initially infected only at $u$, sends an arrow along one specified outgoing edge from $u$ before internal extinction. Let $b$ be the corresponding probability for one specified outgoing edge from $v$, and let $c$ be the probability of success for the first target when both cell vertices are initially infected. First-step conditioning on the three nonempty pair states givesFor example, from the state with only $u$ infected, recovery at rate one fails, an internal arrow at rate $\lambda$ leads to the two-infected state, and the target arrow at rate $\lambda$ succeeds. From the state with only $v$ infected, the target cannot be reached until $u$ is infected. Symmetry identifies this latter success probability with $b$. Solving these equations yieldsBy linearity of expectation, the offspring mean is $M(\lambda )=(d-1)a+db$. At the comparison rate ${\lambda }_0=1/(d-1)$,These finite-state probabilities are continuous in $\lambda$. Hence some $0<{\lambda }^{\prime }<{\lambda }_0$ still has $M({\lambda }^{\prime })>1$. The branching-process extinction criterion gives positive probability of infinitely many activated cells. Nonexplosion prevents infinitely many activations in bounded time, and each activation is connected to its ancestor by an infection path. Thus infection survives for all time on that event. The global survival threshold of the contact process consequently satisfiesRetaining reinfection inside pairs is what supplies the strict improvement; a comparison that permits only one infection per vertex would give merely the non-strict bound.

For the local-survival estimate, set $h(x)={\rho }^{g(x)}$ and $w_{\rho }(A)={\sum }_{x\in A}h(x)$. Each vertex has one neighbour of weight ${\rho }^{-1}h(x)$ and $d$ neighbours of weight $\rho h(x)$. Recoveries remove their vertex weights. Ignoring the restriction that an infection target must be vacant only increases the birth contribution, soThese weights have finite expectations on finite time intervals: a birth-only branching process with the same spatial arrows has expected weight at most $w_{\rho }(A)e^{\lambda ({\rho }^{-1}+d\rho )t}$. This justifies localization and the expectation identity for the generator. If $c=1-\lambda ({\rho }^{-1}+d\rho )>0$, Dynkin's formula and the integrating-factor form of the Gronwall inequality giveFor $d\ge 2$, take $\rho =d^{-1/2}$, which minimizes ${\rho }^{-1}+d\rho$ and makes it $2\sqrt{d}$. Starting from $\{x\}$ then givesIn particular the expected total occupation time of $x$ is finite. Its recovery clock has rate one, so the expected number of recovery marks that occur while $x$ is infected equals this occupation-time integral and is finite. Each infection episode ends almost surely at a recovery. Infection at unbounded times would therefore require infinitely many such recoveries, an event of probability zero. This height-weighted local extinction bound for the contact process provesThis is a bound for the local survival threshold of the contact process, not just a bound on single-time infection probabilities. For the degree-two tree $d=1$, the same local conclusion follows by choosing $\rho <1$ sufficiently close to one for each $\lambda <1/2$; the displayed expression $1/(d-1)$ for the global threshold is not a finite numerical assertion in that case.

The joint law is the Edwards-Sokal coupling. For a fixed spin configuration, the sum over each edge state contributes $(1-p)+p{\delta }_e(\sigma )$. Since ${\delta }_e$ is either zero or one, setting $\beta =-\log (1-p)$ givesConsequently the spin marginal distribution is the Potts measureThis follows from a finite sum that factorizes over edges, without any independence assumption on the spin marginal.

For a fixed edge configuration, the joint weight vanishes unless the spins agree across every open edge, equivalently unless they are constant on each open percolation cluster. Each of the $k(\omega )$ clusters, including isolated vertices, may independently be assigned any of $q$ colors. Thus exactly $q^{k(\omega )}$ spin configurations have nonzero weight, and their common weight is the edge-product factor divided by $Z$. The edge marginal distribution is therefore the random-cluster measureIn this convention $Z^{\prime \prime }=Z$. Dividing the joint mass by this positive marginal gives the conditional distributionEquivalently the clusters receive independent uniformly chosen colors. Conversely, conditionally on the spins, edges are independent: an unequal-spin edge must be closed, while an equal-spin edge is open with probability $p$. These two conditional descriptions explain the Edwards-Sokal coupling directly.

If $x$ and $y$ lie in the same open cluster, their conditional spin-equality probability is one. If they lie in different clusters, their two independent uniform colors agree with probability $1/q$. Averaging over the random-cluster measure yieldsand hence the spin-connectivity identity for the Potts modelThe identity also includes $x=y$, when connectivity and spin equality are both certain.

Let the common vertex degree be $r>0$. For each unordered edge place an independent Poisson process of rate $1/r$, and at a mark interchange the two endpoint occupations. If exactly one endpoint is occupied, this moves its particle across that edge at rate $1/r$; if both or neither are occupied, the occupied set stays unchanged. Thus each particle proposes jumps at total rate one, uniformly among its neighbours, with occupied-target proposals suppressed. This is the stated symmetric simple exclusion process. An edgeless graph has the identity dynamics and both conclusions below hold trivially.

In the stirring representation of symmetric exclusion, put a distinct label at every vertex and interchange labels at every edge mark, even when the occupations agree. There are finitely many marks on every finite time interval. Their chronological composition is a random permutation ${\pi }_t$ of the vertex set, and simultaneously for every initial set,Each edge swap is its own inverse. Reflecting the edge-mark times in $[0,t]$ preserves their joint Poisson process law and reverses the order of the swaps. Hence ${\pi }_t^{-1}$ and ${\pi }_t$ have the same distribution. Pathwise,Taking probabilities and then using the inverse-permutation distribution proves the product self-duality of symmetric exclusion in set form:No assumption about disjointness or equal cardinality of $A$ and $B$ is required; impossible inclusions have probability zero on both sides.

For invariance, independently choose the initial occupied set $A$ under the product measure ${\mu }_{\rho }$. The occupations are independent identically distributed Bernoulli distribution variables, so permuting their sites by any deterministic permutation preserves their joint law. Conditional on the independent stirring permutation ${\pi }_t$, the output therefore still has law ${\mu }_{\rho }$. Averaging proves the Bernoulli invariant laws of finite symmetric exclusion:There is also a direct check from the duality. For every $B\subseteq V$,because the exclusion process conserves particle number. These are exactly the joint occupation moments of ${\mu }_{\rho }$; on a finite set they determine the law by the inclusion-exclusion principle. The endpoint densities give the absorbing empty and fully occupied configurations, and the empty-set moment is one also at $\rho =0$.