String matching bounds via coding

• 成果类型: Article
• 署名作者: Shields, PC
• 署名单位: University System of Ohio; University of Toledo
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 1997
• 页码: 329-336
• 关键词: entropy

摘要

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 it 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.