# Show that $\frac{1}{n(n-1)} \sum_{i\neq j} \sin\left(X_i X_j\right)$ converges almost surely to a constant

Let $$X_i$$ be iid random variables. How does one show that

$$\frac{1}{n(n-1)}\sum_{i\neq j}^n \sin\left(X_i X_j\right)$$ converges almost surely to a constant?

• Is this a homework question or something from a textbook? Could you add information about the nature of the question such that the answers can be adapted for this. Commented Oct 22, 2023 at 9:49
• If it is a homework, then you should add self-study tag and maybe include your attempts or ideas in the post so that answers can be built upon your current progress.
– Derf
Commented Oct 22, 2023 at 9:51
• Do you need to proof convergence in probability to a constant or convergence almost sure to a constant? Commented Oct 22, 2023 at 10:18
• This is a problem I found on a statistics entrance exam for the Indian Statistical Institute (if I remember correctly); I’ve not yet found it any textbook although if you know of (similar) problems in a textbook I’d be happy to hear a reference. My main issue is that I don’t know of an LLN that finds purchase with this kind of dependence structure. Commented Oct 22, 2023 at 11:44
• What you have is a U-statistic $\frac1{\binom{n}{2}}\sum_{1\le i<j\le n}\sin(X_iX_j)$. Reading up on SLLN/consistency for U-statistics could help. Commented Oct 25, 2023 at 20:51

I think it is worth elaborating @StubbornAtom's sharp comment as applying the U-statistics theory is perhaps the most direct way to prove this proposition. To this end, identify the random variable of interest as the U-statistic \begin{align} U_n := U(X_1, \ldots, X_n) := \frac{1}{\binom{n}{2}}\sum_{1 \leq i < j \leq n}h(X_i, X_j), \end{align} where $$h(x, y) = \sin(xy)$$ is the "kernel" function of this U-statistic. Now the result immediately follows by the following theorem (cf. Approximation Theorems of Mathematical Statistics by R.Serfling, Theorem 5.4.A) because $$|h| \leq 1$$:

If $$E[|h|] < \infty$$, then $$U_n$$ converges to $$\theta = E[h(X_1, X_2)]$$ almost surely.

For more details (e.g., which references provided the proof to this theorem), refer to the same reference, Section 5.4. At high-level, the key of the proof is the Hoeffding representation of the quantity $$U_n - \theta$$.

• Hmm this does seem to be a martingale approach in disguise... this is probably the method the examiners expected, although they probably expected students to use the reverse martingale convergence theorem directly rather than the theorem on U-statistics (which isn't part of the standard undergraduate curriculum). Commented Oct 26, 2023 at 7:15

### In the case of the weak LLN

We can prove that the variance of the sum decreases for increasing $$n$$ (then applying Chebyshev's inequality).

For simplicity of writing the equations, I will define $$Z_{\mathscr{ij}} = \sin(X_\mathscr{i}X_\mathscr{j})$$ and $$S_n = \frac{1}{n(n-1)} \sum_{\mathscr{i}\neq \mathscr{j}} Z_{\mathscr{ij}}$$

The variance of the sum can be computed as

$$\operatorname{Var}(S_n) = \left(\frac{1}{n(n-1)} \right)^2 \sum_{\mathscr{i}\neq \mathscr{j}} \sum_{\mathscr{k}\neq\mathscr{l}} \operatorname{Cov}(Z_{\mathscr{ij}} Z_{\mathscr{kl}}).$$

We have three situations of the covariance terms

$$\operatorname{Cov}(Z_{\mathscr{ij}} Z_{\mathscr{kl}}) = \begin{cases} V & \quad \text{if \mathscr{ij} = \mathscr{kl} or if \mathscr{ij} = \mathscr{lk}} \\ C & \quad \text{if (\mathscr{i} = \mathscr{k} and \mathscr{j}\neq \mathscr{l}) or (\mathscr{i} = \mathscr{l} and \mathscr{j} \neq \mathscr{k})} \\ 0 & \quad \text{if \mathscr{i} \neq \mathscr{j} \neq \mathscr{k} \neq \mathscr{l}} \\ \end{cases}$$

For each $$\mathscr{ij}$$ pair, there are 2 cases of $$V$$ and $$2 (n-2)$$ cases of $$C.$$

Then the variance can be computed as

\begin{align} \operatorname{Var}(S_n) &= \left(\frac{1}{n(n-1)} \right)^2 \sum_{\mathscr{i}\neq \mathscr{j}} (2V+ 2(n-2)C) \\[6pt] &= \left(\frac{1}{n(n-1)} \right)^2 (n(n-1)) (2V+ 2(n-2) C) \\[6pt] &= 2 \frac{V+(n-2)C}{n(n-1)} \end{align} and this approaches zero for increasing $$n$$.

• A side note, Sextus, try to not define the new commands at the beginning of the post - it inadvertently creates an unusual space at the beginning of the post. Commented Oct 23, 2023 at 2:04
• @User1865345 I didn't do that ;-) Commented Oct 23, 2023 at 6:24
• I see, Sextus. It was Michael Hardy. But the comment stands! Commented Oct 23, 2023 at 6:29
• There is a problem associated with defining commands here: the definitions apply to all posts (and perhaps comments -- I haven't checked) on that page, no matter whose. Consequently, for posts on this site, I have adopted a cut-and-paste practice rather than the more elegant approach of command definition.
– whuber
Commented Oct 23, 2023 at 12:01
• @innisfree Yes, since all $Z_{\mathscr{ij}}$ have second moments $\leq 1$. Commented Oct 26, 2023 at 1:56

Acting hastily, I first thought that the boundeness of $$Y_{ij}\mathrel{:=\sin(X_iX_j)}$$ and $$\mathop{\mathbb E}\left[Y_{ij}^2\right] \leq \mathbb E[1] = 1$$ would be enough to solve the problem with a version of the strong law of large numbers for pairwise uncorrelated random variables.
However, clearly, in general we don't have pairwise uncorrelatedness of $$Y_{ij}$$ and $$Y_{ik}$$ for $$j \neq k$$ if $$X_i \overset{\mathrm{i.i.d.}}{\sim} \mathbb P$$ for an arbitrary distribution $$\mathbb P$$ on $$\mathcal B(\mathbb R).$$

We can exploit the following result (e.g., Brown, 1992, Proposition 1) to show almost sure convergence:

Suppose that $$\left(X_k\right)_{k \in \mathbb N_{\geq 1}}$$ is a sequence of complex-valued random variables of bounded modulus and that $$\sum_{n=1}^\infty\frac{1}{n}\mathop{\mathbb E}\left[\left|\frac{1}{n} \sum_{k=1}^nX_k\right|^2\right] < \infty.$$ Then $$\frac{1}{n} \sum_{k=1}^nX_k \overset{n \to \infty}{\longrightarrow} 0$$ almost surely.

This result is a slight generalization of Theorem 1 in Lyons (1988), in which $$|X_k|\leq 1$$ almost surely $$\forall \,k \in \mathbb N_{\geq 1}$$ is assumed, and can be proved analogously.

Let $$\mu \mathrel{:=} \mathbb E[Y_{ij}].$$
Applying the above result to the sequence $$\left(Y_{ij}-\mu\right)_{i \neq j}$$ with $$\mathop{\mathbb E}\left[\left|\frac{1}{n\left(n-1\right)} \sum_{i \neq j}^n \left(Y_{ij}-\mu\right)\right|^2\right] = \mathop{\mathbb V}\left[\frac{1}{n\left(n-1\right)} \sum_{i \neq j}^n Y_{ij}\right]$$ and $$\mathop{\mathbb V}\left[\frac{1}{n\left(n-1\right)} \sum_{i \neq j}^n Y_{ij}\right] = 2 \frac{V+(n-2)C}{n(n-1)} \leq c/n$$ (for all $$n \in \mathbb N_{\geq 2}$$ and a constant $$c \in \mathbb R_{>0}$$) from Sextus Empiricus' answer yields $$\frac{1}{n\left(n-1\right)} \sum_{i \neq j}^n \left(Y_{ij}-\mu\right)\underset{n \to \infty}{\overset{\mathrm{a.s.}}{\longrightarrow}} 0,$$ and hence $$\frac{1}{n\left(n-1\right)} \sum_{i \neq j}^n Y_{ij} \underset{n \to \infty}{\overset{\mathrm{a.s.}}{\longrightarrow}} \mu.$$

References

• The terms are not independent. I don’t know if there’s a particular law of large numbers which works with a dependence structure of this form — perhaps a triangular array LLN? Commented Oct 22, 2023 at 11:39
• I tried this trick relating to the Borel–Cantelli lemma, but I had a converging series instead. Are you sure it isn't $$\sum_{n=1}^\infty\mathop{\mathbb E}\left[\left|\frac{1}{n} \sum_{k=1}^nX_k\right|^2\right] < \infty.$$ instead of $$\sum_{n=1}^\infty\frac{1}{n}\mathop{\mathbb E}\left[\left|\frac{1}{n} \sum_{k=1}^nX_k\right|^2\right] < \infty.$$ Commented Oct 23, 2023 at 12:40
• Possibly it helps that the summands are bounded. Commented Oct 23, 2023 at 12:58
• @SextusEmpiricus from what I know the result should be how I've stated it, I didn't check the proof though. Without the factor $1/n$ the result wouldn't apply because the series $\sum_{n=1}^\infty c/n$ diverges. Commented Oct 23, 2023 at 15:02
• @SextusEmpiricus I've added a reference that proves (a slight variation on) the result, in case you're interested. Commented Oct 25, 2023 at 18:58