# Expressing “Probability that #successes is an even number” mathematically

Needing a little help with my probability concept. Here's the question:

An urn contains $10$ red balls, $20$ green balls and $30$ blue balls. Each trial consists of drawing a ball from the urn with replacement. If either red or blue ball is drawn, the trial is called a success. Suppose that $n$ independent trials are performed and let $P_n$ be the probability that the total number of successes that result is an even number. Find $P_n$ and $\lim \limits_{n \to \infty} P_n$.

My Solution:

$$P (\text{success}) = \frac{\binom{40}{1}}{\binom{60}{1}} = \frac {2}{3} .$$

Then it is a binomial r.v with parameters $(n, \frac 2 3)$.

How do I express the idea "total number of successes that result is an even number" mathematically?

Thanks for looking at my question.

-

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.

-
Hi Andre, thanks for answering my question, your solution looks so much neater and cleaner! but i obtained the question from an introductory probability course, so the idea of "recurrence" is currently beyond my scope, so i'm more familiar with Didier's Pn. Thanks again for taking your time though to answer my question though, i'll be sure to revisit your solution again once i add more tricks to my mathematical arsenal. – adsisco Nov 6 '11 at 18:01
actually, i read it 5 times through, and i think they are starting to make sense to me! i actually like your solution better now =D – adsisco Nov 6 '11 at 18:05
@adsisco: If the solution by Didier Piau is the one that suits your needs, it is the one that should be accepted. He was of course perfectly aware of the recurrence solution, and chose not to use it. – André Nicolas Nov 6 '11 at 18:07
I'm sure the binomial in Didier's solution is instantly recognizable by most probability students, but theres an elegance to your solution that i'm fond of. There is something to be learnt here. – adsisco Nov 6 '11 at 18:12

Since $P_n=P(X_n\ \text{is even})$ with $X_n$ binomial $(n,p)$ and $p=\frac23$, $$P_n=\sum\limits_{k\geqslant0}P(X_n=2k)=\sum\limits_{k\geqslant0}{n\choose 2k}p^{2k}(1-p)^{n-2k}.$$ From this point, it might help to note that, for every $(x,y)$, one can compute $$e_n(x,y)=\sum\limits_{k\geqslant0}{n\choose 2k}x^{2k}y^{n-2k}\quad \text{and}\quad o_n(x,y)=\sum\limits_{k\geqslant0}{n\choose 2k+1}x^{2k+1}y^{n-2k-1}$$ both at the same time by considering $e_n(x,y)+o_n(x,y)$ and $e_n(x,y)-o_n(x,y)$.

Edit Once you computed $P_\infty=\lim\limits_{n\to\infty} P_n$, you might wish to check that $P_\infty=\frac23(1-P_\infty)+\frac13P_\infty$ and to explain why this relation, which allows to compute $P_\infty$ without knowing what the exact formula for $P_n$ is, should hold.

-
I'm still confused about the computation of limit, it seems like from the last equation P_infinity = 1/2 which seems kinda intuitive, after all, the chance of odd/even numbers are equal? Anyway, you've answered my original question perfectly, great work! THANKS ALOT! heres a tick =D – adsisco Nov 6 '11 at 12:13
I wonder if you computed $e_n(x,y)+o_n(x,y)$ and $e_n(x,y)-o_n(x,y)$ and deduced from them the value of $P_n$ for every $n$ (how?) and deduced FROM THAT the value of the limit. Your comment makes it sound like you did not. – Did Nov 6 '11 at 13:11