Infinite line of people

Question

Let us assume that we have an infinite line of people, and each person can either move forwards or remain at the same place. They move only one step at a time. (They are jumping from one position to the next if that position is empty). All people either move or remain still simultaneously.

Let us further assume that a person in spot $x$ will move forward to spot $x+1$ if spots $x+1$,$x+2$ and $x-1$ are empty. For all other people, they move with a probability $\alpha$.

Can it be shown that "eventually", there will be only two regions, one where the density is high and one where the density is low? (the fast lane, and a jammed lane)

A way to think about this is to think about the people being on a finite circular loop. (obviously then there are not infinite people in the line)

EDIT:

For the purposes of clarification since many people are worried about the initial configuration, if it is assumed that it is sufficiently dense. (more than 0.33). We can have any initial configuration, it should not matter as we are interested in long term behavior.

EDIT 2:

The objection raised below in the comments is deterministic. However, the question is about stochastic, thus we can say that $\alpha \not = 0$ or $1$.

Example: Let 1 be a occupied spot and a 0 an unoccupied spot. then we can start with

...1110001000...

and then next we have either

...1110000100...

or

...1101000100...

depending on whether the person advanced who had the probability $\alpha$ of advance.

EDIT: C++ PROGRAM

Program that I wrote. File You may have to add a .exe to the end if you want to run it in Windows OS.

Same program with colors fixed and much longer time frame. File2

Answer 1

I suspect that the restriction "if spots x+1,x+2 and x−1 are empty" turns the problem more complex without adding anything conceptually relevant.

I don't claim to have an answer, but want to point that the model has some resemblance to some physical models. In particular, consider the Tonk gas (or "hard rods" model). Here, we have one dimensional particles of a fixed width that move in a line, and only interact through hard elastic colitions. One way to simulate this statistical models (not is dynamics, but its average configurations) is through Montecarlo simulations. In this procedure, we produce random configurations by some rule that produces a representative sampling of the ensemble - in the hard-rods model a possible rule would be to displace the particles (one at a time or all simultaneously) a random distance and "accept" the new configuration iff no particles overlap.

Now, the model presented here has (to me) some resemblance to such a Montecarlo simulation of a system of hard rods with a "drift" added. I'm not sure if that similarity can be exactly worked out, but I suspect so - and also I suspect that there is no "phase separation" as you seem to expect.

I made some little simulation here (only modern browsers with canvas support: Chrome, Firefox - perhaps IE 9) http://hjg.com.ar/varios/mat/queuesimul.html

UPdate: sorry, I had misread the model. My thoughts (and simulation) correspond to another model (people move if probability 'a' if forward neighbours are empty )

Answer 2

Having seen the simulations, here are some definitions that may help clarify the problem. (Though I don't have a solution.)

1. First, to define the free region versus the jammed region, the expected density of either region should be dependent on $\alpha$.

   i. Say you start with a single solid block. For $\alpha = 0$ there will be no motion, so the "free region" would be empty. But for $\alpha = 1$, the people would peel off from the front of the queue, so the expected free region should have about 50% density. In general you probably will expect the free region to have $\alpha / (\alpha + 1)$ density.

   ii. On the other hand, say you start with initially alternating configuration. For $\alpha = 0$, this leads to no motion, and should be considered as jammed. While for $\alpha = 1$, this leads to continuous flow, and should be considered as non-jammed.

   So we can probably define free and non-free based on the expected proportion of moving guys. Say a stretch of $K$ spots has density $\delta$. Then you should expect $(1-\delta)^3K$ number individuals that can flow freely, $[(1-\delta)\delta^2 + 2\delta(1-\delta)^2]K$ individuals to flow with probability $\alpha$, and $\delta K$ individuals to be necessarily trapped. So the expected proportion of moving individuals is $$ P(\delta,\alpha) = (1-\delta)^3 + 2\alpha (1-\delta)^2\delta + (1-\delta)\delta^2 \alpha$$ so maybe we can arbitrarily define a free-flowing region to be one with density $\delta$ such that $P(\delta,\alpha) > 2/3$ and a jammed region to be one with density such that $P(\delta,\alpha) < 1/3$ (the numbers 1/3 and 2/3 I just pulled out of a hat). In any case, since $\alpha$ and $\delta$ will be between 0 and 1, you can check that $P(\delta,\alpha)$ is a decreasing function of $\delta$. So you can define $\delta_{max}$ the lower bound for the jammed region and $\delta_{min}$ the upper bound for the free region.

2. However, to compute $\delta$, you will need a window of size $K$ over which to compute. So perhaps what we need to do is to set the initial number of people really large, say $N > 10000$. Then at every point we compute its neighboring density $\delta_K(x)$ as the density of people in the region $[x-50,x+50]$ (again, here I picked $K = 101$ rather arbitrarily, just much smaller than $N$). Then you can properly define the density near a point $x$.

3. So you can rephrase your question as asking for the following. Given $K$ much bigger than 1 and $N$ much bigger than $K$. Let your process run with some initial density $\delta_{min} < \Delta < \delta_{max}$ (so you don't start with something that is already completely free or completely jammed) under probability $\alpha$. At every point $x$ compute $\delta_K(x)$ as above. Your question then is one about the expected number of of components of $\{x| \delta_K(x) > \delta_{max}\}$ and the expected number of components of $\{x|\delta_K(x) < \delta_{min}\}$, the former being the number of jammed regions and the latter being the number of free regions.

Or, perhaps an even better formulation (instead of steps 2 and 3 above) of the question can be taken as the following. Start with a large number $N$ and probability $\alpha$, with initial configuration with density $\delta_{min} < \Delta < \delta_{max}$. Prove or disprove that there is a constant $k$ depending on $\delta_{max}$, $\delta_{min}$ and $\alpha$, such that there must exist (with probability 1), after a long time evolution, a contiguous set of size at least $N/k$ on which the density of people is larger than $\delta_{max}$ and a contiguous set of size at least $N/k$ on which the density of people is less than $\delta_{min}$.

This way, I think, you will have a problem that is well-formulated and tractable mathematically. Good luck!