Proof. Take expectations of (1.1) to get

\begin{align*}{\mathbb E}[C_{n,k}] = \sum_{i=1}^n \sum_{r=1}^n \mathbf{1}_{\{|r -i| \le k\}}\, {\mathbb P}(\pi_i= r) = \dfrac 1 n\sum_{i=1}^n \sum_{r=1}^n \mathbf{1}_{\{|r -i| \le k\}}. \end{align*}

Here and throughout, we call the sum $\sum_{r=1}^n \mathbf{1}_{\{|r -i| \le k\}}$ by the name $x_{n,i,k}$ . In view of edge effects, we evaluate $x_{n,i,k}$ piecewise and deal with cases. Thus $x_{n,i,k}$ counts the 1s across row i in this matrix.

The case $0\le k < n/2$ . We find

\begin{align*}x_{n,i,k} = \begin{cases} k+i , &\text{for $ i = 1,\ldots,k$,}\\[3pt] 2k+1 , & \text{for $ i = k+1, \ldots, n-k$,}\\[3pt] k+1+ n-i, &\text{for $ i = n-k+1, \ldots,n$.} \end{cases} \end{align*}

It follows that

(2.1) \begin{align}\sum_{i=1}^n x_{n,i,k} &= \sum_{i=1}^k (k+i) + \sum_{i=k+1}^{n-k} (2k+1) + \sum_{i=n-k+1}^n (k+1+n-i)\nonumber \\[3pt] &= (2k+1)n - k(k+1). \end{align}

The case $k \ge n/2$ . We find

\begin{align*}x_{n,i,k} = \begin{cases} k+i , &\text{for $ i = 1,\ldots,n-k-1$,}\\[3pt] n , & \text{for $ i = n-k, \ldots, k+1$,}\\[3pt] k+1 +n-i , &\text{for $ i = k+2, \ldots,n$.} \end{cases} \end{align*}

It follows that

\begin{align*}\sum_{i=1}^n x_{n,i,k} &= \sum_{i=1}^{n-k-1} (k+i) + \sum_{i=n-k}^{k+1} n + \sum_{i=k+2}^n (k+1+n-i)\nonumber \\[3pt] &= (2k+1)n - k(k+1),\end{align*}

which is the same expression as the counterpart in the case $k < n/2$ . In either case, we get

\begin{equation*}{\mathbb E}[C_{n,k}] = \dfrac 1 n\sum_{i=1}^n x_{n,i,k} = (2k+1) - \dfrac k n(k+1).\end{equation*}

Proof. Take expectations of (3.1), noting that for distinct i and j, the positions $\pi_i$ and $\pi_j$ are distinct, and the joint distribution of $(\pi_i,\pi_j)$ is uniform over $[n]\times [n] -\{(i,i) \colon i = 1, \ldots, n \}$ . This yields

\begin{align*}{\mathbb E}\big[C_{n,k}^2\big] = {\mathbb E}[C_{n,k}] + \dfrac 1 {n(n-1)} \sum_{\substack{1\le i,j,r,s \le n\\[3pt] i\not= j, r\not = s}} \mathbf{1}_{\{|r -i| \le k\}}\, \mathbf{1}_{\{|s-j| \le k\}}. \end{align*}

For economy of space, we introduce the notation $\mathbf{J}_{p,q,k} = \mathbf{1}_{\{|p -q| \le k\}}$ to write the last relation as

\begin{align*}{\mathbb E}\big[C_{n,k}^2\big] &= {\mathbb E}[C_{n,k}] + \dfrac 1 {n(n-1)} \sum_{\substack{1\le i,j,r,s \le n \\[3pt] i \not = j, r \not = s}}\mathbf{J}_{r,i,k}\, \mathbf{J}_{s,j,k} \\[3pt] &= {\mathbb E}[C_{n,k}] + \dfrac 1 {n(n-1)} \!\left(\rule{0pt}{21pt}\right.\! \sum_{\substack{1\le i,j,r,s \le n \\[3pt] r \not = s}} \mathbf{J}_ {r,i,k}\, \mathbf{J}_{s,j,k} - \sum_{\substack{1\le i,r,s \le n\ r \not = s}} \mathbf{J}_{r,i,k}\,\mathbf{J}_{s,i,k}\!\left.\rule{0pt}{21pt}\right)\!\\[3pt] &\, =\!: \, {\mathbb E}[C_{n,k}] + \dfrac 1 {n(n-1)}( L_{n,k} - M_{n,k}) ,\end{align*}

where $L_{n,k}$ and $M_{n,k}$ are the two four-fold sums in the penultimate line, defined in their order of appearance.

We have an exact expression for ${\mathbb E}[C_{n,k}]$ from Proposition 2.1. The evaluation of these four-fold sums requires a very lengthy computation that can be distracting; we only give the result here and relegate the detailed derivation to the appendix. We have

\begin{align*}L_{n,k} &= \begin{cases} (2k+1)((2k+1) n^2 - (2k^2 + 4k +1)n)\\[3pt] \quad{} + \tfrac{1}{3} k(k+1)(3k^2+13k+5), & \text{for $ 0 \le k < n/2$,}\\[3pt] \tfrac{1}{3} n^3 + 2k(2k+1)n^2 - ( 4k^3 +6k^2 +2k + \tfrac{1}{3}) n \\[3pt] \quad {}+ \tfrac{1}{3} k(k+1) (3k^2 +5k +1), & \text{for $ n/2 \le k < n$,}\\[3pt] \end{cases}\end{align*}

and

\begin{align*}M_{n,k} &= \begin{cases} 2k(2k+1)n - \tfrac{2}{3} k(k + 1)(5k + 1), & \text{for $ 0 \le k < n/2$,}\\[3pt] - \tfrac{1}{3} n^3 + (2k +1) n^2 - \tfrac{2}{3} (3k+1) n - \tfrac{2}{3} k(k^2-1), &\text{for $ n/2\le k < n$.} \end{cases}\end{align*}

Assembling all the elements and simplifying, we get

\begin{align*}{\mathbb E}\big[C_{n,k}^2\big] = \begin{cases} (6(k+1)(2k+1) n^2 - 3(4k^3 +15k^2 +11k + 2)n \\[3pt] \quad {}+ k(k+1)(3k^2+23k +10)) /(3n(n - 1)), &\text{for $ 0 \le k < n/2$,}\\[3pt] (2 n^3 + 6k (2k+1) n^2 -( 12k^3+21k^2+9k+2)n\\[3pt] \quad {} +k(k+1)(k+2) (3k+1)) /(3n(n - 1)), & \text{for $ n/2\le k < n$.}\end{cases}\end{align*}

The variance follows from the computation of ${\mathbb E}\bigl[C_{n,k}^2\bigr] - {\mathbb E}^2[C_{n,k}]$ and further algebraic simplification yielding the stated expression.

Proof. The parts of the theorem are treated by different methods. In certain parts, we use Bolthausen’s theorem (Theorem 5.1) or the Arratia–Goldstein–Gordon theorem (Theorem 5.2) specialized to the k-window matrix $\mathbf{A}_n$ described in the paragraph before Section 2.

(a) Let k be a fixed natural number. We start from the representation (1.1) of $C_{n,k}$ as a sum of indicators. The factorial moments of a sum of indicators have a special form [Reference Johnson, Kemp and Kotz11, Chapter 2]:

(5.2) \begin{equation}{\mathbb E}[(C_{n,k})_r] = \sum_{i_1, \ldots, i_r \in Q_{n,r}} {\mathbb E}\bigl[\mathbf{1}_{\{|\pi_{i_1} -i_1| \le k\}}\cdots \mathbf{1}_{\{|\pi_{i_r} -i_r| \le k\}}\bigr],\end{equation}

where $Q_{n,r}$ is the set of tuples of r distinct integers from [n]. We first establish an upper bound. For any fixed r, let n be large enough to pack r non-intersecting windows centered at $i_1, \ldots, i_r$ . There are at most $(2k+1)$ placements for each of the chosen indices within its window that give rise to success (value 1) of the corresponding indicator. (We say ‘at most’ to take into account possible edge effects for the first and the last indices.)

The rest of the elements of [n] can be distributed freely over the remaining positions in $(n-r)!$ ways. That is, all the indicators in the summand will be 1 and their product is 1 with probability at most $(n-r)!\, (2k+1)^r / n!$ . If some of the windows intersect, $(2k+1)$ remains as an upper bound on the number of positions for the success of an indicator in the summand. This counting leads to the bound

\begin{align*}{\mathbb E}[(C_{n,k})_r] &\le \sum_{i_1, \ldots, i_r \in Q_{n,r}} \dfrac {(n-r)!\,(2k+1)^r} {n!}\\[3pt] &=\dfrac {(n-r)!\,(2k+1)^r} {n!}\, n(n-1) \cdots (n-r+1)\\[3pt] & = (2k+1)^r.\end{align*}

Toward a lower bound, consider the set $Q_{n,r}'$ of r-tuples of well-separated indices, in which the difference between any two indices in the tuple is at least $2k+1$ , and the smallest and largest of these indices are at distance at least k from the edges.

We break up the sum in (5.2) into two sums, one over $Q_{n,r}'$ and another over $Q_{n,r}-Q_{n,r}'$ . We keep only the sum over $Q_{n,r}'$ . On the set $Q_{n,r}'$ there are exactly $2k+1$ positions for $i_j$ to fall within its window, for $j=1, \ldots, r$ , and obtain the lower bound

\begin{align*}{\mathbb E}[(C_{n,k})_r] \ge \sum_{i_1, \ldots, i_r \in Q_{n,r}'} \dfrac {(n-r)!\,(2k+1)^r} {n!} = \dfrac {(n-r)!\,(2k+1)^r} {n!} \, |Q_{n,r}'|. \end{align*}

The size of $Q_{n,r}'$ can be computed by figuring out the number of ways to place elements in the gaps between the well-separated blocks as follows. Let the number of elements preceding the first window be $\delta_0$ , let the distance (number of keys) in the gap between the ith and $(i+1)$ th windows be $\delta_i$ , and let the number of elements following the rth window be $\delta_r$ . We need to solve

\begin{align*}\delta_0 + \delta_1 +\cdots + \delta_r = n - (2k+1)r \end{align*}

in non-negative integers. By a standard stars-and-bars count, we find

\begin{align*}|Q_{n,r}'| = r! {\binom{n-2kr}{r}}. \end{align*}

We go further with the lower bound to get

\begin{align*}{\mathbb E}[(C_{n,k})_r] \ge \dfrac {(n-r)!\,(2k+1)^r} {n!} \, {(n-2kr)_r} . \end{align*}

From the lower and upper bounds, we tightly sandwich the rth factorial moment of the k-window statistic:

(5.3) \begin{equation}(2k+1)^r \biggl(1 - \Theta\biggl(\dfrac 1 n\biggr)\biggr) \le {\mathbb E}[(C_{n,k})_r] \le (2k+1)^r. \end{equation}

Take the limit (as $n\to\infty$ ), for any fixed k, to find that ${\mathbb E}[(C_{n,k})_r]\to (2k+1)^r$ . We know that $(2k+1)^r$ are the factorial moments of $\operatorname{Poi}(2k+1)$ , and convergence of all factorial moments implies convergence in distribution, while uniquely characterizing the limit. Since the factorial moments converge to those of a Poi $(\lambda)$ law, convergence in distribution to $\operatorname{Poi}(2k+1)$ is implied in the standard moment theorem [Reference Billingsley5, Theorem 30.2].

(b) We next consider $k=k_n$ growing, but remaining ${\mathrm{o}} (n)$ , as $n\to\infty$ . The characteristic function of a random variable, V, has a standard expansion in terms of factorial moments (see e.g. [Reference Johnson, Kemp and Kotz11, Chapter 2]):

\begin{align*}\phi_V(t) = \sum_{r=0}^\infty {\mathbb E}[(V)_r]\, \dfrac{({\mathrm{e}}^{{\mathrm{i}} t} -1)^r}{r!}. \end{align*}

By (5.3), the characteristic function of $C_{n,k}$ is

\begin{align*}\phi_{n,k_n} (t) &\sim \sum_{r=0}^\infty (2k_n)^r\dfrac{({\mathrm{e}}^{{\mathrm{i}} t} -1)^r}{r!}\\[3pt] &= {\mathrm{e}}^{2k_n ({\mathrm{e}}^{{\mathrm{i}} t}-1)}\\[3pt] &= {\mathrm{e}}^{2k_n ({\mathrm{i}} t - t^2/2 + {\mathrm{O}} (t^3))}.\end{align*}

Hence, as $n\to\infty$ , we have

\begin{align*}\phi_{n,k_n} \biggl(\dfrac t {\sqrt{k_n}}\biggr)\exp\biggl(-\frac {2{\mathrm{i}} k_nt} {\sqrt{k_n}}\biggr) &\to \exp\biggl(2k_n \biggl(- \dfrac {t^2} {2k_n} + {\mathrm{O}}\biggl(\dfrac {t^3} {k_n^{3/2}}\biggr)\biggr),\end{align*}

from which we conclude that

\begin{align*}\dfrac {C_{n,k} - 2k_n} {\sqrt {k_n}} \to {\mathrm{e}}^{-t^2}. \end{align*}

The right-hand side in the last convergence relation is the characteristic function of $\mathcal{N}(0,2)$ . By Lévy’s continuity theorem [Reference Billingsley5, Theorem 26.3], part (b) is proved.

(c)–(d) In the linear regime of these two parts, we have $k_n\sim \alpha n$ , with $\alpha \in (0, 1)$ . Let $\sigma_{\mathbf{A}_n}^2 = \operatorname{Var}[C_{n,k}]$ . By the symmetry of $\mathbf{A}_n$ , we have $x_{n,j,k} = x_{n, n-j+1,k}$ . With every $a_{i,j}$ being 0 or 1, and $a_{i.}=x_{n,i,k}/n$ , $a_{.j} = x_{n,n-j+1,k}/n$ , and the proportion of 1s in the matrix all being fractions, each of the four factors in Bolthausen’s bound is absolutely bounded by 1. We have the bound

\begin{align*}\sup_{x}\biggl(\biggl|{\mathbb P}\biggl(\dfrac{C_{n,k_n} - {\mathbb E}[C_{n,k}]} {\sigma_{\mathbf{A}_n}} \le x\biggr) - \Phi(x)\biggr|\biggr)\le \dfrac K n \sum_{1\le i,j\le n} \biggl(\dfrac 4 {\sigma_{\mathbf{A}_n}}\biggr)^3 =\dfrac {64 K n}{\sigma_{\mathbf{A}_n}^3}. \end{align*}

The variance of $C_{n,k_n}$ in this regime is asymptotic to $\rho (\alpha)n$ (see Proposition 3.1). Asymptotic normality follows. After cleaning up via Slutsky’s theorem, we get

\begin{align*}\dfrac {C_{n,k_n}- \alpha (2-\alpha) n} {\sqrt n} \ {\buildrel \mathcal{D} \over \longrightarrow}\ \mathcal{N}(0,\rho(\alpha)) \quad \text{as $ n \to\infty$;} \end{align*}

the rate of convergence is ${\mathrm{O}} (1/\sqrt n\,)$ . Recall that the linearity coefficient $\rho(\alpha)$ in the variance in the regime $(0,\tfrac{1}{2})$ is different from the linearity coefficient in the regime $[\tfrac{1}{2}, 1)$ (see the discussion in Section 3.1). For each part, we use the corresponding $\rho(\alpha)$ . Parts (c) and (d) are proved.

(e) Consider next the regime $k_n = n - g_n$ , for $g_n = {\mathrm{o}} (n)$ but growing faster than $\sqrt n$ . Again, we use Bolthausen’s theorem (Theorem 5.1). We examine the geometry of $\mathbf{A}_n$ . It has two corners filled with zeros. These are positions excluded from viewing. The top row has $g_n -1$ excluded cells flushed to its right end, the second row has $g_n-2$ excluded cells flushed to its right end, and so on until we reach row $g_n-1$ , which has one excluded cell at its rightmost position. There are $(g_n-1) + (g_n-2)+ \cdots +1 =g_n(g_n-1)/2 $ excluded cells in this top right corner. The lower left corner is a mirror image of the top right one. So we have exactly $(g_n-1)g_n$ excluded cells.

To the double sum (5.1) in Bolthausen’s theorem, a cell containing $a_{i,j}=1$ contributes

\begin{align*}& \biggl|1 - \dfrac {x_{n,i,k}} n - \dfrac {x_{n,n-j+1,k}} n + \dfrac {n^2 -g_n(g_n-1)} {n^2}\biggr|^3 \\[3pt] &\quad = \biggl|1 - \dfrac {n-{\mathrm{O}} (g_n)} n - \dfrac {n-{\mathrm{O}} (g_n)} n + \dfrac {n^2 -g_n(g_n-1)} {n^2}\biggr|^3\\[3pt] & \quad = {\mathrm{O}}\biggl(\dfrac {g_n^3} {n^3}\biggr),\end{align*}

whereas a cell containing $a_{i,j}=0$ contributes

\begin{align*} \biggl|0 - \biggl(1+ {\mathrm{O}}\biggl(\dfrac {g_n} n\biggr)\biggr) - \biggl(1+ {\mathrm{O}}\biggl(\dfrac {g_n} n\biggr)\biggr) + \biggl(1- {\mathrm{o}}\biggl(\dfrac {g_n} n\biggr)\biggr) \biggr|^3 = 1 + {\mathrm{O}}\biggl(\dfrac {g_n} n\biggr). \end{align*}

The double sum (5.1) in Bolthausen’s theorem amasses $(n^2 -g_n(g_n-1)){\mathrm{O}} ({{g_n^3}/{ }}{n^3})$ from the cells containing 1 and $g_n(g_{n-1})(1 + {\mathrm{O}} ({{g_n}/{ }}{n}))$ from the excluded zeros at the corners, a total double sum of order $g_n^2$ . The variance is asymptotic to $g_n^2/n$ and the overall bound is

\begin{align*}\frac{{\mathrm{O}} \left(g_n^2\right) }{ n \Theta \left({{g_n^2 }/{ n}}\right)^{3/2}} = \Theta \biggl(\frac {\sqrt n} {g_n}\biggr). \end{align*}

The bound tends to 0 for the regime $k_n = n - g_n$ , with $n = {\mathrm{o}} (g_n^2)$ . Limiting Gaussianity follows. After cleaning up via Slutsky’s theorem, part (e) is proved.

(f) In the critical regime $k_n = n - g_n$ , with $g_n \sim c \sqrt n$ , and $c\in {\mathbb R}^+$ , we prove a Poisson limit. Let us first focus on $C_{n, k_n}' = n - C_{n,k_n}$ , which counts the number of permutation elements lying outside their viewing window.

The natural indexing by the set $\{1, \ldots, n\}$ gives bounds on the total variation distance that are too high to be of use. It is then helpful to work with refined indexing $\mathcal{I}$ , derived from the representation of $\{|\pi_i -i | > k_n\}$ as a union of individual atoms specified by locations on row i.

On row $i \in\{1, \ldots, g_n-1\}$ , the set $\mathcal{I}$ collects

\begin{align*}\{(i,i+ k+1)\} \cup \{(i, i+k+2)\} \cup \cdots \cup \{(i,n)\}. \end{align*}

On row $i\in \{n-g_n+2, \ldots, n\}$ , the set $\mathcal{I}$ collects

\begin{align*}\{(i,1)\} \cup \{(i,2)\} \cup \cdots \cup \{(i,i+g_n-n-1)\}. \end{align*}

On rows $i=g_n, \ldots, n-g_n +1$ , the sets $\{|\pi_i -i | > k_n\}$ are empty and add nothing to $\mathcal{I}$ . So the indexing set can be written as

\begin{align*}\mathcal{I} = \Biggl(\bigcup_{i=1}^{g_n-1} \bigcup_{j=i+k+1}^n {\{(i,j)\}}\Biggr) \bigcup \Biggl(\bigcup_{i=n-g_n+2}^n \bigcup_{j=1}^{i+g_n-n-1} {\{(i,j)\}}\Biggr). \end{align*}

The size of the indexing set is $2((g_n-1)+(g_n -2) + \cdots +1) = g_n (g_n-1)$ .

For $(i,j)\in [n]\times [n]$ , define $X_{(i,j)}= \mathbf{1}_{\{\pi_i = j\}}$ . Now we have

\begin{align*}C_{n,k_n}' = \sum_{i=1}^n \mathbf{1}_{\{|\pi_i -i | > k_n\}}= \sum_{i=1}^n \sum_{\alpha = (i,j)\in \mathcal{I}} X_{(i,j)}. \end{align*}

After all, with this representation, $C_{n,k_n}'$ is the sum of a large number of Bernoulli random variables, making the case a candidate for Poisson approximation via the Chen–Stein method.

In the Arratia–Goldstein–Gordon version of the Chen–Stein method (Theorem 5.2), take the dependency neighborhood corresponding to $\alpha=(i,j)\in\mathcal{I}$ to be

\begin{align*}B_\alpha = \{\beta =(i', j') \colon i'=i {\ \rm or\ } j' = j\}. \end{align*}

In other words, we take $X_\beta$ to be in the dependency neighborhood of $X_\alpha$ if the cell specified by the pair $\beta= (i',j')$ in the matrix $\mathbf{A}_n$ is in the same row or column as $\alpha=(i,j)$ . The size of the dependency neighborhood of $\alpha \in \mathcal{I}$ is at most $g_n+ g_n-1 = 2g_n-1$ .

We next go through the calculation of the three components $b_1,b_2,b_3$ . For $b_1$ , we use that the size of $B_\alpha$ of any $\alpha\in \mathcal{I}$ is at most $2g_n-1$ , and the size of $\mathcal{I}$ is $g_n(g_n-1)$ , and that we are in the regime $g_n \sim c\sqrt n$ to get

\begin{align*}b_1 =\sum_{\alpha \in \mathcal{I}}\dfrac {|B_\alpha|} {n^2} \le \dfrac {|\mathcal{I}| (2g_n-1)}{n^2} = \Theta\biggl(\dfrac 1 {\sqrt n}\biggr). \end{align*}

As no two elements can occupy the same location in the permutation, and no element appears in two places in the permutation, if $X_\alpha = 1$ , then $X_\beta=0$ for all $\beta\in B_\alpha- \{\alpha\}$ . Otherwise, $X_\alpha = 0$ . In both cases $X_\alpha X_\beta=0$ and $b_2=0$ .

The computation of $b_3$ requires conditioning on the variables $X_\beta$ , with $\beta$ in the subset $H_\alpha = \{\beta\in \mathcal{I}\colon \beta\not \in B_\alpha\}$ . By the geometry of the neighborhoods, if $X_\beta =1$ , for $\beta\in H_\alpha$ , then this deprives $X_\alpha$ from a position in the permutation, as $\beta \in H_\alpha$ specifies a cell in $\mathbf{A}_n$ in a different row and a different column from $\alpha$ . Therefore, for $\alpha = (i,j) \in \mathcal{I}$ , conditionally, there are $n - \sum_{\beta \in H_\alpha} X_\beta$ equally likely positions for i.

Observe that at most one among the Bernoulli random variables in a row within $\mathcal{I}$ can equal 1 (an element of [n] cannot be at two positions in the permutation). In other words, the sum of all the Bernoulli random variables on the same row of $\mathcal{I}$ is one combined Bernoulli random variable. Conditionally, there are

\begin{align*}n - \sum_{\substack{i'=1 \\[3pt] i'\not =i}}^{g_n-1} \tilde X_{i'} - \sum_{\substack{i''=n-g_n+2 \\[3pt] i''\not =i}}^n \tilde X_{i''} , \end{align*}

for Bernoulli random variables

\begin{align*}\tilde X_{i'} = \sum_{j=n-g_n+i'+1}^n X_{(i',j)} \quad \text{for $ i' \in\{ 1 ,\ldots, g_n-1\}$,} \end{align*}

and

\begin{align*}\tilde X_{i''} = \sum_{j=1}^{i''-n+g_n-1} X_{(i'',j)} \quad \text{for $ i'' \in \{ n-g_n+2 ,\ldots, n\}$.} \end{align*}

So we have

\begin{align*} b_3 &= \sum_{\alpha =(i,j)\in \mathcal{I}} \mathbb{E}\left[\dfrac{1}{n - \sum_{\substack{i'=1 \\ i'\neq i}}^{g_n-1} \tilde{X}_{i'} - \sum_{\substack{i''=n-g_n+2 \\ i''\neq i}}^n \tilde{X}_{i''}} - \dfrac{1}{n}\right] \\[3pt] &= \sum_{\alpha \in \mathcal{I}} \mathbb{E}\left[\dfrac{\sum_{\substack{i'=1 \\ i'\neq i}}^{g_n-1}\tilde{X}_{i'} + \sum_{\substack{i''=n-g_n+2 \\ i''\neq i}}^n \tilde{X}_{i''}}{n\Big(n - \sum_{\substack{i'=1 \\ i'\neq i}}^{g_n-1}\tilde{X}_{i'} - \sum_{\substack{i''=n-g_n+2 \\[3pt] i''\neq i}}^n \tilde{X}_{i''}\Big)}\right] \end{align*}

\begin{align*} &\le \sum_{\alpha \in \mathcal{I}} \dfrac{2(g_n-1)}{n(n - 2 (g_n-1))} \\[3pt] &= \dfrac{2|\mathcal{I}|\, (g_n-1)}{n(n - 2(g_n-1))} \\[3pt] &= \dfrac{\mathrm{O}(g^3(n))}{\Theta(n^2)} \\[3pt]&= \mathrm{O}\left(\dfrac{1}{\sqrt{n}}\right). \end{align*}

With $b_2=0$ and both $b_1$ and $b_3$ being of order $1/ \sqrt n$ , in Theorem 5.2, we get to the conclusion that

\begin{align*}d_{\textit{TV}} \bigl(C_{n,k_n}', \operatorname{Poi}\bigl({\mathbb E}\bigl[C_{n,k_n}'\bigr]\bigr)\bigr) = {\mathrm{O}}\biggl(\dfrac 1 {\sqrt n}\biggr). \end{align*}

By the triangle inequality, we have

\begin{align*}d_{\textit{TV}} \bigl(C_{n,k_n}', \operatorname{Poi}(c^2)\bigr) &\le d_{\textit{TV}} \bigl(C_{n,k_n}',\operatorname{Poi}\bigl({\mathbb E}\bigl[C_{n,k_n}'\bigr]\bigr)\bigr) + d_{\textit{TV}} \bigl(\operatorname{Poi}\bigl({\mathbb E}\bigl[C_{n,k_n}'\bigr], \operatorname{Poi}(c^2)\bigr)\bigr)\\[3pt] &= {\mathrm{O}}\biggl(\dfrac 1 {\sqrt n}\biggr) + d_{\textit{TV}} \bigl(\operatorname{Poi}\bigl({\mathbb E}\bigl[C_{n,k_n}'\bigr], \operatorname{Poi}(c^2)\bigr).\end{align*}

As shown in [Reference Lyon and Mahmoud12, Lemma 4.2], the total variation distance between two Poisson distributions is at most the absolute difference between their parameters. So we have

\begin{align*} d_{\textit{TV}} \bigl(\operatorname{Poi}\bigl({\mathbb E}\bigl[C_{n,k_n}'\bigr], \operatorname{Poi}(c^2)\bigr)\bigr) = \bigl|n -{\mathbb E}\bigl[C_{n,k_n}\bigr] - c^2\bigr|. \end{align*}

The expectation of $C_{n,k_n}$ is given in Proposition 2.1. After a calculation, we find that the latter total variation distance is ${\mathrm{O}} (1/ \sqrt n\,)$ too. We have arrived at

\begin{align*}d_{\textit{TV}} \bigl(n - C_{n,k_n}, \operatorname{Poi}(c^2)\bigr) \to 0 \quad \text{as $ n \to \infty$,} \end{align*}

which implies that $n - C_{n,k_n}\, {\buildrel \mathcal{D} \over \longrightarrow}\, \operatorname{Poi}(c^2)$ . Part (f) is proved.

(g) In the extremal regime $n-g_n$ , with $g_n = {\mathrm{o}} (\sqrt n\,)$ , the variance is ${\mathrm{O}} (g_n^2/n)$ . For every $\varepsilon >0$ , the Chebyshev inequality gives

\begin{align*}{\mathbb P} \bigl(\bigl|C_{n, k_n} - {\mathbb E}\bigl[C_{n, k_n}\bigr] \bigr|> \varepsilon\bigr) \le \dfrac{{\mathrm{O}} \left(g_n^2/n\right)} {\varepsilon^2} \to 0 \quad \text{as $ n \to\infty$,} \end{align*}

which means $C_{n, k_n} - {\mathbb E}[C_{n, k_n}]\buildrel {\mathbb P} \over \longrightarrow 0$ . It is discussed in Section 2.1 that $ {\mathbb E}[C_{n, k_n}] -n \to 0.$ The addition rule of probabilistic convergence relations proves part (g).