First occurrence of a word among the elements of a finite dictionary in random sequences of letters

Emilio De Santis (University of Roma "La Sapienza")
Fabio L. Spizzichino (University of Roma "La Sapienza")


In this paper we study a classical model concerning  occurrence of words in a random sequence of letters from an alphabet. The problem can be studied as a game among $(m+1)$ words: the winning word in this game is the one that occurs first.  We prove that the knowledge of the  first $m$ words results in an advantage in the construction of the last word, as it has been shown in the literature for the cases $m=1$ and $m=2$ [CZ1,CZ2]. The last word can in fact be constructed so that its probability of winning is strictly larger than $1/(m+1)$. For the latter probability we will give an explicit lower bound. Our method is based on rather general  probabilistic arguments that allow us to consider an arbitrary cardinality  for the alphabet, an arbitrary value for $m$ and different mechanisms generating the random sequence of letters.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-9

Publication Date: March 20, 2012

DOI: 10.1214/EJP.v17-1878


  • Chen, Robert; Zame, Alan. On fair coin-tossing games. J. Multivariate Anal. 9 (1979), no. 1, 150--156. MR0530646
  • Chen, Robert W.; Zame, Alan; Rosenberg, Burton. On the first occurrence of strings. Electron. J. Combin. 16 (2009), no. 1, Research Paper 29, 16 pp. MR2482097
  • Feller, William. An introduction to probability theory and its applications. Vol. I. Third edition John Wiley & Sons, Inc., New York-London-Sydney 1968 xviii+509 pp. MR0228020
  • Li, Shuo-Yen Robert. A martingale approach to the study of occurrence of sequence patterns in repeated experiments. Ann. Probab. 8 (1980), no. 6, 1171--1176. MR0602390
  • Robin, S.; Daudin, J. J. Exact distribution of word occurrences in a random sequence of letters. J. Appl. Probab. 36 (1999), no. 1, 179--193. MR1699643
  • Stefanov, V. T.; Pakes, A. G. Explicit distributional results in pattern formation. Ann. Appl. Probab. 7 (1997), no. 3, 666--678. MR1459265
  • Stefanov, V. T.; Robin, S.; Schbath, S. Waiting times for clumps of patterns and for structured motifs in random sequences. Discrete Appl. Math. 155 (2007), no. 6-7, 868--880. MR2309853

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.