TY - JOUR

T1 - A phase transition for the distribution of matching blocks

AU - Neuhauser, Claudia

PY - 1996

Y1 - 1996

N2 - We show distributional results for the length of the longest matching consecutive subsequence between two independent sequences A1, A2,..., Am and B1, B2,..., Bn whose letters are taken from a finite alphabet. We assume that A1, A2,... are i.i.d. with distribution μ and B1, B2,... 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.

AB - We show distributional results for the length of the longest matching consecutive subsequence between two independent sequences A1, A2,..., Am and B1, B2,..., Bn whose letters are taken from a finite alphabet. We assume that A1, A2,... are i.i.d. with distribution μ and B1, B2,... 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.

UR - http://www.scopus.com/inward/record.url?scp=17644389210&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17644389210&partnerID=8YFLogxK

U2 - 10.1017/S0963548300001930

DO - 10.1017/S0963548300001930

M3 - Article

AN - SCOPUS:17644389210

SN - 0963-5483

VL - 5

SP - 139

EP - 159

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 2

ER -