Probability

The Analysis of Data, volume 1

Metric Spaces: Limits

B.2. Limits

Definition B.2.1. A sequence $x^{(n)}$, $n\in\mathbb{N}$ in a metric space $(\mathcal{X},d)$ converges to a limit $x$, denoted by $x^{(n)}\to x$ or $\lim_{n\to\infty} x^{(n)}= x$, if \[ \forall \epsilon>0, \quad \exists N\in\mathbb{N}, \quad n>N\quad \Rightarrow \quad d( x^{(n)}, x) < \epsilon.\] In other words, for all $\epsilon>0$, there exists a $N\in\mathbb{N}$ such that whenever $n>N$, we have $d(x^{(n)}, x) < \epsilon$. If a sequence does not converges to a limit, we say that the sequence diverges.

It is possible that a sequence $x^{(n)}$ converges to a limit $x$, but the limit will never be realized: ${x}^{(n)} \neq x$ for all $n\in\mathbb{N}$. However, as $n$ increases the tail subsequences \[A_n=\{x^{(k)}:k\geq n\}, \quad n\in\mathbb{N}\] are contained in smaller and smaller neighborhoods of $x$. We sometimes write $\lim x^{(n)}$ rather than $\lim_{n\to\infty} x^{(n)}$ when there is no confusion. We use superscripts $x^{(n)}$ rather than subscripts $x_n$ since the latter will be used to denote vector components later on in this chapter.

Unless stated otherwise, real numbers in this book are associated with the metric space $(\R,d)$ where $d(x,y)=|x-y|$. Thus, convergence of a sequence of real numbers $x^{(n)}$ to a limit implies that \[ \forall \epsilon > 0, \quad \exists N\in\mathbb{N}, \quad n > N\quad \Rightarrow \quad |x^{(n)}- x| < \epsilon.\]

Definition B.2.2. For a sequence $s^{(n)}\in\R, n\in\mathbb{N}$, we write $\lim s^{(n)}= +\infty$ if \[ \forall M\in \R, \quad \exists N\in \mathbb{N}, \quad n > N\Rightarrow s^{(n)}\geq M.\] Similarly we write $\lim s^{(n)}=-\infty$ if \[ \forall M\in \R, \quad \exists N\in \mathbb{N}, \quad n>N\Rightarrow s^{(n)}\leq M.\]
Example B.2.1. The sequence $1,1,1,\ldots$ converges to 1, but the sequence $1,2,1,2,1,\ldots$ does not converge to any limit.
Example B.2.2. The sequence $2^{-n}, n\in\mathbb{N}$ converges to 0 since the tail sequences of $1/(2^n)$ get arbitrarily close to 0. Formally, for all $\epsilon$ there exists $N$ such that $n>N$ implies $|2^{-n}-0|=2^{-n}=(1/2)^n < \epsilon$. For example, we can take $N$ be a natural number greater than $\log_{1/2}(\epsilon)$.
Example B.2.3. We have $\lim_{n\to\infty} n=\lim_{n\to\infty} n^2=+\infty$ but $1,0,2,0,3,0,\ldots$ does not converge to a finite limit nor does it converge to infinity.
Definition B.2.3. A sequence of real numbers $x^{(n)}\in\R, n\in\mathbb{N}$ is monotonic increasing, denoted by $x^{(n)}\nearrow$, if $x^{(n)}\leq x^{(n+1)}$ for all $n\in\mathbb{N}$ and is monotonic decreasing, denoted by $x^{(n)}\searrow$, if $x^{(n)}\geq x^{(n+1)}$ for all $n\in\mathbb{N}$. A sequence is monotonic if it is either monotonic increasing or monotonic decreasing. We use the notations $x^{(n)}\nearrow x$ and $x^{(n)}\searrow x$ if $\lim x^{(n)}= x$ and $x^{(n)}$ is monotonic increasing or decreasing, respectively. Replacing the $\leq$ symbol above with $\lt$, we get the analogous concept of strictly monotonic sequences.
Definition B.2.4. An upper bound $x$ of a set $A\subset\R$ satisfies $x\geq y$ for all $y\in A$. A lower bound $x$ of a set $A\subset\R$ satisfies $x\leq y$ for all $y\in A$. The smallest upper bound of a set $E$ is the value $\alpha$ such that if $\beta < \alpha$ then $\beta$ is not an upper bound. This value is called the supremum of $E$ and is denoted by $\sup E$. The largest lower bound of a set $E$ is the value $\alpha$ such that if $\beta>\alpha$ then $\beta$ is not a lower bound. This value is called the infimum of $E$ and is denoted by $\inf E$.
Example B.2.4. We have $\sup [a,b]=\sup (a,b)=b$, and $\inf [a,b]=\inf (a,b)=a$.

An important property of the real numbers is that the supremum of a set $A\subset\R$ that is bounded from above always exist. Similarly, the infimum of a set $A\subset \R$ that is bounded from below always exist. A proof of this property is available in (Rudin, 1976, Chapter 1). Interestingly, the set of rational numbers $\mathbb{Q}$ does not have this property.

Proposition B.2.1. A monotonic increasing sequence $x^{(n)}\in\R$, $n\in\mathbb{N}$ that is bounded from above converges to a finite limit. Similarly, a monotonic decreasing sequence $x^{(n)}\in\R$, $n\in\mathbb{N}$ that is bounded from below converges to a finite limit. Monotonic sequences that are not bounded also converge to a limit, which may be a finite number or $+\infty$ (if it is increasing) or $-\infty$ (if it is decreasing).
Proof. We assume the sequence is monotonic increasing and bounded. The sequence of distances $y^{(n)}=|x^{(n)}-\sup\{x^{(n)}\,:\,n\in\mathbb{N}\}|$, $n\in\mathbb{N}$ is monotonically decreasing and for $\epsilon$ there exists $N$ such that $n>n$ implies $y^{(n)} < \epsilon$. This means that $x^{(n)}$ converges to $\sup\{x^{(n)}:n\in\mathbb{N}\}$. The case of monotonic decreasing is similar.
Definition B.2.5. A function $f:(a,b)\to\R$ is monotonic increasing if for all $c < d$, we have $f(c)\leq f(d)$ and monotonic decreasing if for all $c < d$, we have $f(c)\geq f(d)$. If the inequalities hold without equality the function is strictly monotonic increasing or strictly monotonic decreasing.

The following definitions are analogous the the $\limsup$ and $\liminf$ definitions in Section A.4.

Definition B.2.6. For a sequence $s^{(n)}\in\R, n\in\mathbb{N}$, we define \begin{align*} \liminf_{n\to\infty} s^{(n)} &= \lim_{n\to\infty} \inf \{s^{(k)}: k\geq n\} \\ \limsup_{n\to\infty} s^{(n)} &= \lim_{n\to\infty} \sup \{s^{(k)}: k \geq n\}. \end{align*}
Proposition B.2.2. The values $\liminf_{n\to\infty} s^{(n)}$ and $\liminf_{n\to\infty} s^{(n)}$ always exist, either as a finite number or as $+\infty$ or $-\infty$.
Proof. The sequence $v^{(n)}=\inf \{s^{(k)}: k\geq n\}$ is monotonic increasing, which converges by Proposition B.2.1 either to a finite limit or to an infinite limit. The proof in the case of $\limsup s^{(n)}$ is analogous.
Definition B.2.7. A subsequence of a sequence $x^{(n)}, n\in\mathbb{N}$ is a sequence obtained from $x^{(n)}, n\in\mathbb{N}$ by omitting some indices.
Definition B.2.8. If a sub-sequence of ${x}^{(n)}$ converges to $\alpha$ then $\alpha$ is called a sub-sequential limit of the sequence $ x^{(n)}$.

Note that sub-sequential limits may exist even when a limit may not. For example, the sequence $1,2,1,2,1,\ldots$ in Example B.2.1 has no limit, but it has two sub-sequential limits: 1 and 2.

Proposition B.2.3. For a sequence $s^{(n)}\in\R, n\in\mathbb{N}$ whose set of sub-sequential limits is $E$, we have \begin{align*} \limsup_{n\to\infty} s^{(n)} &= \sup E\\ \liminf_{n\to\infty} s^{(n)} &= \inf E. \end{align*}
Proof. If $\liminf_{n\to\infty} s^{(n)} < \inf E$, then for all $\epsilon>0$ there exists $N>0$ such that $\inf \{s^{(k)}: k\geq N\} \leq\inf E-\epsilon$. This contradicts the definition of $E$ as the set of sub-sequential limits. The case $\liminf_{n\to\infty} s^{(n)}>\inf E$ leads to a similar contradiction. The proof of the first statement is similar.
Corollary B.2.1. \[-\infty\leq \liminf s^{(n)} \leq \limsup s^{(n)} \leq +\infty.\]
Proposition B.2.4. For $s^{(n)}\in\R, n\in\mathbb{N}$, we have $\lim s^{(n)}=s$ if and only if \[\liminf s^{(n)} = \limsup s^{(n)}=s.\]
Proof. If $\liminf s^{(n)}=\limsup s^{(n)}=\alpha$ then $v^{(n)}=\inf_{k\geq n} s^{(k)}$ and $w^{(n)}=\sup_{k\geq n} s^{(k)}$ converge to $\alpha$, implying that for all $\epsilon>0$ there exists $N>0$ such $n>N$ implies $d(s^{(n)},\alpha) < \epsilon$. This implies that $s^{(n)}\to\alpha$.

If $s^{(n)}\to \alpha$ then for all $\epsilon>0$ there exists $N>0$ such that $n>N$ implies $d(s^{(n)},\alpha) < \epsilon$. It follows that $v^{(n)}=\inf_{k\geq n} s^{(k)}$ and $w^{(n)}=\sup_{k\geq n} s^{(k)}$ converge to $\alpha$.

Example B.2.5. We have \begin{align*} \limsup_{n\to\infty} 2^{-n} &= \liminf_{n\to\infty} 2^{-n}=\lim_{n\to\infty} 2^{-n}=0\\ \limsup_{n\to\infty} n &= \liminf_{n\to\infty} n=\lim_{n\to\infty} n=+\infty, \end{align*} and for $x^{(n)}=1,0,2,0,3,0,4,0,\ldots$ we have that $\lim_{n\to\infty} x^{(n)}$ does not exist and \[0 = \liminf x^{(n)} < \limsup x^{(n)}=+\infty.\]
Definition B.2.9. Let $f:A\to B$ be a function from one metric space to another. The limit $\lim_{ x\to y} f( x)$ is the value $ v$ for which \[ \forall \epsilon>0, \quad \exists \delta>0, \quad d( x, y) < \delta\quad \Rightarrow\quad d(f( x), v) < \epsilon.\] When $B=\R$ we write $\lim_{ x\to y} f( x) = +\infty$ if \[ \forall M\in \R, \quad \exists\delta>0 \quad d( x, y) < \delta \quad \Rightarrow \quad f(x) > M\] and $\lim_{ x\to y} f( x)=-\infty$ if \[ \forall M\in\R, \quad \exists\delta>0 \quad d( x, y) < \delta \quad \Rightarrow\quad f(x) < M.\]
Definition B.2.10. For a function $f:\R\to B$, where $B$ is a metric space, we write $\lim_{x\to +\infty} f(x)= v$ if \[ \forall \epsilon>0 \quad \exists N\in\mathbb{N}, \quad x > N \quad\Rightarrow \quad d(f( x), v) < \epsilon\] and $\lim_{x\to -\infty} f(x)=v$ if \[ \forall \epsilon>0 \quad \exists N\in\mathbb{N}, \quad x < N \quad\Rightarrow \quad d(f(x), v) < \epsilon.\]

There are two limit concepts defined above, one for sequences and one for functions. The following proposition connects these two concepts.

Proposition B.2.5. $\lim_{ x\to y} f( x)= v$ if and only if the following statement holds \begin{align} \lim_{n\to\infty}{ x}^{(n)}=y \text{ and } \forall n\in\mathbb{N},\, { x}^{(n)}\neq y \quad \text{ implies } \quad \lim_{n\to\infty} f({ x}^{(n)})= v. \tag{*} \end{align}
Proof. We assume $\lim_{ x\to y} f( x)= v$ and $\lim { x}^{(n)}=y$ and for all $n$, $x^{(n)}\neq y$, and show that $\lim_{n\to\infty} f({ x}^{(n)})= v$. For all $\delta>0$ there exists $N$ such that for $n>N$, $d({ x}^{(n)}, y) < \delta$. Also, for every $\epsilon>0$ there exists $\delta>0$ such that if $d({ x}, y) < \delta$ then $d(f({ x}), v) < \epsilon$. Combining these two results shows that $\lim_{n\to\infty} f({ x}^{(n)})= v$.

Conversely, we assume that $\lim_{ x\to y} f( x)\neq v$ and show that Equation (*) does not hold. In this case $\exists \epsilon>0$ such that for all $\delta>0$ there exists a point $ x$ for which $d( x, y) < \delta$ and $d(f( x), v)>\epsilon$. Repeating this argument for $\delta_n=1/n$, we find a sequence ${ x}^{(n)}$ converging to $ y$ but for which $\lim f({ x}^{(n)})\neq v.$

One sided limits of $f:\R\to\R$ are similar to limits, except that the approach $x\to a$ is restricted to be from a single side. In some cases, the limit $\lim_{x\to a}f(x)$ does not exist but the one sided limits do.

Definition B.2.11. The right-sided limit of $f:\R\to \R$ is $L=\lim_{x\to a^+}f(x)$ if \begin{align*} \forall \epsilon > 0 \quad\exists \delta > 0, \quad a < x < a+\delta\quad \Rightarrow \quad |f(x)-L| < \epsilon. \end{align*} The left-sided limit is $L=\lim_{x\to a^-}f(x)$ if \[\forall\epsilon > 0 \quad\exists \delta > 0, \quad a-\delta < x < a\quad \Rightarrow \quad |f(x)-L| < \epsilon.\]
Definition B.2.12. Let $f_n:A\to B, n\in\mathbb{N}$ be a sequence of functions for which $f_n(x)\to f(x)$ for all $x\in A$. We then say that $f_n$ converge point-wise to $f$, and denote it by $f_n\to f$. We denote $f_n\nearrow f$ if in addition to $f_n\to f$ we also have $B=\R$ and $f_1\leq f_2\leq f_3\leq \cdots$ (recall Definition A.2.5).
Definition B.2.13. A function $f:A\to\R$ is bounded if $\sup_{x\in A}|f(x)| < \infty$, bounded from above if $\sup_{x\in A} f(x) < \infty$, and bounded from below if $\inf_{x\in A} f(x) > -\infty$.