Optimal Penney Ante strategy via correlation polynomial identities (Q2500954)

Summary: 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. \textit{L. J. Guibas} and \textit{A. M. Odlyzko} [J. Comb. Theory, Ser. A 30, 183--208 (1981; Zbl 0454.68109)] 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\).