JohnF
Posts:
219
Registered:
5/27/08


Re: Prob of flipping coin n times, at no time with #h > #t?
Posted:
Feb 8, 2013 2:36 AM


Ray Vickson <RGVickson@shaw.ca> wrote: > On Wednesday, February 6, 2013 11:12:36 PM UTC8, JohnF wrote: >> Ray Vickson wrote: >> > On Wednesday, February 6, 2013 9:12:51 AM UTC8, Ray Vickson wrote: >> >> On Wednesday, February 6, 2013 5:42:18 AM UTC8, JohnF wrote: >> >> >> >> > What's P_n, the prob of flipping a coin n times, >> >> > and at no time ever having more heads than tails? >> >> > There are 2^n possible ht... sequences of n flips, >> >> > comprising a binomial tree (or pascal's triangle), >> >> > with 5050 prob of going left/right at each node. >> >> > So, equivalently, how many of those 2^n paths never >> >> > cross the "center line" (#h = #t okay after even number >> >> > of flips)? >> >> > Actual problem's a bit more complicated. For m<=n, >> >> > what's P_n,m, the prob that #h  #t <= m at all times? >> >> > That is, P_n above is P_n,0 here. Equivalently, how >> >> > many of those binomial tree paths never get >m past >> >> > the "center line"? >> >> >> >> Feller, "Introduction to Probability Theory and its Applications, >> >> Vol I (Wiley, 1968), Chapter III, page 89, deals with this >> >> (and many related) problems. Chapter II deals with the simple >> >> random walk S_k = X_1 + X_2 + ... + X_k, where the X_i are iid >> >> and X_i = +1 with prob. 1/2 each. >> >> >> >> On page 89 Feller states and proves Theorem 1: "The probability >> >> that the maximum of a path of length n equals r >= 0 coincides with >> >> the positive member of the pair p(n,r) and p(n,r+1). >> >> >> >> Earlier in Chapter he gave the formula p(n,k)= Pr{S_n = k} = >> >> C(n,(n+k)/2)/2^n, where C(u,v) denotes the binomial coefficient >> >> "u choose v". >> >> Thanks, Ray. That sounds like my same problem (but what's "iid" mean >> in the context "X_i are iid" in your first paragraph above?). >> I take it my answer should be "the positive member of" p(n,0) and p(n,1), >> where p(n,k) = C(n,(n+k)/2)/2^n. And I'm guessing that means k=0 if >> n even, and k=1 if n odd. >> Actually, I think I already had a solution for the odd cases >> worked out, but much more complicatedlooking than yours: >> P_{2n+1} = 0.5  sum(i=1...n) { 1/(2i) * 1/(2^(2i)) * C(2i,i+1) } >> Note that 2n+1 is always an odd (your k=1, I think) case. >> Numerically, mine gives (haven't programmed yours yet, to check agreement) >> n  P_n >> + >> 0  .5 >> 1  .375 >> 2  .3125 >> .  ... >> 4999 .00798 >> 9999 .00564 >> 19999 .00399 >> slowly going to zero, i.e., you eventually get an extra head >> (your r>0, I think), but it may take a lot longer than you'd >> naively guess (because prob goes to zero very slowly). >> What I still can't get, in closed form, is equating the two >> expressions, i.e., for your n>2n+1 and then k=1, >> yours: p(2n+1,k=1) = C(2n+1,n+1)/2^(2n+1) >> mine: P_{2n+1} = 0.5  sum(i=1...n) { 1/(2i) * 1/(2^(2i)) * C(2i,i+1) } >> Are those two really equal? (I'll get around to checking numerically) >> >> >> The answer to your "<= m" question is the sum of those probabilities >> >> for r from 0 to m, plus the probability that the max is < 0. >> >> The latter can be obtained from the expression on page 77, which is >> >> P{S_1 > 0, S_2 > 0, ... S_2n > 0} = (1/2)* u(2n), >> >> and where u(2j) = C(2j,j)/2^(2j) = P{S_2j = 0}. Note that having >> >> all S_i < 0 has the same probability as having all S_i > 0. >> >> Thanks again. My cumbersome derivation wasn't general enough to cover >> this situation. > > "iid" means independent and identically distributed. > Thus, Feller's S_k is you H  T count at the end of toss k. > Yes, the positive member of the pair p(n,0) and p(n,1) uses > (n,0) if n is even and (n,1) if n is odd (because you need > (n+k)/2 = integer). > > For n even, > P{all S_i <= 0} > = P{max S_1 = 0} + P{all S_i < 0} > = p(n,0) + (1/2)u(n). > If n is odd, the formula for P{all S_i < 0} is, of course, > more complicated. First, X_1 = 1 must happen (so that S_1 < 0); > then the remaining (n1) tosses must not have their HT count > rise above 0, so that means the mutually exclusive events > {max new_S = 0} or {all new_S < 0} must occur (where now we have > (n1) tosses and are starting over, counting from toss 2that is, > new_S_1 = X_2, new_S_2 = X_2 + X_3, etc. We can compute > P{all new_S_i < 0} because n1 is even. So, we finally get > P{all S_i < 0} = (1/2)[p(n1,0) + (1/2)u(n1)] for odd n. > > I have not checked to see if this matches what you got.
Thanks a lot for additional explanation, Ray. Your p(2n+1,k=1) = C(2n+1,n+1)/2^(2n+1), taken from above, indeed matches my P_{2n+1} = 0.5  sum(i=1...n) { 1/(2i) * 1/(2^(2i)) * C(2i,i+1) } for n=0,1,2, as per numerical table above. I'll have to do a little more work to check the large n cases, but would guess agreement. And I fooled around a little algebraically, but so far failed to prove them equal.  John Forkosh ( mailto: j@f.com where j=john and f=forkosh )

