Colliding Bullets

Question

I saw this problem yesterday on reddit and I can't come up with a reasonable way to work it out.

---

Once per second, a bullet is fired starting from $x=0$ with a uniformly random speed in $[0,1]$. If two bullets collide, they both disappear. If we fire $N$ bullets, what is the probability that at least one bullet escapes to infinity? What if we fire an infinite number of bullets?

Attempt.

• If $N$ is two, then it's equal to the probability that the first bullet is faster than the second, which is $\dfrac{1}{2}$.

• If $N$ is odd, the probability of three bullets or more colliding in the same spot is $0$, so we can safely ignore this event. And since collisions destroy two bullets then there will be an odd number of bullets at the end. So at least one escapes to infinity.

For infinite bullets, I suspect that no single bullet will escape to infinity, but that they'll reach any arbitrarily big number. Although, I'm not sure on how I'd begin proving it.

Is there a closed form solution for even $N$? Or some sort of asymptotic behavior?

Answer 1

I did some experiment with Mathematica for even $N$ and found some regularities, but I don't have an explanation for them at the moment.

1) If we fix $N$ different speeds for the bullets and count how many bullets escape to infinity for all the $N!$ permutations of those speeds among bullets, then the result doesn't seem to depend on the chosen speeds. In particular, I consistently found that only in $\bigl((N-1)!!\bigr)^2$ cases out of $N!$ no bullet reaches infinity (checked for $N$ equal to 4, 6, 8, 10).

2) Running a simulation (1,000,000 trials) the probability that no bullet reaches infinity is consistent with the above result, i.e. $\bigl((N-1)!!\bigr)^2/N!$, for $N$ equal to 4, 6, 8.

Answer 2

Among the $N$ bullets fired at time $0,1,2...N$ (with $N$ even), let us call $B_{\max, N}$ the one with the highest velocity. We have two cases:

• if $B_{\max, N}$ is the first bullet that has been fired, then it will escape to infinity: the probability of this event is $\dfrac{1}{N}$;

• if $B_{\max, N}$ is any one of the other bullets (probability $\dfrac{N-1}{N}$), we can consider the pair of consecutive bullets $B_k$ and $B_{k+1}$ where the expected time to collision is the shortest (with $B_{k+1}$, fired at time $k+1$, faster than $B_{k}$, fired at time $k$). This pair will be the first to collide.

Now let us cancel out the two bullets that have collided, so that there remain $N-2$ bullets. Applying the same considerations explained above, we can call $B_{\max, N-2}$ the bullet with the highest velocity among these remaining $N-2$ ones (note that $B_{\max, N}$ and $B_{\max, N-2}$ can be the same bullet, since the first pair that collides does not necessary include $B_{\max, N}$). Again, we have two cases:

• if $B_{\max, N-2}$ is the first bullet that has been fired among the $N-2$ ones that now we are considering, then it will escape to infinity: assuming uniformity,the probability of this event is $\dfrac{1}{N-2}$;

• if $B_{\max, N-2}$ is any one of the other bullets, then it will not escape to infinity, since it will necessary collide with a bullet that, among these $N-2$ ones, has been fired before it: the probability of this event is $\dfrac{N-3}{N-2}$. Again we can now consider the pair of consecutive bullets $B_j$ and $B_{j+1}$ (with $B_{j+1}$ faster than $B_{j}$) where the expected time to collision is the shortest. This pair will be the second to collide.

Continuing in this way we get that the probability that none of the bullets escape to infinity is

$$\frac{(N-1)!!}{N!!}$$

that is equivalent to

$$\frac{[(N-1)!!]^2}{N!}$$

EDIT: This answer assumes that, in any step, the probability that $B_{\max, N-2k}$ is the first fired bullet among the remaining $N-2k$ ones is $\dfrac{1}{N-2k}$. This uniformity assumption remains to be demonstrated.

Answer 3

[Revised answer: 2015-11-28]

Contrary to my initial thoughts the arrangements with more than one different scenario as outcome are not necessarily equiprobable (see below for more information).

But it is an interesting aspect that despite this asymmetry there seem to exist corresponding arrangements which show the same probabilities but differently mapped to the scenarios. This kind of balancing implies that the assumed probability that none of the bullets escape to infinity is still $\frac{(N-1)!!}{N!!}$ for even $N$.

This is a somewhat closer look at the first non-trivial case with $N=4$ bullets and a proposal stated in the summary how we could consider this problem.

Example: $N=4$

Let's number the bullets in chronological order according to the time they are fired. The first with number $1$, followed by $2,3$ and $4$, each of them fired with uniformly random speed in $[0,1]$.

We write the bullets sorted with respect to the order of their speed resulting in $4!=24$ different arrangements. The permutation \begin{align*} 2\ 1\ 4\ 3\tag{1} \end{align*} means, that the bullet $2$ is the fastest, followed by $1$ and the bullet with number $3$ is the slowest one. Since the order of firing is $1 2 3 4$ we see that in (1) the bullet number $2$ is faster than $1$ and so they will collide. We also see that $4$ is faster than $3$ and they will also collide.

Note, that it is irrelevant if $1$ collides with $2$ before or after $3$ collides with $4$. What matters is solely the order, the inversions of the permutation $2 1 4 3$ according to the speed of the bullets. So, in case (1) all bullets will collide and vanish.

Before we systematically write down the $24$ different cases let's consider another much more interesting example, namely

\begin{align*} 3\ 4\ 2\ 1 \end{align*}

We see that $3$ is the fastest bullet and it could collide with $2$. But since $2$ is faster than $1$, the bullet $2$ could instead collide with $1$ before the bullet $3$ reaches bullet $2$.

Here are two different scenarios to consider with two different outcomes. One scenario is the collision of $2$ with $1$ leaving two bullets $3$ and $4$ which won't collide, since $3$ is faster than $4$. \begin{align*} 3\ 4\ 2\ 1 \rightarrow 3\ 4 \end{align*} The other scenario is a collision of $3$ with $2$ and since $4$ is faster than $1$, they will also collide. We obtain \begin{align*} 3\ 4\ 2\ 1 \rightarrow 4\ 1\rightarrow \emptyset \end{align*} So, we have two different scenarios, one with two bullets as outcome, while all bullets vanish in the other scenario.

$$ $$

The gory details:

We now analyse more detailed these scenarios. Let's denote the speed of the bullet $j$ with $v_j$ . We obtain \begin{align*} 1>v_3>v_4>v_2>v_1>0 \end{align*} The bullet $2$ is faster than bullet $1$. But bullet $1$ was fired one second before bullet $2$. So, after $t$ units of time the travelled distance by bullet $2$ is $tv_2$ units while the distance travelled by bullet $1$ is $(t+1)v_1$ units. They will collide if $tv_2=(t+1)v_1$, i.e. \begin{align*} t&=\frac{v_1}{v2-v1} \end{align*}

Similarly, since $v_3>v_2$ bullet $3$ will collide with bullet $2$ if \begin{align*} t&=\frac{v_2}{v3-v2} \end{align*}

Observe that bullet $3$ was fired one second after bullet $2$ and this gives rise to an asymmetry. Bullet $3$ will not collide with bullet $2$ if there was already a collision in the second before bullet $3$ was fired. So, bullet $3$ will collide with bullet $2$ only if \begin{align*} \frac{v_1}{v_2-v_1}>1+\frac{v_2}{v_3-v_2} \end{align*}

A simulation of this scenario gives roughly a proportion of \begin{align*} 28:13 \end{align*} in favor of a collision of bullet $2$ with bullet $1$, so that bullets $4$ and $3$ will escape to infinity. It's quite plausible that bullet $2$ will collide with bullet $1$ with higher probability, since all bullets were uniformly fired and bullet $2$ has one second advantage compared with bullet $3$.

$$ $$

One more surprising fact:

Although the discussion of this example was a bit cumbersome, we should have a look at one more example. Let's study the permutation $3\ 2\ 4\ 1$ which means

\begin{align*} 1>v_3>v_2>v_4>v_1>0 \end{align*}

with the scenarios

\begin{align*} 3\ 2\ 4\ 1 \rightarrow 1\ 4 \end{align*} and \begin{align*} 3\ 2\ 4\ 1 \rightarrow 2\ 1\rightarrow \emptyset \end{align*}

It looks pretty much the same as the example above, but a simulation gives the result

\begin{align*} 40:2 \end{align*} in favor of a collision of bullet $2$ with bullet $1$.

So, why was the proportion $28:13$ in the situation above and now there is the much greater proportion $40:2$?

Since we consider specific arrangements, the speed $v_j$ of the bullets are no longer independent, but follow a specific order. In the first situation the bullet $2$ is slower than bullet $3$ and bullet $4$. But even in that case the advantage of one second is sufficient that a collision with the slowest bullet $1$ is more than twice often than a collision of bullet $3$ with bullet $2$.

In the current situation bullet $2$ is faster than bullet $1$ and even faster than bullet $4$, so that together with the bonus of one second the probability of a collision with bullet $1$ is much greater than in the former case resulting in the proportion $40:2$.

Now something for relaxing, but one more interesting aspect to follow...

Twenty-four arrangements

Here is a list of all $24$ arrangements of four bullets together with their outcomes. The values in brackets give the number of bullets which will escape to infinity. Some permutations give rise to more than one scenario. This is indicated by more than one bracketed value in one line.

\begin{array}{ccrrcrr} 1\ 2\ 3\ 4&&&(4)\\ 1\ 2\ 4\ 3&\rightarrow&1\ 2&(2)\\ 1\ 3\ 2\ 4&\rightarrow&1\ 4&(2)\\ 1\ 3\ 4\ 2&\rightarrow&1\ 4&(2)\\ 1\ 4\ 2\ 3&\rightarrow&1\ 2&(2)\\ 1\ 4\ 3\ 2&\rightarrow&1\ 2&(2)&\rightarrow&1\ 4&(2)\\ \\ 2\ 1\ 3\ 4&\rightarrow&3\ 4&(2)\\ \color{blue}{2\ 1\ 4\ 3}&\rightarrow&\emptyset&(0)\\ 2\ 3\ 1\ 4&\rightarrow&3\ 4&(2)\\ 2\ 3\ 4\ 1&\rightarrow&3\ 4&(2)\\ \color{blue}{2\ 4\ 1\ 3}&\rightarrow&\emptyset&(0)\\ \color{blue}{2\ 4\ 3\ 3}&\rightarrow&\emptyset&(0)\\ \\ 3\ 1\ 2\ 4&\rightarrow&1\ 4&(2)\\ 3\ 1\ 4\ 2&\rightarrow&1\ 4&(2)\\ 3\ 2\ 1\ 4&\rightarrow&1\ 4&(2)&\rightarrow&3\ 4&(2)\\ \color{blue}{3\ 2\ 4\ 1}&\rightarrow&3\ 4&(2)&\rightarrow&\emptyset&(0)\\ \color{blue}{3\ 4\ 1\ 2}&\rightarrow&\emptyset&(0)\\ \color{blue}{3\ 4\ 2\ 1}&\rightarrow&3\ 4&(2)&\rightarrow&\emptyset&(0)\\ \\ 4\ 1\ 2\ 3&\rightarrow&1\ 2&(2)\\ \color{blue}{4\ 1\ 3\ 2}&\rightarrow&1\ 2&(2)&\rightarrow&\emptyset&(0)\\ \color{blue}{4\ 2\ 1\ 3}&\rightarrow&\emptyset&(0)\\ \color{blue}{4\ 2\ 3\ 1}&\rightarrow&\emptyset&(0)\\ \color{blue}{4\ 3\ 1\ 2}&\rightarrow&1\ 2&(2)&\rightarrow&\emptyset&(0)\\ \color{blue}{4\ 3\ 2\ 1}&\rightarrow&\emptyset&(0)&\rightarrow&\emptyset&(0)\\ \end{array}

$$ $$

Corresponding arrangements:

We see in the table above two more arrangements $4\ 1\ 3\ 2$ and $4\ 3\ 1\ 2$ resulting in two different scenarios.

When we look at $4\ 1\ 3\ 2$ with \begin{align*} 1>v_4>v_1>v_3>v_2>0 \end{align*} and the scenarios \begin{align*} 4\ 1\ 3\ 2 \rightarrow 1\ 2 \end{align*} and \begin{align*} 4\ 1\ 3\ 2 \rightarrow 1\ 4\rightarrow \emptyset \end{align*}

we are in the same situation as in $3\ 4\ 2\ 1$. Here the bullet $3$ is faster by one rank than $2$ in the same way as bullet $2$ is faster than bullet $1$ in the former scenario $3\ 4\ 2\ 1$ (both with rank $3$ and $4$). Furthermore is here bullet $4$ the fastest and two ranks faster than bullet $3$, analogously to the former scenario where bullet $3$ was the fastest and two ranks faster then bullet $2$.

So, a simulation gives \begin{align*} 28:13 \end{align*} but this time with the alternate outcome, that bullet $4$ and bullet $2$ will collide with proportion $28:13$ while in the former scenario bullet $3$ and bullet $4$ will escape to infinity with the same proportion.

Now, as we might expect, the fourth scenario $4\ 3\ 1\ 2$ results in a proportion of roughly \begin{align*} 40:2 \end{align*} with alternate outcome to $3\ 2\ 4\ 1$.

$$ $$

Conclusion:

Based on the tabulated values and the simulation in case of arrangements with different scenarios we calculate the probability that none of the $4$ bullets escape to infinity. If a permutation gives rise to exactly one scenario its proportion is $\frac{1}{24}$.

• There are six permutations with exactly one scenario where all bullets collide, resulting in $\frac{6}{24}$

• One permutation $4\ 3\ 2\ 1$ with two scenarios where all bullets collide, resulting in $\frac{2}{48}$

• Four permutations with two scenarios and one of them with all bullets colliding, resulting based upon simulation roughly in \begin{align*} \left(\frac{40}{42}+\frac{2}{42}\right)\frac{1}{24}+\left(\frac{28}{41}+\frac{13}{41}\right)\frac{1}{24} \end{align*}

We conclude: The probability that none of the $4$ bullets escape to infinity is \begin{align*} \frac{6}{24}+\frac{2}{48}+\frac{2}{24}=\frac{3}{8} \end{align*}

Note, that $\frac{3}{8}$ corresponds to \begin{align*} \frac{(N-1)!!}{N!!} \end{align*} with $N=4$ according to the formula presented by the other answers.

$$ $$

Summary:

• The problem can be reduced to the study of permutations and their inversions in order to retrieve all arrangements with scenarios where no bullets escape to infinity.

• An approach could be to look for a representation of the permutations by a symbolic equation (similar to examples given in Analytic Combinatorics by P. Flajolet and R. Sedgewick).

• The arrangements with different scenarios need a deeper analysis respecting also the time domain.

• It seems, that despite the different scenarios with different probabilities corresponding arrangements provide a symmetry so that the probability $\frac{(N-1)!!}{N!!}$ for even $N$ still holds.

Answer 4

Just for reference, I found a recent (yes, it's a today's posting!) arXiv paper about this problem and its variants.

https://arxiv.org/abs/1709.00789

If I skimmed over correctly, it considers various scenarios about randomness of bullet speeds and shooting interval and shows that the number of survival bullets have all the same distributions.