14 Interacting Particles on Finite Graphs (March 10, 1994)

14.6 Other interacting particle models

As mentioned at the start of the chapter, the models discussed in sections 14.3 - 14.5 are special in that their behavior relates to the behavior of processes built up from independent random walks on the underlying graph. In other models this is not necessarily true, and the results in this book have little application.

xxx mention Ising model and contact process.

14.6.1 Product-form stationary distributions

Consider a continuous-time particle process whose state space is the collection of subsets of vertices of a finite graph (representing the subset of vertices occupied by particles), and where only one state can change occupancy at a time. The simplest stationary distribution would be of the form

each vertex vv is occupied independently with probability θ/(1+θ)\theta/(1+\theta) (14.25)

where 0<θ<∞0<\theta<\infty is a parameter. By considering the detailed balance equations (Chapter 3 yyy), such a process will be reversible with stationary distribution (14.25) iff its transition rates satisfy

For configurations 𝐱0,𝐱1{\bf x}^{0},{\bf x}^{1} which coincide except that vertex vv is unoccupied in 𝐱0{\bf x}^{0} and occupied in 𝐱1{\bf x}^{1}, we have q⁢(𝐱0,𝐱1)q⁢(𝐱1,𝐱0)=θ\frac{q({\bf x}^{0},{\bf x}^{1})}{q({\bf x}^{1},{\bf x}^{0})}=\theta.

There are many ways to set up such transition rates. Here is one way, observed by Neuhauser and Sudbury [269]. For each edge (w,v)(w,v) at time tt with ww occupied,

if vv is occupied at time tt, then with chance d⁢tdt it becomes unoccupied by time t+d⁢tt+dt

if vv is unoccupied at time tt, then with chance θ⁢d⁢t\theta dt it becomes occupied by time t+d⁢tt+dt.

If we exclude the empty configuration (which cannot be reached from other configurations) the state space is irreducible and the stationary distribution is given by (14.25) conditioned on being non-empty.

Convergence times for this model have not been studied, so we ask

Open Problem 14.31

Give bounds on the relaxation time τ2\tau_{2} in this model.

14.6.2 Gaussian families of occupation measures

We mentioned in Chapter 3 yyy that, in the setting of a finite irreducible reversible chain (Xt)(X_{t}), the fundamental matrix 𝐙{\bf Z} has the property

πi⁢Zi⁢j⁢ is symmetric and positive-definite .\pi_{i}Z_{ij}\mbox{ is symmetric and positive-definite }.

So by a classical result (e.g. [145] Theorem 3.6.4) there exists a mean-zero Gaussian family (γi)(\gamma_{i}) such that

E⁢γi⁢γj=πi⁢Zi⁢j⁢ for all ⁢i,j.E\gamma_{i}\gamma_{j}=\pi_{i}Z_{ij}\mbox{ for all }i,j. (14.26)

What do such Gaussian random variables represent? It turns out there is a simple interpretation involving occupation measures of “charged particles”. Take two independent copies (Xt+:-∞<t<∞)(X^{+}_{t}:-\infty<t<\infty) and (Xt-:-∞<t<∞)(X^{-}_{t}:-\infty<t<\infty) of the stationary chain, in continuous time for simplicity. For fixed u>0u>0 consider the random variables

γi(u)≡12⁢∫-u0(1(Xt+=i)-1(Xt-=i))⁢d⁢t.\gamma^{(u)}_{i}\equiv\frac{1}{2}\int_{-u}^{0}\left(1_{(X^{+}_{t}=i)}-1_{(X^{-% }_{t}=i)}\right)dt.

Picture one particle with charge +1/2+1/2 and the other particle with charge -1/2-1/2, and then γi(u)\gamma^{(u)}_{i} has units “charge ×\times time”. Clearly E⁢γi(u)=0E\gamma^{(u)}_{i}=0 and it is easy to calculate

E⁢γi(u)⁢γj(u)\displaystyle E\gamma^{(u)}_{i}\gamma^{(u)}_{j} =\displaystyle= 12⁢E⁢∫-u0∫-u0(1(Xs=i,Xt=j)-πi⁢πj)⁢d⁢s⁢d⁢t\displaystyle\frac{1}{2}E\int_{-u}^{0}\int_{-u}^{0}\left(1_{(X_{s}=i,X_{t}=j)}% -\pi_{i}\pi_{j}\right)\ ds\ dt
=\displaystyle= 12πi∫-u0∫-u0(P(Xt=j|Xs=i)-πj)dsdt\displaystyle\frac{1}{2}\pi_{i}\int_{-u}^{0}\int_{-u}^{0}(P(X_{t}=j|X_{s}=i)-% \pi_{j})\ ds\ dt
=\displaystyle= πi⁢∫0u(1-ru)⁢(pi⁢j⁢(r)-πj)⁢d⁢r\displaystyle\pi_{i}\int_{0}^{u}\left(1-\frac{r}{u}\right)(p_{ij}(r)-\pi_{j})% \ dr

and hence

u-1⁢E⁢γi(u)⁢γj(u)→πi⁢Zi⁢j⁢ as ⁢u→∞.u^{-1}E\gamma^{(u)}_{i}\gamma^{(u)}_{j}\rightarrow\pi_{i}Z_{ij}\mbox{ as }u% \rightarrow\infty. (14.27)

The central limit theorem for Markov chains (Chapter 2 yyy) implies that the u→∞u\rightarrow\infty distributional limit of (u-1/2⁢γi(u))(u^{-1/2}\gamma^{(u)}_{i}) is some mean-zero Gaussian family (γi)(\gamma_{i}), and so (14.27) identifies the limit as the family with covariances (14.26).

As presented here the construction may seem an isolated curiousity, but in fact it relates to deep ideas developed in the context of continuous-time-and-space reversible Markov processes. In that context, the Dynkin isomorphism theorem relates continuity of local times to continuity of sample paths of a certain Gaussian process. See [253] for a detailed account. And various interesting Gaussian processes can be constructed via “charged particle” models – see [2] for a readable account of such constructions. Whether these sophisticated ideas can be brought to bear upon the kinds of finite-state problems in this book is a fascinating open problem.

Bibliography