gun with unlimited bullets

[BMAD]

There's a gun located on an infinite line. It starts shooting bullets along that line at the rate of one bullet per second. Each bullet has a velocity between 0 and 1 m/s randomly chosen from a uniform distribution. If two bullets collide, they explode and disappear. What is the probability that at least one of the bullets will infinitely fly without colliding with another bullet?

[bonanova]

I believe surviving bullets are a certainty.

Simulations showed when a million or ten million or a hundred million Fired bullets had been created, the overwhelming majority had already died by virtue of collision. The number of remaining Active bullets immediately after n Fired bullets had been created is given empirically by

<Active bullets> = a n^t where a is ~ 4, and t is ~0.235.

Typically,

Fired <Active> Survivors (See text. Numbers were random, few, and not discernibly related to n)

n 4n^.235

10³ 20 4-10

10⁴ 35 4-10

10⁵ 60 4-10

10⁶ 104 4-10

10⁷ 179 4-10

10⁸ 309 4-10

The Active group comprised two parts: [1] the early bullets, which had already sorted themselves by velocity and [2] the recently fired bullets, at the back of the pack, that had mixed velocities and were still colliding. When n was large, the later bullets never got to the front of the pack. The index number of each bullet was noted. For the (typical) 179 Active bullets for n = 10⁷, the leading bullets (group [1] above) came from the first thousand or maybe ten thousand fired. Invariably they came from the first 10% of the bullets fired.

Since the trailing 90% of the Fired bullets won't influence the front of the pack, neither would any later bullets. It seemed instructive therefore to turn off the gun and allow the Active bullets to drift until their velocities were monotonic. Collisions pared down the Active group to another, smaller, even number, usually less than ten, and never zero. I called these the Surviving bullets. So the three classes were Fired, Active and Survivors. To repeat, their sizes might be 10,000,000, 200, and 6.

1. Survivors had a large spread in distance, and a strictly decreasing velocity profile.
2. Active bullets never totally annihilated themselves. There were always Survivors.
3. The leading Active bullet collide never collided. It became the leading Survivor.

Disclaimer: these were all finite cases. They demonstrated miniscule (not strictly zero) probabilities for the leading bullet's death.

But Survivors came in pairs, sorted by velocity.

If there were say 8 survivors in one of these finite cases it would take at least 9 faster ones to attack the group from the rear.

Very unlikely.

Moreover, it would take exactly nine.

Why? Because if there were a 10th, (and why wouldn't there be?) it would become the Survivor.

Thus: After say 100 million firings, any argument for the annihilation of a "Surviving" bullet has a stronger argument that a new Survivor would be created in its place.

[harey]

No.

Behind the first bullet, there always is a combination of bullets which contains one that will reach the first one.

[santhu221633]

No.

Behind the first bullet, there always is a combination of bullets which contains one that will reach the first one.

what you said is wrong. For your understanding, what if first bullet has velocity 1m/s, then it will reach infinity right.

[Pickett]

Since you are firing an infinite number of bullets...the answer is that it is "infinitely improbable"...the ONLY chance you have of a bullet not colliding with another is that it is the FIRST bullet, and that it has a speed of EXACTLY 1 m/s (or, for fun, let's say 0.99999...

repeating). The chances of this are 1/infinity...which is mathematically zero. However, there is theoretically a CHANCE that it could happen, so you can't say it is "impossible"

The chances of ANY number in that distribution are 1/infinity (aka, mathematically zero)...however, whenever you pick a number, you have just made it happen...in statistics, it is completely fair to say something has a 0 probability of happening, and yet not be impossible...

EDIT: Alright, thinking about this more...this gets very interesting...

Suppose I fire a bullet and it has speed X...then the second bullet has X+Y...they will collide, which means that if the THIRD bullet wouldn't hit either of those no matter how fast it is going...and if it has a speed of 1m/s, it would fly infinitely far.

We can still make the argument that the only way a bullet would NEVER get hit is if it is going 1 m/s exactly...but we then have to state that it has to be going exactly 1m/s without any other bullets in front of it. Since we're firing forever, I'm going to go ahead and state that since we're firing an infinite number of bullets, were are Almost Surely going to have this event happen at some point...

Edited March 19, 2014 by Pickett

[Pickett]

• We have a 1/infinity chance of firing a bullet at 1 m/s.
• Even if there are other bullets on the line, if none are going 1m/s, we will EVENTUALLY fire enough bullets to collide with all of them, which leaves us with an empty line again
• That means we have another 1/infinity chance of firing a bullet at 1 m/s...

This process will repeat an infinite number of times...which means our probably of getting a bullet to NEVER collide is (1/infinity) * infinity...which is 1. However, this is why I said "Almost Surely" above...as I'm certainly not going to wait around for it to be proven. This is just like the Infinite Monkey Theorem...

[bonanova]

OP doesn't say the word "inclusive," leaving open the question

of whether a bullet can be fast enough that it cannot be overtaken.

So there are the two possibilities.

1. If the velocity interval is open (0, 1) then there is no highest velocity.
   That means every bullet will be followed by a faster one.
   In this case, the probability is zero.
   A stronger statement can be made: there is no outcome that will
   guaranty any single bullet will escape collision.
   
2. However, if the interval is closed [0, 1] then the first bullet could have velocity of 1.
   That would guaranty no other bullet would collide with it.
   However, the probability of that occurrence is zero.

In either case the probability is zero.

In the "inclusive" case, however, a no-collision possibility exists.

[Rainman]

Let V be the speed of the first bullet. For argument's sake, let V > 0.99 m/s. We call a bullet fast if its speed is greater than V, and slow otherwise. The probability is 1 that there will be infinitely many fast bullets. If left unhindered, every fast bullet would catch up with the first bullet. But there could be an infinite cloud of slow bullets blocking their way. The probability is at most 0.01 that any given bullet is fast.

Consider the following related question: if you flip a biased coin (with 0.99 probability of heads) infinitely many times, what is the probability that tails will be in majority at some point?

I'm not sure of the answer to that question and I'm too rushed to find out, but I think it's no more than 0.02 probability. If we ignored the (very relevant) fact that slow bullets can eliminate each other, the only way for a fast bullet to reach the first bullet would be if fast bullets were in majority at some point. So the probability of the first bullet escaping would be no less than P(V > 0.99)*0.98 = 0.01*0.98 = 0.0098.

[BMAD]

i changed the status of this question as we consider Rainman's argument.

[bonanova]

Let V be the speed of the first bullet. For argument's sake, let V > 0.99 m/s. We call a bullet fast if its speed is greater than V, and slow otherwise. The probability is 1 that there will be infinitely many fast bullets. If left unhindered, every fast bullet would catch up with the first bullet. But there could be an infinite cloud of slow bullets blocking their way. The probability is at most 0.01 that any given bullet is fast.

Consider the following related question: if you flip a biased coin (with 0.99 probability of heads) infinitely many times, what is the probability that tails will be in majority at some point?

I'm not sure of the answer to that question and I'm too rushed to find out, but I think it's no more than 0.02 probability. If we ignored the (very relevant) fact that slow bullets can eliminate each other, the only way for a fast bullet to reach the first bullet would be if fast bullets were in majority at some point. So the probability of the first bullet escaping would be no less than P(V > 0.99)*0.98 = 0.01*0.98 = 0.0098.

Your conjecture of 0.02 probability of reaching parity of heads and tails for a coin with p(H) = .99 is correct.

A biased coin with probability p_min of the less-likely outcome behaves, with probability 2p_min, like an unbiased coin.

I'm not sure which case you're unconvinced of, (0, 1) or [0. 1].

Since the closed case seems clear, here's an expanded description of the open case:

We had a recent problem about cars forming clusters,

owing to the fact that their speeds are not ordered fastest to slowest.

Thus any car followed by a faster car will form a cluster - a local traffic jam.

In this puzzle, clusters annihilate themselves - that is they do not persist.

To say they persist is to provide an argument with a false premise.

More accurately: clusters have a finite lifetime: they do not persist indefinitely.

On the open interval there is no greatest speed.

Thus every bullet is followed by a faster one.

So it can not be the case that a bullet can break free of all the others and continue forever.

To prove this, assume the opposite.

At some time t_a a bullet a will be at the head of the pack, traveling at speed s_a < 1.

We conjecture that bullet a will continue forever.

However, bullets continue to be fired, with uniform distribution of speed.

Thus, within a finite time interval of 1 / (1-t_a) seconds, a bullet b will be fired with s_a < s_b < 1.

Bullet b will, with non-zero probability find its way to bullet a and annihilate it.

(Rainman, I imagine this is the non-convincing statement.)

It's an assertion, so it merits discussion, and that discussion

centers on the (lifetimes of the bullets fired between bullets a

and b) compared to the sum of (time interval between the firing

of those bullets) + (time interval required for b to catch up with a.)

It would be an interesting calculation.

If we postulate that because of "slow-bullet clutter" between bullets a and b this annihilation event is not certain, but only has probability p_ab > 0 of happening, then on average it will take 1/p_ab (a finite number of) faster bullets b for this to happen. But if p_ab > 0 it will happen. And it will happen within a finite time interval. At that finite point in time, (with bullets a and b now gone) there will be a surviving bullet c at the front of the pack that has speed s_c. We may not make an assumption about its speed. In all likelihood s_c < s_a, but not necessarily, and for this argument it does not matter.

We now conjecture that bullet c will continue forever.

Rinse, repeat. We are now back at the starting point, with a possibly slower bullet attempting to escape.

The OP asks if there is at least one bullet that has infinite survival time.

If there is, it has a name. Its name is n, -- it was fired n seconds into the process.

But whatever (finite) value n has, its bullet has a calculable finite lifetime.

Only a bullet with speed = 1 will never be caught.

That could, with probability zero be the first bullet in the [0, 1] case.

On the open interval, every bullet is followed by a faster one.

Every bounded infinite sequence has an infinite convergent monotone sub sequence.

In this case, there is an infinite subset of bullets with monotone increasing speeds whose limit is 1.

(Bolzano-Weierstrass.)

[bonanova]

Revised answer, without need of spoiler:

I now believe (with Rainman,) but cannot prove it, that in general bullets will escape.

1. If first bullet has v=1 (possible but with zero probability) it will escape.
   
2. Since bullets destroy themselves pairwise, If we could show that infinity were "even" then an even number of bullets will escape (including possibly zero.) If we could show that infinity were "odd" then an odd number of bullets will escape (guaranteeing at least one.) But infinity is not a number and does not have parity. There may be some validity to averaging the results to say that (2n-1)/2 bullets are guaranteed to escape, but I think that is specious. It's like saying the alternating series 1 - 1 + 1 - 1 + 1 - 1 + ... converges to 1/2. The partial sums are alternately 1 and 0, and in fact it does not converge at all.
   
3. The question that I do not know how to answer is how efficiently a faster bullet can destroy the leading bullet if there are intervening bullets. It seems too complicated, even, to simulate. If the leading bullet has speed very close to 1, the expected number of bullets before a faster one is fired will be very large. In my previous post I said they would self-annihilate with non-zero probability. But that's not enough. If no bullet is to escape, this must happen with certainty. It is not likely that the intervening bullets will [a] be even in number and destroy each other, which would be necessary for the leading bullet to be caught. This leads me to agree with Rainman.

It seems that with a high degree of likelihood bullets will escape. But it is not a proof.

This is a good puzzle.

[k-man]

Bona,

... that no matter how long an experiment is,

as long as it's finite, there will be surviving bullets with almost a certainty. Does this, however, mean that any single bullet would survive infinitely long in an infinite case? Your own conclusion suggests that the answer is still "no".

But Survivors came in pairs, sorted by velocity.

If there were say 8 survivors in one of these finite cases it would take at least 9 faster ones to attack the group from the rear.

Very unlikely.

It's very unlikely to happen in a finite case, but is almost certain in an infinite case. It won't be exactly 8 - there will be more and there will be new "survivors" that will live maybe even longer that those 8, but they will not survive forever.

Moreover, it would take exactly nine.

Why? Because if there were a 10th, (and why wouldn't there be?) it would become the Survivor.

I think you meant exactly 8 and the 9th will be the new survivor. Yes, I agree with that and that's what will eventually happen, but the new survivor(s) will also not survive forever.

Thus: After say 100 million firings, any argument for the annihilation of a "Surviving" bullet has a stronger argument that a new Survivor would be created in its place.

My sentiments exactly.

[bonanova]

My opinion is that the process is unbounded, and that bullets escape to infinity.

Simulations influenced its formation. And while infinite simulations don't exist,

and I don't know of a rigorous proof that the answer to the OP is Yes, those

facts do not mean that the answer is No.

Here are the results of three simulations, taken from those described in my previous post, for n = 10⁶ 10⁷ and 10⁸:

Fired: n.

Active: Bullets that had not collided at the conclusion of firing

Surviving: Bullets that after further time elapsed had not and will never collide with each other.

Distance: The position of the leading Survivor after the last collision.

It's not its ultimate distance, just where it was when there was nothing left to simulate.

It is a (very conservative) lower bound for the distance the leading survivor will travel.

Index and speed: describing the surviving bullets; the leading bullet is at the top of the list.

Fired bullets: n=10⁶
Active bullets = 112.
Surviving bullets = 10
Distance: 7.66xn units

Index Speed
671 0.83396
75886 0.78665
76015 0.78494
995610 0.70276
996551 0.66797
999588 0.65309
999949 0.64195
999976 0.54671
999995 0.37676
1000000 0.07547

Fired bullets: n=10⁷
Active bullets = 162
Surviving bullets = 6
Distance: 13.84xn units

Index Speed
7 0.97582
150228 0.80477
150301 0.80471
9676586 0.75852
9893465 0.70747
9999964 0.51058

Fired bullets: n=10⁸
Active bullets = 282
Surviving bullets = 8
Distance: 32.47xn units

Index Speed
51327 0.7654
51646 0.76038
77844477 0.75960
78194004 0.75934
99601167 0.75455
99839044 0.75424
99994569 0.70475
100000000 0.34023

Two observations led me to my opinion.

1. Bullet firings were simulated for orders of magnitude beyond the creation of the leading surviving bullet.
   Consider the event E₁ that the leading bullet collides.
   The simulations show that,
   In finite time:
   -- The probability p(E₁) is large at first. The first bullet fired rarely (almost never) survives.
   -- The probability p(E₁) decreases strongly (exponentially?) with n. After n ~ 10000 the leading bullet rarely changes.
   -- The probability p(E₁) = 0 condition is approached but not reached.
   -- The identity of the leading bullet may change any number of times.
   Nevertheless, having said that, for finite times,
   
   If Lim _n->inf p(E₁) = 0, then the leading bullet is ultimately immortal.
   
2. Suppose the answer is No. No bullet escapes to infinity.
   The down-field range of the leading bullet is either bounded or infinite.
   The conjecture says that it is bounded.
   That is, there is a finite distance X beyond which no bullet will travel.
   Let's divide X by n and call the quotient k, a finite number.
   The distance of the leading bullet then is always less than kn.
   As n increases, k must therefore decrease as 1/n.
   Simulations show the opposite: k is seen to increase with n.
   Nothing in the statement of the problem provides for a mathematical "brick wall" for the bullets.

There are as yet no proofs.

An infinite supply of bullets that have nothing other than other bullets to impede them seems likely on the face of it to be an unbounded process.

Nothing, in a large number of finite simulations, suggests otherwise: for larger values of n, bullets have increasing lower bounds for their distance.

The lack of proof for boundedness seems more compelling to say Yes than a lack of proof for unboundedness compels an answer of No.

With no attempt to garner anyone's agreement, that is my opinion.

In infinite time, will there be bullets at infinity? Yes. (Give me a value of X and, for finite n, I will simulate a bullet that travels farther.)

Can I tell you which bullets they are? No.