The Jammed Phase of the Biham-Middleton-Levine Traffic Model

Omer AngelFunded in part by the Pacific Institute of Mathematical Sciences. , Alexander E. HolroydFunded in part by an NSERC (Canada) grant. and James B. Martin

March 30, 2005

Abstract
Initially a car is placed with probability p   at each site of the two-dimensional integer lattice. Each car is equally likely to be East-facing or North-facing, and different sites receive independent assignments. At odd time steps, each North-facing car moves one unit North if there is a vacant site for it to move into. At even time steps, East-facing cars move East in the same way. We prove that when p   is sufficiently close to 1   traffic is jammed, in the sense that no car moves infinitely many times. The result extends to several variant settings, including a model with cars moving at random times, and higher dimensions.      

1 Introduction

The following simple model for traffic congestion was introduced in [?] . Let Z 2 = { z = ( z 1 , z 2 ) : z 1 , z 2 ∈ Z }   be the two-dimensional integer lattice. At each time step t = 0 , 1 , …   , each site of Z 2   contains either an East car ( →   ), a North car ( ↑   ) or an empty space (0). Let p ∈ [ 0 , 1 ]   . The initial configuration is given by a random element σ   of { 0 , → , ↑ } Z 2   under a probability measure P p   in which P p ( σ ( z ) = → ) = P p ( σ ( z ) = ↑ ) = p / 2 and P p ( σ ( z ) = 0 ) = 1 − p   for each site z ∈ Z 2   , and the initial states of different sites are independent.
The configuration evolves in discrete time according to the following deterministic dynamics. On each odd time step, every ↑   which currently has a 0   immediately to its North (i.e. in direction (0,1)) moves into this space.
On each even time step, each →   which currently has a 0   immediately to its East (i.e. in direction (1,0)) moves into this space. The configuration remains otherwise unchanged.
Theorem 1. There exists p 1 < 1   such that for all p ≥ p 1   , almost surely no car moves infinitely often and the state of each site is eventually constant.
The above result goes part way towards establishing the following natural conjecture.

Conjecture.

There exists p c ∈ ( 0 , 1 )   such that for p > p c   almost surely no car moves infinitely often, while for p < p c   almost surely all cars move infinitely often.
The model may be defined on a finite torus (i.e. a rectangle with periodic boundary conditions) in a natural way, and our proof can be adapted to this case.
Theorem 2. Consider the model on an m   by n   torus. There exists p 1 < 1   such that for any p ≥ p 1   and any sequence of tori such that m , n → ∞   and m / n   converges to a limit in ( 0 , ∞ )   , asymptotically almost surely no car moves infinitely often and the configuration is eventually constant.
The present article represents the first rigorous progress on the model, which has previously been studied very extensively via simulation and partly non-rigorous methods. Such studies have suggested that p c ≈ 0.35   , and furthermore that for p   sufficiently small (and perhaps even for all p < p c   ), all cars move with asymptotic speed equal to the maximum possible “free flowing” speed of 1 / 2   . The latter striking phenomenon was observed experimentally in [?] , and has been conjectured for the infinite lattice by Ehud Friedgut (personal communication). Recent results in [?]  suggest the existence of further intermediate phases (involving speeds strictly in ( 0 , 1 / 2 )   ) for the model on finite tori. The model appears to exhibit remarkable self-organizing behaviour. The problem of rigorously analyzing the model was given as an “unsolved puzzle” in [?] . References to earlier work may be found for example in [?] .
Here is an overview of our proof of Theorem  1 . First consider the (trivial) case p = 1   . Any given car is blocked by another car immediately in front of it, this car in turn is blocked by a further car, and so on. Thus the original car can never move because there is an infinite chain of cars blocking it. This argument does not extend to p < 1   because such a chain will always be broken by an empty space. Therefore we consider an additional local configuration which can cause a car to be blocked in a different way, and which gives rise to additional types of blocking paths. This local configuration occurs with some positive intensity throughout space, therefore for p = 1   we obtain an extensive network of blocking paths, any of which block a given car. Now if we add a sufficiently low proportion of empty spaces it is likely that some of these paths will survive, and so the original car will be blocked even when p < 1   . This argument is formalized via a comparison with super-critical oriented percolation on a renormalized lattice.
In principle, our arguments give an explicit bound for p 1   in Theorem  1 .
We do not attempt to compute this bound, since it would be very close to 1, and nowhere near the supposed value of p c   .
Our proof extends to yield analogous results in a number of variant settings. These include: a model in which cars move at random Poisson times rather than at alternate discrete time steps, initial conditions with different probabilities of East and North cars, and higher dimensional generalizations.
We discuss these variants, and Theorem  2 concerning the torus, at the end of the article.

2 Proof of Main Result

A finite or infinite sequence of sites z 0 , z 1 , z 2 , . . . [ , z n ]   is called a blocking path if for each m ≥ 0   , one of the following holds:
  • (i) σ ( z m ) = →   and z m + 1 = z m + ( 1 , 0 )   ;
  • (ii) σ ( z m ) = ↑   and z m + 1 = z m + ( 0 , 1 )   ;
  • (iii) σ ( z m ) = σ ( z m + ( 1 , 0 ) ) = →   , σ ( z m + ( 1 , − 1 ) ) = ↑   , and z m + 1 = z m + ( 1 , 1 )   ;
  • or (iv) σ ( z m ) = σ ( z m + ( 0 , 1 ) ) = ↑   , σ ( z m + ( − 1 , 1 ) ) = →   , and z m + 1 = z m + ( 1 , 1 )   .
See Figure  1 for an illustration. Note that if z 0 , … , z n   and z n , z n + 1 , …   are blocking paths then so is z 0 , … , z n , z n + 1 , …   . Cases (i) and (ii) correspond to the naïve chains of cars mentioned in the introduction. Cases (iii) and (iv) will provide the key to our argument by allowing for additional types of blocking path.

Figure 1 : There are blocking paths from (0,0) (bottom left) to (2,2) and from (0,0) to (1,2). The latter uses a step of type (iii).

Lemma 3. No car on an infinite blocking path ever moves.
  • Proof. We claim that the car at z m   can only move strictly after that at z m + 1   has moved. This implies the result, by induction on the time step. The claim is immediate in cases (i) and (ii) above. In case (iii), we note that the car at z m   can only move after that at z m + ( 1 , 0 )   . If the latter car ever moves then it does so at an even step, and it is replaced immediately at the next step by the car initially at z m + ( 1 , − 1 )   . But this car now cannot move again until after that at z m + 1   . An analogous argument applies in case (iv).
We introduce a renormalized lattice with the structure of Z 2   . Let M , k   be integers to be fixed later satisfying M > 2 k > 0   . Each site in the renormalized lattice consists of 2 k + 1   sites on a diagonal. Denote by D k   the set { ( s , − s ) : | s | ≤ k }   . For each site u = ( u 1 , u 2 ) ∈ Z 2   we define the renormalized site V u = u 1 ( 10 M , 9 M ) + u 2 ( 9 M , 10 M ) + D k .   A renormalized edge is an ordered pair ( u , v )   where v − u   equals ( 1 , 0 )   or ( 0 , 1 )   . We say that the edge ( u , v )   is good if from every x ∈ V u there is a blocking path to some y ∈ V v .   See Figure  2 for an illustration.

Figure 2 : Part of the renormalized lattice; ( ( 0 , 0 ) , ( 0 , 1 ) )   and ( ( 0 , 1 ) , ( 1 , 1 ) )   are good edges.

Lemma 4. Suppose M > 2 k > 0   . The process of good edges is 30-dependent. (That is, if A , B   are sets of edges at graph-theoretic distance at least 30 from each other in the renormalized lattice, then the states of the edges in A   are independent of those in B   ).
  • Proof. From the definitions of blocking paths and good edges, the event that the edge ( u , v )   is good depends only on the initial states σ ( x )   of sites x   in a certain box containing V u   and V v   . Since M > 2 k   , such boxes are disjoint for edges at graph-theoretic distance at least 30   from each other.
Theorem  1 is a consequence of the following.
Proposition 5. Let α < 1   . There exist M   and k   with M > 2 k   such that for all p   sufficiently close to 1, for every edge ( u , v )   ,
P p ( edge ( u , v ) is good ) ≥ α . (6)
Proof of Theorem  1 . Recall that the critical probability for oriented percolation on Z 2   is strictly less than 1 (see [?]  or [?] ). By the results of [?] , if α   is sufficiently close to 1 then any 30-dependent bond percolation process on Z 2   satisfying ( 6 ) stochastically dominates a Bernoulli percolation process which is super-critical for oriented percolation on Z 2   .
Therefore by Proposition  5 and Lemma  4 , we may choose M , k   such that if p   is sufficiently close to 1, with positive probability there is an infinite path of good renormalized edges starting from V ( 0 , 0 )   , oriented in the positive directions of both coordinates. On this event, there is an infinite blocking path starting at ( 0 , 0 )   , so by Lemma  3 we have P p ( there is a car which never moves at ( 0 , 0 ) ) > 0 .   Now consider any site z   . By translation invariance and ergodicity, it follows from the above that almost surely there are cars which never move at z + ( r , 0 )   and z + ( 0 , s )   for some (random) r , s ≥ 0   . This implies that any car initially at z   moves at most max { r , s }   times, while the state of z   changes at most 2 ( r + s )   times.
To prove Proposition  5 , we start by reducing to the case p = 1   .
Proposition 7. For any β < 1   , there exist M   and k   with M > 2 k   such that for every edge ( u , v )   , P 1 ( edge ( u , v ) is good ) ≥ β .  
Proof of Proposition  5 . Pick β ∈ ( α , 1 )   , and fix M , k   according to Proposition  7 . Since the event that an edge is good depends only on the initial states in a finite box, it is a polynomial in p   and therefore continuous.
Thus the result follows from Proposition  7 .
It remains to prove Proposition  7 . We therefore consider only the case p = 1   from now on. Figure  3 illustrates all blocking paths starting at the origin.
The following key lemma states that such paths come close to any site in a certain cone.

Figure 3 : Blocking paths for p = 1   . Blocking paths from the origin are highlighted.

Lemma 8. Let E ( y , k )   be the event that there is a blocking path from ( 0 , 0 )   to y + ( s , − s )   for some s ∈ [ − k , k ]   . There exists c > 0   such that for any site y ∈ Z 2   satisfying y 1 , y 2 > 0   and y 1 / y 2 ∈ [ 8 / 9 , 9 / 8 ]   we have P 1 ( E ( y , k ) ) > 1 − e − c k .  
  • Proof. Given a “target” y   , we will algorithmically construct a blocking path z 0 , z 1 , …   starting at z 0 = ( 0 , 0 )   . The idea is as follows. If we use only steps of types (i),(ii) in the definition of a blocking path, we obtain a unique random path with asymptotic direction ( 1 , 1 )   . If we also allow steps of types (iii),(iv), then at a positive proportion of steps we have a choice of which direction to move. By always choosing the direction which moves closer to the target we are exponentially unlikely to miss the target by much, provided that the target is within a cone determined by the typical slopes that would result from choosing to go always up or always down.
    For simplicity, we will only allow choices at alternate steps. Let z 0 = ( 0 , 0 )   . Suppose that a blocking path z 0 , … , z m   has been constructed, and suppose that z m   lies on the diagonal line z 1 + z 2 = 2 n   . We will extend the blocking path by one or two sites to some site on the line z 1 + z 2 = 2 n + 2   .
    Suppose first that σ ( z m ) = →   , and consider the following cases:
    • (1) If σ ( z m + ( 1 , 0 ) ) = ↑   we set z m + 1 = z m + ( 1 , 0 )   and z m + 2 = z m + ( 1 , 1 )   .
    • (2) If σ ( z m + ( 1 , 0 ) ) = σ ( z m + ( 1 , − 1 ) ) = →   we set z m + 1 = z m + ( 1 , 0 )   and z m + 2 = z m + ( 2 , 0 )   .
    • (3) If σ ( z m + ( 1 , 0 ) ) = →   and σ ( z m + ( 1 , − 1 ) ) = ↑   we have a choice:
      we can set either
      • (a) z m + 1 = z m + ( 1 , 0 )   and z m + 2 = z m + ( 2 , 0 )  
      • or (b) z m + 1 = z m + ( 1 , 1 )   (using a blocking path step of type (iii)).
      We choose (a) if z 1 m − z 2 m < y 1 − y 2   , otherwise (b).
    Thus we take the naïve path (using steps of types (i) and (ii)) unless a step of type (iii) is possible and it moves us closer to y   than the alternative.
    On the other hand if σ ( z m ) = ↑   then z m + 1   (and possibly z m + 2   ) are determined in an identical way, but interchanging the roles of the two coordinates, and of ↑ , →   . In particular, in the equivalent of case (3) above we extend the blocking path to z m + 2 = z m + ( 0 , 2 )   if z 1 m − z 2 m > y 1 − y 2   , and to z m + 1 = z m + ( 1 , 1 )   otherwise.
    The above construction evidently yields a blocking path z 0 , z 1 , …   . Suppose for the moment that y 1 + y 2   is even. For each n   , let z r ( n )   be the site at which the blocking path intersects the line z 1 + z 2 = 2 n   , and let W n = | ( z 1 r ( n ) − z 2 r ( n ) ) − ( y 1 − y 2 ) | / 2   . It is straightforward to check that ( W n ) n ≥ 0   is a Markov chain with transition probabilities
    P j , j − 1 = 1 / 4 , P j , j = 5 / 8 , P j , j + 1 = 1 / 8 for j ≥ 1 ;
    P 0 , 0 = 3 / 4 , P 0 , 1 = 1 / 4 .
    Thus ( W n ) n ≥ 0   is a random walk on the natural numbers with drift − 1 / 8   , and a reflecting boundary condition at 0   .
    Claim 9. For the above Markov chain ( W n )   , there exists c 1 > 0   such that for any N > 9 r   and any k   , P ( W N > k | W 0 = r ) ≤ e − c 1 k .  
    If y 1 + y 2   is even, then the lemma follows from the claim immediately. If y 1 + y 2   is odd, then we apply the lemma first to y − ( 1 , 0 )   or y − ( 0 , 1 )   and k − 1   , and note that that any finite blocking path may always be extended by one site in direction ( 1 , 0 )   or ( 0 , 1 )   .
Proof of Claim  9 . Since the chain has increments at most 1, we have W N ≤ r + N ≤ N / 9 + N < 2 N   . Hence the probability in question is zero when k > 2 N   , so we may assume k ≤ 2 N   .
Let T   be the first time ( W n )   hits 0   . Before T   , the increments are i.i.d.
with mean − 1 / 8   , so by the Chernoff bound we have P ( T > 9 r ) ≤ e − c 2 N ≤ e − c 2 k / 2   . Therefore, applying the strong Markov property at T   , the claim will follow if we can establish for fixed c 3 > 0   and all n ≥ 0   that P ( W n > k | W 0 = 0 ) ≤ e − c 3 k   . To check this, observe that we may couple ( W n )   with a stationary copy ( W ~ n )   in such a way that W n ≤ W ~ n   for all n   , then note that the stationary distribution has exponentially decaying tail.
Proof of Proposition  7 . Take k   large enough that ( 2 k + 1 ) e − c k < 1 − β   , and then take M > 2 k   large enough that 10 M + k 9 M − k ≤ 9 8 .   By Lemma  8 and translation invariance we obtain
P 1 ( edge ( u , v ) is not good ) ≤ ∑ x ∈ V u P 1 ( ∄ a blocking path from x to V v )
≤ ( 2 k + 1 ) e − c k < 1 − β .

Remarks.

An alternative proof of Proposition  7 involves considering only blocking paths from the two endpoints of V u   (rather than all 2 k + 1   elements), and noting that blocking paths cannot cross without intersecting. (This argument does not extend to higher dimensions).
Lemma  8 in fact holds with the improved slope 3/2 (rather than 9/8); this may be shown by allowing choices at all possible steps rather than just alternate steps.
Experiments suggest that infinite blocking paths exist whenever p > 0.95   .

3 Extensions

At the core of the proof is a comparison of the collection of blocking paths to super-critical oriented percolation. Since percolation is relatively robust to variations in the model, it is not surprising that our result holds for several other natural models. We present several of these.
The proofs of the following theorems follow the same basic argument as for Theorem  1 . Each of the variants differs in some part of the proof, and so we only indicate the changes that need to be made. For simplicity we do not formulate a model encompassing all extensions simultaneously.

The finite torus.

We consider the model in which Z 2   is replaced with the rectangle { 1 , … , m } × { 1 , … , n }   with periodic boundary conditions. Thus, a car moving East from ( m , i )   re-appears at ( 1 , i )   , while a car moving North from ( j , n )   re-appears at ( j , 1 )   . Our aim is to prove Theorem  2 .
We will use the following definition in constructing a renormalized lattice on the torus. For linearly independent vectors a , b ∈ Z 2   , the skew torus T ( a , b )   is the directed graph obtained from the oriented square lattice by identifying vertices x , y ∈ Z 2   whenever x − y = s a + t b   for some s , t ∈ Z   (and identifying the corresponding edges).
Lemma 10. Let q   exceed the critical probability for oriented bond percolation on Z 2   . For any a , b ∈ Z 2   , asymptotically almost surely as r → ∞   with r ∈ Z   , bond percolation with parameter q   on the skew torus T ( r a , r b )   contains an open oriented cycle.
Lemma  10 may be proved by standard percolation methods; we present an argument after the following proof.

Figure 4 : The renormalized lattice on a torus. Here it is the skew torus T ( ( 6 , − 3 ) , ( − 2 , 4 ) )   .

Proof of Theorem  2 . First note that the existence of a cyclic blocking path including both horizontal and vertical steps is sufficient to ensure that no car moves infinitely often. The proof goes through as on Z 2   except that we need to adjust the geometry of the renormalized lattice, which will have the structure of a skew torus. The process of good edges will still be 30-dependent and the probability of an edge being good will be uniformly large provided the slopes of the renormalized edges lie strictly within a certain interval, and provided M   and k   are large enough; indeed M   and k   may vary from edge to edge. Consider a sequence of tori of dimensions m k , n k   as in Theorem  2 . For k   sufficiently large we may construct a sequence of renormalized lattices subject to the above restrictions and with graph structure of T ( r k a , r k b )   , where r k → ∞   . See Figure  4 for an illustration.
The result then follows from Lemma  10 , since an oriented cycle in the renormalized lattice yields the required cyclic blocking path.
Proof of Lemma  10 . The event that bond percolation on the skew torus contains an open oriented cycle is increasing, and it is quasi-symmetric; more precisely, it is invariant under a group of permutations of the edges of the skew torus having two transitivity classes (the horizontal edges and the vertical edges). By the Friedgut-Kalai sharp threshold theorem (see Theorem 2.1 and the comment following Corollary 3.5 in [?] ), it therefore suffices to prove that for any q   as described, the probability in question is bounded away from 0   as r → ∞   . (See [?]  for another application of [?]  to percolation).
First consider oriented bond percolation with parameter q   on Z 2   . We write x → y   for the event that there is an open oriented path from x   to y   .
We claim that
inf r ≥ 1 P ( ( 0 , 0 ) → ( r , r ) ) > 0 . (11)
To check this, write θ = P ( ( 0 , 0 ) → ∞ )   ( > 0   ), and note that P ( ( 0 , 0 ) → ( r , r ) + ( s , − s ) for some s ) ≥ θ .   Hence by symmetry, P ( ( 0 , 0 ) → ( r , r ) + ( s , − s ) for some s ≥ 0 ) ≥ θ / 2 ,   and similarly P ( ( s , − s ) → ( r , r ) for some s ≥ 0 ) ≥ θ / 2 .   On the intersection of the last two events we have ( 0 , 0 ) → ( r , r )   , since the two directed paths must intersect. Therefore by the Harris-FKG inequality (see [?]  or [?] ) we have P ( ( 0 , 0 ) → ( r , r ) ) ≥ ( θ / 2 ) 2   , establishing ( 11 ).
Let ℓ   be the smallest positive integer such that ( 0 , 0 ) = ( ℓ , ℓ )   in the skew torus T ( a , b )   ( ℓ   is at most the number of vertices in T ( a , b )   ). Now consider bond percolation with parameter q   on T ( r a , r b )   , and let A   be the event that ( 0 , 0 ) → ( r , r ) → ( 2 r , 2 r ) → ⋅ ⋅ ⋅ → ( ℓ r , ℓ r ) .   By the Harris-FKG inequality we have P ( A ) ≥ γ ℓ   , where γ   is the infimum in ( 11 ). And clearly on A   there is an open oriented cycle.

Higher dimensions.

Consider a variant model on Z d   in which each non-empty site is occupied by a car facing in one of the d   directions. At times congruent to i   modulo d   , all the cars facing in direction i   advance if the place ahead of them is empty.
Many of the conjectures for the 2-dimensional model appear reasonable in this case as well. Define P p   to be the probability measure in which initially each site has a car with direction i   with probability p / d   , and is empty otherwise.
Theorem 12. For the model on Z d   with any d ≥ 2   , there exists some p 1 = p 1 ( d ) < 1   such that for p > p 1   , almost surely no car moves infinitely often.
  • Proof. The proof is very similar to that of the two-dimensional case. Suppose more than one car is directly blocked by a car at z   . If the car at z   moves, than the order at which cars advance dictates which of the blocked cars will enter z   . This allows us to generalize the notion of a blocking path, and it is easy to see that there is some fixed positive probability of being able to continue a blocking path in any given direction.
    The argument now continues as for Z 2   . The probability of having no path from x   to a neighborhood of y   inside a sufficiently narrow cone is exponentially small, and the renormalization argument applies.

Biased initial conditions.

Let P θ , p   be the probability measure on initial configurations in which P θ , p ( σ ( z ) = 0 ) = 1 − p   , P θ , p ( σ ( z ) = → ) = θ p   , and P θ , p ( σ ( z ) = ↑ )   = ( 1 − θ ) p   for each site z   , and the states of different sites are independent.
Theorem 13. For any θ ∈ ( 0 , 1 )   there exists p 1 = p 1 ( θ ) < 1   such that for p > p 1   we have that P θ , p   -a.s. no car moves infinitely often.
  • Proof. The proof of Theorem  1 adapts to this case as well. The maximum and minimum typical slopes of blocking paths are altered, and are not generally symmetric about the diagonal. A renormalized lattice spanned by two vectors inside the reachable cone can still be constructed.

Random moves.

Another interesting modification is to replace the deterministic evolution of the model by a random mechanism. In particular, suppose each car attempts to move forwards at the times of a Poisson process of unit intensity, where different cars have independent Poisson processes.
Theorem 14. For the Poisson model there exists p 1 < 1   such that for any p > p 1   , almost surely no car moves infinitely often.
  • Proof. Consider a location corresponding to a step of type (iii) or (iv) in a blocking path. This involves a local configuration where two cars are directly blocked by a third car at some z   . With deterministic evolution it is determined from the directions of the cars which of the two will advance to z   (thereby blocking the other), should z   become empty. With the random moves this is not determined just by the directions. Clearly each of the two is equally likely to advance into z   before the other, independently of what happens at other locations where such a configuration exists.
    Thus we can toss an independent coin in advance at each such location, where the results of these coin tosses tell us which of the locations allow for a branching in the blocking paths and which do not. Since each potential branching point is retained with probability 1/2 independently of all others, the blocking paths still form a super-critical process, and the proof goes through.
Acknowledgements We thank Ehud Friedgut, Yuval Peres and Raissa D'Souza for valuable conversations.
Omer Angel: angel(at)math.ubc.ca Alexander E. Holroyd: holroyd(at)math.ubc.ca Department of Mathematics University of British Columbia Vancouver, BC V6T 1Z2, Canada James B. Martin: James.Martin(at)liafa.jussieu.fr CNRS and Université Paris 7 2 place Jussieu (case 7014) 75251 PARIS Cedex 05, France

  This work was done while all three authors were hosted by the Mathematical Sciences Research Institute in Berkeley.

  Key words: traffic, phase transition, percolation, cellular automata

  2000 Mathematics Subject Classifications: Primary 60K35; Secondary 82B43