11

Here's an amusing problem brought to me by a student. Although it was originally phrased in terms of mutually annihilating bullets fired at regular intervals by a gun, I thought you might enjoy a more peaceable presentation.

In the infinite flat world of Oz, the Yellow Brick Road begins in the center of the Emerald City, unwinds across the countryside, and proceeds forever without crossing itself. At noon each day, one lusty young hermaphroditic Tribble sets out rolling along this road from its origin at a uniformly randomly chosen speed of up to one kilometer per day. Throughout its journey it will keep rolling at the same speed, never stopping. But if ever one Tribble overtakes another on the road, each instantly recognizes its soulmate and the two drop off to the side (presumably to reproduce and eventually supply more Tribbles back home).

As you know, such matings occur often, because the chance of any two Tribbles rolling at exactly the same speed is zero. Oh happy Tribbles! But is life guaranteed to be good for all of them?

What is the chance that at least one Tribble continues forever, never overtaking or being overtaken?

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • 2
    Does this assume that Tribbles began traveling at a particular time point (so that there was Tribble #1) and continue forever since then, and the probability should be computed over this infinite time span? – amoeba Mar 31 '16 at 20:54
  • 1
    @amoeba If you find it makes a difference to assume there was a definite starting time, then it would be very interesting to analyze that difference. – whuber Mar 31 '16 at 20:58
  • 4
    http://math.stackexchange.com/questions/1526292/colliding-bullets – Alex R. Apr 01 '16 at 01:02
  • 2
    Tribbles in Oz? Your fictional universes seem a bit mixed up. – Kodiologist Jul 18 '17 at 17:10
  • 3
    @Kodio Both universes are well known for intersecting other universes :-). – whuber Jul 18 '17 at 18:00

1 Answers1

3

Edit: I seem to have mixed up the idea of positive probability and probability 1. The statement proved here is much weaker than I was hoping.

Intuitively, the answer is 0. It's not hard to prove that

Any given Tribble, with positive probability, eventually gets a mate.

But I think this might not be enough to imply that with positive probability, every tribble eventually gets a mate, per Zeno's paradox.

Here's a proof of the quoted statement. First, let's replace the problem with a simpler alternative formulation as follows. There is a stack that starts empty. A computer draws random variates in sequence independently and uniformly from [0, 1]. Each time a value is drawn, the stack changes.

  • If the stack is empty, or the top item on the stack has a greater value, then a new item is added with the new value. (A bullet slower than the last bullet or a Tribble slower than the last Tribble has been created.)
  • Otherwise, the top item is removed. (The bullets or Tribbles collide.)

(This formulation doesn't include the event of a bullet or Tribble faster than the previous one being created but then being destroyed before it hits the previous one, but such an event leaves the stack the same, so it's of no consequence.)

I want to prove that any given item, with positive probability, is eventually removed from the stack. We may assume without loss of generality that the value $1$ is never drawn, since the probability of this ever happening is 0. Let $I_0$ be an existing item and $v_0$ its value. Let $k$ be the number of items above $I_0$, and $v_1,\; v_2,\; …,\; v_k$ their values in order, with $v_k$ being the value of the current top item. If the next $k + 1$ values to be drawn land in, respectively, the interval $(v_k, 1)$, the interval $(v_{k-1}, 1)$, and so on until $(v_0, 1)$, then $I_0$ and all the items above it will be removed. The probability of this event is $(1 - v_k)(1 - v_{k-1})\cdots(1 - v_0)$, which is a finite product of positive numbers, so it's positive.

Kodiologist
  • 19,063
  • 2
  • 36
  • 68