2
$\begingroup$

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})$?

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

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Excellent thanks! $\endgroup$ Mar 10, 2021 at 9:41

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.