# Using Chebyshev’s inequality and the Borel-Cantelli lemma to study the variation of Brownian motion

Chebyshev’s inequality and the Borel-Cantelli lemma are seemingly disparate results from probability theory but they combine beautifully in demonstrating a curious property of Brownian motion: that it has finite quadratic variation even though it has unbounded linear variation. Not only do the proofs of Chebyshev’s inequality and the Borel-Cantelli lemma have some interesting features themselves, but their application to the variation of Brownian motion also provides a nice example of how to prove explicitly that a sequence of random variables converges almost surely by showing that the probability of the divergence set is zero. In this note I want to bring out this last aspect in particular.

There are two equivalent forms of Chebyshev’s inequality. Letting $X$ denote an integrable random variable with mean $\mu$ and finite non-zero variance $\sigma^2$, one form of Chebyshev’s inequality says

$P(|X - \mu| \geq k\sigma) \leq \frac{1}{k^2}$

where $k > 0$ is a real number.

Equivalently, if we let $\epsilon = k\sigma$, then we can write Chebyshev’s inequality as

$P(|X - \mu| \geq \epsilon) \leq \frac{\sigma^2}{\epsilon^2}$

Proof of Chebyshev’s inequality

The following is a proof of the second form. Since $\epsilon > 0$, we have

$|X - \mu| \geq \epsilon \iff (X - \mu)^2 \geq \epsilon^2$

Let $g(t) = (t - \mu)^2$ so that $\mathbb{E}[g(X)] = \sigma^2$.

Let

$A = \{\omega : g(X(\omega)) \geq \epsilon^2\}$

$\equiv \{\omega : (X - \mu)^2 \geq \epsilon^2\}$

$\equiv \{\omega : |X - \mu| \geq \epsilon\}$

If $\omega \in A$ then $I_A(\omega) = 1$ and

$\epsilon^2I_A(\omega) \leq g(X(\omega))$

(by definition of $A$). However, if $\omega \in A^c$ then $I_A(\omega) = 0$ so it is still true that

$\epsilon^2I_A(\omega) \leq g(X(\omega))$

Thus, this inequality always holds. Taking expectations we get

$\mathbb{E}[\epsilon^2I_A(\omega)] = \epsilon^2P(A) = \epsilon^2P(|X - \mu| \geq \epsilon) \leq \mathbb{E}[g(X(\omega))] = \sigma^2$

Division of both sides by $\epsilon^2$ gives Chebyshev’s inequality. QED

The Borel-Cantelli lemma actually consists of a pair of results. Let $\{A_k : 1 \leq k\}$ be a sequence of events, i.e., a sequence of subsets of $\Omega$. Then

$\limsup \limits_{ k } A_k \equiv \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k$

is the set of all elements $\omega \in \Omega$ that are in an infinity of the subsets $A_k$. The Borel-Cantelli lemma says the following:

(a) If $\sum_{k=1}^{\infty} P(A_k) < \infty$ then $P\bigg(\limsup \limits_{ k } A_k\bigg) = 0$

(b) If $\{A_k : 1 \leq k\}$ is independent and $\sum_{k=1}^{\infty}P(A_k) = \infty$ then $P\bigg(\limsup \limits_{ k } A_k\bigg) = 1$

Proof of the Borel-Cantelli lemma

(a) For any integer $n \geq 1$, we can write

$0 \leq P\bigg(\limsup \limits_{ k } A_k\bigg) = P(\bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k) \leq P(\bigcup_{k=n}^{\infty}) \leq \sum_{k=n}^{\infty}P(A_k)$

(the last inequality by subadditivity). Since $\sum_{k=1}^{\infty} P(A_k)$ converges, the tail sums $\sum_{k=n}^{\infty}P(A_k) \rightarrow 0$ as $n \rightarrow \infty$. Therefore (by a ‘sandwich’ argument) $P\bigg(\limsup \limits_{ k } A_k\bigg) = 0$.

(b) We have

$\bigg(\limsup \limits_{ k } A_k\bigg)^c = (\bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty} A_k)^c$

$= \bigcup_{n=1}^{\infty} (\bigcup_{k=n}^{\infty} A_k)^c = \bigcup_{n=1}^{\infty} \bigcap_{k=n}^{\infty} A_k^c$

$\equiv \bigcup_{n=1}^{\infty} F_n$

(by De Morgan’s laws). Therefore

$1 - P\bigg(\limsup \limits_{ k } A_k\bigg) = P\bigg(\bigg(\limsup \limits_{ k } A_k\bigg)^c\bigg) = P(\bigcup_{n=1}^{\infty} F_n) \leq \sum_{n=1}^{\infty}P(F_n)$

By the product rule for independent events,

$P(F_n) = P(\bigcap_{k=n}^{\infty} A_k^c) = \prod_{k=n}^{\infty}P(A_k^c) = \prod_{k=n}^{\infty}(1 - P(A_k))$

Now, for all $a \geq 0$ we have $1 - a \leq e^{-a}$. (To see this, let $f(a) = e^{-a} - (1 - a)$. Then $f(0) = 0$ and $f^{\prime}(a) = -e^{-a} + 1 > 0$. Therefore $f(a)$ is an increasing function, so $f(a) \geq f(0)$ for $a \geq 0$). It follows that

$1 - P(A_k) \leq \exp(-P(A_k))$

and therefore also

$\prod_{k=n}^{N}(1 - P(A_k)) \leq \exp(-\sum_{k=n}^N P(A_k))$

But $\exp(-\sum_{k=n}^N P(A_k)) \rightarrow 0$ as $N \rightarrow \infty$. Therefore $P(F_n) = 0$ and $\sum_{n=1}^{\infty}P(F_n) = 0$, so $1 - P\bigg(\limsup \limits_{ k } A_k\bigg) = 0 \implies P\bigg(\limsup \limits_{ k } A_k\bigg) = 1$. QED

To apply these results to the variation of Brownian motion, let

$\triangle_n \equiv \{a = t_0 < t_1 < \cdots < t_n = b\}$

be a partition of the interval $[a, b]$. Define the mesh of the partition $\triangle_n$ by

$||\triangle_n|| \equiv \max_{1 \leq i \leq n}(t_i - t_{i-1})$

Let us restrict ourselves only to sequences of partitions $\{\triangle_n : 1 \leq n\}$ for which $||\triangle_n|| \rightarrow 0$, and in particular for which $\sum_{n=1}^{\infty} ||\triangle_n|| < \infty$. For every $p > 0$ let

$Q_p(f; a, b, \triangle_n) \equiv \sum_{i=1}^{n}|f(t_i) - f(t_{i-1})|^p$

and let

$V_p(f; a, b) \equiv \lim \limits_{||\triangle_n|| \rightarrow 0} Q_p(f; a, b, \triangle_n)$

where $f$ is a real-valued function defined on $[a, b]$. If $V_p(f; a, b) < \infty$ we will say that $f$ has finite $p^{th}$ variation on $[a, b]$. In the case $p = 1$, if $V_1(f; a, b) < \infty$ we will say that $f$ is of bounded linear variation on $[a, b]$. In the case $p = 2$, if $V_2(f; a, b) < \infty$ we will say that $f$ is of bounded quadratic variation on $[a, b]$

If we replace $f$ in the above by a Brownian motion $B$, then we find a curious result: $B$ is of unbounded linear variation almost surely, but it has a finite quadratic variation equal to $b - a$ almost surely. In other words,

$V_1(B; a, b) = \infty$    (a.s.)

$V_2(B; a, b) = b - a$    (a.s.)

We will use Chebyshev’s inequality and the Borel-Cantelli lemma to prove these.

Theorem 1

If $\{\triangle_n : 1 \leq n\}$ is a sequence of partitions of $[a, b]$ with $\sum_{n=1}^{\infty} ||\triangle_n|| < \infty$ (and therefore $||\triangle_n|| \rightarrow 0$), then

$Q_2(B; a, b, \triangle_n) = \sum_{i=1}^n |B(t_i) - B(t_{i-1})|^2 \rightarrow b - a$ (a.s.)

as $n \rightarrow \infty$. In other words, Brownian motion has bounded quadratic variation on $[a, b]$ equal to $b - a$, almost surely.

Proof:

Observe that, by ‘telescoping’,

$\sum_{i=1}^{n}(t_i - t_{i-1}) = b - a$

Let

$Y_n = \sum_{i=1}^{n}(B(t_i) - B(t_{i-1}))^2 - (b - a)$

$= \sum_{i=1}^{n}\big\{(B(t_i) - B(t_{i-1}))^2 - (t_i - t_{i-1})\big\}$

Note that $\mathbb{E}[Y_n] = 0$ because $\mathbb{E}[(B(t_i) - B(t_{i-1}))^2] = t_i - t_{i-1}$. Therefore

$\mathbb{V}[Y_n] = \mathbb{E}[Y_n^2]$

$= \mathbb{E}\big[\big(\sum_{i=1}^n \big\{(B(t_i) - B(t_{i-1}))^2 - (t_i - t_{i-1})\big\} \big)^2 \big]$

$= \sum_{i=1}^n \mathbb{E}\big[\big\{(B(t_i) - B(t_{i-1}))^2 - (t_i - t_{i-1})\big\}^2 \big]$

(cross product terms vanish since Brownian motion has independent increments)

$= \sum_{i=1}^n \mathbb{E}\big[(B(t_i) - B(t_{i-1}))^4 - 2(t_i - t_{i-1})(B(t_i) - B(t_{i-1}))^2 + (t_i - t_{i-1})^2 \big]$

$= \sum_{i=1}^n \big(3(t_i - t_{i-1})^2 - 2(t_i - t_{i-1})^2 + (t_i - t_{i-1})^2 \big)$

(since the fourth moment of a zero-mean normal random variable is $3\sigma^4$ and here $\sigma^2 = (t_i - t_{i-1})$)

$= \sum_{i=1}^n 2(t_i - t_{i-1})^2$

$\leq 2 ||\triangle_n||\sum_{i=1}^n (t_i - t_{i-1})$

$= 2(b - a)||\triangle_n||$

(Since $||\triangle_n|| \rightarrow 0$, we see already at this stage that $Y_n \rightarrow 0$ in $\mathcal{L}^2$).

By the second form of Chebyshev’s inequality we can now write for any $\epsilon > 0$ that

$\sum_{n=1}^{\infty}P(|Y_n| > \epsilon) \leq \sum_{n=1}^{\infty} \frac{\mathbb{E}[Y_n^2]}{\epsilon^2}$

$\leq \frac{2(b - a)}{\epsilon^2}\sum_{n=1}^{\infty}||\triangle_n|| < \infty$

In particular, we can write for any integer $q \geq 1$ that

$\sum_{n=1}^{\infty} P\big(|Y_n| > \frac{1}{q}\big) < \infty$

By the first result in the Borel-Cantelli lemma we can then say

$P\bigg(\limsup \limits_{ k } A_k(q)\bigg) = 0$

where

$A_k(q) = \big\{\omega : |Y_k| > \frac{1}{q}\big\}$

Now,

$\limsup \limits_{ k } A_k(q) = \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty}A_k(q)$

so if $P\bigg(\limsup \limits_{ k } A_k(q)\bigg) = 0$ then we must also have

$P\big(\bigcup_{q=1}^{\infty} \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty}A_k(q)\big) = 0$

But

$\bigcup_{q=1}^{\infty} \bigcap_{n=1}^{\infty} \bigcup_{k=n}^{\infty}A_k(q)$

is the divergence set when considering the almost sure convergence of $Y_n$ to zero. Since the probability of the divergence set is zero, we conclude that $Y_n \rightarrow 0$ a.s., and therefore $Q_p(B; a, b, \triangle_n) \rightarrow b - a$ (a.s.). QED

Theorem 2

If $\{\triangle_n : 1 \leq n\}$ is a sequence of partitions of $[a, b]$ with $||\triangle_n|| \rightarrow 0$, then

$Q_1(B; a, b, \triangle_n) = \sum_{i=1}^n |B(t_i) - B(t_{i-1})| \rightarrow \infty$ (a.s.)

as $n \rightarrow \infty$. In other words, Brownian motion has unbounded linear variation on $[a, b]$, almost surely.

Proof:

By contradiction. Suppose Brownian motion has bounded linear variation, i.e., $V_1(B; a, b) < \infty$. Then we can write

$\sum_{i=1}^n |B(t_i) - B(t_{i-1})|^2 \leq \max_{1 \leq i \leq n}|B(t_i) - B(t_{i-1})|\sum_{i=1}^n |B(t_i) - B(t_{i-1})|$

$\leq V_1(B; a, b)\max_{1 \leq i \leq n}|B(t_i) - B(t_{i-1})|$

Since $B$ is uniformly continuous on $[a, b]$ ($B$ is continuous on $[a, b]$ and any continuous function is uniformly continuous when restricted to a compact set) we can write

$\max_{1 \leq i \leq n}|B(t_i) - B(t_{i-1})| \rightarrow 0$ as $||\triangle_n|| \rightarrow 0$

which if $V_1(B; a, b) < \infty$ implies

$\sum_{i=1}^n |B(t_i) - B(t_{i-1})|^2 \rightarrow 0$ (a.s.)

This contradicts Theorem 1. Therefore $B$ cannot have bounded linear variation. QED