User:IssaRice/Little o notation

From Machinelearning
Jump to: navigation, search

Definition

Definition (little o near a point). Let f : \mathbf R \to \mathbf R and g : \mathbf R \to \mathbf R be two functions, and let a \in \mathbf R. We say that f is little o of g near a iff for every \epsilon > 0 there exists \delta > 0 such that |x - a| < \delta implies |f(x)| < \epsilon|g(x)|. Some equivalent ways to say the same thing are:

Notation Comments
f is little o of g near a This is a point-free notation.
f(x) \in o(g(x)) as x \to a This is in point notation, as the variable x appears in the notation. This allows us to define functions anonymously. For example, we can say x^2 \in o(x) as x \to 0; we didn't even name the functions. As the appearance of the symbol "\in" suggests, in this notation we think of o(g(x)) as a set, namely the set of all functions that are o(g(x)) as x \to a.
f(x) = o(g(x)) as x \to a This is in point notation. As the equality symbol suggests, in this notation we think of f as a concrete manifestation of a function that is o(g(x)) near a. This allows us to algebraically manipulate the expression o(g(x)) along with all our other expressions.
f \in o(g) near a This is a point-free notation. As the appearance of the symbol "\in" suggests, in this notation we think of o(g) as a set, namely the set of all functions that are o(g) near a. In other words, o(g) = \{f : \forall \epsilon > 0 \ \exists \delta > 0\ \forall x\ (|x-a| < \delta \implies |f(x)| < \epsilon|g(x)|)\}
f = o(g) near a This is a point-free notation.

Definition (little o at infinity). Let f : \mathbf R \to \mathbf R and g : \mathbf R \to \mathbf R be two functions. We say that f is little o of g at positive infinity (or equivalently f(x) is little of g(x) as x \to \infty) iff for every real \epsilon > 0 there exists a real number M such that for all x, if x > M then |f(x)| < \epsilon|g(x)|. We say that f is little o of g at negative infinity (or equivalently f(x) is little of g(x) as x \to -\infty) iff for every real \epsilon > 0 there exists a real number M such that for all x, if x < M then |f(x)| < \epsilon|g(x)|.

Exercise. Show that in the definition of little o at positive infinity, "there exists a real number M" can be replaced by "there exists a real number M > 0". Show that in the definition of little o at negative infinity, "there exists a real number M" can be replaced by "there exists a real number M < 0".

Exercise. Can we write just f \in o(g) or f = o(g) or f(x) \in o(g(x)) or f(x) = o(g(x))?

Expand to see solution:

In general we can't because for this notation to make sense, we also need to know where the argument x is going. In algorithms, we have x \to \infty, but in analysis (e.g. in some definitions of differentiability) we have x \to 0.

Exercise. If we are being a little pedantic, what is wrong with saying "f \in o(g) as x \to a"?

Expand to see solution:

We are saying x \to a, but we haven't clarified what x is. Instead, we are relying on the reader to assume that x is an argument to f and g.

Exercise. Interpret the meaning of x^2 \in o(x).

Expand to see solution:

It depends on where x is going. We want |x^2| < \epsilon |x| whenever |x-a|<\delta, so this is only true when a = 0.

Properties

Proposition. Let f : \mathbf R \to \mathbf R and g : \mathbf R \to \mathbf R be two functions, and suppose g(x) \ne 0 for all x \in \mathbf R. Then f is little o of g near a if and only if \lim_{x\to a} \frac{f(x)}{g(x)} = 0.

Proposition. transitivity

Proposition. we can replace the < in the definition with \leq, right?

Exercise. Let c, x_0 \in \mathbf R be constants. Interpret the statement "o(c(x-x_0) + o(x-x_0)) \in o(x-x_0) as x \to x_0".

Expand to see solution:

TODO: be careful with universal vs existential quantifiers.

The statement is saying f(x) \in o(x-x_0) where f is some function such that \lim_{x\to x_0} \frac{f(x)}{c(x-x_0) + o(x-x_0)} = 0.

Because of the nested little o, we need to expand again and introduce g, where g(x) \in o(x-x_0) so \lim_{x\to x_0} \frac{g(x)}{x-x_0} = 0.

Now we verify:

\lim_{x\to x_0} \frac{f(x)}{x-x_0} = \lim \frac{f(x)}{c(x-x_0) + g(x)} \lim \frac{c(x-x_0) + g(x)}{x-x_0} = 0 \cdot (c + 0) = 0

Could g have been arbitrary? In other words, could we have said o(c(x-x_0) + o(h(x))) \in o(x-x_0) for arbitrary h(x)? To compute the limit \lim_{x\to x_0} \frac{f(x)}{x-x_0} we actually used the limit laws, which require that the right hand limit exist. This means that we needed \lim_{x\to x_0} g(x)/h(x) to exist.

References

[1]

[2]