\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

Explain what a branching chain is.  Suppose a population is
descended from a single individual (generation 0).  Let $A(s)$
denote the probability generating function for the number of
offspring of any individual.  Let $F_n(s)$ denote the probability
generating function for the number of individuals in generation n.

${}$

Prove that \begin{eqnarray*} F_n(s) & = & F_{n-1}(A(s))
\hspace{.2in}{\rm and\ dedcue\ that} \\ F_n(s) & = &
A(F_{n-1}(s)).\end{eqnarray*}

${}$

A game is played with coins as follows.  Each coin has a
probability $\ds \frac{2}{3}$ of showing a head when tossed.
Player A starts with one coin.  This is given to player B, who
takes it and tosses it until the first head is obtained.  If the
number of tosses needed {\underline {before}} the first head is
obtained is k, then k coins are given to player A.  For the next
stage of the game all the coins held by player A are given to
player B, who takes each one and tosses it until a head is
obtained, independently of the other coins.  Again if the number
of tosses needed before the first head shows for any particular
coin is k, then k coins are given to player A, who therefore
finishes this stage of the game with a certain number of coins.
This process is repeated for all subsequent stages of the game.

${}$

Write down the probability that k tosses occur before the fist
head.  Use this to show that the probability generating function
$A(s)$ for the number if tosses needed before the first heads is
$\ds \frac{2}{3-s}.$  Use the relation deduced above to show, by
induction or otherwise, that the probability generating function
for the total number of coins held by player A after n stages of
the game is given by $$F_n(s) =
\frac{2[2^n-1-(2^{n-1}-1)s]}{2^{n+1} - 1 - (2^n-1)s}$$ Show that
this game terminates with probability 1.



\vspace{.25in}

{\bf Answer}

Suppose we have a population of individuals, each reproducing
independently of the others,Suppose the distributions of the
number of offspring of all individuals are identical.  Let $X_n$
denote the number of individuals in generation n.  Then $(X_n)$ is
a branching Markov chain.

Suppose $P(Z+k) = a_k$ and $\ds A(s) = \sum_{k=0}^\infty a_ks^k$

Now $P(X_n = l| X_{n-1} = j)= P(Z_1 + ...+Z_j = l)$

= coefficient of $s^l$ in $[A(s)]$ as the $Z_i$'s are i.i.d.

So \begin{eqnarray*} P(X_n=l) & = & \sum_{j=0}^\infty
P(X_n=l|X_{n-1} = j)\\ F_n(s) & = & \sum_{l=0}^\infty
\sum_{j=0}^\infty ({\rm coeff\ of\ }s^k {\rm \ in\
}[A(s)]^j)P(X_{n-1} = j)s^l \\ & = & \sum_{j=0}^\infty \left(
\sum_{k=0}^\infty ({\rm coeff\ of\ }s^k {\rm \ in\
}[A(s)]^j)s^l\right)P(X_{n-1}=j) \\ & = & \sum_{j=0}^\infty
P(X_{n-1}=j)[A(s)]^j \\ & = & F_{n-1}(A(s)) \end{eqnarray*}

Now $P(X_0=1)=1$ so $F_0(s) =s$.  Thus $F_1(s) = F_0(A(s)) = A(s)$

$F_2(s) = F_1(A(s)) = A(A(s))$

$F_n(s) = \underbrace{A(A(A(.....}(s))...)) = A(F_{n-1}(s))$

\hspace{0.75in} n times

${}$

The game is a branching Markov chain.  Let $X$ denote the number
of tosses before the first head.  Then we have

$\ds P(X=k) = \left(\frac{1}{3}\right)^k\cdot \frac{2}{3}
\hspace{.2in} k = 0, 1, ...$

So $\ds A(s) = \sum \left(\frac{1}{3}\right)^k \cdot
\frac{2}{3}s^k = \frac{2}{3} \frac{1}{1-\frac{s}{3}} =
\frac{2}{3-s}$

Now for n=1 $F_1(s) = A(s)$ and the formula reduces to
$\frac{2}{3-s}.$

Assume the formula is correct for n.

Then \begin{eqnarray*} F_{n+1}(s) & = & A(F_n(s)) \\ & = &
\frac{2}{3-F_n(s)} \\ & = & \frac{2}{\left\{3 - \ds \frac{2[2^n -
1 - (2^{n-1}-1)s]}{2^{n+1}-1-(2^n-1)s}\right\}} \\ & = &
\frac{2\cdot[2^{n+1} - 1 - (2^n-1)s]}{2^{n+2} - 1 - (2^{n+1}-1)s}
\\ & & \hspace{.2in} {\rm after\ apporx\ 3\ lines\ of\ algebra}
\end{eqnarray*}

Hence the result, by induction.

The probability that the game terminates is the smallest positive
root of $s=A(s)$.  So $\ds s = \frac{2}{3-s} ,\, \, \, \, \, {\rm
i.e.\ }s^2 - 3s + 2 = 0,$ giving $\ds (s-1)(s-2) = 0$.  s=1 is the
smallest root, so the game terminates with probability 1.



\end{document}