exercise:Feb61dc4a0: Difference between revisions
From Stochiki
(Created page with "<div class="d-none"><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></div> We consider next a game called ''Penney-ante'' by its inventor W. Penney.<ref group="Notes" >W. Penney, “Problem: Penney-Ante,” ''Journal of Recreational Math,'' vol. 2 (1969), p. 241.</ref> There are two players; the first player picks a pa...") |
No edit summary |
||
| Line 5: | Line 5: | ||
\newcommand{\secstoprocess}{\all} | \newcommand{\secstoprocess}{\all} | ||
\newcommand{\NA}{{\rm NA}} | \newcommand{\NA}{{\rm NA}} | ||
\newcommand{\mathds}{\mathbb}</math></div> We consider next a game called ''Penney-ante'' by its | \newcommand{\mathds}{\mathbb}</math></div> We consider next a game called ''Penney-ante'' by its inventor W. Penney.<ref group="Notes" >W. Penney, “Problem: Penney-Ante,” ''Journal of Recreational Math,'' vol. 2 (1969), p. 241.</ref> 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. | ||
inventor W. Penney.<ref group="Notes" >W. Penney, “Problem: Penney-Ante,” ''Journal | |||
of | 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 | ||
Recreational Math,'' vol. 2 (1969), p. 241.</ref> There are two | |||
players; the first | <math>p_B = 1- p_A</math> that pattern | ||
player picks a pattern A of H's and T's, and then the second player, | B occurs before pattern A. To determine these probabilities we use the results of [[exercise:18da878882 |Exercise]] and [[exercise:72af71c8ee |Exercise]]. Here you were asked to show that, the expected time to reach a pattern B for the first time is, | ||
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 | |||
to show that, the expected time to | |||
reach a pattern B for the first time is, | |||
<math display="block"> | <math display="block"> | ||
E(T^B) = BB\ , | E(T^B) = BB\ , | ||
</math> | </math> | ||
and, starting with pattern A, the expected time to reach pattern B is | and, starting with pattern A, the expected time to reach pattern B is | ||
| Line 33: | Line 22: | ||
</math> | </math> | ||
<ul><li> Show that the odds that the first player will win are given by John | <ul style="list-style-type:lower-alpha"><li> Show that the odds that the first player will win are given by John | ||
Conway's | Conway's formula<ref group="Notes" >M. Gardner, “Mathematical Games,” ''Scientific American,'' | ||
formula<ref group="Notes" >M. Gardner, “Mathematical Games,” ''Scientific American,'' | |||
vol. 10 (1974), pp. 120--125.</ref>: | vol. 10 (1974), pp. 120--125.</ref>: | ||
| Line 64: | Line 52: | ||
3</math>, the second player has an advantage no matter what choice the first player | 3</math>, the second player has an advantage no matter what choice the first player | ||
makes. | makes. | ||
(It has been shown that, for <math>k \geq 3</math>, if the first player chooses | (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.<ref group="Notes" >Guibas and Odlyzko, op. cit.</ref>) | ||
<math>a_1</math>, <math>a_2</math>, | |||
of the form <math>b</math>, <math>a_1</math>, | |||
choices H | |||
</li> | </li> | ||
</ul> | </ul> | ||
Latest revision as of 01:28, 16 June 2024
[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