eklhad@ihnet.UUCP (K. A. Dahlke) (06/10/85)
< no two-headed coins please > Suppose you have a counter, initialized to 0. Flip a fair coin N times, incrementing the counter whenever the coin comes up heads, and decrementing the counter whenever the coin comes up tails. As a function of N, what is the probability that the counter never dipped below 0. By never, I mean after each flip, the counter should be >= 0. N 1 2 3 4 5 6 7 8 odds 1/2 2/4 3/8 6/16 10/32 20/64 35/128 70/256 I have come up with some recursive relations that answer the question, but I was hoping for a simpler formula. Surely this question has been asked, and answered, before. Happy flipping. -- Karl Dahlke ihnp4!ihnet!eklhad
gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins) (06/11/85)
In article <239@ihnet.UUCP> eklhad@ihnet.UUCP (K. A. Dahlke) writes: > Suppose you have a counter, initialized to 0. >Flip a fair coin N times, incrementing the counter whenever the coin >comes up heads, and decrementing the counter whenever the coin comes up tails. >As a function of N, what is the probability that the >counter never dipped below 0. >Surely this question has been asked, and answered, before. >Karl Dahlke ihnp4!ihnet!eklhad Yes, Feller "An Introduction to Probability Theory and its Applications" Volume 1, section iii.2, page 75, equation 2.3. Also see the next Theorem "Lemma 1" of section 3, pg 76, in which he proves that this probability is the same as the probability that it becomes 0 exactly on the n'th step (n even). -- Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo {allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins
hes@ecsvax.UUCP (Henry Schaffer) (06/11/85)
This is a classical Random Walk problem. The answer concerning the probability of crossing the equal number of heads and tails ratio depends very much on whether the coin is symmetrical. It is my understanding that a symmetrical coin will return to equal numbers again and again (although at surprisingly long intervals) and so will always eventually cross over to the other side. Ref:An Intro to Probability Theory with Applications Vol 1. (I have the 2nd ed., copyright 1957) Chap. 3 is titled "Coin Tossing and Random Walks"
lambert@boring.UUCP (06/14/85)
> Suppose you have a counter, initialized to 0. > Flip a fair coin N times, incrementing the counter whenever the coin > comes up heads, and decrementing the counter whenever the coin comes up tails. > As a function of N, what is the probability that the > counter never dipped below 0. > By never, I mean after each flip, the counter should be >= 0. > N 1 2 3 4 5 6 7 8 > odds 1/2 2/4 3/8 6/16 10/32 20/64 35/128 70/256 > I have come up with some recursive relations that answer > the question, but I was hoping for a simpler formula. Let F(N) stand for the numerator of the above odds (so F(7) = 35) and put F(0) = 1, F(N) = 0 for N < 0. Then F(N) is the number of sequences of increments/decrements not dipping below zero. For N = 4, these sequences are ++++ +++- ++-+ ++-- +-++ +-+- Here is a CF grammar for the language of such sequences: F ::= D | D+F D ::= | D+D- Using the theory of generating functions, we find equations for f(x) and d(x), where f(x) is the formal power series SUM(N=0,...) F(N)*x^N and d(x) is defined likewise. (D(N) is of course the number of sentences leaving the counter zero.) This gives f(x) = d(x) + d(x)*x*f(x) = d(x)(1+xf(x) d(x) = 1 + d(x)*x*d(x)*x = 1+x^2d(x)^2. Eliminating d(x) gives f(x) = 1/(1-2x) - xf(x)^2. This gives a recurrence relation for F(N): F(N) = 2^N - SUM(P+Q=N-1) F(P)F(Q). For example, F(7) = 128 - (1*20+1*10+2*6+3*3+6*2+10*1+20*1) = 128 - 93 = 35. From the numeric evidence, we guess that F(2N-1) = F(2N)/2 for N > 0. By putting f(x) = g(x) + (g(x)-1)/(2x) (corresponding to G(2N) = F(2N), G(2N+1) = 0) we find (after considerable juggling) g(x)^2 = 1/(1-4x^2). So G(2N+1) = 0 indeed, proving the guess, and the coefficients G(2N) of x^(2N) in the formal power series expansion of g(x) must satisfy the identity SUM(2P+2Q=2N) G(2P)G(2Q) = 4^N. This has the same pattern as the well-known identity SUM(P+Q=N) C(2P,P)*C(2Q,Q) = 4^N, where C(P,Q) = (P+Q)!/(P!Q!). Moreover, G(0) = F(0) = 1 and C(0,0) = 1, so it must be the case that F(2N) = C(2N,N) and F(2N-1) = C(2N,N)/2 = C(2N-1,N-1). So F(N) = C(N, floor(N/2)). The elements of the sequence occur in Pascal's Triangle, thus: >1< ^ >1< 1 ^ 1 >2< 1 ^ 1 >3< 3 1 ^ 1 4 >6< 4 1 ^ 1 5 >10< 10 5 1 ^^ 1 6 15 >20< 15 6 1 ^^ 1 7 21 >35< 35 21 7 1 ^^ -- Lambert Meertens ...!{seismo,okstate,garfield,decvax,philabs}!lambert@mcvax.UUCP CWI (Centre for Mathematics and Computer Science), Amsterdam