A phase transition for the distribution of matching blocks

We show distributional results for the length of the longest matching consecutive subsequence between two independent sequences A₁, A₂,..., A_m and B₁, B₂,..., B_n whose letters are taken from a finite alphabet. We assume that A₁, A₂,... are i.i.d. with distribution μ and B₁, B₂,... are i.i.d. with distribution ν. It is known that if μ and ν are not too different, the Chen-Stein method for Poisson approximation can be used to establish distributional results. We extend these results beyond the region where the Chen-Stein method was previously successful. We use a combination of 'matching by patterns' results obtained by Arratia and Waterman [1], and the Chen-Stein method to show that the Poisson approximation can be extended. Our method explains how the matching is achieved. This provides an explanation for the formulas in Arratia and Waterman [1] and thus answers one of the questions posed in comment F19 in Aldous [2]. Furthermore, in the case where the alphabet consists of only two letters, the phase transition observed by Arratia and Waterman [1] for the strong law of large numbers extends to the distributional result. We conjecture that this phase transition on the distributional level holds for any finite alphabet.