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.