wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Gun with infinite bullets
        
(Message started by: foo on Nov 2nd, 2013, 2:15pm)
Title: Gun with infinite bullets
Post by foo on Nov 2nd, 2013, 2:15pm
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 (are at the same spot at the same time) they explode and disappear.
What is the probability that at least one of the bullets will infinitely fly without colliding with another bullet?
Title: Re: Gun with infinite bullets
Post by jollytall on Nov 24th, 2013, 10:43am
Since nobody is replying let me try.
My gutfeel tells me, that the original question is something that cannot be answered. The event we want to judge the probability of, is not clear. When do we say that the event (i.e. a bullet flew to infinity) happened? At any time it is only flying with a finite speed and if that speed is not 1 (what has a zero probability), then there might come a bullet somewhere later that can still catch it.
Also on the other side, how can we say that no bullet reaches the infinity if there are infinitely more bullets still coming.
Title: Re: Gun with infinite bullets
Post by towr on Nov 24th, 2013, 11:52am

on 11/24/13 at 10:43:36, jollytall wrote:
At any time it is only flying with a finite speed and if that speed is not 1 (what has a zero probability), then there might come a bullet somewhere later that can still catch it.
However, as time increases the chance that the intercepting bullet is intercepted before it can intercept the leading bullet increases. It becomes increasingly unlikely that the leading bullet will be intercepted (at least within a given amount of time).

For simplicity we could first consider that we wait for a steady state before shooting the next bullet, i.e. we wait till every bullet that can catch up to any other bullet has done so, so at "steady state" from left to right (if we're firing in that direction) every bullet we encounter goes faster than the previous. To intercept the leading (fastest) bullet, we need to fire at least as many bullets as are already on their way. And some of those are likely to intercept each other.
If we fire a new bullet, it can either add one to the line (if it's slower than the slowest), or remove one from the line (if it's faster than the currently slowest). So it's a bit similar to a random walk here, except they're not even odds (if it was, then we'd expect to get to a state of 0 bullets with probability 1).
Title: Re: Gun with infinite bullets
Post by TimMann on Dec 27th, 2013, 2:19pm
FWIW, it seems to me that the probability is zero. At any given point, the probability is 0 that the most distant bullet has velocity 1. Therefore with some probability greater than 0, a later bullet will catch it. Since we are running the process forever, the probability is 1 that eventually another bullet will catch it.

This is mostly a gut feel too, though. Maybe jollytall is right that the problem doesn't have a well-defined answer.

What about trying to define the problem in terms of limits? We could ask: what's the limit (if any) of the probability that a bullet will eventually reach distance n from the origin as n goes to infinity? Hmm, I'm pretty sure that's 1, though, contradicting my previous guess!
Title: Re: Gun with infinite bullets
Post by Grimbal on Jan 1st, 2014, 11:29am
I did the same reasoning.  But I don't think it is that simple.  It is not enough that a later bullet eventually will be faster.  It must be faster and not meet any other bullet in the way, and it must not be caught by another still faster bullet coming from behind.
Title: Re: Gun with infinite bullets
Post by TimMann on Jan 9th, 2014, 12:50pm
I realized that, but ended up getting muddled anyway. It certainly is always possible that the most distant bullet will be caught by a still faster one that manages not to be exploded first by some other bullet. (Well, except for the unique point case where the most distant bullet has velocity exactly 1.) But I carelessly said the probability of a later bullet catching up is nonzero, when actually I don't know what the probability is.
Title: Re: Gun with infinite bullets
Post by riddler358 on Mar 3rd, 2014, 3:13pm
i'd like to share my take on this one

i'm thinking it's 0

reasoning
1) let's say at some point we fired some bullet that is "going to infinity", now forget this bullet, we have at least same probability of firing another one that is at least as fast as the first, and infinite tries
2) no matter how far first bullet is, there is always a chance to generate faster bullet for which difference in speed of this 2nd bullet and the 1st one will be infinitely times greater than difference of speed for any faster bullets to come and 2nd bullet
example
let's say 1st is going to infinity with 0,999
we fire at some point bullet with 0,999999999 speed
that 2nd is chasing 1st with difference of speeds 0,000999999
while any faster bullet to come might chase 2nd with at most 0,000000001
Title: Re: Gun with infinite bullets
Post by rmsgrey on Mar 4th, 2014, 6:26am

on 03/03/14 at 15:13:51, riddler358 wrote:
i'd like to share my take on this one

i'm thinking it's 0

reasoning
1) let's say at some point we fired some bullet that is "going to infinity", now forget this bullet, we have at least same probability of firing another one that is at least as fast as the first, and infinite tries
2) no matter how far first bullet is, there is always a chance to generate faster bullet for which difference in speed of this 2nd bullet and the 1st one will be infinitely times greater than difference of speed for any faster bullets to come and 2nd bullet
example
let's say 1st is going to infinity with 0,999
we fire at some point bullet with 0,999999999 speed
that 2nd is chasing 1st with difference of speeds 0,000999999
while any faster bullet to come might chase 2nd with at most 0,000000001


But unless the faster bullet is the next bullet fired, there's a good chance that it'll hit one of the intervening bullets first...
Title: Re: Gun with infinite bullets
Post by riddler358 on Mar 4th, 2014, 8:08am

on 03/04/14 at 06:26:35, rmsgrey wrote:
But unless the faster bullet is the next bullet fired, there's a good chance that it'll hit one of the intervening bullets first...

but it's the same chance as for the bullet that is "going to infinity"
Title: Re: Gun with infinite bullets
Post by rloginunix on Mar 4th, 2014, 8:23am
What if the very first Adam and Eve bullet is fired at velocity of exactly 1? Since the time interval between the shots is > 0 no other bullet will ever catch up to it. May be the answer then is given the bell curve distribution what is the probability of the very first bullet being fired at velocity 1?
Title: Re: Gun with infinite bullets
Post by towr on Mar 4th, 2014, 8:50am
But that's just 0. The probability of any exact value in a continuous smooth distribution is zero.
Title: Re: Gun with infinite bullets
Post by rmsgrey on Mar 5th, 2014, 3:40am

on 03/04/14 at 08:08:59, riddler358 wrote:
but it's the same chance as for the bullet that is "going to infinity"

If the "going to infinity" bullet catches up with another bullet before the chaser bullet catches up with it, then the chaser is no longer doomed to catch it, so could itself escape to infinity...
Title: Re: Gun with infinite bullets
Post by riddler358 on Mar 5th, 2014, 3:05pm

on 03/05/14 at 03:40:02, rmsgrey wrote:
If the "going to infinity" bullet catches up with another bullet before the chaser bullet catches up with it, then the chaser is no longer doomed to catch it, so could itself escape to infinity...

there is no bullet in front of "going to infinity" bullet, and so called chaser is bullet that is faster than the "going to infinity" one and no bullets are between them, so either chaser catches or gets caught by it's own chaser
Title: Re: Gun with infinite bullets
Post by foo on Mar 8th, 2014, 7:55am
I think I managed to solve the so called "steady state" variant that towr proposed.
However, I did not figure how to make it work for the original riddle.

The proof isn't as elegant or rigorous as you'd hope, but it's the best I could do:

[hideb]

I'll mark a steady state of n bullets with velocities p1,...,pn with <pn, ..., p1>
It helps to imagine the bullets being fired in the left-to-right direction.

The velocities must satisfy pn <= ... <= p1 , otherwise the state is not steady.

Suppose the system is at a state <pn, ..., p1>.
The next bullet fired will either have velocity p <= pn (with probabilty pn) resulting in <p, pn, ..., p1> as the next state,
or p > pn (with probabilty 1-pn) resulting in <pn-1, ..., p1> as the next state

Define f(<pn, ..., p1>, i) as the probability that the bullet at index i ( that has velocity pi ) will survive infinitely given that the system is at the state <pn, ..., p1>.
Denote g(p) as f(<p>, 1). This is just shorter notation for the probability that a lone bullet with velocity p will survive infinitly.


I'll try to prove that for all p in [0,1): g(p) = 0
This means that for any bullet fired (in a clean state) the probabilty that it will survive is 0 (eventually returning to a clean state).
Since unifying a countable amount of events with probabilty 0 results in an event also with probabilty 0, this implies that the probabilty that at least one bullet survives is 0.


Claim 1: If p1 <= p2 then g(p1) <= g(p2)

If a bullet with velocity p1 survives for a certain sequence of velocities then a bullet with velocity p2 will most certainly survive for the same sequence of velocities.


Claim 2: f(<pn, ..., p1>, n) = f(<pn>, 1) = g(pn)

Every time a bullet is fired, it can only affect the leftmost bullet.
Unless the bullet with index n is destroyed there can be no interaction between bullets to its left and to bullets to its right.


Claim 3: f(<p2, p1>, 1) = g(p2) + (1-g(p2))*g(p1)

f(<p2, p1>, 1) = f(<p2, p1>, 2) + (1-f(<p2, p1>, 2))*g(p1)

For a state with two bullets there are two distinct cases in which the first bullet survives:
1. The second bullet survives and thus no bullet can destroy the first bullet so it will survive as well.
2. The second bullet is destroyed at some point, in which case we return to the state <p1> with the probablity g(p1) for survival.

f(<p2, p1>, 2) + (1-f(<p2, p1>, 2))*g(p1) = g(p2) + (1-g(p2))*g(p1)

This is direct usage of Claim 2.


Claim 4: For all p2 <= p1 ,  f(<p2, p1>, 1) <= g(p1)*(2 - g(p1))

f(<p2, p1>, 1) = g(p2) + (1-g(p2))*g(p1) = g(p1) + g(p2) - g(p1)*g(p2)
= g(p1) + g(p2) - g(p1)*g(p2) = g(p1) + (1-g(p1))*g(p2) <= g(p1) + (1-g(p1))*g(p1) = g(p1)*(2 - g(p1))

This is use of Claim 3 with some algebra + Claim 1 for the inequality.


Denote <*, p> as the set of all states <p2, p> where p2 <= p.
Define f(<*, p>, 1) as the probabilty for a bullet with velocity p to survive given that there is a bullet behind it with velocity taken uniformly from [0, p].


Claim 5: f(<*, p>, 1) <= g(p)*(2 - g(p))

The upper bound is true for all p2 <= p so we can derive this bound from the law of total probabilty.


Claim 6: g(p) <= p*g(p)*(2 - g(p))

g(p) = Pr[ The next bullet fired has velocity in [0,p] (next state is in <*,p>) ] * Pr[ The first bullet survives | the state is in <*,p> ] = p * f(<*, p>, 1) <= p*g(p)*(2 - g(p))


Claim 7: g(p) = 0 or g(p) <= 2 - 1/p

If g(p) = 0 then the claim is true. Otherwise we can take Claim 6 and divide by g(p):
1 <= p*(2 - g(p))
1/p <= 2 - g(p)
g(p) <= 2 - 1/p


Claim 8: for all p <= 1/2, g(p) = 0

This is a direct result of Claim 7 and g(p) being in [0,1] (since it is a probabilty).

[/hideb]
Title: Re: Gun with infinite bullets
Post by foo on Mar 8th, 2014, 7:57am
[hideb]

Denote <[a,b], p> as the set of all states <p2, p> where a <= p2 <= b <= p.
Define f(<[a,b], p>, 1) as the probabilty for a bullet with velocity p >= b to survive given that there is a bullet behind it with velocity taken uniformly from [a, b].


Claim 9: for all p > 1/2, f(<[0,1/2], p>, 1) = g(p)

Let p2 <= 1/2 <= p be some velocity for the second bullet.
f(<p2, p>, 2) = g(p2) (Claim 2)
We know that g(p2) = 0 (Claim 8)

Hence, if the state is in <[0,1/2], p> the second bullet will be destroyed with probability 1.
So at some point we return to state <p> in which the first bullet has probabilty g(p) to survive.


Claim 10: f(<[a,b], p>, 1) <= g(p)*(2 - g(p))

Same as in Claim 5.
The upper bound is true for all p2 in [a,b] so we can derive this bound from the law of total probabilty.


Claim 11: for all p > 1/2 , g(p) <= (1/2)*g(p) + (p - 1/2)*g(p)*(2 - g(p))

g(p) = Pr[ The next bullet fired has velocity in [0,1/2] ] * f(<[0,1/2], p>, 1) + Pr[ The next bullet fired has velocity in (1/2, p] ] * f(<(1/2, p], p>, 1) =
= 1/2 * g(p) + (p - 1/2) * f(<(1/2, p], p>, 1) <= (1/2)*g(p) + (p - 1/2)*g(p)*(2 - g(p))


Claim 12: for all p > 1/2 , g(p) = 0 or g(p) <= 2 - 1/(2p - 1)

If g(p) = 0 then the claim is true. Otherwise we can take Claim 11 and divide by g(p):
g(p) <= (1/2)*g(p) + (p - 1/2)*g(p)*(2 - g(p))
1 <= 1/2 + (p-1/2)*(2 - g(p))
1/2 <= (p-1/2)*(2 - g(p))
1/(2p - 1) <= 2 - g(p)
g(p) <= 2 - 1/(2p - 1)


Claim 13: for all p <= 3/4, g(p) = 0

Same as in Claim 8.
This is a direct result of Claim 7 and g(p) being in [0,1] (since it is a probabilty).


Claim 14: If we know that for all p <= 1-1/2k , g(p) = 0 then for all p <= 1-1/2k+1 , g(p) = 0

This is basically the same as the previous steps (Claims 9-13), only for the general case.
g(p) = Pr[ The next bullet fired has velocity in [0,1-1/2k] ] * f(<[0,1-1/2k], p>, 1) + Pr[ The next bullet fired has velocity in (1-1/2k, p] ] * f(<(1-1/2k, p], p>, 1) =
= (1-1/2k) * g(p) + (p - (1-1/2k)) * f(<(1-1/2k, p], p>, 1) <= (1-1/2k)*g(p) + (p - 1 + 1/2k)*g(p)*(2 - g(p))

If g(p) = 0 then the claim is true, Otherwise we can divide by g(p):
g(p) <= (1-1/2k)*g(p) + (p - 1 + 1/2k)*g(p)*(2 - g(p))
1 <= (1-1/2k) + (p - 1 + 1/2k)*(2 - g(p))
1/2k <= (p - 1 + 1/2k)*(2 - g(p))
1/(2k*p - 2k + 1) <= 2 - g(p)
g(p) <= 2 - 1/(2k*p - 2k + 1)

for p <= 1-1/2k+1 the expression above is <= 0


Claim 15: for all k, If p <= 1-1/2k then g(p) = 0

This is given by induction with Claim 8 as it's base, and Claim 14 as the induction step.


Claim 16: for all p < 1 , g(p) = 0

This is derived directly from Claim 15 (for large enough k ...).


The probabilty for any bullet to be fired with velocity 1 is 0.
Since Unifying a countable amount of events with probabilty 0 results in an event also with probabilty 0, this implies that the probability that at least one bullet has velocity 1 is 0.

Given that no bullet has velocity 1, any bullet has a probability of 0 for survival (g(p) = 0).
Since Unifying a countable amount of events with probabilty 0 results in an event also with probabilty 0, this implies that the probability that at least one bullet survives is also 0.


[/hideb]
Title: Re: Gun with infinite bullets
Post by mykingislonely on Mar 14th, 2014, 7:07pm
(Complete beginner riddler here. I have no solutions, just some random thoughts)

Great problem! I've been going back and forth to thinking it was 0% or 100% and now I have no clue.


I don't mean to go off-topic on this thread, but I remember some other problem that went something like:

"You are playing a game in which you get 1 point for rolling a 6 and lose 1 point for any other roll. If you keep playing, you should approach -infinite points. After playing a while, you are at -1,000,000 points.
What are the odds of approaching -infinity without crossing 0?"


Somehow I imagine this problem being really similar. The probability in getting to infinity increases after the average  shot (or roll)... but there is always this chance of losing your leading bullet  (or getting to 0).
Title: Re: Gun with infinite bullets
Post by aicoped on May 1st, 2014, 10:26pm
I don't think I agree with the proposed solutions, but I know infinity can cause some issues.

If there can be no bullets with speed 1, then there clearly is some maximal speed bullet. while the probability of a given bullet hitting exactly 1 is "zero" the probability of firing a "faster than the fastest bullet also approaches zero with whatever method you use"

The maximal speed bullet has a limit of 1 and the speed of the bullet that reaches infinity by necessity must be the bullet with the limit of 1.

Firing any specific speed bullet has a zero probabilty, but yet a bullet gets fired.

If I said what is your probability to fire a bullet moving at .75 it is still zero. If any bullet you can name is probability zero, but you must fire a bullet of some speed, there is clearly a problem in our formulation of the problem.

I think though since the rate at which our probability of firing a specific bullet with a given probability goes down at the same rate our "accuracy" of measuring bullet speed does as well, then that all cancels and we could solve the problem by using instead of zero to 1 we could use 1 to 100 and see what happens then we could try again with 1 to 1000 and so on. While going from a finite result to infinite is not always possible, I think it is in this case.

If i am way off or if there is a known solution, would someone link me it?
Title: Re: Gun with infinite bullets
Post by foo on May 2nd, 2014, 1:29am
I think that the reason you don't agree with the proposed solution is that you are not familiar with  continuous random variables (as opposed to discrete random variables).

You are welcome to read about it:
http://en.wikipedia.org/wiki/Probability_distribution

"When a random variable takes values from a continuum, probabilities can be nonzero only if they refer to intervals."

In our case, it means that the probability that a bullet will have a velocity of either 0.75, 0.764539 or 1 is 0. However, the probability that the velocity is between 0.7 and 0.8 is 0.1 since the distribution is uniform.

The proposed solution, if it is indeed correct, only solves the "steady state" variant proposed by towr in this thread. I'm not familiar with any solution for the original riddle.
Title: Re: Gun with infinite bullets
Post by Grimbal on May 2nd, 2014, 7:29am
IMB's "Ponder This" has a challenge very much related to this one.
http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/May2014.html

And from the name of the inventor, I got the following page that proposes a solution a the end.
http://brentmeeker.com/?page_id=48


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board