Gaussian limiting distribution for the three-letter pair count

Proof of the full Gaussian limiting-distribution conjecture for every geometric parameter.

Fix $0<p<1$, write $q=1-p$, and let independent letters satisfy $P_i=\Pr(Z_r=i)=pq^{i-1}$. For distinct ordered pairs set

$$I_{ij}=\mathbf1\{\exists r<n:(Z_r,Z_{r+1})=(i,j)\}, \qquad X_n=\sum_{i\ne j}I_{ij}.$$

We prove

$$\frac{X_n-\mathbb EX_n}{\sqrt{\operatorname{Var}(X_n)}} \Longrightarrow N(0,1).$$

1. Common-letter rows have uniformly bounded fluctuations. Independent disjoint position trials and a union bound give

$$\Pr(I_{ij}=0)\le e^{-\lfloor n/2\rfloor P_iP_j}, \qquad \Pr(I_{ij}=1)\le nP_iP_j.$$

For fixed $i$, let $j_i$ be the last index with $nP_iP_{j_i}\ge1$. Relative to the deterministic cutoff $d_i=\#\{j\le j_i:j\ne i\}$, Minkowski's inequality gives

$$\left\|\sum_{j\ne i}I_{ij}-d_i\right\|_2 \le \sum_{r\ge0}e^{-q^{-r}/6} + \sum_{r\ge1}q^{(r-1)/2} =:C_q<\infty.$$

The same estimate holds for columns and restricted rows. Put $L=\log n$,

$$K=\left\lceil\frac{10\log L}{|\log q|}\right\rceil, \qquad \rho=q^K\le L^{-10}.$$

If $E_n$ counts all directed unequal pair types with at least one letter at most $K$, summing the row and column bounds gives

$$\|E_n-\mathbb EE_n\|_2=O(K)=O(\log\log n). \tag{1}$$

2. Poisson coupling for rare central types. Among $i,j>K$, $i\ne j$, declare types with $nP_iP_j>L^4$ saturated. Their simultaneous occupancy fails with probability $O(L^2)e^{-L^4/3}$. For the remaining types use occurrence indicators

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

Their dependency neighborhoods are precisely the occurrence indices whose positions differ by at most one. Set $b=L^4/n$ and

$$R_j=\sum_{\substack{i>K\P_iP_j\le b}}P_i \le\min\left(\rho,\frac{b}{pP_j}\right).$$

Geometric summation, split at $P_j=b/(p\rho)$, gives

$$S=\sum_{\rm rare}P_iP_j=O(bL), \qquad H=\sum_{j>K}P_jR_j^2=O(\rho b).$$

Hence the Chen--Stein dependency sums satisfy

$$b_1\le3nS^2=O(L^{10}/n), \qquad b_2\le2nH=O(L^{-6}), \qquad b_3=0.$$

The point-process theorem of Arratia, Goldstein, and Gordon therefore couples the entire rare-type occupancy field to independent variables

$$B_{ij}=\mathbf1\{N_{ij}>0\}, \qquad N_{ij}\sim\operatorname{Pois}((n-1)P_iP_j),$$

with total-variation error

$$\delta_n=O(L^{10}/n+L^{-6}). \tag{2}$$

Let $C_n=X_n-E_n$ and

$$V_n=\#\{\text{saturated central types}\} +\sum_{\rm rare}B_{ij}.$$

Truncating letters above $J=\lceil12L/|\log q|\rceil$ costs $O(n^{-11})$. The remaining counts are bounded by $J^2=O(L^2)$, so (2) yields

$$|\mathbb EC_n-\mathbb EV_n|=O(L^2\delta_n)+o(1)=o(1),$$ $$|\operatorname{Var}(C_n)-\operatorname{Var}(V_n)| =O(L^4\delta_n)+o(1)=o(1). \tag{3}$$

3. Independent triangular-array central limit theorem. Independence gives

$$\sigma_n^2=\operatorname{Var}(V_n) =\sum_{\rm rare}e^{-\lambda_{ij}}(1-e^{-\lambda_{ij}}), \qquad \lambda_{ij}=(n-1)p^2q^{i+j-2}.$$

Choose $u_n$ with $1\le(n-1)p^2q^{u_n-2}<q^{-1}$. The antidiagonal $i+j=u_n$ contains $\Theta(L)$ admissible ordered types, each contributing variance bounded below by a positive constant. Summing adjacent antidiagonals using

$$e^{-\lambda}(1-e^{-\lambda})\le\min(\lambda,e^{-\lambda})$$

also gives the matching upper bound. Therefore

$$\sigma_n^2=\Theta(\log n).$$

The independent centered Bernoulli summands are bounded, so the Lindeberg theorem yields

$$\frac{V_n-\mathbb EV_n}{\sigma_n}\Longrightarrow N(0,1).$$

By (2)--(3) this transfers to $C_n$, and (1) contributes only $O(\log\log n)=o(\sqrt{\log n})$ in $L^2$. Moreover,

$$\operatorname{Var}(X_n) =\sigma_n^2+O(\sqrt{\log n}\log\log n+(\log\log n)^2) =\sigma_n^2(1+o(1)).$$

Slutsky's theorem proves the displayed Gaussian limit.

This resolves Conjecture 4.14 in Louchard, Schachinger, and Ward, Discrete Mathematics and Theoretical Computer Science 25 (2023), pp. 30–31, whose published heuristic expressly leaves a rigorous proof open. The separate bounded-cumulant conjecture is not needed here.