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 (1970) law of large numbers implies that the longest run of ones in the first n observations has a length Rn that behaves like log2(n) as n tends to infinity. Erdős and Révész (1976) refined this result by giving a description of the Lévy upper and lower classes of the process Rn. In another direction, Arratia and Waterman (1985) 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 2log2(n). The present paper gives 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.