Steven R. Dunbar
Department of Mathematics
203 Avery Hall
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Orders of Growth

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________ ### Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________ ### Section Starter Question

What would it mean to say that the sequence ${n}^{3}+50{n}^{2}+100000$ grows at the same rate as ${n}^{3}$? How could you make that precise?

_______________________________________________________________________________________________ ### Key Concepts

1. ${a}_{n}=O\left({b}_{n}\right)$ if and only if ${limsup}_{n\to \infty }\left|\frac{{a}_{n}}{{b}_{n}}\right|<\infty$.
2. ${a}_{n}=\Omega \left({b}_{n}\right)$ if and only if ${liminf}_{n\to \infty }\left|\frac{{a}_{n}}{{b}_{n}}\right|>0$.
3. ${a}_{n}=o\left({b}_{n}\right)$ if and only if $\underset{n\to \infty }{lim}\left|\frac{{a}_{n}}{{b}_{n}}\right|=0$.
4. ${a}_{n}=\omega \left({b}_{n}\right)$ if and only if $\underset{n\to \infty }{lim}\left|\frac{{a}_{n}}{{b}_{n}}\right|=\infty$.
5. ${a}_{n}\sim {b}_{n}$ (as $n\to \infty$) if ${a}_{n}=\left(1+o\left(1\right)\right){b}_{n}$.

__________________________________________________________________________ ### Vocabulary

1. We say ${a}_{n}=O\left({b}_{n}\right)$ as $n\to \infty$ if there are constants $C>0$ and ${n}_{0}\in ℕ$ such that $|{a}_{n}|\le C|{b}_{n}|$ for all $n\ge {n}_{0}$.
2. We say ${a}_{n}=\Omega \left({b}_{n}\right)$ as $n\to \infty$ if ${b}_{n}=O\left({a}_{n}\right)$, that is there are constants $C>0$ and ${n}_{0}\in ℕ$ such that $|{a}_{n}|\ge C|{b}_{n}|$ for all $n\ge {n}_{0}$.
3. We say ${a}_{n}=o\left({b}_{n}\right)$ as $n\to \infty$ if for all $𝜖>0$ there is an ${n}_{0}\in ℕ$ such that $|{a}_{n}|\le 𝜖|{b}_{n}|$ for all $n\ge {n}_{0}$.
4. ${a}_{n}\sim {b}_{n}$ (as $n\to \infty$) if ${a}_{n}=\left(1+o\left(1\right)\right){b}_{n}$.

__________________________________________________________________________ ### Mathematical Ideas

#### Deﬁnitions

Let ${a}_{n}$, ${b}_{n}$ be sequences of real numbers indexed by $n\in ℕ$. Assume that ${a}_{n}$, ${b}_{n}$ are nonzero except for ﬁnitely many terms.

Deﬁnition. We say ${a}_{n}=O\left({b}_{n}\right)$ as $n\to \infty$ if there are constants $C>0$ and ${n}_{0}\in ℕ$ such that $|{a}_{n}|\le C|{b}_{n}|$ for all $n\ge {n}_{0}$.

The deﬁnition says that ${a}_{n}$ grows in magnitude slower than ${b}_{n}$, or that (a constant multiple of) ${b}_{n}$ is a upper bound on ${a}_{n}$.

Deﬁnition. We say ${a}_{n}=\Omega \left({b}_{n}\right)$ as $n\to \infty$ if ${b}_{n}=O\left({a}_{n}\right)$, that is there are constants $C>0$ and ${n}_{0}\in ℕ$ such that $|{a}_{n}|\ge C|{b}_{n}|$ for all $n\ge {n}_{0}$.

The deﬁnition says that ${a}_{n}$ grows in magnitude faster than ${b}_{n}$, or that (a constant multiple of) ${b}_{n}$ is a lower bound on ${a}_{n}$.

Deﬁnition. We say ${a}_{n}=\Theta \left({b}_{n}\right)$ as $n\to \infty$ if ${a}_{n}=O\left({b}_{n}\right)$ and ${a}_{n}=\Omega \left({b}_{n}\right)$, that is there are constants ${C}_{1}>0$, ${C}_{2}>0$ and ${n}_{0}\in ℕ$ such that ${C}_{1}|{b}_{n}|\le |{a}_{n}|\le {C}_{2}|{b}_{n}|$ for all $n\ge {n}_{0}$.

The deﬁnition says that ${a}_{n}$ grows in magnitude at about the same rate as ${b}_{n}$.

Lemma 1.

1. ${a}_{n}=O\left({b}_{n}\right)$ if and only if ${limsup}_{n\to \infty }\left|\frac{{a}_{n}}{{b}_{n}}\right|<\infty$.
2. ${a}_{n}=\Omega \left({b}_{n}\right)$ if and only if ${liminf}_{n\to \infty }\left|\frac{{a}_{n}}{{b}_{n}}\right|>0$.

Deﬁnition. We say ${a}_{n}=o\left({b}_{n}\right)$ as $n\to \infty$ if for all $𝜖>0$ there is an ${n}_{0}\in ℕ$ such that $|{a}_{n}|\le 𝜖|{b}_{n}|$ for all $n\ge {n}_{0}$.

The deﬁnition says that if ${b}_{n}\to 0$, then ${a}_{n}$ diminishes to $0$ faster than ${b}_{n}$, or that (a constant multiple of) ${b}_{n}$ is a upper bound on ${a}_{n}$.

Deﬁnition. We say ${a}_{n}=\omega \left({b}_{n}\right)$ as $n\to \infty$ if ${b}_{n}=o\left({a}_{n}\right)$, that is for every constants $K>0$ there is an ${n}_{0}\in ℕ$ such that $|{a}_{n}|\ge K|{b}_{n}|$ for all $n\ge {n}_{0}$.

Lemma 2.

1. ${a}_{n}=o\left({b}_{n}\right)$ if and only if $\underset{n\to \infty }{lim}\left|\frac{{a}_{n}}{{b}_{n}}\right|=0$.
2. ${a}_{n}=\omega \left({b}_{n}\right)$ if and only if $\underset{n\to \infty }{lim}\left|\frac{{a}_{n}}{{b}_{n}}\right|=\infty$.
3. ${a}_{n}=o\left({b}_{n}\right)$ implies ${a}_{n}=O\left({b}_{n}\right)$.
4. ${a}_{n}=\omega \left({b}_{n}\right)$ implies ${a}_{n}=\Omega \left({b}_{n}\right)$.

Remark. Read the equality symbol “$=$” in ${a}_{n}=O\left({b}_{n}\right)$ not as equality, but rather as membership. In other words, ${a}_{n}=O\left({b}_{n}\right)$ asserts that ${a}_{n}$ belongs to the class of $O\left({b}_{n}\right)$ sequences. This abuse of the equality notation can be confusing at times. Consequently, we should more properly write ${a}_{n}\in O\left({b}_{n}\right)$, but the equality sign is more commonly used.

Since equality means membership, asymptotic notations must always be read from left to right. For example, statements like ${f}_{n}=O\left(n\right)=O\left({n}^{2}\right)$, mean ${f}_{n}$ belongs to the $O\left(n\right)$ class of sequences which is in turn contained inside the $O\left({n}^{2}\right)$ class. Note that the order of the terms in the above asymptotic statement cannot be changed.

Remark. Furthermore, expressions like

${f}_{n}={\mathrm{e}}^{n+O\left(\sqrt{n}\right)}$

mean that there is a sequence ${g}_{n}=O\left(\sqrt{n}\right)$ such that ${f}_{n}={\mathrm{e}}^{n+{g}_{n}}$. Similar considerations apply to the $\Omega \left(\right)$, $\Theta \left(\right)$, $o\left(\right)$ and $\omega \left(\right)$ notations.

#### Little-Oh Notation and Asymptotics

Lemma 3. ${a}_{n}\sim {b}_{n}$ (as $n\to \infty$) if ${a}_{n}=\left(1+o\left(1\right)\right){b}_{n}$.

#### Big-Oh Algebra

The deﬁnitions above can be easily modiﬁed from sequences to functions.

Deﬁnition. We say $f\left(t\right)=O\left(g\left(t\right)\right)$ as $x\to \infty$ if there are constants $C>0$ and $A\in ℝ$ such that $|f\left(t\right)|\le C|g\left(t\right)|$ for all $t\ge A$.

The following propositions stated in terms of functions can be easily modiﬁed to equivalent propositions abut sequences.

Proposition 4 (Addition). If $f\left(t\right)=O\left({t}^{n}\right)$ and $g\left(t\right)=O\left({t}^{n}\right)$ then $f\left(t\right)+g\left(t\right)=O\left({t}^{n}\right)$

Proposition 5 (Powers). If $f\left(t\right)=O\left({t}^{n}\right)$, then ${t}^{m}f\left(t\right)=O\left({t}^{m+n}\right)$.

#### Common Expansions Using Big-Oh Expressions

Proposition 6 (One-Term Geometric Series Expansion). As $t\to 0$,

$\frac{1}{1+t}=1+O\left(t\right).$

Proposition 7 (One-Term Logarithm Expansion). As $t\to 0$,

$log\left(1+t\right)=t+O\left(1∕{t}^{2}\right).$

Proposition 8 (Two-Term Logarithm Expansion). As $t\to 0$,

$log\left(1+t\right)=t-{t}^{2}∕2+O\left(1∕{t}^{3}\right).$

Proposition 9 (Square-Root Expansion). As $t\to 0$,

$\sqrt{1+t}=1+O\left(t\right)$

Example. The Section on Moderate Deviations use the following expansions

$\begin{array}{llll}\hfill \frac{n}{k\left(n-k\right)}& =\frac{1}{np\left(1-p\right)}\cdot \left(1+{\text{O}}_{u}\left({c}_{n}{n}^{-1∕3}\right)\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill \sqrt{\frac{n}{k\left(n-k\right)}}& =\frac{1}{\sqrt{np\left(1-p\right)}}\cdot \left(1+{\text{O}}_{u}\left({c}_{n}{n}^{-1∕3}\right)\right).\phantom{\rule{2em}{0ex}}& \hfill \text{(1)}\end{array}$

The subscript u on $O$ is to indicate that the estimate is uniform over $k=0,1,\dots ,n$.

Proposition 10 (Exponential Expansion). As $t\to 0$,

$exp\left(1+t\right)=1+O\left(t\right)$

Example. In the section on Moderate Deviations, we need the following expansion

$\begin{array}{llll}\hfill ln\left[{\left(\frac{n}{k}p\right)}^{k}{\left(\frac{n}{n-k}\left(1-p\right)\right)}^{n-k}\right]& =-\frac{1}{2}{\left(k-np\right)}^{2}\left(\frac{1}{k}+\frac{1}{n-k}\right)+\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}k{\text{O}}_{u}\left({c}_{n}^{3}{n}^{-1}\right)+\left(n-k\right){\text{O}}_{u}\left({c}_{n}^{3}{n}^{-1}\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =-\frac{1}{2}{\left(k-np\right)}^{2}\frac{1}{np\left(1-p\right)}+{\text{O}}_{u}\left({c}_{n}^{3}\right).\phantom{\rule{2em}{0ex}}& \hfill \text{(2)}\end{array}$ Thus
${\left(\frac{np}{k}\right)}^{k}{\left(\frac{n\left(1-p\right)}{n-k}\right)}^{n-k}=exp\left(\frac{-{\left(k-np\right)}^{2}}{2np\left(1-p\right)}\right)\left(1+{\text{O}}_{u}\left({c}_{n}^{3}\right)\right).$

Proposition 11 ($p$-Series Tail Expansion).

$\sum _{n+1}^{\infty }\frac{1}{{k}^{2}}=O\left(\frac{1}{n}\right)$

Proof.

$\sum _{n+1}^{\infty }\frac{1}{{k}^{2}}\le \sum _{n+1}^{\infty }\frac{1}{k\left(k-1\right)}=\frac{1}{n}$

#### Sources

This deﬁnitions, some of the remarks and the problems are adapted from lecture notes by Xavier Perez Gimenez.

_______________________________________________________________________________________________ ### Problems to Work for Understanding

1. Explain what is wrong with the following fallacious proof of the claim ${n}^{2}=O\left(n\right)$ by induction: “The base case $1=O\left(1\right)$ is clearly true. Assuming that ${\left(n-1\right)}^{2}=O\left(n-1\right)$, we easily derive ${n}^{2}={\left(n-1\right)}^{2}+2n-1=O\left(n-1\right)+O\left(n\right)+O\left(n\right)=O\left(n\right)$.”
2. Let ${f}_{n}$, ${g}_{n}$ be positive sequences tending to $\infty$. Prove or disprove each of the following statements:
1. ${f}_{n}\sim {g}_{n}$ implies ${\mathrm{e}}^{{f}_{n}}\sim {\mathrm{e}}^{{g}_{n}}$.
2. ${f}_{n}\sim {g}_{n}$ implies $log{f}_{n}\sim log{g}_{n}$.

__________________________________________________________________________ __________________________________________________________________________ __________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.