BBy Bot
Jun 09'24

Exercise

[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.[Notes 1] 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[Notes 2]:
    [[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 3])

Notes

  1. W. Penney, “Problem: Penney-Ante,” Journal of Recreational Math, vol. 2 (1969), p. 241.
  2. M. Gardner, “Mathematical Games,” Scientific American, vol. 10 (1974), pp. 120--125.
  3. Guibas and Odlyzko, op. cit.