Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.1 6/24/83 (MC840302); site boring.UUCP Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!genrad!mit-eddie!think!harvard!seismo!mcvax!boring!lambert From: lambert@boring.UUCP Newsgroups: net.math Subject: Re: Combinatorics, Flipping a Coin With Restrictions Message-ID: <6455@boring.UUCP> Date: Fri, 14-Jun-85 02:45:16 EDT Article-I.D.: boring.6455 Posted: Fri Jun 14 02:45:16 1985 Date-Received: Sat, 15-Jun-85 10:08:56 EDT References: <239@ihnet.UUCP> Reply-To: lambert@boring.UUCP (Lambert Meertens) Distribution: net Organization: CWI, Amsterdam Lines: 89 Apparently-To: rnews@mcvax.LOCAL > 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