Generating functions and their applications

Find the generating functions of the following mass functions, and state where they converge. Hence calculate their means and variances.

Let $X( \geq 0)$ have probability generating function $G$ and write $t(n) = \mathbb {P}\left(X > n\right)$ for the 'tail' probabilities of $X$. Show that the generating function of the sequence $\left\{ t(n): n \geq 0\right\}$ is $T(s) = (1-G(s)) /(1-s)$. Show that $\mathbb {E}\left[X\right] = T(1)$ and $\operatorname {Var}\left[X\right] = 2 T^{\prime }(1)+T(1)-T(1)^{2}$.

Let $G_{X, Y}(s, t)$ be the joint probability generating function of $X$ and $Y$. Show that $G_{X}(s) = G_{X, Y}(s, 1)$ and $G_{Y}(t) = G_{X, Y}(1, t)$. Show that

Find the joint generating functions of the following joint mass functions, and state for what values of the variables the series converge.

A coin is tossed $n$ times, and heads turns up with probability $p$ on each toss. Assuming the usual independence, show that the joint probability generating function of the numbers $H$ and $T$ of heads and tails is $G_{H, T}(x, y) = \left\{ p x+(1-p) y\right\}^{n}$. Generalize this conclusion to find the joint probability generating function of the multinomial distribution of Exercise (3.5.1).

Let $X$ have the binomial distribution $\operatorname {bin}(n, U)$, where $U$ is uniform on $(0,1)$. Show that $X$ is uniformly distributed on $\left\{ 0,1,2, \ldots , n\right\}$.

Show that

is the joint generating function of four variables that are pairwise and triplewise independent, but are nevertheless not independent.

Let $p_{r} > 0$ and $a_{r} \in \mathbb {R}$ for $1 \leq r \leq n$. Which of the following is a moment generating function, and for what random variable?

Let $G_{1}$ and $G_{2}$ be probability generating functions, and suppose that $0 \leq \alpha \leq 1$. Show that $G_{1} G_{2}$, and $\alpha G_{1}+(1-\alpha ) G_{2}$ are probability generating functions. Is $G(\alpha s) / G(\alpha )$ necessarily a probability generating function?

Let $X_{1}, X_{2}, \ldots$ be independent, continuous random variables with common distribution function $F$, that are independent of the positive integer-valued random variable $Z$. Define the maximum $M = \max \left\{ X_{1}, X_{2}, \ldots , X_{Z}\right\}$. Show that

where $G$ is the probability generating function of $Z$.

Let $0 < p = 1-q < 1$, and let $X$ have the geometric mass function $f(x) = q^{x-1} p$ for $x = 1,2, \ldots$. Find the probability generating function of $Y = \min \left\{ n, X\right\}$ for fixed $n \geq 1$, and show that $\mathbb {E}\left[Y\right] = \left(1-q^{n}\right) / p$.

Let $X_{i}$ be the number of balls in the $i$th of a sequence of bins, and assume the $X_{i}$ are independent with common probability generating function $G_{X}$. There are $N$ such bins, where $N$ is independent of the $X_{i}$ with probability generating function $G_{N}$. Each ball is 'unmarked' with probability $u$, and marked otherwise, with marks appearing independently.

Let $X$ be the number of events in the sequence $A_{1}, A_{2}, \ldots , A_{n}$ which occur. Let $S_{m} = \mathbb {E}\left[\binom {X}{m}\right]$, the mean value of the random binomial coefficient $\binom {X}{m}$, and show that

Each person in a group of $n$ people chooses another at random. Find the probability:

Let $X$ have the binomial distribution with parameters $n$ and $p$, and show that

Find the limit of this expression as $n \rightarrow \infty$ and $p \rightarrow 0$, the limit being taken in such a way that $n p \rightarrow \lambda$ where $0 < \lambda < \infty$. Comment.

A coin is tossed repeatedly, and heads turns up with probability $p$ on each toss. Let $h_{n}$ be the probability of an even number of heads in the first $n$ tosses, with the convention that 0 is an even number. Find a difference equation for the $h_{n}$ and deduce that they have generating function $\frac{1}{2}\left\{ (1+2 p s-s)^{-1}+(1-s)^{-1}\right\}$.

An unfair coin is flipped repeatedly, where $\mathbb {P}\left(\mathrm{H}\right) = p = 1-q$. Let $X$ be the number of flips until HTH first appears, and $Y$ the number of flips until either HTH or THT appears. Show that $\mathbb {E}\left[s^{X}\right] = \left(p^{2} q s^{3}\right) /\left(1-s+p q s^{2}-p q^{2} s^{3}\right)$ and find $\mathbb {E}\left[s^{Y}\right]$.

The pile of (by now dog-eared) letters is dropped again and enveloped at random, yielding $X_{n}$ matches. Show that $\mathbb {P}\left(X_{n} = j\right) = (j+1) \mathbb {P}\left(X_{n+1} = j+1\right)$. Deduce that the derivatives of the $G_{n}(s) = \mathbb {E}\left[s^{X_{n}}\right]$ satisfy $G_{n+1}^{\prime } = G_{n}$, and hence derive the conclusion of Example (3.4.3), namely:

Let $X$ have a Poisson distribution with parameter $\Lambda$, where $\Lambda$ is exponential with parameter $\mu$. Show that $X$ has a geometric distribution.

Recall from Exercise (3.3.2) that each packet of an overpriced commodity contains a worthless plastic object. There are four types of object, and each packet is equally likely to contain any of the four. Let $T$ be the number of packets you open until you first have the complete set. Find $\mathbb {E}\left[s^{T}\right]$ and $\mathbb {P}\left(T = k\right)$.

A library permits a reader to hold at most $m$ books at any one time. Your holding before a visit is $B$ books, having the binomial $\operatorname {bin}(m, p)$ distribution. On each visit, a held book is retained with probability $r$, and returned otherwise; given the number $R$ of retained books, you borrow a further $N$ books with the $\operatorname {bin}(m-R, \alpha )$ distribution. Assuming the usual independence, find the distribution of the number $A = R+N$ of books held after a visit. Show that, after a large number of visits, the number of books held has approximately the $\operatorname {bin}(m, s)$ distribution where $s = \alpha /[1-r(1-\alpha )]$. You may assume that $0 < \alpha , p, r < 1$.

Matching yet again, Exercise (5.2.7) revisited. Each envelope is addressed correctly with probability $t$, and incorrectly otherwise (assume the usual independence). It is decided that an incorrectly addressed envelope cannot count as a match even when containing the correct letter. Show that the number $Y_{n}$ of correctly addressed matches satisfies

Note the Poisson limit distribution.

A random variable is called simple if it may take only finitely many values. Show that a simple random variable $X$ may be simulated using a finite sequence of Bernoulli random variables, in the sense that there exist independent Bernoulli random variables $\left\{ B_{j}: j = 1,2, \ldots , m\right\}$ with respective parameters $b_{j}$, and real numbers $\left\{ r_{j}\right\}$, such that $Y = \sum_{j} r_{j} B_{j}$ has the same distribution as $X$.

For a simple random walk $S$ with $S_{0} = 0$ and $p = 1-q < \frac{1}{2}$, show that the maximum $M = \max \left\{ S_{n}: n \geq 0\right\}$ satisfies $\mathbb {P}\left(M \geq r\right) = (p / q)^{r}$ for $r \geq 0$.

Use generating functions to show that, for a symmetric random walk,

A particle performs a random walk on the corners of the square $A B C D$. At each step, the probability of moving from corner $c$ to corner $d$ equals $\rho_{c d}$, where

and $\alpha , \beta > 0, \alpha +\beta = 1$. Let $G_{\mathrm{A}}(s)$ be the generating function of the sequence $\left(p_{\mathrm{AA}}(n): n \geq 0\right)$, where $p_{\mathrm{AA}}(n)$ is the probability that the particle is at A after $n$ steps, having started at A. Show that

Hence find the probability generating function of the time of the first return to A.

A particle performs a symmetric random walk in two dimensions starting at the origin: each step is of unit length and has equal probability $\frac{1}{4}$ of being northwards, southwards, eastwards, or westwards. The particle first reaches the line $x+y = m$ at the point $(X, Y)$ and at the time $T$. Find the probability generating functions of $T$ and $X-Y$, and state where they converge.

Derive the arc sine law for sojourn times, Theorem (3.10.21), using generating functions. That is to say, let $L_{2 n}$ be the length of time spent (up to time $2 n$) by a simple symmetric random walk to the right of its starting point. Show that

Let $\left\{ S_{n}: n \geq 0\right\}$ be a simple symmetric random walk with $S_{0} = 0$, and let $T = \min \left\{ n > 0 : S_{n} = 0\right\}$. Show that

Let $S_{n} = \sum_{r = 0}^{n} X_{r}$ be a left-continuous random walk on the integers with a retaining barrier at zero. More specifically, we assume that the $X_{r}$ are identically distributed integer-valued random variables with $X_{1} \geq -1, \mathbb {P}\left(X_{1} = 0\right) \neq 0$, and

Show that the distribution of $S_{0}$ may be chosen in such a way that $\mathbb {E}\left[z^{S_{n}}\right] = \mathbb {E}\left[z^{S_{0}}\right]$ for all $n$, if and only if $\mathbb {E}\left[X_{1}\right] < 0$, and in this case

Consider a simple random walk starting at 0 in which each step is to the right with probability $p( = 1-q)$. Let $T_{b}$ be the number of steps until the walk first reaches $b$ where $b > 0$. Show that $\mathbb {E}\left[T_{b} \mid T_{b} < \infty \right] = b /\left|p-q\right|$.

Let $S = \left\{ S_{k}: k = 0,1,2, \ldots \right\}$ be a simple random walk on the non-negative integers, with $S_{0} = i$ and an absorbing barrier at 0. A typical jump $X$ has mass function $\mathbb {P}\left(X = 1\right) = p$ and $\mathbb {P}\left(X = -1\right) = q = 1-p$, where $p \in \left(\frac{1}{2}, 1\right)$. Let $H$ be the event that the walk is ultimately absorbed at 0. Show that, conditional on $H$, the walk has the same distribution as a simple random walk $W = \left\{ W_{k}: k = 0,1,2, \ldots \right\}$ for which a typical jump $Y$ satisfies $\mathbb {P}\left(Y = 1\right) = q$, $\mathbb {P}\left(Y = -1\right) = p$.

Let $Z_{n}$ be the size of the $n$th generation in an ordinary branching process with $Z_{0} = 1, \mathbb {E}\left[Z_{1}\right] = \mu$, and $\operatorname {Var}\left[Z_{1}\right] > 0$. Show that $\mathbb {E}\left[Z_{n} Z_{m}\right] = \mu^{n-m} \mathbb {E}\left[Z_{m}^{2}\right]$ for $m \leq n$. Hence find the correlation coefficient $\rho \left(Z_{m}, Z_{n}\right)$ in terms of $\mu$.

Consider a branching process with generation sizes $Z_{n}$ satisfying $Z_{0} = 1$ and $\mathbb {P}\left(Z_{1} = 0\right) = 0$. Pick two individuals at random (with replacement) from the $n$th generation and let $L$ be the index of the generation which contains their most recent common ancestor. Show that $\mathbb {P}\left(L \geq r\right) \geq \mathbb {E}\left[Z_{r}^{-1}\right]$ for $0 \leq r < n$. Show when $r \neq 0$ that equality holds if and only if $Z_{1}$ is a.s. constant. What can be said if $\mathbb {P}\left(Z_{1} = 0\right) > 0$?

Consider a branching process whose family sizes have the geometric mass function $f(k) = q p^{k}$, $k \geq 0$, where $p+q = 1$, and let $Z_{n}$ be the size of the $n$th generation. Let $T = \min \left\{ n: Z_{n} = 0\right\}$ be the extinction time, and suppose that $Z_{0} = 1$. Find $\mathbb {P}\left(T = n\right)$. For what values of $p$ is it the case that $\mathbb {E}\left[T\right] < \infty$?

Let $Z_{n}$ be the size of the $n$th generation of a branching process, and assume $Z_{0} = 1$. Find an expression for the generating function $G_{n}$ of $Z_{n}$, in the cases when $Z_{1}$ has generating function:

Each generation of a branching process (with a single progenitor) is augmented by a random number of immigrants who are indistinguishable from the other members of the population. Suppose that the numbers of immigrants in different generations are independent of each other and of the past history of the branching process, each such number having probability generating function $H(s)$. Show that the probability generating function $G_{n}$ of the size of the $n$th generation satisfies $G_{n+1}(s) = G_{n}(G(s)) H(s)$, where $G$ is the probability generating function of a typical family of offspring.

Let $Z_{n}$ be the size of the $n$th generation in a branching process with $\mathbb {E}\left[s^{Z_{1}}\right] = (2-s)^{-1}$ and $Z_{0} = 1$. Let $V_{r}$ be the total number of generations of size $r$. Show that $\mathbb {E}\left[V_{1}\right] = \frac{1}{6} \pi^{2}$, and $\mathbb {E}\left[2 V_{2}-V_{3}\right] = \frac{1}{6} \pi^{2}-\frac{1}{90} \pi^{4}$.

Let $T$ be the total number of individuals in a branching process with family-size distribution $\operatorname {bin}(2, p)$, where $p \neq \frac{1}{2}$. Show that

What is the family-size distribution conditional on $T < \infty$?

Let $Z$ be a branching process with $Z_{0} = 1, \mathbb {E}\left[Z_{1}\right] = \mu > 1$, and $\operatorname {Var}\left[Z_{1}\right] = \sigma^{2}$. Use the Paley-Zygmund inequality to show that the extinction probability $\eta_{n} = \mathbb {P}\left(Z_{n} = 0\right)$ satisfies

Let $Z(t)$ be the population-size at time $t$ in an age-dependent branching process, the lifetime distribution of which is exponential with parameter $\lambda$. If $Z(0) = 1$, show that the probability generating function $G_{t}(s)$ of $Z(t)$ satisfies

where $G$ is the probability generating function of a typical family-size. Show in the case of 'exponential binary fission', when $G(s) = s^{2}$, that

and hence derive the probability mass function of the population size $Z(t)$ at time $t$.

Solve the differential equation of Exercise (5.5.1) when $\lambda = 1$ and $G(s) = \frac{1}{2}\left(1+s^{2}\right)$, to obtain

Hence find $\mathbb {P}\left(Z(t) \geq k\right)$, and deduce that

Let $X_{1}, X_{2}, \ldots$ be random variables satisfying $\mathbb {E}\left[\sum_{i = 1}^{\infty }\left|X_{i}\right|\right] < \infty$. Show that

Let $\left\{ X_{n}\right\}$ be a sequence of random variables satisfying $X_{n} \leq Y$ a.s. for some $Y$ with $\mathbb {E}\left[\left|Y\right|\right] < \infty$. Show that

Suppose that $\mathbb {E}\left[\left|X^{r}\right|\right] < \infty$ where $r > 0$. Deduce that $x^{r} \mathbb {P}\left(\left|X\right| \geq x\right) \rightarrow 0$ as $x \rightarrow \infty$. Conversely, suppose that $x^{r} \mathbb {P}\left(\left|X\right| \geq x\right) \rightarrow 0$ as $x \rightarrow \infty$ where $r \geq 0$, and show that $\mathbb {E}\left[\left|X^{s}\right|\right] < \infty$ for $0 \leq s < r$.

Show that $\mathbb {E}\left[\left|X\right|\right] < \infty$ if and only if the following holds: for all $\epsilon > 0$, there exists $\delta > 0$, such that $\mathbb {E}\left[\left|X\right| I_{A}\right] < \epsilon$ for all $A$ such that $\mathbb {P}\left(A\right) < \delta$.

Let $M = \max \left\{ X, Y\right\}$ where $X, Y$ have some joint distribution. Show that $\operatorname {Var}\left[M\right] \leq \operatorname {Var}\left[X\right]+ \operatorname {Var}\left[Y\right]$.

Let $A_{1}, A_{2}, \ldots , A_{n}$ be events, and let $S$ be the number of them which occur. Show that

where $I_{r}$ is the indicator function of $A_{r}$.

Find two dependent random variables $X$ and $Y$ such that $\phi_{X+Y}(t) = \phi_{X}(t) \phi_{Y}(t)$ for all $t$.

If $\phi$ is a characteristic function, show that $\operatorname {Re}\left\{ 1-\phi (t)\right\} \geq \frac{1}{4} \operatorname {Re}\left\{ 1-\phi (2 t)\right\}$, and deduce that $1-\left|\phi (2 t)\right| \leq 8\left\{ 1-\left|\phi (t)\right|\right\}$.

The cumulant generating function $K_{X}(\theta )$ of the random variable $X$ is defined by $K_{X}(\theta ) = \log \mathbb {E}\left[e^{\theta X}\right]$, the logarithm of the moment generating function of $X$. If the latter is finite in a neighbourhood of the origin, then $K_{X}$ has a convergent Taylor expansion:

and $k_{n}(X)$ is called the $n$th cumulant (or semi-invariant) of $X$.

Let $X$ be $N(0,1)$, and show that the cumulants of $X$ are $k_{2}(X) = 1, k_{m}(X) = 0$ for $m \neq 2$.

The random variable $X$ is said to have a lattice distribution if there exist $a$ and $b$ such that $X$ takes values in the set $L(a, b) = \left\{ a+b m: m = 0, \pm 1, \ldots \right\}$. The span of such a variable $X$ is the maximal value of $b$ for which there exists $a$ such that $X$ takes values in $L(a, b)$.

Let $X$ be a random variable with density function $f$. Show that $\left|\phi_{X}(t)\right| \rightarrow 0$ as $t \rightarrow \pm \infty$.

Let $X_{1}, X_{2}, \ldots , X_{n}$ be independent variables, $X_{i}$ being $N\left(\mu_{i}, 1\right)$, and let $Y = X_{1}^{2}+X_{2}^{2}+\cdots +X_{n}^{2}$. Show that the characteristic function of $Y$ is

where $\theta = \mu_{1}^{2}+\mu_{2}^{2}+\cdots +\mu_{n}^{2}$. The random variables $Y$ is said to have the non-central chi-squared distribution with $n$ degrees of freedom and non-centrality parameter $\theta$, written $\chi^{2}(n ; \theta )$.

Let $X$ be $N(\mu , 1)$ and let $Y$ be $\chi^{2}(n)$, and suppose that $X$ and $Y$ are independent. The random variable $T = X / \sqrt{Y / n}$ is said to have the non-central $t$-distribution with $n$ degrees of freedom and non-centrality parameter $\mu$. If $U$ and $V$ are independent, $U$ being $\chi^{2}(m ; \theta )$ and $V$ being $\chi^{2}(n)$, then $F = (U / m) /(V / n)$ is said to have the non-central $F$-distribution with $m$ and $n$ degrees of freedom and non-centrality parameter $\theta$, written $F(m, n ; \theta )$.