On the First Occurrence of Strings

Robert W. Chen, Burton Rosenberg

Abstract


We consider a game in which players select strings over $\{\,0, 1\,\}$ and observe a series of fair coin tosses, interpreted as a string over $\{\,0, 1\,\}$. The winner of this game is the player whose string appears first. For two players public knowledge of the opponent's string leads to an advantage. In this paper, results for three players are presented. It is shown that given the choices of the first two players, a third string can always be chosen with probability of winning greater than $1/3$. It is also shown that two players can chose strings such that the third player's probability of winning is strictly less than the greater of the other two player's probability of winning, and that whichever string is chosen, it will always have a disadvantage to one of the two other strings.


Full Text: PDF