Massachusetts Institute of Technology Handout ?? 6.042J/18.062J: Mathematics for Computer Science May 5, 2000 Professors David Karger and Nancy Lynch

Problem Set 10.5 Solutions

Problems

Problem 1 Eight men and seven women, all single, happen randomly to have purchased single seats in the same 15-seat row of a theater.

(a) What is the probability that the first two seats contain a marriageable couple, i.e., a single man next to a single woman?

Solution.

There are \binom{15}{2} = 105 possible pairs that could occupy the first two seats, only 8 · 7 = 56 of which are marriageable couples. So the probability is 56/105 = 8/15.

□

(b) What is the expected number of pairs of adjacent seats which contain marriageable couples? (For example, if the sequence of men and women in the seats is

MMMWMMMMWWWWWWM,

then there are four possible couples sitting in the pairs of adjacent seats that start at the 3rd, 4th, 7th and 14th seats, respectively.)

Solution.

Let the random variable S be the number of pairs of seats containing a marriageble couple; we want to find E [S]. Let A_{i} be the event “there is a marriageable couple in seats i and i + 1,” and S_{i} be the indicator random variable for A_{i}; that is, S_{i} = 1 if A_{i} and S_{i} = 0 otherwise. Then S = ∑_{i=1}^{14} S_{i}.

Since S_{i} is the indicator random variable for A_{i}, E [S_{i}] = Pr(A_{i}). Since each pair of seats is like any other, Pr(A_{i}) = Pr(A_{1}) = 8/15, as we computed in the previous part. Because expectation is linear,

E [S] = ∑_{i=1}^{14} E [S_{i}] = 14 · \frac{8}{15}.

Note that this works even though the S_{i}’s are not independent. That’s the beauty of linearity of expectation!

□

Problem 2 One hundred twenty students take the 6.042 final exam. The mean on the exam is 90 and the lowest score was 30. You have no other information about the students and the exam, e.g., you should not assume that the final is worth 100 points.

2 Handout ??: Problem Set 10.5 Solutions

(a) State the best possible upper bound on the number of students who scored at least 180. Solution. Let R be the score of a student chosen at random. Apply Markov’s Bound to R − 30:

Pr(R ≥ 180) = Pr(R − 30 ≥ 150) ≤ \frac{E [R − 30]}{150} = \frac{60}{150} = \frac{2}{5}.

So at most \frac{2}{5} · 120 = 48 students scored greater than or equal to 180.

□

(b) Give an example set of scores which achieve your bound. Solution. Of the 120 students, 48 score 180 and 72 score 30. The mean is \frac{48·180+72·30}{120} = 90, as required.

□

(c) If the maximum score on the exam was 100, give the best possible upper bound on the number of students who scored at most 50. Solution. Apply Markov’s Bound to 100 − R:

Pr(R ≤ 50) = Pr(100 − R ≥ 50) ≤ \frac{E [100 − R]}{50} = \frac{10}{50} = \frac{1}{5}.

So at most \frac{1}{5} · 120 = 24 students scored 50 or less.

□

Problem 3 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. Let C be the expected number of children up to and including the first boy. We showed E [C] = 2 in Lecture 22. We can compute the variance as follows:

Var [C] = E [C^{2}] − E [C]^{2} = ∑_{k=1}^{∞} k^{2} · (\frac{1}{2})^{k} − 2^{2} = \frac{\frac{1}{2} + (\frac{1}{2})^{2}}{(1 − \frac{1}{2})^{3}} − 4 = 6 − 4 = 2

The sum is computed by differentiating the formula for the sum of an infinite geometric sequence.

□

Problem 4 Suppose that n people have their hats returned at random. Let X_{i} = 1 if the ith person gets his or her own hat back and 0 otherwise. Let S_{n} = ∑_{i=1}^{n} X_{i}, so S_{n} is the total number of people who get their own hat back. Show that Handout ??: Problem Set 10.5 Solutions 3

(a) E [X_{i}^{2}] = 1/n. Solution. Note that X_{i}^{2} = X_{i}, which is 1 with probability 1/n and 0 otherwise. Thus, E [X_{i}^{2}] = E [X_{i}] = 1/n.

□

(b) E [X_{i}X_{j}] = 1/n(n − 1) for i ≠ j. Solution. X_{i}X_{j} is 1 if both X_{i} and X_{j} are 1, and 0 otherwise. Pr(X_{i} = 1 ∧ X_{j} = 1) = \frac{1}{n} · \frac{1}{n−1} = \frac{1}{n(n−1)}. Thus, E [X_{i}X_{j}] = 1/n(n − 1).

□

(c) E [S_{n}^{2}] = 2. Hint: Use (a) and (b). Solution.

E [S_{n}^{2}] = E [(∑_{i=1}^{n} X_{i})^{2}] = E [∑_{i} ∑_{j} X_{i}X_{j}] = ∑_{i} ∑_{j} E [X_{i}X_{j}]

= ∑_{i} E [X_{i}^{2}] + ∑_{i} ∑_{j≠i} E [X_{i}X_{j}] = n · \frac{1}{n} + n(n − 1) · \frac{1}{n(n − 1)} = 2.

□

(d) Var [S_{n}] = 1. Solution. Var [S_{n}] = E [S_{n}^{2}] − E^{2} [S_{n}] = 2 − (n · \frac{1}{n})^{2} = 2 − 1 = 1

□

(e) Pr(S_{n} ≥ 11) ≤ .01 for any n ≥ 11. Hint: Use Chebyshev’s Inequality. Solution.

Pr(S_{n} ≥ 11) = Pr(S_{n} − E [S_{n}] ≥ 11 − E [S_{n}])

= Pr(S_{n} − E [S_{n}] ≥ 10)

≤ \frac{Var [S_{n}]}{Var [S_{n}] + 10^{2}}

= \frac{1}{101} < .01

Note that the X_{i}’s are Bernoulli variables but are not independent, so S_{n} does not have a binomial distribution and the estimates from Lecture Notes 21 do not apply.

□

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

4 Handout ??: Problem Set 10.5 Solutions

(a) Var [aX + bY] Solution. First, we compute Var [X], which is also Var [Y] since X and Y are identically distributed.

Var [X] = E [X^{2}] − E [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}

We now use this to compute Var [aX + bY]:

Var [aX + bY] = Var [aX] + Var [bY]  because aX and bY are independent
= a^{2}Var [X] + b^{2}Var [Y]  Theorem 4.4 in Lecture Notes 24
= (a^{2} + b^{2})Var [X]  because Var [X] = Var [Y]
= (a^{2} + b^{2})\frac{n^{2} − 1}{12}  substitution from computation above

□

(b) E [max(X, Y)] Solution. First we compute the probability that the maximum of X and Y is equal to i:

Pr(max(X, Y) = i) = Pr(X ≤ i ∧ Y ≤ i) − Pr(X < i ∧ Y < i)

= Pr(X ≤ i) Pr(Y ≤ i) − Pr(X < i) Pr(Y < i)

= \frac{i}{n} · \frac{i}{n} − \frac{i − 1}{n} · \frac{i − 1}{n}

= \frac{2i − 1}{n^{2}}

We now compute the expectation using these probabilities:

E [max(X, Y)] = ∑_{i=i}^{n} i · Pr(max(X, Y) = i) = ∑_{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}

Alternatively, we could also compute it as follows:

E [max(X, Y)] = ∑_{i=0}^{∞} Pr(max(X, Y) > i) = ∑_{i=0}^{n−1} (1 − Pr(max(X, Y) ≤ i))

= n − ∑_{i=0}^{n−1} Pr(X ≤ i ∧ Y ≤ i) = n − ∑_{i=0}^{n−1} Pr(X ≤ i) Pr(Y ≤ i)

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

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

□

(c) E [min(X, Y)] Solution. Note that max(X, Y) + min(X, Y) = X + Y. Thus,

E [min(X, Y)] = E [X] + E [Y] − E [max(X, Y)]

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

= \frac{(n + 1)(2n + 1)}{6n}

□

(d) E [|X − Y |] Solution. We could compute this directly. However, note that |X − Y | = max(X, Y) − min(X, Y). Thus,

E [|X − Y |] = E [max(X, Y) − min(X, Y)]

= E [max(X, Y)] − E [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 |] = E [|X − Y |^{2}] − E [|X − Y |]^{2} = E [(X − Y)^{2}] − E [|X − Y |]^{2}

We could compute E [(X − Y)^{2}] directly, but note that Var [X − Y] = E [(X − Y)^{2}] − E [X − Y]^{2}, and E [X − Y] = 0. We can compute Var [X − Y] using the result in part (a). Thus,

Var [|X − Y |] = Var [X − Y] − E [|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 6 Suppose you are playing the game “Hearts” with three of your friends. In Hearts, all the cards are dealt to the players, in this case the four of you will each have 13 cards.

(a) What is the expectation and variance of the number of hearts in your hand?

Solution.

Let H be the number of hearts in your hand, and let X_{i} be the indicator random variable for the event that the ith card in your hand is a heart. Then H = ∑_{i=1}^{13} X_{i}. So

E [H] = ∑_{i=1}^{13} E [X_{i}] = ∑_{i=1}^{13} Pr(ith card is a heart) = ∑_{i=1}^{13} \frac{1}{4} = \frac{13}{4}.

To compute variance, we first compute E [H^{2}], following the solution to Problem 4c.

E [H^{2}] = E [(∑_{i=1}^{13} X_{i})^{2}] = ∑_{i} E [X_{i}] + ∑_{i} ∑_{j≠i} E [X_{i}X_{j}]

Note that X_{i}^{2} = X_{i}, so E [X_{i}^{2}] = 1/4. When i ≠ j, X_{i}X_{j} = 1 if cards i and j are both hearts, and 0 otherwise. The probability that both cards are hearts is \binom{13}{2}/\binom{52}{2}, so E [X_{i}X_{j}] = \binom{13}{2}/\binom{52}{2} = 3/51. In the summation above, there are 13 E [X_{i}^{2}] terms, and 13 · 12 = 156 terms of the form E [X_{i}X_{j}] with i ≠ j. Thus,

Var [H] = E [H^{2}] − E [H]^{2} = 13 · \frac{1}{4} + 156 · \frac{3}{51} − (\frac{13}{4})^{2} ≈ 1.864.

□

(b) What is the expectation and variance of the number of suits in your hand?

Solution.

Let N denote the number of suits in a hand. Let X_{s} be the indicator random variable for the event that there is a spade in the hand. Define X_{h}, X_{d}, X_{c} analogously for the three remaining suits: hearts, diamonds, and clubs. Then N = X_{s} + X_{h} + X_{d} + X_{c}.

The expectation of each of the indicator variables is the probability that a hand contains the corresponding suit. Thus, for i ∈ {s, h, d, c}

E [X_{i}] = 1 − \begin{matrix}( & {52−13 \atop 13} & ) \\ ( & {52 \atop 13} & ) \end{matrix} ≈ 0.9872,

because \binom{52−13}{13} is the number of hands that are missing the particular suit, and \binom{52}{13} is the total number of hands.

E [N] = E [X_{s} + X_{h} + X_{d} + X_{c}] = E [X_{s}] + E [X_{h}] + E [X_{d}] + E [X_{c}] ≈ 4 · 0.9872 = 3.9488.

To compute variance, we compute E [N^{2}] directly, and then Var [N] = E [N^{2}] − E [N]^{2}. We first calculate Pr(N = i) for i = 1, 2, 3, 4.

Pr(N = 1) = \frac{4}{\binom{52}{13}} ≈ 6.299 × 10^{−12},

because there are four possible hands of all one suit out of \binom{52}{13} possible hands of 13 cards.

Pr(N = 2) = \begin{matrix}\binom{4}{2} & [\binom{26}{13} − 2] \\ ( & {52 \atop 13} & ) \end{matrix} ≈ 9.827 × 10^{−5},

because there are \binom{4}{2} ways to choose which two suits. There are \binom{26}{13} ways to choose 13 cards from the 26 possible cards of those two suits. Two of those \binom{26}{13} hands actually contain only one suit.

Pr(N = 3) = \begin{matrix}\binom{4}{3} & [\binom{39}{13} − \binom{3}{2}\binom{26}{13} + 3] \\ ( & {52 \atop 13} & ) \end{matrix} ≈ 0.05097,

because there are \binom{4}{3} ways to choose the three suits, and \binom{39}{13} ways to choose 13 cards from the 39 cards of those three suits. But that includes hands with only one or two suits. So, using Inclusion-Exclusion, we subtract the \binom{3}{2}\binom{26}{13} ways to choose two of the three suits and then choose 13 cards from the 26 cards of those suits. This subtracts out the three hands with only one suit twice, so we add these back.

Of course,

Pr(N = 4) = 1 − (Pr(N = 1) + Pr(N = 2) + Pr(N = 3)) ≈ 0.9489.

Thus,

E [N^{2}] = 1 · Pr(N = 1) + 4 · Pr(N = 2) + 9 · Pr(N = 3) + 16 · Pr(N = 4)
≈ 0 + 0.0004 + 0.4587 + 15.1824 = 15.6415

This allows us to complete the calculation of the variance:

Var [N] ≈ 15.6415 − (3.9488)^{2} ≈ 0.0485.
□

Problem 7 We have two coins: one is a fair coin and the other is a coin that produces heads with probability 3/4. One of the two coins is picked, and this coin is tossed n times.

(a) Does the Weak Law of Large Numbers allow us to predict what limit, if any, is approached by the expected proportion of heads that turn up as n approaches infinity? Briefly explain.

Solution.

The Weak Law of Large Numbers tells us that the proportion of heads will approach 1/2 if the fair coin was picked, and it will approach 3/4 if the other coin was picked. But it does not tell us anything about which of these two numbers it will approach, as we have no information about which coin is picked.

□

(b) How many tosses suffice to make us 95% confident which coin was chosen? Explain.

Solution.

To guess which coin was picked, set a threshold t between 1/2 and 3/4. If the proportion of heads is less than the threshold, guess it was the fair coin; otherwise, guess the biased coin. Let the random variable H_{n} be the number of heads in the first n flips. We need to flip the coin enough times so that Pr(H_{n}/n > t) ≤ 0.05 if the fair coin was picked, and Pr(H_{n}/n < t) ≤ 0.05 if the biased coin was picked. A natural threshold to choose is 5/8, exactly in the middle of 1/2 and 3/4.

H_{n} is the sum of independent Bernoulli variables, which each have variance 1/4 for the fair coin and 3/16 for the biased coin. Using Chebyshev’s Inequality for the fair coin,

Pr (\frac{H_{n}}{n} > \frac{5}{8}) = Pr (\frac{H_{n}}{n} − \frac{1}{2} > \frac{5}{8} − \frac{1}{2}) = Pr (H_{n} − \frac{n}{2} > \frac{n}{8})

= Pr (H_{n} − E [H_{n}] > \frac{n}{8}) ≤ Pr (|H_{n} − E [H_{n}] | > \frac{n}{8})

≤ \frac{Var [H_{n}]}{(n/8)^{2}} = \frac{n/4}{n^{2}/64} = \frac{16}{n}

For the biased coin, we have

Pr (\frac{H_{n}}{n} < \frac{5}{8}) = Pr (\frac{3}{4} − \frac{H_{n}}{n} > \frac{3}{4} − \frac{5}{8}) = Pr (\frac{3n}{4} − H_{n} > \frac{n}{8})

= Pr (E [H_{n}] − H_{n} > \frac{n}{8}) ≤ Pr (|H_{n} − E [H_{n}] | > \frac{n}{8})

≤ \frac{Var [H_{n}]}{(n/8)^{2}} = \frac{3n/16}{n^{2}/64} = \frac{12}{n}

We are 95% confident if these are at most 0.05, which is satisfied if n ≥ 320.

Because the variance of the biased coin is less that of the fair coin, we can do slightly better if make our threshold a bit bigger, to about 0.634, which gives 95% confidence with 279 coin flips.

Because H_{n} has a binomial distribution, we can get a much better bound using the estimates from Lecture 21, giving 95% confidence when n > 42.

□

Problem 8 Handout ??: Problem Set 10.5 Solutions 9

(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 E [XY] = E [X] E [Y]. Are X and Y independent? Solution. To see that E [XY] = E [X] E [Y], note that E [X] = 0 and E [XY] = E [X^{3}] = 0 since X and X^{3} are both symmetric; that is, Pr(X = i) = Pr(X = −i) and Pr(X^{3} = i) = Pr(X^{3} = −i) for all i. However X and Y are not independent, since Y is determined by X. There are many cases that demonstrate this, for example, Pr(Y = 0) = 1/(2n + 1), but Pr(Y = 0 | X = 0) = 1.

□

(b) Show that in general for any two random variables X and Y that if E [XY] = E [X] E [Y] then Var [X + Y] = Var [X] + Var [Y]. Solution.

Var [X + Y] = E [(X + Y)^{2}] − (E [X + Y])^{2}
= E [X^{2} + 2XY + Y^{2}] − (E [X] + E [Y])^{2}
= E [X^{2}] + 2E [XY] + E [Y^{2}] − E [X]^{2} − 2E [X] E [Y] − E [Y]^{2}
= (E [X^{2}] − E [X]^{2}) + (E [Y^{2}] − E [Y]^{2}) + 2 (E [XY] − E [X] E [Y])
= Var [X] + Var [Y] .
□

Problem 9 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. 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 E [Z].

All the rolls are mutually independent, so we can use Wald’s theorem to get E [Y] = E [X] E [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 E [Z] = E [Y] E [Z_{i}] = (7/2)^{3} = 42.875.

□

Problem 10 Suppose that someone is infected with an unknown incurable contagious disease. Every day 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 sick people on the (k + 1)-st day in terms of the expected number of sick people on the kth day. Assume that each day every sick person meets n different persons.

Solution.

Let the random variable S_{k} be the number of sick people at the end of the kth day. We want an expression for S_{k+1} in terms of S_{k}. The base case is S_{0} = 1.

Let the sick people after day k be numbered 1, …, S_{k}, and let the random variable H_{i,k} be the number of (healthy) people infected on day k + 1 by the ith sick person from day k. We get S_{k+1} = S_{k} +∑_{i=1}^{S_{k}} H_{i,k}. H_{i,k} has a binomial distribution with parameters n and p, so E [H_{i,k}] = np, provided i ≤ S_{k}. That is, Pr(H_{i,k} = x|S_{k} ≥ i) = Pr(H = x), where H is the binomial random variable with parameters n and p. Thus,

E [S_{k+1}] = E [S_{k}] + E [∑_{i=1}^{S_{k}} H_{i,k}]  by linearity of expectation
= E [S_{k}] + E [S_{k}] · E [H]  by Wald’s Theorem
= E [S_{k}] (1 + np)  since E [H] = np

If we let e_{k} = E [S_{k}] then e_{0} = 1 and e_{k+1} = e_{k}(1 + np).

□

(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,k} be the indicator variable for whether the ith sick person from day k gets better. Then E [B_{i,k}] = r and S_{k+1} = S_{k} + ∑_{i=1}^{S_{k}}(H_{i,k} − B_{i,k}). Let B be the Bernoulli random variable with parameter r. Then, as before,

E [S_{k+1}] = E [S_{k}] + E [∑_{i=1}^{S_{k}} H_{i,k}] − E [∑_{i=1}^{S_{k}} B_{i,k}]  by linearity of expectation
= E [S_{k}] + E [S_{k}] · E [H] − E [S_{k}] · E [B]  by Wald’s Theorem
= E [S_{k}] (1 + np − r)  since E [H] = np and E [B] = r

and with this new recurrence, e_{k+1} = e_{k}(1 + np − r), so e_{k} = (1 + np − r)^{k}.

□

Problem 11 In this problem, we analyze probabilistically the first 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 biggest so far) = 1/(k + 1).

□

(b) Let C_{k} be the indicator random variable for the event “i_{k+1} > i_{k}”. What is E [C_{k}]? Solution. We can prove by a simple induction that i_{k} is always the biggest of the first k elements at the beginning of the kth step.

E [C_{k}] = Pr(i_{k+1} > i_{k}) = Pr(i_{k+1} is biggest so far) = \frac{1}{k + 1}.
□

(c) Let random variable C = ∑_{k=1}^{n} C_{k}. Give an asymptotic bound for E [C] as well as an interpretation of what E [C] is. Solution. Since we swap iff i_{k} > i_{k+1}, C_{k} is also the indicator variable for not swapping on the kth step. There are n − 1 steps in a stage of bubble sort, so n − 1 − C is the total number of swaps in a stage, 12 Handout ??: Problem Set 10.5 Solutions and E [C] is the expected number of non-swapping steps. We can compute it as follows:

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

□