eklhad@ihnet.UUCP (K. A. Dahlke) (06/12/85)
< 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