# Prove $\lim_{n\rightarrow \infty}\left(\sup_{\theta\in \Theta}\left| \frac{1}{n}\sum_{i=1}^n f(X_i,\theta)-E(f(X,\theta)) \right|\right)=0$

$$\Theta\in\mathbb{R}^d$$ is a compact set, $$f(x,\theta):\mathbb{R}^p\times Y\in \mathbb{R}^+$$ are continous functions in $$\theta$$ for every $$x$$. Let $$X,X_1,\dots,X_n,\dots$$ be i.i.d random vectors.

Then $$\displaystyle E\left( \sup_{\theta\in \Theta}f(X,\theta)\right)<\infty\implies \lim_{n\rightarrow \infty}\left(\sup_{\theta\in \Theta}\left| \frac{1}{n}\sum_{i=1}^n f(X_i,\theta)-E(f(X,\theta)) \right|\right)=0$$

I don't see an immediate way of doing this rather than working with the definition of limit. The idea is to show that there is $$N$$ such that $$\sup_{\theta\in \Theta}\left| \frac{1}{n}\sum_{i=1}^n f(X_i,\theta)-E(f(X,\theta)) \right|<\epsilon$$ for a given $$\epsilon$$.

I think the compactness of $$\Theta$$ might be used to argue that there is a $$\theta_0$$ for which $$\sup_{\theta\in \Theta}f(X,\theta) = f(X,\theta_0)$$. Then I would apply the same to the second equation $$\left| \frac{1}{n}\sum_{i=1}^n f(X_i,\theta_0)-E(f(X,\theta_0)) \right|<\epsilon$$.

But I find the $$\frac{1}{n}$$ in $$\displaystyle\frac{1}{n}\sum_{i=1}^n f(X_i,\theta_0)$$ problematic because it will make the term smaller meanwhile $$E(f(X,\theta_0))$$ doesn't seem to decrease.

• The $1/n$ does decrease the term, but the $\sum$ (mostly) increases the term, and the two do indeed wash out in the long run. Example: If the $X_i$ terms are $\{0, 1\}$ coin flips, then you add $n$ of them together and divide by $n$. You'd expect about half of the coin flips to be $1$, so the sum would be roughly $n/2$ and thus $\frac 1 n \sum X_i$ is roughly $1/2$. (I provide this only as a heuristic that the problem is reasonable.) – Aaron Montgomery Oct 12 '17 at 18:47
• @kimchilover I think it should be part of the hypothesis. If it is true, then the last limit is true. – Cure Oct 16 '17 at 14:59
• I did not notice that $f$ takes values in $\mathbb R^+$ only. – kimchi lover Oct 16 '17 at 17:55
• @AaronMontgomery I don't see it. $E(f(x,\phi))=\int_{-\infty}^{+\infty}f(x,\theta)$ but I think for the purposes of this exercises we can consider $E(f(x,\phi)) = \sum_{i=1}^n x_i f(x_i,\theta)$. The problem is I do not know the $x_i$ values, and for all I know the all might be $1$ in which case the limit wouldn't be true. – Cure Oct 16 '17 at 18:50
• Unless I'm misinterpreting something, having all the $x_i$ values be $1$ would just mean that your random variables were all $1$ with probability 1. In that case, $\frac 1 n \sum f(X_i, \theta) = \frac 1 n \sum f(1, \theta) = \frac 1 n n \cdot f(1, \theta) = f(1, \theta)$, and $E[f(X, \theta)] = E[f(1, \theta)] = f(1, \theta)$. – Aaron Montgomery Oct 16 '17 at 20:19

This is an immediate consequence of the SLLN for separable Banach spaces (see here for the first publication and here for a dumbed down statement), in particular, for $S=C(\Theta),$ the space of continuous real-valued functions on $\Theta$, with the topology induced by the sup norm $\|h\| = \sup_{\theta\in\Theta}|h(\theta)|$. Let $Y\in S$ be the function $\theta\mapsto f(X,\theta)$; you need to check that this defines $Y$ as a random element of $C(\Theta)$, and similarly for $Y_i:\theta\mapsto f(X_i,\theta)$. Then you need to check that $E\|Y\| = E\sup_{\theta\in\Theta}|f(X,\theta)| \lt \infty$. Let $m=EY:\theta\mapsto E(X,\theta)$. Then the desired result follows directly from the SLLN: $\overline Y_n \to m$ almost surely, which is to say, $\|\overline Y_n-m\|\to0$ almost surely.
The $S=C(\Theta)$ SLLN is easy to prove, in principle. Here is a sketch of one line of argument. Let $Y$ be a random vector in $S$, with distribution $\mu$, for which $\int _S\|Y\|\mu(dY)<\infty$. Let $m=EY$. Define another measure on $S$ by $\nu(A)=\int_A\|Y\|\mu(dY).$ Note that $\nu$ is finite, and hence for any given real $\epsilon>0$ there exists a compact $K\subset S$ such that $\nu(A^c)<\epsilon$. Cover $K$ with open $\epsilon$-balls, extract a finite sub-cover, and let $T(\epsilon)$ denote the centers of the balls in the finite sub-cover. Now define the random vector $T_i$ to be a closest element of $T(\epsilon)$ if $Y_i\in K$, and $0$ otherwise. Note that $E\|Y_i - T_i\| <\epsilon$, observe that the $T_i$ obey the finite dimensional SLLN and so $\overline T_n\to ET_1$ a.s. But $\|ET_1 -m \|<\epsilon$, so we have $\|\overline Y_n - m\|<2\epsilon$ for all $n$ sufficiently large. Since $\epsilon>0$ was arbitrary we are done. In particular, let $G(\epsilon)$ be the event that $\|\overline Y_n - m\|<2\epsilon$ holds for all $n$ sufficiently large. We have just seen that $P(G(\epsilon))=1$ for $\epsilon>0$, so $G = \bigcap_{k>0}G(1/k)$ also has probability $1$. But conditional on $G$, we have $\overline Y_n \to m.$
• (1) What is $C(\Theta)$? (2) Isn't $E||Y|| < \infty$ already considered in the problem? I don't see exactly how SLLN is appplied, could you be a little more explicit in the last part ("then the desired result follows directly..."). Thank you. – Cure Oct 16 '17 at 23:18
• You are right: checking (2) is a triviality: if $f$ is nonnegative, and if $\sup f$ is nice, then of course $\sup|f|$ is also nice, because they are the same thing. – kimchi lover Oct 16 '17 at 23:51