Variant of the Strong Law of Large Numbers

Question

Let $X_1,X_2,\ldots$ be a i.i.d. sequence of random variables with uniform distribution on $[0,1]$, with $X_n: \Omega \to \mathbf{R}$ for each $n$.

Question. Is it true that $$ \mathrm{Pr}\left(\left\{\omega \in \Omega: \lim_{n\to \infty}\frac{\sum_{1\le i\le j \le n}{\bf{1}}_{(-1/n,1/n)}{(X_i(\omega)-X_j(\omega))}}{n}=2\right\}\right)=1\,\,\,? $$

Here ${\bf{1}}_A(z)$ is the characteristic function of $A$, that is, it is $1$ if $z \in A$ and $0$ otherwise.

Answer 1

Yes. Here is a proof sketch:

1) The statement is equivalent to the statement $\frac{Z_n}{n}\rightarrow 2$ with prob 1, where $$ Z_n = \sum_{i=1}^n \sum_{j \in \{1, ..., n\}, j \neq i} 1_{\{|X_i-X_j|\leq 1/n\}}$$

2) We get $E[\frac{Z_n}{n}]\rightarrow 2$ and $Var(\frac{Z_n}{n}) = O(1/n)$. Thus, $Var(\frac{Z_{n^2}}{n^2})=O(1/n^2)$ and hence $$ \frac{Z_{n^2}}{n^2} \rightarrow 2 \quad \mbox{with prob 1} $$

3) For indices $k$ such that $n^2\leq k <(n+1)^2$, unfortunately we cannot "quite" say that $\frac{Z_{n^2}}{(n+1)^2} \leq \frac{Z_k}{k} \leq \frac{Z_{(n+1)^2}}{n^2}$ because the indicators $1_{\{|X_i-X_j|\leq 1/n\}}$ now have dependence on $n$. So we have to go to step 4:

---

Here is a fix:

4) Let $\{a_n\}_{n=1}^{\infty}$ be a deterministic sequence of (possibly negative) integers that satisfies $a_n = O(\sqrt{n})$ and $n + a_n \in \{1, 2, 3, \ldots\}$ for all positive integers $n$. Define: $$R_n(\{a_n\}) := \sum_{i=1}^n \sum_{j \in \{1, …, n\}, j \neq i} 1_{\{|X_i-X_j|\leq 1/(n+a_n)\}}$$ Now we can equally say $E[\frac{R_n(\{a_n\})}{n}]\rightarrow 2$ and $Var(\frac{R_n(\{a_n\})}{n})=O(1/n)$, and so $R_{n^2}(\{a_n\})/n^2\rightarrow 2$ with prob 1. Furthermore for any $k$ such that $n^2\leq k <(n+1)^2$ we get $$ \frac{R_{n^2}(\{a_n\})}{(n+1)^2}\leq\frac{Z_k}{k} \leq \frac{R_{(n+1)^2}(\{b_n\})}{n^2}$$ for some sequences $\{a_n\}$ and $\{b_n\}$.

Answer 2

One can use also tools related to $U$-statistics.

1. First step: for the indices $i=j$, the indicator is always one hence it suffices to prove the $$\frac 1n\sum_{1\leqslant i<j\leqslant n}\mathbf{1}_{(-1/n,1n)}\left(X_i-X_j\right)\to 1 \mbox{ a.s.}.$$
2. Define $h_n(x,y):= \mathbf{1}_{(-1/n,1n)}\left(x-y\right)$ and $\mathcal F_i$ the $\sigma$-algebra generated by the random variables $X_1,\dots,X_i$. Then $$\mathbb E\left[h_n\left(X_i,X_j\right)\mid\mathcal F_{j-1}\right]=g_n\left(X_i\right), $$ where $g_n(x)=2/n$ for $1/n\leqslant x\leqslant 1-1/n$, $g_n(1)=g_n(0)=1/n$ and $g_n$ is piecewise affine.
3. We are thus reduces to show that $$ \frac 1n\sum_{1\leqslant i<j\leqslant n} \left(h_n\left(X_i,X_j\right)-\mathbb E\left[h_n\left(X_i,X_j\right)\mid\mathcal F_{j-1}\right]\right)\to 0 \mbox{ a.s.} $$ $$ \frac 1n\sum_{i=1}^{n-1}\left(n-i\right)g_n\left(X_i\right)\to 1 \mbox{ a.s.} $$
4. The first part can be treated by looking at the fourth order moments and the fact that for a martingale differences sequence $\left(D_i\right)_{i\geqslant 1}$, $$\left\lVert \sum_{i=1}^nD_i\right\rVert_4^2\leqslant 3\sum_{i=1}^n\left\lVert D_i\right\rVert_4^2. $$
5. For the other part, control $g_n(X_i)-2/n$.