1. (a) If $X$ is a constant random variable, say $\mathbb P(X=a)=1$ for some $a∈\mathbb N$, what is its probability generating function?
   (b) If $Y$ has probability generating function $G_Y(s)$, and $m,n$ are positive integers, what is the probability generating function of $Z=mY+n$?
   Solution.
   (a) $G_X(s)=s^a$.
   (b) $s^nG_Y(s^m)$.
2. (a) Suppose that we perform a sequence of independent trials, each of which has probability $p$ of success. Let $Y$ be the number of trials up to and including the $m$th success, where $m≥1$ is fixed. Explain why$$\mathbb{P}(Y=k)=\left(\begin{array}{c}k-1 \\ m-1\end{array}\right) p^{m}(1-p)^{k-m}, \quad k=m, m+1, \ldots$$(This is called the negative binomial distribution.)
   (b) By expressing $Y$ as a sum of $m$ independent random variables, find its probability generating function.
   Solution.
   (a) Because the outcomes of the $k$ trials are supposed to happen independently, the probability for every specific sequence of $m$ successes and $k-m$ failures is $p^{m}(1-p)^{k-m}$. Since the last trial is successful, it remains to choose the $m-1$ successful trials out of the remaining $k-1$ trials.
   (b) $Y=\sum_{i=1}^mY_i,Y_i\sim$Geom($p$), so $G_Y(s)=\left(ps\over1-(1-p)s\right)^m$.
3. Let $X_1,X_2,\cdots$ be a sequence of independent and identically distributed non-negative integer valued random variables, and let $N$ be a non-negative integer valued random variable which is independent of the sequence $X_1,X_2,…$
   Let $Z=X_1+…+X_N$ (where we take $Z=0$ if $N=0$).
   (a) Show that $\mathbb E[Z]=\mathbb E[N]\mathbb E[X_1]$ and $\operatorname{var}(Z)=\operatorname{var}(N)\mathbb E[X_1]^2+\mathbb E[N]\operatorname{var}(X_1)$.
   (b) If $N$∼Po($λ$) and $X_1\sim$Ber($p$), find $\operatorname{var}(Z)$.
   (c) Suppose we remove the condition that $N$ is independent of the sequence $(X_i)$. Is it still necessarily the case that $\mathbb E[Z]=\mathbb E[N]\mathbb E[X_1]$? Find a proof or a counterexample.
   Solution.
   (a)$\mathbb{E}\left[X_{1}+\cdots+X_{N}\right]=\sum_{n=1}^{\infty} \mathbb{E}\left[X_{1}+\cdots+X_{N} \mid N=n\right] \mathbb{P}(N=n)\xlongequal{\text{by independence}}\sum_{n=1}^{\infty} \mathbb{E}\left[X_{1}+\cdots+X_{n}\right] \mathbb{P}(N=n)=\mathbb{E}\left[X_{1}\right] \sum_{n=1}^{\infty} n \mathbb{P}(N=n)=\mathbb{E}\left[X_{1}\right] \mathbb{E}[N]$
   By independence of $X_i$, $\Bbb E[X_iX_j]=\Bbb E[X_i]\Bbb E[X_j]=\Bbb E[X_1]^2$. Apply part (a) to $X_i^2$ we have $\mathbb E[X_1^2+\cdots+X_N^2]=\mathbb E[N]\mathbb E[X_1^2]$⇒$\operatorname{var}(Z)=\mathbb E[(X_1+…+X_N)^2]-\mathbb E[X_1+…+X_N]^2=\mathbb E[N]\mathbb E[X_1^2]+(\mathbb E[N^2]-\mathbb E[N])\Bbb E[X_1]^2-\mathbb E[N]^2\mathbb E[X_1]^2=(\mathbb E[N^2]-\mathbb E[N]^2)\mathbb E[X_1]^2+\mathbb E[N](\mathbb E[X_1^2]-\mathbb E[X_1]^2)=\operatorname{var}(N)(\mathbb E[X_1])^2+\mathbb E[N]\operatorname{var}(X_1)$
   (b) $\operatorname{var}(Z)=λ\cdot p^2+λp(1-p)=λp$.
   (c) Counterexample: Let $X_1, X_2, X_3, . . .\stackrel{\rm i.i.d.}{\ \sim}$Bernoulli(1/2), and let $N$ be the smallest non-negative integer $n$ such that $X_{n+1}=1$, that is, $N :=\min\{n ∈\mathbb N : X_{n+1}=1\}$. Also, we define the random $X_1 + · · · + X_N$ to be 0 when $N=0$. Then, $\mathbb E[X_1] = 1/2$ and since $N$ is a shifted geometric random variable, i.e., $N+1$∼Geom(1/2), we can also compute $\mathbb E[N]=1$.
   Thus, we have $\mathbb E[X_1]\mathbb E[N] = 1/2$, but the random sum $X_1 + · · · + X_N$ is always 0. This is because $X_{N+1}$ is the first of the random variables which is non-zero, by the definition of $N$.
4. A random variable $X$ has probability generating function $G_X$. Let $\omega$ the $n$-th primitive root of unity, then $\displaystyle\mathbb P(n\text{ divides }X)=\frac1n\sum_{i=0}^{n-1}G_X(\omega^i)$.
   Proof.
   For $k=0,1,2,\cdots$, we need to prove the coefficient of $k$-th degree term of $\sum_{i=0}^{n-1}G_X(\omega^i)$ is $n$ if $n\mid k$; 0 if $n\nmid k$.
   Let $s_k=1+\omega^k+\dots+\omega^{(n-1)k}$. If $n$ divides $k$, then $\omega^k=1$ and so $s_k=1+1+1\dots+1=n$ otherwise by the definition of primitive root of unity, $\omega^k≠1$, so $s_k=\frac{1-\omega^{nk}}{1-\omega^k}=0$.
5. A population of cells is grown on a petri dish. Once a minute, each cell tries to reproduce by splitting in two. This is successful with probability 1/4; with probability 1/12, the cell dies instead; and with the remaining probability 2/3, nothing happens. Assume that different cells behave independently and that we begin with a single cell. What is the probability generating function $G(s)$ of the number of cells on the dish after 1 minute? How about after 2 minutes? What is the probability that after 2 minutes the population has died out?
   Solution.
   $G(s)=\frac1{12}+\frac23s+\frac14s^2$. $G(G(s))=\frac{1}{576} \left(9 x^4+48 x^3+166 x^2+272 x+81\right)$. The probability that after 2 minutes the population has died out is $G(G(0))=\frac9{64}$.
6. Consider a branching process in which each individual has 2 offspring with probability $p$, and 0 offspring with probability $1-p$. Let $X_n$ be the size of the $n$th generation, with $X_0=1$.
   (a) Write down the mean $µ$ of the offspring distribution, and its probability generating function $G(s)$.
   (b) Find the probability that the process eventually dies out. [Recall that this probability is the smallest non-negative solution of the equation $s=G(s)$.] Verify that the probability that the process survives for ever is positive if and only if $µ>1$.
   (c) Let $β_n=\mathbb P(X_n>0)$, the probability the process survives for at least $n$ generations. Write down $G(s)$ in the case $p=1/2$. Deduce that in that case, $\beta_{n}=\beta_{n-1}-\beta_{n-1}^{2} / 2$ and use induction to prove that, for all $n$, $\frac{1}{n+1} \leq \beta_{n} \leq \frac{2}{n+2}$
   (d) In lectures we considered a simple random walk, which at each step goes up with probability $p$ and down with probability $1-p$. Suppose the walk starts from site 1. By taking limits in the gambler’s ruin model, we showed that the probability that the walk ever hits site 0 equals 1 for $p≤1/2$, and $(1-p)/p$ for $p>1/2$. Compare this probability to your answer in part (b). Can you find a link between the branching process and the random walk? [Hint: if I take an individual in the branching process and replace it by its children (if any), what happens to the size of the population?]
   Solution.
   (a) $G(s)=1-p+ps^2$. $μ=G'(1)=2p$.
   (b) The solutions of $G(s)=s$ are $s=1,s=\frac{1-p}p$. If $p>\frac12$, we have $\frac{1-p}p\lt1$, so the probability that the process eventually dies out is $\frac{1-p}p$; if $p≤\frac12$, the probability that the process eventually dies out is 1.
   (c) In the case $p=\frac12$, $G(s)=\frac12(1+s^2)$. $1-\beta_n=\mathbb P(X_n=0)=G^{\circ n}(0)$⇒$\beta_{n}=1-G(1-\beta_{n-1})=\beta_{n-1}-\frac12\beta_{n-1}^{2}$.
   For $n=1$ we have $\frac1{1+1}\leq\frac12\leq\frac2{1+2}$. Assume $\frac{1}{n+1} \leq \beta_{n} \leq \frac{2}{n+2}$, because $f(x)=x-\frac12x^2(0<x<1)$ is increasing function of $x$, we have $\frac{2 n+1}{2 (n+1)^2}=f\left(\frac1{n+1}\right)\leq β_{n+1}=f(β_n)\leq f\left(\frac2{n+2}\right)=\frac{2(n+1)}{(n+2)^2}$, and $\frac{2 n+1}{2 (n+1)^2}-\frac1{n+2}=\frac{n}{2 (n+1)^2 (n+2)}>0$, $\frac{2(n+1)}{(n+2)^2}-\frac2{n+3}=-\frac{2}{(n+2)^2 (n+3)}<0$, ∴the inequality is true for $n+1$, by induction, it is true for all $n\in\mathbb N$.
   (d) Each time, the population increases 1 or decreases 1, so it is equivalent to a random walk.