A gun sits on a line. Every second, the gun shoots a bullet to the right at a random constant speed between 0 and 1. If two bullets collide they annihilate. It's probability 0, but if more than two bullets collide, the slowest bullets annihilate in pairs. Can we expect the speed of the furthest bullet to approach 1 over time?
I like David's problem a lot. A simpler scenario that seems interesting (and is probably simpler to analyze) involves a gun that shoots a bullet to the right at a random speed that is either 1 or 2 in an iid (independent, identically distributed) fashion, with respective probabilities p and q, with p+q=1. (If you like, we can focus on the case p=q=1/2.) Here the speed of the furthest bullet has trivial asymptotics but other features of the evolution of this system may not be so obvious. There will be a whole bunch of bullets moving at speed 2 that are to the right of all the bullets moving at speed 1 and hence can never be destroyed (call them the immortal bullets, at least until someone comes up with a better name); how does this bunch of bullets grow over time, and how far apart are they typically spaced? It's not obvious to me that the spacing between the successive immortal bullets should be iid. I'd be glad if someone wrote up some code and generated some pictures for us to see, for both my dynamics and David's. I'd also like to see what happens with a non-random gun that simply alternates between emitting speed-1 bullets and speed-2 bullets; probably it gives something with a simple fractal structure, but I'm too tired right now to do by-hand simulations or to code. Jim Propp On Tue, Jun 5, 2012 at 3:16 PM, David Wilson <davidwwilson@comcast.net>wrote:
A gun sits on a line.
Every second, the gun shoots a bullet to the right at a random constant speed between 0 and 1.
If two bullets collide they annihilate.
It's probability 0, but if more than two bullets collide, the slowest bullets annihilate in pairs.
Can we expect the speed of the furthest bullet to approach 1 over time?
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
On 6/6/2012 2:16 AM, James Propp wrote:
I'd also like to see what happens with a non-random gun that simply alternates between emitting speed-1 bullets and speed-2 bullets; The only possible collision is a 2 colliding with a 1 ahead of it. So alternating 1's and 2's should annihilate in simply cyclic pattern.
But some simulations, yeah.
Okay, I've spent a day playing with this problem, and I really like it. David asked "Can we expect the speed of the furthest bullet to approach 1 over time?" Prying things apart a bit: A bullet is shot at each time t=0,1,2,..., with velocity v_t. (I'll generally identify bullets with the times at which they are fired.) Over time there is a sequence of rightmost bullets -- perhaps finite, perhaps infinite. Suppose they are the bullets shot at times r_0=0, r_1, r_2, etc. (perhaps ending ...r_n), with velocities v_r_0, v_r_1, v_r_2, etc. Bullet r_i only becomes rightmost when bullet r_(i-1) gets destroyed. Since each r_i is at some point a rightmost bullet, it must be killed off by a bullet fired later than it -- say its slayer is the bullet (fired at time) s_i, and their mutual annihilation happens at time a_i. Then r_i < s_i < r_(i+1). We also know v_r_i < v_s_i -- that is, s_i must have moved faster than r_i, since s_i was fired later and caught up with r_i. But we don't know how v_r_(i+1) compares to v_r_i, certainly: when s_i takes out rightmost r_i, it's of coure possible that its replacement rightmost r_(i+1) is a slower-moving bullet than it was. This alternation between rightmosts and their slayers is a special case of a more general phenomenon: every stream of bullets has a combinatorial type where bullets turn into properly nested open and closed parens, where the "(" are the elder and the ")" are the younger in each colliding pair. Except, of course, for the bullets that never get destroyed -- the time evolution of the combinatorial state is that we have a string of "(", ")", along with strings of "?"s not contained in any parens at all, whose fate is yet to be determined. The r's and s's aren't necessarily the outermost pairs in this sequence: the combinatorial type I just described doesn't care about the relative times of the annihilations, except that inner pairs have to collide before the ones containing them, while the notion of rightmost is based on which is the first "?" at the time the the previous one is resolved into a ")". It may be that the outermost pairs of parens here are nicer to study than the rightmosts. Anyway! So David asks (1) whether the sequence of r_i's is expected to be infinite with probability 1, and (2) whether the v_r_i's have limit 1 with probability 1. We can also ask about the probability distribution of r_i and v_r_i, and the distribution of how long bullet r_i gets to be the furthest (that is, a_i - a_(i-1)). Note that even if we don't expect the sequence of v_r_i to have limit 1, we might expect successive v_r_i to be drawn from distributions that lean towards 1 more heavily over time -- but not so much so that we'd get a limit-1 result, since we might expect (with probability p>0, maybe 1) to see randomly-drawn values from these distributions to sometimes end up far from 1 by chance. Anyway, I wrote some Mma to do simulations. Obligatory trivial formula: the bullets fired at times t0 and t1 will hit each other at time (t1 v_t1 - t0 v_t0) / (v_t1 - v_t0), if that quantity is positive and they both survive that long. A picture of a random state at time t=1M is at http://oi47.tinypic.com/140by9x.jpg, and a 100-frame video of the progress every 10K steps towards this 1M state is at http://tinypic.com/r/almd10/6. At time 1M there are 106 remaining bullets, with birth times and velocities: {{5769, 0.810498}, {76434, 0.781825}, {158485, 0.847359}, {279802, 0.759877}, {280185, 0.759482}, {321534, 0.788998}, {326931, 0.774271}, {356924, 0.765573}, {359973, 0.741867}, {384862, 0.762665}, {391833, 0.753527}, {394718, 0.721474}, {440913, 0.781062}, {477110, 0.801775}, {477123, 0.800536}, {501934, 0.812875}, {501997, 0.794214}, {501998, 0.784559}, {512309, 0.762418}, {512448, 0.749265}, {549709, 0.774931}, {570286, 0.789898}, {571895, 0.761382}, {572468, 0.752214}, {588167, 0.77105}, {634026, 0.746764}, {655957, 0.759021}, {659534, 0.746899}, {712195, 0.793246}, {718834, 0.768258}, {721235, 0.722048}, {749020, 0.753078}, {752769, 0.753849}, {753736, 0.750945}, {798831, 0.740068}, {801220, 0.747585}, {801229, 0.742817}, {805500, 0.723091}, {828325, 0.739009}, {828520, 0.737319}, {828627, 0.704252}, {848996, 0.787475}, {850039, 0.765578}, {859176, 0.800172}, {860315, 0.778141}, {873248, 0.847469}, {873251, 0.802821}, {875094, 0.796998}, {876177, 0.782271}, {886480, 0.746351}, {886581, 0.735464}, {891744, 0.747382}, {893241, 0.737935}, {905774, 0.740857}, {905907, 0.690533}, {925048, 0.738608}, {928211, 0.744855}, {940638, 0.771715}, {946711, 0.721796}, {946780, 0.711175}, {952667, 0.764724}, {952698, 0.742518}, {955627, 0.770061}, {955992, 0.760852}, {956849, 0.728275}, {968868, 0.770733}, {969119, 0.656716}, {978862, 0.855576}, {980161, 0.85302}, {982578, 0.799501}, {985525, 0.798804}, {985526, 0.752503}, {989249, 0.727467}, {989386, 0.699095}, {993265, 0.787379}, {993370, 0.717206}, {994119, 0.755953}, {994442, 0.726103}, {994443, 0.58519}, {994526, 0.567163}, {996307, 0.817535}, {997766, 0.979566}, {997769, 0.901306}, {997770, 0.682783}, {997781, 0.675616}, {998802, 0.950575}, {998833, 0.85234}, {998870, 0.769616}, {999017, 0.602757}, {999494, 0.868798}, {999495, 0.830337}, {999524, 0.851822}, {999669, 0.796337}, {999848, 0.545824}, {999927, 0.933554}, {999944, 0.886968}, {999961, 0.96944}, {999978, 0.924073}, {999985, 0.587939}, {999988, 0.718973}, {999989, 0.580051}, {999992, 0.440393}, {999995, 0.278242}, {999998, 0.154237}, {999999, 0.0326541}, {1000000, 0.77405}} The 2nd- and 3rd-oldest bullets will annihilate one another soon, and the eldest still has plenty of bullets slower than it that will provide it protection from young position-usurpers for a while to come. If no new bullets were fired at this point, then the current eldest would keep its position forever; after time ~27684002.34, when bullets 512309 and 718834 collide, only eight of the bullets would remain: {{5769, 0.810498}, {501998, 0.784559}, {752769, 0.753849}, {753736, 0.750945}, {999989, 0.580051}, {999992, 0.440393}, {999995, 0.278242}, {999998, 0.154237}} and since their velocities are in decreasing order, no more collisions would occur. I can imagine coming up with a recursive formula for the probability of some finite combinatorial type happening, and maybe one could get a closed form out of it, but I haven't played with this in Mma yet. It would be very cool to be able to say anything about the probability of the current rightmost bullet ever being annihilated. Whew, okay, that came out much longer than I thought it was going to be. Heh. --Michael On Tue, Jun 5, 2012 at 6:16 PM, David Wilson <davidwwilson@comcast.net>wrote:
A gun sits on a line.
Every second, the gun shoots a bullet to the right at a random constant speed between 0 and 1.
If two bullets collide they annihilate.
It's probability 0, but if more than two bullets collide, the slowest bullets annihilate in pairs.
Can we expect the speed of the furthest bullet to approach 1 over time?
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
-- Forewarned is worth an octopus in the bush.
participants (3)
-
David Wilson -
James Propp -
Michael Kleber