The conjecture on asymptotic normality and log-normality of hidden-word counts

From papers

Let ZZ be the number of occurrences of a pattern ww as a subsequence in a random text of length nn, and let (nm)\binom{n}{m} be the number of possible positions for a subsequence when ww has length mm. Let σ12(nm)2\tfrac{\sigma_1^2}{\binom{n}{m}^2} denote the variance scale appearing in the first-order projection. Asymptotic normality and log-normality conjecture. If

σ12=o((nm)2),\sigma_1^2=o\bigl(\binom{n}{m}^2\bigr),

or equivalently

σ12=o(n2m2(n1m1)2),\sigma_1^2=o\bigl(\frac{n^2}{m^2}\binom{n-1}{m-1}^2\bigr),

then

Z/EZAsN(1,σ12(nm)2).Z/\operatorname{\mathbb E{}}Z\sim \operatorname{AsN}\Bigl(1,\frac{\sigma_1^2}{\binom{n}{m}^2}\Bigr).

Moreover, at least as long as m=o(n)m=o(n),

lnZAsN(an,σ12(nm)2)\ln Z\sim \operatorname{AsN}\Bigl(a_n,\frac{\sigma_1^2}{\binom{n}{m}^2}\Bigr)

for some sequence ana_n. The conjecture extends the asymptotic normality results proved earlier in the paper and predicts a corresponding log-normal regime under the stated variance condition.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Svante Janson and Wojciech Szpankowski, “Hidden Words Statistics for Large Patterns”, arXiv:2003.09584 (2020).

Solutions 0

No solutions have been posted yet.