Sudden jumps and almost surely slow convergence

Estimating a mean can be an arduous task. Observe, for instance, the “sudden jumps” in trajectories of the Monte Carlo estimate \overline X_n of \mathbb{E}X, where \mathbb{E}X^2 = \infty.

sudden jumpsProposition.
Let X_1, X_2, X_3, \dots be a sequence of i.i.d. and integrable random variables, and let \overline X_k = \frac{1}{k}\sum_{i=1}^k X_i. For all M > 0 we have that

P\left( \left| \overline X_{n} - \overline X_{n-1}\right| > Mn^{-1/2} \;\; \text{ i.o.} \right)

is 1 or 0 according to \text{Var}(X_n) =\infty or \text{Var}(X_n) < \infty.

Corollary.
If \text{Var}(X_k) = \infty, then \overline X_n converges towards \mathbb{E}X_k at a rate almost surely slower than \frac{1}{\sqrt{n}} :

\left|\overline X_n - \mathbb{E}X_n \right| \not = \mathcal{O}\left(n^{-1/2}\right) \quad \text{a.s.}

Proof of the proposition.
We can suppose that M=1/2, by the scale invariance of the problem. Note also that

|\overline X_{n} - \overline X_{n-1}| = |X_{n} - \overline X_{n-1}|/n \geq |X_{n}|/n - \left|\overline X_{n-1}\right|/n,

from which we find

P\left(\left| \overline X_n - \overline X_{n-1} \right| > \frac{1}{2\sqrt{n}}\; \text{ i.o.} \right) \geq P\left( | X_n | > \frac{\sqrt{n}}{2} + \left|\overline X_{n-1}\right|\; \text{i.o}\right)  \geq P\left(|X_n| > \sqrt{n}\; \text{ i.o}\right)

since |\overline X_{n-1}| = o(1) almost surely. From the Borel-Cantelli lemma and

\infty = \mathbb{E}X_k^2 = \int_0^\infty P\left(X_k^2 > u\right) du \le 1+\sum_{n=1}^{\infty} P\left(X_{n}^2 > n\right),

we obtain that P\left(\left| \overline X_n - \overline X_{n-1} \right| > \frac{1}{2\sqrt{n}}\; \text{ i.o.} \right) = 1 in this case.

When \text{Var}(X_n) < \infty, we let M=2 and note that |\overline X_{n} - \overline X_{n-1}| \le |X_{n}|/n + \left|\overline X_{n-1}\right|/n. Therefore

sudden_jumps_tex_2

Since the sum over n of the right hand side probabilities converges (again using the fact that \mathbb{E}X_n^2 = \int_{0}^\infty P(X_n^2 > u) du), the Borel-Cantelli lemma yields the result. \Box

Remark.
The result can be refined knowing that \mathbb{E} |X_k|^p = \infty for some small 1 < p: \mathbb{E} X_k^{1/(1-\varepsilon)} = \infty implies P\left(|\overline X_{n} - \overline X_{n-1}| > n^{-\varepsilon}\; \text{i.o.}\right) =1. The almost sure lower bound on the rate of convergence can be correspondingly adjusted.

Many thanks to Xi’an who wondered about the occurence of these jumps.

One thought on “Sudden jumps and almost surely slow convergence

  1. Pingback: Fair unfavorable games – Math. Stat. Notes

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s