Probability Theory

Solutions to Selected Exercises

1 Review Questions in Combinatorics

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} .

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}.

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].

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}} ] .

(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

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.

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.