We consider next a game called Penney-ante by its inventor W. Penney. There are two players; the first player picks a pattern A of H's and T's, and then the second player, knowing the choice of the first player, picks a different pattern B. We assume that neither pattern is a subpattern of the other pattern. A coin is tossed a sequence of times, and the player whose pattern comes up first is the winner. To analyze the game, we need to find the probability pA that pattern A will occur before pattern B and the probability pB=1−pA that pattern B occurs before pattern A. Using the results of Exercises 28 and 29, the expected time to reach a pattern B for the first time is E(TB)=BB, and starting with pattern A, the expected time to reach pattern B is EA(TB)=BB−AB.
(a) Show that the odds that the first player will win are given by John Conway's formula:
1−pApA=pBpA=AA−ABBB−BA.
Hint: Explain why E(TB)=E(TA or B)+pAEA(TB) and thus BB=E(TA or B)+pA(BB−AB). Interchange A and B to find a similar equation involving pB. Finally, note that pA+pB=1. Use these equations to solve for pA and pB.
(b) Assume that both players choose a pattern of the same length k. Show that, if k=2, this is a fair game, but, if k=3, the second player has an advantage no matter what choice the first player makes.