4
$\begingroup$

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

  • 0
    A person can only move if there is an empty spot, right? So when you say "they move with probability a" do you mean that "given $x+1$ is empty, and either $x+2$ or $x-1$ is non-empty, then there is probability $a$ that a person at $x$ will move to $x+1$"?2011-02-02
  • 0
    yes, that is what I meant. two people cannot be on one spot.2011-02-02
  • 0
    and people cannot move as a group!2011-02-02
  • 3
    But don't you need to tell us more about the initial configuration? After all, if the line is already completely full, then no-one moves at all (and the whole line is one jammed region), but if the people are originally very sparse, then everyone moves in lock-step to the next position on each move (so the whole line remains sparse). So I'm not sure exactly what the question is.2011-02-02
  • 0
    @JDH, let us say it is randomly distributed(but it doesnt matter since it is stochastic). I am interested in how it behaves with the density(of people) too.2011-02-02
  • 0
    @picakhu: Randomly distributed according to which distribution?2011-02-03
  • 0
    @Rasmus, it doesnt really matter here, we are talking about a stochastic process, we are interested in the long term behavior. But if it helps you, you can assume each initial spot having a probability of the density of having a person there. So say we have spots A B C D, and we want the density to be 50%, then we can have a probability of 50% that there is a person at A, at B etc. As the number of spots goes to infinity, the fraction of people to spots goes to the density2011-02-03
  • 0
    I see. So since people cannot move in lock-step, if a person sees at least 2 open spots in front of him, once he starts moving he can only be stopped if he 'catches up' to the person in front?2011-02-03
  • 1
    Um, if you take $a = 0$ or $a = 1$, there are examples where there are more than 2 regions. Consider a stretch of individuals separated by one spot, and a stretch of individuals separated by two spots, and alternate several times. In $a=1$ the whole thing moves in the direction of travel. In $a=0$ the configuration propagates against the direction of travel.2011-02-03
  • 0
    @Willie: We can ignore the "boring" cases. As a side note, does this belong to a place like overflow instead? I do not know the solution to this question, but I do know that it is very difficult.2011-02-04
  • 4
    @picakhu "does this belong to a place like overflow". No, at least not until you clearly define what the question is. At the very least, all of the "trivial" or "boring" objections raised by commenters will have to be factored into the problem, in a way that doesn't look _ad hoc_. Now, the point in the previous comment is this: do you have any intuitive reason why those "boring" cases should be unstable if you change $a$ slightly away from 0 or 1? If not, then why would you guess the limiting configuration to have only two clumps? If yes, that info can be useful.2011-02-04
  • 0
    Put another way: in some more complicated deterministic models, [jamitons](http://math.mit.edu/projects/traffic/) are known to arise and trains of multiple jamitons can form. What motivated you to think that your stochastic model will lead to a single clump only?2011-02-04
  • 0
    Hey, I seem to have offended you by posting on MO. I was just trying to see if I could get some response there. Anyway, the main idea is just to study such systems and find some interesting phenomenon. Early simulation suggests that you get clumping which is why I think it will lead to that.2011-02-04
  • 0
    Interest problem, conceptually. I don't see why your restrict the movements two empty positions at front at one behind. It seems that simply requiring one empty position at x+1 would be enough.2011-02-08
  • 0
    @leonbloy: we want to differentiate between a person who is truly free vs one that is apparently so.2011-02-08
  • 0
    @picakhu: the fact that you ran simulations should be included in the problem as evidence, preferably with the parameters you used for those simulations (what are the values for the total number of spaces, and the value of the movement probability, is the initial configuration randomly seeded, and what are the initial densities you tested) and the results (after what time-scale does clumping occur, and whether there were some interesting intermediate stage behaviour).2011-02-08
  • 0
    Also, since you've been running simulations, can you try running one with the "boring" initial data I described for the deterministic case, but with movement probability very close to deterministic? It'd be great if you can give some data on (a) roughly how long the boring initial data with multiple clumps would persist (b) if everything clumps up in the end, how fast is the transition from multiple clumps to a single one (is it a noticeable phase transition or a gradual change?)2011-02-08
  • 0
    @Willie, Hi, I would have to re-program it since I stopped working on that a really long time ago.. It just crept up again and I decided to post it. If you are interested, I could code it and post the c++ code somewhere. It would take me a while though.2011-02-08
  • 0
    @picakhu: my C/C++ is more than a bit rusty. so unfortunately i don't expect to be able to play with your code much :(2011-02-08
  • 0
    @Willie: I will probably not give the code. I will just give the output file which you should then be able to run. Just to check though, what OS are you using?2011-02-09
  • 0
    @Willie: I added my program. Let me know if you want the source instead. My trials with a $\alpha$ as low as 0.001 show the clustering that I was talking about.2011-02-09
  • 0
    @picakhu: OS-wise, linux. So ELF executables works fine. What do the colours mean? Also, what are the number of spots you used and the density you started with?2011-02-09
  • 0
    @Willie: I make my screen very small using ctrl + -, I use 500 points, and densities not too high so that convergence is quicker ~ 0.35. Color wise, I need to fix a mistake I spotted with red, but red is generally a person who cannot move (except if red is at the front), blue and green are people who can move but blue has a person behind him and no one in front, but does not have space much ahead. Green has no one behind, and also but not ample space ahead. You can fathom having different probabilities for different colored people to move, and that was the starting point for this.2011-02-09
  • 0
    and last, Yellow is a free person2011-02-09
  • 0
    okay, I ran it several times with parameters $\alpha = 0.05, N = 280$ and density 0.4, when the program exits, there generally seems to be 3 or 4 clumps. Is there a way of changing the maximum number of steps? (For $\alpha$ around 0.8 or larger, I also don't see clear clumping into one band. But I wonder if the program terminates too soon for the large scale structure to emerge.)2011-02-09
  • 0
    @Willie: I uploaded a program that runs longer.2011-02-09
  • 0
    @Willie: for things like 0.8 or larger, it is really difficult too see the banding, because the density of the "free region" is very similar to the "dense" region. Our eyes may not be able to differentiate between them, but I really have no idea how to do that. Perhaps one way is to make the number of spots very very large. 10000~20000 seems plausible.2011-02-09

2 Answers 2

0

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!

  • 0
    BTW, from the last formulation, if 2/3 is the required proportion for movement to be considered free, and $\alpha = 0.8$, then $\delta_{min} = 0.27$. So starting with $\Delta = 0.35$ probably won't lead to formation of easily identifiable jammed regions. On the other hand, the 1/3 movement criterion for jammed region is probably a poor choice, since for $\alpha = 0.1$ that would imply $\delta_{max}$ around 0.34. So I guess it would be better to define free and jammed with something more extreme, like 90% and 10% moving.2011-02-09
  • 0
    @Willie: I may be misunderstanding what you said, but the aim is to show that eventually there will be exactly 2 regions. (all the denser regions merge, and all the less dense regions merge)2011-02-09
  • 0
    @picakhu: and that's what I wrote above. The problem is how do you define dense and how to you define non-dense *mathematically*. It is not enough to just say "it looks dense to the eye". As you well know, small "local" blips can happen. Which means that any definition of dense and non-dense really should average over a sufficiently large region to ignore the local blips.2011-02-10
  • 0
    If the expectation is exatly one dense region, then you'd be asking to show that, using the formulation in item 3, that the contiguous region corresponding to high density has exactly one connected component. But analytically I think the reformulation in the second to last paragraph makes more sense: it says that essentially there will be one large region where people are concentrated, and essentially there will be one large region where people are sparse, with some intermediate zones due to stochastic blips.2011-02-10
  • 0
    @Willie: If the region of queue(or jam if this is though of as traffic) is defined slightly differently, we can get rid of that difficulty. The definition in English is that if there is a jam, it can only disintegrate (lose cars from front) or become bigger from the back, but it is not allowed to split. So if it does split, we still call it a bigger jam.2011-02-10
  • 0
    @picakhu: define split. And is a jam allowed to move? If not, I don't see how you true can possibly be true for large $\alpha$. If yes, there will always be non-zero possibility of spontaneous splitting. The whole exercise above is trying to give mathematical meaning to intuitive concepts. Switching to using other English words doesn't help.2011-02-10
  • 0
    @Willie: I wanted to avoid using mathematical definitions. Anyway, for any "non-free" set of cars, we define the car furthest in front as the first car(person). We similarly define the furthest back as the last car. Next, if a car is added from the back, the new car is now defined as the last car, and if a car is "lost" from the front, the car directly after it is the first car. "lost" means became a free car. Thus, with this definition, jams can only grow, or break up(all the front cars leave), but never "split", because that is not allowed.2011-02-11
  • 0
    The challenge is to prove that with such a definition(which implies that there will eventually be just one jam), and infinitely many cars, we cannot get the jam to "catch up" with itself. Which implies some sort of "splitting".2011-02-11
  • 1
    @picakhu: You said, "I wanted to avoid using mathematical definitions". Unfortunately, I guess I won't be help you then. But let me poke a hole in your intuition: you've so far explained why you think that if you start from one jam, you won't split to form more. But what about two jams? In some sort of a steady state, the expected rate of car loss from one jam should be the same as the gain from the other. For two jams to coalese, you need the essentially the jam in front to gain cars faster than the jam behind loses them.2011-02-11
  • 0
    @Willie: yes that is correct. Why is it that not possible? I claim, (which I think is not difficult to prove, though I am not sure), that the probability that we have just one jam as time goes to infinity, is 1.2011-02-11
  • 0
    @picakhu: I don't claim it is impossible. I claim that *I don't* see how it is possible. The problem for me is that the laws of motion for cars/people are essentially local, so I don't see what drives the asymmetry. (A jam's evolution should not be effected by how far away the next jam in front of it, or behind it, is, as long as it is sufficiently far.)2011-02-13
  • 0
    @Willies: I guess it takes getting used to that idea. Even though I have played with this kind of simulations for about a year now, I am still uncertain about the macro picture about how the cars/people are actually interacting. Actually, I think no matter how far the jams are apart, they still influence each other. (if a jam were to release a larger than normal proportion of cars, the jam in front would grow at a rate greater than what it would have otherwise)2011-02-14
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 )

  • 0
    @leonboy: is there a minimal version of firefox required? I am running 3.6.13 on linux and can't see anything happening on the simulation page? (Also, since you obviously have the skills: if you have time, can you try running some simulations on the parameters I suggested in my last comment on the main question?)2011-02-08
  • 0
    It had a bug, fixed.2011-02-08
  • 0
    @leonbloy, I'll try what you claim to be the same and let you test out my code. My program works a little better than yours (easier to see what is happening) but will take me a while to finish since I was working on it in a different way till now.2011-02-08
  • 0
    @leonbloy, My program is posted. I am in the process of testing your claim. Ill let you know if I think you are right. But so far, it seems you are.2011-02-09
  • 0
    I wonder how are you testing it. Let me add this property: in the hard rods model (in the thermodynamic limit) the probability distribution of distances (between consecutive particles) is a exponential - truncated at the colition distance. And (this would be also important to check) they are all independent.2011-02-09
  • 0
    @leonbloy, I was testing your claim that having a look ahead of one spot is sufficient to see clustering.2011-02-09
  • 0
    Visual examination can't tell much about that "clustering". I relevant indicator, I think, might be the correlation of consecutive distances. If my analogy with the hard-rod gas applies, this should be zero.2011-02-09
  • 0
    @leonbloy: The hard-rod gas is hardly typical. This model clearly develops at least short-range correlations, wouldn't you say?2011-02-09