Author |
Topic: Gun with infinite bullets (Read 9206 times) |
|
foo
Newbie
Posts: 4
|
 |
Gun with infinite bullets
« on: Nov 2nd, 2013, 2:15pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
|
Re: Gun with infinite bullets
« Reply #1 on: Nov 24th, 2013, 10:43am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Gun with infinite bullets
« Reply #2 on: Nov 24th, 2013, 11:52am » |
Quote Modify
|
on Nov 24th, 2013, 10:43am, 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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Gun with infinite bullets
« Reply #3 on: Dec 27th, 2013, 2:19pm » |
Quote Modify
|
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!
|
| « Last Edit: Dec 27th, 2013, 2:25pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Gun with infinite bullets
« Reply #4 on: Jan 1st, 2014, 11:29am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Gun with infinite bullets
« Reply #5 on: Jan 9th, 2014, 12:50pm » |
Quote Modify
|
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.
|
| « Last Edit: Jan 9th, 2014, 12:52pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: Gun with infinite bullets
« Reply #6 on: Mar 3rd, 2014, 3:13pm » |
Quote Modify
|
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
|
| « Last Edit: Mar 3rd, 2014, 3:15pm by riddler358 » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Gun with infinite bullets
« Reply #7 on: Mar 4th, 2014, 6:26am » |
Quote Modify
|
on Mar 3rd, 2014, 3:13pm, 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...
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: Gun with infinite bullets
« Reply #8 on: Mar 4th, 2014, 8:08am » |
Quote Modify
|
on Mar 4th, 2014, 6:26am, 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"
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Gun with infinite bullets
« Reply #9 on: Mar 4th, 2014, 8:23am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Gun with infinite bullets
« Reply #10 on: Mar 4th, 2014, 8:50am » |
Quote Modify
|
But that's just 0. The probability of any exact value in a continuous smooth distribution is zero.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Gun with infinite bullets
« Reply #11 on: Mar 5th, 2014, 3:40am » |
Quote Modify
|
on Mar 4th, 2014, 8:08am, 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...
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: Gun with infinite bullets
« Reply #12 on: Mar 5th, 2014, 3:05pm » |
Quote Modify
|
on Mar 5th, 2014, 3:40am, 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
|
|
IP Logged |
|
|
|
foo
Newbie
Posts: 4
|
|
Re: Gun with infinite bullets
« Reply #13 on: Mar 8th, 2014, 7:55am » |
Quote Modify
|
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:
| hidden: |
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).
|
|
|
IP Logged |
|
|
|
foo
Newbie
Posts: 4
|
|
Re: Gun with infinite bullets
« Reply #14 on: Mar 8th, 2014, 7:57am » |
Quote Modify
|
| hidden: |
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.
|
|
|
IP Logged |
|
|
|
mykingislonely
Newbie
Posts: 4
|
|
Re: Gun with infinite bullets
« Reply #15 on: Mar 14th, 2014, 7:07pm » |
Quote Modify
|
(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).
|
| « Last Edit: Mar 14th, 2014, 7:07pm by mykingislonely » |
IP Logged |
|
|
|
aicoped
Junior Member
Gender:
Posts: 57
|
|
Re: Gun with infinite bullets
« Reply #16 on: May 1st, 2014, 10:26pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
foo
Newbie
Posts: 4
|
|
Re: Gun with infinite bullets
« Reply #17 on: May 2nd, 2014, 1:29am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print