A coin is tossed $n$ times. What is the probability of getting odd number of heads?

I started this chapter sometimes ago and faced in front of a tough problem. At first I started considering cases. Case-I : The probability of getting 1 head.Case-II : The probability of getting 3 head and so on. But there are many cases. So how can I solved this . Please help me. Thank you!


Hint. Let $p_n$ be the probability of getting an odd number of heads tossing a coin $n$ times, then $$p_{n+1}=(1-p_1)\cdot p_{n}+ p_1(1-p_{n})$$ where $p_1$ is the probability to obtain a head with one toss. So given $p_1$ (if the coin is fair then $p_1=1/2$), the above linear recursion allows us to evaluate $p_n$ for any positive integer $n$.

P.S. The recursion is explained as follows: at the $(n+1)$th toss we have an odd number of heads if and only if one of these disjoint cases occurs:

i) we have a tail and in the previous $n$ tosses there are an odd number of heads;

ii) we have a head and in the previous $n$ tosses there are an even number of heads.

  • $\begingroup$ @RoberZ So what is the answer $\endgroup$ – Agile_Eagle Nov 17 '17 at 15:13
  • $\begingroup$ @DeltaScuti_Fomalhautb What is $p_1$? Then you will be able to find $p_n$... $\endgroup$ – Robert Z Nov 17 '17 at 15:15
  • $\begingroup$ @DeltaScuti_Fomalhautb it isn't always necessary to answer the question - it is a hint. $\endgroup$ – John Doe Nov 17 '17 at 15:15
  • $\begingroup$ @RobertZ Ok sorry got it $\endgroup$ – Agile_Eagle Nov 17 '17 at 15:16
  • $\begingroup$ @RobertZ please explain why you had written $p_n=(1-p_1)p_n+p_1(1-p_n)$? $\endgroup$ – Sufaid Saleel Nov 18 '17 at 2:03

First toss $n-1$ times. When you toss the $n^{th}$ time, one outcome will give an even number of heads and one outcome an odd number of heads.

If the coin is a fair coin, this gives the result immediately. If it is not, then you need to combine the probabilities of odd/even after $n-1$ tosses with the probabilities on the last toss as Robert Z has done, or sum the binomial.

  • $\begingroup$ For a fair coin this analysis is complete due to indistinguishability, but for a biased coin it is not, then it matters if $n$ is odd or even. $\endgroup$ – orlp Nov 17 '17 at 15:16
  • $\begingroup$ @orip True, I had assumed an unbiased coin, and will make that clear. Robert Z's answer does the recurrence version o which this would lead and others are summing the binomial. $\endgroup$ – Mark Bennet Nov 17 '17 at 15:18

The probability of getting $k$ heads is $\binom{n}{k}2^{-n}$. So the required probability is $$\sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n}{2k+1}2^{-n}=2^{-n}\times2^{n-1}=\frac{1}{2}$$


At first we need to determine the sample space.

The sample space is analogous to a 'n' digit number whose each place can have only two digits, i.e., either a head(H) or a tail(T). For example, a three digit number can be written as HTT, or, HTH, or, HHH, etc.

Considering this analogy, we get the total number of 'n' digit numbers as $2^5$. Please refer to the figure: Sample space. So, our sample space consists of $2^5$ elements.

Now, we need the number of favorable events, which is in this case, odd number of heads. Therefore the number of favorable events is the summation of the series -

number of times we get only 1 head + number of times we get 3 heads + number of times we get 5 heads + number of times we get 7 heads + $\cdots$

Let the desired number of head be 3 and the coin is tossed eight times. So, one of our possible number is HHHTTTTT. The number of distinct permutations of this number is $\frac{8!}{3! \times 5!}$, which is equal to $8C_3$.

Generalizing this case, when the coin is tossed n number of times and for 'k' number of desired heads, the number of outcomes is $nC_k$.

So, finally we get the number of favorable events as $nC_1+nC_3+nC_5+nC_7+\cdots$

Now, we can determine the probability of getting odd number of heads as \begin{align} \text{P(odd numbers of heads)} &= \frac{nC_1+nC_3+nC_5+nC_7+\cdots}{2^n} \\ &= \frac{2^{n-1}}{2^n} \\ &= \frac{1}{2} \end{align}


If $X$ is the number of heads you have to calculate $$P(X \text{ is odd})=\sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}P(X=2k+1).$$

As $X\sim Binomial(n,1/2)$, you can calculate that probability for each $k$. That is: $$P(X \text{ is odd})=\sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}{n \choose 2k+1}\left(\frac12\right)^{2k+1} \left(\frac12\right)^{n-(2k+1)} =\left(\frac12\right)^n \sum_{k=0}^{\left\lfloor \tfrac{n-1}2 \right\rfloor}{n \choose 2k+1}.$$

Now, if $n$ is odd the last sum is $${n \choose 1}+{n \choose 3}+\cdots+{n \choose n-2}+{n \choose n},$$ which by the symmetry of the binomial coefficients is equal to $${n \choose n-1}+{n \choose n-3}+\cdots+{n \choose 2}+{n \choose 0}.$$

Since it is known that $${n \choose 0}+{n \choose 1}+{n \choose 2}+\cdots+{n \choose n-1}+{n \choose n}=2^n,$$ then both previous sums add up to $\tfrac{2^n}2=2^{n-1}$.

On the other hand, if $n$ is even the sum is $${n \choose 1}+{n \choose 3}+\cdots+{n \choose n-1}=$$ $$=\left[{n-1 \choose 0} + {n-1 \choose 1}\right] + \left[{n-1 \choose 2} + {n-1 \choose 3}\right]+\cdots+\left[{n-1 \choose n-2}+{n-1 \choose n-1}\right]=$$ $$=2^{n-1},$$ as in the '$n$ is odd' case.

So for every $n \in \mathbb{N}$ $$P(X \text{ is odd})=\left(\frac12\right)^n \cdot 2^{n-1}= \frac12.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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