# Big O and little o notation explained?

Throughout many of my statistics classes, I've had my professors attempt to explain big "O" (oh) and little "o" notation (especially as it involves convergence, the central limit theorem, and the delta method). However, none of them have done a very good job at explaining this and they tend to wave their hand at it as though it's magic. Can someone please help me understand this notation? For example, in a proof (using moment generating functions) of the the convergence in distribution of independent Bernoulli($p$) variables, we are shown a step:

$[p(1+\sum_{i=0}^{\infty}{{(t/n)^i}\over{i!}}) +(1-p)]^n=[1+pt/n+o(1/n)]^n$

If you look at the RHS, you'll see this $o(1/n)$ notation. Can anyone help me understand what this means exactly?

## Definition

The sequence $a_n = o(x_n)$ if $a_n/x_n \to 0$. We would read it as $a_n$ is of smaller order than $1/n$, or $a_n$ is little-oh of $1/n$. In your case, if some term $a_n$ is $o(1/n)$ that means that $n a_n \to 0$. A few examples of sequences that are $o(1/n)$ are $c/n^p$ where $p > 1$, $1/(n\log(n))$, and $1/n^2 + 1/n^3$. Even though writing $o(1/n)$ conveys less information than writing the specific sequence, it takes up less space than writing the whole thing out, and tells us that, in this case, the term goes to $0$ faster than $1/n$ (it could also tell us about the speed at which sequences approach infinity).

## Some Other Things

On the other hand, writing $a_n = O(1/n)$ means that $|na_n| < M < \infty$ for $n$ bigger than some $n_0$. Typically (but not always) this means that $a_n = c/n$. This means that $a_n$ is of the same or smaller order than $1/n$.

Another thing that might pop up is when people write $o_p(x_n)$ or $O_p(x_n)$. Replace all the definitions above with convergence in probability. It doesn't look like you're using this, however, because you aren't talking about convergence of random variables...just their mgfs.

Also, are you sure that those are what your mgfs look like multiplied together? Specifically the part $1 + \sum_{i=0}^{\infty} \frac{(t/n)^i}{i!}$. I suspect you mean $\sum_{i=0}^{\infty} \frac{(t/n)^i}{i!} = e^{t/n}$ because \begin{align*} M_{\bar{X}}(t) &= E[e^{t/n \sum_iX_i}] \\ &= \prod_{i} M_{X_i}(t/n) \\ &= [(1-p)+pe^{t/n}]^n \\ &= \left[(1-p) + p\left\{ \sum_{i=0}^{\infty} \frac{(t/n)^i}{i!}\right\} \right]^n \\ &= \left[ 1 - p + p\left\{ 1 + t/n + \sum_{i=2}^{\infty}\frac{ (t/n)^{i} }{i!} \right\}\right]^n \\ &= \left[1 + pt/n + \sum_{i=2}^{\infty} \frac{pt^i}{i!n^i} \right]^n \end{align*}

Your professor means $\sum_{i=2}^{\infty} \frac{pt^i}{i!n^i} = o(1/n)$ because $$\sum_{i=2}^{\infty} \frac{pt^i}{i!n^{i-1}} \to 0$$ as $n \to \infty$ as $i-2 \ge 1$.

• Although the intuitions you share are sort of on target, much of this answer is wrong. Please take some care with the subtleties. For the little-o notation, note that the limit in your definition might not exist. (Consider $x_n=1+(-1)^n$, which causes you to divide by zero infinitely often.) For the big-O notation, note that when $a_n = O(1/n)$ it is not necessarily the case that $na_n$ approaches a limit or even, if it does, that the limit be positive. A simple counterexample is the true statement that $a_n=n^{-2}$ is $O(1/n)$. Another counterexample is that $a_n=-1/n$ is $O(1/n)$.
– whuber
May 15, 2017 at 13:40
• Thank you for working to fix that up. Note that your little-o definition still needs to be corrected. I would also suggest not oversimplifying, because that might cause more confusion: when $a_n$ is $o(1/n)$ it is rarely the case that $a_n=c/n^p$ for any $p \gt 1$. As examples, consider that $1/(n\log(n))$ and $1/n^2 + 1/n^3$ are both $o(n)$ but neither is of the form $c/n^p$. The little-o and big-O notations are only referring to asymptotic behavior, not to specific formulas for all $a_n$.
– whuber
May 15, 2017 at 17:35
• @whuber the little-o definition is fine, but I agree that the examples were lacking. I added yours in there. May 15, 2017 at 19:30
• In my first comment I explained why your little-o definition must be incorrect. For instance, with $a_n=(1+(-1)^n)/n$ and $x_n=1+(-1)^n$ we do have $a_n$ is $o(x_n)$, but $a_n/x_n$ does not have a limit (because the ratio is undefined for infinitely many $n$). You really do need to use standard definitions rather than hoping intuitive shortcuts will work.
– whuber
May 15, 2017 at 20:11
• (+1) Thank you for the reference. E.L. Lehmann is well respected, so the sloppiness in that definition is a surprise. The Wikipedia article is much more general, rigorous, and correct. I would speculate that Lehmann doesn't feel a need for full generality because he will only be using simple and eventually monotonic nonzero sequences like $n$, $1/n$, $1/n^p$, etc., for his $x_n$, for which these problems don't arise. In the preface he makes it clear that this is an "elementary" volume and is not proof-oriented.
– whuber
May 15, 2017 at 20:34