Each month, IBM publish a mathematical puzzle. For example in May 2014 they posted
The Colliding Bullets Puzzle:
Every second, a gun shoots a bullet in the same direction at a random constant speed between 0 and 1.
The speeds of the bullets are independent uniform random variables. Each bullet keeps the exact same speed and when two bullets collide, they are both annihilated.
After shooting 20 bullets, what is the probability that eventually all the bullets will be annihilated?
Please supply the answer rounded to the 10th decimal digit.
It is reasonably straight-forward to let a Monte-Carlo engine work it out.
For example see
this link to Java code in github.
However, to get an answer to an accuracy of 10 decimal digits would take a lot of computing power or a more clever algorithm.
Let \(v_i\) be the speed of bullet
i
( I’m going to use a zero based numbering system, not because I really like it, but rather to be consistent with the Java code. It makes it simpler to transition between the two. ).
We're assuming that the bullets are infinitesimally small and the the probability of 3 colliding together at the same point in time and space is (almost surely) zero.
Also, we note that collisions can only take place between odd and even bullets. We can't have two even-numbered bullets colliding together.
To explain why, we consider what would happen if two even bullets were to collide. Then we would need all the intermediate bullets to have been annihilated. And the number of bullets between say bullet 2m and 2(m+n) is 2n-1 which is odd. But bullets only annihilate in pairs. So we can't have an odd number of intermediate bullets annihilating. Thus two even bullets cannot collide with each other. Similarly two odd bullets cannot collide with each other.
(Far) below we deal with the case when we have 4 bullets but first we'll look at an more general case, with generalized initial conditions.
Suppose \(2N\) bullets are fired. We will label the starting condition to be \(\mathcal{J}_{2N} (\textbf{X},\textbf{t})\):
each bullet has position \(X_i\) with
\(X_i \ge X_{i+1} \) and \(X_i \ge 0 \ \ \ \ \ \forall i: 0 \le i \le N-1 \)
start times: \(t_i \) with
\(t_i \le t_{i+1} \) and \(t_i \ge 0 \ \ \ \ \forall i: 0 \le i \le N-1 \)
and speeds as before \(v_i \sim U(0,1) \)
We define \(\mathcal{A}_{2N} \) to be the probability that all bullets released in our generalized version will be annihilated.
In the case when there are 2 bullets ( \(N=1 \) )
they will collide when \(v_0 < v_1\).
Otherwise they won't.
So the probability that they annihilate each other is:
\[\mathcal{A}_{2} = \frac{1}{2}\]
Now consider the case when we have an even number of bullets and there are more than 2 of them, i.e \(N>1\):
The only case when there are no collisions at all is when the velocities are strictly ordered:
\[v_i > v_{i+1} \ \ \ \ \ \forall i: 0 \le i < N-1 \]
In that case, the first bullet is the fastest and the last is the slowest.
On the other hand, if last is not the slowest, then we know there will be at least one collision.
The probability that the last is not the slowest is: \(p_{2N} = \frac{2N-1}{2N} \).
In this case, when the last is not the slowest there will a first collision. We don't know which pair will collide first, but we know that the first collision will definitely occur.
After this first collision occurs, we then have 2 fewer remaining bullets.
Immediately after the first collision we will then have a valid starting condition \(\mathcal{J}_{2N-2}(\textbf{X}',\textbf{t}') \).
If all the original 2N bullets are to be annihilated, then we will need the remaining (2N-2) bullets to be annihilated and so we find:
\[\mathcal{A}_{2N} = \frac{2N-1}{2N} \mathcal{A}_{2N-2}\]
Using this recursive definition we find:
\[\mathcal{A}_{2N}=\prod_{n=1}^N\frac{2n-1}{2n}\]
Alternative approaches
Integration
Another way to try to get the solution is to analytically do integrals over the probability density functions and thus end up with an exact solution.
Now lets move on to the case when we have 4 bullets.
We'll introduce some notation. The probability that all 4 bullets will be annihilated is:
\[A_4= \Phi (**,|/) + \Phi (\bigwedge,\bigwedge) + \Phi (|/,\bigwedge) \]
Where:
\(\Phi (**,|/)\)is the contribution from the case when we don’t have any restrictions on the first pair and \(v_2 < v_3\).
I.e. the second pair is NOT on a collision course.
\(\Phi (\bigwedge,\bigwedge)\) is the contribution from the case when \(v_0 < v_1\) and \(v_2 < v_3\).
I.e. that's the case when the first are on a collision course and so are the second pair. Though it doesn't necessarily mean that the first pair will collide with each other.
\(\Phi (|/,\bigwedge)\) is the contribution from the case when \(v_1 < v_0\) and \(v_2 < v_3\).
i.e. the first pair are NOT on a collision course, but the second pair are.
First lets evaluate \(\Phi (**,|/)\). In this case the second pair are not on a collision course.
For all to be annihilated we must have a collision between bullets 1 and 2 and then a collision between 0 and 3.
We first work out the minimum velocity of \(v_0\) required to ensure that bullets 0 and 1 do not collide before the collision of bullets 1 and 2.
With a little bit of algebra ( and or geometry ) we find that minimum velocity to be:
\[\beta=\frac{v_1 v_2}{2 v_2 - v_1}\]
So we have the constraints:
\[0 < v_2 < 1 \]
\[0 < v_1 < v_2 \]
\[\beta < v_0 < v_2 \]
\[v_0 < v_3 < v_2 \]
Note that the probability density function of each of the velocities \(v_i\) is 1 inside the range 0 to 1. And it is zero outside.
The (subtle) difference between the condition \( v_2 < 1 \) and \( v_2 \leq 1 \) is on a set of zero measure which won't affect our results.
Integrating over the probability space we find:
\[\Phi (**,|/)=\int_0^1 dv_2 \int_0^{v_2}dv_1 \int_{\beta}^{v_2}dv_0 \int_{v_0}^{v_2}dv_3 \]
Doing the \(dv_3\) integral we find:
\[\Phi (**,|/)=\int_0^1 dv_2 \int_0^{v_2}dv_1 \int_{\beta}^{v_2}dv_0 ( v_2 - v_0) \]
No doing the \(dv_0\) integral we find:
\[\Phi (**,|/)=\int_0^1 dv_2 \int_0^{v_2^2}dv_1 \left( \frac{v_2}{2} - \frac{v_1 v_2^2}{2v_2 - v_1}
+ \frac{1}{2} \left( \frac{v_1 v_2}{2v_2 - v_1} \right)^2\right) \]
To evaluate the \(dv_1\) integral takes a bit of effort.
After doing the work we find:
\[\Phi (**,|/)=\int_0^1 dv_2 ( v_2^3 [ 3 - 4 ln(2)]) \]
and so:
\[\Phi (**,|/)= \frac{3}{4} - ln(2) \approx 0.0568528 \]
Now we’ll evaluate \(\Phi (\bigwedge,\bigwedge)\).
In this case \(v_0 < v_1\) and \(v_2 < v_3\).
Suppose it is also true that \(v_1 < v_2\).
In that case we can deduce that \(v_0 < v_3\)
Thus if \(v_1\) and \(v_2\) collide then so too will \(v_0\) and \(v_3\).
And so all 4 will have been annihilated.
On the other hand if \(v_1\) and \(v_2\) don't collide, then we know that the first pair
will collide and so will the second pair.
Either way all 4 bullets will be annihilated.
\[Prob(v_0 < v_1)= \frac{1}{2} \]
and
\[Prob(v_2 < v_3)= \frac{1}{2} \]
So
\[\Phi (\bigwedge,\bigwedge)=\frac{1}{2} \frac{1}{2} = \frac{1}{4}\]
Now we move on to: \(\Phi (|/,\bigwedge)\)
We're dealing with the case when the first pair is not on a collision course, but the second pair are.
For all 4 bullets to be annihilated we requrie bullets 1 and 2 to collide and then bullets 0 and 3 to collide.
We have conditions:
\[v_1 < v_0 < v_3 \]
\[v_1 < v_2 < v_3 \]
However, if we just integrate over those ranges, then we'll have over counted.
Because we will have also included a contribution from the case when bullets 2 and 3 collide before bullets 1 and 2. And when that happens bullets 0 and 1 won't be annihilated.
So we need to subtract a bit which we'll label \(\phi\)
Thus:
\[\Phi (|/,\bigwedge) =\left( \int_0^1 dv_3 \int_0^{v_3}dv_1 \int_{v_1}^{v_3}dv_0 \int_{v_1}^{v_3}dv_2 \right) - \phi \]
doing that quadruple integral we find:
\[\Phi (|/,\bigwedge) =\frac{1}{12} - \phi \]
|
| Showing the over-counting when bullets 0 and 1 are not annihilated.
|
Now we turn to that extra bit ( \(\phi\) ).
We have the same constraints as above:
\[v_1 < v_0 < v_3 \]
\[v_1 < v_2 < v_3 \]
but we have some extra constraints, which we'll now look into.
We work out the time of collision between 1 and 2 to be:
\[T_{12}=\frac{2v_2 - v_1}{v_2 - v_1}\]
In this extra bit, that we've over-counted, bullet 3 will have already overtaken bullet 2 before the collision between 1 and 2. I.e. bullet 3 will have passed the (1,2) collision at time \(T_{12}\):
\[v_2(T_{12} -2) < v_3 ( T_{12} - 3 )\]
That implies:
\[ v_1 v_2 < v_3 ( 2v_1 - v_2) \]
and we must have:
\[2 v_1 > v_2 \]
and
\[v_3 > \frac{v_1 v_2}{2v_1 - v_2}\]
The lower limit of the integral over \(v_3\) will be \(\frac{v_1 v_2}{2v_1 - v_2} \), so we need to ensure that:
\[ \frac{v_1 v_2}{2v_1 - v_2} < 1 \]
and so we require:
\[v_1 > \frac{v_2}{2-v_2} \]
Thus
\[\phi = \int_0^1 dv_2 \int_{\frac{v_2}{2-v_2}}^{v_2}dv_1 \int_{\frac{v_1 v_2}{2v_1 - v_2}}^{1}dv_3 \int_{v_1}^{v_3}dv_0 \]
So:
\[\phi = \int_0^1 dv_2 \int_{\frac{v_2}{2-v_2}}^{v_2}dv_1 \int_{\frac{v_1 v_2}{2v_1 - v_2}}^{1}dv_3 (v_3 - v_1) \]
and hence:
\[\phi = \int_0^1 dv_2 \int_{\frac{v_2}{2-v_2}}^{v_2}dv_1 \left( \frac{1}{2} - v_1
+ \frac{v^2_1 v_2}{2v_1 - v_2}
- \frac{1}{2} \left( \frac{v_1 v_2}{2v_1 - v_2} \right)^2
\right) \]
It does indeed take a bit of work to show that it evaluates to:
\[\phi = \int_0^1 dv_2 \left( \frac{v_2}{2} - \frac{5v_2^2}{8} + \frac{v_2^3}{2}
+ \frac{v_2^3-4v_2}{8(2-v_2)}
+ \frac{2v_2^2-3v_2^3+v_2^4}{4 (2-v_2)^2} \right)\]
(To work out the integral
this link may be helpful. )
We find:
\[\phi= \frac{6}{24} - \frac{5}{24} + \frac{3}{24} - \frac{4}{24} + \frac{17}{24} - ln(2)\]
So we end up with:
\[\phi= \frac{17}{24} - ln(2)\]
and we now have:
\[ \Phi (|/,\bigwedge) = \frac{1}{12} - \left( \frac{17}{24} - ln(2) \right) = ln(2) - \frac{5}{8} \]
We return to the probability that all 4 bullets will be annihilated:
\[A_4= \left[ \Phi (**,|/) \right] + \Phi (\bigwedge,\bigwedge) + \left\{ \Phi (|/,\bigwedge) \right\} \]
We now have evaluated all the terms on the right hand side:
\[A_4= \left[ \frac{3}{4} - ln(2) \right] + \frac{1}{4}
+ \left\{ ln(2) - \frac{5}{8} \right\} \]
And so:
\[A_4 = \frac{3}{8}\]
So we now know that, when 4 bullets are fired,
the probability that all will be annihilated is \(\frac{3}{8}\)
Let's not integrate:
I am aware that for some people, when they are imagining a fun evening, thoughts of doing quadruple integrals by the fireside do not enter their mind. For such individuals, we offer an alternative approach to working out \(A_4\) without doing any integration at all.
We write the probability that all 4 will be annihilated:
\[A_4=\Phi \left( \bigwedge , \bigwedge \right) + \Phi \left( |/ , |/ \right)
+ \Phi \left( |/ , \bigwedge \right) + \Phi \left( \bigwedge, |/ \right) \]
\( \Phi \left( \bigwedge , \bigwedge \right) \) is the contribution from the case when
\( (v_0 < v_1 ) \) and \( (v_2 < v_3 ) \)
We have already worked that out above, without using integration and found it to be:
\[ \Phi \left( \bigwedge , \bigwedge \right) = \frac{1}{4} \]
Now moving on to \( \Phi \left( |/ , |/ \right)\) which is the contribution from the case when
\( (v_1 < v_0 ) \) and \( (v_3 < v_2 ) \)
When that is true, all 4 bullets will be annihilated when we have the additional conditions:
\( (v_0 < v_3 ) \) and \( (v_1 < v_3 ) \)
So we have the conditions:
\[ v_1 < v_0 < v_3 < v_2 \]
There are \(4!=24\) ways in which the 4 \(v_i \)s can be ordered. Each has the same probability \( \frac{1}{24} \).
Only 1 of the 24 permuations obeys the conditions that we have here and so we can deduce that:
\[\Phi \left( |/ , |/ \right) = \frac{1}{24} \]
Now moving on to: \( \Phi \left( |/ , \bigwedge \right) \). Remember, it is the contribution to \(A_4 \) from the case when the first pair not on a collision course, but the second pair are. So we have conditions:
\( (v_1 < v_0 ) \) and \( (v_2 < v_3 ) \)
for all to be annihilated, we have additional constraints:
\( (v_0 < v_3 ) \) and \( (v_1 < v_2 ) \)
and we also require that bullet 2 does not collide with 3 before 1.
After a bit of work, we find that that condition is:
\[ 2 v_1 v_3 < v_2 ( v_1 + v_3) \]
We'll denote the probability to be \(P\left\{.\right\}\)
So we have:
\[ \Phi \left( |/ , \bigwedge \right) = P \left\{ (v_1 < v_0 ) \& (v_2 < v_3 ) \& (v_0 < v_3 ) \& (v_1 < v_2 ) \&
\left[ 2 v_1 v_3 < v_2 ( v_1 + v_3) \right] \right\} \]
We'll return to that in a moment. But first we'll examine \( \Phi \left( \bigwedge, |/ \right) \). Using a similar argument we find that:
\[ \Phi \left( \bigwedge, |/ \right) = P \left\{ (v_0 < v_1 ) \& (v_3 < v_2 ) \& (v_0 < v_3 ) \& (v_1 < v_2 ) \&
\left[ 2 v_0 v_2 > v_1 ( v_0 + v_2) \right] \right\} \]
We now note that the \(v_i\) are independent, identically distributed random variables and so we could permute the indices on the right hand side of the above equations without changing the value. On the right hand side of the equation immediately above change:
\[i_{new} = (i_{old} + 1) mod \ 4\]
And so we have:
\[ \Phi \left( \bigwedge, |/ \right) = P \left\{ (v_1 < v_2 ) \& (v_0 < v_3 ) \& (v_1 < v_0 ) \& (v_2 < v_3 ) \&
\left[ 2 v_1 v_3 > v_2 ( v_1 + v_3) \right] \right\} \]
Now note that the right hand side that equation contains a term:
\[ 2 v_1 v_3 > v_2 ( v_1 + v_3)\]
And the formula above for \( \Phi \left( |/, \bigwedge \right) \) contains the same term with the '>' switched to a '<'.
When we're working out the probabilities we can ignore '=' case, since that is on a set of zero measure.
Now note that generally speaking:
\[P\left\{K \& L \right\} + P\left\{K \& \ not(L) \right\} = P\left\{K \right\}\]
And so we find:
\[\Phi \left( \bigwedge, |/ \right) + \Phi \left( |/, \bigwedge \right)
= P \left\{ (v_1 < v_0 ) \& (v_2 < v_3 ) \& (v_0 < v_3 ) \& (v_1 < v_2 ) \right\}\]
Of the 24 permutations of \(v_i\), we find that just 2 obey those conditions and so
\[\Phi \left( \bigwedge, |/ \right) + \Phi \left( |/, \bigwedge \right) = \frac{2}{24} = \frac{1}{12}\]
Note that we have not worked out what each of the terms on the left hand side is equal to, but we have worked out their sum, which is what we needed.
Now returning to \(A_4\) we find:
\[A_4=\frac{1}{4}+ \frac{1}{24}+ \frac{1}{12} = \frac{3}{8}\]
.jpg)
