Suppose we have intervals of alternating color on $\mathbb{R}$ (say, red / blue / red / blue / …). All intervals have independent length, with all red intervals distributed as $\mathbb{P}_{R}$, all blue intervals distributed as $\mathbb{P}_B$.
Once the intervals are generated, I update them iteratively as follows: if an interval is smaller than its two immediate neighbors, then it get swallowed by its neighbors: all three intervals join to become one big interval of the same color as the two end ones.
For example, if we have: … (red 2) (blue 3) (red 4) (blue 1) (red 3) (blue 4) (red 5) …
Then the next step we will see … (red 2) (blue 3) (red 8) (blue 4) (red 5) …
And the next step we will see … (red 2) (blue 3) (red 17) …
And so on.
The question is: does one color eventually wins out, or do the two colors switch back and forth infinitely often? Concretely: for any fixed point $x \in \mathbb{R}$, if $B_n(x)$ denotes the color of $x$ at time step $n$ (= 1 if blue, = 0 if red), then will the sequence $\{B_n(x)\}$ converges, or will it visit 1 and 0 infinitely often (with probability 1)?
Clearly we need to know something about the two distributions. Then, the question really is: under what assumptions on $\mathbb{P}_R$ and $\mathbb{P}_B$ can we answer the above question?
One can check that the process is well defined, in the sense that it doesn't matter which interval is updated first. Also, for the process to get stuck, one needs to have an infinite sequence of increasing numbers, and this happens with probability 0. We further assume that the distributions are such that there is no tie between intervals with positive probability. (E.g.: when the distributions are continuous.)
We know the following:
If $\mathbb{P}_R = \mathbb{P}_B$ (that is, if red and blue have the same distributions), then the answer is infinitely often w.p. 1.
Proof: for any point $x$, the events of {converge to 1} and {converge to 0} lie in the tail sigma-field, hence occur w.p. 1 or 0. But by symmetry they have the same probability, hence it must be 0. Since the process is translation invariant, sequences $\{B_n(x)\}$ have the same tail distribution at all points, and hence there is no convergence in color for the whole line. (In particular, this argument implies that if one point converges to a color with probability 1, then the whole line converges to the same color with probability 1). ▢
THOUGHTS:
Intuitively, suppose that at the start, red has a slight "advantage" over blue. (Say, $\mathbb{P}_R$ stochastically dominates $\mathbb{P}_B$.) Then one would expect this advantage to get amplified in later rounds, and eventually red wins with probability 1. But we can't find a concrete proof of this. The hardest step seems to be finding a characterization of "advantage" (that is, a property of a distribution relative to another) that is invariant under updates, and tells us that it improves the probability of one color winning eventually. Stochastic domination is a fairly strong assumption — we think that there should be a milder condition.
For a toy case, a simple example is when all red intervals have length 1, and all blue intervals have length either $1 - \epsilon_1$ or $1 + \epsilon_2$, where $\epsilon_1, \epsilon_2$ are distinct irrational numbers (so as to stop having ties with positive probability).
For simple examples as above, one can write down the distribution of red and blue after step 1 of the update (one step of the update means: updating all local minima in the previous round) — note that the intervals of the same color are still i.i.d., but red and blue are not independent (since we know that the surviving blues and reds have to have "big" size to stop the neighbor from expanding). However, I think they should be exchangeable, in which case it might be easier to do the following:
- update the process once. Now red and blue have new distributions $\mathbb{P}_R'$ and $\mathbb{P}_B'$;
- "peel off" all the reds and blue and "shuffle" them (that is: generate another sequence of interlacing red/blue following the new distribution). Then run another update.
If we have exchangeability, then this does not change the tail distribution. But analytically it is easier to work with. And now one can search for the characterization of an "advantage" that get amplified in further updates.
For instance, one might hope that if red has a "huge advantage" over blue, then $P(B_n(x) = 1)$ decays fast enough so $\sum_{n}P(B_n(x) = 1) < \infty$, then the result follows from Borel–Cantelli. Then the next step would be to show that one can reach this "huge advantage" starting from a "small advantage" in finite time step.
Intuitively it seems that the tightest (minimal definition of advantage) would be $P(B_0(x) = 1) < 1/2$. In this case we can compute and show that $P(B_n(x) = 1)$ is a monotone decreasing function in $n$, but quantifying the rate seems very difficult.
If anybody has fresh idea to approach this problem, please let me know!
Here are some updates on this problem: We can also run this problem in continuous time as follows: at each end point of the intervals there is a balloon. At time $t$ the balloon as radius $t/2$. When two balloons meet they "pop", and the two points are removed from the line.
This put the process in the world of stable matching, hierarchical coalescent process, and some other physics literature. The advantage of this continuous time approach is that one can check that the sequence of points after running for some time $T$ is still a renewal process, and furthermore, one can write down a set of ODEs for the Laplace transform of the distribution of the two lengths. In fact, if the distribution $P_R$ and $P_B$ are identical, then one can show that the normalized length $X_t/t$ converges to a "universal" limit. (Universal in the sense that it almost doesn't depend on the initial distribution).
The relevant paper is: Faggionato, Roberto, and Toninelli - Universality for one-dimensional hierarchical coalescence processes with double and triple merges.
This paper considers a very similar situation, so to apply the result in this paper directly one needs to do a little argument, which unfortunately does not carry over when $P_R$ and $P_B$ have different distributions. I'll skip writing down the argument because I think that we might benefit from a fresh approach.
Edit (Stefan Kohl, 2021-05-01): I undeleted this highly upvoted question which was deleted single-handedly by an (at that time) SE employee in 2014, since I didn't see a reason why it should be deleted. If there is a reason why it should be deleted, feel free to delete again.
