On Sun, Jun 17, 2012 at 1:01 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I don't think William Feller is on this list, but according to him, the probability p(n) of first hitting -1 at the nth step is
p(n) = bin(n, (n-1)/2) / (n * 2^n)
where the binomial coefficient should be taken as 0 for n even -- so p(2k) = 0, which is obvious anyway.
Right, those are the Catalan numbers, as expected. In other words: Take Dan's K=2 discretization, and look at how many different ways there are for the bullet fired at time 2n+1 to eventually end up a rightmost bullet with velocity 1. That requires that the first 2n bullets all annihilate one another, i.e. that there are n velocity-1's and n velocity-1/2's in the first 2n bullets, with the running total of 1/2's-so-far always larger than 1's-so-far. That's exactly the nth Catalan number. We should be able to do the same thing for K=3. I think I've coded things up in Mma correctly to count exactly this same number with K=3, and I get 1, 0, 3, 0, 16, 0, 93, 0, 620, 0, 4418 possible ways for the bullet fired at time t to eventually be the rightmost bullet with velocity 1. (But I would be delighted for independent verification of those numbers!) No hits in the OEIS, so seems like a new generalization of the Catalans, as if more were needed. Assuming my counts are correct and turning them into decimal approximations of probabilities (dividing by K^n in both cases), we get: K=2: 0.5, 0., 0.125, 0., 0.0625, 0., 0.0390625, 0., 0.0273438, 0., 0.0205078 K=3: 0.333333, 0., 0.111111, 0., 0.0658436, 0., 0.042524, 0., 0.0314993, 0., 0.0249397 Looks like the K=2 starts out larger but drops off more quickly. In other words, if we didn't get lucky with a rightmost-bullet-of-velocity-1 near the beginning, this seems to indicate that it's easier to get one later with the K=3 version than with K=2. No idea whether these higher probabilities are enough larger to make the expected value of the time it happens finite instead of infinite, though. Not sure how to read these if we're seeking augury for the original continuous problem. --Michael
The generating function for these probabilities is shown to be
G(s) = (1 - sqrt(1-s^2)) / s
from which G'(1) = oo. Which shows that as Michael said, the expected time to reach -1 is oo. (I found this to be rather surprising.)
--Dan
Michael wrote: << Surely many people on this list know more than I do about the distribution of times at which the random walker first hits -1.
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.