Limiting-distribution equivalence for identical-letter pair counts

Proof of the full limiting-distribution conjecture, uniformly over every threshold.

Fix $0<p<1$, put $q=1-p$, and let $P_i=pq^{i-1}$. For independent geometric letters $Z_1,\ldots,Z_n$, define

$$I_{n,i}=\mathbf 1\{\exists r<n: Z_r=Z_{r+1}=i\},\qquad X_n=\sum_{i\ge1}I_{n,i}.$$

Independently let $Y_{n,i}\sim\operatorname{Pois}(nP_i^2)$, $J_{n,i}=\mathbf1\{Y_{n,i}>0\}$, and $\xi_n=\sum_{i\ge1}J_{n,i}$.

Write $L=\log n$, and choose the smallest $a=a_n$ with $nP_a^2\le L^4$. Then $a=O_p(L)$, $q^2L^4<nP_a^2\le L^4$, and $nP_i^2>L^4$ for $i<a$. Independent disjoint trials give

$$\Pr(I_{n,i}=0)\le(1-P_i^2)^{\lfloor n/2\rfloor}, \qquad \Pr(J_{n,i}=0)=e^{-nP_i^2}.$$

Consequently both head subvectors equal the all-ones vector except with probability at most $2a e^{-L^4/3}$.

For $r<n$, $i\ge a$, introduce the occurrence variables

$$W_{r,i}=\mathbf1\{Z_r=Z_{r+1}=i\}.$$

Give $(r,i)$ the dependency neighborhood consisting of all $(s,j)$ with $|s-r|\le1$. Variables outside this neighborhood are independent. With

$$S_\ell=\sum_{i\ge a}P_i^\ell=\frac{P_a^\ell}{1-q^\ell},$$

the two nonzero Chen--Stein dependency sums are exactly

$$b_1=(3n-5)S_2^2,\qquad b_2=2(n-2)S_3.$$

Indeed, overlapping occurrences of distinct letters are impossible, whereas overlapping occurrences of the same letter have probability $P_i^3$.

By the point-process Poisson approximation of Arratia, Goldstein, and Gordon, Theorem 2, the entire tail occurrence field couples to independent Poisson variables at total-variation cost at most $4(b_1+b_2)$. The countable version follows by finite truncation and monotone convergence. Summing over positions and applying the indicator map yields independent Poisson means $(n-1)P_i^2$. Independent Poisson increments change these to $nP_i^2$ at additional cost at most $S_2$. Therefore

$$\begin{aligned} d_{\rm TV}\left( \mathcal L((I_{n,i})_{i\ge1}), \mathcal L((J_{n,i})_{i\ge1}) \right) &\le \frac{12L^8}{n(1-q^2)^2} +\frac{8L^6}{\sqrt n(1-q^3)} +\frac{L^4}{n(1-q^2)} +2a e^{-L^4/3}\\ &=O_p\left(\frac{(\log n)^6}{\sqrt n}\right). \end{aligned} \tag{*}$$

In particular, uniformly even over moving thresholds,

$$\sup_{t\in\mathbb R} \left|\Pr(X_n\le t)-\Pr(\xi_n\le t)\right| =O_p\left(\frac{(\log n)^6}{\sqrt n}\right).$$

To obtain all absolute centered moments, fix $k\ge1$ and put

$$M_n=\left\lceil\frac{(k+4)\log n}{2|\log q|}\right\rceil, \qquad \Lambda_n=n\sum_{i>M_n}P_i^2=O_p(n^{-k-3}).$$

For the genuine count, the probability that any omitted letter occurs as a repeated pair is at most $\Lambda_n$, and $X_n\le n-1$; thus deleting the tail changes its first $k$ raw moments by $o(1)$. For the independent count the number of omitted Poisson occurrences is $\operatorname{Pois}(\Lambda_n)$, independent of the first $M_n$ coordinates, so the same conclusion follows from the Poisson moment formulas.

Both truncated counts lie in $[0,M_n]$. The maximal coupling in (*) gives moment errors bounded by

$$M_n^j\,d_{\rm TV} =O_{p,j}\left(\frac{(\log n)^{j+6}}{\sqrt n}\right), \qquad 1\le j\le k.$$

Their exact means therefore differ by $o(1)$. Finally,

$$\big||x-u|^k-|y-v|^k\big| \le k(|x|+|y|+|u|+|v|)^{k-1}(|x-y|+|u-v|)$$

also handles odd absolute moments after coupling and restoring the negligible tails. Hence, for every fixed positive integer $k$,

$$\mathbb E|X_n-\mathbb EX_n|^k - \mathbb E|\xi_n-\mathbb E\xi_n|^k \longrightarrow0.$$

Thus both Conjectures 3.1 and 3.4 of Louchard, Schachinger, and Ward, Discrete Mathematics and Theoretical Computer Science 25 (2023) hold; their previously conditional cumulant and distribution formulas are consequently unconditional.