String matching bounds via coding
Shields, Paul C.
Ann. Probab., Tome 25 (1997) no. 4, p. 329-336 / Harvested from Project Euclid
It is known that the length $L(x_1^n)$ of the longest block appearing at least twice in a randomly chosen sample path of length $n$ drawn from an i.i.d. process is asymptotically almost surely equal to $C \log n$, where the constant $C$ depends on the process. A simple coding argument will be used to show that for a class of processes called the finite energy processes, $L(x_1^n)$ is almost surely upper bounded by $C \log n$, where $C$ is a constant. While the coding technique does not yield the exact constant $C$, it does show clearly what is needed to obtain log $n$ bounds.
Publié le : 1997-01-14
Classification:  STring matching,  prefix codes,  60G17,  94A24
@article{1024404290,
     author = {Shields, Paul C.},
     title = {String matching bounds via coding},
     journal = {Ann. Probab.},
     volume = {25},
     number = {4},
     year = {1997},
     pages = { 329-336},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1024404290}
}
Shields, Paul C. String matching bounds via coding. Ann. Probab., Tome 25 (1997) no. 4, pp.  329-336. http://gdmltest.u-ga.fr/item/1024404290/