[FrontPage] [TitleIndex] [WordIndex] 

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. A hard path to enlightenment

A student at a Zen Buddhist monastery meditates for 17 hours a day. After each year of meditation, he becomes enlightened with probability 1/10, gives up and leaves the monastery with probability 2/10, and stays for another year with the remaining probability 7/10.

  1. What is the probability that the student eventually becomes enlightened?
  2. What is the expected number of years that pass before the student either becomes enlightened or leaves?
  3. What is the expected number of years that pass before the student becomes enlightened, conditioned on that event eventually occurring?

1.1. Solution

  1. Let p be the probability that the student eventually becomes enlightened. Then p = (1/10)⋅1 + (2/10)⋅0 + (7/10)⋅p, where the last term follows because the student has the same chance of eventually becoming enlightened even if we condition on having wasted a year already. Solving for p gives p = (1/10)/(3/10) = 1/3.
  2. Let T be the waiting time. Then ET = 1 + (7/10)ET, because the student always spends at least one year, and with probability 7/10 goes back to where he started. Solving for ET gives ET = 10/3.
  3. This is a little tricky. Let T again be the waiting time and let A be the event that the student is eventually enlightened. Then we have E[T|A] = 1 + Pr[stays|A] E[T|A]. To compute Pr[stays|A], expand as Pr[stays|A] = Pr[stays ∧ A] / Pr[A] = Pr[A|stays] Pr[stays] / Pr[A]. But Pr[A|stays] = Pr[A], since after staying the student is back where he started, giving Pr[stays | A] = Pr[stays] = 7/10. So again we get E[T|A] = 1 + (7/10) E[T|A], or E[T|A] = 10/3.

That these last two results are equal is so highly non-intuitive that it may be helpful to compute the conditional expectation more explicitly. Let Ai be the event that the student is enlightened after i years, then Pr[Ai] = (7/10)i-1(1/10), since the student must stay for i-1 years and then be enlightened. E[T|A] = ∑i i Pr[T=i|A] = ∑i i Pr[T=i ∧ A] / Pr[A] = ∑i i Pr[Ai] / Pr[A] = ∑i i (7/10)i-1 (1/10) / Pr[A] = (3/10) ∑i i (7/10)i-1. The sum is of the form ∑ izi-1, which we instantly recognize as having the generating function 1/(1-z)² = 1/(1-(7/10))² = 100/9. To get the full answer we must multiply this by (3/10) giving 10/3.

2. Two random variables

Let X and Y be independent random variables that each take on the values 1..n with probability 1/n for each value.

  1. Compute E[X].

  2. Compute E[X|X>Y].

You may find it helpful to use the fact that

\[ \sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}. \]

2.1. Solution

  1. E[X] = ∑ x Pr[X=x] = ∑[x=1 to n] x/n = n(n+1)/2n = (n+1)/2. Alternate solution: observe (n+1)-X has the same distribution as X. So 2E[X] = E[(n+1)-x] + E[X] = E[(n+1)-X+X] = E[n+1] = n+1, giving E[X] = (n+1)/2.

  2. E[X|X>Y] = ∑ x Pr[X=x|X>Y]. Let's start by computing Pr[X=x|X>Y] for fixed x. We have Pr[X=x|X>Y] = Pr[X=x ∧ X>Y]/Pr[X>Y]. Pr[X=x ∧ X>Y] = Pr[X=x] Pr[X>Y|X=x] = (1/n)((x-1)/n) = (x-1)/n². To get Pr[X>Y], observe that Pr[X>Y]=Pr[Y>X] and Pr[X>Y]+Pr[Y>X]+Pr[X=Y] = 2Pr[X>Y] + (1/n) = 1, giving Pr[X>Y] = (1-1/n)/2 = (n-1)/(2n). This gives Pr[X=x|X>Y] = 2n(x-1)/(n²(n-1)) = 2(x-1)/(n(n-1)).

Now we have to compute the sum. We need ∑[x=1..n] x (2(x-1)/(n(n-1))) = (2/(n(n-1))) ∑[x=1..n] x(x-1) = (2/(n(n-1))) ∑[x=1..n] (x² - x).

Using the sum formulas we get

\begin{eqnarray*} E[X|X>Y] &=& \frac{2}{n(n-1)} \sum_{x=1}^{n} (x^2 - x) \\ &=& \frac{2}{n(n-1)} \left(\frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2}\right) \\ &=& \frac{(n+1)(2n+1)-3(n+1)}{3(n-1)} \\ &=& \frac{(n+1)(2n-2)}{3(n-1)} \\ &=& \frac{2}{3}(n+1). \end{eqnarray*}

As a quick check, when n=2 we get 2 (the only possible value for X), and when n=3 we get 8/3, which we can also compute by averaging the X over the three cases for X>Y of 3>1, 3>2, and 2>1.

3. Character generation

Thrognor the Unwashable is playing a new Massive Multiplayer On-line Roleplaying Game with a discrete mathematics theme. He rolls 3 independent six-sided dice and takes their sum to compute his Mathematical Ability score M.

Unhappy with the results, Thrognor selects the Take CS202 option on the character generation screen. This deducts 197 hours from his sleep score, but lets him roll 4 independent six-sided dice and discard the lowest roll, giving a new Mathematical Ability score M'.

  1. What is the expected value of M?
  2. What is the probability that the lowest roll of four dice is equal to k, as a function of k? (Hint: First compute the probability that all four dice show at least k.)
  3. What is the expected value of the lowest roll of four dice?
  4. What is the expected value of M'?

3.1. Solution

  1. M = X₁+X₂+X₃ where each Xi has expectation (1+2+3+4+5+6)/6 = 7/2. So E[M] = 3(7/2) = 21/2 = 10½.

  2. Following the hint, we observe Pr[one die ≥ k] = (7-k)/6, so Pr[all four dice ≥ 6] = (7-k)4/64. But then Pr[lowest die = k] = Pr[all dice ≥ k] - Pr[all dice ≥ k+1] = ((7-k)4 - (7-k-1)4)/64 = ((7-k)4 - (6-k)4)/64.

  3. E[lowest die] = ∑ k Pr[lowest die = k] = ∑ k((7-k)4-(6-k)4)/64. I don't really know any easy way to compute this sum other than by adding up all the terms. I get 2275 for the total denominator, giving 2275/1296 for the expected lowest die.

  4. Here we use the fact that E[M'] = 4E[X] - E[lowest die]. So E[M'] = 4(7/2) - 2275/1296 = 15869/1296 = 12.24... .

4. Moving day

One day, the authorities evacuate the n occupants of a hotel with n rooms. When the occupants return, they are each assigned a new room according to a uniform random permutation. Use Chebyshev's inequality to show that the probability that more than k occupants end up in their old rooms is at most 1/k².

4.1. Solution

Let Xi be the indicator variable for the event that occupant i ends up in their old room. Let S = ∑ Xi be the total number of occupants who end up in their old rooms. To use Chebyshev's inequality, we need to know both E[S] and Var[S].

For E[S], we have E[S] = E[∑ Xi] = ∑ E[Xi] = n(1/n) = 1.

Getting the variance is more complicated, since the Xi are not independent. For a single Xi we can compute Var[Xi] = E[Xi2] - E[Xi]2 = 1/n - 1/n² = (n-1)/n². We also need Cov(Xi, Xj) for i≠j. Recall that Cov(Xi, Xj) = E[XiXj] - E[Xi]E[Xj] = Pr[i and j both get their old room back] - 1/n². To calculate the probability that i and j both get their old room back, observe that in this case there are (n-2)! ways to arrange the remaining occupants, so we have (n-2)! permutations out of n! total, giving (n-2)!/n! = 1/(n(n-1)), or Cov(XiXj) = 1/(n(n-1)) - 1/n2 = (n - (n-1))/(n²(n-1)) = 1/(n²(n-1)).

Now use the sum formula for variance to get Var[S] = ∑ Var[Xi] + ∑[i≠j] Cov[XiXj] = n((n-1)/n²) + n(n-1)(1/(n²(n-1))) = (n-1)/n + 1/n = 1.

Recall that Chebyshev's inequality says Pr[|S-ES| ≥ r] ≤ Var[S]/r². If S > k, then S ≥ k+1, so we have Pr[S > k] = Pr[S ≥ k+1] ≥ Pr[|S-ES| ≥ k] ≤ Var[S]/k² = 1/k².

2014-06-17 11:57