1. A fair coin is independently ?ipped n times, k times by A and n - k times by B. Show that the probability that A and B ?ip the same number of heads is equal to the probability that there are a total of k heads.

2. Suppose that we want to generate a random variable X that is equally likely to be either 0 or 1, and that all we have at our disposal is a biased coin that, when ?ipped, lands on heads with some (unknown) probability p. Consider the following procedure:

1. Flip the coin, and let 01, either heads or tails, be the result.

2. Flip the coin again, and let 02 be the result.

3. If 01 and 02 are the same, return to step 1.

4. If 02 is heads, set X = 0, otherwise set X = 1.

(a) Show that the random variable X generated by this procedure is equally likely to be either 0 or 1.

(b) Could we use a simpler procedure that continues to ?ip the coin until the last two ?ips are different, and then sets X = 0 if the ?nal ?ip is a head, and sets X = 1 if it is a tail?