I shouldn't think William Feller is on this list either, unless Rich has been scouting for talent in unexpected locations: according to Wikipedia, he died in 1970! http://en.wikipedia.org/wiki/William_Feller WFL On 6/17/12, 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.

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

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.