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

- 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.
- 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 1x_{k-1}x_{k-2}...x_{0} in binary, then encode it as 1^{k-1}1x_{k-1}x_{k-2}...x_{0}. 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.

- Let X be the length of the first codeword in the sequence. Whats is E[X]?
Let Y be the value of the first codeword. Let A

_{n}be the event that the sequence starts with exactly n zeros. What is E[Y|A_{n}]?- What is E[Y]?

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