IA Probability Lent 2007

3. DISCRETE RANDOM VARIABLES

3.1 Introduction

When an experiment is conducted there may be a number of quantities associated with the outcome ω ∈ Ω that may be of interest. Suppose that the experiment is choosing a male student at random from the audience of the IA Probability lecture – there are many different measurements, or attributes, of the person chosen that may be of interest: his height, his weight, his IQ, the colour of his eyes, etc. Rather than think of each of these as the outcome of a separate experiment it is more useful to view them as functions of the outcome ω. This leads to the following definition which is a central notion of probability. Definition A random variable X, taking values in a set S, is a function X : Ω → S.

Typically, S may be a subset of the real numbers, ℝ, as would be the case if the height of the student was of interest; or it could be a subset of ℝ^{k}, if more than one measurement is made on the subject as would be the case, with k = 2, if height and weight are measured; or, S could be some arbitrary set such as S = {Blue, Green, Brown}, say, if it is the colour of the subject’s eyes that are to be recorded. The most frequent situation that we will encounter is the case when S ⊆ ℝ, and X is then said to be a real-valued random variable. Denote by Ω_{X} the range of X, so that Ω_{X} = {X(ω) : ω ∈ Ω}. In this chapter we will assume that the sample space Ω is either a finite or a countable set, so that Ω_{X} is finite or countable.

For T ⊆ S, we denote the event {ω : X(ω) ∈ T } as {X ∈ T }, so that the dependence of X on ω is suppressed in the notation. Suppose that we enumerate the points in Ω_{X} (equivalently the values taken on by X), so that Ω_{X} = {x_{j} : j ∈ J}, then we write the event {ω : X(ω) = x_{j}} = {X = x_{j}}. If we let p_{j} = ℙ (X = x_{j}), j ∈ J, then {p_{j} : j ∈ J} is a probability distribution on the space Ω_{X}, and is referred to as the probability distribution of the random variable X. Note that it is a probability distribution on the set Ω_{X}, not on the underlying sample space Ω.

Example 3.1 Suppose that two standard dice are rolled so that the sample space is Ω = {(i, j) : 1 ⩽ i, j ⩽ 6}, and we are interested in the sum of the numbers shown so that the random variable X : Ω → ℝ is given by X(i, j) = i + j. The probability of each point in Ω is \frac{1}{36} with the set of possible values taken on by X being Ω_{X} = \{2, 3, …, 12\} and, for example,

ℙ (X = 6) = ℙ (\{(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)\}) = \frac{5}{36}.

If we set p_{j} = ℙ (X = j), for j = 2, …, 12, then the table

\begin{matrix}j & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ p_{j} & \frac{1}{36} & \frac{2}{36} & \frac{3}{36} & \frac{4}{36} & \frac{5}{36} & \frac{6}{36} & \frac{5}{36} & \frac{4}{36} & \frac{3}{36} & \frac{2}{36} & \frac{1}{36} \end{matrix}

gives the full probability distribution of the random variable X. □

Terminology If the probability distribution of X is a standard distribution such as the binomial distribution (or Poisson, or geometric), we say that X is a binomial (respectively, Poisson, or geometric) random variable. We often write X ∼ Bin (n, p), for example, for the statement that X is binomial distribution where the parameters are n and p, or X ∼ Poiss(λ) for a Poisson random variable with parameter λ..

Example 3.2 Suppose that a coin is tossed n times and a 1 is recorded whenever a head occurs and a 0 is recorded for each tail. Then Ω = {(i_{1}, i_{2}, …, i_{n}) : i_{j} = 1 or 0}. If p is the probability of a head and tosses are independent then the probability on Ω is specified by

ℙ (i_{1}, i_{2}, …, i_{n}) = p^{i_{1}+···+i_{n}}(1 − p)^{n−i_{1}−···−i_{n}}.

Let X denote the number of heads obtained, so that X(i_{1}, …, i_{n}) = i_{1} + ⋯ + i_{n}, then X is a binomial random variable since the distribution of X is given by

ℙ (X = k) = \binom{n}{k}p^{k}(1 − p)^{n−k}, for 0 ⩽ k ⩽ n.  □

For a function g : S → T, mapping from the set S to the set T, then if X is a random variable taking values in S, g(X) is the random variable taking values in T, with g(X) : Ω → T specified by g(X)(ω) = g(X(ω)). For subsets C ⊆ T we have ℙ (g(X) ∈ C) = ℙ (X ∈ g^{−1}(C)) and the distribution of g(X) may be obtained from that of X by observing that

ℙ (g(X) = y) = ℙ (X ∈ g^{−1}(y)) = ∑_{x∈g^{−1}(y)} ℙ (X = x) .

A real-valued random variable which takes on just the two values 0 and 1 is known as an indicator random variable; suppose that the event on which it takes the value 1 is A ⊆ Ω then the random variable is denoted by I_{A}, so that

I_{A}(ω) = \{ \begin{matrix}1 & for ω ∈ A, \\ 0 & for ω ∉ A, \end{matrix}

and I_{A} is 1 or 0 according as the event A occurs or does not occur. The following properties of indicator random variables should be noted for events A and B:

1. I_{A^{c}} = 1 − I_{A}.

2. I_{A∩B} = I_{A}I_{B}.
3. I_{A∪B} = 1 − (1 − I_{A}) (1 − I_{B}).

and, for events A_{1}, A_{2}, …, A_{n}, Properties 2 and 3 generalize to I_{A_{1}∩A_{2}∩···∩A_{n}} = ∏_{1}^{n} I_{A_{i}}, and

I_{A_{1}∪A_{2}∪···∪A_{n}} = 1 − ∏_{1}^{n} (1 − I_{A_{i}})

= ∑_{i} I_{A_{i}} − ∑_{i_{1}<i_{2}} I_{A_{i_{1}}} I_{A_{i_{2}}} + ∑_{i_{1}<i_{2}<i_{3}} I_{A_{i_{1}}} I_{A_{i_{2}}} I_{A_{i_{3}}} − ⋯ + (−1)^{n−1}I_{A_{1}} ⋯ I_{A_{n}}

= ∑_{i} I_{A_{i}} − ∑_{i_{1}<i_{2}} I_{A_{i_{1}} ∩A_{i_{2}}} + ∑_{i_{1}<i_{2}<i_{3}} I_{A_{i_{1}} ∩A_{i_{2}} ∩A_{i_{3}}} − ⋯ + (−1)^{n−1}I_{A_{1}∩···∩A_{n}}.

In the next section we see how this last relation provides an alternate proof of the inclusionexclusion formula.

3.2 Expectation, variance and covariance

From now on, unless we indicate to the contrary, the random variables we will consider will take real values. For a non-negative random variable X, that is one for which X(ω) ⩾ 0 for all ω ∈ Ω, (usually just written as X ⩾ 0),we define the expectation (or expected value or mean value) of X to be

𝔼 X = ∑_{ω∈Ω} X(ω)ℙ({ω});

since all the terms in the sum are non-negative the sum is well defined (although it may take the value +∞). Note that, since Ω = ⋃_{x∈Ω_{X}} {X = x}, we have a more useful form for the expectation given by

𝔼 X = ∑_{ω∈Ω} X(ω)ℙ({ω}) = ∑_{x∈Ω_{X}} ∑_{ω∈{X=x}} X(ω)ℙ({ω}) = ∑_{x∈Ω_{X}} xℙ (X = x) .

Thus the expectation is the average of the values taken on by the random variable, averaged with weights corresponding to the probabilities of the values.

Example 3.3 Suppose that X ∼ Bin(n, p), so that ℙ (X = k) = \binom{n}{k}p^{k}(1 − p)^{n−k}, for 0 ⩽ k ⩽ n, then

𝔼 X = ∑_{k=0}^{n} k\binom{n}{k}p^{k}(1 − p)^{n−k} = p ∑_{k=1}^{n} \frac{n!}{(n − k)!(k − 1)!}p^{k−1}(1 − p)^{n−k}
= np ∑_{k=1}^{n} \binom{n − 1}{k − 1}p^{k−1}(1 − p)^{n−k} = np [p + (1 − p)]^{n−1} = np.  □

Example 3.4 Suppose that X ∼ Poiss(λ), so that ℙ(X = k) = e^{−λ} \frac{λ^{k}}{k!} , for k = 0, 1, 2, …, then

𝔼 X = ∑_{k=0}^{∞} ke^{−λ} \frac{λ^{k}}{k!} = λe^{−λ} ∑_{k=1}^{∞} \frac{λ^{k−1}}{(k − 1)!} = λe^{−λ}e^{λ} = λ.  □

For any random variable X denote by X_{+} = max(X, 0), the positive part of X, and X_{−} = max(−X, 0), the negative part of X are non-negative random variables, for which so that X = X_{+} − X_{−} and |X| = X_{+} + X_{−}. Provided not both 𝔼 X_{+} = ∞ and 𝔼 X_{−} = ∞, we define the expectation of X to be

𝔼 X = 𝔼 X_{+} − 𝔼 X_{−} = ∑_{x∈Ω_{X}} xℙ (X = x) ;

if both 𝔼 X_{+} and 𝔼 X_{−} are infinite then the expectation of X is not defined. In the following, when we write 𝔼 X for a random variable X, it may be assumed that the expectation of X is well defined. Properties of 𝔼 X

1. If X ⩾ 0, then 𝔼 X ⩾ 0, and 𝔼 X = 0 implies that ℙ(X = 0) = 1.

2. If c is a constant then 𝔼 (cX) = c𝔼 X, and 𝔼 c = c.

3. For random variables X and Y, 𝔼 (X + Y) = 𝔼 X + 𝔼 Y. Properties 2 and 3 show the important property that the operator 𝔼 (·) is a linear operator and they generalize, by induction, to the case of random variables X_{1}, …, X_{n} and constants

c_{1}, …, c_{n} so that 𝔼 (∑_{i=1}^{n} c_{i}X_{i}) = ∑_{i=1}^{n} c_{i}𝔼 X_{i}.

4. 𝔼 g(X) = ∑_{x∈Ω_{X}} g(x)ℙ(X = x).

To see this, let Y = g(X), then

𝔼 g(X) = 𝔼 Y = ∑_{y∈Ω_{Y}} yℙ (Y = y) = ∑_{y∈Ω_{Y}} y ( ∑_{x∈g^{−1}(y)} ℙ (X = x))

= ∑_{y∈Ω_{Y}} ∑_{x∈g^{−1}(y)} yℙ (X = x) = ∑_{y∈Ω_{Y}} ∑_{x∈g^{−1}(y)} g(x)ℙ (X = x)

= ∑_{x∈Ω_{X}} g(x)ℙ (X = x) .

5. For the indicator of any event A ⊆ Ω we have 𝔼 I_{A} = ℙ(A).

6. If X ⩾ 0 and X takes integer values, then 𝔼 X = ∑_{n=1}^{∞} ℙ (X ⩾ n).

Proof. We have

𝔼 X = ∑_{k=1}^{∞} kℙ (X = k) = ∑_{k=1}^{∞} ∑_{n=1}^{k} ℙ (X = k) = ∑_{n=1}^{∞} ∑_{k=n}^{∞} ℙ (X = k) = ∑_{n=1}^{∞} ℙ (X ⩾ n) ,

after interchanging the order of the summations. □

Terminology For a random variable X, the expected values of powers of X are known as moments of X; thus 𝔼 (X^{r}) (assuming it is well defined) is the rth moment of X and 𝔼 (|X|^{r}) is the rth absolute moment of X.

Example 3.5 Another proof of inclusion-exclusion. For events A_{1}, …, A_{n}, use the previous expression for the product of indicators to calculate

ℙ(A_{1} ∪ ⋯ ∪ A_{n}) = 𝔼 (I_{A_{1}∪A_{2}∪···∪A_{n}}) = 𝔼 (1 − ∏_{1}^{n} (1 − I_{A_{i}}))

= 𝔼 (∑_{i} I_{A_{i}} − ∑_{i_{1}<i_{2}} I_{A_{i_{1}} ∩A_{i_{2}}} + ∑_{i_{1}<i_{2}<i_{3}} I_{A_{i_{1}} ∩A_{i_{2}} ∩A_{i_{3}}} − ⋯ + (−1)^{n−1}I_{A_{1}∩···∩A_{n}})

then using the linearity of the expectation, this

= ∑_{i} 𝔼 (I_{A_{i}}) − ∑_{i_{1}<i_{2}} 𝔼 (I_{A_{i_{1}} ∩A_{i_{2}}} ) + ⋯ + (−1)^{n−1}𝔼 (I_{A_{1}∩···∩A_{n}})

= ∑_{i} ℙ(A_{i}) − ∑_{i_{1}<i_{2}} ℙ (A_{i_{1}} ∩ A_{i_{j}}) + ⋯ + (−1)^{n−1}ℙ (A_{1} ∩ ⋯ ∩ A_{n}) ,

which is the required expression for the inclusion-exclusion formula. □ For any random variable, X with finite mean, the variance is defined to be

𝕍ar (X) = 𝔼 (X − 𝔼 X)^{2} ,

and it is a measure of how much the distribution of X is spread out around the mean; the smaller the distribution the more the distribution of X is concentrated close to 𝔼 X. The quantity \sqrt{𝕍ar (X)} is known as the standard deviation of X. When we use the notation 𝕍ar (X) we will assume implicitly that it is a finite quantity. Properties of 𝕍ar (X)

1. 𝕍ar (X) = 𝔼 X^{2} − (𝔼 X)^{2}. Proof. We have, using Properties 2 and 3 of the expectation,

𝔼 (X − 𝔼 X)^{2} = 𝔼 (X^{2} − 2X𝔼 X + (𝔼 X)^{2})
= 𝔼 X^{2} − 2𝔼 X𝔼 X + (𝔼 X)^{2} = 𝔼 X^{2} − (𝔼 X)^{2}.  □

2. If c is a constant, 𝕍ar (cX) = c^{2}𝕍ar (X).

3. If c is a constant, 𝕍ar (X + c) = 𝕍ar (X).

4. 𝕍ar (X) ⩾ 0, and 𝕍ar (X) = 0 if and only if ℙ(X = c) = 1, for some constant c.

5. The expression 𝔼 (X − c)^{2} is minimized over constants c when c = 𝔼 X, so that 𝔼 (X − c)^{2} ⩾ 𝕍ar (X), for all c, with equality when c = 𝔼 X.

Proof. Expand out the expression

𝔼 (X − c)^{2} = 𝔼 (X^{2} − 2cX + c^{2}) = 𝔼 X^{2} − 2c𝔼 X + c^{2},

and minimize the right-hand side in c to see that the minimum occurs at c = 𝔼 X. □

Example 3.6 For X ∼ Bin(n, p), we have

\begin{aligned}𝔼 (X(X − 1)) & = ∑_{k=0}^{n} k(k − 1)\binom{n}{k}p^{k}(1 − p)^{n−k} = ∑_{k=2}^{n} \frac{n!}{(k − 2)!(n − k)!}p^{k}(1 − p)^{n−k} \\ & = n(n − 1)p^{2} ∑_{r=0}^{n−2} \binom{n − 2}{r}p^{r}(1 − p)^{n−2−r} = n(n − 1)p^{2}; \end{aligned}

then it follows that

𝔼 X^{2} = 𝔼 (X(X − 1)) + 𝔼 X = n(n − 1)p^{2} + np,

since we had seen that 𝔼 X = np; hence 𝕍ar (X) = 𝔼 X^{2} − (𝔼 X)^{2} = np(1 − p). □

Example 3.7 Suppose that X ∼ Poiss(λ), then a similar calculation to that in the previous Example gives

𝔼 (X(X − 1)) = ∑_{k=0}^{∞} k(k − 1)e^{−λ} \frac{λ^{k}}{k!} = ∑_{k=2}^{∞} e^{−λ} \frac{λ^{k}}{(k − 2)!} = λ^{2}e^{−λ} ∑_{r=0}^{∞} \frac{λ^{r}}{r!} = λ^{2};

recalling that in this case 𝔼 X = λ, we have 𝔼 X^{2} = λ^{2} + λ, so that 𝕍ar (X) = λ, showing that for a Poisson random variable the mean is the same as the variance. □

Example 3.8 Use of indicators Return to the situation, considered in Chapter 2, where n students leave their n coats outside the lecture room and when they leave they pick up their coats at random. Let N be the number of students who get their own coat, then N = ∑_{i=1}^{n} I_{A_{i}}, where A_{i} is the event that student i obtains his own coat. It follows that

𝔼 N = 𝔼 (∑_{i=1}^{n} I_{A_{i}}) = ∑_{i=1}^{n} 𝔼 (I_{A_{i}}) = ∑_{i=1}^{n} ℙ (A_{i}) = ∑_{i=1}^{n} \frac{1}{n} = 1, and
𝔼 N^{2} = 𝔼 (∑_{i=1}^{n} I_{A_{i}})^{2} = 𝔼 (∑_{i=1}^{n} (I_{A_{i}})^{2} + ∑_{i} ∑_{j≠i} I_{A_{i}}I_{A_{j}} );

since I_{A_{i}}I_{A_{j}} = I_{A_{i}∩A_{j}} we have (I_{A_{i}})^{2} = I_{A_{i}}, and we see that

𝔼 N^{2} = 𝔼 (∑_{i=1}^{n} I_{A_{i}} + ∑_{i} ∑_{j≠i} I_{A_{i}∩A_{j}} ) = ∑_{i=1}^{n} ℙ (A_{i}) + ∑_{i} ∑_{j≠i} ℙ (A_{i} ∩ A_{j})

= ∑_{i=1} \frac{1}{n} + ∑_{i} ∑_{j≠i} \frac{1}{n(n − 1)} = n × \frac{1}{n} + n(n − 1) × \frac{1}{n(n − 1)} = 1 + 1 = 2.

That gives 𝕍ar (N) = 𝔼 N^{2}−(𝔼 N)^{2} = 1. The fact that the mean and the variance are both the same might suggest that the distribution of the random variable N is close to being Poisson (with mean λ = 1) as is indeed the case when n is large. If we let p_{n} = ℙ (N = 0), the probability that when there are n students none of them gets his own coat, then we have seen previously (using inclusion-exclusion) that

p_{n} = 1 − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!} + ⋯ + (−1)^{n} \frac{1}{n!} → e^{−1}, as n → ∞;

take p_{0} = 1. The probability that exactly k students get their own coats is

ℙ (N = k) = \binom{n}{k}\frac{1}{n!}((n − k)!)p_{n−k} = \frac{1}{k!}p_{n−k} → \frac{1}{k!}e^{−1}, as n → ∞,

showing that the distribution of N is approximately Poisson. □

Theorem 3.9 (Cauchy–Schwarz inequality) For any random variables X and Y,

(𝔼 (XY))^{2} ⩽ 𝔼 (X^{2}) 𝔼 (Y^{2});

if 𝔼 (Y^{2}) > 0, equality occurs if and only if X = aY for some constant a ∈ ℝ.

Proof. For any a ∈ ℝ, observe that 𝔼 (X − aY)^{2} ⩾ 0, so that

0 ⩽ 𝔼 (X^{2} − 2aXY + a^{2}Y^{2}) = 𝔼 (X^{2}) − 2a𝔼 (XY) + a^{2}𝔼 (Y^{2}) ,

showing that the quadratic in a on the right-hand side has at most one real root, whence the discriminant 4 ((𝔼 (XY))^{2} − 𝔼 (X^{2}) 𝔼 (Y^{2})) ⩽ 0, giving the inequality. There is clearly equality if X = aY for some a ∈ ℝ, whereas if 𝔼 (Y^{2}) > 0 and the discriminant is 0 then the quadratic is 0 for a = 𝔼 (XY) /𝔼 (Y^{2}), and for that value of a, 𝔼 (X − aY)^{2} = 0 and so X = aY. Of course, if 𝔼 (Y^{2}) = 0 then Y = 0 and equality occurs. □

For two random variable X and Y, we define the covariance between X and Y as

ℂov (X, Y) = 𝔼 ((X − 𝔼 X) (Y − 𝔼 Y)) .

We shall see that this is a measure of the dependence between the random variables X and Y. Properties of ℂov (X, Y)

1. ℂov (X, Y) = ℂov (Y, X).

2. ℂov (X, Y) = 𝔼 (XY) − (𝔼 X) (𝔼 Y).

Proof. We have

ℂov (X, Y) = 𝔼 (XY − X(𝔼 Y) − Y (𝔼 X) + (𝔼 X)(𝔼 Y))
= 𝔼 (XY) − (𝔼 X)(𝔼 Y) − (𝔼 X)(𝔼 Y) + (𝔼 X)(𝔼 Y)
= 𝔼 (XY) − (𝔼 X) (𝔼 Y) .  □

3. ℂov (X, X) = 𝕍ar (X).

4. 𝕍ar (X + Y) = 𝕍ar (X) + 𝕍ar (Y) + 2ℂov (X, Y).

Proof. We have

𝕍ar (X + Y) = 𝔼 (X + Y − 𝔼 X − 𝔼 Y)^{2} = 𝔼 ((X − 𝔼 X) + (Y − 𝔼 Y))^{2}
= 𝔼 ((X − 𝔼 X)^{2} + (Y − 𝔼 Y)^{2} + 2 (X − 𝔼 X) (Y − 𝔼 Y))
= 𝔼 (X − 𝔼 X)^{2} + 𝔼 (Y − 𝔼 Y)^{2} + 2𝔼 (X − 𝔼 X) (Y − 𝔼 Y) .  □

5. If c is a constant, ℂov (X, c) = 0.

6. If c is a constant, ℂov (X + c, Y) = ℂov (X, Y).

7. If c is a constant, ℂov (cX, Y) = c ℂov (X, Y).

8. ℂov (X + Z, Y) = ℂov (X, Y) + ℂov (Z, Y). These last two generalize to the case of random variables X_{1}, …, X_{n} and Y_{1}, …, Y_{n} and constants c_{1}, …, c_{n} and d_{1}, … d_{n} to give, by induction,

ℂov (∑_{i=1}^{n} c_{i}X_{i}, ∑_{j=1}^{n} d_{j}Y_{j}) = ∑_{i=1}^{n} ∑_{j=1}^{n} c_{i}d_{j}ℂov (X_{i}, Y_{j}) .  (3.10)

Using the fact that 𝕍ar (X) = ℂov (X, X), we see that a special case of this is

𝕍ar (∑_{i=1}^{n} X_{i}) = ∑_{i=1}^{n} 𝕍ar (X_{i}) + ∑_{i=1}^{n} ∑_{j≠i} ℂov (X_{i}, X_{j}) ,  (3.11)

for any random variables X_{1}, …, X_{n}.

The correlation coefficient (or just the correlation) between random variables X and Y with 𝕍ar (X) > 0 and 𝕍ar (Y) > 0 is

ℂorr (X, Y) = \frac{ℂov (X, Y)}{\sqrt{𝕍ar (X)𝕍ar (Y)}}.

Notice that by the Cauchy-Schwarz inequality

|ℂorr (X, Y)| ⩽ 1, for all X and Y;

this follows by applying the inequality to the random variables \overline{X} = X − 𝔼 X and \overline{Y} = Y − 𝔼 Y. It may be further seen that |ℂorr (X, Y)| = 1 if and only if X = aY + b for some constants a and b. One property of correlation that we should note is that for constants a, b, c and d with ac ≠ 0, we have

ℂorr (aX + b, cY + d) = \{ \begin{matrix}ℂorr (X, Y) & when ac > 0, \\ −ℂorr (X, Y) & when ac < 0. \end{matrix}

This follows easily from the definition of correlation and the properties of the covariance and variance; notice that when ac = 0, ℂov (aX + b, cY + d) = 0, and the correlation is not defined because at least one of 𝕍ar (aX + b) = 0 or 𝕍ar (cY + d) = 0.

Notice that one consequence of this fact is that the correlation between two random variables is scale invariant – if we multiply the observation of X and Y by positive constants we do not alter the correlation.

3.3 Independence

Discrete random variables X_{1}, X_{2}, …, X_{n} are independent if, for all choices of x_{i} ∈ Ω_{X_{i}}, 1 ⩽ i ⩽ n, we have

ℙ (X_{1} = x_{1}, X_{2} = x_{2}, …, X_{n} = x_{n}) = ∏_{i=1}^{n} ℙ (X_{i} = x_{i}) .  (3.12)

Notice that X_{1}, X_{2}, …, X_{n} are independent if and only if, for all choices of subsets S_{i} ⊆ Ω_{X_{i}}, 1 ⩽ i ⩽ n, we have

ℙ (X_{1} ∈ S_{1}, X_{2} ∈ S_{2}, …, X_{n} ∈ S_{n}) = ∏_{i=1}^{n} ℙ (X_{i} ∈ S_{i}) .  (3.13)

To see this, if (3.13) holds, take S_{i} = {x_{i}} for each i and we see that (3.12) is true; conversely, the left hand side of (3.13) is

∑_{x_{1}∈S_{1}} ∑_{x_{2}∈S_{2}} ⋯ ∑_{x_{n}∈S_{n}} ℙ (X_{1} = x_{1}, X_{2} = x_{x}, …, X_{n} = x_{n})

and we see that, if (3.12) holds, then this is expression is

∑_{x_{1}∈S_{1}} ∑_{x_{2}∈S_{2}} ⋯ ∑_{x_{n}∈S_{n}} ∏_{i=1}^{n} ℙ (X_{i} = x_{i}) = ∏_{i=1}^{n} ( ∑_{x_{i}∈S_{i}} ℙ (X_{i} = x_{i})) = ∏_{i=1}^{n} ℙ (X_{i} ∈ S_{i}) ,

which gives (3.13).

Notice that events A_{1}, …, A_{n} are independent, as defined in the previous chapter, if and only if their indicator random variables I_{A_{1}}, …, I_{A_{n}} are independent random variables. Observe also that if random variables are independent then they are independent in pairs (this follows by taking S_{i} = Ω_{X_{i}} for all but two of the subsets S_{i} in (3.13)) – they are said to be pairwise independent; a similar argument shows that if any collection of random variables is independent then any sub-collection of them is independent. By considering indicators, the example from the last chapter shows that pairwise independence of random variables does not imply independence in general. Properties of independent random variables

1. If X_{1}, …, X_{n} are independent random variables and g_{i} : ℝ → ℝ, 1 ⩽ i ⩽ n, are

functions then g_{1}(X_{1}), …, g_{n}(X_{n}) are independent random variables.

Proof. For y_{i} ∈ Ω_{g_{i}(X_{i})}, 1 ⩽ i ⩽ n, we have

\begin{aligned}ℙ (g_{1}(X_{1}) = y_{1}, …, g_{n}(X_{n}) = y_{n}) & = ℙ (X_{1} ∈ g_{1}^{−1}(y_{1}), …, X_{n} ∈ g_{n}^{−1}(y_{n})) \\ & = ∏_{i=1}^{n} ℙ (X_{i} ∈ g_{i}^{−1}(y_{i})) = ∏_{i=1}^{n} ℙ (g_{i}(X_{i}) = y_{i}) \end{aligned}

after using (3.13), showing that the random variables g_{1}(X_{1}), …, g_{n}(X_{n}) are independent. □

2. If X_{1}, …, X_{n} are independent random variables, then

𝔼 (∏_{i=1}^{n} X_{i}) = ∏_{i=1}^{n} 𝔼 (X_{i}) ;

that is, the expectation of the product of independent random variables is the product of their expectations.

Proof. In a similar way to the previous proof, we may represent the event

(∏_{i=1}^{n} X_{i} = y) = ⋃ (X_{1} = x_{1}, X_{2} = x_{2}, …, X_{n} = x_{n})

as a disjoint union of events over values of x_{1}, …, x_{n} with ∏_{i} x_{i} = y. Then

𝔼 (∏_{i=1}^{n} X_{i}) = ∑_{y} yℙ (∏_{i=1}^{n} X_{i} = y) = ∑_{y} y ∑ ; x_{i}:∏_{i} x_{i}=y ℙ (X_{1} = x_{1}, …, X_{n} = x_{n})

= ∑_{y} ∑ ; x_{i}:∏_{i} x_{i}=y y ∏_{i=1}^{n} ℙ (X_{i} = x_{i}) , by independence

= ∑_{x_{1},...,x_{n}} ∏_{i=1}^{n} (x_{i}ℙ (X_{i} = x_{i})) = ∏_{i=1}^{n} (∑_{x_{i}} x_{i}ℙ (X_{i} = x_{i})) = ∏_{i=1}^{n} 𝔼 (X_{i}) ,

as required. □

3. If X and Y are independent random variables then ℂov (X, Y) = 0 (and hence ℂorr (X, Y) = 0). The converse is not true in general (see Example 3.14 below): that is, ℂov (X, Y) = 0 does not imply that X and Y are independent.

Proof. Property 1 shows that X − 𝔼 X and Y − 𝔼 Y are independent random variables and then by Property 2,

ℂov (X, Y) = 𝔼 ((X − 𝔼 X) (Y − 𝔼 Y)) = 𝔼 (X − 𝔼 X) 𝔼 (Y − 𝔼 Y) = 0

since 𝔼 (X − 𝔼 X) = 𝔼 (X) − 𝔼 (X) = 0 (and similarly 𝔼 (Y − 𝔼 Y) = 0). □

4. If X_{1}, …, X_{n} are independent random variables then

𝕍ar (∑_{i=1}^{n} X_{i}) = ∑_{i=1}^{n} 𝕍ar (X_{i}) ;

that is, the variance of the sum of independent random variables is the sum of their variances.

Proof. Use Property 3 to see that for j ≠ i, ℂov (X_{i}, X_{j}) = 0 and the result follows from the relation (3.11). □

5. If X_{1}, …, X_{n} are independent random variables then the conditional probability

ℙ (X_{1}, = x_{1}, …, X_{n−1} = x_{n−1} | X_{n} = x_{n}) = ℙ (X_{1}, = x_{1}, …, X_{n−1} = x_{n−1}) ,

for all choices of x_{i} ∈ Ω_{X_{i}}, 1 ⩽ i ⩽ n. Proof. We have the conditional probability on the left-hand side is

\frac{ℙ (X_{1}, = x_{1}, …, X_{n} = x_{n})}{ℙ (X_{n} = x_{n})} = \frac{∏_{i=1}^{n} ℙ (X_{i} = x_{i})}{ℙ (X_{n} = x_{n})} = ∏_{i=1}^{n−1} ℙ (X_{i} = x_{i}) ,

which equals the right-hand side, again by independence. □

Terminology Random variables with the same distribution are usually said to be identically distributed, and if they are also independent they are i.i.d. (independent and identically distributed). If X_{1}, …, X_{n} are i.i.d. then, from Property 4,

𝕍ar (\frac{X_{1} + ⋯ + X_{n}}{n} ) = \frac{𝕍ar (X_{1})}{n}.

Example 3.14 Covariance equal to 0 does not imply independence Suppose that X is a random variable with distribution determined by

\begin{matrix}x & 2 & 1 & -1 & -2 \\ ℙ (X = x) & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \end{matrix}

and let Y = X^{2}. Then 𝔼 X = 0 and 𝔼 (X^{3}) = 0 so that ℂov (X, Y) = 𝔼 (X^{3}) = 0, but

ℙ (X = 2, Y = 4) = \frac{1}{4} ≠ ℙ (X = 2) ℙ (Y = 4) = \frac{1}{4} × \frac{1}{2},

so that X and Y are not independent. □

Example 3.15 Efron’s dice An interesting example showing that odds are not transitive is given by a set of 4 dice with the following faces:

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................  .................................................................................................................................................................................................................................................................................................................................................................................................................................................... .......................................................  ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................  .................................................................................................................................................................................................................................................................................................................................................................................................................................................... .......................................................  ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................  .................................................................................................................................................................................................................................................................................................................................................................................................................................................... .......................................................  ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................  .................................................................................................................................................................................................................................................................................................................................................................................................................................................... ....................................................... A 4 4 4 4 0 0  B 3 3 3 3 3 3  C 6 6 2 2 2 2  D 5 5  5 1 1 1

If each of the dice is rolled with respective outcomes A, B, C and D then

ℙ(A > B) = ℙ(B > C) = ℙ(C > D) = ℙ(D > A) = \frac{2}{3}.  □

3.4 Probability generating functions

Consider a random variable, X, taking values in the non-negative integers 0, 1, 2, … with distribution determined by p_{r} = ℙ (X = r), r = 0, 1, 2, . . .. The probability generating function (p.g.f.) of X is defined to be

p(z) = 𝔼 (z^{X}) = ∑_{r=0}^{∞} p_{r}z^{r}, for 0 ⩽ z ⩽ 1.

Since the terms in the sum are all non-negative and 0 ⩽ ∑_{r} p_{r}z^{r} ⩽ ∑_{r} p_{r} = 1, the probability generating function is well defined and takes values in [0, 1]. Its importance stems from the following result. Theorem 3.16 The probability generating function of X, p(z), 0 ⩽ z ⩽ 1, determines the probability distribution of X uniquely. Proof. Suppose that p(z) = ∑_{r=0}^{∞} p_{r}z^{r} = ∑_{r=0}^{∞} q_{r}z^{r}, for all 0 ⩽ z ⩽ 1, where p_{r} ⩾ 0, and

q_{r} ⩾ 0 for each r, and ∑_{r=0}^{∞} p_{r} = 1 = ∑_{r=0}^{∞} q_{r}. We will show by induction on n that p_{n} = q_{n} for all n. First see, by setting z = 0, that p_{0} = q_{0}. Now assume that p_{i} = q_{i} for 0 ⩽ i ⩽ n, then for 0 < z ⩽ 1

∑_{r=n+1}^{∞} p_{r}z^{r} = ∑_{r=n+1}^{∞} q_{r}z^{r}.

Divide through both sides by z^{n+1} and let z ↓ 0 to see that p_{n+1} = q_{n+1} to complete the induction. □

In addition to determining the distribution uniquely, the probability generating function may be used to compute moments of the random variable by evaluating derivatives of the function.

Theorem 3.17 Let X be a random variable with probability generating function p(z), then the mean of X is

𝔼 X = lim_{z↑1} p′(z) = p′(1−).

Proof. First assume that 𝔼 X < ∞. For 0 < z < 1,

p′(z) = ∑_{r=1}^{∞} rp_{r}z^{r−1} ⩽ ∑_{r=1}^{∞} rp_{r} = 𝔼 X.

We see that p′(z) is non-decreasing in z so that lim_{z↑1} p′(z) ⩽ 𝔼 X. Take ϵ > 0, and choose

N so that ∑_{r=1}^{N} rp_{r} ⩾ 𝔼 X − ϵ. Then

lim_{z↑1} p′(z) ⩾ lim_{z↑1} ∑_{r=1}^{N} rp_{r}z^{r−1} = ∑_{r=1}^{N} rp_{r} ⩾ 𝔼 X − ϵ;

this is true for each ϵ > 0, whence lim_{z↑1} p′(z) ⩾ 𝔼 X and it follows that lim_{z↑1} p′(z) = 𝔼 X. If

𝔼 X = ∞, then for any M > 0 choose N so that ∑_{r=1}^{N} rp_{r} ⩾ M, and, as above, see that

lim_{z↑1} p′(z) ⩾ lim_{z↑1} ∑_{r=1}^{N} rp_{r}z^{r−1} = ∑_{r=1}^{N} rp_{r} ⩾ M;

this is true for any M, whence lim_{z↑1} p′(z) = ∞. □

Note By considering the second derivative of p(z), a similar argument to that of Theorem 3.17 may be used to show that

p′′(1−) = lim_{z↑1} p′′(z) = lim_{z↑1} ∑_{r=1}^{∞} r(r − 1)p_{r}z^{r−2} = 𝔼 (X(X − 1)) ,

and by considering the kth derivative, k ⩾ 1, we have

\begin{aligned}p^{(k)}(1−) & = lim_{z↑1} p^{(k)}(z) = lim_{z↑1} ∑_{r=1}^{∞} r(r − 1) ⋯ (r − k + 1)p_{r}z^{r−2} \\ & = 𝔼 (X(X − 1) ⋯ (X − k + 1)) . \end{aligned}

In particular, 𝕍ar (X) = p′′(1−) + p′(1−) − (p′(1−))^{2}.

Example 3.18 Geometric distribution Let X be a random variable with probability distribution given by ℙ (X = r) = p(1 − p)^{r} = pq^{r}, r = 0, 1, 2, …, where 0 < p = 1 − q < 1. Then X may be thought of as the number of tails obtained before getting the first head when successively tossing a coin with probability p of heads on each toss. The probability generating function of X is

p(z) = 𝔼 (z^{X}) = ∑_{r=0}^{∞} p_{r}z^{r} = ∑_{r=0}^{∞} pq^{r}z^{r} = \frac{p}{1 − qz} .

We have p′(z) = pq/ (1 − qz)^{2}, so that 𝔼 X = p′(1) = q/p. Also, p′′(z) = 2pq^{2}/ (1 − qz)^{3}, so that 𝔼 (X(X − 1)) = 2q^{2}/p^{2}, from which we deduce that

𝔼 (X^{2}) = \frac{2q^{2}}{p^{2}} + \frac{q}{p} and 𝕍ar (X) = 𝔼 (X^{2}) − (𝔼 X)^{2} = \frac{q}{p^{2}} .  □

Note The term geometric distribution is often also given to the situation where ℙ (X = r) = pq^{r−1}, r = 1, 2, … for 0 < p = 1 − q < 1. Here, X would be the number of tosses required to achieve the first head where the probability of heads is p. This just corresponds to replacing X in Example 3.18 by X+1, so the probability generating function becomes pz/(1 − qz), the mean is 1/p and the variance is unchanged at q/p^{2}. □

Another use for probability generating functions is that they provide an easy way of dealing with sums of independent random variables. Suppose that X_{1}, …, X_{n} are independent random variables with probability generating functions p_{1}(z), …, p_{n}(z) respectively. Then, since z^{X_{1}}, …, z^{X_{n}} are independent, we have that the probability generating function of X_{1} + ⋯ + X_{n} is

𝔼 (z^{X_{1}+···+X_{n}}) = ∏_{i=1}^{n} 𝔼 (z^{X_{i}}) = ∏_{i=1}^{n} p_{i}(z).

In the special case when X_{1}, …, X_{n} are i.i.d. with common probability generating function p(z) we have

𝔼 (z^{X_{1}+···+X_{n}}) = (p(z))^{n} .

Example 3.19 Sums of Binomial random variables Consider independent random variables X ∼ Bin (n, p) and Y ∼ Bin (m, p), where 0 < p = 1 − q < 1. The probability generating function of X is

𝔼 (z^{X}) = ∑_{r=0}^{n} \binom{n}{r}p^{r}q^{n−r}z^{r} = (pz + q)^{n} ,

so that the probability generating function of Y is (pz + q)^{m}. It follows that the probability generating function of X + Y is the product of the two generating functions and is therefore (pz + q)^{m+n}. From Theorem 3.16 we conclude that X + Y ∼ Bin(n + m, p). The probabilistic interpretation is immediate, of course; X is the number of heads in n tosses of a coin with probability p of heads and Y is the number of tosses in m (independent) tosses of the coin, so that X + Y is the number of heads in n + m tosses. This of course generalizes, by induction, to the case of independent random variables X_{1}, …, X_{k} with X_{i} ∼ Bin (n_{i}, p), to give X_{1} + ⋯ + X_{k} ∼ Bin (∑_{1}^{k} n_{i}, p). □

Example 3.20 Sums of Poisson random variables Consider independent random variables X ∼ Poiss (λ) and Y ∼ Poiss (μ), where λ > 0 and μ > 0. The probability generating function of X is

𝔼 (z^{X}) = ∑_{r=0}^{∞} z^{r}e^{−λ} \frac{λ^{r}}{r!} = e^{−λ(1−z)}.

The probability generating function is the same expression with μ replacing λ and the probability generating function of X + Y is

e^{−λ(1−z)}e^{−μ(1−z)} = e^{−(λ+μ)(1−z)};

from Theorem 3.16 we conclude that X + Y ∼ Poiss (λ + μ); for an alternative argument see Example 3.22 below. □

Example 3.21 Negative binomial distribution Consider a random variable X which has distribution given by

ℙ (X = r) = \binom{r − 1}{n − 1}p^{n}(1 − p)^{r−n}, for r = n, n + 1, …,

where 0 < p = 1 − q < 1, and n ⩾ 1. Here, X represents the number of tosses of a coin to get n heads for the first time, where the probability of heads is p. The probability generating function of X is

𝔼 (z^{X}) = ∑_{r=n}^{∞} z^{r}\binom{r − 1}{n − 1}p^{n}q^{r−n} = (pz)^{n} ∑_{r=n}^{∞} \binom{r − 1}{n − 1}(qz)^{r−n} = (pz/(1 − qz))^{n} .

From the note following Example 3.18 we see that X may be represented as the sum X_{1} + ⋯ + X_{n} of n i.i.d. random variables each with the same geometric distribution

ℙ (X_{1} = r) = pq^{r−1}, for r = 1, 2, ….

The distribution of X is usually referred to as the negative binomial distribution. □

3.5 Conditional distributions

The joint distribution of random variables X_{1}, …, X_{n}, is given by

ℙ (X_{1} = x_{1}, …, X_{n} = x_{n}) for x_{1} ∈ Ω_{X_{1}}, …, x_{n} ∈ Ω_{X_{n}},

and it is a probability distribution on Ω_{X_{1}} × ⋯ × Ω_{X_{n}}, and the marginal distribution of X_{i} is

ℙ (X_{i} = x_{i}) = ∑ ℙ (X_{1} = x_{1}, …, X_{n} = x_{n}) ,

where the summation is over x_{1}, …, x_{i−1}, x_{i+1} …, x_{n}; this identity is a consequence of the law of total probability. Now consider the case n = 2 and (to avoid unnecessary subscripts) consider the random variables X and Y. The conditional distribution of X, given Y = y, is a probability distribution on Ω_{X} given by

ℙ (X = x | Y = y) for x ∈ Ω_{X},

where, of course, ℙ (X = x | Y = y) = ℙ (X = x, Y = y) /ℙ (Y = y). Again, by the law of total probability

ℙ (X = x) = ∑_{y∈Ω_{Y}} ℙ (X = x, Y = y) = ∑_{y∈Ω_{Y}} ℙ (X = x | Y = y) ℙ (Y = y) .

Example 3.22 Sum of two independent random variables Suppose that X and Y are independent random variables, then we may express the distribution of their sum as follows

ℙ (X + Y = z) = ∑_{y∈Ω_{Y}} ℙ (X + Y = z | Y = y) ℙ (Y = y) = ∑_{y∈Ω_{Y}} ℙ (X = z − y) ℙ (Y = y)
= ∑_{x∈Ω_{X}} ℙ (X = x) ℙ (Y = z − x) ,  (3.23)

where the last expression is obtained if we condition on X initially instead of Y. This procedure gives the convolution of the distributions of X and Y. For example, if X ∼ Poiss(λ) and Y ∼ Poiss(μ),

ℙ (X + Y = n) = ∑_{r=0}^{∞} ℙ (X = n − r) ℙ (Y = r)

= ∑_{r=0}^{n} e^{−λ} \frac{λ^{n−r}}{r!} e^{−μ} \frac{μ^{r}}{(n − r)!}, since ℙ (X = k) = 0, for k < 0,

= \frac{e^{−(λ+μ)}}{n!} ∑_{r=0}^{n} \binom{n}{r}λ^{n−r}μ^{r} = e^{−(λ+μ)} \frac{(λ + μ)^{n}}{n!} ,

so that X + Y ∼ Poiss(λ + μ), as seen in Example 3.20 previously using generating functions. □

The conditional expectation of X given Y = y is

𝔼 (X | Y = y) = ∑_{x∈Ω_{X}} xℙ (X = x | Y = y) = ∑_{ω:Y (ω)=y} X(ω)ℙ ({ω}) /ℙ (Y = y) .

Note that 𝔼 (X | Y = y) is a function of y, g(y) say, then the random variable g(Y) is known as the conditional expectation of X given Y and is written 𝔼 (X | Y). It is important to emphasize that 𝔼 (X | Y) is a random variable and it is a function of Y, in contrast to 𝔼 (X | Y = y), which is a real number.

Example 3.24 Consider tossing a coin n times where the probability of a head is p, 0 < p = 1 − q < 1, and let X_{i} = 1 if the ith toss produces a head and X_{i} = 0, otherwise. Let Y = X_{1} + ⋯ + X_{n} denote the total number of heads so that Y ∼ Bin (n, p). Then, for r ⩾ 1,

ℙ (X_{1} = 1 | Y = r) = \frac{ℙ (X_{1} = 1, Y = r)}{ℙ (Y = r)} = \frac{ℙ (X_{1} = 1, X_{1} + ⋯ + X_{n} = r)}{ℙ (Y = r)}

= \frac{ℙ (X_{1} = 1, X_{2} + ⋯ + X_{n} = r − 1)}{ℙ (Y = r)},

then by independence and the fact that X_{2} + ⋯ + X_{n} ∼ Bin (n − 1, p) this

= \frac{ℙ (X_{1} = 1) ℙ (X_{2} + ⋯ + X_{n} = r − 1)}{ℙ (Y = r)}

= \frac{p\binom{n − 1}{r − 1}p^{r−1}q^{n−r}}{\binom{n}{r}p^{r}q^{n−r}} = \frac{r}{n};

we may see also that ℙ (X_{1} = 1 | Y = 0) = 0. Then

𝔼 (X_{1} | Y = r) = 1 × ℙ (X_{1} = 1 | Y = r) + 0 × ℙ (X_{1} = 0 | Y = r) = \frac{r}{n}, 0 ⩽ r ⩽ n.

In this case we have 𝔼 (X_{1} | Y) = Y/n. □

Properties of conditional expectation 1. For c, a constant, then 𝔼 (cX | Y) = c𝔼 (X | Y) and 𝔼 ( c | Y) = c.

2. For random variables X_{1}, …, X_{n}, 𝔼 (∑_{i} X_{i} | Y ) = ∑_{i} 𝔼 (X_{i} | Y).

3. 𝔼 (𝔼 (X | Y)) = 𝔼 (X). Proof. We have

𝔼 (𝔼 (X | Y)) = ∑_{y∈Ω_{Y}} ( ∑_{x∈Ω_{X}} xℙ (X = x | Y = y)) ℙ (Y = y)
= ∑_{x∈Ω_{X}} x ∑_{y∈Ω_{Y}} ℙ (X = x, Y = y) = ∑_{x∈Ω_{X}} xℙ (X = x) = 𝔼 (X) .  □

4. When X and Y are independent, 𝔼 (X | Y) = 𝔼 (X). Proof. For y ∈ Ω_{Y},

𝔼 (X | Y = y) = ∑_{x∈Ω_{X}} xℙ (X = x | Y = y) = ∑_{x∈Ω_{X}} xℙ (X = x) = 𝔼 (X) .  □

5. When Y and Z are independent, 𝔼 (𝔼 (X | Y) | Z) = 𝔼 (X).

Proof. Since 𝔼 (X | Y) is a function of Y it is independent of Z, so using Property 4 and then Property 3, we have

𝔼 (𝔼 (X | Y) | Z) = 𝔼 (𝔼 (X | Y)) = 𝔼 (X) .  □
6. For any function h : ℝ → ℝ, we have 𝔼 (h(Y)X | Y) = h(Y)𝔼 (X | Y).

Proof. We have, for y ∈ Ω_{Y},

𝔼 (h(Y)X | Y = y) = ∑_{ω:Y (ω)=y} h(Y (ω))X(ω)ℙ ({ω}) /ℙ (Y = y) = h(y)𝔼 (X | Y = y) .

A particular consequence of this and Property 1 is that 𝔼 (𝔼 (X | Y) | Y) = 𝔼 (X | Y).□

7. The conditional expectation 𝔼 (X | Y) is that function h(Y) of Y which minimizes 𝔼 (X − h(Y))^{2} over all functions h.

Proof. Write

𝔼 (X − h(Y))^{2} = 𝔼 [X − 𝔼 (X | Y) + 𝔼 (X | Y) − h(Y)]^{2},

which may be expanded to

𝔼 [X − 𝔼 (X | Y)]^{2} + 𝔼 [𝔼 (X | Y) − h(Y)]^{2} + 2𝔼 [(X − 𝔼 (X | Y))(𝔼 (X | Y) − h(Y))].

Now consider half the cross-product term,

𝔼 [(X − 𝔼 (X | Y))(𝔼 (X | Y) − h(Y))] = 𝔼 (𝔼 [(X − 𝔼 (X | Y))(𝔼 (X | Y) − h(Y)) | Y ])

by using Property 3, and then, using Property 5, this = 𝔼 ((𝔼 (X | Y) − h(Y))𝔼 [(X − 𝔼 (X | Y)) | Y ]);

but 𝔼 [(X − 𝔼 (X | Y)) | Y ] = 𝔼 (X | Y) − 𝔼 (X | Y) = 0, so that

𝔼 (X − h(Y))^{2} = 𝔼 [X − 𝔼 (X | Y)]^{2} + 𝔼 [𝔼 (X | Y) − h(Y)]^{2}

from which the result follows, since the first term in this expression does not involve h and the second term is minimized by h(Y) = 𝔼 (X | Y). □

Example 3.25 Sum of a random number of random variables Let X_{1}, X_{2}, … be independent and identically distributed random variables with common probability generating function p(z). Let N be a non-negative integer valued random variable independent of the {X_{i}} and having probability generating function q(z). We consider the p.g.f. of the random variable X_{1} + ⋯ + X_{N}; (here the sum is 0 if N = 0).

\begin{aligned}r(z) = 𝔼 (z^{X_{1}+···+X_{N}} ) & = 𝔼 (𝔼 (z^{X_{1}+···+X_{N}} | N)) = 𝔼 ((𝔼 z^{X_{1}})^{N}) \\ & = 𝔼 ((p(z))^{N}) = q(p(z)). \end{aligned}

If at a first reading you find the second equality too cryptic, you might wish to spell out the argument as

𝔼 (z^{X_{1}+···+X_{N}} ) = ∑_{n=0}^{∞} 𝔼 (z^{X_{1}+···+X_{N}} | N = n) ℙ (N = n)

= ∑_{n=0}^{∞} 𝔼 (z^{X_{1}+···+X_{n}} | N = n) ℙ (N = n)

= ∑_{n=0}^{∞} 𝔼 (z^{X_{1}+···+X_{n}}) ℙ (N = n) = ∑_{n=0}^{∞} (p(z))^{n} ℙ (N = n) = q(p(z)).

After some practice you should find the conditional expectation shorthand notation given first more helpful. It follows from the expression for r(z) that r′(z) = q′(p(z))p′(z), so that

𝔼 (X_{1} + ⋯ + X_{N}) = q′(p(1−))p′(1−) = (𝔼 N) (𝔼 X_{1}) ,

since p(1−) = 1. Furthermore, since r′′(z) = q′′(p(z) (p′(z))^{2} + q′(p(z))p′′(z), and the fact that q′′(1−) = 𝔼 (N)^{2} − 𝔼 N and p′′(1−) = 𝔼 (X_{1})^{2} − 𝔼 X_{1}, we may calculate that

\begin{aligned}𝕍ar (X_{1} + ⋯ + X_{N}) & = r′′(1−) + r′(1−) − (r′(1−))^{2} \\ & = (𝔼 N) 𝕍ar (X_{1}) + (𝔼 X_{1})^{2} 𝕍ar (N) . \end{aligned}

Notice that the variance of X_{1}+⋯+X_{N} is increased over what it would be if N is constant, N ≡ 𝔼 N = n, say, by the amount (𝔼 X_{1})^{2} 𝕍ar (N); if 𝕍ar (N) = 0 and N is constant we get the usual expression for the variance of a sum of n i.i.d. random variables. □

3.6 Branching processes

As an example of conditional expectations and of generating functions we will consider a model of population growth and extinction known as the Bienaymé-Galton-Watson process. Consider a sequence of random variables X_{0}, X_{1}, …, where X_{n} represents the number of individuals in the nth generation. We will assume that the population is initiated by one individual, take X_{0} ≡ 1, and when he dies he is replaced by k individuals with probability g_{k}, k = 0, 1, 2, . . .. These individuals behave independently and identically to the parent individual, as do those in subsequent generations. The number in the (n + 1)st generation, X_{n+1}, depends on the number in the nth generation and is given by

X_{n+1} = \{ \begin{matrix}Y_{1}^{n} + Y_{2}^{n} + ⋯ + Y_{X_{n}}^{n} & when X_{n} ⩾ 1, \\ 0 & when X_{n} = 0. \end{matrix}

Here {Y_{j}^{n} : n ⩾ 1, j ⩾ 1} are independent, identically distributed random variables with ℙ (Y_{j}^{n} = k) = g_{k}, for k ⩾ 0 and Y_{j}^{n} represents the number of offspring of the jth individual in the nth generation, j ⩽ X_{n}. Assumptions (i) g_{0} > 0; and (ii) g_{0} + g_{1} < 1. Assumption (i) means that the population can die out (extinction) since in each generation there is positive probability that all individuals have no offspring; assumption (ii) means that the population may grow, there is positive probability that the next generation has more individuals than the present one. Now let G(z) = ∑_{k=0}^{∞} g_{k}z^{k} = 𝔼 (z^{X_{1}}) and set G_{n}(z) = 𝔼 (z^{X_{n}}), for n ⩾ 1, so that G_{1} = G.

Theorem 3.26 For all n ⩾ 1, G_{n+1}(z) = G_{n} (G(z)) = G (⋯ (G(z)) ⋯) = G (G_{n}(z)).

Proof. Note that Y_{1}^{n}, Y_{2}^{n}, … are independent of X_{n}, so that

G_{n+1}(z) = 𝔼 (z^{X_{n+1}}) = ∑_{k=0}^{∞} 𝔼 (z^{X_{n+1}} | X_{n} = k) ℙ (X_{n} = k)

= ∑_{k=0}^{∞} 𝔼 (z^{Y_{1}^{n}+···+Y_{k}^{n}}) ℙ (X_{n} = k) = ∑_{k=0}^{∞} (G(z))^{k} ℙ (X_{n} = k)

= 𝔼 ((G(z))^{X_{n}}) = G_{n} (G(z)) .  □

Corollary 3.27 For m = 𝔼 (X_{1}) = ∑_{k=1}^{∞} kg_{k} and σ^{2} = 𝕍ar (X_{1}) = ∑_{k=0}^{∞} (k − m)^{2} g_{k}, then for n ⩾ 1, we have

𝔼 (X_{n}) = m^{n}, 𝕍ar (X_{n}) = \{ \begin{matrix}\frac{σ^{2}m^{n−1} (m^{n} − 1)}{m − 1} & when m ≠ 1, \\ nσ^{2} & when m=1. \end{matrix}

Proof. Differentiating G_{n}(z) = G_{n−1}(G(z)) to obtain G′_{n}(z) = G′_{n−1}(G(z))G′(z) and letting z ↑ 1, it follows that

𝔼 (X_{n}) = m𝔼 (X_{n−1}) = ⋯ = m^{n}𝔼 (X_{0}) = m^{n},

since X_{0} = 1. Differentiating G_{n}(z) a second time gives

G′′_{n}(z) = G′′_{n−1} (G(z)) (G′(z))^{2} + G′_{n−1} (G(z)) G′′(z),

and letting z ↑ 1 again we have

𝔼 (X_{n} (X_{n} − 1)) = m^{2}𝔼 (X_{n−1} (X_{n−1} − 1)) + (σ^{2} + m^{2} − m) 𝔼 (X_{n−1}) .

We then have, using the fact that 𝔼 X_{n} = m^{n},

𝕍ar (X_{n}) = 𝔼 (X_{n}(X_{n} − 1)) + 𝔼 (X_{n}) − (𝔼 X_{n})^{2}
= m^{2}𝔼 (X_{n−1}(X_{n−1} − 1)) + (σ^{2} + m^{2} − m) 𝔼 (X_{n−1}) + m^{n} − m^{2n}
= m^{2} [𝕍ar (X_{n−1}) − 𝔼 (X_{n−1}) + (𝔼 X_{n−1})^{2}] + (σ^{2} + m^{2}) m^{n−1} − m^{2n}
= m^{2}𝕍ar (X_{n−1}) + σ^{2}m^{n−1}.

Iterating this, we see that

𝕍ar (X_{n}) = m^{2}𝕍ar (X_{n−1}) + σ^{2}m^{n−1} = m^{4}𝕍ar (X_{n−2}) + σ^{2} (m^{n−1} + m^{n}) = ⋯
= m^{2n}𝕍ar (X_{0}) + σ^{2} (m^{n−1} + ⋯ + m^{2n−2})
= σ^{2} (m^{n−1} + ⋯ + m^{2n−2}) , since 𝕍ar (X_{0}) = 0 because X_{0} = 1,

and then the result may be obtained immediately. □

Probability of extinction Notice that X_{n} = 0 implies that X_{n+1} = 0 so that if we let A_{n} = (X_{n} = 0), the event that the population is extinct at or before generation n, we have A_{n} ⊆ A_{n+1} and A = ⋃_{n=1}^{∞} A_{n} represents the event that extinction ever occurs. Notice that ℙ (A_{n}) = G_{n}(0) and by the continuity property of probabilities on increasing events we see that the extinction probability, q, say, is

q = ℙ (A) = lim_{n→∞} ℙ (A_{n}) = lim_{n→∞} G_{n}(0) = lim_{n→∞} ℙ (X_{n} = 0) .

Theorem 3.28 The extinction probability q is the smallest positive root of the equation G(z) = z. When m, the mean number of offspring per individual, satisfies m ⩽ 1 then q = 1; when m > 1 then q < 1. Proof. The fact that the extinction probability q is well defined follows from the above and since G is continuous and q = lim_{n→∞} G_{n}(0) we have G ( lim_{n→∞} G_{n}(0)) = lim_{n→∞} G_{n+1}(0), so that G(q) = q, that is q is a root of G(z) = z; note that 1 is always a root since G(1) = ∑_{r=0}^{∞} g_{r} = 1. Now let H(z) = G(z) − z, then H′′ = ∑_{r=0}^{∞} r(r − 1)g_{r}z^{r−2} > 0 for 0 < z < 1 provided g_{0} + g_{1} < 1, so the derivative of H is strictly increasing in the range 0 < z < 1, hence H can have at most one root different from 1 in [0, 1] (Rolle’s Theorem).

Firstly, suppose that H has no root in [0, 1) then, since H(0) = g_{0} > 0 we must have H(z) > 0 for all 0 < z < 1, so H(1) − H(z) < H(1) = 0 and so

H′(1−) = lim_{z↑1} \frac{H(1) − H(z)}{1 − z} ⩽ 0, whence m = G′(1−) ⩽ 1.

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} z 1 G(0) G(z)  Fig. 1: m ⩽ 1, q = 1^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}.................................................................................................................................................................................................................................................................................................................. . . . . . . . . . . ..... . . . .... . .  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} z 1 q G(0) G(z)  Fig. 2: m > 1, q < 1^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  .............................................................................................................................................................................................................................................................................................................................. . . . . . . . . . . .... . .

Next, suppose that H has a unique root r in [0, 1), then H′ must have a root in [r, 1); that is H′(z) = G′(z) − 1 = 0 for some z, r ⩽ z < 1. The function G′ is strictly increasing (since g_{0} + g_{1} < 1) so that m = G′(1−) > G′(z) = 1. Thus we see that m ⩽ 1, if and only if, q = 1. Furthermore, if m > 1, let α > 0 be the smallest positive root of G(z) = z, so that because G is increasing, α = G(α) ⩾ G(0), and repeating n times we have α ⩾ G_{n}(0), whence α ⩾ lim_{n→∞} G_{n}(0) = q, so that we must have α = q, completing the proof. □

Note Figures 1 and 2 illustrate the two situations m ⩽ 1 and m > 1; the dotted lines illustrate the iteration G_{n+1}(0) = G (G_{n}(0)) tending to the smallest positive root, q.

3.7 Random walks

Let X_{1}, X_{2}, … be i.i.d. random variables and set S_{n} = S_{0} + X_{1} + ⋯ + X_{k} for k ⩾ 1 where S_{0} is a constant then {S_{k}, k ⩾ 0} is known as a (one-dimensional) random walk. When each X_{i} just takes the two values +1 and −1 with probabilities p and q = 1 − p, respectively, it is a simple random walk and further when p = q = \frac{1}{2} it is a simple, symmetric random walk. We will consider simple random walks.

Recurrence relations The problems we will look at for the simple random walk often reduce to the solution of recurrence relations (or difference equations). We consider the general solution of such equations in the simplest situations which have constant coefficients.

1. First-order equations: The general first-order equation is x_{n+1} = ax_{n} + b, for n ⩾ 0,where a and b are constants; the case b = 0 gives the general first-order homogeneous equation x_{n+1} = ax_{n}, which trivially may be solved as x_{n} = a^{n}x_{0}; if y_{n} is any solution of the inhomogeneous equation, then the general solution of the inhomogeneous equation is of the form x_{n} = Ca^{n} + y_{n} for some constant C (because x_{n} −y_{n} must be a solution of the homogeneous equation). The constant is determined by a boundary condition.

2. Second-order equations: x_{n+1} = ax_{n} + bx_{n−1} + c, for n ⩾ 1, where a, b and c are constants. First consider the homogeneous case where c = 0. Then write the relation in matrix form as follows:

( \begin{matrix}x_{n+1} \\ x_{n} \end{matrix} ) = ( \begin{matrix}a & b \\ 1 & 0 \end{matrix} ) ( \begin{matrix}x_{n} \\ x_{n−1} \end{matrix} ) = A ( \begin{matrix}x_{n} \\ x_{n−1} \end{matrix} ) , where A = ( \begin{matrix}a & b \\ 1 & 0 \end{matrix} ) .

It follows that

( \begin{matrix}x_{n+1} \\ x_{n} \end{matrix} ) = A^{n} ( \begin{matrix}x_{1} \\ x_{0} \end{matrix} );

find the eigenvalues of A, by solving

| \begin{matrix}a − λ & b \\ 1 & −λ \end{matrix} | = 0, to give the equation λ^{2} − aλ − b = 0,

with roots λ_{1} and λ_{2}, say. This equation is known as the auxiliary equation of the recurrence relation; it corresponds to seeking a solution of the form x_{n} = λ^{n}. If λ_{1} and λ_{2} are distinct then for some matrix Λ we may write

A = Λ^{−1} ( \begin{matrix}λ_{1} & 0 \\ 0 & λ_{2} \end{matrix} ) Λ and then A^{n} = Λ^{−1} ( \begin{matrix}λ_{1}^{n} & 0 \\ 0 & λ_{2}^{n} \end{matrix} ) Λ,

so that the general solution of the homogeneous equation may be seen to be of the form x_{n} = Cλ_{1}^{n} + Dλ_{2}^{n} for some constants C and D. If the eigenvalues are not distinct, λ_{1} = λ_{2} = λ, then

A = Λ^{−1} ( \begin{matrix}λ & 1 \\ 0 & λ \end{matrix} ) Λ and then A^{n} = Λ^{−1} ( \begin{matrix}λ^{n} & nλ^{n−1} \\ 0 & λ^{n} \end{matrix} ) Λ,

and then the general solution of the homogeneous equation may be seen to be of the form x_{n} = λ^{n}(C + Dn) for some constants C and D. As before, if y_{n} is any particular solution of the inhomogeneous equation, the general solution is of the form x_{n} + y_{n} where x_{n} is the general solution of the homogeneous equation.

Example 3.29 Gambler’s ruin For the simple random walk, {S_{k}} may represent the fortune of a gambler after k plays of a game where on each play he either wins £1, with probability p, or loses £1 with probability q = 1−p; his initial fortune is £S_{0} and a classical problem is to calculate the probability that his fortune achieves the level a, a > S_{0}, before the time of ruin, that is the time that he goes bankrupt (his fortune hits the level 0). If T_{a} denotes the first time that the random walk hits the level a and T_{0} the time the random

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} • • • • • • • • • • • • • • • • • • • • • • • • •^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} S_{0}  k S_{k} a  T_{0} T_{a}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}

walk first hits the level 0, we would wish to calculate ℙ (T_{a} < T_{0}), given that his fortune starts at S_{0} = r, 0 < r < a. The figure illustrates a path of the random walk–although, in the case of the game, it finishes at the instant T_{0}, the time of bankruptcy! Let x_{r} = ℙ (T_{a} < T_{0}) when S_{0} = r, for 0 ⩽ r ⩽ a, so that we have the boundary conditions x_{a} = 1 and x_{0} = 0. A general rule in problems of this type in probability may be summed up as ‘condition on the first thing that happens’, which here would be a shorthand for using the Law of Total Probability to express the probability conditional on the outcome of the first play of the game, that is, whether X_{1} = 1 or X_{1} = −1, or equivalently, S_{1} = r+1 or S_{1} = r−1. Thus, for 0 < r < a,

\begin{aligned}x_{r} & = ℙ (T_{a} < T_{0} | S_{1} = r + 1) ℙ (X_{1} = 1) + ℙ (T_{a} < T_{0} | S_{1} = r − 1) ℙ (X_{1} = −1) \\ & = px_{r+1} + qx_{r−1}. \end{aligned}

The auxiliary equation for this recurrence relation is pλ^{2} − λ + q = 0, and since p + q = 1, this may be factored as (λ − 1)(pλ − q) = 0 to give roots λ = 1 and λ = q/p. Case p ≠ q: the roots are distinct and the general solution is of the form x_{r} = A+B (q/p)^{r} for some constants A and B; the boundary conditions at r = a and r = 0, fix A and B and we conclude that

x_{r} = ℙ (T_{a} < T_{0}) = \frac{1 − (q/p)^{r}}{1 − (q/p)^{a}} , for 0 ⩽ r ⩽ a.

Case p = q = \frac{1}{2}: here λ = 1 is a repeated root of the auxiliary equation so that the general solution of the recurrence relation is x_{r} = A + Br, which, after using the boundary conditions, leads to the solution x_{r} = r/a, 0 ⩽ r ⩽ a.

We do not know necessarily that at least one of T_{0} and T_{a} must be finite, but if we interchange p and q and replace r by a − r, (or just calculate directly as above) we may obtain, for S_{0} = r, 0 ⩽ r ⩽ a, that

ℙ (T_{0} < T_{a}) = \{ \begin{matrix}\frac{(q/p)^{r} − (q/p)^{a}}{1 − (q/p)^{a}} & when p ≠ q, \\ 1 − r/a & when p = q = \frac{1}{2}. \end{matrix}

It follows, in both cases, that P (T_{a} < T_{0}) + ℙ (T_{0} < T_{a}) = 1, so that at least one of the the two barriers, 0 or a, must be reached with certainty. □

Example 3.30 Probability of ruin From the previous calculation we may derive an expression for ℙ (T_{0} < ∞) given S_{0} = r > 0, which is the probability that ruin ever happens. We see that the event that ruin occurs may be written as

(T_{0} < ∞) = ⋃_{a=r+1}^{∞} (T_{0} < T_{a}) ;

the events in the union are expanding as a increases, so by the continuity of the probability on expanding events, we have

ℙ (T_{0} < ∞) = lim_{a→∞} ℙ (T_{0} < T_{a}) = \{ \begin{matrix}(q/p)^{r} & when p > q, \\ 1 & when p ⩽ q, \end{matrix}

so that ruin is certain except in the case when the probability of winning a play is strictly larger than \frac{1}{2}. □

Example 3.31 Expected duration of the game Suppose that the gambler plays either until his fortune reaches a or until he goes bankrupt, whichever is sooner. That is the number of plays is min (T_{0}, T_{a}) = T_{0} ∧ T_{a}. We will derive the expected length of the game, 𝔼 (T_{0} ∧ T_{a}), given that S_{0} = r, 0 ⩽ r ⩽ a, which we will denote by m_{r}. We do not know whether m_{r} is finite. Consider blocks of jumps of the random walk of length a, that is

\begin{matrix}X_{1} & X_{2} & ⋯ & X_{a} \\ X_{a+1} & X_{a+2} & ⋯ & X_{2a} \\ X_{2a+1} & X_{2a+2} & ⋯ & X_{3a} \\ ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

and for i ⩾ 1 set Y_{i} = 1 if either X_{(i−1)a+1} = X_{(i−1)a+2} = ⋯ = X_{ia} = 1 or X_{(i−1)a+1} = X_{(i−1)a+2} = ⋯ = X_{ia} = −1, otherwise Y_{i} = 0. Thus Y_{i} = 1 if and only if the ith block of plays is a run of all wins or all losses, and ℙ (Y_{i} = 1) = 1 − ℙ (Y_{i} = 0) = p^{a} + q^{a} = θ, say. If we let Z be the first i such that Y_{i} = 1, then Z has a geometric distribution ℙ (Z = j) = (1−θ)^{j−1}θ, j ⩾ 1, and so 𝔼 (Z) = 1/θ < ∞. But it is clear that T_{0} ∧T_{a} ⩽ aZ, hence we see that 𝔼 (T_{0} ∧ T_{a}) ⩽ a𝔼 (Z) < ∞. To compute m_{r}, we again condition on the first thing to happen, that is whether the first play is a win or loss, to see that for 0 < r < a,

m_{r} = p (1 + m_{r+1}) + q (1 + m_{r−1}) = 1 + pm_{r+1} + qm_{r−1}, with m_{0} = m_{a} = 0;

here the 1 in the recurrence relation counts the initial play of the game. The solution of the homogeneous equation is again m_{r} = A + B (q/p)^{r} when p ≠ q and m_{r} = A + Br for the case p = q = \frac{1}{2}. Case p ≠ q: look for a particular solution of the inhomogeneous equation with m_{r} = cr, then

cr = 1 + pc(r + 1) + qc(r − 1), so that c = 1/(q − p),

so that the general solution is m_{r} = r/(q −p)+A+B (q/p)^{r}, and after using the boundary conditions we have

m_{r} = \frac{r}{q − p} − (\frac{a}{q − p}) \frac{1 − (q/p)^{r}}{1 − (q/p)^{a}} .

Case p = q = \frac{1}{2}: a particular solution of the inhomogeneous equation is −r^{2}, so the general solution is m_{r} = A + Br − r^{2} and after using the boundary conditions we have m_{r} = r(a − r). □

10 February 2007