# Why does the order of expectation plus the square root of order of variance equal the big $O_p$ rate of convergence in probability?

Midway through p. 154 of this paper, the authors compute the expectation and variance of a variable $$\sum_{i,j=1}^nG_{i,j}^l$$ and get \begin{align} E\bigg[\sum_{i,j=1}^nG_{i,j}^l\bigg] & = O(n^2h^{l+1}), \\ \text{Var}\bigg[\sum_{i,j=1}^nG_{i,j}^l\bigg] & = O(n^3 h^{2(l+1)} + n^2h). \end{align}

Using this they say that $$\sum_{i,j=1}^nG_{i,j}^l = O_p(n^2h^{l+1} + \sqrt{n^3 h^{2(l+1)}} + \sqrt{n^2h}).$$

So it seems that the big $$O_p$$ rate of convergence in probability is given by the order of convergence of expectation and the square root of the order of convergence of the variance.

Why is this? Is this due to some kind of bias-variance decomposition? How can it be proved? For example, if we have a random variable $$X$$ such that $$E[X] = O(n)$$ and $$\text{Var}[X] = O(n)$$ how do we prove that $$X = O_p(n + \sqrt{n})$$?

• See Chebyshev's Inequality.
– whuber
Mar 8, 2021 at 18:22
• Note that $X_n = O_p(n + \sqrt{(n)})$ if and only if $X_n = O_p(n)$. Mar 8, 2021 at 18:29

Suppose $$f, g$$ are positive functions and $$E(X_n) = O(f(n))$$ and $$\text{Var}(X_n) = O(g(n))$$. Then there exist $$C>0, N>0$$ such that for all $$n > N$$, $$E(X_n) < Cf(n)$$ and $$\text{Var}(X_n) < C^2g(n)$$.
Given $$\epsilon > 0$$, let $$k > \max(\frac 1 {\sqrt{\epsilon}}, 1)$$.
For $$n > N$$,
\begin{align} P(|\frac{X_n}{f(n) + \sqrt{g(n)}}| < kC) &= P(|X_n| > (f(n) + \sqrt{g(n)})kC) \\ &\le P(|X_n - E(X_n)| > k\sqrt{g(n)}C) \\ &\le P(|X_n - E(X_n)| > k\sqrt{\text{Var}(X_n)}) \\ &\le \frac 1 {k^2} \text{ (by Chebyshev's inequality)}\\ &\lt \epsilon \end{align}
This shows that $$X_n = O_p(f(n) + \sqrt{g(n)})$$.