Optimal Penney Ante Strategy via Correlation Polynomial Identities

Abstract

In the game of Penney Ante two players take turns publicly selecting two distinct words of length $n$ using letters from an alphabet $\Omega$ of size $q$. They roll a fair $q$ sided die having sides labelled with the elements of $\Omega$ until the last $n$ tosses agree with one player's word, and that player is declared the winner. For $n\geq 3$ the second player has a strategy which guarantees strictly better than even odds. Guibas and Odlyzko have shown that the last $n-1$ letters of the second player's optimal word agree with the initial $n-1$ letters of the first player's word. We offer a new proof of this result when $q \geq 3$ using correlation polynomial identities, and we complete the description of the second player's best strategy by characterizing the optimal leading letter. We also give a new proof of their conjecture that for $q=2$ this optimal strategy is unique, and we provide a generalization of this result to higher $q$.