[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?

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

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

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

2014-06-17 11:57