Random bullets

[bonanova]

Here is a simple puzzle using bullets fired at random speeds along a straight line.

1. Every second, a gun shoots a bullet along a straight line.
2. Each bullet has a random speed between 0 and 1.
3. Bullets do not slow down; but if two bullets collide, both of them are annihilated.
4. The gun stops shooting after 10 bullets have been fired.

What is the probability that eventually all the bullets will be annihilated?

Edit:

BMAD previously asked if the bullets never stop firing, whether (at least) one bullet survive forever.
It inspired a lot of debate, I think without resolution.
This puzzle I think has a provable answer.

For starters, solve the problem using 4 bullets.

Edited October 28, 2015 by bonanova
Give credit to BMAD's earlier puzzle

[CaptainEd]

I agree with bubbled about Jasen's statement:

:

Jasen, I disagree with your statement that v3>v2>v1 implies that v2 catches v1 before v3 catches v2.
Sometimes it does, but sometimes it does not.

Here are two cases:
v3, v2, v1 are .8, .5, .2
at time t0, we shoot v1
at time t0+1, v1 is .2 m away and we shoot v2
at time t0+1.667, v1 is .2(1.667) m away, and v2 is .5(.667) m away
v1 is .3333 m away, v2 is .333 m away. In other words, 2 catches 1 before we even shoot v3

v3, v2, v1 are .6, .11, .1
at time t0, we shoot v1
at time t0+1, v1 is .1 m away and we shoot v2
at time t0+2, v1 is .2 m away, v2 is .11 m away, and we shoot v3
at time t0+2.22449, v1 is 2.22449 m away, v2 is .11*1.22449 away, v3 is .6*.22449 away
v2 and v3 are both 1.346894 m away, so 3 catches 2 before 2 catches 1

So we can't assume that v3>v2>v2 implies that v2 catches v1 and v3 goes free.

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

So I calculate all the collision timestamps first, THEN I have to cancel out bullet pairs that self-annihilate. 
look at the cases above:
( 1 ) v3, v2, v1 are .8, .5, .2
t10 = 1.66667
t21 = 3.66667
In this case, t10 collision happens before t21, so 0 and 1 are gone before 2 can catch 1.

( 2 ) v3, v2, v1 are .6, .11, .1
t10 = 11
t21 = 2.22449
In this case, the t21 collision happens before t10, so 2 and 1 are gone before 1 can catch 0.

[bonanova]

There is a conjecture for the probability p₀(n) where n=2m for all n bullets to be annihilated. I do not have a proof. Now that there are two programs that are giving the answers for n=4 and n=10 that agree with p₀(4) and with p₀(10) obtained from the conjectured formula, I think I will give the formula.  It can be tested against simulations for other values of n, and its simple form may suggest a line of attack to derive it analytically.

p₀(4) = (1/2)(3/4) = 1*3 / 2*4 = 3/8 = 0.375

p₀(10) = (1/2)(3/4)(5/6)(7/8)(9/10) = 1*3*5*7*9 / 2*4*6*8*10 = 945/3840 = 0.24609375

p₀(n) = (1/2)(3/4) ... (n-1)/n.

This expression converges very slowly to 0 as n -> infinity, suggesting the answer to BMAD's original question of whether a bullet escapes to infinity (when the gun never stops firing) is that it does.

 

[bubbled]

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

When in doubt, for correctness sake, I try to simulate what actually happens. However, I'm not opposed to using a good insight to make things significantly easier.

I'd be concerned about an edge case where the fact that a bullet didn't exist yet during a collision we might get an incorrect result, but I've thought about extreme edge cases and think your approach works.

[CaptainEd]

Rank order of velocities does not always determine outcome, which is why I can't compute the probabilities in a closed form

Consider the 24 possible rank orderings of velocities, and their results. As we know, any ordering that begins with v0 as highest or v3 as lowest is a failure (the bullets diverge). 
Of the 24 cases, These 10 diverge, accounting for 10/24 of the probability (not zilch).
Here are the remaining patterns.A few of them have more than one possible outcome.
These are ordered from high velocity to low velocities. The number is the index of the bullet.
So, 3021 means v3>v0>v2>v1

1032: 10,32; That is, b1 catches b0, b3 catches b2. Notice, b2 couldn't have caught b1
1302: 10,32;
1320: 10,32;
2301: 21,30
3102: 10,32;
3120: 10,32;
3210: 32,10; 21,30; That is, if b3 catches b2, b1 catches b0. But if b2 catches b1 first, b3 catches b0. Zilch either way
These 7 cases account for 7/24 of the probability of zilch

1230: 10&23 diverge; That is, b1 catches b0, but b2 and b3 diverge, as b3 can never catch b2
3012: 32&01 diverge
2031: 21&03 diverge
These 3 cases account for 3/24 of the probability (not zilch)

2130: 21,30; 10&23 diverge
2310: 21,30; 10&23 diverge
3021: 21,30; 32&01 diverge
3201: 21,30; 32&01 diverge
These 4 cases account for somewhat less than 4/24 of probability of zilch, because each can go either way

Case 2130 has one of two outcomes, zilch or diverge. If T21 < T10, then 2 catches 1 before 1 can catch 0, leaving 3 to catch 0. But if T21 > T10, then 1 catches 0 before 2 can catch 1. But this leaves 3 and 2, and v3 < v2, so 3 can never catch 2.

These are the four patterns that are not fully determined by the rank ordering of their velocities. For these, the collision times have to be calculated from the actual velocities. The formulas are clear, but I sure don't know how to make probability estimates from them.

Using these time formulas, wherever the denominators are stricly positive.
T10 = v1 / ( v1 - v0 )
T21 = (2*v2 - v1) / (v2 - v1)
T32 = (3*v3 - 2*v2) / (v3 - v2)
T30 = 3 * v3 / (v3 - v0)

2130 gives one of two results:
zilch: T21 < T10 
diverge: T21 > T10
Translating the times into their formulas:
zilch: 
(2*v2 - v1) / (v2 - v1) < v1 / ( v1 - v0 )
solving for v1:
v1 < 2*v2*v0/(v2+v0)
for divergence, the inequality goes the other way

The same comparisons apply to 2310

For 3021, zilch requires T21 < T32

(2*v2 - v1) / (v2 - v1) < (3*v3 - 2*v2) / (v3 - v2)
solving for v2:
v2 < 2*v3*v1/(v3+v1)

for divergence, the inequality goes the other way
The same comparisons apply to 3201

until I can see how to calculate probabilities from these constraints, I can see that 7/24 < p(zilch-4) < 11/24, but I can't prove that it is exactly 9/24, as Bonanova claimed. 

[bubbled]

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

OK, I'm trying to wrap my head around you statement of calculating collision times, without simulating the the actual firing of the bullets. How would you calculate the result of this 4-bullet sequence. b_0 = v 0.9;  b_1 = v 0.1;  b_2 = v 0.2;  b_3 = v 0.99. Unless you account for the firing of the bullets and the timing thereof, it might appear that b_3 annihilates b_2 and b_0 and b_1 survive. But taking into account the firing phase, b_2 annihilates b_1, and later b_3 annihilates b_0. 

[bubbled]

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

 

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

OK, I'm trying to wrap my head around you statement of calculating collision times, without simulating the the actual firing of the bullets. How would you calculate the result of this 4-bullet sequence. b_0 = v 0.9;  b_1 = v 0.1;  b_2 = v 0.2;  b_3 = v 0.99. Unless you account for the firing of the bullets and the timing thereof, it might appear that b_3 annihilates b_2 and b_0 and b_1 survive. But taking into account the firing phase, b_2 annihilates b_1, and later b_3 annihilates b_0. 

I agree with bubbled about Jasen's statement:

Hidden Content

Bubbled, I agree that you have to recognize that bullets disappear, but I disagree that you have to simulate each second; merely calculate collision timestamps

Hidden Content

OK, I think I figured out what you meant.

1. I create n bullets all at once.

2. I store them in a list of the form [(n-1, V_n-1), (n-2, V_n-2),...,(0, V_0)]

3. For each pair in order starting from the n-1 bullet, I calculate time of collision. Example for n-1 bullet and n-2 bullet: t = (((n -1) - (n -2)) * V_n-2) / (V_n-1 - V_n-2). The two velocities can't be equal (division by zero) which is very unlikely. In the example, the ((n-1) - (n-2)) term is obviously 1, but in later iterations it might be higher.

4. If t < 0 ignore.

5. If t > 0, then actual collision time is t + n-1.

6. Find min of all actual collision times and remove those two bullets. Then repeat the process with remaining bullets until all bullets gone or there are no collisions left.

I'd be afraid to try to optimize further. CaptainEd, do you have a way of removing all bullets will eventually collide in one pass?

[bubbled]

There is a conjecture for the probability p₀(n) where n=2m for all n bullets to be annihilated. I do not have a proof. Now that there are two programs that are giving the answers for n=4 and n=10 that agree with p₀(4) and with p₀(10) obtained from the conjectured formula, I think I will give the formula.  It can be tested against simulations for other values of n, and its simple form may suggest a line of attack to derive it analytically.

Hidden Content

 

bonanova, it certainly looks like your formula is right. I wrote some new quicker code using suggestions from CaptainEd. I then simulated 100,000 trials for each even number from 4-100 bullets. I then compare the simulation to the result predicted by your formula. The results track the formula very well:

 

Results for  4  bullets
Total annihilation in simulation  0.3727
Predicted annihilation rate  0.375
Results for  6  bullets
Total annihilation in simulation  0.31259
Predicted annihilation rate  0.3125
Results for  8  bullets
Total annihilation in simulation  0.27502
Predicted annihilation rate  0.2734375
Results for  10  bullets
Total annihilation in simulation  0.24536
Predicted annihilation rate  0.24609375
Results for  12  bullets
Total annihilation in simulation  0.22711
Predicted annihilation rate  0.2255859375
Results for  14  bullets
Total annihilation in simulation  0.20922
Predicted annihilation rate  0.20947265625
Results for  16  bullets
Total annihilation in simulation  0.19769
Predicted annihilation rate  0.196380615234
Results for  18  bullets
Total annihilation in simulation  0.18393
Predicted annihilation rate  0.185470581055
Results for  20  bullets
Total annihilation in simulation  0.17622
Predicted annihilation rate  0.176197052002
Results for  22  bullets
Total annihilation in simulation  0.16714
Predicted annihilation rate  0.168188095093
Results for  24  bullets
Total annihilation in simulation  0.16207
Predicted annihilation rate  0.161180257797
Results for  26  bullets
Total annihilation in simulation  0.15443
Predicted annihilation rate  0.154981017113
Results for  28  bullets
Total annihilation in simulation  0.15071
Predicted annihilation rate  0.149445980787
Results for  30  bullets
Total annihilation in simulation  0.1459
Predicted annihilation rate  0.144464448094
Results for  32  bullets
Total annihilation in simulation  0.13952
Predicted annihilation rate  0.139949934091
Results for  34  bullets
Total annihilation in simulation  0.13503
Predicted annihilation rate  0.135833759559
Results for  36  bullets
Total annihilation in simulation  0.13288
Predicted annihilation rate  0.132060599572
Results for  38  bullets
Total annihilation in simulation  0.12941
Predicted annihilation rate  0.128585320635
Results for  40  bullets
Total annihilation in simulation  0.12712
Predicted annihilation rate  0.12537068762
Results for  42  bullets
Total annihilation in simulation  0.12247
Predicted annihilation rate  0.122385671248
Results for  44  bullets
Total annihilation in simulation  0.12085
Predicted annihilation rate  0.119604178719
Results for  46  bullets
Total annihilation in simulation  0.11745
Predicted annihilation rate  0.117004087878
Results for  48  bullets
Total annihilation in simulation  0.11474
Predicted annihilation rate  0.114566502713
Results for  50  bullets
Total annihilation in simulation  0.11162
Predicted annihilation rate  0.112275172659
Results for  52  bullets
Total annihilation in simulation  0.10913
Predicted annihilation rate  0.110116034723
Results for  54  bullets
Total annihilation in simulation  0.10976
Predicted annihilation rate  0.108076848895
Results for  56  bullets
Total annihilation in simulation  0.10705
Predicted annihilation rate  0.106146905165
Results for  58  bullets
Total annihilation in simulation  0.10369
Predicted annihilation rate  0.10431678611
Results for  60  bullets
Total annihilation in simulation  0.10212
Predicted annihilation rate  0.102578173009
Results for  62  bullets
Total annihilation in simulation  0.10062
Predicted annihilation rate  0.100923686347
Results for  64  bullets
Total annihilation in simulation  0.09913
Predicted annihilation rate  0.099346753748
Results for  66  bullets
Total annihilation in simulation  0.098
Predicted annihilation rate  0.0978414999033
Results for  68  bullets
Total annihilation in simulation  0.09683
Predicted annihilation rate  0.0964026543165
Results for  70  bullets
Total annihilation in simulation  0.09548
Predicted annihilation rate  0.0950254735405
Results for  72  bullets
Total annihilation in simulation  0.0936
Predicted annihilation rate  0.0937056752969
Results for  74  bullets
Total annihilation in simulation  0.09156
Predicted annihilation rate  0.0924393823875
Results for  76  bullets
Total annihilation in simulation  0.0905
Predicted annihilation rate  0.0912230747245
Results for  78  bullets
Total annihilation in simulation  0.09127
Predicted annihilation rate  0.0900535481255
Results for  80  bullets
Total annihilation in simulation  0.08921
Predicted annihilation rate  0.0889278787739
Results for  82  bullets
Total annihilation in simulation  0.08814
Predicted annihilation rate  0.0878433924474
Results for  84  bullets
Total annihilation in simulation  0.08683
Predicted annihilation rate  0.0867976377754
Results for  86  bullets
Total annihilation in simulation  0.08456
Predicted annihilation rate  0.0857883629175
Results for  88  bullets
Total annihilation in simulation  0.08574
Predicted annihilation rate  0.0848134951571
Results for  90  bullets
Total annihilation in simulation  0.084
Predicted annihilation rate  0.0838711229887
Results for  92  bullets
Total annihilation in simulation  0.0821
Predicted annihilation rate  0.0829594803475
Results for  94  bullets
Total annihilation in simulation  0.0834
Predicted annihilation rate  0.0820769326843
Results for  96  bullets
Total annihilation in simulation  0.08145
Predicted annihilation rate  0.0812219646355
Results for  98  bullets
Total annihilation in simulation  0.08119
Predicted annihilation rate  0.080393169078
Results for  100  bullets
Total annihilation in simulation  0.07821
Predicted annihilation rate  0.0795892373872

[CaptainEd]

Bubbled, no I don't. You've done what I was suggesting. And the results match Bonanova's formula! Amazing! I sure wish I understood what must be a VERY SIMPLE model of this that allows such a simple formula. i'm not seeing it, given that rank ordering of velocities doesn't even fully determine (zilch vs. escape). This is an exciting puzzle. Thanks for writing this program.

[bonanova]

I disclaim authorship, since BMAD posed the "infinite bullet" version here last year, and I read the finite bullet version elsewhere, along with the conjectured solution. I share Captain Ed's amazement at it.

Here is my contribution. Change random speeds into expected speeds. That eliminates need for simulation. There is a neat result that says for n random speed [0, 1] bullets the expected speeds are i/(n+1). The order they occur defines all the representative cases. And then you're done. (In this approach you know values in addition to ordering.) Although for large n you're back to millions of cases. For small n, though, maybe that formula can be derived. I haven't succeeded yet. 

Clarifying:

The expected speed of  the fastest of n bullets is n/(n+1)

The expected speed of the slowest of n bullets is 1/(n+1)

The expected speed of the ith-fastest bullet is i/(n+1)

[CaptainEd]

I'm still slow. How do those numbers help us know the annihilation order? Suppose there are 4 bullets, with velocities 

2/5, 4/5, 3/5, 1/5

Don't I still need to compute collision times to discover whether it's zilch or escape? I gather from your note that these numbers are sufficient to recognize the pattern.

[harey]

Don't I still need to compute collision times to discover whether it's zilch or escape?

Not necessarily.

v3>v2>v1 and diff_1<>diff_2 assumed

diff_1=v2-v1
diff_2=v3-v2
if(diff_2>diff_1) then [3 reaches 2] else [2 reaches 1]

I just cannot figure out p(diff_2>diff_1).

[bonanova]

I'm still slow. How do those numbers help us know the annihilation order? Suppose there are 4 bullets, with velocities 

2/5, 4/5, 3/5, 1/5

Don't I still need to compute collision times to discover whether it's zilch or escape? I gather from your note that these numbers are sufficient to recognize the pattern.

I'm not sure which was fired first but either way you can see that two bullets survive.

.4 .8 .6 .2

Assuming .2 was fired first - that they will travel to the right..
.6 will catch .2 (before .8 catches .6, owing to the greater speed difference between .6 and .2 ) and they annihilate.
That leaves .4 and .8 to survive.

Assuming .4 was fired first - that they will travel to the left
.8 catches .4 and they annihilate.
That leaves .6 and .2 to survive.

Assigning expected speeds allows you to calculate collision times, and thus annihilation condition, once for each speed permutation, instead of a million times using random values. It may, but I have been unsuccessful, lead to a derivation of the formula (at least for small n.)

Maybe it's still not clear. You just enumerate and analyze the speed permutations once, and you're done.

[bonanova]

I want to solidify the idea of using expected speeds to establish the accuracy of the (1/2)(3/4) ... formula

[1] It gives an exact result. As does the formula. So if there's any difference, no matter how small, it's wrong. It must agree exactly with the formula in order to be correct. That criterion is not available to us when we compare the formula to the result of a finite number of random cases.

[2] It gives the correct result for the four-bullet case, as shown here:

Label the bullets 1, 2, 3, 4 where 1 is the fastest, 2 is the next-fastest and 4 is the slowest. Imagine the bullets moving from left to right and the right-most bullet being fired first. There are 24 cases. A=annihilation; E=escape; x=collision:

1 2 3 4 -> [1x2] [3x4] (A) or [2x3, 1x4] (A) -> A is certain
1 2 4 3 -> [1x2]  (3, 4 E) or [2x4, 1x3] (A) -> A more likely because 2x4 is more likely than 1x2
1 3 2 4 -> [1x3] [2x4] (A) Certain
1 3 4 2 -> [1x3]  (2, 4 E) or [3x4, 1x2] (A) -> E more likely because 1x3 is more likely than 3x4
1 4 2 3 -> [1x4] [2x3] (A) Certain
1 4 3 2 -> [1x4]  (2, 3 E) Certain

2 1 3 4 -> [1x3] [2x4] (A) or [3x4] (1, 2 E) -> A more likely because 1x3 is more likely than 3x4
2 1 4 3 -> [1x4] [2x3] (A) Certain
2 3 1 4 -> [1x4] [2x3] (A) Certain
2 3 4 1 -> [2x3]  (1, 4 E) or [3x4] (1, 2 E) -> E Certain
2 4 1 3 -> [2x4] [1x3] (A) Certain
1 4 3 1 -> [1x4]  (1, 3 E) Certain

3 1 2 4 -> [1x2] [3x4] (A) or [2x4] (1, 3 E) -> E more likely because 2x4 is more likely than 1x2
3 1 4 2 -> [1x4]  (2, 3 E) Certain
3 2 1 4 -> [1x4]  (2, 3 E) Certain
3 2 4 1 -> [2x4]  (1, 3 E) Certain
3 4 1 2 -> [3x4] [1x2] (A) Certain
3 4 2 1 -> [3x4]  (1, 2 E) Certain

4 1 2 3 -> [1x2]  (3, 4 E) or [2x3] (1, 4 E) -> E Certain
4 1 3 2 -> [1x3]  (2, 4 E) Certain
4 2 1 3 -> [1x3]  (2, 4 E) Certain
4 2 3 1 -> [2x3]  (1, 4 E) Certain
4 3 1 2 -> [1x2]  (3, 4 E) Certain
4 3 2 1 ->  (1, 2, 3, 4 E) Certain

Add up the certain cases:

(A) 7
(E) 13

Now examine the "more-likely" cases:

We say that for two collisions, where one is between bullets whose speed ranks differ by 2 and the other is between bullets with adjacent speed ranks, the former is more likely to happen first. Specifically, we expect 1x3 to precede 3x4 and 1x2 to follow 2x4. By symmetry those expectations are the same. When bullet speeds are random, it's possible that 3x4 precedes 1x3 and that 1x2 precedes 2x4. We could generate a million sets of 4 numbers and determine that probability. It would depend on the variances of the expected speeds.

These preferences become certainties if we assign to the bullets their expected speeds of i/5. Doing so permits us simply to add up the A and E cases and determine p(A) = A/(A+E). But we need to provide some justification. So far I've only suggested that "using expected values should give expected results." That's intuitive, but not rigorous. I would like to provide a better footing for it.

Here is the case to justify assigning certainty (using expected speeds) instead of greater likelihood in those cases.

For the random-speed case, let's call p21 the probability that 1x3 will precede 3x4. This is the probability that the difference in speeds of the fastest and third-fastest bullets is greater than the speed difference of the third-fastest and the slowest. By symmetry p21 is also the probability that 1x2 will follow 2x4.

We evaluate the four "more-likely" cases:

1 2 4 3 -> [1x2]  (3, 4 E) or [2x4, 1x3] (A) -> p(A) = p21; p(E) = 1-p21
2 1 3 4 -> [1x3] [2x4] (A) or [3x4] (1, 2 E) -> p(A) = p21; p(E) = 1-p21

3 1 2 4 -> [1x2] [3x4] (A) or [2x4] (1, 3 E) -> p(E) = p21; p(A) = 1-p21
1 3 4 2 -> [1x3]  (2, 4 E) or [3x4, 1x2] (A) -> p(E) = p21; p(A) = 1-p21

Combining the four cases gives an expectation of 2 for each outcome: A and E.

Now let's assign expected speeds so that p21 becomes 1 (certainty.) Doing this, also, gives 2 for A and E.

The reason for the agreement is clear. The fraction of A cases that are excluded by making E certain, instead of more likely, exactly equals the fraction of E cases excluded by making A certain, instead of more likely. Thus the results of using probabilities in the random-speed case and (artificially ascribed) certainties in the expected-speed case agree. With both approaches, the four "more likely" cases resolve to

(A) 2
(E) 2

Adding these counts to those for the certain cases yields

(A) 9
(E) 15

And we note that p(A) = 9/(9+15) = (1/2)(3/4).

Note also that this result came from analyzing only 24 (equally likely) cases, and it is exact.

[3] I think the six-bullet case could also be done by hand

[4] I would guess the ten-bullet case could be done by computer.

[jasen]

I want to solidify the idea of using expected speeds to establish the accuracy of the (1/2)(3/4) ... formula

[1] It gives an exact result. As does the formula. So if there's any difference, no matter how small, it's wrong. It must agree exactly with the formula in order to be correct. That criterion is not available to us when we compare the formula to the result of a finite number of random cases.

[2] It gives the correct result for the four-bullet case, as shown here:

Hidden Content

Very clear explaination Bonanova. and the formula is a beautiful math equation.

You said it is a conjecture, I wonder why nobody has proved it mathematically.

 

[bonanova]

@jasen, You, I and CaptainEd and probably others all wonder that. We all think, it seems, that adding two bullets should modify the analysis incrementally rather than requiring us to start from scratch, because we see that p(A) is found by modifying (by a multiplicative factor) the previous result:

p_n(A) = p_n-2(A) (n-1)/n

But even the first step is hard to see. From the trivial p₂(A) = 1/2 to p₄(A) = 3/8 we need to discern a 3/4 factor. But where is it? It would be so cool if the n=4 cases could be grouped creatively to see this. If that grouping could then be made to be algorithmic, the above recursion might be derived, proving the general formula by induction.

Edited September 7, 2015 by bonanova
Adding the final two sentences

[CaptainEd]

Bonanova, thanks for the clarification for how to use the explicit bin-centered velocities. But even more, I'm most excited by the observations that (a) only 4 of the 24 cases have mixed results ( either A or E ), and the notion of complementary cases (3124, 1243) and (2134, 1342). I'm less convinced of the assignment of I/(n+1) for velocities (I don't have clear enough vision) But it seems to me that the notion of complementary cases renders those assignments unnecessary. As you showed, 20 of the cases give unequivocal results without using explicit velocities, and the other four can be easily proven to be exact complements, so that those four add up to exactly two cases, also without explicit velocities. 
From this, I think we should be able to automatically analyze most of the 6! Cases, and list the remainder. Perhaps it will be obvious that we can automatically find complementary pairs again. 
As you said, the rationalization for the next coefficient is still missing... Oh well!

[bonanova]

I had a thought.

Suppose we treat the ensemble of n=2m bullets as nested clusters. So, for n=2 the bullets are aa. There are two cases: which of the two is faster. Annihilation in one case, Escape in the other. Now can we treat the n=4 case as the two "a" bullets nested within two "b" bullets like baab, and think along the lines that if aa annihilate, then the result depends on which of the two "b" bullets is faster? There's more to it than that, of course, (if aa don't annihilate then you have two ab pairs to consider) but I'm wondering if doing the analysis in that way will permit a way of seeing that the annihilation probability decreases by the factor (n-1)/n each time the previous case is nested between two additional bullets, one in front and one in back.

Anybody see how that might work?

[CaptainEd]

A related thought (perhaps the same thought :-) ). However, I don't think my thought panned out...

There are two A patterns for 4 bullets, which I'll represent with open and closed parens:

• ( ) ( ) 
• ( ( ) ) 

where matching parens represent any two bullet numbers where the left paren represents the lower of the two and the matching right paren represents the higher of the two (using your notation of speed rank in right-to-left firing order). We've already recognized that some velocity assignments can make the first one into an E condition, while others make it A. We've recognized that for each such Mixed assignment, there is another with the opposite result.

But the difficulty that I couldn't get over is that no matter where I add the new bullets, I have to reckon with two unwieldy changes. Adding one or two bullets might change

• an A case into an E case
• an E case into an A case
• or no change

I wasn't wise enough to try the easiest case, as you suggested: the only A pattern for 2 bullets is

• ( ) 

The only permutation of speed ranks that matches is (1  2), and there are no mixed permutations (ie, ones where the A-E outcome depends on a race between consuming and being consumed.)

Now, where/how shall we add the next two bullets? We can follow your suggestion and place them before and after the base pattern, corresponding to first and last bullets in firing order. (Not sure how to avoid undercounting, but maybe it will become clear...)

• .5 1 2 .8 -> 1, 3, 4, 2 ( Mixed: A ( 3x4,1x2 ) or E ( 1x3 ))
• .5, 1, 2, 2.5 -> 1, 2, 3, 4 ( A )
• .5, 1, 2, 1.5 -> 1, 2, 4, 3 ( Mixed: A (2x4, 1x3) or E (1x2))
• 1.5, 1, 2, 2.5 -> 2, 1, 3, 4 ( Mixed: A (2x3, 2x4) or E (3x4)
• 1.5, 1, 2, 1.8 -> 2, 1, 4, 3 ( A )
• 2.5, 1, 2, 2.8 -> 3, 1, 2, 4 ( Mixed: A (1x2, 3x4) or E (2x4)

This has identified all the Mixed cases, but not all of the A cases, because there were some E 2-cases that our bracketing converts to A 4-cases.

I think I see how I overlooked them. I bracketed the original case in time (firing one bullet before and one bullet after), but I didn't assign all combinations of speed ranks. I assumed that the one on the left would have a lower speed rank than the one on the right. Let me add more cases:

• .5, 1, 2, .3 -> 2, 3, 4, 1 ( E )
• 1.5, 1, 2, .3 -> 3, 2, 4, 1 ( E )
• 2.5, 1, 2, .3 -> 4, 2, 3, 1 ( E )
• 1.8, 1, 2, 1.5 -> 3, 1, 4, 2 ( E )
• 2.5, 1, 2, 1.5 -> 4, 1, 3, 2 ( E )
• 2.8, 1, 2, 2.5 -> 4, 1, 2, 3 ( E )

Wow, I've only listed half the 4-cases; I don't see how I missed the other half, AND, I'm missing most of the A cases. Durn. I have the feeling that I didn't do your suggestion justice, Bonanova...Still thinking...

[CaptainEd]

Here are the rest of the cases

bracketing the 2,1 cases

.5 2 1 .8 -> 1, 4, 3, 2 ( E )
.5 2 1 .3 -> 2, 4, 3, 1 ( E )
.5 2 1 1.5 -> 1, 4, 2, 3 ( A )
.5 2 1 2.5 -> 1, 3, 2, 4 ( A )
1.5 2 1 .8 -> 3, 4, 2, 1 ( E )
1.5 2 1 1.3 -> 3, 4, 1, 2 ( A )
1.5 2 1 1.8 -> 2, 4, 1, 3 ( A )
1.5 2 1 2.5 -> 2, 3, 1, 4 ( A )
2.5 2 1 .8 -> 4, 3, 2, 1 ( E )
2.5 2 1 1.5 -> 4, 3, 1, 2 ( E )
2.5 2 1 2.3 -> 4, 2, 1, 3 ( E )
2.5 2 1 2.8 -> 3, 2, 1, 4 ( E ) 

So this added 5 more A's. I had 2, so this completes the tally: 7 A's, 4 Mixed, 13 E's.

Good news; we didn't lose generality by placing the bullets in first and last firing order.
Bad news: we had to look at original E-cases ( 2 1 ) in addition to original A-cases ( 1 2 ) in order to capture all the 4-cases.

[CaptainEd]

More of the A cases are ( ) ( ) than are ( ( ) )

bullets yet again

What patterns correspond to pure A?
1,2,3,4 (()) or ()()
2,1,4,3 (())
1,4,2,3 ()()
1,3,2,4 ()()
3,4,1,2 ()()
2,4,1,3 ()()
2,3,1,4 ()()

What patterns correspond to mixed?

1,3,4,2 can be either (()) or ()xx
1,2,4,3 can be either (()) or ()xx
2,1,3,4 can be either (()) or xx()
3,1,2,4 can be either (()) or xx()

what patterns correspond to pure E?
2,3,4,1 ()xx
3,2,4,1 x()x
4,2,3,1 x()x
3,1,4,2 x()x
4,1,3,2 x()x
4,1,2,3 x()x
1,4,3,2 ()xx
2,4,3,1 ()xx
3,4,2,1 ()xx
4,3,2,1 xxxx
4,3,1,2 xx()
4,2,1,3 xx()
3,2,1,4 xx()

[CaptainEd]

(bows long and deeply) that IS a pretty solution!

[bonanova]

I hope I got it:

 

Hidden Content

Well deserved!

This may have become, unintentionally the best "Aha!" puzzle on the site. Once you see it, you wonder why we thought it was difficult. But for me it took some thought to accept it..

The recursive nature of the formula demands that we associate each fraction with two of the bullets. (n-1)/n must somehow deal with the first collision - when there are n bullets. It can't be otherwise. What can be its significance? That's the only question here, and the answer has to be that it's the fraction of the cases where the ensemble of n bullets will have at least one collision. If so, then the m=n-2 remaining bullets gives rise to an (m-1)/m probability that there will be at least one more collision. The probability of n/2 collisions (annihilation) is then the product of n/2 such fractions where the number is reduced by 2 in each case.

The only thing to be clear about is that (n-1)/n is the probability that n bullets will have at least 1 collision. It's clearly the probability the first bullet is not the fastest. But it's also the probability the last bullet is not the slowest, and that's another case where "all hope is lost." Do these cases interact in any way? I recognize that the formula is correct, and the analysis harey has given creates the formula, so his analysis either absolutely correct or fortuitously correct.

It's certainly true for n=2. There, the two cases mentioned above happen concurrently. But for larger n, you can have one but not the other. In the general case (n large) you will have at least one collision if the last bullet is not the slowest OR if the first bullet is not the fastest. This suggests a (first) probability that is larger than (n-1)/n.

After thinking a bit, I conclude that fact does not matter. We can justifiably restrict our attention to the rightmost bullet. (By symmetry and with equal justification we could restrict our attention to the leftmost bullet and consider whether it's not the slowest.) If the leftmost bullet is the slowest then we won't have annihilation. But that fact does not negate the fact that if the rightmost bullet is not the fastest, there will be at least one collision. That fact by itself is sufficient for us to consider the remaining ensemble of (n-2) bullets and repeat the question. If the leftmost bullet IS the slowest of the bunch, that probability is accounted for when we place the final (1/2) probability fraction in the formula.

[BMAD]

it would seem that this logic relies on the idea that each bullet's speed is distinct.  Wouldn't bullets of the same speed add to the sample space, affecting the number of escape situations?

[harey]

The speed is a real number. As there is an infinity or real numbers, p(two bullets have the same speed)=zero, at least for a "small" n. The same way we do not suppose that 3 (or more) bullets can collide.

However, there is something else that gives me headaches.

It works when there are n bullets in line AFTER all n bullets were shot. What if the first two bullets collide and then n-2 bullets are shot? More generally, what if there are collisions before all bullets are shot?

[bonanova]

@harey, I agree that we are analyzing a string of n bullets that still exist after the nth bullet has been shot. I would say let's not worry about that -- I could even change the OP to reflect it. The other case just seems messy and not interesting enough (to me at least) to pursue.

However ...

I have some uncertainty about the derivation after giving this some thought. I'm not sure we are comparing apples to apples. Let me explain.

Suppose the leading bullet has 1/k chance of being the fastest.  Then we will not get complete annihilation. But *still* we could get another collision, between other bullets. So while it may seem true to say the probability of *at least* one future collision is 1-1/k, we are still measuring only a *sufficient* but not a *necessary* one. Meaning that (k-1)/k is a *lower bound* to the probability of future collisions, not that probability itself. Multiplying lower bounds may not be a justifiable path to determining a final annihilation probability.

Think of it this way. For an initial ensemble of n bullets, there are n! permutations of their speeds, only one of which (monotonic speed profile, increasing back to front) does *not* have a collision in its future. So the initial probability for at least one collision is not (n-1)/n, but (n!-1)/(n!). For any appreciable n, say 10 or greater, that probability is *very* close to unity, not the mere 9/10 that obtains from cases where the leading bullet is not the fastest. So the meaning of 9/10 in that context seems unclear.

Certainly (n-1)/n underestimates the true probability at the outset, while near the "finish line" where k=4 and k=2, it must over-estimate it. While the product of (k-1)/k terms gives the correct result (as verified by simulation, and perhaps amazingly), the individual terms don't have a clear meaning; at least they don't have the meaning that the derivation ascribes to them. It may well be the case that as k decreases, 1/k remains the escape probability for the leading bullet; even so, it's clear that most of the (k-1)/k terms underestimate the next-collision probability.

I'm re-opening this thread. Perhaps more discussion will fill in the question marks. I'm open to reconsidering.

I wish someone would simulate n=100 several times and compare the next-collision probabilities for each k against (k-1)/k. That would be definitive; either to verify harey's derivation or perhaps to suggest, by their empirical values, a derivation of a different kind.

Add to that some simulations starting with n=50 and compare next-collision probabilities for k=50 and lower against those having n=100 as a starting point. If harey's analysis is right, they should be the same whether n=100 initially or n=50 initially.

Anyone care to try that?