Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Giving a a fair coin, and tossing it N times, in how many possible outcomes would there be a point wherein there were more heads than tails tossed, ie, net heads.

share|cite|improve this question
The title does not describe the question in the post. – Did Aug 16 '13 at 22:19

The paths of length $N=2n$ such that this does not happen are the Dyck paths, enumerated by the Catalan number $C_n=(n+1)^{-1}{2n\choose n}$. The total number of paths is $2^{2n}$. Hence the probability you are after is $p_{2n}=1-2^{-2n}C_n$ (and $p_{2n+1}=p_{2n+2}$).

For example, $1-p_N\sim cN^{-3/2}$ when $N\to\infty$, with $c=2\sqrt{2/\pi}$.

share|cite|improve this answer
I am slightly confused. "$C_n$ is the number of Dyck words of length $2n$. A Dyck word is a string consisting of $n$ $X$'s and $n$ $Y$'s such that no initial segment of the string has more $Y$'s than $X$'s". Wouldn't he be interested in one minus the probability you are giving? Or am I missing something? – A.E Aug 16 '13 at 22:33
@Orangutango Thanks. Post modified. – Did Aug 16 '13 at 22:36

If $N$ is odd, there is no possibility of equal heads and tails. Thus, the probability of excess heads is $\frac{1}{2}$

If N is even, the probability of equal heads and tails, $P_{equal}$, is given by:$$P_{equal}=\left(\frac{1}{2}\right)^N\frac{N!}{\left(\frac{N}{2}\right)^2}$$The probability of excess heads is then given by$$P_{Heads}=\frac{1-P_{equal}}{2}$$

share|cite|improve this answer

Tossing a coin N times is a binomial distribution and you want to solve the for the CDF=0.5.

You can work it out from the formula in the article but as a short cut ...

The chance of more heads is half the chance of unequal results.

If N is odd the chance of equal results is 0, so the chance of more heads is 0.5.

If N is even the probability of getting equal results is ${N \choose \frac{N}{2}}\frac{1}{2^N}$, so the chance of more heads is $\frac{1-{N \choose \frac{N}{2}}\frac{1}{2^N}}{2}$.

share|cite|improve this answer
Isn't your binomial term greater than 1? – DJohnM Aug 16 '13 at 22:44
Whoops! Talking possible outcomes not probabilities - will edit. – Dale M Aug 17 '13 at 0:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.