## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Stochastic models for large interacting systems and related correlation inequalities

Contributed by Thomas M. Liggett, August 3, 2010 (sent for review July 1, 2010)

## Abstract

A very large and active part of probability theory is concerned with the formulation and analysis of models for the evolution of large systems arising in the sciences, including physics and biology. These models have in their description randomness in the evolution rules, and interactions among various parts of the system. This article describes some of the main models in this area, as well as some of the major results about their behavior that have been obtained during the past 40 years. An important technique in this area, as well as in related parts of physics, is the use of correlation inequalities. These express positive or negative dependence between random quantities related to the model. In some types of models, the underlying dependence is positive, whereas in others it is negative. We give particular attention to these issues, and to applications of these inequalities. Among the applications are central limit theorems that give convergence to a Gaussian distribution.

## Models for Interacting Systems

During the past half century, mathematical models for the evolution of large interacting systems arising in a number of scientific areas have been proposed and analyzed. Here are some of these areas, together with a sampling of the many papers and books in which such models have been discussed: magnetic systems (1), high energy scattering (2), dynamics of mutation in a structured population (3), tumor growth (4, 5), competition between different strains of viruses (6), mutations of pathogens (7), biopolymers (8), epidemics (9, 10), ecology (11, 12), hydrology (13), cooperative behavior (14–16), spatial distribution of unemployment (17), and the analysis of traffic flow (18–20).

The main objective in the study of these models is to describe their long-time behavior. Usually, the models contain one or more parameters. An important issue is to determine how the long-time behavior depends on these parameters. Often there is a sharp transition in the nature of the behavior at some particular parameter value. This situation is described by saying that a phase transition occurs there.

Some of the analysis of these systems has been mathematical, whereas other approaches have been based on simulations and heuristics. Dobrushin (21) and Spitzer (22) are usually credited with initiating the mathematical developments about 40 years ago. The modern theory of models of this type is treated in my two monographs (23, 24).

Typically, the model is a random process *η*_{t} with state space {0,1}^{Zd} of binary configurations on the *d*-dimensional integer lattice *Z*^{d}. The interpretation of the values 0 and 1 at a site *x*∈*Z*^{d} depends on the model, and on the area that motivated it. The process satisfies the Markov property, which means that once one knows the state of the system at a given time *t*, the evolution of the system after that time does not depend on its behavior before time *t*. It follows that the evolution rules can be described by specifying how the process will behave in an infinitesimal time period (*t*, *t* + *dt*) as a (random) function of the state *η*_{t} at time *t*. This is analogous to describing a deterministic function *y*(*t*) by a differential equation that it satisfies.

In the present context, the evolution rules are given by certain transition rates. To say that the transition *η* → *ζ* from one configuration to another occurs at rate *λ* > 0 means that in a short time period of length *ϵ*, the transition occurs with probability approximately *λϵ*. Usually, the transition rate will depend on *η*, and this dependence leads to interactions among various parts of the system.

Our focus here is on models on the graph *Z*^{d}. However, in many contexts, such as communications and social systems, it is more natural to consider more general graphs. For related evolutions on random graphs, see ref. 25, for example. Some of the results mentioned below have extensions to cases in which *Z*^{d} is replaced by a general countable set.

A very useful tool in the mathematical analysis of interacting systems is that of correlation inequalities—inequalities that assert that the state of one random quantity has a positive (or negative) influence on the state of another. These inequalities often make it possible to treat dependent random quantities as if they were independent. This is, of course, a great simplification. We will see a number of specific instances of this simplification in the present paper.

Here is the plan for this paper: I begin by describing some of the most important models in this area—voter, contact, magnetic, and exclusion—and give a sampling of the most important results about them. Then I discuss the associated correlation inequalities (positive for the first three models and negative for exclusion) and present some consequences that follow from them.

Before getting started, I need to introduce a bit of notation and terminology from probability theory. The probability of an event *A* is denoted by *P*(*A*). If it appears with a superscript, as in *P*^{η}(*A*), the superscript *η* is the initial state of the process. Similarly, *E*^{η}*X* is the expected value, or mean value, of the random quantity *X*, when the initial state of the system is *η*.

Bernoulli random variables are random variables that take only two values, typically 0 and 1. Thus a probability distribution on {0,1}^{Zd} gives the joint distribution of a collection of (generally not independent) Bernoulli random variables indexed by *Z*^{d}.

### Voter Models.

The simplest models in this area are known as voter models. They were introduced in refs. 26 and 27. Later it was realized that they are very similar to the earlier “stepping stone” model of population genetics introduced in ref. 3. A biased version was proposed as a model for tumor growth in ref. 4.

In ref. 27, the idea was to model conflict between populations. Sites *x* for which *η*(*x*) = 1 represent areas controlled by one population; those for which *η*(*x*) = 0 are controlled by the other. A site controlled by one group is taken over by the other at a rate that is proportional to the number of neighbors controlled by the opposing group.

The voter interpretation of ref. 26 was not our motivation in that paper—the actual motivation was of a more mathematical nature. The idea was to identify a class of models that had properties such as Eq. **2** below that permitted an essentially complete mathematical analysis of the process.

Even though I do not claim that this is a good model for electoral behavior, I will describe the process in electoral terms. Each site in *Z*^{d} represents a person, who at any given time, has one of two possible opinions on an issue, labeled 0 and 1. Each person waits a unit exponentially distributed time *T*, i.e., one for which *P*(*T* > *t*) = *e*^{-t}. At that time, he chooses one of his 2*d* neighbors at random and adopts that neighbor’s opinion.

Here is the main question: Is it the case that the system reaches a consensus (in the voter interpretation), or that one population takes over the entire space (in the spatial conflict interpretation), in the sense that [1]for all *x*, *y*∈*Z*^{d} and all initial configurations *η*?

The key to the answer lies in a connection between the voter model and a classical random walk *X*(*t*), which moves on *Z*^{d} in the following way: It waits where it is for a unit exponential time, then moves to a randomly chosen neighbor, and continues in this way. Here is a special case of the connection. Suppose that initially each voter independently chooses opinion 1 with probability α and opinion 0 with probability 1 - *α*. Then the probability that the individuals at *x* and *y* share the same opinion at time *t* can be expressed in terms of a probability related to the random walk: [2]

A classical result in probability theory states that *X*(*t*) is recurrent (i.e., hits 0 eventually with probability 1) if *d* = 1 or 2, but not if *d*≥3. It follows that the limiting statement Eq. **1** holds if and only if *d* ≤ 2.

A key issue for all the models we consider is understanding the nature of their stationary distributions. A probability distribution μ on {0,1}^{Zd} is said to be stationary for *η*_{t} if the process with that initial distribution continues to have distribution μ at all later times. The importance of stationary distributions comes from the fact that any limiting distribution of the process as *t* → ∞ is stationary. Thus the identification of stationary distributions is the first step in the analysis of the limiting behavior of *η*_{t}.

When Eq. **1** holds, the voter model has only trivial stationary distributions: If μ is stationary, then it concentrates on configurations representing consensus; When *d*≥3, the situation is quite different (26). Both opinions can coexist in equilibrium:

Suppose *d*≥3.

*(a) For every 0 ≤**α*≤ 1, there is a stationary distribution*μ*_{α}in which the proportion of 1’s is exactly α. It is obtained by starting the system with all voters having opinion 1 independently with probability α, and then passing to the limit as*t*→ ∞.*(b) Every stationary distribution can be expressed as an average of the distributions**μ*_{α}.

For extensions of this result to voter models on a general countable set, see Chapter V of ref. 23.

Rather than starting the system with a distribution in which all voters are equivalent, one could start the voter model with a single voter with opinion 1 and ask for the behavior of the number *N*_{t} of voters with that opinion at time *t*. It turns out that *EN*_{t} = 1 for all *t*, and it is then easy to check that *P*(*N*_{t}≥1) → 0 as *t* → ∞. In ref. 28, it is proved that this probability has the following order of magnitude as *t* → ∞: Furthermore, conditioned on the event {*N*_{t}≥1} of nonextinction of opinion 1, *N*_{t}*P*(*N*_{t}≥1) converges to a unit exponential distribution if *d*≥2.

In the biased version of the voter model that was proposed to model tumor growth, rates for the transitions 0 → 1 are larger than the corresponding rates for the transitions 1 → 0. The interpretation now is that 1’s correspond to cancerous cells and 0’s to normal cells. The process starts with a single cancerous cell. There is positive probability that the tumor disappears, but as a result of the bias, there is also a positive probability that it continues to grow forever. One of the important results for this model (29) is that the growth of the tumor is linear in time and that it takes on a deterministic asymptotic shape as *t* → ∞.

### Contact Models.

The contact process was introduced in ref. 9. Here the interpretation is one of spread of infection. Later it was realized that the model is closely related to a field theory in high energy physics (2). This is surprising, because nothing in the description of the model suggests that there might be such a connection.

With the infection interpretation, sites with the value 1 are infected, whereas those with the value 0 are healthy. Infected sites remain infected for a unit exponential time, independently of the states of their neighbors, and then become healthy. Healthy sites become infected at rate where *λ* is a positive parameter. This transition mechanism is deceptively similar to that of the voter model, but the analysis is much harder because connections such as Eq. **2** no longer hold.

Now a type of phase transition occurs. For small values of *λ*, the infection dies out, in the sense that for all initial configurations *η* and all sites *x*. For larger *λ*, this is not the case, and there is a probability distribution *ν* on {0,1}^{Zd} with a positive density of infected sites that is stationary for the evolution. The threshold value *λ*_{d} that separates the regimes of survival and extinction of the infection cannot be computed exactly, even in one dimension, but it can be approximated numerically. It does satisfy the rigorous bounds (9, 30) Thus 1 ≤ *λ*_{1} ≤ 2, for example. Somewhat better bounds are available in low dimensions: 1.539 ≤ *λ*_{1} ≤ 1.942. For large *d*, the lower bound above is asymptotically correct: 2*dλ*_{d} → 1 as *d* → ∞.

At this point, it is reasonable to ask the following question: In view of the fact that real systems are finite, why is it reasonable to study infinite models at all? The contact process provides a clear answer to this question. If the set of sites for the mathematical model is taken to be the finite box {1,…, *N*}^{d} instead of *Z*^{d}, then the infection dies out for all values of *λ*. This is a consequence of an elementary result about finite state Markov chains. However, how long it takes to die out depends strongly on the value of *λ*. If *λ* < *λ*_{d} (where *λ*_{d} is the critical value for the process on *Z*^{d}), then the extinction time is logarithmic in the system size *N*^{d}, whereas if *λ* > *λ*_{d}, it is exponential in the system size (31). Therefore, if one observes a large finite system for a large finite time, one will see the infection die out in the subcritical case, but survive in the supercritical case. So, the process on *Z*^{d} is a better model for a large finite system than a process on a finite set would be!

### Magnetic Models.

In this case, it is more natural to let the possible values of *η*(*x*) be ± 1 rather than 0 and 1, because they represent magnetic spins. The central objects of study in statistical mechanics are the Gibbs distributions for the Ising model, which are probability distributions μ on {-1,+1}^{Zd}. They are described by specifying the conditional probabilities for the state at *x*∈*Z*^{d}, given the states at other sites: where the sums are over the neighbors *y* of *x*. Here β is a positive parameter that represents the reciprocal of the temperature of the system. Classical results include the fact that these conditional probabilities determine μ uniquely for all β in one dimension, whereas in higher dimensions the Gibbs distribution is unique for small β, but not for large β.

The transition rates for the random evolution, which is known as the Glauber dynamics (1), are chosen so that the Gibbs distributions are stationary (and in fact reversible) for the evolution. There are many choices with this property; in a simple one, the rate of flipping the state at *x* from *η*(*x*) to -*η*(*x*) is taken to be when the configuration is *η*. Note that these rates are large if *η*(*x*) differs from the states at most of its neighbors, and small if it largely agrees with them. This means that spins prefer to align themselves with their neighbors, which is certainly reasonable to expect in this context.

A natural question is whether all stationary distributions for the time evolution are Gibbs distributions. This is known to be the case if *d* = 1 (which is easy because the Gibbs distribution is unique) or *d* = 2 (which is much harder—see ref. 32). This remains an open problem in higher dimensions.

Although the original motivation for these models comes from physics, they have also led to important techniques known as Markov Chain Monte Carlo or Gibbs sampling. Here the objective is to simulate a Gibbs distribution on a large but finite set of sites. Rather than doing it directly, which is difficult given the large size of the system, the evolution is run for a long time *t*, and the distribution at that time is used as an approximation to the limiting Gibbs distribution. This is a huge field with many applications. Two references are refs. 33 and 34. The latter is an example of an application in computational biology.

### Exclusion Processes.

These are of a different nature than the models described so far. Transitions change the values at two sites rather than only one. Now the states 0 and 1 represent occupancy by particles (or cars in the traffic flow context). Particles move on *Z*^{d} in such a way that there is at most one particle per site. A particle at *x* moves to *y*, if it is vacant (hence the name exclusion), at rate *p*(*y* - *x*), where *p*(*x*)≥0 for each *x* and . An alternative description is that a particle at *x* waits a unit exponential time and then chooses a *y* to try to move to with probability *p*(*y* - *x*). If *y* is vacant, it moves there, whereas if *y* is occupied, it remains at *x*.

Although exclusion processes seem natural in the contexts of particle motion and traffic flow, it is interesting to note that perhaps the earliest appearance of them was in a biological situation—see ref. 8. In this case, the “particles” are ribosomes that move along a messenger RNA template reading genetic information.

Again we are interested in stationary distributions. A probability distribution on {0,1}^{Zd} is called exchangeable if it does not change when finitely many coordinates of *η* are permuted. It is not hard to check that all exchangeable distributions are stationary for the exclusion process. It is harder to determine when these are all the stationary distributions. Here is one of the early results about this problem (35, 36):

Suppose *p*(·) is symmetric, i.e., *p*(-*x*) = *p*(*x*) for all *x*. Then all stationary distributions are exchangeable.

For extensions of this result to exclusion processes on a general countable set, see Chapter VIII of ref. 23.

The above conclusion is often false for asymmetric systems. For example, take the case in which *d* = 1, *p*(1) = *p*, *p*(-1) = 1 - *p*, and *p*(*x*) = 0 otherwise. If , so particles experience a drift to the right, there are stationary distributions with respect to which there are only finitely many particles to the left of the origin, and only finitely many empty sites to the right of the origin. In one example, the coordinates {*η*(*x*), *x*∈*Z*^{1}} are independent, with [3]In fact, all stationary distributions can be constructed from these and the exchangeable ones in this case. Generalizations of this statement to one-dimensional systems with long-range jumps can be found in ref. 37. In this more general context, explicit formulas such as Eq. **3** are usually not available. This is a source of much of the difficulty that arises in the analysis.

To describe a rather surprising consequence of the asymmetry, we continue with the one-dimensional nearest-neighbor case. Suppose the initial distribution is of the following type: negative sites are independently occupied with probability *λ*, and nonnegative sites with probability *ρ*. If *λ* = *ρ*, this distribution is exchangeable, and hence stationary. What happens in the limit as *t* → ∞ if *λ* ≠ *ρ*? Here is the answer (38, 39), which is substantially more complex in the asymmetric case:

*(a)**If**, then**(b) If**, then*

These results can be predicted by the behavior of associated partial differential equations (PDEs)—the heat equation if , and Burgers’ equation [4]if . The more elaborate and interesting limiting behavior in the asymmetric case is a consequence of the nonlinearity in Eq. **4**.

The connection between the exclusion process and the PDE arises in the following way: If the evolution equations for the exclusion process are simplified by assuming that the coordinate variables *η*_{t}(*x*) are independent for different *x*’s, the result is a discrete form of the corresponding PDE. If one solves the PDE with the initial condition then takes the form given in Theorem 3.

The limiting (in distribution) occupation variables *η*_{∞}(*x*) in Theorem 3 are independent for different *x*’s in all of these cases except , , and *λ* + *ρ* = 1, when the covariances are given by

Exclusion processes on finite sets have been of substantial interest as well—see ref. 40, for example. To describe one recent result, suppose *S* is a set with *n* points, and place *n* distinguishable particles on it, one at each point. For each pair *x*, *y*∈*S*, interchange the particles at *x* and *y* at a rate that depends on the locations of the two particles. There are various Markov chains that are embedded in this structure. By following the motion of only one of the particles, one obtains a chain with *n* states. More generally, following the positions of *k* ≤ *n* particles gives rise to a chain with many more states: *n*(*n* - 1)⋯(*n* - *k* + 1). In this case, if one makes the particles indistinguishable, the *k* particles move according to a symmetric exclusion process on *S*.

For a concrete example, consider shuffling a standard 52 card deck. Then *n* = 52, and *S* is the set of possible positions of a card in the deck. The shuffling is done by interchanging the *k*th and *l*th cards at a rate that depends on *k* and *l*. For example, the rate might be higher if the two cards are closer together in the deck than if they are farther apart. If one follows the position of the ace of spades, say, the chain has 52 possible states. If one follows the positions of all 52 cards, the corresponding chain has 52 ! ≈ 10^{68} states.

The rate of convergence to the stationary distribution (which is a perfectly shuffled deck in the shuffling context) is determined by the smallest nontrivial eigenvalue of a matrix made up of the transition rates. This eigenvalue can be computed easily when the chain has 52 states, say, but cannot be computed for a chain of anything like 10^{68} states. Recently, Caputo et al. (41) were able to prove the 1992 conjecture of D. Aldous that the principal eigenvalues for the large (*n* ! states) and small (*n* states) chains are the same for any *n* and any choice of rates. It follows that computing the eigenvalue for the smaller chain is enough to determine the rate of convergence to equilibrium for the larger chain.

Here is the barest outline of our approach. The proof is by induction on *n*. To carry out the induction step, it is necessary to take the set of size *n* with transition rates associated to pairs of points in that set and construct from it a set of size *n* - 1, together with a new collection of rates on pairs of those points. This is done by generalizing the series, parallel, and star-triangle reductions used in electrical network theory. Using the induction hypothesis on the smaller set, the problem becomes one of showing that a particular *n* ! × *n* ! matrix is positive semidefinite. This is done by a careful analysis of the structure of a related large matrix.

## Correlation Inequalities

There is a natural (partial) order on {0,1}^{Zd}: A real valued continuous function *f* on {0,1}^{Zd} is said to be increasing if *η* ≤ *ζ* implies *f*(*η*) ≤ *f*(*ζ*). An important problem is to determine the evolutions and initial distributions for which for all increasing *f* and *g* and all *t* > 0. This means that the random variables *f*(*η*_{t}) and *g*(*η*_{t}) are positively correlated in the usual sense. This section is devoted to a discussion of this question, together with the analogous question for negative correlations.

### Positive Association.

A probability distribution μ on {0,1}^{Zd} is said to be positively associated if [5]when *η* has distribution μ. The best known result related to this concept is the Fortuin–Kasteleyn–Ginibre (FKG) theorem (42), which gives a sufficient condition (known as the FKG lattice condition) for positive association. It is easy to check this condition when the coordinates *η*(*x*) are independent [in which case positive association was known earlier—(43)] and can often be verified for Gibbs distributions. However, the FKG lattice condition can essentially never be checked for the distribution at time *t* of any of the evolutions we are considering. In fact, it is often false, even if it turns out that the distribution is positively associated.

To check that the distribution at time *t* of an evolution is positively associated, one uses the following result (44), which applies to a very general class of processes on {0,1}^{S}, including the voter, contact, and magnetic (but not exclusion) models described above:

Suppose the process satisfies the following two properties:

*(a) Individual transitions affect the state at only one site.**(b) For every continuous increasing function**f*and every*t*> 0, the function*η*→*E*^{η}*f*(*η*_{t})*is increasing.*

Then, if the initial distribution is positively associated, so is the distribution at all later times.

It follows from this that the limiting distribution as *t* → ∞, if it exists, is also positively associated.

### Negative Association.

In the analogous definition for negative association, Eq. **5** is replaced by [6]This last constraint is necessary, because if *f* = *g*, the opposite inequality Eq. **5** automatically holds for any μ.

One might hope that negative association is related to the exclusion process in much the same way that positive association is related to voter, contact, and magnetic models. Here is the reason: In the exclusion process, particles are neither created nor destroyed. Therefore, if one knows that a certain subset of *Z*^{d} has many particles, it is likely that disjoint subsets have relatively fewer particles. It turns out that in order for something like this to actually be true, *p*(·) must be symmetric: *p*(-*x*) = *p*(*x*) for all *x*.

Whereas the intuition is fairly clear, it took 35 years to find the correct version of the connection between the symmetric exclusion process and negative association (45–47). Here is one consequence of the general statement for the symmetric exclusion process that is proved in ref. 47:

Suppose that initially, the random variables {*η*(*x*),*x*∈*Z*^{d}} are independent. Then

*(a) the distribution of the process at time**t*> 0*is negatively associated, and**(b) if**S**is a subset of**Z*^{d}*, the number**of particles in**S**at time**t**has the same distribution as a sum**of appropriately chosen independent Bernoulli random variables.*

Part (b) is a very useful property for proving limit theorems, as we will see in the next section.

Given the form of Theorem 4, one might suspect that negative association itself is preserved by the symmetric exclusion evolution. This is not the case (48). The key to Theorem 5 is finding another property that is preserved, and that implies properties (a) and (b) in this result.

The property that works is a rather unintuitive one known as stability. To describe it, suppose the exclusion process is evolving on a finite set *S* = {1,…, *n*}. The random variables {*η*(*x*), *x*∈*S*} are said to be stable if the (generating) function of *n* complex variables is not zero whenever all the *z*_{i}’s have strictly positive imaginary parts. It turns out that the property of stability is preserved by the symmetric exclusion process. The fact that independent Bernoulli random variables are stable is easy to check. The fact that stable random variables are negatively associated is much more difficult to establish. On the other hand, the fact that stable random variables have property (b) of Theorem 5 is easy to see: Take *z*_{1},…, *z*_{n} to be equal. Then is the generating function of the sum *η*(1) + ⋯+*η*(*n*). This is a polynomial in one variable of degree *n*, whose zeros cannot have positive imaginary parts by the stability property and therefore cannot have negative imaginary part, because the zeros occur in conjugate pairs. They are therefore real, and in fact ≤ 0, because the polynomial is strictly positive on the positive real axis. Therefore, it can be factored in the form [7]where 0 ≤ *p*_{i} ≤ 1 for each *i*. Now take *ζ*(*i*) to be independent with *P*[*ζ*(*i*) = 1] = *p*_{i}. Then *ζ*(1) + ⋯+*ζ*(*n*) has generating function Eq. **7** as well, so *η*(1) + ⋯+*η*(*n*) and *ζ*(1) + ⋯+*ζ*(*n*) have the same distribution.

## Consequences of Correlation Inequalities

In this section, we describe a few of the many results concerning interacting systems that are related to correlation inequalities.

### Voter Models.

It follows from Theorem 4 that when *d*≥3, the nontrivial stationary distributions *μ*_{α} for the voter model are positively associated. In fact, using Eq. **2**, one can show that the covariances for the coordinate random variables relative to *μ*_{α} are given by where which is the expected total amount of time the random walk spends at *x*.

Looking ahead to comments about central limit theorems for contact and magnetic models below, note that This is an indication that the (positive) correlations among voter opinions are quite strong.

### Contact Models.

It took 15 years to prove that the critical contact process (the one with *λ* = *λ*_{d}) dies out. The proof (49, 50) uses several times the fact that collections of independent Bernoulli random variables are positively associated.

The nontrivial stationary distribution *ν* for the supercritical (*λ* > *λ*_{d}) contact process does not satisfy the FKG lattice condition (51). However, it is positively associated by Theorem 4. Theorem 4.20 of Chapter I of ref. 23 and Theorem 2.30 of Part I of ref. 24 combine to show that the covariances of *η*(*x*) and *η*(*y*) relative to *ν* decay exponentially rapidly as a function of the distance |*y* - *x*|. It then follows from results in refs. 52 or 53 that *ν* satisfies the following central limit theorem:

Let . Then

In this statement, ⇒ denotes convergence in distribution, Var stands for variance, and *N*(0, *σ*^{2}) represents the Gaussian distribution with mean 0 and variance *σ*^{2}.

The FKG lattice condition is equivalent to the statement that the distribution is positively associated, even after conditioning on the values of {*η*(*x*),*x*∈*S*} for any *S*. This raises the question of whether *ν* is associated after some special type of conditioning. It is not when the conditioning is on the event *η*(0) = 1. In fact, if *d* = 1, the conditional distribution satisfies Eq. **6** rather than Eq. **5** if *f* depends on {*η*(*x*), *x* < 0} and *g* depends on {*η*(*x*), *x* > 0} (54). The intuition behind this is that if the origin is known to be infected, the infection must have come from somewhere. If it did not come from the left, it must have come from the right.

Nevertheless, *ν* is positively associated after conditioning on the event {*η*(*x*) = 0,*x*∈*S*} (55, 56). A consequence of this (together with other known properties of the contact process) is that if {*η*(*x*),*x*∈*Z*^{d}} have distribution *ν* and *λ*≥2, then there exist independent Bernoulli random variables {*ζ*(*x*), *x*∈*Z*^{d}} with density so that *ζ*(*x*) ≤ *η*(*x*) for all *x* (57). As in Theorem 5(b), this is a connection between nonindependent Bernoulli random variables and independent ones that is very useful is analyzing the former collection.

For example, consider the site percolation model, in which one asks whether there is positive probability that infinitely many sites are connected to the origin by paths that travel only through sites for which *η*(*x*) = 1 (respectively, *ζ*(*x*) = 1). Classical results for independent percolation imply that if *d*≥2 and *λ* is sufficiently large, percolation occurs for the above *ζ*’s. The comparison result implies that it also occurs for the nonindependent *η*’s. Motivated by ref. 57 and the biological application in ref. 58, properties that have long been known for independent percolation have recently been extended to percolation in *ν* for *d* = 2 in ref. 59.

### Magnetic Models.

Suppose that initially all spins are +1. Then for every *t* > 0, the covariances Cov[*η*_{t}(*x*), *η*_{t}(*y*)] decay exponentially rapidly as a function of |*y* - *x*| by Proposition 4.18 of Chapter I of ref. 23. The random variables *η*_{t}(*x*) are positively associated by Theorem 4. It then again follows that the spin variables satisfy the central limit theorem. If the (distributional) limiting random variables *η*_{∞}(*x*) satisfy [8]the same argument applies. Condition **8** holds often, but not always.

### Exclusion Processes.

Assume throughout that the model is symmetric, *p*(-*x*) = *p*(*x*) for all *x*, because it is only then that useful correlation inequalities are available.

The proof of part of Theorem 2 begins with an extension of the symmetry property, which is known as duality. Consider two copies of the exclusion process, *η*_{t} and *ζ*_{t}, with initial configurations *η* and *ζ*, respectively. Then [9]for all *t* > 0. When *η* has infinitely many particles and *ζ* has finitely many particles, this duality property reduces many problems for the infinite system to corresponding problems for the finite system.

By Theorem 5(a), [10]for distinct points *x*_{1},…, *x*_{n}∈*Z*^{d}. The right side can be interpreted as the probability that *n* independent (by Eq. **9** and the fact that it is a product of probabilities) particles starting at *x*_{1},…, *x*_{n} will be in the set {*x*∶*ζ*(*x*) = 1} at time *t*. Thus problems relating to *n* particles moving with the exclusion interaction can often be reduced to problems relating to *n* independent particles, which is a great simplification.

Consider now the problem of the motion of a tagged particle. The tagged particle is initially placed at the origin; other sites are initially occupied with probability each. The problem concerns the asymptotic behavior of the position *X*(*t*) of the tagged particle at time *t*. The presence of the other particles has the effect of slowing down the tagged particle. The question is, by how much is it slowed down? The following situation is special, but particularly interesting in view of the unusual scaling (60):

Suppose *d* = 1 and . Then *X*(*t*) obeys the central limit theorem [11]

In essentially all other cases, *X*(*t*) is asymptotically Gaussian, but with a variance that is of order *t* rather than (61–63). The proof of **11** is based on Eq. **10** as well. A key point is that the variance of the sum of negatively correlated Bernoulli random variables is at most equal to its mean.

The two applications above use only the weak form Eq. **10** of negative association that has been known since 1974. Here is an application of the more elaborate version proved in ref. 47 only recently. Suppose *d* = 1, and that initially all negative sites are occupied and all positive sites are vacant. Let *W*(*t*) be the number of particles that are to the right of the origin at time *t*: By Theorem 5, for each *t* > 0, the summands above are negatively correlated, and there are independent Bernoulli random variables *ζ*_{t}(*x*) so that *W*(*t*) has the same distribution as This makes it possible to apply classical central limit theorems to the sum directly, once one proves that Var[*W*(*t*)] → ∞ as *t* → ∞. This fact is intuitively obvious, but is not particularly easy to prove. The difficulty comes from the fact that in the expression the summands corresponding to *x* = *y* are positive, whereas those corresponding to *x* ≠ *y* are negative, and may cancel the positive contributions and lead to a bounded variance.

The proof that Var[*W*(*t*)] → ∞ is again based on comparisons between finite interacting systems and the corresponding independent systems. Here is the result proved in ref. 64:

If , then [12]with both the mean and the variance of *W*(*t*) being of order .

The central limit theorem **12** has been extended to some choices of *p*(·) with infinite variance in ref. 65.

## Discussion

In this paper, I have described some of the important results from the area of probability theory that is known as interacting particle systems—an area with motivations from, and connections to, a number of the sciences. Among the various techniques that have been important in the analysis of models in this area are the following:

(a) Coupling, in which two or more copies of the process are defined on the same probability space. This leads to conclusions about one of the processes based on known properties of the others.

(b) Duality, in which algebraic relations between two processes are exploited. Examples are given by Eqs.

**2**and**9**. Duality is used in the proofs of Theorems 1 and 2.(c) Renormalization, in which finite boxes in

*Z*^{d}are regarded as individual sites. This is a key tool in the proof of the extinction of the critical contact process, for example.(d) The correlation inequalities discussed here.

I have focussed on the latter technique in this paper for a number of reasons, including (*i*) the fact that major progress has been made in the past 2 years in the case of negative association and (*ii*) my own involvement in the proof and use of both positive and negative correlations in interacting particle systems in recent years.

In various ways, correlation inequalities often allow one to treat dependent random variables as if they were independent and therefore to apply classical results on independent random variables to obtain results in situations in which dependence occurs. Applications of this technique that we have discussed here include the following:

(a) the proof of Theorem 2 and its extensions on stationary distributions for the symmetric exclusion process,

(b) extinction of the critical contact process,

(c) the existence of percolation for the nontrivial stationary distribution of the contact process, and

(d) central limit theorems for a tagged particle in the exclusion process, and for the number of particles in large boxes for several models.

Even in the proofs of the central limit theorems, the way in which the correlation inequalities are used varies from case to case. This is a very versatile tool.

## Acknowledgments

I appreciate helpful comments by R. Durrett and C. Newman on an early version of this paper.

## Footnotes

^{1}E-mail: tml{at}math.ucla.edu.Author contributions: T.M.L. wrote the paper.

This contribution is part of the special series of Inaugural Articles by members of the National Academy of Sciences elected in 2008.

The author declares no conflict of interest.

## References

- ↵
- ↵
- ↵
- Kimura M

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Mollison D

- ↵
- ↵
- ↵
- Rodríguez-Iturbe I,
- Rinaldo A

- ↵
- ↵
- ↵
- ↵
- Topa G

- ↵
- ↵
- ↵
- ↵
- Dobrushin RL

- ↵
- ↵
- Liggett TM

- ↵
- Liggett TM

- ↵
- Durrett R

- ↵
- Holley R,
- Liggett TM

- ↵
- Clifford P,
- Sudbury A

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Winkler G

- ↵
- ↵
- ↵
- ↵
- Bramson M,
- Liggett TM,
- Mountford T

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Borcea J,
- Brändén P,
- Liggett TM

- ↵
- Liggett TM

- ↵
- ↵
- ↵
- Grimmett G

- Liggett TM

- ↵
- ↵
- ↵
- Denteneer D,
- den Hollander F,
- Verbitskiy E

- van den Berg J,
- Häggström O,
- Kahn J

- ↵
- ↵
- Liggett TM

- ↵
- ↵
- ↵
- van den Berg J

- ↵
- Arratia R

- ↵
- ↵
- Varadhan SRS

- ↵
- ↵
- ↵
- Vandenberg-Rodes A

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Applied Mathematics