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

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.

• @RoberZ So what is the answer – Agile_Eagle Nov 17 '17 at 15:13
• @DeltaScuti_Fomalhautb What is $p_1$? Then you will be able to find $p_n$... – Robert Z Nov 17 '17 at 15:15
• @DeltaScuti_Fomalhautb it isn't always necessary to answer the question - it is a hint. – John Doe Nov 17 '17 at 15:15
• @RobertZ Ok sorry got it – Agile_Eagle Nov 17 '17 at 15:16
• @RobertZ please explain why you had written $p_n=(1-p_1)p_n+p_1(1-p_n)$? – 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.

• 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. – orlp Nov 17 '17 at 15:16
• @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. – 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.$$