On the expected duration of a search for a fixed pattern in random data (Corresp.)

Abstract

An expression is obtained for the expected duration of a search to find a given <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</tex> -ary sequence in a semi-infinite stream of random <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</tex> -ary data. The search time is found to be an increasing function of the lengths of the "bifices" of the pattern, where the term bifix denotes a sequence which is both a prefix and a suffix.