# Computable Throughput and Metastability in a Cellular Automaton Model for Traffic Flow

Authors: Ryan Gantner
Journal: ISRN Probability and Statistics
 (2013)

---

## Abstract

A cellular automaton model for traffic flow is analyzed. For this model, it is shown that under ergodic initial configurations, the distribution of cars will converge in time to a mixture of free flow and solid blocks. Furthermore, the nature of the free flow and solid block distributions is fully described, thus allowing for a specific computation of throughput in terms of the parameters. The model is also shown to exhibit a hysteresis phenomenon, which is similar to what has been observed on actual highways.


---

## Body

## 1. Introduction and Description of the Model

### 1.1. Introduction

There have been various cellular automaton models introduced to model traffic flow [1–3]. Many of these models gain computational advantage over older so-called car-following, fluid dynamical, and kinetic (gas-type) models by discretizing both space and time (see [4] for an overview of various models). For these discrete models, simple rules are developed to govern car movement. While, on a small scale, the rules oversimplify traffic behavior, the goal is that large scale traffic phenomena, such as the formation and persistence of traffic jams, present themselves in this simplified approach.The model used in this paper is a discrete time probabilistic cellular automaton model developed by Gray and Griffeath in [2]. We will be concerned with macroscopic limiting phenomena on an infinitely long one-dimensional highway. In this paper, we show the existence of a limiting throughput (flux) of cars and describe these regions explicitly. For traffic densities above a critical value, we are able to show that the traffic organizes itself into regions of free flow and regions of traffic jam, both of which will be given precise mathematical definitions in this context. We also observe the existence of metastable states: conditions which allow certain ergodic traffic distributions to have higher throughput than others with the same density of cars. The existence of metastable states has been sought after [5] due to the fact that such states have been shown to be exhibited in real-world traffic flow [6]. These metastable states exhibit a hysteresis phenomenon in the sense that minor perturbations of the cars in these states may eventually lead to a drastic change in the traffic throughput. As mentioned in [2], a property which may be related to the hysteresis phenomenon encountered with the metastable states is the so-called slow-to-start feature, which may be the key element which gives realistic macroscopic behavior to the cellular automaton model. Other slow-to-start models can be found in [3, 7, 8].


### 1.2. Description of the Model

We now describe the model of Gray and Griffeath used in this paper, which they callSlow-to-Start Traffic Cellular Automaton with Computable Throughput, which we will abbreviate SSTCACT. We divide an infinite one-lane “highway” into cells, or sites. The highway will be represented by a one-dimensional integer lattice. At time t=0 cars are placed on the lattice, with at most one car per site. The process evolves in discrete time. Write ξt(x)=1 if there is a car at site x at time t, and write ξt(x)=0 otherwise. At each time step, a car can move either zero units or one unit forward (positive direction), and the probabilities associated with movement are determined by the occupancy of the neighboring sites.More formally, we define{ξt}, t=0,1,2,…, with initial state ξ0, as follows. We write ξt={ξt(x)}x∈ℤ, which is the configuration at time t. Let ℱt be the σ-field generated by the collection {ξs}s=0t. Let Jtx denote the event that there is a car at site x at time t which moves to site x+1 at time t+1. Probabilities for car movement are assigned as follows:
(1)P(Jtx∣ℱt)={αifξt(x-1)=1,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=0γifξt(x-1)=1,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=11ifξt(x-1)=0,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=11ifξt(x-1)=0,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=00otherwise.
The parameters α and γ are in the interval [0,1], and the events Jtx, x∈ℤ, are to be conditionally independent given ℱt. The car movement probabilities define a time-homogeneous Markov process {ξt}t=0∞. Gray and Griffeath explain that α refers to the probability of “accelerating” and γ refers to the probability of moving in “congestion.”A simple way to think of the model is as follows. Each car has two coins: one which comes up heads with probabilityα and another which comes up heads with probability γ. At each time step, each car looks at the occupancy of the site behind it and the two sites in front of it. If, according to (1), the probability for movement is zero, the car does not move at the next time step. If the probability for movement is one, the car will move one unit forward at the next time step. If the probability for movement is α or γ, the car flips the appropriate coin to determine whether it moves at the next time step. In this case, if the coin comes up heads, then the car moves; if it comes up tails, the car does not move. All cars which are to move at a given time step do so simultaneously. Each coin flip is independent of past flips and independent of the coin flips of all other cars. This informal description of the model not only gives an easy way to think about car movement, it also allows us to identify cars from one time to the next in an obvious manner. Again, this model is the SSTCACT model of Gray and Griffeath [2]. The main result of this paper (Theorem 1) was stated in [2] but not proved.


## 1.1. Introduction

There have been various cellular automaton models introduced to model traffic flow [1–3]. Many of these models gain computational advantage over older so-called car-following, fluid dynamical, and kinetic (gas-type) models by discretizing both space and time (see [4] for an overview of various models). For these discrete models, simple rules are developed to govern car movement. While, on a small scale, the rules oversimplify traffic behavior, the goal is that large scale traffic phenomena, such as the formation and persistence of traffic jams, present themselves in this simplified approach.The model used in this paper is a discrete time probabilistic cellular automaton model developed by Gray and Griffeath in [2]. We will be concerned with macroscopic limiting phenomena on an infinitely long one-dimensional highway. In this paper, we show the existence of a limiting throughput (flux) of cars and describe these regions explicitly. For traffic densities above a critical value, we are able to show that the traffic organizes itself into regions of free flow and regions of traffic jam, both of which will be given precise mathematical definitions in this context. We also observe the existence of metastable states: conditions which allow certain ergodic traffic distributions to have higher throughput than others with the same density of cars. The existence of metastable states has been sought after [5] due to the fact that such states have been shown to be exhibited in real-world traffic flow [6]. These metastable states exhibit a hysteresis phenomenon in the sense that minor perturbations of the cars in these states may eventually lead to a drastic change in the traffic throughput. As mentioned in [2], a property which may be related to the hysteresis phenomenon encountered with the metastable states is the so-called slow-to-start feature, which may be the key element which gives realistic macroscopic behavior to the cellular automaton model. Other slow-to-start models can be found in [3, 7, 8].


## 1.2. Description of the Model

We now describe the model of Gray and Griffeath used in this paper, which they callSlow-to-Start Traffic Cellular Automaton with Computable Throughput, which we will abbreviate SSTCACT. We divide an infinite one-lane “highway” into cells, or sites. The highway will be represented by a one-dimensional integer lattice. At time t=0 cars are placed on the lattice, with at most one car per site. The process evolves in discrete time. Write ξt(x)=1 if there is a car at site x at time t, and write ξt(x)=0 otherwise. At each time step, a car can move either zero units or one unit forward (positive direction), and the probabilities associated with movement are determined by the occupancy of the neighboring sites.More formally, we define{ξt}, t=0,1,2,…, with initial state ξ0, as follows. We write ξt={ξt(x)}x∈ℤ, which is the configuration at time t. Let ℱt be the σ-field generated by the collection {ξs}s=0t. Let Jtx denote the event that there is a car at site x at time t which moves to site x+1 at time t+1. Probabilities for car movement are assigned as follows:
(1)P(Jtx∣ℱt)={αifξt(x-1)=1,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=0γifξt(x-1)=1,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=11ifξt(x-1)=0,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=11ifξt(x-1)=0,ξt(x)=1,ξt(x+1)=0,ξt(x+2)=00otherwise.
The parameters α and γ are in the interval [0,1], and the events Jtx, x∈ℤ, are to be conditionally independent given ℱt. The car movement probabilities define a time-homogeneous Markov process {ξt}t=0∞. Gray and Griffeath explain that α refers to the probability of “accelerating” and γ refers to the probability of moving in “congestion.”A simple way to think of the model is as follows. Each car has two coins: one which comes up heads with probabilityα and another which comes up heads with probability γ. At each time step, each car looks at the occupancy of the site behind it and the two sites in front of it. If, according to (1), the probability for movement is zero, the car does not move at the next time step. If the probability for movement is one, the car will move one unit forward at the next time step. If the probability for movement is α or γ, the car flips the appropriate coin to determine whether it moves at the next time step. In this case, if the coin comes up heads, then the car moves; if it comes up tails, the car does not move. All cars which are to move at a given time step do so simultaneously. Each coin flip is independent of past flips and independent of the coin flips of all other cars. This informal description of the model not only gives an easy way to think about car movement, it also allows us to identify cars from one time to the next in an obvious manner. Again, this model is the SSTCACT model of Gray and Griffeath [2]. The main result of this paper (Theorem 1) was stated in [2] but not proved.


## 2. Formal Statement of Results

Since one of the main goals in traffic modeling is to demonstrate the most efficient way for traffic to flow under given restrictions, one of the statistics of interest in analyzing any traffic model is the measure of throughput, or flux through a given location. We will consider only initial distributions of cars which are ergodic in space; that is,{ξ0(x)}x∈ℤ is an ergodic sequence. By the ergodic theorem, for each initial distribution there is a well-defined spatial density ρ of cars, given by
(2)ρ:=limN→∞12N+1∑x=-NN‍ξ0(x).
Because cars can move at most one unit per time step, the ergodicity of the configurations is preserved at all finite times (cf. [9, Theorem  4.15]). That is, {ξt(x)}x∈ℤ is an ergodic sequence for any time t. Since cars are neither created nor destroyed, the spatial density ρ is preserved. For a fixed initial distribution μ, we will say that the traffic model has throughput θ=θ(μ) given by
(3)θ=limt→∞1t∑s=0t-1‍1{ξs(0)=1,ξs+1(0)=0}
if such a limit exists.We introduce a critical valueρ* as
(4)ρ*=sup{ρ:θ(μ)=ρ∀ergodicμwithdensityρ}.
This is called the maximal free flow density, the highest density of cars in which the throughput and the density are equal for every ergodic initial configuration. If the throughput equals the density, we say the system has achieved permanent free flow.In this paper we calculate the throughput forα∈[0,1] and γ∈[0,1). The special case γ=1 is treated in Theorem 1, part (b) of [2], and it turns out that the throughput obeys the formula (5) of Theorem 1 given in this paper, although the proof is different.We state our first result.Theorem 1.
For the SSTCACT model defined above, with parametersα∈[0,1] and γ∈[0,1) and ergodic initial distribution μ with density ρ, the throughput almost surely exists and is as follows:
(5)(i)if0≤ρ≤ρ*,thenθ=ρ,(ii)if12<ρ≤1,thenθ=(1-ρ)α1+α-γ,(iii)ifρ*<ρ<12,theneitherθ=ρorθ=(1-ρ)α1+α-γaccordingtowhetherornotpermanentfreeflowisachieved.
The maximal free flow densityρ* is given by
(6)ρ*=α2α+1-γ.A pictorial representation of the function (5) is given in Figure 1, which is the so-called fundamental diagram for this model. This sketch has the typical “reverse lambda” shape which appears in the simulation results of most traffic models and in real-world traffic.Figure 1
The fundamental diagram which shows the throughput as a multivalued function of the density, depending on the ergodic initial configuration. The parameters chosen for this sketch areα=0.3 and  γ=0.4.Before continuing, we state an example of how each point on the fundamental diagram can be achieved. If we begin with an initial distribution which puts weight 1/2 on the configuration that has cars at every even numbered site (and no cars at odd numbered sites) and weight 1/2 on the configuration with cars at odd numbered sites, then each car will move deterministically, giving throughput of 1/2. Doing a “thinning” of this initial distribution we can create distributions for whichθ=ρ for any ρ≤1/2.In order to give an example of an initial distribution for each point on the bottom branch of the fundamental diagram, we turn to Bernoulli product measure. We will show the following.Theorem 2.
Ifμ is Bernoulli (ρ), then
(7)θ={ρif0≤ρ≤ρ*(1-ρ)α1+α-γifρ*<ρ≤1,
with ρ* as in (6).The multivalued function forθ gives rise to metastability, in the sense that rearranging the cars while preserving the density and ergodic structure may result in an eventual lowering of the throughput, which is known as a hysteresis phenomenon.Finally, we are able to fully describe the configurations which arise in the time limit if there is no permanent free flow.Theorem 3.
If there is no permanent free flow (i.e.,θ<ρ), then the distribution of cars in SSTCACT converges to
(8)aνf+(1-a)ν1,
where ν1 is the law which places cars at each site, νf is the law which places cars according to the renewal process described in Section 3.3, and
(9)a=(1-ρ)2α+1-γα+1-γ.The bulk of this paper is dedicated to the proof of Theorem1. In Section 3, we give the ideas behind the proof of Theorem 1, build some terminology, and examine how cars exit traffic jams. In Section 4 we prove all three theorems simultaneously.


## 3. The Ideas behind the Proof of Theorem1

Before even attempting to give a formal proof of Theorem1, we make some general comments to help the reader. To begin, we observe right away that (i) in (5) is a trivial consequence of the definition of ρ*. If there is permanent free flow, then θ must equal ρ, so half of (iii) in (5) is trivial. Since there cannot be permanent free flow when ρ>1/2, the fact that θ must be less than ρ in this region (contained in statement (ii)) is obvious. Therefore, in order to prove Theorem 1, we must address what lack of permanent free flow looks like and under what conditions it is achieved.


### 3.1. Terminology

To proceed, we must first build some terminology. A car at sitex is said to be in free flow at a discrete time t if it will be at site x+1 at time t+1 with probability one. Two cars are adjacent if they occupy consecutive sites on the lattice. A block of cars is a maximal collection of consecutive adjacent cars. The last (leftmost) car in a block will be said to be an LCB (last car in a block). There is an obvious way to identify a block at time t+1 with a block at time t by declaring the two blocks to be the same if the block at time t+1 contains the LCB of the block at time t. A block is said to dissolve at time t if there is a block of size two at time t-1 and the trailing car is no longer adjacent to any car at time t. The word block may be used, when no confusion will result, to refer either to the sites that the cars occupy or to the cars themselves.


### 3.2. Flow in and out of Blocks

Consider what happens when several cars occupy adjacent sites. Aside from the rightmost car in a block, none of the cars have any possibility of movement according to (1). Indeed, we think of these cars as being stuck inside a traffic jam. The rightmost car in a block will move forward one site with a probability determined by flipping an appropriate coin which turns up heads with either probability α or γ, depending on the situation. In short, cars peel out of a block one by one from the front, and no car can move in a block until it reaches the front. Thus, there are two main aspects which are key to the analysis of this model: how do cars exit a block and how do cars enter a block?The latter question is easier to answer than the former. Cars in free flow enter a block by moving deterministically until they are themselves part of the block.The more complicated aspect of the process evolution is the manner in which cars leave a block. Imagine a block of cars at a timet with no cars in front of it. At each time step, the leading car in the block flips a coin to determine whether it will move forward. If the coin lands on heads, which happens with probability α, the car moves. Otherwise, the car remains at the same site. Once the first car moves, there is a gap of size one between it and the second car, which is now at the front of the block. Now the second car must flip a γ coin to determine whether it will move forward at time t+2. If it does move forward at time t+2, then the third car will flip a γ coin to determine its movement. If the second car does not move forward at time t+2, then it will flip an α coin to determine its movement at time t+3, because the first car will move another space ahead at time t+2. In summary, the first car in a block flips an α coin to determine when it moves. After that, the car behind it will flip a γ coin to determine movement. Each successive car will flip γ coins until the first tails is flipped. As soon as a car flips tails, then the first car in the block will again begin to flip α coins. This will allow the manner in which cars exit blocks to determine the structure of the free flow regions.


### 3.3. A Renewal Process

Let us make the last paragraph more formal. It is natural to define a renewal process associated with the front of a block. For a fixed block of cars, letTk be the kth time at which the rightmost car in the block does not move forward. Let N(k) be the number of cars which were emitted from the front of the block between times Tk-1 and Tk. We will say that these cars are in the same regular pack. Then the times Tk are the renewal times in a renewal reward processes in which the kth reward is N(k). The process ends when the block dissolves. The probability that N(k)=n is αγn-1(1-γ) for n≥1, and P(N(k)=0)=1-α. Therefore, the expected number of cars emitted in a regular pack is given by
(10)∑n=1∞‍nαγn-1(1-γ)=α1-γ.A standard result from renewal reward theory states that the average reward per unit time is given by the average reward divided by the average time between renewals. In our context, the average reward per unit time is the average number of cars emitted from a block per unit time, which is the density of cars emitted from the block. Since each of the cars in the pack are separated by one space, with one extra space at the left end, the average distance between the first car emitted in a pack and the first car in the next pack is(11)2(α1-γ)+1=2α+1-γ1-γ,
which can be thought of as the length of the pack. Therefore, the density of cars distributed as packs is given by the average number of cars in a pack divided by the length of the pack, which gives
(12)ρf:=α2α+1-γ.
Notice this quantity ρf is what we claim as ρ*.The definition of the term “pack” must be clarified when the emitted cars cause the block to dissolve. Suppose there are only two cars left in a block at timet. Once the first car moves, the second car will follow with probability 1, rather than flipping a γ coin. We say that the second car is emitted from the block in the same pack as the first car. Since the block is now dissolved, there can be no more cars emitted as part of the same pack. Since this special type of car will need to be addressed several places later, we call any car which exits a block without flipping heads on a coin (either α or γ) a tailgater. Such a car will continue to be referred to as a tailgater until it enters another block. We will use the phrase “regular pack” to refer to a pack without a tailgater.Finally, we define thesequence corresponding to the cars emitted from a block after time t as follows. Suppose this block occupies sites [y0,x0] at time t. If there were no cars in front of this block, the cars emitted from this block would continue in free flow indefinitely. Pretending this is the case, we define this sequence {zn} so that zn=ξt+s(x0+s-n) for any s>n. That is, the sequence is defined using what would be the string of cars emitted from a block if there were no cars in front of it. We say the (random) sequence corresponding to the cars in regular packs has a pack distribution.


### 3.4. Outline of Proof of Theorems

To prove Theorem1, we must do the following. We must show that if ρ is less than the pack density of (12), there will be permanent free flow (done in Section 4.3) and if ρ is greater than this density, there will not be permanent free flow for some initial distributions (done by proving Theorem 2 in Sections 4.5 and 4.6). This will establish the value of ρ*. The idea is that if ρ<ρf, there cannot be a positive fraction of cars in blocks at all times because that would cause the free flow region to have a density which is too high. And if ρ>ρf and all of the cars find themselves in blocks at some point, the free flow region will not have a high enough density to support an overall density ρ, so there must be blocks in the system at all times.We must also show that the limiting throughput exists (in Section3). If there is permanent free flow, the existence of throughput is trivial. If not, we show that the boundaries of the blocks behave somewhat like a random walk, so that each site witnesses a limiting flux.


## 3.1. Terminology

To proceed, we must first build some terminology. A car at sitex is said to be in free flow at a discrete time t if it will be at site x+1 at time t+1 with probability one. Two cars are adjacent if they occupy consecutive sites on the lattice. A block of cars is a maximal collection of consecutive adjacent cars. The last (leftmost) car in a block will be said to be an LCB (last car in a block). There is an obvious way to identify a block at time t+1 with a block at time t by declaring the two blocks to be the same if the block at time t+1 contains the LCB of the block at time t. A block is said to dissolve at time t if there is a block of size two at time t-1 and the trailing car is no longer adjacent to any car at time t. The word block may be used, when no confusion will result, to refer either to the sites that the cars occupy or to the cars themselves.


## 3.2. Flow in and out of Blocks

Consider what happens when several cars occupy adjacent sites. Aside from the rightmost car in a block, none of the cars have any possibility of movement according to (1). Indeed, we think of these cars as being stuck inside a traffic jam. The rightmost car in a block will move forward one site with a probability determined by flipping an appropriate coin which turns up heads with either probability α or γ, depending on the situation. In short, cars peel out of a block one by one from the front, and no car can move in a block until it reaches the front. Thus, there are two main aspects which are key to the analysis of this model: how do cars exit a block and how do cars enter a block?The latter question is easier to answer than the former. Cars in free flow enter a block by moving deterministically until they are themselves part of the block.The more complicated aspect of the process evolution is the manner in which cars leave a block. Imagine a block of cars at a timet with no cars in front of it. At each time step, the leading car in the block flips a coin to determine whether it will move forward. If the coin lands on heads, which happens with probability α, the car moves. Otherwise, the car remains at the same site. Once the first car moves, there is a gap of size one between it and the second car, which is now at the front of the block. Now the second car must flip a γ coin to determine whether it will move forward at time t+2. If it does move forward at time t+2, then the third car will flip a γ coin to determine its movement. If the second car does not move forward at time t+2, then it will flip an α coin to determine its movement at time t+3, because the first car will move another space ahead at time t+2. In summary, the first car in a block flips an α coin to determine when it moves. After that, the car behind it will flip a γ coin to determine movement. Each successive car will flip γ coins until the first tails is flipped. As soon as a car flips tails, then the first car in the block will again begin to flip α coins. This will allow the manner in which cars exit blocks to determine the structure of the free flow regions.


## 3.3. A Renewal Process

Let us make the last paragraph more formal. It is natural to define a renewal process associated with the front of a block. For a fixed block of cars, letTk be the kth time at which the rightmost car in the block does not move forward. Let N(k) be the number of cars which were emitted from the front of the block between times Tk-1 and Tk. We will say that these cars are in the same regular pack. Then the times Tk are the renewal times in a renewal reward processes in which the kth reward is N(k). The process ends when the block dissolves. The probability that N(k)=n is αγn-1(1-γ) for n≥1, and P(N(k)=0)=1-α. Therefore, the expected number of cars emitted in a regular pack is given by
(10)∑n=1∞‍nαγn-1(1-γ)=α1-γ.A standard result from renewal reward theory states that the average reward per unit time is given by the average reward divided by the average time between renewals. In our context, the average reward per unit time is the average number of cars emitted from a block per unit time, which is the density of cars emitted from the block. Since each of the cars in the pack are separated by one space, with one extra space at the left end, the average distance between the first car emitted in a pack and the first car in the next pack is(11)2(α1-γ)+1=2α+1-γ1-γ,
which can be thought of as the length of the pack. Therefore, the density of cars distributed as packs is given by the average number of cars in a pack divided by the length of the pack, which gives
(12)ρf:=α2α+1-γ.
Notice this quantity ρf is what we claim as ρ*.The definition of the term “pack” must be clarified when the emitted cars cause the block to dissolve. Suppose there are only two cars left in a block at timet. Once the first car moves, the second car will follow with probability 1, rather than flipping a γ coin. We say that the second car is emitted from the block in the same pack as the first car. Since the block is now dissolved, there can be no more cars emitted as part of the same pack. Since this special type of car will need to be addressed several places later, we call any car which exits a block without flipping heads on a coin (either α or γ) a tailgater. Such a car will continue to be referred to as a tailgater until it enters another block. We will use the phrase “regular pack” to refer to a pack without a tailgater.Finally, we define thesequence corresponding to the cars emitted from a block after time t as follows. Suppose this block occupies sites [y0,x0] at time t. If there were no cars in front of this block, the cars emitted from this block would continue in free flow indefinitely. Pretending this is the case, we define this sequence {zn} so that zn=ξt+s(x0+s-n) for any s>n. That is, the sequence is defined using what would be the string of cars emitted from a block if there were no cars in front of it. We say the (random) sequence corresponding to the cars in regular packs has a pack distribution.


## 3.4. Outline of Proof of Theorems

To prove Theorem1, we must do the following. We must show that if ρ is less than the pack density of (12), there will be permanent free flow (done in Section 4.3) and if ρ is greater than this density, there will not be permanent free flow for some initial distributions (done by proving Theorem 2 in Sections 4.5 and 4.6). This will establish the value of ρ*. The idea is that if ρ<ρf, there cannot be a positive fraction of cars in blocks at all times because that would cause the free flow region to have a density which is too high. And if ρ>ρf and all of the cars find themselves in blocks at some point, the free flow region will not have a high enough density to support an overall density ρ, so there must be blocks in the system at all times.We must also show that the limiting throughput exists (in Section3). If there is permanent free flow, the existence of throughput is trivial. If not, we show that the boundaries of the blocks behave somewhat like a random walk, so that each site witnesses a limiting flux.


## 4. Proof of Theorems

We prove the three theorems simultaneously. The theorems would be much easier to prove if not for the presence of tailgaters. In the next subsection, we show that their presence in some sense does not significantly alter the makeup of the free flow regions.


### 4.1. Dealing with Tailgaters

The first lemma makes use of the fact that if one car enters permanent free flow (never again enters a block), then all cars must enter permanent free flow. This fact is a direct consequence the translation invariance. Furthermore, by the ergodicity of the configuration at each time, there is a zero-one law about entering permanent free flow; the probability of entering permanent free flow (for any car) is either zero or one.To show that the throughput exists, we first state and prove a lemma about the limiting density of LCBs (last cars in a block).Lemma 4.
The following are true.(i)
The spatial density of LCBs decreases to zero.(ii)
If no car enters permanent free flow, the spatial density of tailgaters goes to zero as time goes to infinity.Proof.
For (i), we first observe that blocks cannot be created. Because of this, the spatial density of LCB cars (last cars in a block) does not increase in time and therefore converges to a limit. Suppose the limiting density of LCBs wereδ>0. In order for LCBs to have density at least δ, at least half of the LCBs must be within distance 2/δ of nearest LCB to the right, which means that these blocks have length no more than 2/δ. There is a positive probability that any given one of these blocks will dissolve in the next 2⌈2/δ⌉ time steps by emitting one large pack along with the event of no cars entering the block. This would reduce the density of LCBs. Since this argument can be iterated indefinitely, the density of LCBs cannot remain above δ, which gives the contradiction.
For (ii), recall that when a tailgater reaches another block, the car loses its tailgater status. Since we assume no car will enter permanent free flow, each tailgater will hit another block and thus cease being a tailgater. Letw(t) be the density of cars which become tailgaters at some point after time t, and let b(t) be the density of LCBs at time t, which converges to 0 from (i). Fix an ϵ>0 and time t0 large enough so that b(t0)<ϵ. Since each car which becomes a tailgater is an LCB of a dissolving block, we get that the density of tailgaters created after time t0 cannot be more than the density of LCBs which will vanish after time t0. Therefore, w(t0)<ϵ.
Finally, leta(t) be the density of tailgaters at time t. For any t>t0 we can decompose a(t) into those tailgaters which have been tailgaters since time t0 and those which were created after time t0. Since every car (in particular the tailgaters) will enter a block infinitely often, we can find a time t1≥t0 such that the density of cars which have been tailgaters for the entire time interval [t0,t1] is less than ϵ. Since the tailgater cars which are created after time t0 have density less than ϵ, we get that a(t)<2ϵ for t>t1.Lemma 5.
Let{Zn} be the sequence corresponding to the cars emitted from a block which dissolves at time t. Suppose Zm=1 represents the tailgater car so that Zm+1=0 represents the space behind the tailgater car, and {Zm+k}k=1∞ is the sequence of cars behind the tailgater. Then there is a random N for which the sequence
(13)Z1,Z2,…,Zm-1,Zm+N,Zm+N+1,…
is distributed as a regular pack, as described in Section 3.3. Furthermore, N remains bounded in expected value as t goes to infinity.Before proving this lemma, we observe an immediate corollary. We call the finite subsequenceZm,Zm+1,…,Zm+N-1 from the lemma an exceptional subsequence.Corollary 6.
Upon removing the exceptional subsequences from the free flow region, what remains has a pack distribution as in the renewal process of Section3.3.The corollary is obtained by observing that the free flow space can be divided into two parts: cars that have never been in blocks and the part described by the lemma. The exceptional subsequences mentioned in the corollary will be used later to understand the free flow regions. Denote byN0 an upper bound on their expected length.Proof of Lemma5.
We break this proof into two cases. First, we show the lemma under the additional assumption that the car which eventually becomes the tailgater in the dissolving block has occupied the site adjacent to the car following it at some time in the past; lets be the most recent such time. Without loss of generality, suppose that at time s, the dissolving block occupies sites y0,y0+1,…,x0, the car which will eventually become the tailgater is at site 0, and that there are k cars between site 0 and site y0. We will couple ξt with another SSTCACT process ξ~ as follows. Set
(14)ξ~s(x)={1x≤x0-y0+k+1ξs(x0+2)x=x0-y0+k+30otherwise.
Then, we use the following coupling. We first assign each car in ξ~ a partner in ξ. The rth car to the right of site -1 at time s in ξ~ is partnered with the rth car to the right of site 0 at time s in ξ, for r=1,…,x0-y0+k+1. The rth car to the left of site 0 at time s in ξ~ is partnered with the rth car to the left of site 0 at time s in ξ, for r=1,2,…. The only car in or behind the dissolving block in ξ that is not partnered with a car in ξ~ is the car at site 0: the car which becomes the tailgater. The coupling is defined according to the following rule: the coins flipped by cars in the ξ~ process as they leave the block will be tied to the coins that their partners in the ξ process use when they leave a block for the last time (if a car in ξ leaves multiple blocks, we perform the coupling using the last block they left).
The cars in front of the tailgater inξ will all be emitted from the dissolving block. Due to the coupling, they are emitted following the same sequence as their partners in ξ~, which follows a pack distribution. The car which is at site -1 in ξ~ at time s will remain there until time t, at which time it will flip a γ coin to determine its movement. By the coupling, this coin flip is tied to the coin flip of the car at site -1 the ξ process at the time it leaves the last block. In order for the dissolving block to dissolve, the result of this coin flip must be tails: both cars remain in position one time step and flip an α coin for the next time step. Therefore, by setting N=1 in the statement of the lemma one can observe that the sequence of cars generated in ξ, after having removed the tailgater, is the same as the sequence in ξ~, which has the pack distribution.
Now suppose that the car which eventually becomes the tailgater in the dissolving block has never occupied the site adjacent to the car following it at any point before timet. In this case, set s to be the time when the tailgater car joins the dissolving block. If we label the location of the dissolving block as [y0,x0], the location of the front of the closest block behind it which does not dissolve before time t as 0 and the number of cars between these two blocks at k, we can set up a coupling process exactly as in (14). The coupling, however, will be slightly different.
As before, we assign each car inξ~ a partner in ξ. The rth to the right of site k at time s in ξ~ is partnered with the rth car to the right of site x0 at time s in ξ, for r=1,…,x0-y0-1. The rth car to the left of site 0 at time s in ξ~ is partnered with the rth car to the left of site 0 at time s in ξ, for r=0,1,…. Now many cars in the ξ process do not have a partner: all of the cars between the tailgater and the car which is at the front of the previous block at time s.
We perform the coupling in the same way as in the previous case: the coins flipped inξ~ are tied to the partner car's flips in ξ as they leave the last block. Then it is clear that the way in which the cars at sites [x0,y0] at time s in ξ flow from the dissolving block is the same as the way in which cars flow from the front of the block in ξ~, due to the coupling. This is also clear for cars which begin at sites less than or equal to -1 in both processes at time t. Therefore, if we denote Zm=1 to represent the tailgater car, Zm+1=0 to represent the space behind the tailgater car, Zm+N-2=1 to denote the car which is at site 0 at time s in ξ, and Zm+N-1 to represent the space behind this car, we can conclude that the sequence Z1,…,Zm-1,Zm+N,… is an example of the renewal reward process. In order to complete the lemma, we must show that E[N] remains bounded with time in this case.
By construction,N here is at most x0+1, the distance between the tailgater and the car at site -1 at time s in ξ. This is the distance between the tailgater and the car which is behind the car behind it, given that the tailgater and the car behind it have never occupied adjacent sites. Since the car behind it has then moved in free flow since its initial movement, the size of these gaps cannot increase in time, so E[N] remains bounded.


### 4.2.  Proof That Throughput Exists

We now turn to proving the existence of throughput from Theorem1. For convenience, we define
(15)ξtf(x)=(ξt(x))(1-ξt(x-1))(1-ξt(x+1)),ξtl(x)=(ξt(x))(ξt(x-1))(1-ξt(x+1)),ξtb(x)=(ξt(x))(1-(1-ξt(x-1))(1-ξt(x+1))).
Under these definitions, ξtf(x) is 1 if and only if there is a car at x at time t which is in free flow, ξtl(x) is 1 if and only if there is a car at x at time t which is the leading car in a block, and ξtb(x) is 1 if and only if there is a car at x at time t which is in a block.Lemma 7.
The throughputθ is almost surely given by the limiting density of cars which are in free flow. That is, if we set ρtffc to be the spatial density of free flow cars at time t, then almost surely θ=limt→∞ρtffc(ω).Proof.
There is no throughput within the blocks, aside from the possible movement of the leading car in the block. The law of large numbers gives(16)θ=limt→∞1t∑s=0t-1‍(1{ξsf(0)=1}+1{ξsl(0)=1,ξs+1l(0)=0})=limt→∞1t∑s=0t-1‍(1{ξsf(0)=1}+α1{ξsl(0)=1})
almost surely.
By Lemma4, the observed density of cars at the front of blocks goes to zero as time goes to infinity; hence the α1{ξsl(0)=1} term, due to dividing by t, does not contribute to the throughput. Therefore, the throughput is simply
(17)θ=limt→∞1t∑s=0t-1‍ξsf(0)
if the limit exists. In order to show the lemma, we must show that this time average is equal to the limiting spatial density of cars that are in free flow.
When all cars go into permanent free flow,θ=ρ trivially, so θ exists and is equal to the limiting density of cars that are in free flow. Now suppose that no cars enter permanent free flow.
Without loss of generality we may assume that site 0 is in a block at time 0. We will denote byAi the amount of time that site zero spends in the ith block it enters after time 0 and let Bi be the amount of time it spends in the ith free flow region it enters after time 0. More precisely, we set A1=m if ξt(0)=1 for t=0,1,…,m-1 and ξm(0)=0; we set B1=n if ξt(0)ξt(1)=0 for t=A1,A1+1,…,A1+n-1 and ξA1+n(0)ξA1+n(1)=1. We set t1=A1+B1 and define inductively: Ai=m if ξt(0)=1 for t=ti-1,ti-1+1,…,ti-1+m-1 and ξti-1+m(0)=0; and set Bi=n if ξt(0)ξt(1)=0 for t=ti-1+Ai,ti-1+Ai+1,…,ti-1+Ai+n-1 and ξti-1+Ai+n(0)ξti-1+Ai+n(1)=1, with
(18)ti=ti-1+Ai+Bi.
The sequence of times ti indicate the times in which the site 0 enters the ith block. Another way to write ti is
(19)ti=∑j=1i‍(Aj+Bj).
We think about how the site 0 can “enter” a block, that is, transition from being in a free flow region at timet to being in a block at time t+1. This is possible only if site 1 is in a block at time t and there is a car at site -1 at time t which enters the block. Thus, we can think of the site 0 as entering the back of a block. Site 0 will exit the block only after all of the cars in the block in front of site 0 are emitted from the block as part of regular packs. Therefore, the expected amount of time it will take for site 0 to exit a block after it enters is the average rate at which cars exit from the front of the block times the length of the block. A similar statement can be made about free flow regions drifting through the site 0.
The blocks and the free flow regions are changing in size over time. However, once nearly all of the cars have been in blocks, roughly speaking, the effect of the tailgaters becomes negligible, so the input and output mechanisms for the blocks are free flow cars which are emitted as regular packs. Since the number of cars leaving a block and the number of cars entering a block obey the same laws, the fluctuations in size of the blocks (and free flow regions) obey properties of an unbiased random walk.
Formalizing this discussion, consider the block which site 0 enters at timeti; call it D. Let {Yt} be the sequence corresponding to the cars emitted from this block and let {Xt} be the sequence corresponding to the cars entering the block. The size of this block at time ti is the sum of the size of that block at time 0 with the difference between the sums of the sequences {Xt} and {Yt} to time t0. By Lemma 5, the sequence {Xt} can be expressed as a sequence distributed as regular packs with some exceptional subsequences inserted. Let Ni be the length of the ith such subsequence and let {X^t} be the sequence {Xt} with the exceptional subsequences removed. We have
(20)(lengthofDattimeti)=(lengthofDattime0)+∑‍X^i-∑‍Yi+∑‍Ni,
where the sums are to be taken over all time indices less than ti. By Lemmas 4 and 5 and its corollary, for any positive ϵ the number of terms in ∑‍Ni is eventually less than ϵti as ti→∞, and each of the Ni is bounded by N0<∞ in expected value. The middle two terms on the right side are the difference of two sequences with the same law hence behave like a random walk conditioned to stay positive until time ti. Therefore, we can find constants c1and c2 such that
(21)c1tiloglogti<Ai<c2tiloglogti+ϵN0ti
for all times ti sufficiently large. By a similar reasoning, at the expense of perhaps picking different constants, we can replace Ai in (21) with Bi.
Returning to (17), we will first show that the fraction of time site 0 finds itself in a block tends to a limit. We have that
(22)limsupt→∞1t∑s=0t-1‍ξsb(0)=limn→∞1tn-1+An∑i=1n‍Ai,liminft→∞1t∑s=0t-1‍ξsb(0)=limn→∞1tn∑i=1n‍Ai;
we would like to show that these are the same. The difference between the two can be written:
(23)limn→∞tn-(3/4)∑‍Aitn-1/tn1/4Bn+An/Bntn1/4.
Since ∑‍Ai<tn, we find that the numerator of this fraction goes to zero. The first term in the denominator can be expressed as
(24)tn-1(tn-1+An+Bn)1/4Bn.
By (21), this quantity can be made arbitrarily large almost surely by making ϵ small, giving that difference between the limsup and liminf is almost surely zero. Therefore,
(25)limt→∞1t∑s=0‍t-1ξsb(0)
exists almost surely.
Because of this, the limiting fraction of time that site 0 spends in free flow also exists, almost surely. Again using the argument that the free flow space, as time goes to infinity, is made up of primarily pack distribution as time goes on, we will get our result. Formally, we write(26)ξsf(0)=1{carfromregularpackat0attimes}+1{carfromexceptionalsequenceat0attimes}.
The density of cars from exceptional sequences has been shown to approach zero, so upon dividing by t, we get that
(27)limt→∞1t∑s=0t-1‍ξxf(0)
exists and equals limt→∞ρtfft, and the proof of Lemma 7 is complete.


### 4.3. Outline of Proof Thatρ*=ρf

Recall that the density of free flow cars emitted from a block as regular packs, which we labelρf in (12), is exactly what we claim as ρ*, the maximal free flow density from Theorem 1. Therefore, we must justify why the quantity ρf should be ρ*.The general idea is as follows. Since cars do not move when they are in blocks, there is no throughput within the blocks. Therefore, the entire contribution to the throughput must come from the free flow regions. If all cars enter blocks at some point, then all cars are eventually emitted as part of a pack. Therefore, there is a certain density of free flow cars which cannot be surpassed, provided all cars enter blocks. Loosely speaking, in order to conclude thatρf=ρ*, we must show that there is an initial distribution which will force all cars to enter blocks if the density is greater than ρf, that all cars will enter permanent free flow if the density is less than ρf, and that the presence of tailgaters does not profoundly change the calculations. These general ideas will be made precise throughout the rest of this section.We will divide the proof ofρ*=ρf into two parts. For the first half of the proof we must turn to showing that ρ*≥ρf. The formal proof of this, given in Section 4.4, is borrowed almost completely from the paper of Gray and Griffeath [2]. To show ρ*≥ρf, we assume ρ>ρ* and show that this implies ρ>ρf. The basic idea of the proof is to show that the expected distance between two cars cannot be too far apart when cars are forced to run into blocks (because ρ>ρ*).Second, we will show thatρ*≤ρf. To do this, we prove Theorem 2, showing that if μ is a Bernoulli product measure distribution with density ρ with ρ>ρf then it must be the case that ρ>ρ*. The proof of this is in Section 4.5.


### 4.4. Proof Thatρ*≥ρf

We seek to proveρ*≥ρf. The proof given here is a modification of the proof given for general cruise control systems in the Gray-Griffeath paper [2].Assumeρ>ρ*. We seek to show that ρ>ρ* implies that ρ≥ρf. We condition on the event that a car starts at the origin at time 0. Let Xt be the position of that car at time t and let Yt be the position of the next car to the right of the car at Xt. The ergodic theorem tells us that E[Yt-Xt]=1/ρ for all t. For 0≤s<t, define the following events:
(28)At={Yt-Xt=1},Bs,t={Ys-Xs=1,Yu-Xu>1fors<u≤t},Ct={Yu-Xu>1for0≤u≤t}.Since we assume thatρ>ρ*, the probability of the event that the car that starts out at the origin stays in free flow goes to zero as time goes to infinity, so P(Ct)→0. Thus,
(29)1ρ=limt→∞E[Yt-Xt]=limt→∞1·P(At)+∑s=0t‍P(Bs,t)E[Yt-Xt∣Bs,t].SinceE[Yt-Xt∣Bs,t]>1 for all s and t, if we could show that
(30)E[Yt-Xt∣Bs,t]≤2α+1-γα
for all s and t, we would then get that
(31)1ρ≤2α+1-γα,
which is the desired conclusion.Thus, we turn to proving (30). As in [2], we will actually prove
(32)E[Yt-Xt∣Bs,t,Yt-Ys,ℱs]≤2α+1-γα,
where ℱs is the σ-field generated by the processes up to time s.Since we are assuming thatYs+1-Xs+1>1, there is a vacancy to the right of the car at position Xs+1 at time s+1. If there is also vacancy to the left of that car, then the car at position Xs+1 will move in free flow. In order to have the event Bs,t hold, we must have Yt-Xt=2 in this case. Since 2≤(2α+1-γ)/α, we can restrict our attention to the case where there is a car immediately to the left of the car at site Xs+1 at time s+1.SinceYs-Xs=1 and Ys+1-Xs+1>1, we must have that the car at site Ys moved at time s+1 but the car at site Xs did not. Therefore, in order for the car at site Xs+1 to move at time s+2, the car must flip heads on a γ-coin.LetK=(t-s)-(Yt-Ys), the number of times that the leading car (denoted by the letter Y) did not move in the time interval [s,t]. Because θ<ρ, we are guaranteed a density of cars in the system, bounded away from zero, which are in blocks at any given time. Along with Lemma 4, this tells us that the average block size is nondecreasing in time. Therefore, we can be assured that as time goes on it becomes very unlikely that the car at position Y will pass through an entire block between time s and time t with the car behind it not reaching that block. Therefore, with probability that goes to one, we either have that the leading car is at the left edge of a block at time t-K (and still at time t), or K=0. If the event Bs,t occurs, then the car at site Xs+1 must flip tails at times s+2,s+3,…,s+K, because there is no way for the gap between the two cars to grow once the trailing car enters free flow. Thus, if these flips were not all tails, there would be a time u with s<u≤t with Yu-Xu=1.After times+K, the coin tosses made by the car at site Xs+K are independent of Bs,t and Yt-Ys, since there is no way that this car could catch up to the car at site Ys+K in the next t-s-K time steps to affect its movement. Therefore, Yt-Xt=2+N, where N represents the number of consecutive tails beginning with time s+K+1 tossed by the car which began at the origin. The random variable N is independent of Bs,t, Yt-Ys, and ℱs. Therefore,
(33)E[Yt-Xt∣Bs,t,Yt-Ys,ℱs]=2+E[N].We can decompose the value ofE[N] according to whether or not the leading car hits a block before time t as follows:
(34)E[N]=E[N∣K=0]·P(K=0)+E[N∣K>0]·P(K>0).
We have already argued in Lemma 4 that the probability of a car being at the edge of a block goes to zero as time goes to infinity independently of N. Thus, as time goes to infinity, P[K>0]→0. Therefore, we only need to look at E[N∣K=0].In that case,N=0 means the car at site Xs+1 moved at time s+2 despite having a car immediately behind it and 2 sites in front of it. This happens with probability γ. If N>0, then the car at site Xs+1 did not move at time s+2 (which happens with probability 1-γ), did not move at the next N-1 steps (which happens with probability 1-α at each time step), but did move on the (N+1)st time step (with probability α). Thus,
(35)E[N]=∑i=1∞‍i(1-γ)(1-α)i-1α=1-γα.Thus,1/ρ≤2+(1-γ)/α, which gives the desired inequality, thus completing the proof that ρ*≥ρf.


### 4.5. Start of Proof of Theorem2

In this section, we establish the existence of ergodic initial distributions which lack permanent free flow for any densityρ greater than ρf. Such an example is the Bernoulli product measure family of distributions.Lemma 8.
When the initial distributionμ is Bernoulli product measure with density ρ, ρ>ρf, each car is in a block at some time t≥0 with probability one; no car enters permanent free flow.Proof.
Since we are assuming that the initial distribution is a Bernoulli product measure, we can guarantee that there are arbitrarily long blocks in the initial configuration. Since a block can dissolve only linearly in time, we can guarantee blocks of arbitrary length at any finite timet≥0.
By Lemma4, we are able to fix a time T≥0 so that the density LCBs is less than (1/8)(ρ-ρf). At this time T, we will consider a block which has the following properties. Recall we have assumed that ρ>ρf.
Property A. Let x be the site which is at the front of this block. For any y<x, the spatial density of cars in the interval [y,x] is ≥(1/2)(ρ+ρf).
Property B. Let y′ be the site occupied by the LCB (last car in the block). For any z′<y′-4/(ρ-ρf), the density of LCBs in the interval [z′,y′] is less than (1/4N0)(ρ-ρf), where N0 is a bound on the expected length of the exceptional subsequences from Lemma 4.
We claim that there are infinitely many blocks which possess both of these properties. To see this claim for Property A, suppose on the contrary that there are not any blocks with Property A at a given time. Fix a blockB1, and let x1 be the site of the first car in block B1 at this given time. By our assumption, there exists a site y1<x1 so that the density of cars in the interval [y1,x1] is less than (1/2)(ρ+ρf). Now let x2≤y1 be the largest site index less than or equal to y1 which marks the front of another block, which we call B2. We iterate this construction to obtain an infinite collection of intervals {[yi,xi]}. Let S be the union of these intervals. By construction, the density of cars in S is less than (1/2)(ρ+ρf). The set (-∞,x1]∖S is a set of sites which are not in blocks at the given time. Any cars in these sites were either emitted from blocks as part of packs (in which case, by Lemma 4, their density becomes asymptotically close to ρf) or they have never been in a block (in which case they occur with density ρ according to the Bernoulli product measure). In either case, the density of cars in this region is at most ρ. Combining these facts shows that the density of cars in the interval (-∞,x1] is less than ρ, which is a contradiction. Therefore, there must be at least one block with Property A at any given time. However, by translation invariance, the existence of one block implies the existence of infinitely many blocks, and our claim is shown.
To see that there must be infinitely many blocks with Property B, we recall that by Lemma4 the density of LCBs decreases to 0 in time. Suppose on the contrary that no block has Property B. At any time t>T, fix a block B1 which has LCB at site x1 and let x2<x1-4/(ρ-ρf) be the rightmost site for which the density of LCBs is greater than (1/4N0)(ρ-ρf) in the interval [x2,x1]. By construction, x2 will be the site of an LCB, so we can find the rightmost site x3<x2-4/(ρ-ρf) so that the density of LCBs in [x3,x2] is greater than (1/4N0)(ρ-ρf). We iterate this construction and find that the density of LCBs in the interval (-∞,x1] is greater than (1/4N0)(ρ-ρf), which we have assumed to be false for all times t>T. Again by translation invariance, the existence of one block with Property B at any time t>T implies the existence of infinitely many such blocks.
At this fixed timeT, pick a block V of length L so that block V has Properties A and B. Let us say at time T block V occupies the sites x,x+1,…,x+L-2 and x+L-1 on the integer lattice. We will say that a car which starts at site y<x reaches block V when it first reaches the site x-∑i=yx‍ξT(i), regardless of whether or not block V has dissolved by that time. Since the cars in front of block V will not enter into this discussion, we may as well suppose that there are no cars in front of block V.
Consider the first car to the left of blockV which is able to be in free flow forever after time T. That is, it is the first car to reach the last sites block V occupied after block V has dissolved and without having been in a block since time T. We call this the first free flow car. Let Hy be the event that the first free flow car occupies site y at time T. In order for this to happen, block V must dissolve by the time this car reaches block V, which is certainly at or before time T+(x-y), as free flow cars move at unit speed.
Since the first free flow car does not hit a block, at timeT+(x-y) there are no blocks between coordinates x+L-1+(x-y) and y+(x-y), and all of the cars in this interval except the first free flow car are in blocks after time T.
The number of cars in the interval[x,x+L-1+(x-y)] at time T+(x-y) is the same as the number of cars in the interval [y,x+L-1] at time T, which by Property A is at least (1/2)(ρ+ρf)(x+L-y). The number of tailgaters among these cars is at most (1/4N0)(ρ-ρf)(x+L-y). We remove the exceptional subsequences from this interval, and the density of cars which remain in this interval has expected value at least (1/4)ρ+(3/4)ρf. The probability of the event Hy is less than the probability of having a density at least (1/4)ρ+(3/4)ρf over an interval of length x+L-y emitted as regular packs from a block.
Since the expected value of the density of regular packs isρf (from Section 3.3), we can use Markov's inequality to conclude that it is exponentially unlikely in (x-y) that this scenario occurs. To verify that Markov's inequality applies, let Zi denote the the ith pack to the left of coordinate x+L+(x-y) at time T+(x-y), and let Sn be the nth  partial sum of the #(Zi)’s (number of cars in pack Zi). To get our conclusion, we must see that
(36)E[eb(#(Z1))]=(1-α)+∑j=1∞‍ebjαγj-1(1-γ),
is finite. This is true when we choose b>0 so that γ<e-b. Since we are assuming γ∈[0,1), we can always find such a b.
SinceP(Hy)=0 for any y within L units of x, if we choose L large enough, we can assure a positive probability of no event Hy occurring (P(∪y=L-x∞H-y)<1), which implies that every car behind block V will be in a block at some time after time T. Since there are infinitely many blocks in the configuration at any finite time with Properties A and B and the density of tailgaters will decrease in time, we conclude that every car must enter a block at some point in its lifespan. This completes the proof of Lemma 8.The proof of Theorem2 is almost complete and will be completed in the next section along with the completion of the other two theorems.


### 4.6. Explicit Calculation of Density of Cars in Free Flow, Proof of Theorem3 and Completion of Proof of Theorem 2

According to Lemma7, the throughput θ is given by the limiting density of cars which are in free flow. In order to complete the proof of Theorem 1, we must verify that the formula for θ in (5) is correct.Ifρ≤ρ*, then θμ(ω)=ρ trivially, since all cars eventually enter permanent free flow. Therefore, we focus our attention to the case when ρ>ρ*.Because of (21), any interval [-M,M] will, with probability which approaches one, be either completely enclosed in free flow region or completely enclosed in a block as time goes to infinity. Since traffic density is preserved in time, we have
(37)a(limitingfreeflowdensity)+(1-a)(limitingblockdensity)=ρ.
The block density is clearly 1, and the density in the free flow region is asymptotically given by ρf by Lemma 4 and the corollary to Lemma 5. We then solve for a and get
(38)a=(ρ-1)1+2α-γγ-1-α
which gives Theorem 3.Putting all of this together, we get that the density of the subset of cars which are in free flow is equal to the fraction of space that is occupied by free flow times the density of cars there. Thus,(39)θμ(ω)=(ρ-1)1+2α-γγ-1-αα2α+1-γ=(1-ρ)α1+α-γ,
which completes the verification of (5) and we have proved Theorem 1.Finally, since Lemma8 guarantees that under a Bernoulli (ρ) initial distribution, there is no permanent free flow, we can use the results of Theorem 3 to establish Theorem 2.


## 4.1. Dealing with Tailgaters

The first lemma makes use of the fact that if one car enters permanent free flow (never again enters a block), then all cars must enter permanent free flow. This fact is a direct consequence the translation invariance. Furthermore, by the ergodicity of the configuration at each time, there is a zero-one law about entering permanent free flow; the probability of entering permanent free flow (for any car) is either zero or one.To show that the throughput exists, we first state and prove a lemma about the limiting density of LCBs (last cars in a block).Lemma 4.
The following are true.(i)
The spatial density of LCBs decreases to zero.(ii)
If no car enters permanent free flow, the spatial density of tailgaters goes to zero as time goes to infinity.Proof.
For (i), we first observe that blocks cannot be created. Because of this, the spatial density of LCB cars (last cars in a block) does not increase in time and therefore converges to a limit. Suppose the limiting density of LCBs wereδ>0. In order for LCBs to have density at least δ, at least half of the LCBs must be within distance 2/δ of nearest LCB to the right, which means that these blocks have length no more than 2/δ. There is a positive probability that any given one of these blocks will dissolve in the next 2⌈2/δ⌉ time steps by emitting one large pack along with the event of no cars entering the block. This would reduce the density of LCBs. Since this argument can be iterated indefinitely, the density of LCBs cannot remain above δ, which gives the contradiction.
For (ii), recall that when a tailgater reaches another block, the car loses its tailgater status. Since we assume no car will enter permanent free flow, each tailgater will hit another block and thus cease being a tailgater. Letw(t) be the density of cars which become tailgaters at some point after time t, and let b(t) be the density of LCBs at time t, which converges to 0 from (i). Fix an ϵ>0 and time t0 large enough so that b(t0)<ϵ. Since each car which becomes a tailgater is an LCB of a dissolving block, we get that the density of tailgaters created after time t0 cannot be more than the density of LCBs which will vanish after time t0. Therefore, w(t0)<ϵ.
Finally, leta(t) be the density of tailgaters at time t. For any t>t0 we can decompose a(t) into those tailgaters which have been tailgaters since time t0 and those which were created after time t0. Since every car (in particular the tailgaters) will enter a block infinitely often, we can find a time t1≥t0 such that the density of cars which have been tailgaters for the entire time interval [t0,t1] is less than ϵ. Since the tailgater cars which are created after time t0 have density less than ϵ, we get that a(t)<2ϵ for t>t1.Lemma 5.
Let{Zn} be the sequence corresponding to the cars emitted from a block which dissolves at time t. Suppose Zm=1 represents the tailgater car so that Zm+1=0 represents the space behind the tailgater car, and {Zm+k}k=1∞ is the sequence of cars behind the tailgater. Then there is a random N for which the sequence
(13)Z1,Z2,…,Zm-1,Zm+N,Zm+N+1,…
is distributed as a regular pack, as described in Section 3.3. Furthermore, N remains bounded in expected value as t goes to infinity.Before proving this lemma, we observe an immediate corollary. We call the finite subsequenceZm,Zm+1,…,Zm+N-1 from the lemma an exceptional subsequence.Corollary 6.
Upon removing the exceptional subsequences from the free flow region, what remains has a pack distribution as in the renewal process of Section3.3.The corollary is obtained by observing that the free flow space can be divided into two parts: cars that have never been in blocks and the part described by the lemma. The exceptional subsequences mentioned in the corollary will be used later to understand the free flow regions. Denote byN0 an upper bound on their expected length.Proof of Lemma5.
We break this proof into two cases. First, we show the lemma under the additional assumption that the car which eventually becomes the tailgater in the dissolving block has occupied the site adjacent to the car following it at some time in the past; lets be the most recent such time. Without loss of generality, suppose that at time s, the dissolving block occupies sites y0,y0+1,…,x0, the car which will eventually become the tailgater is at site 0, and that there are k cars between site 0 and site y0. We will couple ξt with another SSTCACT process ξ~ as follows. Set
(14)ξ~s(x)={1x≤x0-y0+k+1ξs(x0+2)x=x0-y0+k+30otherwise.
Then, we use the following coupling. We first assign each car in ξ~ a partner in ξ. The rth car to the right of site -1 at time s in ξ~ is partnered with the rth car to the right of site 0 at time s in ξ, for r=1,…,x0-y0+k+1. The rth car to the left of site 0 at time s in ξ~ is partnered with the rth car to the left of site 0 at time s in ξ, for r=1,2,…. The only car in or behind the dissolving block in ξ that is not partnered with a car in ξ~ is the car at site 0: the car which becomes the tailgater. The coupling is defined according to the following rule: the coins flipped by cars in the ξ~ process as they leave the block will be tied to the coins that their partners in the ξ process use when they leave a block for the last time (if a car in ξ leaves multiple blocks, we perform the coupling using the last block they left).
The cars in front of the tailgater inξ will all be emitted from the dissolving block. Due to the coupling, they are emitted following the same sequence as their partners in ξ~, which follows a pack distribution. The car which is at site -1 in ξ~ at time s will remain there until time t, at which time it will flip a γ coin to determine its movement. By the coupling, this coin flip is tied to the coin flip of the car at site -1 the ξ process at the time it leaves the last block. In order for the dissolving block to dissolve, the result of this coin flip must be tails: both cars remain in position one time step and flip an α coin for the next time step. Therefore, by setting N=1 in the statement of the lemma one can observe that the sequence of cars generated in ξ, after having removed the tailgater, is the same as the sequence in ξ~, which has the pack distribution.
Now suppose that the car which eventually becomes the tailgater in the dissolving block has never occupied the site adjacent to the car following it at any point before timet. In this case, set s to be the time when the tailgater car joins the dissolving block. If we label the location of the dissolving block as [y0,x0], the location of the front of the closest block behind it which does not dissolve before time t as 0 and the number of cars between these two blocks at k, we can set up a coupling process exactly as in (14). The coupling, however, will be slightly different.
As before, we assign each car inξ~ a partner in ξ. The rth to the right of site k at time s in ξ~ is partnered with the rth car to the right of site x0 at time s in ξ, for r=1,…,x0-y0-1. The rth car to the left of site 0 at time s in ξ~ is partnered with the rth car to the left of site 0 at time s in ξ, for r=0,1,…. Now many cars in the ξ process do not have a partner: all of the cars between the tailgater and the car which is at the front of the previous block at time s.
We perform the coupling in the same way as in the previous case: the coins flipped inξ~ are tied to the partner car's flips in ξ as they leave the last block. Then it is clear that the way in which the cars at sites [x0,y0] at time s in ξ flow from the dissolving block is the same as the way in which cars flow from the front of the block in ξ~, due to the coupling. This is also clear for cars which begin at sites less than or equal to -1 in both processes at time t. Therefore, if we denote Zm=1 to represent the tailgater car, Zm+1=0 to represent the space behind the tailgater car, Zm+N-2=1 to denote the car which is at site 0 at time s in ξ, and Zm+N-1 to represent the space behind this car, we can conclude that the sequence Z1,…,Zm-1,Zm+N,… is an example of the renewal reward process. In order to complete the lemma, we must show that E[N] remains bounded with time in this case.
By construction,N here is at most x0+1, the distance between the tailgater and the car at site -1 at time s in ξ. This is the distance between the tailgater and the car which is behind the car behind it, given that the tailgater and the car behind it have never occupied adjacent sites. Since the car behind it has then moved in free flow since its initial movement, the size of these gaps cannot increase in time, so E[N] remains bounded.


## 4.2.  Proof That Throughput Exists

We now turn to proving the existence of throughput from Theorem1. For convenience, we define
(15)ξtf(x)=(ξt(x))(1-ξt(x-1))(1-ξt(x+1)),ξtl(x)=(ξt(x))(ξt(x-1))(1-ξt(x+1)),ξtb(x)=(ξt(x))(1-(1-ξt(x-1))(1-ξt(x+1))).
Under these definitions, ξtf(x) is 1 if and only if there is a car at x at time t which is in free flow, ξtl(x) is 1 if and only if there is a car at x at time t which is the leading car in a block, and ξtb(x) is 1 if and only if there is a car at x at time t which is in a block.Lemma 7.
The throughputθ is almost surely given by the limiting density of cars which are in free flow. That is, if we set ρtffc to be the spatial density of free flow cars at time t, then almost surely θ=limt→∞ρtffc(ω).Proof.
There is no throughput within the blocks, aside from the possible movement of the leading car in the block. The law of large numbers gives(16)θ=limt→∞1t∑s=0t-1‍(1{ξsf(0)=1}+1{ξsl(0)=1,ξs+1l(0)=0})=limt→∞1t∑s=0t-1‍(1{ξsf(0)=1}+α1{ξsl(0)=1})
almost surely.
By Lemma4, the observed density of cars at the front of blocks goes to zero as time goes to infinity; hence the α1{ξsl(0)=1} term, due to dividing by t, does not contribute to the throughput. Therefore, the throughput is simply
(17)θ=limt→∞1t∑s=0t-1‍ξsf(0)
if the limit exists. In order to show the lemma, we must show that this time average is equal to the limiting spatial density of cars that are in free flow.
When all cars go into permanent free flow,θ=ρ trivially, so θ exists and is equal to the limiting density of cars that are in free flow. Now suppose that no cars enter permanent free flow.
Without loss of generality we may assume that site 0 is in a block at time 0. We will denote byAi the amount of time that site zero spends in the ith block it enters after time 0 and let Bi be the amount of time it spends in the ith free flow region it enters after time 0. More precisely, we set A1=m if ξt(0)=1 for t=0,1,…,m-1 and ξm(0)=0; we set B1=n if ξt(0)ξt(1)=0 for t=A1,A1+1,…,A1+n-1 and ξA1+n(0)ξA1+n(1)=1. We set t1=A1+B1 and define inductively: Ai=m if ξt(0)=1 for t=ti-1,ti-1+1,…,ti-1+m-1 and ξti-1+m(0)=0; and set Bi=n if ξt(0)ξt(1)=0 for t=ti-1+Ai,ti-1+Ai+1,…,ti-1+Ai+n-1 and ξti-1+Ai+n(0)ξti-1+Ai+n(1)=1, with
(18)ti=ti-1+Ai+Bi.
The sequence of times ti indicate the times in which the site 0 enters the ith block. Another way to write ti is
(19)ti=∑j=1i‍(Aj+Bj).
We think about how the site 0 can “enter” a block, that is, transition from being in a free flow region at timet to being in a block at time t+1. This is possible only if site 1 is in a block at time t and there is a car at site -1 at time t which enters the block. Thus, we can think of the site 0 as entering the back of a block. Site 0 will exit the block only after all of the cars in the block in front of site 0 are emitted from the block as part of regular packs. Therefore, the expected amount of time it will take for site 0 to exit a block after it enters is the average rate at which cars exit from the front of the block times the length of the block. A similar statement can be made about free flow regions drifting through the site 0.
The blocks and the free flow regions are changing in size over time. However, once nearly all of the cars have been in blocks, roughly speaking, the effect of the tailgaters becomes negligible, so the input and output mechanisms for the blocks are free flow cars which are emitted as regular packs. Since the number of cars leaving a block and the number of cars entering a block obey the same laws, the fluctuations in size of the blocks (and free flow regions) obey properties of an unbiased random walk.
Formalizing this discussion, consider the block which site 0 enters at timeti; call it D. Let {Yt} be the sequence corresponding to the cars emitted from this block and let {Xt} be the sequence corresponding to the cars entering the block. The size of this block at time ti is the sum of the size of that block at time 0 with the difference between the sums of the sequences {Xt} and {Yt} to time t0. By Lemma 5, the sequence {Xt} can be expressed as a sequence distributed as regular packs with some exceptional subsequences inserted. Let Ni be the length of the ith such subsequence and let {X^t} be the sequence {Xt} with the exceptional subsequences removed. We have
(20)(lengthofDattimeti)=(lengthofDattime0)+∑‍X^i-∑‍Yi+∑‍Ni,
where the sums are to be taken over all time indices less than ti. By Lemmas 4 and 5 and its corollary, for any positive ϵ the number of terms in ∑‍Ni is eventually less than ϵti as ti→∞, and each of the Ni is bounded by N0<∞ in expected value. The middle two terms on the right side are the difference of two sequences with the same law hence behave like a random walk conditioned to stay positive until time ti. Therefore, we can find constants c1and c2 such that
(21)c1tiloglogti<Ai<c2tiloglogti+ϵN0ti
for all times ti sufficiently large. By a similar reasoning, at the expense of perhaps picking different constants, we can replace Ai in (21) with Bi.
Returning to (17), we will first show that the fraction of time site 0 finds itself in a block tends to a limit. We have that
(22)limsupt→∞1t∑s=0t-1‍ξsb(0)=limn→∞1tn-1+An∑i=1n‍Ai,liminft→∞1t∑s=0t-1‍ξsb(0)=limn→∞1tn∑i=1n‍Ai;
we would like to show that these are the same. The difference between the two can be written:
(23)limn→∞tn-(3/4)∑‍Aitn-1/tn1/4Bn+An/Bntn1/4.
Since ∑‍Ai<tn, we find that the numerator of this fraction goes to zero. The first term in the denominator can be expressed as
(24)tn-1(tn-1+An+Bn)1/4Bn.
By (21), this quantity can be made arbitrarily large almost surely by making ϵ small, giving that difference between the limsup and liminf is almost surely zero. Therefore,
(25)limt→∞1t∑s=0‍t-1ξsb(0)
exists almost surely.
Because of this, the limiting fraction of time that site 0 spends in free flow also exists, almost surely. Again using the argument that the free flow space, as time goes to infinity, is made up of primarily pack distribution as time goes on, we will get our result. Formally, we write(26)ξsf(0)=1{carfromregularpackat0attimes}+1{carfromexceptionalsequenceat0attimes}.
The density of cars from exceptional sequences has been shown to approach zero, so upon dividing by t, we get that
(27)limt→∞1t∑s=0t-1‍ξxf(0)
exists and equals limt→∞ρtfft, and the proof of Lemma 7 is complete.


## 4.3. Outline of Proof Thatρ*=ρf

Recall that the density of free flow cars emitted from a block as regular packs, which we labelρf in (12), is exactly what we claim as ρ*, the maximal free flow density from Theorem 1. Therefore, we must justify why the quantity ρf should be ρ*.The general idea is as follows. Since cars do not move when they are in blocks, there is no throughput within the blocks. Therefore, the entire contribution to the throughput must come from the free flow regions. If all cars enter blocks at some point, then all cars are eventually emitted as part of a pack. Therefore, there is a certain density of free flow cars which cannot be surpassed, provided all cars enter blocks. Loosely speaking, in order to conclude thatρf=ρ*, we must show that there is an initial distribution which will force all cars to enter blocks if the density is greater than ρf, that all cars will enter permanent free flow if the density is less than ρf, and that the presence of tailgaters does not profoundly change the calculations. These general ideas will be made precise throughout the rest of this section.We will divide the proof ofρ*=ρf into two parts. For the first half of the proof we must turn to showing that ρ*≥ρf. The formal proof of this, given in Section 4.4, is borrowed almost completely from the paper of Gray and Griffeath [2]. To show ρ*≥ρf, we assume ρ>ρ* and show that this implies ρ>ρf. The basic idea of the proof is to show that the expected distance between two cars cannot be too far apart when cars are forced to run into blocks (because ρ>ρ*).Second, we will show thatρ*≤ρf. To do this, we prove Theorem 2, showing that if μ is a Bernoulli product measure distribution with density ρ with ρ>ρf then it must be the case that ρ>ρ*. The proof of this is in Section 4.5.


## 4.4. Proof Thatρ*≥ρf

We seek to proveρ*≥ρf. The proof given here is a modification of the proof given for general cruise control systems in the Gray-Griffeath paper [2].Assumeρ>ρ*. We seek to show that ρ>ρ* implies that ρ≥ρf. We condition on the event that a car starts at the origin at time 0. Let Xt be the position of that car at time t and let Yt be the position of the next car to the right of the car at Xt. The ergodic theorem tells us that E[Yt-Xt]=1/ρ for all t. For 0≤s<t, define the following events:
(28)At={Yt-Xt=1},Bs,t={Ys-Xs=1,Yu-Xu>1fors<u≤t},Ct={Yu-Xu>1for0≤u≤t}.Since we assume thatρ>ρ*, the probability of the event that the car that starts out at the origin stays in free flow goes to zero as time goes to infinity, so P(Ct)→0. Thus,
(29)1ρ=limt→∞E[Yt-Xt]=limt→∞1·P(At)+∑s=0t‍P(Bs,t)E[Yt-Xt∣Bs,t].SinceE[Yt-Xt∣Bs,t]>1 for all s and t, if we could show that
(30)E[Yt-Xt∣Bs,t]≤2α+1-γα
for all s and t, we would then get that
(31)1ρ≤2α+1-γα,
which is the desired conclusion.Thus, we turn to proving (30). As in [2], we will actually prove
(32)E[Yt-Xt∣Bs,t,Yt-Ys,ℱs]≤2α+1-γα,
where ℱs is the σ-field generated by the processes up to time s.Since we are assuming thatYs+1-Xs+1>1, there is a vacancy to the right of the car at position Xs+1 at time s+1. If there is also vacancy to the left of that car, then the car at position Xs+1 will move in free flow. In order to have the event Bs,t hold, we must have Yt-Xt=2 in this case. Since 2≤(2α+1-γ)/α, we can restrict our attention to the case where there is a car immediately to the left of the car at site Xs+1 at time s+1.SinceYs-Xs=1 and Ys+1-Xs+1>1, we must have that the car at site Ys moved at time s+1 but the car at site Xs did not. Therefore, in order for the car at site Xs+1 to move at time s+2, the car must flip heads on a γ-coin.LetK=(t-s)-(Yt-Ys), the number of times that the leading car (denoted by the letter Y) did not move in the time interval [s,t]. Because θ<ρ, we are guaranteed a density of cars in the system, bounded away from zero, which are in blocks at any given time. Along with Lemma 4, this tells us that the average block size is nondecreasing in time. Therefore, we can be assured that as time goes on it becomes very unlikely that the car at position Y will pass through an entire block between time s and time t with the car behind it not reaching that block. Therefore, with probability that goes to one, we either have that the leading car is at the left edge of a block at time t-K (and still at time t), or K=0. If the event Bs,t occurs, then the car at site Xs+1 must flip tails at times s+2,s+3,…,s+K, because there is no way for the gap between the two cars to grow once the trailing car enters free flow. Thus, if these flips were not all tails, there would be a time u with s<u≤t with Yu-Xu=1.After times+K, the coin tosses made by the car at site Xs+K are independent of Bs,t and Yt-Ys, since there is no way that this car could catch up to the car at site Ys+K in the next t-s-K time steps to affect its movement. Therefore, Yt-Xt=2+N, where N represents the number of consecutive tails beginning with time s+K+1 tossed by the car which began at the origin. The random variable N is independent of Bs,t, Yt-Ys, and ℱs. Therefore,
(33)E[Yt-Xt∣Bs,t,Yt-Ys,ℱs]=2+E[N].We can decompose the value ofE[N] according to whether or not the leading car hits a block before time t as follows:
(34)E[N]=E[N∣K=0]·P(K=0)+E[N∣K>0]·P(K>0).
We have already argued in Lemma 4 that the probability of a car being at the edge of a block goes to zero as time goes to infinity independently of N. Thus, as time goes to infinity, P[K>0]→0. Therefore, we only need to look at E[N∣K=0].In that case,N=0 means the car at site Xs+1 moved at time s+2 despite having a car immediately behind it and 2 sites in front of it. This happens with probability γ. If N>0, then the car at site Xs+1 did not move at time s+2 (which happens with probability 1-γ), did not move at the next N-1 steps (which happens with probability 1-α at each time step), but did move on the (N+1)st time step (with probability α). Thus,
(35)E[N]=∑i=1∞‍i(1-γ)(1-α)i-1α=1-γα.Thus,1/ρ≤2+(1-γ)/α, which gives the desired inequality, thus completing the proof that ρ*≥ρf.


## 4.5. Start of Proof of Theorem2

In this section, we establish the existence of ergodic initial distributions which lack permanent free flow for any densityρ greater than ρf. Such an example is the Bernoulli product measure family of distributions.Lemma 8.
When the initial distributionμ is Bernoulli product measure with density ρ, ρ>ρf, each car is in a block at some time t≥0 with probability one; no car enters permanent free flow.Proof.
Since we are assuming that the initial distribution is a Bernoulli product measure, we can guarantee that there are arbitrarily long blocks in the initial configuration. Since a block can dissolve only linearly in time, we can guarantee blocks of arbitrary length at any finite timet≥0.
By Lemma4, we are able to fix a time T≥0 so that the density LCBs is less than (1/8)(ρ-ρf). At this time T, we will consider a block which has the following properties. Recall we have assumed that ρ>ρf.
Property A. Let x be the site which is at the front of this block. For any y<x, the spatial density of cars in the interval [y,x] is ≥(1/2)(ρ+ρf).
Property B. Let y′ be the site occupied by the LCB (last car in the block). For any z′<y′-4/(ρ-ρf), the density of LCBs in the interval [z′,y′] is less than (1/4N0)(ρ-ρf), where N0 is a bound on the expected length of the exceptional subsequences from Lemma 4.
We claim that there are infinitely many blocks which possess both of these properties. To see this claim for Property A, suppose on the contrary that there are not any blocks with Property A at a given time. Fix a blockB1, and let x1 be the site of the first car in block B1 at this given time. By our assumption, there exists a site y1<x1 so that the density of cars in the interval [y1,x1] is less than (1/2)(ρ+ρf). Now let x2≤y1 be the largest site index less than or equal to y1 which marks the front of another block, which we call B2. We iterate this construction to obtain an infinite collection of intervals {[yi,xi]}. Let S be the union of these intervals. By construction, the density of cars in S is less than (1/2)(ρ+ρf). The set (-∞,x1]∖S is a set of sites which are not in blocks at the given time. Any cars in these sites were either emitted from blocks as part of packs (in which case, by Lemma 4, their density becomes asymptotically close to ρf) or they have never been in a block (in which case they occur with density ρ according to the Bernoulli product measure). In either case, the density of cars in this region is at most ρ. Combining these facts shows that the density of cars in the interval (-∞,x1] is less than ρ, which is a contradiction. Therefore, there must be at least one block with Property A at any given time. However, by translation invariance, the existence of one block implies the existence of infinitely many blocks, and our claim is shown.
To see that there must be infinitely many blocks with Property B, we recall that by Lemma4 the density of LCBs decreases to 0 in time. Suppose on the contrary that no block has Property B. At any time t>T, fix a block B1 which has LCB at site x1 and let x2<x1-4/(ρ-ρf) be the rightmost site for which the density of LCBs is greater than (1/4N0)(ρ-ρf) in the interval [x2,x1]. By construction, x2 will be the site of an LCB, so we can find the rightmost site x3<x2-4/(ρ-ρf) so that the density of LCBs in [x3,x2] is greater than (1/4N0)(ρ-ρf). We iterate this construction and find that the density of LCBs in the interval (-∞,x1] is greater than (1/4N0)(ρ-ρf), which we have assumed to be false for all times t>T. Again by translation invariance, the existence of one block with Property B at any time t>T implies the existence of infinitely many such blocks.
At this fixed timeT, pick a block V of length L so that block V has Properties A and B. Let us say at time T block V occupies the sites x,x+1,…,x+L-2 and x+L-1 on the integer lattice. We will say that a car which starts at site y<x reaches block V when it first reaches the site x-∑i=yx‍ξT(i), regardless of whether or not block V has dissolved by that time. Since the cars in front of block V will not enter into this discussion, we may as well suppose that there are no cars in front of block V.
Consider the first car to the left of blockV which is able to be in free flow forever after time T. That is, it is the first car to reach the last sites block V occupied after block V has dissolved and without having been in a block since time T. We call this the first free flow car. Let Hy be the event that the first free flow car occupies site y at time T. In order for this to happen, block V must dissolve by the time this car reaches block V, which is certainly at or before time T+(x-y), as free flow cars move at unit speed.
Since the first free flow car does not hit a block, at timeT+(x-y) there are no blocks between coordinates x+L-1+(x-y) and y+(x-y), and all of the cars in this interval except the first free flow car are in blocks after time T.
The number of cars in the interval[x,x+L-1+(x-y)] at time T+(x-y) is the same as the number of cars in the interval [y,x+L-1] at time T, which by Property A is at least (1/2)(ρ+ρf)(x+L-y). The number of tailgaters among these cars is at most (1/4N0)(ρ-ρf)(x+L-y). We remove the exceptional subsequences from this interval, and the density of cars which remain in this interval has expected value at least (1/4)ρ+(3/4)ρf. The probability of the event Hy is less than the probability of having a density at least (1/4)ρ+(3/4)ρf over an interval of length x+L-y emitted as regular packs from a block.
Since the expected value of the density of regular packs isρf (from Section 3.3), we can use Markov's inequality to conclude that it is exponentially unlikely in (x-y) that this scenario occurs. To verify that Markov's inequality applies, let Zi denote the the ith pack to the left of coordinate x+L+(x-y) at time T+(x-y), and let Sn be the nth  partial sum of the #(Zi)’s (number of cars in pack Zi). To get our conclusion, we must see that
(36)E[eb(#(Z1))]=(1-α)+∑j=1∞‍ebjαγj-1(1-γ),
is finite. This is true when we choose b>0 so that γ<e-b. Since we are assuming γ∈[0,1), we can always find such a b.
SinceP(Hy)=0 for any y within L units of x, if we choose L large enough, we can assure a positive probability of no event Hy occurring (P(∪y=L-x∞H-y)<1), which implies that every car behind block V will be in a block at some time after time T. Since there are infinitely many blocks in the configuration at any finite time with Properties A and B and the density of tailgaters will decrease in time, we conclude that every car must enter a block at some point in its lifespan. This completes the proof of Lemma 8.The proof of Theorem2 is almost complete and will be completed in the next section along with the completion of the other two theorems.


## 4.6. Explicit Calculation of Density of Cars in Free Flow, Proof of Theorem3 and Completion of Proof of Theorem 2

According to Lemma7, the throughput θ is given by the limiting density of cars which are in free flow. In order to complete the proof of Theorem 1, we must verify that the formula for θ in (5) is correct.Ifρ≤ρ*, then θμ(ω)=ρ trivially, since all cars eventually enter permanent free flow. Therefore, we focus our attention to the case when ρ>ρ*.Because of (21), any interval [-M,M] will, with probability which approaches one, be either completely enclosed in free flow region or completely enclosed in a block as time goes to infinity. Since traffic density is preserved in time, we have
(37)a(limitingfreeflowdensity)+(1-a)(limitingblockdensity)=ρ.
The block density is clearly 1, and the density in the free flow region is asymptotically given by ρf by Lemma 4 and the corollary to Lemma 5. We then solve for a and get
(38)a=(ρ-1)1+2α-γγ-1-α
which gives Theorem 3.Putting all of this together, we get that the density of the subset of cars which are in free flow is equal to the fraction of space that is occupied by free flow times the density of cars there. Thus,(39)θμ(ω)=(ρ-1)1+2α-γγ-1-αα2α+1-γ=(1-ρ)α1+α-γ,
which completes the verification of (5) and we have proved Theorem 1.Finally, since Lemma8 guarantees that under a Bernoulli (ρ) initial distribution, there is no permanent free flow, we can use the results of Theorem 3 to establish Theorem 2.



---

*Source: 246045-2013-12-19.xml*