Probability Theory

Solutions to Selected Exercises

1 Review Questions in Combinatorics

2.

(a) Every combination is a sequence of length 7 over {1, …, 5}, in which every digit must appear at least once. By inclusion and exclusion, the number of such sequences is

∑_{k=0}^{5}(−1)^{k}\binom{5}{k}(5 − k)^{7} = 16, 800.

(b) The new combinations are sequences as in case (a), but the first two elements have to be distinct and their order is immaterial. Thus, from the result of the preceding part we have first to subtract the number of those sequences in which the first two entries are equal, which is

5 (5! + 4 · \binom{5}{2, 1, 1, 1}) = 1800,

and then divide by 2. Altogether, we obtain

\frac{16800 − 1800}{2} = 7500

possibilities.

3.

(a) k^{n}.

(b) Let A_{i} be the event that the ith processor is assigned at least one job, i = 1, 2, …, k, and A the event in the question. Clearly, A = ⋂_{i=1}^{k} A_{i}. By the principle of inclusion and exclusion, and using the symmetry of the events A_{i}, we have

\begin{aligned}P (\overline{A}) & = P (⋃_{i=1}^{k} \overline{A_{i}}) \\ & = kP (\overline{A_{1}}) − \binom{k}{2}P (\overline{A_{1}}\overline{A_{2}}) + … + (−1)^{k−1}\binom{k}{k}P (⋂_{i=1}^{k} \overline{A_{i}}) . \end{aligned}

Thus

\begin{aligned}P (A) & = 1 − P (\overline{A}) \\ & = 1 − k (1 − \frac{1}{k})^{n} + \binom{k}{2} (1 − \frac{2}{k})^{n} + … + (−1)^{k−2}\binom{k}{k − 1} · \frac{1}{k^{n}} . \end{aligned}

4.

(a) r^{n}.

(b) The first letter of the word may be any of the letters in Σ. In each of the other n−1 places we may put any of the r−1 letters distinct from the one in the preceding place. Hence there are r(r − 1)^{n−1} possibilities in all.

(c) Let a_{n} be the number of words not containing two consecutive occurrences of σ. The set of words in question consists of two disjoint subsets – those starting with σ, and those starting with some other letter. In the first set, each word may have any letter distinct from σ in the second place, and the remaining n − 2 letters must form a word of length n − 2 satisfying our condition. In the second set, each word may have any letter distinct from σ as the first letter, and the remaining n−1 letters must form a word of length n−1 satisfying our condition. Thus we have:

a_{n} = (r − 1)a_{n−2} + (r − 1)a_{n−1}, a_{0} = 1, a_{1} = r.

Solving the above recurrence relation, we obtain:

x^{2} + (r − 1)x − (r − 1) = 0.

Hence

a_{n} = c_{1}b_{1}^{n} + c_{2}b_{2}^{n},

where b_{1} = ^{\frac{r−1+\sqrt{(r−1)(r+3)}}{2}} and b_{2} = ^{\frac{r−1−\sqrt{(r−1)(r+3)}}{2}}. Substituting in the initial conditions a_{0} = 1, a_{1} = r, we obtain:

c_{1} = \frac{b_{2} − r}{b_{2} − b_{1}} , c_{2} = \frac{r − b_{1}}{b_{2} − b_{1}} .

(d) \binom{n}{n_{1}, n_{2}, …, n_{r}}.

(e) r^{[^{\frac{n+1}{2}}]}.

5.

(b) The generating function is f(x) = \frac{1}{1−2x}, and we obtain a_{n} = 2^{n}, n ≥ 0.

8. Since n! = e^{∑_{i=1}^{n} ln i} the inequality

e (\frac{n}{e})^{n} ≤ n! ≤ e (\frac{n + 1}{e})^{n+1}

is equivalent to

n ln n − n + 1 ≤ ∑_{i=1}^{n} ln i ≤ (n + 1) ln (n + 1) − n.

Since ∫ ln xdx = x ln x − x + c and the function ln x is increasing, we have

∫_{1}^{n} ln xdx ≤ ∑_{i=1}^{n} ln i ≤ ∫_{1}^{n+1} ln xdx,

which gives the required result.

9.

(b) Consider the 2nth row of Pascal’s triangle. The sum of all entries is 2^{2n}, and therefore each of them, in particular the middle entry \binom{2n}{n}, is less than 2^{2n}. On the other hand, it is easy to check that the binomial coefficients \binom{2n}{j} increase as j increases from 0 to n, and decrease from that place on. In particular, \binom{2n}{n} is the maximal entry in the row. Consequently:

\frac{2^{2n}}{2n + 1} ≤ \binom{2n}{n} ≤ 2^{2n} .

10. The set of binary trees on n vertices splits into n + 1 disjoint subsets, depending on the number vertices in the left subtree. For each k, the number of trees with k vertices at the left subtree (and thus n − k − 1 vertices at the right subtree) is C_{k} · C_{n−1−k}. Hence:

C_{n} = ∑_{k=0}^{n−1} C_{k}C_{n−1−k}, n ≥ 1,

with the initial condition C_{0} = 1. It follows that

f(x) = c_{0} + x ∑_{n=1}^{∞} (∑_{k=0}^{n−1} C_{k} · C_{n−1−k}) x^{n−1} = xf(x)^{2},

and therefore

xf(x)^{2} − f(x) + 1 = 0.

Consequently

f(x) = \frac{1 ± \sqrt{1 − 4x}}{2x} = \frac{1 ± (1 − 2 ∑_{k=1} ∞\binom{2(k−1)}{k−1} \frac{x^{k}}{k} )}{2x}.

Choosing the possibility with the minus sign, we obtain

f(x) = ∑_{n=0}^{∞} \binom{2n}{n}\frac{x^{n}}{n + 1},

so that C_{n} = \frac{1}{n+1} \binom{2n}{n}.

11.

(a) The set of all permutations which may be obtained by the system in the question decomposes into a union of disjoint subsets as follows. Consider the number of the step, between 2 and 2n at which the number 1 was moved from S to Q_{2}. The step number may be any even number in this range. Consider the set of permutations in which this move took place at the 2jth step. Thus, we moved the number 1 from Q_{1} to S at the first step, moved the next j−1 integers 2, 3, …, j from Q_{1} to Q_{2} (via S) in the next 2j − 2 steps, moved 1 from S to Q_{2} at the 2jth step, and then moved the remaining integers j + 1, j + 2, …, n from Q_{1} to Q_{2} in the next 2(n − j) steps. We had P_{j−1} possibilities for moving 2, 3, …, j and P_{n−j} possibilities for moving j + 1, j + 2, …, n. Consequenly, the sequence (P_{n}) satisfies the recurrence:

P_{n+1} = P_{0}P_{n} + P_{1}P_{n−1} + P_{2}P_{n−2} + … + P_{n−1}P_{1} + P_{n}P_{0}.

The sequence is completely determined by this recurrence and the initial condition P_{0} = 1.

(b) Let f(x) = ∑_{i=0}^{∞} P_{i}x^{i}. Solving the recurrence relation in the preceding part we have:

f(x) − P_{0} = x ∑_{n=0}^{∞} ∑_{i=0}^{n} P_{i}P_{n−i}x^{n} = xf^{2}(x),

which yields the solutions

f_{1}(x) = \frac{1 + \sqrt{1 − 4x}}{2x}

and

f_{2}(x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

Now \sqrt{1 − 4x} = ∑_{n=0}^{∞} \binom{1/2}{n}(−4x)^{n} = 1 − ∑_{n=1}^{∞} \frac{1}{2n−1} \binom{2n}{n}x^{n}. Since the P_{n}’s are positive, we have to select f_{2}(x) as the relevant solution. The generating function is then

f(x) = \frac{1}{2x} (1 − (1 − ∑_{n=1}^{∞} \frac{1}{2n − 1}\binom{2n}{n}x^{n})) = ∑_{n=0}^{∞} \frac{1}{n + 1}\binom{2n}{n}x^{n},

which gives

P_{n} = \frac{1}{n + 1}\binom{2n}{n}.

12.

(a) We need to make l + m moves, out of which l should be to the right and the other m upwards. Hence the number of possibilities is \binom{m+l}{l}.

(b) The problem is equivalent to the ballot problem, so that the number of possibilities is \binom{m+l}{l} − \binom{m+l}{l+1} if m ≤ k (and 0 otherwise).

(c) Clearly, the number of all walks going from (0, 0) to (l, m) is:

\begin{matrix}W_{l,m} = W_{l,m−1} + W_{l−1,m} + W_{l−1,m−1}, \\ W_{l,0} = W_{0,m} = 1, l, m ≥ 0. \end{matrix}

Thus

W_{l,m}x^{l}y^{m} = W_{l,m−1}x^{l}y^{m} + W_{l−1,m}x^{l}y^{m} + W_{l−1,m−1}x^{l}y^{m}

and

∑_{m=1}^{∞} ∑_{l=1}^{∞} W_{l,m}x^{l}y^{m} = y ∑_{m=1}^{∞} ∑_{l=1}^{∞} W_{l,m−1}x^{l}y^{m−1}+x ∑_{m=1}^{∞} ∑_{l=1}^{∞} W_{l−1,m}x^{l−1}y^{m}+xy ∑_{m=1}^{∞} ∑_{l=1}^{∞} W_{l−1,m−1}x^{l−1}y^{m−1},

or equivalently

f(x, y)−∑_{l=1}^{∞} W_{l,0}x^{l}−∑_{m=1}^{∞} W_{0,m}y^{m}−W_{0,0} = y (f(x, y) − ∑_{m=0}^{∞} W_{0,m}y^{m})+x (f(x, y) − ∑_{m=0}^{∞} W_{l,0}x^{l})+xyf(x, y).

Since W_{l,0} = W_{0,m} = 1 we obtain

f(x, y)−\frac{x}{1 − x}−\frac{y}{1 − y} −1 = y (f(x, y) − \frac{1}{1 − y} )+x (f(x, y) − \frac{1}{1 − x})+xyf(x, y),

which provides the result: f(x, y) = 1/(1 − x − y − xy).

2 Elementary Probability Calculations

18.

(a) For the event in question to occur, the first ⌈n/2⌉ tosses may have any outcomes, and then the other ⌊n/2⌋ tosses are uniquely determined by them. Hence the required probability is 2^{⌈n/2⌉}/2^{n} = 1/2^{⌊n/2⌋}.

(b) There are only two sequences satisfying the property, and hence the probability is \frac{2}{2^{n}} = \frac{1}{2^{n−1}} .

(c) For a non-negative integer n and a word w over {0, 1}, denote by a_{n,w} the number of words of length n starting with w and satisfying the requiremnts. It is easy to see that

a_{n,0} = a_{n,00} + a_{n,01} = a_{n,001} + a_{n,01} = a_{n−2,1} + a_{n−1,1}.

Due to symmetry, a_{n,w} = a_{n,\overline{w}}, where \overline{w} is the word obtained from w upon replacing each 0 by 1 and each 1 by 0. Therefore:

a_{n,0} = a_{n−2,0} + a_{n−1,0}.

The initial conditions are a_{0,0} = a_{1,0} = 1. It follows that a_{n,0} is Fibonacci’s sequence. Therefore the required probability is \frac{2F_{n}}{2^{n}} = \frac{F_{n}}{2^{n−1}} .

(d) If n is even the probability is = \binom{n}{n/2}/2^{n}, while if n is odd there are no sequences satisfying the condition, so that the probability is 0.

25. The sets A_{1} and A_{2} may be chosen in 2^{n} · 2^{n} = 4^{n} ways altogether. To satisfy the condition A_{1} ⋂ A_{2} = ∅, we have to require that each j ∈ {1, 2, …, n} belongs to at most one of the sets A_{1} and A_{2}. Thus we have 3 possibilities for each j, namely either j ∈ A_{1} ⋂ \overline{A}_{2} or j ∈ \overline{A}_{1} ⋂ A_{2} or j ∈ \overline{A}_{1} ⋂ \overline{A}_{2}. Hence the number of possibilities satisfying the requirement is 3^{n}. It follows that the probability of the event in question is (3/4)^{n}.

30. Due to symmetry, all 3! = 6 possible orderings of X_{1}, X_{2} and X_{3} are equi-probable, whence each has probability 1/6.

41.

(a) Since all the events in the union are disjoint, the probability is the sum of probabilities. Consequently:

P (⋃_{i=1}^{∞} [\frac{1}{2i + 1}, \frac{1}{2i}]) = ∑_{i=1}^{∞} (\frac{1}{2i} − \frac{1}{2i + 1}) = 1 − ln 2

.

(b) For any n, the set in question is contained in the set of numbers whose infinite decimal expansion does not contain the digit 7 in any of the first n places. The latter set is clearly of probability (9/10)^{n}. Thus the probability of our set is less than (9/10)^{n} for each n, and therefore it vanishes.

(c) As in the preceding part, the probability is 0.

43.

(a) Let us show that:

lim sup_{n→∞} A_{n} = [0, 2],  lim inf_{n→∞} A_{n} = [1/2, 1].

Indeed, if x ∈ [0, 1], then x ∈ A_{n} for each even n, while if x ∈ [1, 2], then x ∈ A_{n} for each odd n, so that lim sup_{n→∞} A_{n} ⊇ [0, 2]. On the other hand, if x < 0, then x ∉ A_{n} for any n, while if x > 2 then x ∉ A_{n} for n > \frac{1}{x−2}. This gives the inverse inclusion lim sup_{n→∞} A_{n} ⊆ [0, 2]. If x ∈ [1/2, 1], then x ∈ A_{n} for each n, and in particular lim inf_{n→∞} ⊇ [1/2, 1]. If x < 1/2, then x ∉ A_{n} for any odd n, while if x > 1 then x ∉ A_{n} for odd n > \frac{1}{x−1}. Therefore lim inf_{n→∞} ⊆ [1/2, 1].

(b) A point belongs to lim sup_{n→∞} A_{n} if it belongs to infinitely many of the events A_{n}, which happens if and only if it belongs to the union ∪_{i=k}^{∞}A_{i} for each k. It follows that

lim sup_{n→∞} A_{n} = ∩_{k=1}^{∞} ∪_{i=k}^{∞} A_{i},

which representation proves that lim sup_{n→∞} A_{n} is an event. Similarly

lim inf_{n→∞} A_{n} = ∪_{k=1}^{∞} ∩_{i=k}^{∞} A_{i},

which proves that lim inf_{n→∞} A_{n} is an event.

46.

(a) The number of all subsets of A is of size 2^{n}. Thus Equivalently, we have to calculate the sum of those binomial coefficients \binom{n}{k} with even k. Since the expression \frac{1+(−1)^{k}}{2} takes the value 1 for even k and vanishes for odd k, we have:

∑_{2|k} \binom{n}{k} = ∑_{k=0}^{n} \frac{1 + (−1)^{k}}{2} \binom{n}{k}

= \frac{1}{2} ∑_{k=0}^{n} \binom{n}{k} + \frac{1}{2} ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}

= \frac{1}{2} · 2^{n} + \frac{1}{2} · (1 − 1)^{n} = 2^{n−1}.

Consequently the required probability is \frac{1}{2}.

(b) A simple calculation yields:

1 + ω^{k} + ω^{2k} = \{ \begin{matrix}3, & 3|k, \\ 0, & 3 ∤ k. \end{matrix}

Consequently:

∑_{3|k} \binom{n}{k} = ∑_{k=0}^{n} \frac{1 + ω^{k} + ω^{2k}}{3} \binom{n}{k}
= \frac{1}{3} [2^{n} + (1 + ω)^{n} + (1 + ω^{2})^{n}]
= \frac{2^{n} + (−ω^{2})^{n} + (−ω)^{n}}{3} .

Hence the probability for |R| to be divisible by 3 is

\frac{1}{3} [1 + \frac{(−ω^{2})^{n} + (−ω)^{n}}{2^{n}} ] .

Similarly, to find the probability for |R| to be 1 modulo 3, we calculate:

1 + ω^{2}ω^{k} + ωω^{2k} = \{ \begin{matrix}3, & k ≡ 1(mod 3), \\ 0, & otherwise. \end{matrix}

Hence

∑_{k≡1(mod 3)} \binom{n}{k} = ∑_{k=0}^{n} \frac{1 + ω^{2}ω^{k} + ωω^{2k}}{3} \binom{n}{k}
= \frac{1}{3} [2^{n} + ω^{2}(1 + ω)^{n} + ω(1 + ω^{2})^{n}]
= \frac{2^{n} + ω^{2}(−ω^{2})^{n} + ω(−ω)^{n}}{3} .

and the probability is \frac{1}{3} [1 − \frac{(−ω^{2})^{n+1} + (−ω)^{n+1}}{2^{n}} ] .

(c)

P (|R| ≡ i(mod 4)) = \begin{cases}\frac{2^{n}+(1+i)^{n}+(1−i)^{n}}{2^{n+2}} & i = 0 \\ \frac{2^{n}−i(1+i)^{n}+i(1−i)^{n}}{2^{n+2}} & i = 1 \\ \frac{2^{n}−(1+i)^{n}−(1−i)^{n}}{2^{n+2}} & i = 2 \\ \frac{2^{n}+i(1+i)^{n}−i(1−i)^{n}}{2^{n+2}} & i = 3 \end{cases}

(a) The problem is equivalent to the problem regarding 2n people, n with $10 bills and n with $5 bills, waiting in line to but tickets for a show, which has been solved in class. Hence the required

probability is \frac{1}{n + 1} .

(b) The number of legal expressions is the same as in the preceding

part, namely \frac{\binom{2n}{n}}{n + 1} , . However, this time the total number of

possibilities is 2^{2n}. Thus the required probability is \frac{\binom{2n}{n}}{(n + 1)2^{2n}} .

3 Conditional Probability

4 Discrete Distributions

87.

(c) For any c > 0 the values assumed by p(x) are non-negative. The value of c is determined by the requirement that their sum be

1. First let us decompose the given rational function. Namely, we are looking for constants a, b and d for which:

\frac{1}{x(x + 1)(x + 2)} = \frac{a}{x} + \frac{b}{x + 1} + \frac{d}{x + 2} .

This gives:

a(x + 1)(x + 2) + bx(x + 2) + dx(x + 1) = 1.

Making the substitutions x = 0, x = −1 and x = −2 we obtain:

2a = 1,  −b = 1,  2d = 1,

and therefore

a = \frac{1}{2},  b = −1,  d = \frac{1}{2} .

Hence:

∑_{x=1}^{∞} \frac{1}{x(x + 1)(x + 2)} = ∑_{x=1}^{∞} (\frac{1/2}{x} − \frac{1}{x + 1} + \frac{1/2}{x + 2}) = \frac{1/2}{1}−\frac{1}{2}+\frac{1/2}{2} = \frac{1}{4} .

Thus c = 4.

5 Expectation

96.

(b)

\begin{aligned}E(X) & = ∑_{k=0}^{n} 2^{k}\binom{n}{k}p^{k}(1 − p)^{n−k} = ∑_{k=0}^{n} \binom{n}{k}(2p)^{k}(1 − p)^{n−k} \\ & = (2p + (1 − p))^{n} = (1 + p)^{n}. \end{aligned}

(c)

E(X) = ∑_{k=0}^{n} sin k\binom{n}{k}p^{k}(1 − p)^{n−k} = ∑_{k=0}^{n} \frac{e^{ik}−e^{−ik}}{2i} \binom{n}{k}p^{k}(1 − p)^{n−k}
= \frac{1}{2i} (∑_{k=0}^{n} \binom{n}{k}(pe^{i})^{k}(1 − p)^{n−k} − ∑_{k=0}^{n} \binom{n}{k}(pe^{−i})^{k}(1 − p)^{n−k})
= \frac{1}{2i} ((pe^{i} + 1 − p)^{n} − (pe^{−i} + 1 − p)^{n}) .

99.

(a) Let A_{k}, 1 ≤ klen, denote the event whereby k is the largest number in the sample. Then

P (A_{k}) = \frac{k^{n} − (k − 1)^{n}}{N^{n}} ,

and therefore

E(X) = \frac{1}{N^{n}} ∑_{k=1}^{N} k(k^{n} − (k − 1)^{n}).

It follows that:

E(X) = \frac{1}{N^{n}} (N^{N+1} − ∑_{k=1}^{N−1} k^{n}) = N − ∑_{k=1}^{N−1} (\frac{k}{N} )^{n} .

(b) Write E(X) in the form:

E(X) = N − N ∑_{k=0}^{N−1} \frac{1}{N} (\frac{k}{N} )^{n} .

The sum on the right hand side is a Darboux sum corresponding to the integral ∫_{0}^{1} x^{n}dx. Hence E(X) behaves asymptotically as N − \frac{N}{n+1}.

(c) As n becomes large, all the terms in the sum on the right hand side of the expression for E(X) tend to 0, and therefore E(X) tends to N.

(a) If the envelope we took contains an amount x, then it is in principle possible that the value x was selected from the distribution, in which case the other envelope contains an amount of 2x, and it is possible that only x/2 was selected and we received the second envelope, in which case the other envelope is the first and so contains only x/2. Now the probability for the first event is (using conditional probabilities)

\frac{p(x) · \frac{1}{2}}{p(x) · \frac{1}{2} + p(x/2) · \frac{1}{2}} = \frac{p(x)}{p(x) + p(x/2)} .

The probability in this case that x/2 was selected is therefore

\frac{p(x/2)}{p(x) + p(x/2)} . Hence our expected prize if we switch to the

other envelope is

\frac{p(x)}{p(x) + p(x/2)} · 2x + \frac{p(x/2)}{p(x) + p(x/2)} · \frac{x}{2} .

Therefore we should indeed switch if and only

\frac{p(x)}{p(x) + p(x/2)} · 2x + \frac{p(x/2)}{p(x) + p(x/2)} · \frac{x}{2} > x

(where in the case of equality we are actually indifferent between the two options). A routine simplification yields the equivalent condition 2p(x) > p(x/2).

(b) For the distribution in (i) we have the condition in (a) is satisfied for every possible value of x, and we should always switch. For the distribution in (ii), the condition is satisfied only for x = 2, so we should switch only in this case. (Notice that in this latter case we are actually certain that the other envelope contains an amount of 4, as otherwise it would mean that the value 1 had been selected, which is impossible.)

106. Denote by D the distance between v_{1} and v_{2}. Since P (D = 1) = p:

E(D) ≥ 1 · P (D = 1) + 2 · P (D ≥ 2) = p + 2(1 − p) = 2 − p.

On the other hand, by the solution of Problem 50 we have

P (D ≥ 3) ≤ (n − 2) · (1 − p^{2})^{n−2} ,

and consequently:

E(D) ≤ 1 · P (D = 1) + 2 · P (D ≥ 2) + n · P (D ≥ 3)
≤ p + 2(1 − p) + n(n − 2) · (1 − p^{2})^{n−2} ⟶_{n→∞} 2 − p.

Thus E(D) ⟶_{n→∞} 2 − p.

110.

(Algorithm a) Denote by “success” the event that an n-tuple forms a permutation. The probability for this event is p = \frac{n!}{n^{n}}. The number of selections of n-tuples is distributed G(p). Hence the expected number of selections is

\frac{1}{p} = \frac{n^{n}}{n!} .

Since each selection consists of n integers, the expected number of random integers by this algorithm is \frac{n^{n+1}}{n!} . , which is

approximately \sqrt{\frac{2π}{n}}e^{n}.

(Algorithm b) Denote by X_{i} the number of steps required to obtain the i-th digit, i = 1, … n. Clearly, X_{i} ∼ G(1 − (i − 1)/n), and therefore

E(X_{i}) = \frac{n − i + 1}{n} , i = 1, …, n.

The total number of selections is X = ∑_{i=1}^{n} X_{i}, and hence:

E(X) = ∑_{i=1}^{n} E(X_{i}) = ∑_{i=1}^{n} \frac{n − i + 1}{n} = n (1 + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n}) .

This time the expected number of selections is only about n log n.

112. For 0 ≤ i ≤ n, denote by X_{i} the diameter of the graph obtained after the ith stage of the construction process. With this notation, we have to bound E(X_{n}) from below. Denote:

D_{i} = X_{i} − X_{i−1}, 1 ≤ i ≤ n.

Obviously D_{1} = 0 and D_{2} = 1. For i ≥ 3 we have D_{i} = 1 if at the ith stage we connect the selected vertex to a vertex which is at a distance X_{i−1} from some vertex of the graph we have after the (i − 1)st stage; otherwise – D_{i} = 0. Since the diameter after the (i − 1)st stage is X_{i−1}, there are at least two vertices at that point satisfying this condition, so that

P (D_{i} = 1) ≥ \frac{2}{i − 1} .

Hence:

E(X_{n}) = ∑_{i=1}^{n} E(D_{i}) ≥ 0 + 1 + ∑_{i=3}^{n} \frac{2}{i − 1}
= 2(1 + 1/2 + 1/3 + … + 1/(n − 1)) − 1.

6 Continuous Distributions

119. Obviously, X is distributed Cauchy.

7 Variance and Covariance

134. Let X denote the number of ones. Then X = ∑_{i=1}^{n} X_{i}, where X_{i} = 1 if the outcome of the ith roll is 1 and X_{i} = 0 otherwise. Let Y and Y_{i}, 1 ≤ i ≤ n, be defined similarly for the sixes. Obviously, X, Y ∼ B(n, 1/6), so that:

E(X) = E(Y) = \frac{n}{6} .

Now

E(XY) = E (∑_{i=1}^{n} X_{i} · ∑_{j=1}^{n} Y_{j})

= ∑_{i,j=1}^{n} E(X_{i}Y_{j}) = ∑_{i≠j} E(X_{i})E(Y_{j}) + ∑_{i=1}^{n} E(X_{i}Y_{i})

= n(n − 1) · \frac{1}{6} · \frac{1}{6} + ∑_{i=1}^{n} 0 = \frac{n(n − 1)}{6} ,

and therefore

Cov(X, Y) = \frac{n(n − 1)}{6} − \frac{n}{6} · \frac{n}{6} = −\frac{n}{36} .

135.

(a) Obviously, X ∼ H(m, a, b), Y ∼ H(n, a, b), and therefore

E(X) = \frac{ma}{a + b} , V (X) = \frac{mab}{(a + b)^{2}} (1 − \frac{m − 1}{a + b − 1}) ,

and

E(Y) = \frac{na}{a + b} , V (Y) = \frac{nab}{(a + b)^{2}} (1 − \frac{n − 1}{a + b − 1}) .

(b) Write X = ∑_{i=1}^{n} X_{i}, where X_{i} = 1 if the ith ball is white and X_{i} = 0 otherwise. Write Y = ∑_{i=1}^{n} Y_{i}, analogously for the second batch. Then

E(XY) = E (∑_{i=1}^{m} X_{i} · ∑_{j=1}^{n} Y_{j})

= ∑_{i=1}^{m} ∑_{j=1}^{n} E(X_{i}Y_{j}) = mn\frac{a(a − 1)}{(a + b)(a + b − 1)} ,

so that

Cov(X, Y) = mn\frac{a(a − 1)}{(a + b)(a + b − 1)} − \frac{ma}{a + b} · \frac{na}{a + b}
= −\frac{mnab}{(a + b)^{2}(a + b − 1)} .

(c) The covariance is negative since the more white balls there are in the first batch the less we should expect to have in the second.

8 Multi-Dimensional Distributions

9 Independence

10 Normal Distribution 11 Limit Theorems 12 The Moment Generating Function