\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Daniel Felix}
%
%
\medskip
\noindent
%
%
{\bf Optimal Penney Ante Strategy via Correlation Polynomial Identities}
%
%
\vskip 5mm
\noindent
%
%
%
%
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$.
\bye