Colliding Bullets

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

  • 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

Among the N bullets fired at time 0,1,2…N (with N even), let us call Bmax 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.

Attribution
Source : Link , Question Author : Kitegi , Answer Author : Batominovski

Leave a Comment