Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Prob of flipping coin n times, at no time with #h > #t?
Posted:
Feb 7, 2013 1:52 PM


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"? > > >> >  > > >> > John Forkosh ( mailto: j@f.com where j=john and f=forkosh ) > > >> > > >> 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. > >  > > John Forkosh ( mailto: j@f.com where j=john and f=forkosh )
"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.



