Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84 exptools; site ihnet.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!mtuxo!drutx!ihnp4!ihnet!eklhad
From: eklhad@ihnet.UUCP (K. A. Dahlke)
Newsgroups: net.math
Subject: Re: Flipping Coins With Restrictions, Partial Answer
Message-ID: <241@ihnet.UUCP>
Date: Wed, 12-Jun-85 13:53:36 EDT
Article-I.D.: ihnet.241
Posted: Wed Jun 12 13:53:36 1985
Date-Received: Thu, 13-Jun-85 02:06:19 EDT
Distribution: net
Organization: AT&T Bell Laboratories
Lines: 32

< no two-headed coins please >
My original question:
> 	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
An observant mathematician saw the pattern in the above table,
and gave me the formula:  (N chose (N/2)) / 2^N.
It is so obvious, how could I have missed it!?!?
Fortunately, he did not suply a proof,
allowing me to construct my own during an otherwise boring meeting.
There are some beautiful and amazing (to me) relationships at work here.
I will not spoil things by giving a proof, but I will give a hint.
No doubt you recognize the formula.
It gives the probability of a sequence *ending* at 0
(same number of heads as tails).
Find a correspondence function mapping these sequences to legal sequences,
as described in the original problem.
The proof may generalize to include unfair increments,
adding X for a head and subtracting Y for a tail (X and Y integers).
Another question, what is the limit of the probability as N approaches
infinity?  It seems to go to 0, but how to prove it?
And how quickly does it approach 0 (O 1/N)?
How do X and Y affect this limit?
Remember, when the boss looks your way, just nod and smile.
-- 
Is it time to go home yet?
Karl Dahlke    ihnp4!ihnet!eklhad