STRING MATCHING - THE ERGODIC CASE
成果类型：
Article
署名作者：
SHIELDS, PC
署名单位：
Eotvos Lorand University
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/aop/1176989686
发表日期：
1992
页码：
1199-1203
关键词：
摘要：
Of interest in DNA analysis is the length L(x1n) of the longest sequence that appears twice in a sequence x1n 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(x1n) = 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).