Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
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

Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

What would it mean to say that the sequence n3 + 50n2 + 100000 grows at the same rate as n3? How could you make that precise?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. an = O(bn) if and only if limsup nan bn < .
  2. an = Ω(bn) if and only if liminf nan bn > 0.
  3. an = o(bn) if and only if lim nan bn = 0.
  4. an = ω(bn) if and only if lim nan bn = .
  5. an bn (as n ) if an = (1 + o(1))bn.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. We say an = O(bn) as n if there are constants C > 0 and n0 such that |an| C|bn| for all n n0.
  2. We say an = Ω(bn) as n if bn = O(an), that is there are constants C > 0 and n0 such that |an| C|bn| for all n n0.
  3. We say an = o(bn) as n if for all 𝜖 > 0 there is an n0 such that |an| 𝜖|bn| for all n n0.
  4. an bn (as n ) if an = (1 + o(1))bn.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Definitions

Let an, bn be sequences of real numbers indexed by n . Assume that an, bn are nonzero except for finitely many terms.

Definition. We say an = O(bn) as n if there are constants C > 0 and n0 such that |an| C|bn| for all n n0.

The definition says that an grows in magnitude slower than bn, or that (a constant multiple of) bn is a upper bound on an.

Definition. We say an = Ω(bn) as n if bn = O(an), that is there are constants C > 0 and n0 such that |an| C|bn| for all n n0.

The definition says that an grows in magnitude faster than bn, or that (a constant multiple of) bn is a lower bound on an.

Definition. We say an = Θ(bn) as n if an = O(bn) and an = Ω(bn), that is there are constants C1 > 0, C2 > 0 and n0 such that C1|bn||an| C2|bn| for all n n0.

The definition says that an grows in magnitude at about the same rate as bn.

Lemma 1.

  1. an = O(bn) if and only if limsup nan bn < .
  2. an = Ω(bn) if and only if liminf nan bn > 0.

Definition. We say an = o(bn) as n if for all 𝜖 > 0 there is an n0 such that |an| 𝜖|bn| for all n n0.

The definition says that if bn 0, then an diminishes to 0 faster than bn, or that (a constant multiple of) bn is a upper bound on an.

Definition. We say an = ω(bn) as n if bn = o(an), that is for every constants K > 0 there is an n0 such that |an| K|bn| for all n n0.

Lemma 2.

  1. an = o(bn) if and only if lim nan bn = 0.
  2. an = ω(bn) if and only if lim nan bn = .
  3. an = o(bn) implies an = O(bn).
  4. an = ω(bn) implies an = Ω(bn).

Remark. Read the equality symbol “=” in an = O(bn) not as equality, but rather as membership. In other words, an = O(bn) asserts that an belongs to the class of O(bn) sequences. This abuse of the equality notation can be confusing at times. Consequently, we should more properly write an O(bn), 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 fn = O(n) = O(n2), mean fn belongs to the O(n) class of sequences which is in turn contained inside the O(n2) class. Note that the order of the terms in the above asymptotic statement cannot be changed.

Remark. Furthermore, expressions like

fn = en+O(n)

mean that there is a sequence gn = O(n) such that fn = en+gn. Similar considerations apply to the Ω(), Θ(), o() and ω() notations.

Little-Oh Notation and Asymptotics

Lemma 3. an bn (as n ) if an = (1 + o(1))bn.

Big-Oh Algebra

The definitions above can be easily modified from sequences to functions.

Definition. We say f(t) = O(g(t)) as x if there are constants C > 0 and A such that |f(t)| C|g(t)| for all t A.

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

Proposition 4 (Addition). If f(t) = O(tn) and g(t) = O(tn) then f(t) + g(t) = O(tn)

Proposition 5 (Powers). If f(t) = O(tn), then tmf(t) = O(tm+n).

Common Expansions Using Big-Oh Expressions

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

1 1 + t = 1 + O(t).

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

log(1 + t) = t + O(1t2).

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

log(1 + t) = t t22 + O(1t3).

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

1 + t = 1 + O(t)

Example. The Section on Moderate Deviations use the following expansions

n k(n k) = 1 np(1 p) 1 + Ou(cnn13) n k(n k) = 1 np(1 p) 1 + Ou(cnn13) . (1)

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

Proposition 10 (Exponential Expansion). As t 0,

exp (1 + t) = 1 + O(t)

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

ln n kpk n n k(1 p) nk = 1 2(k np)2 1 k + 1 n k + kOu(cn3n1) + (n k)O u(cn3n1) = 1 2(k np)2 1 np(1 p) + Ou(cn3). (2) Thus
np k k n(1 p) n k nk = exp (k np)2 2np(1 p) 1 + Ou(cn3) .

Proposition 11 (p-Series Tail Expansion).

n+1 1 k2 = O 1 n

Proof.

n+1 1 k2 n+1 1 k(k 1) = 1 n

Sources

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

_______________________________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Explain what is wrong with the following fallacious proof of the claim n2 = O(n) by induction: “The base case 1 = O(1) is clearly true. Assuming that (n 1)2 = O(n 1), we easily derive n2 = (n 1)2 + 2n 1 = O(n 1) + O(n) + O(n) = O(n).”
  2. Let fn, gn be positive sequences tending to . Prove or disprove each of the following statements:
    1. fn gn implies efn egn.
    2. fn gn implies log fn log gn.

__________________________________________________________________________

Books

Reading Suggestion:

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

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 effort 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 reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on July 26, 2019