### 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")*

#### Abstract

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

#### References

- 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

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