An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences - Karl Grill (Entropy)
Consider a coin-tossing sequence, i.e., a sequence of independent variables, taking values 0 and 1 with probability <semantics>1/2</semantics>. The famous Erdős-Rényi law of large numbers implies that the longest run of ones in the first n observations has a length <semantics>Rn</semantics> that behaves like <semantics>log(n)</semantics>, as n tends to infinity (throughout this article, log denotes logarithm with base 2). Erdős and Révész refined this result by providing a description of the Lévy upper and lower classes of the process <semantics>Rn</semantics>. In another direction, Arratia and Waterman extended the Erdős-Rényi result to the longest matching subsequence (with shifts) of two coin-tossing sequences, finding that it behaves asymptotically like <semantics>2log(n)</semantics>. The present paper provides some Erdős-Révész type results in this situation, obtaining a complete description of the upper classes and a partial result on the lower ones.