String Matching: The Ergodic Case
Shields, Paul C.
Ann. Probab., Tome 20 (1992) no. 4, p. 1199-1203 / Harvested from Project Euclid
Of interest in DNA analysis is the length $L(x^n_1)$ of the longest sequence that appears twice in a sequence $x^n_1$ of length $n$. Karlin and Ghandour and Arratia and Waterman have shown that if the sequence is a sample path from an i.i.d. or Markov process, then $L(x^n_1) = O(\log n)$. In this paper, examples of ergodic processes are constructed for which the asymptotic growth rate is infinitely often as large as $\lambda(n)$, where $\lambda(n)$ is subject only to the condition that it be $o(n)$.
Publié le : 1992-07-14
Classification:  String matching,  entropy,  92A10,  60F15
@article{1176989686,
     author = {Shields, Paul C.},
     title = {String Matching: The Ergodic Case},
     journal = {Ann. Probab.},
     volume = {20},
     number = {4},
     year = {1992},
     pages = { 1199-1203},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176989686}
}
Shields, Paul C. String Matching: The Ergodic Case. Ann. Probab., Tome 20 (1992) no. 4, pp.  1199-1203. http://gdmltest.u-ga.fr/item/1176989686/