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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.