8 - Crypto

Summary

Answers to puzzles from Chapter 7

Puzzle 1. We are given a biased coin that comes up heads with probability p. Using this coin, construct an unbiased coin.

Solution. The solution is the “von Neumann trick”: flip the biased coin twice, interpreting HT as heads and TH as tails. If the flips come up HH or TT, then try again. Under this scheme, “heads” and “tails” are equiprobable, each occurring with probability p(1 - p) in any given trial. Conditioned on either HT or TH occurring, it follows that the simulated coin is unbiased.

Puzzle 2. n people sit in a circle. Each person wears either a red hat or a blue hat, chosen independently and uniformly at random. Each person can see the hats of all the other people, but not his/her own hat. Based only upon what they see, each person votes on whether or not the total number of red hats is odd. Is there a scheme by which the outcome of the vote is correct with probability greater than ½?

Solution. Each person decides his/her vote as follows: if the number of visible blue hats is larger than the number of visible red hats, then vote according to the parity of the number of visible red hats. Otherwise, vote the opposite of the parity of the number of visible red hats. If the number of red hats differs from the number of blue hats by at least 2, then this scheme succeeds with certainty. Otherwise, the scheme might fail. However, the probability that the number of red hats differs from the number of blue hats by less than 2 is small – O(1/√N).