[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

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 [math]p_A[/math] that pattern A will occur before pattern B and the probability

[math]p_B = 1- p_A[/math] that pattern B occurs before pattern A. To determine these probabilities we use the results of Exercise and Exercise. Here you were asked to show that, the expected time to reach a pattern B for the first time is,

[[math]] E(T^B) = BB\ , [[/math]]

and, starting with pattern A, the expected time to reach pattern B is

[[math]] E_A(T^B) = BB - AB\ . [[/math]]

• Show that the odds that the first player will win are given by John Conway's formula:
  [[math]] \frac{p_A}{1-p_A} = \frac{p_A}{p_B} = \frac{BB - BA}{AA - AB}\ . [[/math]]
  Hint: Explain why
  [[math]] E(T^B) = E(T^{A\ {\rm or}\ B}) + p_A E_A(T^B) [[/math]]
  and thus
  [[math]] BB = E(T^{A\ {\rm or}\ B}) + p_A (BB - AB)\ . [[/math]]
  Interchange A and B to find a similar equation involving the [math]p_B[/math]. Finally, note that
  [[math]] p_A + p_B = 1\ . [[/math]]
  Use these equations to solve for [math]p_A[/math] and [math]p_B[/math].
• Assume that both players choose a pattern of the same length k. Show that, if [math]k = 2[/math], this is a fair game, but, if [math]k = 3[/math], the second player has an advantage no matter what choice the first player makes. (It has been shown that, for [math]k \geq 3[/math], if the first player chooses [math]a_1[/math], [math]a_2[/math], ..., [math]a_k[/math], then the optimal strategy for the second player is of the form [math]b[/math], [math]a_1[/math], ..., [math]a_{k - 1}[/math] where [math]b[/math] is the better of the two choices H or T.)

Notes