Consider a series of independent trials at each of which there is a success of a failure with probabilities $p$ and $1-p$ respectively. I am finding it difficult to derive the probability of even number of successes occurring at the nth trial. Any assistance will be much appreciated. Thanks
[Math] Probability of even number of successes in a series of independent trials
generating-functionsprobability
Related Solutions
Let $P_n$ be the probability that after $n$ trials the number of successes is even.
Let $p$ be the probability of success on any one trial. In our problem, $p=2/3$, but we might as well generalize a bit.
The number of successes after $n+1$ trials can be even in two ways: (a) After $n$ trials we had an odd number of successes and we got a success on the $(n+1)$-th trial; or (b) After $n$ trials we had an even number of successes, and we had a failure on the $(n+1)$-th trial. The probability of (a) is $p(1-P_n)$ and the probability of (b) is $(1-p)P_n$. We therefore have the recurrence $$P_{n+1}=p(1-P_n)+(1-p)P_n=p+(1-2p)P_n.\qquad (\ast)$$ The recurrence $(\ast)$ is linear, and there are general tools for solving such recurrences. But the recurrence is particularly simple, as is the physical situation, so we will use a trick.
It is intuitively clear that if $p(1-p)\ne 0$ and $n$ is large, then $P_n$ should be close to $1/2$. Let $P_n=1/2+y_n$, and substitute in $(\ast)$. There is a lot of cancellation, and we obtain $$y_{n+1}=y_n(1-2p). \qquad (\ast\ast)$$ Note that $y_0=1/2$, since if there are $0$ trials, for sure there are $0$ successes. Each time we increment $n$ by $1$, $y_n$ gets multiplied by $1-2p$. So the sequence $(y_n)$ is the geometric sequence $y_n=\frac{1}{2}(1-2p)^n$, and therefore $$P_n=\frac{1}{2}(1+(1-2p)^n).$$ If $p=0$ or $p=1$, $P_n$ is completely determined by the parity of $n$. Suppose now that $p\ne 0$ and $p\ne 1$. Then $|1-2p|<1$, so $(1-2p)^n$ approaches $0$ as $n \to\infty$. Thus $P_n$ indeed has limit $1/2$.
Comments: $1$. The recurrence approach can be used with more complicated problems, such as determining the probability that the number of successes after $n$ trials is a multiple of $3$.
$2$. One can also use an algebraic approach which is basically a rewording of the solution by Didier Piau. Let $F_n(t)=(tp +(1-p))^n$. Expand $F_n(t)$ using the Binomial Theorem. Evaluate $F_n(t)$ at $t=1$ and at $t=-1$, add up. Suppose that $k$ is odd. Then the terms $\binom{n}{k}p^k(1-p)^{n-k}$ and $\binom{n}{k}(-p)^k(1-p)^{n-k}$ cancel. Suppose that $k$ is even. Then the terms $\binom{n}{k}p^k(1-p)^{n-k}$ and $\binom{n}{k}(-p)^k(1-p)^{n-k}$ are equal. It follows that $$P_n=\frac{1}{2}(F_n(1)+F_n(-1))=\frac{1}{2}(1^n+(1-2p)^n).$$
$3$. When we let $y_n=1/2+F_n$, the recurrence simplified. Consider the general recurrence $P_{n+1}=a+bP_n$, where $b \ne 1$. Make the substitution $F_n=w+y_n$. We get $y_{n+1}=by_n +a+ bw-w$. By setting $w=a/(1-b)$, we get the recurrence $y_{n+1}=by_n$, which is simple to solve.
If you want to analytically calculate the sum, you can do as follows: $$ \sum_{n = k}^{\infty} n\binom{n - 1}{k -1} p^{k} (1 - p)^{n - k}=(\frac{p}{1-p})^k\sum_{m = 0}^{\infty} (m+k)\binom{m+k - 1}{m} (1 - p)^{m+k} $$
Now you can find the following identity in the literature: $$ \sum_{m = 0}^{\infty} \binom{m+k - 1}{m} y^{m}=\frac{1}{(1-y)^k} $$ Now by multiplication of $y^k$ and derivation wrt $y$, you get: $$ \sum_{m = 0}^{\infty} (m+k)\binom{m+k - 1}{m} y^{m+k-1}=\left(\frac{y^k}{(1-y)^k}\right)^{'}=\left(\frac{ky^{k-1}}{(1-y)^{k+1}}\right) $$ Now put $y=1-p$ in the first identity and you get:
$$ \mathbb{E}(X)=\frac{k}{p} $$
Best Answer
Use induction. If $P_n$ is the probability of even number of successes in n trials, then
$$ P_n = p(1-P_{n-1}) + (1-p)P_{n-1}$$
This results in
$$ P_n = \frac{1+(1-2p)^n}{2}$$