PineWiki
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 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.
- 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 An be the event that the sequence starts with exactly n zeros. What is E[Y|An]?
- What is E[Y]?
(Give a closed-form expression for each case.)
