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

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

## 1.1. Solution

- 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.
- 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.
- 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 A_{i} be the event that the student is enlightened after i years, then Pr[A_{i}] = (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[A_{i}] / 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 ∑ iz^{i-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.

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

You may find it helpful to use the fact that

## 2.1. Solution

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

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

- What is the expected value of M?
- 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.)
- What is the expected value of the lowest roll of four dice?
- What is the expected value of M'?

## 3.1. Solution

M = X₁+X₂+X₃ where each X

_{i}has expectation (1+2+3+4+5+6)/6 = 7/2. So E[M] = 3(7/2) = 21/2 = 10½.Following the hint, we observe Pr[one die ≥ k] = (7-k)/6, so Pr[all four dice ≥ 6] = (7-k)

^{4}/6^{4}. But then Pr[lowest die = k] = Pr[all dice ≥ k] - Pr[all dice ≥ k+1] = ((7-k)^{4}- (7-k-1)^{4})/6^{4}= ((7-k)^{4}- (6-k)^{4})/6^{4}.E[lowest die] = ∑ k Pr[lowest die = k] = ∑ k((7-k)

^{4}-(6-k)^{4})/6^{4}. 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.- 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 X_{i} be the indicator variable for the event that occupant i ends up in their old room. Let S = ∑ X_{i} 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[∑ X_{i}] = ∑ E[X_{i}] = n(1/n) = 1.

Getting the variance is more complicated, since the X_{i} are not independent. For a single X_{i} we can compute Var[X_{i}] = E[X_{i}^{2}] - E[X_{i}]^{2} = 1/n - 1/n² = (n-1)/n². We also need Cov(X_{i}, X_{j}) for i≠j. Recall that Cov(X_{i}, X_{j}) = E[X_{i}X_{j}] - E[X_{i}]E[X_{j}] = 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(X_{i}X_{j}) = 1/(n(n-1)) - 1/n^{2} = (n - (n-1))/(n²(n-1)) = 1/(n²(n-1)).

Now use the sum formula for variance to get Var[S] = ∑ Var[X_{i}] + ∑[i≠j] Cov[X_{i}X_{j}] = 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².