Maximal Length of Common Words Among Random Letter Sequences
Karlin, Samuel ; Ost, Friedemann
Ann. Probab., Tome 16 (1988) no. 4, p. 535-563 / Harvested from Project Euclid
Consider random letter sequences $\{\xi^{(\sigma)}_t, t = 1,\ldots, N; \sigma = 1,\ldots, s\}$ based on a finite alphabet generated by uniformly mixing stationary processes. The asymptotic distributional properties of the length of the longest common word in $r$ or more of the $s$ sequences $K_{r,s}(N)$, are investigated. When the probability measures of the different sequences are not too dissimilar, a classical extremal type limit law holds for $K_{r,s}(N) - (r \log N/(-\log \lambda)), \lambda$ being an appropriate local match parameter. The distributional properties of other long-word relationships and patterns among the sequences are also discussed.
Publié le : 1988-04-14
Classification:  Random letter sequences,  extremal distributions,  uniformly mixing stationary processes,  local match distribution,  longest common word,  60F10,  60F99
@article{1176991772,
     author = {Karlin, Samuel and Ost, Friedemann},
     title = {Maximal Length of Common Words Among Random Letter Sequences},
     journal = {Ann. Probab.},
     volume = {16},
     number = {4},
     year = {1988},
     pages = { 535-563},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176991772}
}
Karlin, Samuel; Ost, Friedemann. Maximal Length of Common Words Among Random Letter Sequences. Ann. Probab., Tome 16 (1988) no. 4, pp.  535-563. http://gdmltest.u-ga.fr/item/1176991772/