Will the running score ever dip below zero?

Question

Flip a fair coin 2n times. Keep a running score that goes up by 1 for each head and down by 1 for each tail. So after k flips the score is (heads so far) minus (tails so far). What is the probability that the running score is never negative at any point during the 2n flips?

Accepted Answer

We are counting fair-walk paths of length 2n (each step \pm 1) that stay at or above 0 the whole time, then dividing by the 2^{2n} equally likely paths. There is a slick identity: the number of length-2n paths that stay \ge 0 equals the number of paths that end at exactly 0, namely \binom{2n}{n}. One clean way to see it uses the reflection principle to show that the count of non-negative paths ending at height 2j telescopes; summing over all endpoints leaves exactly the central count \binom{2n}{n}. So P(	ext{never negative}) = \frac{\binom{2n}{n}}{2^{2n}} = \frac{\binom{2n}{n}}{4^{n}}. Sanit…

Will the running score ever dip below zero?

Your answer

More Probability questions