| We consider the well-known problem of string
overlapping in connection with the so-called Penney Ante game with a
$q$-sided die. Let two players, (1) and (2), agree on some integer $n
\ge 2.$ Then both of them select a $q$-ary $n$-word, say $w_1$ and
$w_2,$ and begin rolling a die until either $w_1$ or $w_2$ appears as a
block of $n$ consecutive outcomes. Player (1) wins if $w_1$ appears
before $w_2$ does. The problem is to find the probability $P(w_1, w_2)$
that player (1) will win for the chosen $w_1$ and $w_2.$ A solution of
the problem was proposed by J.H. Conway (but was not published), and the
key tool of his solution is the so-called Conway matrix $C_n^{(q)}$
whose indices encode $n$ consecutive outcomes.
We extend our previous results obtained for the case $q = 2$
("coin") to the case of arbitrary $q >1.$ We propose a simple and
effective algorithm for calculation and visualization of Conway matrices
$C_n$ and the corresponding matrices $P_n$ (that give probabilities
that player (1) will win for the chosen words $w_1$ and $w_2$) via the
standard technique of the (inverse) multidimensional DFT. Computer
Algebra system {\it Mathematica} (versions 5 and 6) was used for
intermediate calculations, check of hypotheses and visualization of
results.
This is joint work with N. Gogin and T. Myllari.
|