Massachusetts Institute of Technology Handout 65 6.042J/18.062J: Mathematics for Computer Science December 8, 1998 Professors Nancy Lynch and Srinivas Devadas

Sample Problems

Note: This handout contains problems (with solutions) on the material at the end of the term, which was not covered by problem sets.

Problem 1. A couple plans to have children until they have a boy. What is the expected number of children that they have, and what is the variance?

Solution: The probability of having a single child (a boy) is \frac{1}{2}, the probability of having two children (a girl and then a boy) is \frac{1}{4}, and so forth; the probability of having k children is \frac{1}{2^{k}}. Therefore, the expected number of children is:

Ex(children) = ∑_{k=1}^{∞} k · \frac{1}{2^{k}}
= 2

Similarly, we can compute the variance as follows:

Var(children) = Ex(children^{2}) − Ex(children)^{2}
= ∑_{k=1}^{∞} k^{2} · \frac{1}{2^{k}} − (∑_{k=1}^{∞} k · \frac{1}{2^{k}} )^{2}
= 6 − 2^{2}
= 2

The sums above are computed using the trick of differentiating the formula for the sum of an infinite geometric sequence.

Problem 2. Let X and Y be independent random variables taking on integer values in the range 1 to n uniformly. Compute the following quantities.

(a) Var(aX + bY)

Solution: First, we can simplify this expression using standard rules.

Var(aX + bY) = Var(aX) + Var(bY)
= a^{2}Var(X) + b^{2}Var(Y)
= (a^{2} + b^{2})Var(X)

The first step uses the fact that the variance of a sum of independent random variables is equal to the sum of the variances. The second step uses the fact that multiplying a random variable by a constant multiplies the variance by the square of that constant. The final step is simplification, using the fact that X and Y must have the same variance, because they are indentically distributed. What remains is to compute Var(X). The calculation is carried out below.

Var(X) = Ex(X^{2}) − Ex(X)^{2}
= ∑_{i=1}^{n} i^{2} · \frac{1}{n} − (∑_{i=1}^{n} i · \frac{1}{n})^{2}

= \frac{(n + 1)(2n + 1)}{6} − \frac{(n + 1)^{2}}{4}
= \frac{n^{2} − 1}{12}

Substituting in this result gives a complete formula for the variance.

Var(aX + bY) = (a^{2} + b^{2})Var(X)
= (a^{2} + b^{2}) · \frac{n^{2} − 1}{12}

(b) Ex(max(X, Y))

Solution: We begin with the definition of expectation.

Ex(max(X, Y)) = ∑_{i=i}^{n} i · Pr(max(X, Y) = i)

To proceed, we must compute Pr(max(X, Y) = i), the probability that the maximum of X and Y is equal to i. This is done below.

Pr(max(X, Y) = i) = Pr(X = i ∩ Y < i) +
Pr(X < i ∩ Y = i) +
Pr(X = i ∩ Y = i)
= Pr(X = i) · Pr(Y < i) +
Pr(X < i) · Pr(Y = i) +
Pr(X = i) · Pr(Y = i)
= (\frac{1}{n} · \frac{i − 1}{n}) + (\frac{i − 1}{n} · \frac{1}{n}) + (\frac{1}{n} · \frac{1}{n})
= \frac{2i − 1}{n^{2}}

Substituting this result into the formula above gives:

Ex(max(X, Y)) = ∑_{i=i}^{n} i · \frac{2i − 1}{n^{2}}

= \frac{1}{n^{2}} · ∑_{i=1}^{n} 2i^{2} − i

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

(c) Ex(min(X, Y))

Solution: Note that max(X, Y) + min(X, Y) = X + Y. Taking the expected value of both sides of this equation, applying linearity of expectation, and shuffling terms gives:

Ex(min(X, Y)) = Ex(X) + Ex(Y) − Ex(max(X, Y))
= \frac{n + 1}{2} + \frac{n + 1}{2} − \frac{(n + 1)(4n − 1)}{6n}
= \frac{(n + 1)(2n + 1)}{6n}

(d) Ex(|X − Y |)

Solution: We could compute this in a straightforward way from the definition of expected value. However, we use a trick instead. Note that |X − Y | = max(X, Y) − min(X, Y). We now get the answer by taking the expected value of both sides and substituting the results from above.

Ex(|X − Y |) = Ex(max(X, Y) − min(X, Y))
= Ex(max(X, Y)) − Ex(min(X, Y))
= \frac{(n + 1)(4n − 1)}{6n} − \frac{(n + 1)(2n + 1)}{6n}
= \frac{n^{2} − 1}{3n}

(e) Var(|X − Y |).

Solution: We start with one of the standard formulas for variance.

Var(|X − Y |) = Ex(|X − Y |^{2}) − Ex(|X − Y |)^{2}
= Ex((X − Y)^{2}) − Ex(|X − Y |)^{2}

We could procede from here by brute force, using the definition of expectation. But note that this expression for the variance of |X − Y | is quite close to the expression for the variance of X − Y obtained from the same formula.

Var(X − Y) = Ex((X − Y)^{2}) − Ex(X − Y)^{2}
= Ex((X − Y)^{2})

By substituting one equation into the other, we obtain the following formula for the desired variance.

Var(|X − Y |) = Var(X − Y) − Ex(|X − Y |)^{2}

The quantities on the right side of the this equation were computed earlier. Plugging in these results, we have:

Var(|X − Y |) = Var(X − Y) − Ex(|X − Y |)^{2}
= (1^{2} + (−1)^{2}) · \frac{n^{2} − 1}{12} − (\frac{n^{2} − 1}{3n})^{2}
= \frac{(n^{2} − 1)(n^{2} + 2)}{18n^{2}}

Problem 3. (a) Let X be a random variable whose value is an observation drawn uniformly at random from the {i ∈ ℕ | −n ≤ i ≤ n}. Let Y = X^{2}. Show that X and Y are not independent, but that Ex[XY] = Ex[X]Ex[Y]. Solution: Since Y is determined by X, there are many cases indicating where X and Y are not independent, e.g.,

Pr(Y = 0) = 1/(2n + 1), but Pr(Y = 0 | X = 0) = 1.

To see that Ex[XY] = Ex[X]Ex[Y], note that Ex[X] = 0 and Ex[XY] = Ex[X^{3}] = 0 since X and X^{3} are both symmetrical.

(b) Show that in general for any two random variables X and Y that if Ex[XY] = Ex[X]Ex[Y] then Var(X + Y) = Var(X) + Var(Y). In particular, this shows that it is possible for nonindependent variables to have variances that exhibit linearity. Solution: We have that Var(X + Y) = Ex((X + Y)^{2}) − (Ex(X + Y))^{2} = Ex(X^{2} + 2XY + Y^{2})−(Ex(X)+Ex(Y))^{2} = Ex(X^{2})−(Ex(X))^{2}+Ex(Y^{2})−(Ex(Y))^{2}+2Ex(XY)− 2Ex(X)Ex(Y) = Var(X) + Var(Y).

Problem 4. Suppose that someone is infected with an unknown incurable contagious disease. Everyday he encounters n healthy people and infects each of them with probability p. Encounters are mutually independent. These people in turn meet n people and infect them with probability p and so on.

(a) Write a recurrence for the expected number of people on the k + 1st day in terms of the expected number of people on the kth day. Assume that each day every sick person meets n different persons. Solution: Let S_{k} be a random variable giving the number infected people after k days. We can write a recurrence for S_{k+1} in terms of S_{k}.

Let the sick people after day k be numbered 1, …, S_{k}. Let H_{i} be a random variable giving the number of healthy people infected by sick person i in one day. Then H_{i} has a binomial distribution with parameters n and p. Then:

S_{k+1} = S_{k} + ∑_{i=1}^{S_{k}} H_{i}

It follows from linearity of expectation that

Ex[S_{k+1}] = Ex[S_{k}] + Ex[∑_{i=1}^{S_{k}} H_{i}].

Then by Wald’s theorem,

Ex[S_{k+1}] = Ex[S_{k}] + Ex[S_{k}] · Ex[H]

where H is a variable with the binomial distribution with parameters n and p. Thus, Ex[H] = np.

So

Ex[S_{k+1}] = Ex[S_{k}] + Ex[S_{k}] · np = (1 + np)Ex[S_{k}]

Also, Ex[S_{0}] = 1. So we have a recurrence involving these expectations. Writing e_{i} for Ex[S_{i}], we have:

e_{k+1} = (1 + np)e_{k}

and

e_{0} = 1

(b) Solve the recurrence of part (a). Solution: e_{k} = (1 + np)^{k}.

(c) Now suppose that any sick person recovers from the disease each day with probability r. Find the expected number of sick people on the kth day. Solution: Let B_{i} be the indicator variable for whether the i^{th} sick person gets better. Then Ex[B_{i}] = r. Then

S_{k+1} = S_{k} + ∑_{i=1}^{S_{k}}(H_{i} − B_{i})

It follows that

Ex[S_{k+1}] = Ex[S_{k}] + Ex[S_{k}] · Ex[H] − Ex[S_{k}]Ex[B_{i}]

and so

e_{k+1} = e_{k}(1 + np − r)
= (1 + np − r)^{k}

Problem 5. A miner, lost in some abandoned mine, finds himself in a room containing three doors. Door 1 leads him to freedom after two hours travel; door 2 returns him to the same room after four hours travel, and door 3 returns him to the room after eight hours travel. Each time he finds himself in the room, the miner picks a door with equal probability. Let T denote the time until he finds the exit.

(a) Define a sequence of iid random variables X_{i} and a stopping rule N such that

T = ∑_{i=1}^{N} X_{i}

Solution: We view this as an experiment where at each step we make a choice between three equiprobable outcomes. Let X_{i} = number of hours to return to room on ith step. Let N = number of steps until good door is selected. Then N is geometrically distributed with probability 1/3.

(b) Use Wald’s Identity to find Ex[T] Solution: Pr(X_{i} = 2) = 1/3 Pr(X_{i} = 4) = 1/3 Pr(X_{i} = 8) = 1/3 Ex[X_{i}] = 14/3 Ex[N] = 3 By Wald’s Identity

Ex[∑_{i=1}^{N} X_{i}] = 14

Problem 6. In this problem, we analyze probabilistically the 1st stage of bubble sort performed on a list of n integers {i_{1}, … i_{n}}. We assume that all the integers are distinct. On the first step we compare integers i_{1} and i_{2}. If i_{1} > i_{2} we swap them otherwise we leave them as they are. On step k (2 ≤ k ≤ n − 1), we compare the new i_{k} with i_{k+1}. If i_{k} > i_{k+1} we swap else we leave them as they are. We assume that the order of the integers is chosen uniformly from all possible orderings.

(a) If a number x is randomly (uniformly) chosen from a set of n distinct numbers, what is the probability that x is the largest number in the set? What is the probability that on the kth step (2 ≤ k ≤ n − 1), i_{k+1} is the biggest integer to appear in the list so far? Solution: Pr(choosing largest of n numbers) = 1/n. Pr(i_{k+1} in k step is highest so far) = 1/(k + 1).

(b) Let C_{k} be a random variable that is equal to 1 if i_{k+1} > i_{k}. What is Ex[C_{k}]? Solution:

Ex[C_{k}] = Pr(C_{k} = 1) = Pr( i_{k} is highest so far) = \frac{1}{k + 1}.

(c) Let random variable C = ∑_{k=1}^{n} C_{k}. Give an asymptotic bound for Ex[C] as well as an interpretation of what Ex[C] is. Solution:

Ex[C] = ∑_{k} Ex[C_{k}] = ∑_{k=2}^{n} \frac{1}{k} ∼ ln n.

C is the total number of swaps, so Ex[C] is the expected number of swaps.

Problem 7. Consider the following 3-stage experiment:

In the first stage, I throw a 6-sided die. The number of spots that I get determines how many instances of the second stage to perform.

In the second stage, I throw a 6-sided die. This stage is repeated once for each spot I got in the first stage. The total number of spots that I get in this stage determines how many instances of the third stage to perform.

In the third stage, I throw a 6-sided die. This stage is repeated once for each spot I got in all instances of the second stage.

For example, if the outcome of the first stage is 3, then stage 2 gets played 3 times. Suppose the outcomes of the 3 instances of stage 2 are 1, 3, 4. Then stage 3 is played 1 + 3 + 4 = 8 times, and the score is the sum of 8 instances of stage 3.

Assume that all throws are mutually independent.

My score is the total number of spots on all the instances of the third stage.

What is my expected score?

(Analyze this as carefully as you can, using Wald’s theorem. Try to be careful about uses of independence.)

Solution:

Let X be the random variable whose value is the roll in the first stage. Let Y_{1}, Y_{2}, …, Y_{X} be the random variable whose values are the rolls in the second stage. Define Y = Y_{1} +⋯+Y_{X}. Let Z_{1}, Z_{2}, …, Z_{Y} be the random variable whose values are the rolls in the third stage. Define Z = Z_{1} + ⋯ + Z_{Y}. We want to find Ex[Z]. Now all the rolls are mutually independent, so we can use Wald’s theorem to get Ex[Y] = Ex[X]Ex[Y_{i}] = (7/2)^{2}. Since Y is determined by rolls that are independent of the rolls in the third stage, Y and Z_{i} are independent. So we apply Wald‘s theorem again to get Ex[Z] = Ex[Y]Ex[Z_{i}] = (7/2)^{3}.

The answer is (7/2)^{3}.

Problem 8. Suppose you flip a fair coin 100 times. The coin flips are all mutually independent. What is an upper bound on the probability that the number of heads is at least 70 …

(a) … according to Markov’s Inequality? Solution: The expected number of heads of 50. So the probability that the number of heads is at least 70 is at most 50/70 = 0.71.

(b) … according to Chebyshev’s Inequality? Solution: Let X_{i} be the random variable whose value is 1 if the ith coin flip is heads. Then Var[X_{i}] = 1/2−(1/2)^{2} = 1/4. So Var[X_{1}+⋯+X_{1}00] = 100/4 = 25. The variance of the number of heads is 100/4 = 25, so the standard deviation is 5. So 70 is four times the standard deviation from the mean. Since the distribution is symmetric, the probability is at most \frac{1}{2} · \frac{1}{4^{2}} = \frac{1}{32}

(c) … according to Chernoff’s Bound? Solution: We apply Chernoff‘s bound with c = 70/50 = 1.4. This gives us that α = ln(1.4) + 1/1.4 − 1 = 0.05076 and that the probability is at most e^{−0.05076·1.4·50} = 0.0286.

Problem 9. Let S be a sample space. Say random variable X : S → ℕ has distribution

X = \{ \begin{matrix}2 & with probability 1/4, \\ 3 & with probability 1/4, \\ 5 & with probability 1/2; \end{matrix}

and random variable Y : S → ℕ has distribution

Y = \{ \begin{matrix}1 & with probability 2/3, \\ 4 & with probability 1/3; \end{matrix}

where X and Y are independent.

Let random variable Z : S → ℕ be given by Z = max(X, Y).

(a) What is the expected value of Z? Solution: We first compute the values of Z along with their associated probabilities. Note that P (X = x & Y = y) = P (X = x)P (Y = y) since X and Y are independent.

\begin{matrix}X & Y & Z & Z^{2} & Pr \\ 2 & 1 & 2 & 4 & \frac{1}{6} \\ 3 & 1 & 3 & 9 & \frac{1}{6} \\ 5 & 1 & 5 & 25 & \frac{1}{3} \\ 2 & 4 & 4 & 16 & \frac{1}{12} \\ 3 & 4 & 4 & 16 & \frac{1}{12} \\ 5 & 4 & 5 & 25 & \frac{1}{6} \end{matrix}

Now

E(Z) = 2 · \frac{1}{6} + 3 · \frac{1}{6} + 5 · \frac{1}{3} + 4 · \frac{1}{12} + 4 · \frac{1}{12} + 5 · \frac{1}{6} = 4

(b) What is the variance of Z? Solution: Recall that VarZ = E(Z^{2}) − E(Z)^{2}. So we first compute E(Z^{2}) using the data from the above table

E(Z^{2}) = 4 · \frac{1}{6} + 9 · \frac{1}{6} + 25 · \frac{1}{3} + 16 · \frac{1}{12} + 16 · \frac{1}{12} + 15 · \frac{1}{6} = \frac{52}{3}

Finally Var(Z) = 52/3 − 16 = \frac{4}{3}.

Problem 10. (a) Show that if random variables X and Y are independent then Cov(X, Y) = 0 Solution:

First we show that if X and Y are independent, then E(XY) = E(X)E(Y).

E(XY) = ∑_{x,y} xyP (X = x & Y = y)
= ∑_{x} ∑_{y} xyP (X = x & Y = y)
= ∑_{x} ∑_{y} xyP (X = x)P (Y = y)
= ∑_{x} xP (X = x) ∑_{y} yP (Y = y)
= ∑_{x} xP (X = x)E(Y)
= E(Y) ∑_{x} xP (X = x)
= E(X)E(Y)

Since Cov(X, Y) = E(XY) − E(X)E(Y), Cov(X, Y) = 0.

(b) Show that having Cov(X, Y) = 0 does not necessarily mean that X and Y are independent. Solution: Let (X, Y) have joint probability given by the table below:

\begin{matrix}X & Y & P \\ −1 & 1 & \frac{1}{3} \\ 0 & 0 & \frac{1}{3} \\ 1 & 1 & \frac{1}{3} \end{matrix}

Note that X and Y are not independent. P (X = 1 & Y = 1) = \frac{1}{3} ≠ \frac{2}{9} = P (X = 1)P (Y = 1). But E(X) = 0 and E(XY) = 0 (since XY = X). Thus Cov(X, Y) = 0.