## Calculating Probability via Generating Functions

You have coins $C_1, C_2, . . . , C_n$ . For each k, coin $C_k$ is biased so that, when tossed, it has probability $\frac{1}{2k+1}$ of falling heads. If the n coins are tossed, what is the probability that number of heads is odd? Express the answer as a rational function of n ?

Let $P_n$ denote the desired probability. Then $P_1 =\frac{1}{3}$, and for $n>1$,  By conditioning on $n^{th}$ coin’s outcome, we can see that

$\begin{array}{rcl} P_n &= &\frac{2n}{2n+1} P_{n-1} + \frac{1}{2n+1} (1-P_{n-1}) \\ &=& \frac{2n-1}{2n+1} P_{n-1} + \frac{1}{2n+1}\end{array}$

Using above recurrence we get $P_2= \frac{2}{5}, P_3=\frac{3}{7}$. Now it is easy to guess that $P_n=\frac{n}{2n+1}$. It is easy to verify this guess using Mathematical Induction.

Now, let us see alternative way to derive the same result using Generating Functions.

If $X$ is a discrete random variable taking values on some subset of the non-negative integers,{0,1,….,n}, then the probability-generating function of X is defined as :

$G_{X}(z) = E( z^{X}) = \sum_{x=0}^{n} p(X=x) z^x$

where symbol $E$ denotes the Expectation of Random Variable.

If $X_1, X_2, ..., X_n$ is a sequence of independent ( not necessarily identically distributed ) random variables, and $X = \sum_{i=1}^{n} X_i$, then the probability-generating function of $X$ is given by

$G_{X}(z) = E( z^{X}) = E(z^{\sum_{i=1}^{n}X_i})= G_{X_1}(z)G_{X_2}(z)....G_{X_n}(z)$.

The last equality follows from the fact that the expectation of  product of independent random variables is equal to the product of expectation of individual random variables.

Let the probability of heads on $C_i$ be donted by $p_i$. So $p_i=\frac{1}{2k+1}$. Let $q_i=1-p_i.$

Let $X_i$ denote the indicator random variable, which takes on value 1 if $C_i$ falls on heads, takes value 0 otherwise

P.G.F of $X_i$ is $G_{X_i}(z) = q_i + p_iz,\forall i=1,2,...,n$

Let $X$ denote the number of heads in the n coin tosses. So $X = \sum_{i=1}^{n} X_i$

P.G.F of $X$ is $G_X(z) = Q_0 + Q_1z +Q_2z^2 ...+ Q_nz^n$

The probability of getting exactly m heads is equal to the coefficient of $z^m$ in the generating fucntion, that is $Q_m$.

Since the coin tosses are independent,

$G_X(z) = Q_0 + Q_1z +Q_2z^2 ...+ Q_nz^n = \prod_{i=1}^{n}(q_i +p_iz)$

Notice that

$G_X(1) = Q_o + Q_1 + Q_2 + ... + Q_n = \prod_{i=1}^{n}(q_i +p_i)=1$

and

$G_X(-1) = Q_o - Q_1 + Q_2 - ... + (-1)^{n} Q_n =\prod_{i=1}^{n}(q_i-p_i)$

The required probability is $Q_1 + Q_3 + Q_5 + ...$

Hence

$\begin{array}{rcl} P_n &=& \frac{G_X(1) - G_X(-1)}{2} \\ &=& \frac{1}{2}( 1-\prod_{i=1}^{n}(1-2p_i)) \\ &=& \frac{1}{2}( 1-\prod_{i=1}^{n}\frac{2k-1}{2k+1})\\ &=& \frac{1}{2}(1-\frac{1}{2n+1})\\ &=& \frac{n}{2n+1} \end{array}$

It is easy to interpret the result of substituting 1 for z in terms of probability : it is the probability of Sample Space , which is 1. The result of substituting -1 for z, is the Difference between  probability of getting Even number of heads and probability of getting Odd number of heads ( Generating functions actually helped in calculating this difference easily ). The difference is equal to $\prod_{i=1}^{n}(q_i-p_i)$ . In retrospect, we can see why this is so. If we expand this product we see that each +ve term in the expansion correspond to the probability of some sample point which has even number of heads in it, and each -ve term in the expansion correspond to probability of some sample point which has Odd number of heads in it. Hence the sum of +ve terms is equal to probability of getting Even number of heads, and the sum of -ve terms is equal to probability of getting Odd number of heads.