# Variant of the Strong Law of Large Numbers

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.

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\}$$.

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
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 $$\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$$.