Monday 5 January 2015

Generating functions in probability

Say we want to find the probability of a family of three children having exactly two boys and one girl.

Conventional methods
1. List out all possibilities
There are $2^3 = 8$ possibilities (because a child can be either boy or girl, and there are three of them): BBB, BBG, BGB, BGG, GBB, GBG, GGB, and GGG.
As a result, the required probability is $\dfrac{3}{8}$.

2. Binomial probability
$$P(X=r)=C^n_r\:p^r (1-p)^{n-r}$$In this case, $r$ is the number of boy(s), $n = 3, p = 1-p = \frac{1}{2}$. $$P(X=2)=C^3_2 (\frac{1}{2})^2 (\frac{1}{2})^1 = \frac{3}{8}$$

Generating function method
This method makes use of properties of combination.
The function $(b+g)^3=b^3+3b^2g+3bg^2+g^3$ demonstrates that there is 1 possibility of having 3 boys, 3 possibilities of having 2 boys and 1 girl (BBG, BGB, GBB), and so on.
$$\text{Required probability}=\dfrac{\text{coefficient of}\: b^2g}{\text{sum of all coefficients}}=\dfrac{3}{8}$$
Example:

Conventional method
7 can only be obtained if we have 2, 2, 3 or 1, 3, 3.

Cases for 2, 2, 3:
2, 2, 3 --> 3*3*1
2, 3, 2 --> 3*1*3
3, 2, 2 --> 1*3*3

Cases for 1, 3, 3:
1, 3, 3 --> 2*1*1
3, 1, 3 --> 1*2*1
3, 3, 1 --> 1*1*2

So probability: $\dfrac{3(3\cdot3 + 2)}{6^3}=\dfrac{11}{72}$

Generating function method
The outcomes of a single die are given by the polynomial
and the outcomes of three dice rolls are given by .
Let .
Number of dice outcomes with a value of $7$ is the coefficient of $x^7$. $$\begin{align}f(x)&=(2x+3x^2+x^3)^3\\
&=\cdots+3(3\cdot 3+2)x^7+\cdots\\
&=\cdots+33x^7+\cdots\end{align}$$
[Here we are essentially doing the same thing as the conventional method, looking for the coefficient of $x^2x^2x^3$ and $xx^3x^3$. This generating function method can be useful to those who doesn't know the convention method.]
So the probability of getting a total of $7$ is $\dfrac{33}{6^3}=\dfrac{11}{72}$.

How to find the right function?
[Disclaimer: The followings are just my interpretations.]
For an event repeated for n times, each time with mutually exclusive outcomes a, b and c, the function will be $(a+b+c)^n$.
The coefficient of a particular term of the function which represents a particular outcome will be the number of possibilities of that outcome. The sum of all the coefficients of the function will be the total number of possibilities. Alternatively, you can find it by referring to the question. For example, for the dice question, we know the total number of possibilities is $6^3$ because we are rolling $3$ dice and there are $6$ possible outcomes in rolling each dice.

No comments:

Post a Comment