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

[jasen]

The interesting fact is : Whatever number of bullets fired, the highest probability is 2 bullets left.

initial  2 bullets  1000000 tries
 P of 0 bullets anhilated =  .500683
 P of 2 bullets anhilated =  .499317

initial  4 bullets  1000000 tries
 P of 0 bullets anhilated =  .041601
 P of 2 bullets anhilated =  .582647
 P of 4 bullets anhilated =  .375752

initial  6 bullets  1000000 tries
 P of 0 bullets anhilated =  .001354
 P of 2 bullets anhilated =  .076568
 P of 4 bullets anhilated =  .609111
 P of 6 bullets anhilated =  .312967

initial  8 bullets  1000000 tries
 P of 0 bullets anhilated =  .000029
 P of 2 bullets anhilated =  .00346
 P of 4 bullets anhilated =  .104317
 P of 6 bullets anhilated =  .619309
 P of 8 bullets anhilated =  .272885

initial  10 bullets  1000000 tries
 P of 0 bullets anhilated =  0
 P of 2 bullets anhilated =  .000075
 P of 4 bullets anhilated =  .006025
 P of 6 bullets anhilated =  .127299
 P of 8 bullets anhilated =  .620703
 P of 10 bullets anhilated =  .245898

initial  12 bullets  1000000 tries
 P of 0 bullets anhilated =  0
 P of 2 bullets anhilated =  .000002
 P of 4 bullets anhilated =  .000186
 P of 6 bullets anhilated =  .008569
 P of 8 bullets anhilated =  .147078
 P of 10 bullets anhilated =  .618606
 P of 12 bullets anhilated =  .225559

initial  14 bullets  1000000 tries
 P of 0 bullets anhilated =  0
 P of 2 bullets anhilated =  0
 P of 4 bullets anhilated =  .000002
 P of 6 bullets anhilated =  .000258
 P of 8 bullets anhilated =  .011055
 P of 10 bullets anhilated =  .164173
 P of 12 bullets anhilated =  .614903
 P of 14 bullets anhilated =  .209609

initial  16 bullets  1000000 tries
 P of 0 bullets anhilated =  0
 P of 2 bullets anhilated =  0
 P of 4 bullets anhilated =  0
 P of 6 bullets anhilated =  .000008
 P of 8 bullets anhilated =  .000366
 P of 10 bullets anhilated =  .013871
 P of 12 bullets anhilated =  .178564
 P of 14 bullets anhilated =  .610811
 P of 16 bullets anhilated =  .19638

initial  18 bullets  1000000 tries
 P of 0 bullets anhilated =  0
 P of 2 bullets anhilated =  0
 P of 4 bullets anhilated =  0
 P of 6 bullets anhilated =  0
 P of 8 bullets anhilated =  .000005
 P of 10 bullets anhilated =  .000545
 P of 12 bullets anhilated =  .016474
 P of 14 bullets anhilated =  .191395
 P of 16 bullets anhilated =  .606078
 P of 18 bullets anhilated =  .185503

initial  20 bullets  1000000 tries
 P of 0 bullets anhilated =  0
 P of 2 bullets anhilated =  0
 P of 4 bullets anhilated =  0
 P of 6 bullets anhilated =  0
 P of 8 bullets anhilated =  .000001
 P of 10 bullets anhilated =  .000012
 P of 12 bullets anhilated =  .000665
 P of 14 bullets anhilated =  .018998
 P of 16 bullets anhilated =  .203064
 P of 18 bullets anhilated =  .601149
 P of 20 bullets anhilated =  .176111

 

[harey]

Suppose the leading bullet has 1/k chance of being the fastest.  Then we will not get complete annihilation.
So far, so good.

 

But *still* we could get another collision, between other bullets.
We could and very often we would, but we do not care. We ONLY consider the complementary case where the leading bullet is NOT the fastest. And that happens with the probability (1-1/k).

 

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.

Look at it this way:
- If the LB is the fastest, we quit the game. p=1/k
- Necessary condition to continue the game: LB may not be the fastest. p=1-1/k. There SURE will be a collision. We have k-2 bullets

Example for k=8:

We do not care what happens if LB is the fastest because there will be no annihilation. EXIT

In 7/8 cases, LB is not the fastest, so we are sure there will be a collision. It does not matter whether 3 collides with 4, 6 with 7 or 7 with 8. Just two bullets are gone. For future convinience, we renumber the bullets.

Now, we have k=6

We do not care what happens if LB is the fastest... EXIT

In 5/6 cases, LB is not the fastest, so we are sure there will be a collision. Again, it does not matter who collides with whom. Again, we renumber.

We got here with the p that the LB was not the fastest when we had 8 bullets AND with the p that the LB was not the fastest when we had 6 bullets: 7/8 * 5/6

Now, we have k=4

We do not care what happens if LB is the fastest... EXIT

In 3/4 cases, LB is not the fastest, so we are sure there will be a collision. Again, it does not matter who collides with whom. Again we renumber.

We got here with the p that the LB was not the fastest when we had 8 bullets AND with the p that the LB was not the fastest when we had 6 bullets AND with the p that the LB was not the fastest when we had 4 bullets: 7/8 * 5/6 * 3/4

Now, we have 2 bullets
We do not care what happens if LB is the fastest... EXIT

In 1/2 cases, LB is not the fastest, so we are sure there will be a collision. To get here: 7/8 * 5/6 * 3/4 * 1/2

 

Think of it this way. For an initial ensemble of n bullets, there are n! permutations of their speeds,

Oh, not again!!! It took me a long time to get freed of the relative speeds. The trouble is that it works well for k=2, but it gets very complicated for higher k. Take 4 bullets with v1>v2>v3>v4 when the distances are equal:

9 8 2 1  at first, 8 hits 2
9 8 6 1  at first, 6 hits 1

To know what happens, you have to consider not only the speed hierarchy, but the speed differences. There remain two bullets, it can be managed.

However, imagine 6 bullets. After the first collision, the distances are not equal so the speed differences do not help. Gets really, really complicated.

Edited October 4, 2015 by harey

[k-man]

I've been following this thread without comment as there wasn't anything I could contribute (didn't have the aha! moment like harey did). I'm convinced that harey's approach is correct. Probably the easiest way to see it is to draw the probability tree of complementary events (see below).

The green track leads to the complete annihilation with total probability established earlier, the red track is the "no collision" track with total probability of 1/n! and the yellow tracks are all the partial annihilation tracks.

This tree also explains jasen's finding that the most likely outcome is that 2 bullets remain. Half the leaf nodes of this tree will have that outcome and the total probability will be the sum of those leaf node's probabilities. 

Edited October 5, 2015 by k-man
fixing a typo

[harey]

@k-man great graphics!!! Do you know an easy to learn freeware? It might be very handy to attack the problem of collisions before all bullets have been fired.

[k-man]

I built the probability tree using PowerPoint. It's not freeware, but it's easy to learn and use. If you don't have PowerPoint you can try Google Docs, but I don't know if they have the same widgets that PowerPoint has or not.

[bonanova]

@kman, I have argued this analysis in another venue, and my doubter objects to the proof. He accepts that 1/n is the probability that initially the first bullet is fastest, but not subsequently. He asks for proof that the first collision does not alter the statistical properties of the surviving bullets -- he says that 1/(n-2) cannot simply be assumed for the first remaining bullet to be the fastest of the remaining bullets. I pulled my hair out trying to disabuse him of that doubt.

The best argument I could give is that the first collision is random (in the sense that it is governed by random placement and speed of the original bullets), and that random processes do not introduce bias. He asks for a stronger argument. I don't think there is one. And I don't think there needs to be one. It's self-evident. That is his only objection, btw. And it's the only possible objection, because it's a sufficient condition for the proof, as your diagram eloquently shows. Total annihilation happens according to the product of (k-1)/k terms, with k decreasing from n to 2 in steps of 2.

One aspect of the analysis that led to confusion in our discussion is the meaning of these terms. At each step, (k-1)/k is *not* the probability of a next collision. It is a lower bound. Thus, while the formula seems intuitive, its partial products do not have their intuitive meaning. But that is a red herring. Only the complete expression has been offered as being meaningful.

For example, in the case of n=4, the probability for at least one collision is not 3/4, it's 23/24. Accordingly, the probability for a second collision is not 1/2, it's 9/23. The annihilation probability for n=4 is thus 23/24 x 9/23 = 9/24 = 3/8. These factors have a clear interpretation, whereas 3/4 and 1/2 do not. It is tempting to think of 3/4 and 1/2 as sequential probabilities, but it is incorrect to do so. Except that, *given that k has become 2,* 1/2 is the probability for the last collision. But the priors are modified in that line of thinking. Also, for that last case, 1/n just happens to equal 1/n!.

It would be interesting for someone who has a simulation program running (bubbled seems to have departed the scene) to start say with say n=20 and record the fraction of cases that get to each value of k (18, 16, ... ) remaining bullets, down to k=2. (By "get to" I do not mean "terminate with.") The ratios of those numbers give the probabilities of a next collision. The formula in question gives the correct number for which k gets to 0. But the intermediate results will be seen (I posit) to differ from the partial products of the formula. In only 1/n! of the cases will k not get to 18, for example.

The complete formula applies to total annihilation. I don't see a simple interpretation for its partial products.

[CaptainEd]

Perhaps part of the difficulty of persuading doubters is related to the fact that the proposed argument does not seem to depend on bullets being fired at one second intervals, and in fact doesn't appear to depend on the probability distribution of velocities?

 

[jasen]

Suppose the leading bullet has 1/k chance of being the fastest.  Then we will not get complete annihilation.
So far, so good. ....

 

After rethinking this, I understand the doubter opinion.

We have to avoid using "first bullet fastest"
Although first bullet is not the fastest, it it still possible that the first bullet escape

1 4 2 3  -> in this arrangement  3 (first bullet) is not the fastest, but it escape.

-----

we better explain it in another way.

with n bullets, if the fastest bullet is not the first, there is (n-1)/n cases that we are sure there will be a collision. n-2 bullets will remains.  an so on...

[harey]

Bonanova wrote:
@kman, I have argued this analysis in another venue, and my doubter objects to the proof. He accepts that 1/n is the probability that initially the first bullet is fastest, but not subsequently. He asks for proof that the first collision does not alter the statistical properties of the surviving bullets -- he says that 1/(n-2) cannot simply be assumed for the first remaining bullet to be the fastest of the remaining bullets. I pulled my hair out trying to disabuse him of that doubt.

If I claim that I still have quite correct reactions after drinking a glass of wine, it is on you to prove me that I am wrong.
If I claim that I still have quite correct reactions after drinking two bottles of whisky, it is on me to prove  that I am right.

In this case, it is on him to prove that the statistical properties change.

Anyway, both methods use the same proceeding:
Step 1) build a table of speeds
Step 2) split the table into 2 parts: 'to reject' and 'to reexamine'
Step 3) reexamine the part 'to reexamine'.

Where they differ is the definition of 'to reject'.
One method rejects vn< ... <v3<v2<v1.
One method rejects v1>vi (i=2,3, ... ,n).

Interpretation of partial products: (number of cases we retained/rejected)/(total before retention/rejection). The partial products of the second method describe what happens collision after collision; the first method might be much less clear, depending on proceedings in step 3.

Bonanova wrote:
For example, in the case of n=4, the probability for at least one collision is not 3/4, it's 23/24.
I agree that p(at least one collision) is not 3/4.
I agree that p(at least one collision) is 23/24.

Just I do not consider ALL cases with at least one collision: I deselect cases v1>vi (i=2,3, ... ,n). For n=4, 3/4 of cases will remain. It is NOT the full set of cases with at least one collision.

Edited October 8, 2015 by harey