An Erdős-Révész Type Law for the Length of the Longest Match of Two Coin-Tossing Sequences

Consider a coin-tossing sequence, i.e., a sequence of independent variables, taking values 0 and 1 with probability 1/2. 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 Rn that behaves like log(n), 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 Rn. 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 2log(n). 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.