tailieunhanh - Báo cáo toán học: "On the first occurrence of strings"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On the first occurrence of strings. | On the first occurrence of strings Robert W. Chen Alan Zame Dept of Mathematics University of Miami Burton Rosenberg Dept of Computer Science University of Miami Submitted Feb 9 2008 Accepted Feb 6 2009 Published Feb 27 2009 Mathematics Subject Classification 65C50 Abstract We consider a game in which players select strings over 0 1 g and observe a series of fair coin tosses interpreted as a string over 0 1 g. 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. 1 Introduction We consider a game in which players select strings over W 0 1g and observe a series of fair coin tosses that is a string Ơ s1 s2. where each Si is chosen independently at random from 0 1g with equal probability of a 0 or 1 being chosen. The winner of this game is the player whose string appears first. This problem has been studied both in the context of games and as a pure probabilistic problem in Chen 1 2 3 Guibas et al 4 Li 5 Gerber et al 6 and Mori 7 . In Chen 3 it was proved that for two players public knowledge of the opponent s string leads to an advantage. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R29 1 Theorem 1 For any string Ơ 2 W ơ 3 there exists a string T 2 W of the same length as Ơ such that P Tơ Tt 1 2. That is the first occurrence of T is likely to be before that of Ơ. In this paper we establish results for three players. In is quite natural to suspect that under some reasonable conditions we might .