12
$\begingroup$

The standard Penney's game is played by two players. Player $A$ chooses a sequence of $k>2$ bits and $B$ (seeing $A$'s selection) chooses a different sequence of $k$ bits. A fair coin is flipped repeatedly; whichever player's sequence appears first in the (long) sequence of random coin flips is the winner.

Paradoxically, no matter what sequence $A$ chooses, $B$ can choose a different sequence that is more likely to appear before $A$'s. For instance, for $k=3$, if $A$ chooses $HHH$, then $B$ should choose $THH$. In $1/8$ games, the $HHH$ will appear as the first three coin tosses and $A$ will win; in all other games $B$ will win because before $HHH$ can appear, $B$'s sequence $THH$ must appear. If instead $A$ chose $THH$, then $B$ should choose $TTH$, which is more likely to appear first. Here are some simulations illustrating the effect:

  • $HHH\underline{TTH}TTTTHHTTT$: B wins
  • $H\underline{TTH}TTHTHHTHHTT$: B wins
  • $H\underline{TTH}THHHHHHTHTT$: B wins
  • $H\underline{TTH}THHTTHTHHHT$: B wins
  • $HHHTT\underline{TTH}THHTHTH$: B wins
  • $TTTTTT\underline{THH}THHTTH$: A wins
  • $\underline{TTH}TTTHTHTHHHTH$: B wins
  • $HH\underline{TTH}TTTTTHHTTT$: B wins
  • $HHHHHHH\underline{THH}TTHHT$: A wins
  • $\underline{TTH}TTTHHHHTHTHT$: B wins
  • $\underline{THH}HTHTTTTHTHHT$: A wins
  • $TH\underline{THH}TTTHTTHTTH$: A wins

And so on. Thus the available sequences exhibit non-transitive dominance: $\alpha_1 > \alpha_2 > \ldots > \alpha_1$, where the $\alpha_i$ are distinct $k$-bit sequences and "$>$" means "is more likely to appear first in a sequence randomly generated by a fair coin."

In short, if $B$ plays optimally, he is guaranteed (in probability) to win most the games.

Let's call that traditional Penney game a one-level game, because only one sequence match is needed for termination.

Consider a two-level generalization, in which $A$ first chooses two different $k$-bit sequences and $B$ (seeing $A$'s choices) chooses two different sequences (not already chosen by $A$). The game proceeds as before, with random coin flips, but now the winner is the first to have both his chosen sequences appear, in either order and at any separation. (Allow overlaps of sequences.)

Question

Is there an optimal strategy for $B$ such that he is guaranteed (in probability) to win most two-level Penney games?

Improve this question
$\endgroup$
14
  • $\begingroup$ My brute-force simulation for k=3 does not find that Bob can beat Alice's pair THH, HHT. None of his strategies beat 50% with statistical significance in a million trials. (It is possible he has a slight edge but more trials are needed to detect it.) $\endgroup$
    – usul
    Commented Jul 17, 2018 at 10:42
  • $\begingroup$ @usul: Please check your code and assumptions. As the table (Analysis of the three-bit game) in the linked wikipedia page states, the odds in favor of $TTH$ over $THH$ are 2:1. (I'll run my own simulations to confirm too.) . en.wikipedia.org/wiki/Penney%27s_game $\endgroup$
    – David G. Stork
    Commented Jul 17, 2018 at 15:34
  • $\begingroup$ @usul: My computer simulations confirm the 2:1 odds ratio described in the wikipedia page. Please check that page and your code. Also, on that page there is a helpful "intuitive" explanation why the non-transitive dominance woks. $\endgroup$
    – David G. Stork
    Commented Jul 17, 2018 at 16:10
  • $\begingroup$ oops, I was unclear. I refer not to the original problem but to your question about two-level generalization. When I simulate Alice's choice of the two sequences (THH, HHT), I cannot find any pair of length-3 sequences $(x,y)$ for Bob such that, with probability noticeably over 0.5, both $x$ and $y$ appear as subsequences prior to both TTH and HHT. $\endgroup$
    – usul
    Commented Jul 17, 2018 at 17:56
  • 1
    $\begingroup$ The intransitivity in the one-level game only shows up for $k\ge3$. Perhaps the calculations of @usul are telling us that intransitivity in the two-level game doesn't show up at $k=3$, but that might just mean we need to look at some larger $k$ to find it. $\endgroup$
    – Gerry Myerson
    Commented Jul 17, 2018 at 23:57

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .