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

/Solutions

1. Rolling dice

Recall that a standard six-sided die is labeled with the numbers from 1 through 6, each occurring with equal probability. When rolling two dice, their sum can range from 2 up to 12, and the probability that the sum equals k depends on k. We'd like to relabel these dice so that the distribution of their sum is uniform.

  1. Prove or disprove: It is possible to relabel two six-sided dice so that all integers x with 1 ≤ x ≤ 12 are equally likely to appear as the sum of the dice.
  2. Prove or disprove: It is possible to relabel two six-sided dice so that all integers x with 2 ≤ x ≤ 12 are equally likely to appear as the sum of the dice.

Clarification added 2010-11-22: In each case, the probability of getting any value other than the specified values should be zero.

2. Flipping coins

Alice flips m independent fair coins and Bob flips n independent fair coins. Give a closed-form expression for the probability that Alice gets the same number of heads as Bob.

3. Gamma coding

The Elias gamma code is a method for encoding positive integers as strings of bits so that no encoding is a prefix of any other encoding. The method is to first write the target integer as a sequence of bits 1xk-1xk-2...x0 in binary, then encode it as 1k-11xk-1xk-2...x0. For example, 6 = 110 is encoded as 00110 while 34 = 10010 is encoded as 000010010.

Because of the prefix-free property, any infinite sequence of bits can be uniquely decoded as an infinite sequence of positive integers. For example, the sequence 000110100011000100110011110101... decodes as:

0001101 0001100 010 011 00111 1 010 1 ...
   13      12    2   3    7   1  2  1 ...

Here we've chopped the original sequence into a sequence of codewords, each of which decodes to a positive integer.

Suppose we generate an infinite sequence by choosing 1 independently at each position with probability p and 0 with probability q = 1-p.

  1. Let X be the length of the first codeword in the sequence. Whats is E[X]?
  2. Let Y be the value of the first codeword. Let An be the event that the sequence starts with exactly n zeros. What is E[Y|An]?

  3. What is E[Y]?

(Give a closed-form expression for each case.)


2014-06-17 11:57