A Phase Transition for the Distribution of Matching Blocks
Claudia M. Neuhauser · Combinatorics Probability Computing · 1996
We show distributional results for the length of the longest matching consecutive subsequence between two independent sequencesA1,A2, …,AmandB1,B2, …,Bnwhose letters are taken from a finite alphabet. We assume thatA1,A2, … are i.i.d. with distribution μ andB1,B2, … are i.i.d. with distribution ν. It is known that if μ andvare 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.