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

About 6 years old · traced to

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(n−1m−1)2),\sigma_1^2=o\bigl(\frac{n^2}{m^2}\binom{n-1}{m-1}^2\bigr),

then

Z/E⁡Z∼AsN⁡(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),

ln⁡Z∼AsN⁡(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.