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.
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.
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.$$
