Long repetitive patterns in random sequences

L. J. Guibas, A. M. Odlyzko

Research output: Contribution to journalArticlepeer-review

62 Scopus citations

Abstract

Appearances of long repetitive sequences such as 00...0 or 1010...101 in random sequences are studied. The expected length of the longest repetitive run of any specified type in a random binary sequence of length n is shown to tend to the binary logarithm of n plus a periodic function of log n. Necessary and sufficient conditions are derived to ensure that with probability 1 an infinite random sequence should contain repetitive runs of specified lengths in given initial segments. Finally, the number of long repetitive runs of a specified kind that occur in a random sequence is studied. These results are derived from simple expressions for the generating functions for the probabilities of occurrences of various repetitive runs. These generating functions are rational, and lead to sharp asymptotic estimates for the probabilities.

Original languageEnglish (US)
Pages (from-to)241-262
Number of pages22
JournalZeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete
Volume53
Issue number3
DOIs
StatePublished - Jan 1 1980

Fingerprint Dive into the research topics of 'Long repetitive patterns in random sequences'. Together they form a unique fingerprint.

Cite this