53
$\begingroup$

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?

If $N$ is two, then it's equal to the probability that the first bullet is faster than the second, which is $\frac{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?

$\endgroup$
  • $\begingroup$ Suppose the first bullet has speed $\frac{1}{4}$, the second bullet has speed $\frac{3}{8}$ and the third bullet has speed $\frac{3}{4}$. Won't they all collide at $t=3$? $\endgroup$ – John Douma Nov 12 '15 at 20:58
  • 6
    $\begingroup$ @JohnDouma Yes, but any exact condition on speeds happens with probability zero. In particular, when you have two bullets that collide at some point. For the third to collide at that same point, there's only one value of speed for which this works, so it's almost impossible. $\endgroup$ – Kitegi Nov 12 '15 at 21:01
  • $\begingroup$ It seems to me like we need to expand consideration to any continuous distribution of speeds and arbitrary firing times $t_i$ (s.t. $t_i\to \infty$) and arbitrarily firing position to somehow inductively show that $p(D_{2N})=\prod_{i=1}^{N}\frac {2i-1}{2i}$ in general for all these set-ups (since base case $N=1$ is satisfied always). But conditioning on the first collision changes distribution of speeds of the bullets left and possibly differently for different bullets. If we could show that all new conditional speeds are equally distributed, we are done. $\endgroup$ – A.S. Nov 15 '15 at 4:18
  • $\begingroup$ @A.S. I don't think we need to consider arbitrary speed distributions in this case (although, I think you're right about the distribution being irrelevant). Also, I think that considering both arbitrary starting positions and arbitrary firing times is redundant. One of them should be enough. $\endgroup$ – Kitegi Nov 15 '15 at 10:43
  • 4
    $\begingroup$ See also math.stackexchange.com/questions/1040479/shooting-bullets $\endgroup$ – Hetebrij Nov 21 '15 at 14:37
22
$\begingroup$

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 $\frac{1}{N}$;

  • if $B_{max, N}$ is any one of the other bullets (probability $\frac{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 $\frac{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 $\frac{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 $\frac{1}{N-2k}$. This uniformity assumption remains to be demonstrated.

$\endgroup$
  • $\begingroup$ Very nicely done! $\endgroup$ – nbubis Nov 14 '15 at 22:36
  • $\begingroup$ What if the fastest bullet isn't the first one to collide? $\endgroup$ – Kitegi Nov 14 '15 at 22:41
  • 2
    $\begingroup$ Whether the fastest bullet is or is not the first to collide does not matter. We only have to progressively cancel out "pairs" of bullets to arrive to the final result. $\endgroup$ – Anatoly Nov 14 '15 at 23:09
  • 4
    $\begingroup$ You say that after the first collision, the probability that $B_{max,N-2}$ is the first bullet is $\frac{1}{N-2}$. I'm not sure this is the case. I agree that all the positions are equally likely for $B_{max,N}$. But it may not be true for $B_{max,N-2}$, $B_{max,N-4}$ and so on. What if the collisions mess up the "uniformity" of the positions? $\endgroup$ – Kitegi Nov 15 '15 at 0:40
  • 4
    $\begingroup$ > if $B_{max,N}$ is any one of the other bullets, then it will not escape to infinity, since it will necessary collide with a bullet that has been fired before it: It's not true. Consider 4 bullets with the speeds (from the first to the last) $0.1, 0.9, 1, 0.2$. Then the first two bullets will collide before the third (and the fastest) bullet catches up with the second one, which will allow it to escape to infinity. $\endgroup$ – Litho Nov 16 '15 at 12:56
14
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow! That's a pretty weird result. Somebody came up with the same thing here. Do you have any idea why this is true? $\endgroup$ – Kitegi Nov 13 '15 at 15:56
  • $\begingroup$ You are right: that post you link gives exactly the same results. I have no idea why that should work. Probably the formula coming from the permutations can be justified somehow, but I would like to understand why speed values are unimportant and only their order matters. $\endgroup$ – Aretino Nov 13 '15 at 17:04
  • $\begingroup$ The result does depend on the chosen speeds. Fire four bullets at times t=0, 1, 2, and 3, and at speeds 400, 200, 300, and 500 (metres per second, say, although the units don't matter). Then bullets 2 and 3 collide at time t=4, after travelling 600 metres; and bullets 1 and 4 collide at time t=15, after travelling 6000 metres. But if the fourth bullet were faster than 600m/s, it would catch the third bullet before t=4, letting the first two bullets survive. $\endgroup$ – TonyK Nov 14 '15 at 21:24
  • $\begingroup$ @TonyK I think what he meant was that, if you fix a list $2N$ speeds, then the number of permutations for which a bullet escapes to infinity does not depend of the speeds. So for your example, having a speed larger than 600 gives a valid solution, but if what he found was true, then some other permutation of your list of speeds, which worked for $v<600$, will stop working for $v>600$ $\endgroup$ – Kitegi Nov 14 '15 at 22:23
  • $\begingroup$ @TonyK Yes, indeed: the result from a single choice of velocities can depend on their values, but if you consider all the permutations, that dependence cancels out. $\endgroup$ – Aretino Nov 14 '15 at 22:26
7
+200
$\begingroup$

[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.

$\endgroup$
  • $\begingroup$ When a permutation gives two different results, how do we know that they're equally likely? $\endgroup$ – Kitegi Nov 26 '15 at 11:10
  • $\begingroup$ @Farnight: You're right. I had to revise my answer. $\endgroup$ – Markus Scheuer Nov 28 '15 at 19:50
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

We recently posted a result about survival of the first bullet with infinitely many bullets taking uniform speeds from a discrete set:

https://128.84.21.199/abs/1610.00282

The canonical example is when speeds are from {1,2,3}. We show that an initial bullet with speed 2 survives with positive probability, while an initial bullet with speed 1 is annihilated almost surely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.