Each of m + 2 players pays 1 unit to a kitty in order to play the following game: A fair coin is to be flipped successively n times, where n is an odd number, and the successive outcomes are noted. Before the n flips, each player writes down a prediction of the outcomes. For instance, if n = 3, then a player might write down (H,H,T), which means that he or she predicts that the first flip will land on heads, the second on heads, and the third on tails. After the coins are flipped, the players count their total number of correct predictions. Thus, if the actual outcomes are all heads, then the player who wrote (H, H, T) would have 2 correct predictions. The total kitty of m + 2 is then evenly split up among those players having the largest number of correct predictions.
Since each of the coin flips is equally likely to land on either heads or tails, m of the players have decided to make their predictions in a totally random fashion. Specifically, they will each flip one of their own fair coins n times and then use the result as their prediction. However, the final 2 of the players have formed a syndicate and will use the following strategy: One of them will make predictions in the same random fashion as the other m players, but the other one will then predict exactly the opposite of the first. That is, when the randomizing member of the syndicate predicts an H, the other member predicts a T. For instance, if the randomizing member of the syndicate predicts (H, H, T), then the other one predicts (T, T, H).
(a) Argue that exactly one of the syndicate members will have more than n/2 correct predictions. (Remember, n is odd.)
(b) Let X denote the number of the m nonsyndicate players that have more than n/2 correct predictions. What is the distribution of X?
(c) With X as defined in part (b), argue that
E[payoff to the syndicate] = (m + 2) × E[1/X + 1]
(d) Use part (c) of Problem 59 to conclude that
E[payoff to the syndicate] = 2(m + 2)/m + 1 × [1 – (1/2)m+1]
and explicitly compute this number when m = 1, 2, and 3. Because it can be shown that
2(m + 2)/m + 1 [1 – (1/2)m+1] > 2
it follows that the syndicate’s strategy always gives it a positive expected profit.