Probability Theory

Probability: Study of regular patterns that arise from random phenomena

Statistics: The inverse problem of making inferences from observations of patterns in random phenomena.

1 Preliminary: Measure Theory

Measures are defined to characterize the ”mass” of a set, which is crucial in defining the Lebesgue integral, probability measure, etc. In order to define measures, we need first assume some structures on the space of sets, i.e., $\sigma$-Algebra.

1.1 $\sigma$-Algebra

Definition 1.1 ($\sigma$-Algebra).

A $\sigma$-algebra on $X$ is a family of subsets of $X$, $ℱ$, such that,

• $\mathrm{\varnothing },X\in ℱ$

• If $A\in ℱ$, then $A^C\in ℱ$

• Let $ℐ$ be a countable set. If $\forall A_i\in ℱ$, for $i\in ℐ$, then ${\bigcup }_{i=1}^{ℐ}{A}_i\in ℱ$ and ${\bigcap }_{i\in ℐ}{A}_i\in ℱ$.

Definition 1.2 (Borel $\sigma$-Algebra).

Borel $\sigma$-Algebra $B\mathit{}\mathrm{(}X\mathrm{)}$ is the $\sigma$-Algebra generated by open sets in $X$.

$$B(X)=B({𝒯}_X)$$ (1)

where $\mathrm{(}X\mathrm{,}{𝒯}_X\mathrm{)}$ is a topological space.

1.2 Measures

Definition 1.3 (Measures).

A measure $\mu \mathrm{:}ℱ\mathrm{\to }\mathrm{[}\mathrm{0}\mathrm{,}\mathrm{\infty }\mathrm{]}$ is defined on a space with $\sigma$-Algebra $\mathrm{(}X\mathrm{,}ℱ\mathrm{)}$, such that

• $\mu (\mathrm{\varnothing })=0$.

• $\mu ({\cup }_{i=1}^{\mathrm{\infty }}{A}_i)={\sum }_{i=1}^{\mathrm{\infty }}\mu (A_i)$, for disjoint sets $\{A_i\}$.

This space is then called measurable space $\mathrm{(}X\mathrm{,}ℱ\mathrm{,}\mu \mathrm{)}$.

Definition 1.4 (Probability measure).

A probability measure $\mu$ on $X$ is a specific measure with $\mu \mathit{}\mathrm{(}X\mathrm{)}\mathrm{=}\mathrm{1}$.

Other measures:

• Dirac measure:

  $${\delta }_t(A):=\{\begin{array}{cc}1,t\in A\hfill & \\ 0,t\notin A\hfill & \end{array}$$ (2)

• Counting measures

  $$\mathrm{\#}(A)=\mathrm{\#}\text{ elements in }A$$ (3)

1.3 Some related definitions

Finite measure: If , then $\mu$ is finite.

$\sigma$-finite measure: If we can cover $X$ by countably many measurable sets each with finite measure, we call it a $\sigma$-finite measure.

A straightforward claim: finite measures are $\sigma$-finite measures. ”Length” on $ℝ$ is a $\sigma$-finite measure but not finite.

Negligible: If a measurable set $A$ has $\mu (A)=0$ then it is a negligible set for $\mu$.

Almost everywhere: If a measurable set $A$ has $\mu (A^C)=0$ then it is $\mu$-almost everywhere, denoted as $\mu -$a.e.

1.4 Lebesgue measure

Borel measure: $B(ℝ)\to [0,\mathrm{\infty }]$.

Lebesgue measures are defined on Borel $\sigma$-Algebra. For example, on $ℝ$:

$$\lambda (A):=inf\{\sum _{i=1}^{\mathrm{\infty }}|b_i-a_i|:A\subseteq \bigcup _{i=1}^{\mathrm{\infty }}(a_i,b_i)\},\forall A\in B(ℝ).$$ (4)

Intuition: to find the minimum union of intervals that covers $A$. (Note: union of intervals on $ℝ$ can always be written as a countable union of intervals).

• It is a measure

• $\lambda ((a,b))=|b-a|$, for .

• Translation invariance: $\lambda (A+t)=\lambda (A)$ for all $A\in B(ℝ)$.

Lebesgue measure is the only Borel measure that satisfies the above properties.

Another example of Borel measure: is the cumulative distribution function, which is finite and monotone.

1.5 Integration

Riemann Integral. Let $a\le b\in ℝ$. We say $f$ is Riemann Integrable if the following limit exists:

$$\underset{\max \mathrm{\Delta }{x}_k\to 0}{lim}\sum _{k=1}^{n}f(x_k^{*})\mathrm{\Delta }{x}_k,$$ (5)

where $x_k^{*}$ is an arbitrary point in the interval $\mathrm{\Delta }{x}_k$.

However, Riemann integral may not exist. For example, $f_n(q_i)=1$ for rational numbers in $[0,1]$ and $f_n(x)=0$ otherwise. No matter how small an interval $\mathrm{\Delta }{x}_k$ could be, it contains rational numbers and irrational numbers.

Definition 1.5 (Decreasing Rearrangement).

For a function $f\mathrm{:}ℝ\mathrm{\to }{ℝ}_{\mathrm{+}}$, the dereasing rearrangement $h\mathrm{:}{ℝ}_{\mathrm{+}}\mathrm{\to }{ℝ}_{\mathrm{+}}$ is defined as following:

$$h(t):=\lambda \{x\in ℝLf(x)>t\}\text{𝑓𝑜𝑟}t\ge 0.$$ (6)

$h(t)$ is a decreasing function, as measure $h$ is monotonic.

Remark. Given the definition of $h$, our expectation is to define integration by:

$${\int }_{ℝ}f(x)\lambda (𝕕x)={\int }_0^{\mathrm{\infty }}\lambda \{x\in ℝ:f(x)>t\}dt={\int }_0^{\mathrm{\infty }}h(t)dt.$$ (7)

The intuition of this definition is: instead of counting the area by $x$-axis, we count the area by $y$-axis.

In order to ensure this integration works, we need $\{x\in ℝ:f(x)>t\}$ to be measurable. The definition below of measurable function solves this problem.

Definition 1.6 ((Borel) Measurable function).

Let $\mathrm{(}X\mathrm{,}ℱ\mathrm{)}$ be a measurable space. A function $f\mathrm{:}X\mathrm{\to }ℝ$ is Borel-measurable if

$$f^{-1}((t,\mathrm{\infty })):=\{x\in X:f(x)>t\}\in ℱ$$ (8)

Proposition 1.7.

A function $f\mathrm{:}X\mathrm{\to }ℝ$ is Borel measurable if and only if

$$f^{(-1)}(B)\in ℱ,$$ (9)

for all Borel $B\mathrm{\in }ℬ\mathit{}\mathrm{(}ℝ\mathrm{)}$.

Properties of measurable functions:

• If $f,g$ measurable, $f\circ g$ is measurable (for $X=ℝ$),

• $f+g$ is measurable,

• $f_{+}(x):=\max \{f(x),0\},f_{(}x)=\max {}_{-f(x),0}$ are measurable,

• $|f|$ is measurable,

• $fg$ is measurable.

• If $f_i:X\to ℝ\cup \{-infty,\mathrm{\infty }\}$ are measurable functions, ${sup}_{i\in \mathbb{N}}{f}_i,{inf}_{i\in \mathbb{N}}{f}_i$ are measurable.

Given the rigorous definition above, we can finally define Lebesgue integration. We first define it on positive functions and use it as a tool to define Lebesgue-integrable function in general.

Definition 1.8 (Lebesgue integral of positive function).

Let $\mu$ be a Borel measure. Let $f\mathrm{:}ℝ\mathrm{\to }{ℝ}_{\mathrm{+}}\mathrm{\cup }\mathrm{\{}\mathrm{\infty }\mathrm{\}}$ be a positive, measurable function. Then we define the Lebesgue integral of $f$ with respect to $\mu$ with

$${\int }_{ℝ}f(x)\mu (\mathrm{d}x)={\int }_0^{\mathrm{\infty }}\mu \{x\in ℝ:f(x)>t\}dt$$ (10)

Definition 1.9 (Lebesgue integrable function).

A finite valued measurable function $f\mathrm{:}ℝ\mathrm{\to }ℝ$ is integrable with respect to Borel measure $\mu$ if

(11)

Its Lebesgue integral is defined as

$${\int }_{ℝ}f(x)\mu (\mathrm{d}x):={\int }_{ℝ}{f}_{+}(x)\mu (\mathrm{d}x)-{\int }_{ℝ}{f}_{-}(x)\mu (\mathrm{d}x).$$ (12)

notated by $\mu \mathit{}\mathrm{(}f\mathrm{)}$.

Proposition 1.10.

A bounded function over a bounded domain $f\mathrm{:}\mathrm{[}a\mathrm{,}b\mathrm{]}\mathrm{\to }ℝ$ is a Riemann integrable function, then $f$ is Lebesgue integrable with respect to the Lebesgue measure $\lambda$.

$$f_{[a,b]}f(x)\lambda (\mathrm{d}x)={\int }_a^{b}f(x)dx.$$ (13)

Proposition 1.11 (Monotone Convergence).

Let $\mathrm{(}{f}_j\mathrm{:}X\mathrm{\to }{ℝ}_{\mathrm{+}}\mathrm{\cup }\mathrm{\{}\mathrm{\infty }\mathrm{\}}\mathrm{)}j\mathrm{\in }\mathbb{N}$ are positive, measurable functions. $f_j\mathit{}\mathrm{(}x\mathrm{)}$ increasing in terms of $j$, and ${\lim }_{j\mathrm{\to }\mathrm{\infty }}{f}_j\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}f\mathit{}\mathrm{(}x\mathrm{)}$ for all $x\mathrm{\in }X$. Then the integral

$$\underset{j\to \mathrm{\infty }}{lim}\mu (f_j)=\mu (f).$$ (14)

2 Mathematical Foundation of Probability

Developed by Kolmogorov in 1933, an axiomatic foundation for the theory of probability.

Definition 2.1 (Probability Space, ANK 1933).

A triple $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$, where

• $\mathrm{\Omega }$ is a set called the sample space.

• $ℱ$ is a $\sigma$-Algebra of $\mathrm{\Omega }$.

• $\mathbb{P}$ is a probability measure on $(\mathrm{\Omega },ℱ)$ assigning probability to events.

Notes:

• $\omega \in \mathrm{\Omega }$ are called sample points, outcomes of a probability experiment in simple cases.

• $ℱ$ identifies sets of sample points that are assigned probabilities. $E\in ℱ$ are called events.

• When ${\omega }_0\in E$ occurs, we say the event $E$ occurs.

• If $\mathrm{\Omega }$ is finite or countable, then we can take $ℱ=P(\mathrm{\Omega })$. However for ${ℝ}^n$, the power set is too big for a reasonable measurable $\sigma$-Algebra, so we take Borel $\sigma$-Algebra $B({ℝ}^n)$.

States in $\mathrm{\Omega }$ give a complete system description, but it’s often too detailed and inaccessible. Instead, we are more interested in observables, or system statistics, which are called random variables in probability theory.

Definition 2.2 (Real Random Variable).

Let $\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}$ be a probability space. A real random variable is a measurable function

$$X:\mathrm{\Omega }\to ℝ$$ (15)

Remarks.

$X$ is a fixed function, so where does the ”randomness” come from? In fact, all the randomness comes from the $X(\omega )$ where $\omega$ is random in the probability space.

Distributions of probability over the events induce a distribution of probability over the values in $ℝ$ of the random variable.

The term ”measurable function” used above is defined as:

Definition 2.3 (Measurable function).

A measurable function $X\mathrm{:}\mathrm{\Omega }\mathrm{\to }ℝ$ has the property that $X^{\mathrm{-}\mathrm{1}}\mathit{}\mathrm{(}B\mathrm{)}\mathrm{\in }ℱ$ for all $B\mathrm{\in }ℬ\mathit{}\mathrm{(}ℝ\mathrm{)}$.

Based on this property, we can compute the probability that $X$ takes a value in $B\in ℬ(ℝ)$:

$$\mathbb{P}(X\in B):=\mathbb{P}\{\omega \in \mathrm{\Omega }:X(\omega \in B\}=\mathbb{P}(X^{-1}(B)).$$ (16)

Definition 2.4 (Law of a real random variable).

Let $\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}$ be a probability space. Let $X\mathrm{:}\mathrm{\Omega }\mathrm{\to }ℝ$ be a real random variable.

The law (or distribution) of $X$ is the Borel probability measure ${\mu }_X$ on $\mathrm{(}ℝ\mathrm{,}ℬ\mathit{}\mathrm{(}ℝ\mathrm{)}\mathrm{)}$, s.t.,

$${\mu }_X(B)=\mathbb{P}\{X\in B\},\forall B\in (ℝ).$$ (17)

Notes. The probability that $X\in B$ can be expressed as

$$\mathbb{P}(X\in B)={\int }_{ℝ}{\mathrm{𝟙}}_B(x){\mu }_X(\mathrm{d}x).$$ (18)

Definition 2.5 (Distribution function).

Let $X$ be a real random variable on a probability space with law ${\mu }_X$. Define

$$F_X(a):=\mathbb{P}\{X\le a\}={\mu }_X((-\mathrm{\infty },a]),\forall a\in ℝ.$$ (19)

This is called a cumulative distribution function (CDF) of $X$.

Note: It is important to make sure it’s a $\le$ but not a in the definition.

Properties of CDF:

• Monotonicity

• Asymptotic

• Right-continuous

• Law: ${\mu }_X(a,b]=F_X(b)-F_X(a)$.

Continuous random variables: Law has a density with respect to the Lebesgue measure $\lambda$.

$${\mu }_X(B)={\int }_B{f}_X(x)\lambda (\mathrm{d}x).$$ (20)

where $f_X(x)$ is the probability density function. In particular, $F_X$ is absolutely continuous.

Singular continuous: $F_X$ is continuous but ${\mu }_X$ has no densit1y functions.

3 Expectation

3.1 Definitions

Definition 3.1 (Expectation).

Let $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$ be a probability space and $X\mathrm{:}\mathrm{\Omega }\mathrm{\to }ℝ$ be a real random variable.

The expectation $𝔼\mathit{}\mathrm{[}X\mathrm{]}$ is the real number given by the integral:

$$𝔼[X]:={\int }_{\mathrm{\Omega }}X(\omega )\mathbb{P}(\mathrm{d}\omega )={\int }_{\mathrm{\Omega }}Xd\mathbb{P}.$$ (21)

More formally, we define it using the Lebesgue integral:

$$𝔼[X]:={\int }_0^{\mathrm{\infty }}\mathbb{P}\{X>t\}\lambda (\mathrm{d}t),\mathit{\text{ when }}X\ge 0.$$ (22)

For real $X$ (not necessarily positive), if , we define $𝔼\mathit{}\mathrm{[}X\mathrm{]}\mathrm{:=}𝔼\mathit{}\mathrm{[}{X}_{\mathrm{+}}\mathrm{]}\mathrm{-}𝔼\mathit{}\mathrm{[}{X}_{\mathrm{-}}\mathrm{]}$.

Definition 3.2 (Integrable random variable.).

For a probability space $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$, we define

(23)

Note: Not all random variables are integrable, e.g., Cauchy random variables.

3.2 Change of variables

How to compute the expectation using the law? We have the change of variables proposition.

Proposition 3.3 (Law of the unconscious statistician, Lotus).

Let $X$ be a real random variable with law ${\mu }_X$. Let $h\mathrm{:}ℝ\mathrm{\to }ℝ$ be a function that is ${\mu }_X$-integrable. Then

$$𝔼[h(X)]={\int }_{ℝ}h(x){\mu }_X(\mathrm{d}x)$$ (24)

Example. If $X$ is continuous with a density $f_X$,

$$𝔼[X]={\int }_{ℝ}x\cdot {\mu }_X(\mathrm{d}x)={\int }_{ℝ}x{f}_X(x)\cdot \lambda (\mathrm{d}x)$$ (25)

Expectation is linear. $𝔼[\alpha X_1+X_2]=𝔼[\alpha X_1]+𝔼[X_2]$.

3.3 Convexity

Recall the (informal) definition of convex functions in $ℝ\to ℝ$:

$$f(\lambda x_1+(1-\lambda )x_2)\le \lambda f(x_1)+(1-\lambda )f(x_2),\forall x_1,x_2\in dom(f),dom(f)\text{ convex}.$$ (26)

Proposition 3.4 (Subgradient property).

Suppose $f\mathrm{:}{ℝ}^d\mathrm{\to }ℝ$ is a convex function. Then for all $x\mathrm{,}y\mathrm{\in }{ℝ}^d$, there exists a subgradient vector $g_x\mathrm{\in }{ℝ}^d$.

$$f(y)\ge f(x)+⟨y-x,g_x⟩.$$ (27)

Theorem 3.5 (Jensen’s inequality).

Let $f\mathrm{:}ℝ\mathrm{\to }ℝ$ convex. Assume $f$ is bounded below. Let $X$ be an integrable random variable, then

$$𝔼[f(x)]\ge f(𝔼[X]).$$ (28)

Proof Sketch..

Use the subgradient property with $x=𝔼[X]$ and the inequality should pop out directly. ∎

4 Moments and Tails

How do we collect information about the distribution of a random variable?

4.1 Definitions

Definition 4.1 (Moment).

Let $X$ be a real random variable with law ${\mu }_X$ . A moment is an integral of a real test function (${\mu }_X$-integrable) $h\mathrm{:}ℝ\mathrm{\to }ℝ$ against the law:

$$𝔼[h(X)]={\int }_{ℝ}h(x){\mu }_X(\mathrm{d}x)$$ (29)

Examples:

• Indicator $h={\mathrm{𝟙}}_B$ for Borel $B$, which gives ${\mu }_X(B)$.

• $1^{st}$ order moment, $h(x)=x$. Then $m_1=𝔼[X]={\int }_{ℝ}x{\mu }_X(\mathrm{d}x)$.

• $n$-th polynomial moment: $h(x)=x^n$ for $n\in \mathbb{N}$. $m_n=𝔼[X^n]$.

• Exponential moment: let $h(x)={\exp }^{\theta x}$. $𝔼[e^{\theta X}]$.

Definition 4.2 (Tails).

Let $X$ be a real random variable, $t\mathrm{\in }ℝ$. The (right) tail is defined as $\mathbb{P}\mathit{}\mathrm{(}X\mathrm{\ge }t\mathrm{)}$. We often refer to the tail probability $\mathbb{P}\mathit{}\mathrm{(}\mathrm{|}X\mathrm{|}\mathrm{\ge }t\mathrm{)}$.

4.2 Moments and Tail Bounds

Several theorems on tail bounds bridge a connection between moments and tails.

Theorem 4.3 (Markov’s inequality).

Let $X$ be a real random variable and $X\mathrm{\ge }\mathrm{0}$.

$$\mathbb{P}[X\ge t]\le \frac{1}{t}𝔼[X],\forall t>0.$$ (30)

Remark. For positive, increasing $\phi :{ℝ}_{+}={ℝ}_{+}$, we have

$$\mathbb{P}\{X\ge t\}\le \frac{1}{\phi (t)}𝔼[\phi (X)],\forall t>0.$$ (31)

We can use $\phi (x)=x^p$ to introduce higher-order information of $X$ to the tail bound. $\phi (x)={\exp }^{cx}$ sometimes yields a tighter tail bound of exponential decay, i.e., Chernoff bound.

In other words, polynomial moments control tail probabilities.

Theorem 4.4 (Integral by parts).

Let $X$ be a positive real random variable and $\phi \mathrm{:}{ℝ}_{\mathrm{+}}\mathrm{\to }ℝ$ be an increasing and continuously differentiable function. Then,

$$𝔼[\phi (X)]=\phi (0)+{\int }_0^{\mathrm{\infty }}\mathbb{P}\{X\ge t\}{\phi }^{\prime }(t)dt.$$ (32)

Remark.

• When $\phi (x)=x^q$ for some $q>0$, then

  $$𝔼[{|X|}^q]={\int }_0^{\mathrm{\infty }}\mathbb{P}\{|X|\ge t\}\cdot q\cdot t^{q-1}dt.$$ (33)

This means tail probability controls moments.

Assume $X$ is a real random variable with $\mathbb{P}\{|X|\ge t\}=O(t^{-p})$ for some $p\ge 1$. Then we can bound the $q$-th moment for .

$𝔼{|X|}^q$ $={\displaystyle {\int }_0^{\mathrm{\infty }}}\mathbb{P}\{|X|\ge t\}q{t}^{q-1}dt$ (34)

$={\displaystyle {\int }_0^1}\mathbb{P}\{|X|\ge t\}q{t}^{q-1}dt+{\displaystyle {\int }_1^{\mathrm{\infty }}}\mathbb{P}\{|X|\ge t\}q{t}^{q-1}dt$ (35)

$\le {\displaystyle {\int }_0^1}q{t}^{q-1}dt+{\displaystyle {\int }_1^{\mathrm{\infty }}}Cq{t}^{q-p-1}dt$ (36)

(37)

5 $L_p$ Spaces

Definition 5.1 ($L_p$ space).

For $p\mathrm{>}\mathrm{0}$, the space $L_p\mathrm{:=}{L}_p\mathit{}\mathrm{\{}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{\}}$ is

(38)

Roughly, random variables with tail decay rate at least $t_{\mathrm{-}p}$. These random variables are called “$p$-integrable random variables”.

Remarks. $L_p$ is a linear space.

Definition 5.2 (Homogeneous p-th moment.).

For $p\mathrm{>}\mathrm{0}$, we define the homogeneous p-th moment of $X$ by

$${\Vert X\Vert }_p:={(𝔼{|X|}^p)}^{1/p}$$ (39)

Sometimes denoted as ${\mathrm{\Vert }X\mathrm{\Vert }}_{L_p}$.

Theorem 5.3 (Lyapunov inequality).

For , real random variables $X$ have

$${\Vert X\Vert }_p\le {\Vert X\Vert }_q.$$ (40)

Therefore,

$${\Vert X\Vert }_q\subseteq {\Vert X\Vert }_p.$$ (41)

Proof Sketch..

Use Jensor’s inequality for $\phi (t)={|t|}^{q/p}$. ∎

Warning. For sequence spaces, ${\mathrm{\ell }}_p\subseteq {\mathrm{\ell }}_q$. For Lebesgue spaces ${ℒ}_p(ℝ)\not\subset {ℒ}_q(ℝ)$.

5.1 Pseudonorm

Question: Is $\parallel \cdot {\parallel }_{L_p}$ a norm? We would need to prove the triangular inequality.

Theorem 5.4 (H$\ddot{\mathrm{o}}$lder’s inequality).

Let $X\mathrm{,}Y$ be real random variables with $X\mathrm{\in }{L}_p\mathrm{,}Y\mathrm{\in }{L}_q$ with $\frac{\mathrm{1}}{p}\mathrm{+}\frac{\mathrm{1}}{q}\mathrm{=}\mathrm{1}$,$p\mathrm{,}q\mathrm{>}\mathrm{1}$.

$${\Vert XY\Vert }_1\le {\Vert X\Vert }_p{\Vert Y\Vert }_q.$$ (42)

Proof.

We use a lemma called Young’s inequality. If $\frac{1}{p}+\frac{1}{q}=1,p>1$, then $|xy|\le \frac{1}{p}{|x|}^p+\frac{1}{q}{|y|}^q$. We consider $X/{\Vert X\Vert }_p$ and $Y/{\Vert Y\Vert }_q$, and take expectation. ∎

Theorem 5.5 (Minkowski).

Assume $p\mathrm{\ge }\mathrm{1}$. Let $X\mathrm{,}Y\mathrm{\in }{L}_p$. Then

$${\Vert X+Y\Vert }_p\le {\Vert X\Vert }_p+{\Vert Y\Vert }_p.$$ (43)

Proof.

$${|X+Y|}^p=|X+Y|\cdot {|X+Y|}^{p-1}\le |X|\cdot {|X+Y|}^{p-1}+|Y|\cdot {|X+Y|}^{p-1}.$$ (44)

Apply Holden with $\frac{1}{p}+\frac{p-1}{p}=1$.

$$𝔼{|X+Y|}^p\le {(𝔼{|X|}^p)}^{1/p}{(𝔼{|X+Y|}^p)}^{\frac{p-1}{p}}+{(𝔼{|Y|}^p)}^{1/p}(𝔼{({|X+Y|}^p)}^{p-1/p})$$ (45)

After dividing $𝔼{|X+Y|}^{p-1}$, the triangular inequality pops out. ∎

Proposition 5.6 ($L_p$ pseudonorm).

For random variables in $L_p$, $\mathrm{\parallel }\mathrm{\cdot }{\mathrm{\parallel }}_p$ is a pseudonorm

• Positive semi-definite: ${\Vert X\Vert }_p\ge 0$ and ${\Vert 0\Vert }_p=0$.

• Positive homogeneous: $\Vert \alpha X\Vert =|\alpha |\cdot {\Vert X\Vert }_p$.

• Triangle inequality: ${\Vert X+Y\Vert }_p\le {\Vert X\Vert }_p+{\Vert Y\Vert }_p$.

• Almost positive: ${\Vert X\Vert }_p=0$ implies $X=0$ $\mu$-almost sure.

We can thus define a pseudometric on $L_p$:

$$D(X,Y):={\Vert X-Y\Vert }_p,\forall X,Y\in L_p.$$ (46)

5.2 Convergence in $L_p$

Definition 5.7.

A sequence $\mathrm{(}{X}_j\mathrm{:}j\mathrm{\in }\mathbb{N}\mathrm{)}$ in $L_p$ converges in $L_p$ if there is a real random variable $Y\mathrm{\in }{L}_p$, such that

$${\Vert X_j-Y\Vert }_p\to 0,asj\to \mathrm{\infty }.$$ (47)

Notes. $X_j\to Y$ in $L_p$ implies $X_j\to Y$ in $L_q$ for $q\le p$.

Question: When does a sequence in $L_p$ converge?

Definition 5.8 (Cauchy sequence).

A sequence $\mathrm{(}{X}_j\mathrm{:}j\mathrm{\in }\mathbb{N}\mathrm{)}$ in $L_p$ is called Cauchy if

$$\underset{i,j\ge N}{sup}{\Vert X_i-X_j\Vert }_p\to 0asN\to \mathrm{\infty }.$$ (48)

It is trivial that any converging sequence is Cauchy, but the other direction is not trivial.

Theorem 5.9 ($L_p$ space is complete.).

Every Cauchy sequence in $L_p$ converges to a random variable. Moreover, it converges to a random variable in $L_p$.

Notes. An example of non-complete space: $\mathbb{Q}$. A sequence of rational numbers may converge to an irrational number.

Remark. Limits in $L_p$ are not necessarily unique! They are only required to be equal $\mu$-almost surely.

5.3 $L_2$ Space

Next, we restrict our discussion to $L_2$ space, which is special for setting orthogonality, variance, covariance, and orthogonal projection.

(49)

Theorem 5.10 (Cauchy-Schwarz).

If $X\mathrm{,}Y\mathrm{\in }{L}_{\mathrm{2}}$, then $X\mathit{}Y\mathrm{\in }{L}_{\mathrm{1}}$, and

$$|𝔼[XY]|\le {\Vert XY\Vert }_1\le {\Vert X\Vert }_2\cdot \Vert Y_2\Vert .$$ (50)

This is a special case of H$\ddot{\mathrm{o}}$lder’s theorem when $p=q=2$. Nevertheless, here is another simpler proof

Proof.

Let $t\in ℝ$.

$$0\le 𝔼{(t|X|+|Y|)}^2=𝔼{|X|}^2{t}^2+2t𝔼|XY|+𝔼{|Y|}^2,$$ (51)

which is a quadratic function of $t$. Hence $4{(E|XY|)}^2-4𝔼{|X|}^2𝔼{|Y|}^2\le 0$. ∎

Definition 5.11 ($L_2$ (pseudo)-inner product).

For random variables $X\mathrm{,}Y\mathrm{\in }{L}_{\mathrm{2}}$, we define

$${⟨X,Y⟩}_{L_2}:=𝔼[XY].$$ (52)

Remarks.

• This is well-defined by Cauchy-Schwarz.

• $⟨X,X⟩=𝔼[{|X|}^2]={\Vert X\Vert }_{L_2}^2$.

Definition 5.12 (Orthogonality).

If $\mathrm{⟨}X\mathrm{,}Y\mathrm{⟩}\mathrm{=}\mathrm{0}$, then we say $X$ and $Y$ are orthogonal random variables, and we write $X\mathrm{⟂}Y$.

Warning: $X⟂Y$ does NOT imply that $X,Y$ are ”independent”.

Definition 5.13 (Covariance).

Let $X\mathrm{,}Y\mathrm{\in }{L}_{\mathrm{2}}$, the covariance of $X\mathrm{,}Y$ is

$$Cov(X,Y):=⟨X-𝔼X,Y-𝔼Y⟩.$$ (53)

If $C\mathit{}o\mathit{}v\mathit{}\mathrm{(}X\mathrm{,}Y\mathrm{)}\mathrm{=}\mathrm{0}$, we say $X\mathrm{,}Y$ are uncorrelated, not necessarily independent!

Moreover, we define the variance of a random variable $X\mathrm{\in }{L}_{\mathrm{2}}$ by $V\mathit{}a\mathit{}r\mathit{}\mathrm{(}X\mathrm{)}\mathrm{:=}C\mathit{}o\mathit{}v\mathit{}\mathrm{(}X\mathrm{,}X\mathrm{)}$.

The correlation of $X\mathrm{,}Y$ is defined by

$$\rho (X,Y):=\frac{Cov(X,Y)}{\sqrt{Var(X)\cdot Var(Y)}}\in [-1,1]$$ (54)

Proposition 5.14 (Pythagorean).

If $X\mathrm{,}Y\mathrm{\in }{L}_{\mathrm{2}}$, then $C\mathit{}o\mathit{}v\mathit{}\mathrm{(}X\mathrm{,}Y\mathrm{)}\mathrm{=}\mathrm{0}$ implies

$$Var(X,Y)=Var(X)+Var(Y).$$ (55)

Theorem 5.15 (Orthogonal projection).

Let $K\mathrm{\subseteq }{L}_{\mathrm{2}}$ be a complete linear subspace of $L_{\mathrm{2}}\mathit{}\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$.

For $X\mathrm{\in }{L}_{\mathrm{2}}$, there is a random variable $Y\mathrm{\in }K$ such that

• Primal: $\parallel X-Y{\parallel }_2=inf\{\parallel X-w{\parallel }_2:w\in K\}$.

• Dual: $(X-Y)⟂Z$ for all $Z\in K$.

These two statements are essentially the same. We call $Y$ a version of the orthogonal projection of $X$ onto $K$.

Remark. Such $Y$ are not unique. We can have $Y=Y^{\prime }$ almost surely.

Proof.

Consider a minimizing sequence in $K$: $(Y_i\in K:I\in \mathbb{N})$, such that ${\Vert Y_i-X\Vert }_2$ is decreasing and converges to $d:=inf\{\parallel w-X{\parallel }^2:w\in K\}$.

Step 1: Show that $(Y_i)$ has a limit in $K$, which is a candidate for the projection. Check that the sequence $(Y_i)$ is Cauchy.

$$0\le {\Vert \frac{1}{2}(Y_i-Y_j)\Vert }^2=\frac{1}{2}{\Vert Y_i-X\Vert }^2+\frac{1}{2}{\Vert Y_j-X\Vert }^2-{\Vert \frac{1}{2}(Y_i+Y_j)-X\Vert }^2\le d^2+(-d^2)=0.$$ (56)

So $Y_i$ is Cauchy in $K$. Since $K$ is complete, we know $Y_i\to Y$ for some $Y\in K$. $Y$ is a candidate for the orthogonal projection of $X$ onto $K$.

Step 2: Check that $Y$ is indeed an orthogonal projection. By Minkowski, for each i

$${\Vert X-Y\Vert }_2\le {\Vert X-Y_i\Vert }_2+{\Vert Y_i-Y\Vert }_2,$$ (57)

which converges to $d$. Moreover, ${\Vert X-Y\Vert }_2\ge d$, so ${\Vert X-Y\Vert }_2=d$.

Step 3: Dual characterization. For $Z\in K$, let $t\in ℝ$, $Y+tZ\in K$ since $K$ is a linear subspace. Then

$${\Vert X-(Y+tZ)\Vert }^2\ge {\Vert X-Y\Vert }^2$$ (58)

Expand the equation and it’s trivial to see we must have $⟨X-Y,Z⟩=0$. ∎

6 Independence

Let $(\mathrm{\Omega },ℱ,\mathbb{P})$ be a probability space. How to update our knowledge about an event $A$, when another event $E$ has occurred?

$$\mathbb{P}(A|E):=\frac{\mathbb{P}(A\cap E)}{\mathbb{P}(E)}$$ (59)

We define ${ℱ|}_E$ the $\sigma$-algebra $\{A\cap E|A\in ℱ\}$.

Then $(E,ℱ{|}_E,\mathbb{P}(\cdot |E))$ is a probability measure space.

Definition 6.1 (Independence of events).

Suppose knowledge that $E$ occurs does not change the probability of $A$:

$$\mathbb{P}(A|E)=\mathbb{P}(A)$$ (60)

Then we call events $A$ and $E$ are independent. It is equivalent to saying

$$\mathbb{P}(A\cap E)=\mathbb{P}(A)\cdot \mathbb{P}(E).$$ (61)

6.1 Independent for random variables

How about random variables being independent? Random variables can take any value in their domain, so we must consider a series of events to be independent.

Definition 6.2 (Independence of random variables).

Let $X\mathrm{,}Y$ be real random variables. We say that $\mathrm{(}X\mathrm{,}Y\mathrm{)}$ are independent when

$$\mathbb{P}\{X\in A\cap Y\in B\}=\mathbb{P}\{X\in A\}\cdot \mathbb{P}\{X\in B\},$$ (62)

for all $A\mathrm{,}B\mathrm{\in }ℬ\mathit{}\mathrm{(}ℝ\mathrm{)}$.

In particular, for all $a,b\in ℝ$, it is common to see the definition below,

$$\mathbb{P}\{X\le a\wedge Y\le b\}=\mathbb{P}\{X\le a\}\cdot \mathbb{P}\{Y\le b\}.$$ (63)

Fact: These two definitions are equivalent.

This is also equivalent to

$${\mu }_{XY}(A\times B)={\mu }_X(A)\cdot {\mu }_X(B),\forall A,B\in ℬ(ℝ).$$ (64)

Moreover, it is equivalent to ${\mu }_{XY}={\mu }_X\times {\mu }_Y$ on $ℬ({ℝ}^2)$.

Proposition 6.3.

Let $X\mathrm{,}Y$ be independent real random variables. Let $f\mathrm{\in }{L}_{\mathrm{1}}\mathit{}\mathrm{(}{\mu }_X\mathrm{)}$ and $g\mathrm{\in }{L}_{\mathrm{1}}\mathit{}\mathrm{(}{\mu }_Y\mathrm{)}$. Then

$$𝔼[f(X)\cdot g(Y)]=𝔼[f(X)]\cdot 𝔼[g(Y)].$$ (65)

Proof.

$𝔼[f(X)\cdot g(Y)]$ $={\displaystyle {\int }_{{ℝ}^2}}f(x)g(y){\mu }_{XY}(\mathrm{d}x\mathrm{d}y)$ (66)

$={\displaystyle {\int }_{{ℝ}^2}}f(x)g(y){\mu }_X(\mathrm{d}x){\mu }_Y(\mathrm{d}y)$ (67)

$={\displaystyle {\int }_{ℝ}}f(x){\mu }_X(\mathrm{d}x){\displaystyle {\int }_{ℝ}}g(y){\mu }_Y(\mathrm{d}y)=𝔼[f(X)]𝔼[g(Y)].$ (68)

∎

Question: Can we generate a collection of random variables with specified marginals? For a countable sequence, the answer is yes!

Theorem 6.4 (Kolmogorov extension).

Let $\mathrm{(}{\mu }_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ be a collection of Borel probability measures on $ℝ$. Define

$$\mathrm{\Omega }={ℝ}^{\mathbb{N}}=\{\omega =({\omega }_1,{\omega }_2,\mathrm{\dots },):{\omega }_i\in ℝ,i\in \mathbb{N}\}.$$ (69)

Consider coordinate random variables $X_i\mathit{}\mathrm{(}\omega \mathrm{)}\mathrm{=}{\omega }_i$.

We can define product $\sigma$-algebra:

$$ℱ=\sigma (X_i:i\in \mathbb{N})=\mathit{\text{ smallest sigma algebra that have coordinate rvs measurable.}}$$ (70)

There exists a product probability measure $\mathbb{P}$ in $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{)}$, such that

$$\mathbb{P}\{(x_1,x_2,\mathrm{\dots })\in B_1\times B_2\times \mathrm{\dots }\}=\prod _{i\in \mathbb{N}}\mathbb{P}(X_i\in B_i)=\prod _{i\in \mathbb{N}}{\mu }_i(B_i).$$ (71)

6.2 Independence for sigma-algebras

Note that $\sigma$-algebras carry information. We can also define the independence of $\sigma$-algebras.

Definition 6.5 (Independence of $\sigma$-algebra).

Let $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$ be a probability space. Let ${ℱ}_{\mathrm{1}}\mathrm{,}{ℱ}_{\mathrm{2}}$ be sub-$\sigma$-algebra of $ℱ$.

We say that ${ℱ}_{\mathrm{1}}\mathrm{,}{ℱ}_{\mathrm{2}}$ are independent if for all $E_{\mathrm{1}}\mathrm{\in }{ℱ}_{\mathrm{1}}$ and $E_{\mathrm{2}}\mathrm{\in }{ℱ}_{\mathrm{2}}$,

$$\mathbb{P}(E_1\cap E_2)=\mathbb{P}(E_1)\cdot \mathbb{P}(E_2).$$ (72)

For events $A,B$.$\sigma (\{A\})=\{\mathrm{\varnothing },A,A^C,\mathrm{\Omega }\}$. We can check that $A$ and $B$ are independent if and only if $\sigma (\{A\})$ and $\sigma (\{B\})$ are independent $\sigma$-algebras.

For real random variables: $\sigma (X):=\sigma (\{X^{-1}(B),B\in ℬ(ℝ)\})$. Then real random variables $X,Y$ are independent if and only if $\sigma (X)$,$\sigma (Y)$ are independent $\sigma$-algebras.

7 Law of Large Numbers

Definition 7.1 (Stochastic process).

Let $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$ be a probability space. A stochastic or random process is a family $\mathrm{(}{X}_t\mathrm{:}t\mathrm{\in }T\mathrm{)}$ of real random variables, indexed by an abstract set $T$.

• Discrete time: $T=\mathbb{N}$.

• Continuous time: $T={ℝ}_{\ge 0}$.

• Space: $T={ℝ}^n$, ”random fields”.

Key models covered in this note: Independent sum; discrete-time martingales.

Definition 7.2 (Independent sum).

Let $\mathrm{(}{Y}_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ be an independent sequence of real random variables.

The partial sums:

$$X_n:=\sum _{i=1}^m{Y}_i$$ (73)

compose a discrete-time $\mathrm{(}T\mathrm{=}{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ random process, called an independent sum process.

Examples.

• Repeated independent experiments.

• Random walk.

• Renewal processes.

Definition 7.3 (Running average process).

Let $\mathrm{(}{Y}_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ be independent real random variables. ${\overline{X}}_n\mathrm{=}\frac{\mathrm{1}}{n}\mathit{}{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^n{Y}_u$ is called the running average process.

$𝔼[{\overline{X}}_n]=𝔼[Y]$ (74)

$Var({\overline{X}}_n)={\displaystyle \frac{1}{n}}Var[Y].$ (75)

7.1 Weak Law of Large Numbers

Definition 7.4 (Convergence in probability).

A sequence $\mathrm{(}{W}_n\mathrm{:}n\mathrm{\in }\mathbb{N}\mathrm{)}$ of real random variables converges in probability to a random variable $W$, if

$$\underset{t>0}{sup}\underset{n\to \mathrm{\infty }}{lim}\mathbb{P}\{|W_n-W|\ge t\}=0,\forall t>0.$$ (76)

Theorem 7.5 (Chebyshev’s weak LLN).

Let $Y\mathrm{\in }{L}_{\mathrm{2}}$ be a real random variable and $\mathrm{(}{Y}_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ are iid copies of $Y$. Let ${\overline{X}}_n\mathrm{=}{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^n{Y}_i$. Then

$${\overline{X}}_n\to 𝔼Y\mathit{\text{in probability}}\mathbb{P}$$ (77)

7.2 Strong Law of Large Numbers

Definition 7.6 (A.s. Convergence).

Consider a sequence $\mathrm{(}{W}_n\mathrm{:}n\mathrm{\in }\mathbb{N}\mathrm{)}$ of real random variables. We say that $W_n\mathrm{\to }W$ almost surely, if when $n\mathrm{\to }\mathrm{\infty }$,

$$\mathbb{P}\{w\in \mathrm{\Omega }:W_n(\omega )\to w(\omega )\}=1.$$ (78)

Equivalently,

$$\mathbb{P}\{lim\underset{n\to \mathrm{\infty }}{sup}|W_n\to W|>0\}=0.$$ (79)

Remark.

$$W_n\to W\text{point-wise}⟹W_n\to Wa.s.⟹W_n\to W\text{ in}\mathbb{P}.$$ (80)

Theorem 7.7 (Kolmogorov Strong LLN).

Let $Y\mathrm{\in }{L}_{\mathrm{1}}$ be a real random variable. Let $\mathrm{(}{Y}_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ be iid copies of $Y$. Let ${\overline{X}}_n\mathrm{=}\frac{\mathrm{1}}{n}\mathit{}{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^n{Y}_i$. Then ${\overline{X}}_n\mathrm{\to }𝔼\mathit{}Y$ a.s. That is,

$$\mathbb{P}\{{\overline{X}}_n\to 𝔼Y\}=1.$$ (81)

Theorem 7.8 (Cantelli Strong LLN).

Assume $Y\mathrm{\in }{L}_{\mathrm{4}}$. Then the previous theorem has a simpler proof $\mathrm{:}\mathrm{)}$

Proof.

WLOG, assume $𝔼Y=0$.

Lemma 1 (Borel Cantelli.).

Let $\mathrm{(}{A}_n\mathrm{:}n\mathrm{\in }\mathbb{N}\mathrm{)}$ be events.

(82)

Proof of the lemma..

$$lim\underset{n\to \mathrm{\infty }}{sup}{A}_n=\bigcap _{n=1}^{\mathrm{\infty }}\bigcup _{i\ge n}{A}_i=\text{event that}{A}_i\text{ happens infinite times}$$ (83)

$\mathbb{P}(lim\underset{n\to \mathrm{\infty }}{sup}{A}_n)$ $\le \mathbb{P}({\displaystyle \bigcup _{i\ge n}}{A}_i),\forall n$ (84)

$\le {\displaystyle \sum _{i\ge n}}\mathbb{P}(A_i)=0,\text{as}n\to \mathrm{\infty }.$ (85)

∎

Lemma 2 (Cartelli tail bound.).

Assume $𝔼\mathit{}Y\mathrm{=}\mathrm{0}$, $\mu \mathrm{=}𝔼\mathit{}{\mathrm{|}Y\mathrm{|}}^{\mathrm{4}}$. Then $\mathrm{\forall }n\mathrm{\in }\mathbb{N}$,

$$\mathbb{P}\{|{\overline{X}}_n|\ge n^{-1/8}\}\le 3\mu n^{-3/2}.$$ (86)

Cont. Define event $A_n=\{\omega \in \mathrm{\Omega }:|{\overline{X}}_n(\omega )|\ge n^{-1/8}\}$. Then

(87)

Then using the Borel-Cantelli lemma.

$$\mathbb{P}\{lim\underset{n\to \mathrm{\infty }}{sup}|X_n|>0\}=0.$$ (88)

∎

7.3 Concentration

The law of large numbers gives an asymptotic analysis for the limit of $X_n=\frac{1}{n}{\sum }_{i=1}^n{Y}_i$. However, we also want nonasymptotic analysis for a fixed $n$.

Proposition 7.9 (Chebyshev).

Let $X\mathrm{\in }{L}_{\mathrm{2}}$, and $\sigma \mathrm{=}\sqrt{V\mathit{}a\mathit{}r\mathit{}\mathrm{(}X\mathrm{)}}$,

$$\mathbb{P}\{|X-𝔼X|\ge \sigma t\}\le \frac{1}{t^2},\forall t>0.$$ (89)

• Chebyshev’s inequality gives weak controls on tail bound ($t^{-2}$), but this is the best we could get by assuming $X\in L_2$ only.

Definition 7.10 (Moment generating function (mgf) and cumulant generating function (cgf)).

Let $X$ be a real random variable. The moment generating function is defined as

$$m_X(\theta ):=𝔼[e^{\theta X}],$$ (90)

and the cumulant generating function

$${\xi }_X(\theta ):=\log 𝔼[e^{\theta X}].$$ (91)

Proposition 7.11 (Laplace transform method).

Let $X$ be a real random variable. For all $t\mathrm{\in }ℝ$,

$$\mathbb{P}\{X\ge t\}\le \underset{\theta >0}{inf}\exp \left(-\theta t+{\xi }_X(\theta )\right)$$ (92)

(93)

Proof Sketch..

Simply apply Markov’s inequality to $\exp \left(\theta X\right)$. ∎

Example. (Normal distribution) Recall that for $Z\sim 𝒩(0,{\sigma }^2)$, we have ${\xi }_Z(\theta )=\frac{{\sigma }^2{\theta }^2}{2}$. Then

$$𝔼\{Z\ge t\}\le \underset{\theta >0}{inf}\exp \left(-\theta t+{\sigma }^2{\theta }^2/2\right)=\exp \left(-t^2/2{\sigma }^2\right).$$ (94)

Proposition 7.12 (Additivity of cgf).

Let $X\mathrm{=}{\mathrm{\sum }}_i{Y}_i$ for independent random variables $Y_i$, then

$${\xi }_X(\theta )=\sum _i{\xi }_{Y_i}(\theta ).$$ (95)

Thanks to the additivity of cgf, we can easily derive a tail bound for independent sums,

Theorem 7.13.

Let $X\mathrm{=}{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^n{Y}_i$ for independent $Y_i$.

$\mathbb{P}\{X\ge t\}\le \underset{\theta >0}{inf}\exp \left(-\theta t+{\displaystyle \sum _{i=1}^n}{\xi }_{Y_i}(\theta )\right)$ (96)

(97)

Example. (Binomial) Let $X\sim Binomial(n,p)$, so $X={\sum }_{i=1}^n{Y}_i$ where $Y_i\sim Bern(p)$ iid.

$${\xi }_{Y_i}(\theta )\le p(e^{\theta }-1).$$ (98)

So we get (the Chernoff bound)

$$\mathbb{P}\{X\ge t𝔼[X]\}\le \underset{\theta >0}{inf}\exp \left(-np(\theta t-e^{\theta }+1)\right)=\exp \left(-np(t\log t-t+1)\right)={\left(\frac{e^{t-1}}{t^t}\right)}^{np}.$$ (99)

Theorem 7.14 (Hoeffding’s theorem).

For $X\mathrm{=}{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^n{Y}_i$ for independent bounded random variables $Y_i\mathrm{\in }\mathrm{[}{a}_i\mathrm{,}{b}_i\mathrm{]}$. Let $\sigma \mathrm{=}\sqrt{{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^n{\mathrm{(}{b}_i\mathrm{-}{a}_i\mathrm{)}}^{\mathrm{2}}}\mathrm{/}\mathrm{2}$. Then

$$\mathbb{P}\{|X-𝔼X|\ge \sigma t\}\le 2\exp \left(-t^2/2\right)$$ (100)

Proof.

We need a cgf bound for $Y_i$. We find that ${\xi }_{Y_i}(\theta )\le {(b_i-a_i)}^2{\theta }^2/8$. This is because

$m_{Y_i}(\theta )$ $=𝔼[e^{\theta Y}]$ (101)

$\le 𝔼[f(x)]=\cosh \left(\theta {\displaystyle \frac{b-a}{2}}\right)$ (102)

where $f(x)=\frac{(e^{\theta b}-e^{\theta a})(x-a)}{2(b-a)}+e^{-\theta a}$ so on $[a,b]$. Plug in ${\xi }_{Y_i}=\log m_{Y_i}$ proves the theorem. ∎

7.4 Weak convergence

Limit theorems in probability tell us when a sequence of random variables converges to a limiting random variable. In this section, we consider describing when the distributions of the random variables converge to a limiting distribution.

What does it mean for the distributions of random variables to converge?

Idea: Moments carry information about distributions.

$$\mu (h)={\int }_{ℝ}h(x)\mu (\mathrm{d}x)$$ (103)

If two measures $\mu ,\nu$ are close, then many moments are similar: $\mu (h)\approx \nu (h)$ for “many” $h$.

Definition 7.15.

A function $h\mathrm{:}ℝ\mathrm{\to }ℝ$ is bounded Lipschitz, if

(104)

where

$$\parallel h{\parallel }_{sup}=sup\{|h(x)|:x\in ℝ\}$$ (105)

and

$${\Vert h\Vert }_{Lip}=\underset{L>0:|h(x)-h(y)|\le L|x-y|,\forall x,y\in ℝ}{inf}$$ (106)

Remark. $\parallel \cdot {\parallel }_{BL}$ is a norm.

Proposition 7.16 (BL functions separate measures.).

Let $\mu \mathrm{,}\nu$ be Borel probability measures on $ℝ$.

Then $\mu \mathrm{=}\nu$ if and only if $\mu \mathit{}\mathrm{(}h\mathrm{)}\mathrm{=}\nu \mathit{}\mathrm{(}h\mathrm{)}$ for all bounded Lipschitz $h\mathrm{:}ℝ\mathrm{\to }ℝ$.

Proof.

The forward direction is trivial.

The reverse direction. Assume $\mu \ne \nu$, then the cdf $F_{\mu }\ne F_{\nu }$, so there exists $a\in ℝ$,

$$F_{\mu }(a)\ne F_{\nu }(a).$$ (107)

Let us consider a series of BL functions:

$$h_n(x)=\{\begin{array}{cc}1,x\le a\hfill & \\ 0,x\ge a+\frac{1}{n}\hfill & \\ 1-n(x-a),x\in (a,a+\frac{1}{n}.\hfill & \end{array}$$ (108)

Using bounded convergence theorem (or dominated convergence), $\mu (h_n)\to F_{\mu }(a)$ and $\nu (h_n)\to F_{\nu }(a)$. Therefore, there exists $n$, such that $\mu (h_n)\ne \nu (h_n)$. ∎

Definition 7.17 (Bounded Lipschitz metric).

Let $\mu \mathrm{,}\nu$ be Borel probability measures on $ℝ$. Define

$$d_{BL}(\mu ,\nu ):=sup\{|\mu (h)-\nu (h)|:\parallel h{\parallel }_{BL}\le 1\}.$$ (109)

Note: $d_{BL}$ is a metric on the probability measures on $ℝ$, i.e.,

• $d_{BL}(\mu ,\nu )=0$ if and only if $\mu =\nu$.

• $d_{BL}(\mu ,\nu )=d_{BL}(\nu ,\mu )$.

• $d_{BL}(\mu ,\nu )\le d_{BL}(\mu ,\rho )+d_{BL}(\rho ,\nu )$.

Definition 7.18 (Weak convergence).

Let $\mathrm{(}{\mu }_n\mathrm{:}n\mathrm{\in }\mathbb{N}\mathrm{)}$ be Borel probability measures on $ℝ$, $\mu$ be a Borel probability. We say $\mu$ converges weakly to $\mu$, if

$$d_{BL}({\mu }_n,\mu )\to 0\text{𝑎𝑠}n\to \mathrm{\infty }.$$ (110)

Let $\mathrm{(}{X}_n\mathrm{:}n\mathrm{\to }\mathbb{N}\mathrm{)}$ be real random variables and $X$ be a real random variable. Then we say $X_n$ weakly converges to $X$, if ${\mu }_{X_n}$ weakly converges to ${\mu }_X$.

Theorem 7.19.

Let $\mathrm{(}{\mu }_n\mathrm{:}n\mathrm{\in }\mathbb{N}\mathrm{)}$, $\mu$ be Borel probability measures on $ℝ$. The following are equivalent:

• ${\mu }_n$ weakly converges to $\mu$

• ${\mu }_n(h)\to \mu (h)$ for all bounded Lipschitz $h:ℝ\to ℝ$.

• ${\mu }_n(h)\to \mu (h)$ for all bounded continuous $h:ℝ\to ℝ$.

• The distribution function $F_{{\mu }_n}(a)$ converges to $F_{\mu }(a)$ for all $a\in ℝ$ where $F_{\mu }(a)$ us continuous.

• The characteristic function ${\chi }_{{\mu }_n}\to {\chi }_{\mu }$ point-wise, where

  $${\chi }_W(\theta )=𝔼[e^{i\theta W}]$$ (111)

Proposition 7.20.

$X_n\to 𝔼Y$ almost sure implies that $X_n$ converges weakly to $𝔼\mathit{}Y$.

Definition 7.21 (Integral probability metric).

Let $H$ be a collection of functions from $ℝ\mathrm{\to }ℝ$. Define the IPM related to $H$ by

$$d_H(\mu ,\nu )=sup\{|\mu (h)-\nu (h)|:h\in H\},$$ (112)

for all Borel probability measure $\nu$ on $ℝ$.

Remark.

• Different $H$ gives different notions of distance

• If $H\subseteq H^{\prime }$, then $d_H\le d_{H^{\prime }}$

• $d_H$ is a metric if and only if $H$ separates measures.

Examples

• Kolmogorov: $H=\{{\mathrm{𝟙}}_{(-\mathrm{\infty },a]}:a\in ℝ\}$, which induces uniform convergence of cdfs.

• Total variation: $H=\{h:ℝ\to ℝ:{\Vert h\Vert }_{sup}\le 1,h\text{continuous}\}$ or $H^{\prime }=\{{\mathrm{𝟙}}_B:B\text{Borel}\}$.

• Kantorovich Wasserstein-1 distance

  $$H=\{h:ℝ\to ℝ:{\Vert h\Vert }_{Lip}\le 1\}$$ (113)

  Convergence weakly and $L_1$.

7.5 Central Limit Theorem

Let $(Y_i:i\in \mathbb{N})$ be iid copies of $Y\in L_2$, then ${\overline{X}}_n=\frac{1}{n}{\sum }_{i=1}^n{Y}_i$ converges almost surely to $𝔼Y$.

Idea: rescale ${\overline{X}}_n$ to make its variance nontrivial. We define standardized sums

$$T_n:=\sqrt{n}\frac{{\overline{X}}_n-𝔼Y}{\sqrt{Var(Y)}}.$$ (114)

It can be checked that $𝔼T_n=0$ and $Var(T_n)=1$.

Theorem 7.22 (Central Limit Theorem).

Let $\mathrm{(}{Y}_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ be iid copies of $Y\mathrm{\in }{L}_{\mathrm{2}}$. Define

$$T_n=\sqrt{n}\left(\frac{{\overline{X}}_n-𝔼Y}{\sqrt{Var(Y)}}\right)\forall n\in \mathbb{N}.$$ (115)

Then $T_n$ weakly converges to $𝒩\mathit{}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$ as $n\mathrm{\to }\mathrm{\infty }$.

Remark.

• Historically, the central limit theorem is used to support asymptotic confidence intervals for $𝔼Y$.

• Equivalent statements:

  $$d_{BL}(T_n,Z)=\underset{{\Vert h\Vert }_{BL}\le 1}{sup}|𝔼h(T_n)-𝔼h(Z)|\to \mathrm{\infty }.$$ (116)

  Also equivalent to

  $$\mathbb{P}\{T_n\le a\}=F_{T_n}(a)\to \mathrm{\Phi }(a),\forall a\in ℝ,$$ (117)

  which is often called the convergence in distribution.

7.6 Nonasymptotic counterpart

Theorem 7.23 (Berry-Esseen).

Let $\mathrm{(}{Y}_i\mathrm{:}i\mathrm{\in }\mathbb{N}\mathrm{)}$ be iid copies of $Y\mathrm{\in }{L}_{\mathrm{3}}$. Define

$${\sigma }^2=Var(Y),\text{𝑎𝑛𝑑}{M}_3=𝔼{|Y-𝔼Y|}^3.$$ (118)

Let $Y_n$ be the standardized sum, then the Kolmogorov distance

$$d_{Kol}(T_n,Z):=\underset{a\in ℝ}{sup}|F_{T_n}(a)-\mathrm{\Phi }(a)|\le \frac{M_3}{\sqrt{n}{\sigma }^3},\forall n\in \mathbb{N}.$$ (119)

Proof of a weaker version by the Lindeberg exchange principle..

The idea is to show for smooth functions $h:ℝ\to ℝ$,

$$𝔼h(T_n)=𝔼h(Z),\text{by Taylor expansion.}$$ (120)

Lemma 3.

Let $\mathrm{(}Y\mathrm{,}Z\mathrm{)}$ be $L_{\mathrm{3}}$ random variables with $𝔼\mathit{}Y\mathrm{=}𝔼\mathit{}Z$ and $𝔼\mathit{}{Y}^{\mathrm{2}}\mathrm{=}𝔼\mathit{}{Z}^{\mathrm{2}}$. Let $h\mathrm{:}ℝ\mathrm{\to }ℝ$ with .

$$\Vert 𝔼h(Y)-𝔼h(Z)\Vert \le \frac{1}{6}{\Vert h^{(3)}\Vert }_{sup}(𝔼{|Y|}^3+𝔼{|Z|}^3).$$ (121)

Proof of Lemma..

$$h(t)-h(0)-t{h}^{\prime }(0)-\frac{t^2}{2}{h}^{\prime \prime }(0)=\frac{t^3}{6}{h}^{(3)}(\xi ),\text{for some}\xi \in [0,t].$$ (122)

Then

$$\left|𝔼[h(Y)-h(0)-Y{h}^{\prime }(0)-\frac{1}{2}{Y}^2{h}^{\prime \prime }(0)]\right|\le \frac{1}{6}𝔼|Y^3|{\Vert h^{(3)}\Vert }_{sup}.$$ (123)

The left hand side is1 the same for $Y$ and $Z$, except for the first term, so

$$|𝔼h(Y)-𝔼h(Z)|\le \frac{1}{6}{\Vert h^{(3)}\Vert }_{sup}\cdot (𝔼{|Y|}^3+𝔼{|Z|}^3).$$ (124)

∎

Let $Y_1,\mathrm{\dots }{Y}_n$ and $Z_1,\mathrm{\dots },Z_n$ be independent with $𝔼Y_i=𝔼Z_i$ and $𝔼Y_i^2=𝔼Z_i^2$. For $f:{ℝ}^n\to ℝ$, such that , then

$$|𝔼f(Y_1,\mathrm{\dots },Y_n)-𝔼f(Z_1,\mathrm{\dots },Z_n)|\le \frac{1}{6}\sum _{i=1}^n{\Vert {\partial }_{iii}f\Vert }_{sup}(𝔼{|Y_i|}^3+𝔼{|Z_i|}^3).$$ (125)

This is called the Lindeberg exchange theorem. To see this, let

$$W_i=(Y_1,\mathrm{\dots },Y_i,Z_{i+1},\mathrm{\dots },Z_n).$$ (126)

Then since $W_0=(Z_1,\mathrm{\dots },Z_n)$ and $W_n=(Y_1,\mathrm{\dots },Y_n)$,

$$|𝔼f(Y)-𝔼f(Z)|\le \sum _{i=1}^n|𝔼f(W_i)-𝔼f(W_{i+1})|\le \frac{1}{6}\sum _{i=1}^n{\Vert {\partial }_{iii}f\Vert }_{sup}(𝔼{|Y_i|}^3+𝔼{|Z_i|}^3).$$ (127)

Let $Y_i\sim Y$, $Z_i\sim Z$ in $L_3$ be independent random variables that are already standardized, i.e., $𝔼Y=\mathbb{Z}=0$ and $Var(Y)=Var(Z)=1$. Let . Let $h:ℝ\to ℝ$ be smooth. Define

$$f(X_1,\mathrm{\dots },X_n)=h(\frac{1}{\sqrt{n}}\sum _{i=1}^n{X}_i),\text{where}X\text{means}Y,Z.$$ (128)

${\Vert {\partial }_{iii}f\Vert }_{sup}\le n^{-3/2}{\Vert h^{(3)}\Vert }_{sup}$. Then applying the Lindeberg exchange principle,

$$|𝔼h(\frac{1}{\sqrt{n}}\sum _{i=1}^n{Y}_i)-𝔼h(\frac{1}{\sqrt{n}}\sum _{i=1}^n{Z}_i)|\le \frac{M}{3\sqrt{n}}{\Vert h^{(3)}\Vert }_{sup}.$$ (129)

Let

$$H=\{h:ℝ\to ℝ,{\Vert h^{(3)}\Vert }_{sup}\le 1\}$$ (130)

$$d_H(\frac{1}{\sqrt{n}}\sum _i{Y}_i,\frac{1}{n}\sum _i{Z}_i)\le \frac{M}{3\sqrt{n}}.$$ (131)

∎

Issues:

• Where is the normal random variable?

  Solution: Choose $Z_i\sim 𝒩(0,1)$, then we can compute $\frac{1}{\sqrt{n}}{\sum }_{i=1}^n{Z}_i\sim 𝒩(0,1)$.

• What is $d_H$?

  Solution: For each $h:ℝ\to ℝ$ with ${\Vert h\Vert }_{BL}\le 1$, we can smooth $h$ to get a function $h_{\sigma }$ such that ${\Vert h_{\sigma }^{(3)}\Vert }_{sup}$ is bounded and ${\Vert h-h_{\sigma }\Vert }_{sup}$ is bounded, which implies

  $$d_{BL}(T_n,Y)\le \frac{C𝔼{({|Y|}^3)}^{1/3}}{n^{1/6}}\to \mathrm{\infty },\text{as}n\to \mathrm{\infty }.$$ (132)

8 Conditional Expectation

If two random variables are dependent, by observing one, we can update our knowledge about probabilities of events involving the other. In particular, we can update our “best guess” for the expectation.

Fix a probability space $(\mathrm{\Omega },ℱ,\mathbb{P}).$ Let $X\in L_2(\mathrm{\Omega }.ℱ,\mathbb{P})$.

Recall that $Var(X)=𝔼[{(X-𝔼X)}^2]={inf}_{a\in ℝ}{\Vert X-a\Vert }^2$.

8.1 Conditional expectation in least squares

Consider a subspace in $L_2$:

$$K_0=\{Y\in L_2(\mathrm{\Omega },ℱ,\mathbb{P}):Y(\omega )=a,\forall \omega \in \mathrm{\Omega },a\in ℝ\}.$$ (133)

$K_0$ is a complete subspace in $L_2$, so there is always a projection from $L_2$ to $K_0$, i.e.,

$$Y^{*}=\arg \underset{Y\in K_0}{\min }𝔼{(X-Y)}^2$$ (134)

Now suppose we observe a random variable $Z\in L_2$ and want to update our best guess of $𝔼X$. We first try an affine approximation:

$$\underset{Y}{\min }{\Vert X-Y\Vert }_2,$$ (135)

where $Y\in K_1$.

$$K_1=\{a+bZ:a,b\in ℝ\}.$$ (136)

We can compute the optimal $a,b$ given $Var(X),Var(Z)$ and $Cov(X,Z)$.

As $K_0\subset K_1$, the error is no worse than $Y=𝔼X$.

However, this affine function of $Z$ is suboptimal (consider $X\mathrm{=}{Z}^{\mathrm{2}}$). In general, we have to consider a nonlinear function of $Z$.

Consider $K_Z=\{h(Z)\in L_2,h:ℝ\to ℝ\text{ measurable}\}$.

$$\min {\Vert X-Y\Vert }_2,\mathrm{s}.\mathrm{t}.Y\in K_Z.$$ (137)

Recall that

Lemma 4.

$Y$ is $\sigma \mathit{}\mathrm{(}Z\mathrm{)}$-measurable, if and only if $Y\mathrm{=}h\mathit{}\mathrm{(}Z\mathrm{)}$ for some $h\mathrm{:}ℝ\mathrm{\to }ℝ$ measurable.

As a result, $K_Z$ is a complete subspace of $L_2$, since

$$K_Z=L_2(\mathrm{\Omega },\sigma (Z),\mathbb{P}).$$ (138)

Therefore, there exists an orthogonal projection of $X$ to $K_Z$. Moreover, it is unique almost sure.

We define this projection by $𝔼[X|Z]$.

8.2 Conditioning on a $\sigma$-algebra

Consider conditioning on a $\sigma$-algebra: $𝒢\subseteq ℱ$. For each event $G\in 𝒢$, we can decide if $\omega \in G$ or not.

Definition 8.1 (Conditional expectation in $L_2$).

Fix $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$. Let $𝒢\mathrm{\subseteq }ℱ$ be a sub-$\sigma$-algebra on $\mathrm{\Omega }$.

For $X\mathrm{\in }{L}_{\mathrm{2}}\mathit{}\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$,

$$\underset{Y}{\min }{\Vert X-Y\Vert }_2,\mathrm{s}.\mathrm{t}.Y\in L_2(\mathrm{\Omega },𝒢,{\mathbb{P}|}_{𝒢}).$$ (139)

A solution $Y$ to this least square problem is the conditional expectation of $X$, given $𝒢$, denoted as $Y\mathrm{=}𝔼\mathit{}\mathrm{[}X\mathrm{|}𝒢\mathrm{]}$.

Dual Characterization. $(X-Y)⟂Z$ for all $Z\in L_2(\mathrm{\Omega },𝒢,{\mathbb{P}}_{𝒢})$.

Remarks.

• $Y=𝔼[X|𝒢]$ is a random variable on the sample space. Value is determined, once given ${\mathrm{𝟙}}_G$ for all $G\in 𝒢$.

• For random variables $Z$, $𝔼[X|Z]:=𝔼[X|\sigma (Z)]$.

• For an event $E$, $𝔼[X|E]:=𝔼[X|\sigma (E)]$. The conditional expectation must be $Y=a{\mathrm{𝟙}}_E+b{\mathrm{𝟙}}_{E^C}$.

  The optimal value of $a,b$ is $a=\frac{𝔼[X{\mathrm{𝟙}}_E]}{\mathbb{P}(E)}$ and $b=\frac{𝔼[X{\mathrm{𝟙}}_{E^C}]}{\mathbb{P}[E^C]}$.

8.3 Characteristic properties of conditional expectation

Let $G_1,\mathrm{\dots },G_n$ be a disjoint cover of $\mathrm{\Omega }$, $𝒢=\sigma (G_1,G_2,\mathrm{\dots },G_n)$. Let $Y=𝔼[X|𝒢]$.

Measurability: $Y$ is a constant on each minimal event $G_i$. Therefore, $Y$ is $𝒢$-measurable, i.e., $Y^{-1}(B)\in 𝒢$, for all Borel $B$.

Consistency: Average of $Y$ on events in $𝒢$ equals the average of $X$ on the event.

$$𝔼[X{\mathrm{𝟙}}_G]=𝔼[Y{\mathrm{𝟙}}_G],\forall G\in 𝒢.$$ (140)

This is also often called the coarse-graining property.

Proof.

$$⟨X-Y,W⟩=0,\forall W\in L_2(\mathrm{\Omega },𝒢,\mathbb{P}).$$ (141)

Then $𝔼[XW]=𝔼[YW]$. Since ${\mathrm{𝟙}}_G$ is measurable in $𝒢$, the statement is proved. ∎

8.4 Conditional expectation in $L_1$

So far we have only defined conditional expectation in $L_2$. How can we make it work if it only belongs to $L_1$?

Definition 8.2 (Kolmogorov, 1933).

Let $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$ be a probability space. Let $𝒢\mathrm{\in }ℱ$ be a $\sigma$-algebra on $\mathrm{\Omega }$. Let $X\mathrm{\in }{L}_{\mathrm{1}}\mathit{}\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$. A real random variable $Y$ is a version of $𝔼\mathit{}\mathrm{[}X\mathrm{|}𝒢\mathrm{]}$ if

• $Y$ is integrable: $Y\in L_1(\mathrm{\Omega },ℱ,\mathbb{P})$

• $Y$ is $𝒢$-measurable

• Consistency: $𝔼[Y{\mathrm{𝟙}}_G]=𝔼[X{\mathrm{𝟙}}_G]$ for all $G\in 𝒢$.

Theorem 8.3 (Fundamental theorem of conditional expectation).

There exists a version $Y$ of the conditional expectation $𝔼\mathit{}\mathrm{[}X\mathrm{|}𝒢\mathrm{]}$. If $Y^{\mathrm{\prime }}$ is a another version, then $\mathbb{P}\mathit{}\mathrm{[}Y\mathrm{=}{Y}^{\mathrm{\prime }}\mathrm{]}\mathrm{=}\mathrm{1}$.

Proof Sketch..

Existence. WLOG assume $X\ge 0$. Let $X_n(\omega )=\min \{X(\omega ),n\}$.

$X_n$ is positive, bounded, $ℱ$-measurable, and mono-increasingly converges to $X$ point-wise.

$X_n$ bounded implies that $X_n\in L_2$, so we can compute its conditional expectation $Y_n=𝔼[X_n|𝒢]$. We can check that $Y_1\le Y_2\le \mathrm{\cdots }\le Y_n$. Define

$$Y(\omega )=lim\underset{n\to \mathrm{\infty }}{sup}{Y}_n(\omega )\text{ for}\omega \in \mathrm{\Omega }.$$ (142)

By monotone convergence theorem, . Following a similar argument, $𝔼[Y{\mathrm{𝟙}}_G]=𝔼[X{\mathrm{𝟙}}_G]$ for all $G\in 𝒢$.

Moreover, $Y=lim{sup}_{n\to \mathrm{\infty }}{Y}_n$ is $𝒢$-measurable, since $Y_n$ are measurable.

Uniqueness. Assume $Y,Y^{\prime }$ are both versions of conditional expectations. By consistency $𝔼[(Y-Y^{\prime }){\mathrm{𝟙}}_G]=0$ for all $G\in 𝒢$. For contradiction, assume $\mathbb{P}\{Y>Y^{\prime }\}>0$.

Let $E_n=\{Y>Y^{\prime }+1/n\}$, which are $𝒢$-measurable events. $E_n$ mono-increasing converges to $E=\{Y>Y^{\prime }\}$. This means $\mathbb{P}(E_n)$ mono-increasingly converges to $\mathbb{P}\{Y>Y^{\prime }\}>0$. Therefore, there exists $n\in \mathbb{N}$, such that $𝔼[(Y-Y^{\prime })E_n]>\frac{1}{n}\mathbb{P}(E_n)>0$, contradiction. ∎

Proposition 8.4 (Conditional expectation is an expectation.).

Conditional expectation satisfies the same properties as expectation.

• Unital and positive.

• Conditional expectation is linear.

• Monotonic. If $X\le Y$ a.s., then $𝔼[X|𝒢]\le 𝔼[Y|𝒢]$ a.s.

• Jenson’s inequality holds: $𝔼[\phi (x)|𝒢]\ge \phi (𝔼[X|𝒢])$ a.s for convex $\phi$.

8.5 Convergence theorems

Theorem 8.5 (Conditional Monotonic convergence).

Suppose $\mathrm{0}\mathrm{\le }{X}_n\mathrm{\uparrow }X$ a.s. where $X\mathrm{\in }{L}_{\mathrm{1}}$. Then

$$𝔼[X_n|𝒢]\uparrow 𝔼[X|𝒢]\mathrm{a}.\mathrm{s}.$$ (143)

Proposition 8.6.

Some properties for conditional expectation:

• Expectation: If $Y=𝔼[X|𝒢]$, then $𝔼[X]=𝔼[Y]$

• Full knowledge: If $X$ is $𝒢$-measurable, then $𝔼[X|𝒢]=X$ a.s.

• Independence: If $\sigma (X)$ independence of $𝒢$, then $𝔼[X|𝒢]$, then $𝔼[X|𝒢]=𝔼[X]$ a.s.

• Pull-through: If $Z$ is bounded and $𝒢$-measurable, then $𝔼[XZ|𝒢]=𝔼[X|𝒢]Z$, a.s.

• Tower: If $𝒢\subseteq \mathscr{H}\subseteq ℱ$ are increasing $\sigma$-algebras. Then

  $$𝔼[𝔼[X|\mathscr{H}]|𝒢]=𝔼[X|𝒢],a.s.$$ (144)

Conditional integration:

$$𝔼[h(X)|𝒢](\omega )=\int h(x){\mu }_{X|𝒢}(\mathrm{d}x|\omega ),a.s.$$ (145)

8.6 Gaussian and conditioning

Definition 8.7 (Multivariate normal random variable).

$𝐗=(X_1,\mathrm{\dots },X_n)$ is a multivariate normal random vector if it is an affine function of a standard normal vector $𝐙\mathrm{=}\mathrm{(}{𝐙}_{\mathrm{𝟏}}\mathrm{,}\mathrm{\dots }\mathrm{,}{𝐙}_{𝐧}\mathrm{)}$.

$$𝐗=m+\mathrm{\Sigma }𝐙,$$ (146)

where $m\mathrm{\in }{ℝ}^n$ and $\mathrm{\Sigma }\mathrm{\in }{ℝ}^{n\mathrm{\times }n}$.

Remark.

• $𝔼[X_i]=m_i,Cov(X_i,X_j)=C_{ij}$, where $C=\mathrm{\Sigma }{\mathrm{\Sigma }}^{*}⪰0$.

• We denote $𝐗\sim 𝒩(m,C)$, as $m,C$ uniquely determine a multivariate normal random variable.

Definition 8.8 (Multivariate characteristic function).

Let $𝐗$ be a random vector on ${ℝ}^n$. The characteristic function of $𝐗$ is $\chi \mathrm{:}{ℝ}^n\mathrm{\to }ℂ$

$${\chi }_{𝐗}(\theta ):=𝔼[e^{i{\theta }^T𝐗}]$$ (147)

We can check that if $𝐘=A𝐗+b$, then

$${\chi }_{𝐘}(\theta )=e^{i{\theta }^{T}b}{\chi }_{𝐗}(A^{*}\theta ).$$ (148)

If $𝐗,𝐘$ are independent random vectors on ${ℝ}^n$, then

$${\chi }_{𝐗+𝐘}(\theta )={\chi }_{𝐗}(\theta ){\chi }_{𝐘}(\theta ).$$ (149)

It is easy to check that for $𝐗=m+\mathrm{\Sigma }𝐙$,

$${\chi }_{𝐗}(\theta )=e^{i{\theta }^{T}m}{e}^{(-{\Vert {\mathrm{\Sigma }}^{*}\theta \Vert }_2^2/2)}=\exp \left(i{\theta }^{T}m-\frac{{\theta }^{T}C\theta }{2}\right).$$ (150)

Theorem 8.9.

Suppose $X$ are random vectors taking values in ${ℝ}^n$, then the laws of $X$ and $Y$ are the same if and only if the characteristic functions are the same.

Theorem 8.10 (Linear marginals).

A random vector $X$ on ${ℝ}^n$ is normal if and only if $\mathrm{⟨}a\mathrm{,}X\mathrm{⟩}$ is a real normal random variable for every $a\mathrm{\in }{ℝ}^n$.

8.6.1 Gaussian conditioning

Let $(X,𝐘)\in {ℝ}^{n+1}$ be multivariate normal distribution. $𝐘=(Y_1,\mathrm{\dots },Y_n)$. Assume $𝔼[X]=0$ and $𝔼[𝐘]=0$.

We want to find the best approximation of $X$ as a linear function of $Y$:

$$\underset{a\in {ℝ}^n}{\min }{\Vert X-⟨a,𝐘⟩\Vert }^2.$$ (151)

We define $c_{XX}=Var(X)$, $c_{XY}=Cov(X,𝐘)\in {ℝ}^n$, and $C_{YY}=Cov(𝐘,𝐘)\in {ℝ}^{n\times n}$.

Then

$$𝔼[{(X-⟨a,𝐘⟩)}^2]=c_{XX}-2⟨a,c_{XY}⟩+a^T{C}_{YY}a.$$ (152)

By taking the derivative with respect to $a$,

$$a=C_{YY}^{-1}{c}_{XY}$$ (153)

The best approximation is thus

$$\widehat{X}=⟨a,𝐘⟩=c_{XY}^T{C}_{YY}^{-1}𝐘.$$ (154)

This means that

$$X-\widehat{X}⟂span(Y_1,\mathrm{\dots },Y_n).$$ (155)

Then, $Cov(X-\widehat{X},Y)=0$. Specifically, for normal distributions, uncorrelation means independence (which can be shown using characteristic functions as normal random variables are determined by covariance).

Theorem 8.11 (Gaussian conditional expectation.).

Different from general random variables, linear functions $\mathrm{⟨}a\mathrm{,}Y\mathrm{⟩}$ gives full information for conditioning.

$$𝔼[X|Y]=\widehat{X}=c_{XY}{C}_{YY}^{-1}Y.$$ (156)

Proof.

$𝔼[X|Y]$ $=𝔼[(X-\widehat{X})+\widehat{X}|Y]$

$=𝔼[X-\widehat{X}|Y]+𝔼[\widehat{X}|Y].$

$=𝔼[X-\widehat{X}]+\widehat{X}.$ (independence and full information)

$=\widehat{X}.$

∎

9 Martingales

Recall that a $\sigma$-algebra captures information about the world. A bigger $\sigma$-algebra includes more knowledge.

A filtration is a mathematical model for accumulating information.

9.1 Filtration

Definition 9.1 (Filtration).

Let $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$ be a probability space. A (discrete-time) filtration is a sequence of increasing $\sigma$-algebras on $\mathrm{\Omega }$:

$${ℱ}_0\subseteq {ℱ}_1\subseteq \mathrm{\cdots }\subseteq {ℱ}_{\mathrm{\infty }}\subseteq ℱ.$$ (157)

Commonly, define ${ℱ}_{\mathrm{0}}\mathrm{=}\mathrm{\{}\mathrm{\varnothing }\mathrm{,}\mathrm{\Omega }\mathrm{\}}\mathrm{,}{ℱ}_{\mathrm{\infty }}\mathrm{=}\sigma \mathit{}\mathrm{(}{\mathrm{\bigcup }}_{k\mathrm{=}\mathrm{1}}^{\mathrm{\infty }}{ℱ}_k\mathrm{)}$.

Examples.

Let $Z_0,Z_1,\mathrm{\dots },Z_n$ be real random variables, and ${ℱ}_k=\sigma (Z_0,\mathrm{\dots },Z_k)$. Then $\{{ℱ}_k\}$ is a filtration.

Definition 9.2 (Adapted process).

A sequence $\mathrm{(}{X}_{\mathrm{0}}\mathrm{,}{X}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{)}$ of real random variables is adapted to the filtration $\mathrm{(}{ℱ}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ if each $X_k$ is ${ℱ}_k$-measurable.

In other words, at time $k$, the value of $X_k$ is determined by the information we have.

9.2 Defining Martingales

Definition 9.3 (Martingales (Informal)).

A martingale is an adapted process that is indifferent about the future.

That is, for $n\mathrm{\ge }k$, $𝔼\mathit{}\mathrm{[}{X}_n\mathrm{|}{ℱ}_k\mathrm{]}\mathrm{=}{X}_k$.

Definition 9.4 (Martingales (Formal)).

Let $\mathrm{(}\mathrm{\Omega }\mathrm{,}ℱ\mathrm{,}\mathbb{P}\mathrm{)}$ be a probability space, and a filtration ${ℱ}_{\mathrm{0}}\mathrm{\subseteq }{ℱ}_{\mathrm{1}}\mathrm{\subseteq }\mathrm{\cdots }\mathrm{\subseteq }{ℱ}_{\mathrm{\infty }}$. An sequence of real random variables $\mathrm{(}{X}_i\mathrm{:}i\mathrm{\in }{\mathbb{Z}}^{\mathrm{+}}\mathrm{)}$ is a martingale if

• Adapted: $(X_k)$ is adapted to the filtration $({ℱ}_k)$

• Integrable: , for each $k$.

• Status Quo: $𝔼[X_{k+1}|{ℱ}_k]=X_k$ almost sure for each $k$.

We can relax the third property to $𝔼\mathit{}\mathrm{[}{X}_{k\mathrm{+}\mathrm{1}}\mathrm{|}{ℱ}_k\mathrm{]}\mathrm{\le }{X}_k$ a.s., in which $\mathrm{(}{X}_k\mathrm{)}$ is called a supermartingale.

$𝔼[X_{k+1}|{ℱ}_k]\ge X_k$ a.s. is called a submartingale.

This seemingly awkward terminology comes from the super/sub-harmonic function of Markov chains.

Examples. Independent sums of centered random variables, Random walks, Levy-Doob process.

9.3 Formal model for Gambling strategies

Definition 9.5 (Previsible process.).

A sequence of real random variables $\mathrm{(}{C}_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathrm{,}\mathrm{)}$ is a previsible with respect to the filtration $\mathrm{(}{ℱ}_k\mathrm{)}$ if $c_k$ is ${ℱ}_{k\mathrm{-}\mathrm{1}}$-measurable for all $k\mathrm{\in }\mathbb{N}$.

When you play a game of chance, you bet before the game.

Definition 9.6 (Martingale transform).

Let $\mathrm{(}{X}_k\mathrm{)}$ be a martingale and $\mathrm{(}{C}_k\mathrm{:}k\mathrm{\in }\mathbb{N}\mathrm{)}$ be a previsible sequence. The martingale transform is the sequence

$${(C\cdot X)}_k=\sum _{i=1}^k{C}_i(X_i-X_{i-1}),\text{𝑓𝑜𝑟}k=1,2,\mathrm{\dots }.$$ (158)

Remark. You bet $C_i$ units of capital on a fair game (martingale). Then you win $C_i(X_i-X_{i-1})$ on the $i$-th day. The total winnings after $k$ plays is

$${(C\cdot X)}_k=\sum _{i=1}^k{C}_i(X_i-X_{i-1}).$$ (159)

Proposition 9.7 (Martingale transform.).

Let $\mathrm{(}{X}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ be a martingale and $\mathrm{(}{C}_k\mathrm{:}k\mathrm{\in }\mathbb{N}\mathrm{)}$ be a previsible process that are bounded. Then

$$({(C\cdot X)}_k:k\in {\mathbb{Z}}_{+})$$ (160)

is a null martingale, i.e., ${\mathrm{(}C\mathrm{\cdot }X\mathrm{)}}_{\mathrm{0}}\mathrm{=}\mathrm{0}$.

Proof.

Pull-through property:

$$𝔼[{(C\cdot X)}_{k+1}-{(C\cdot X)}_k|{ℱ}_k]=𝔼[C_{k+1}(X_{k+1}-X_k)|{ℱ}_k]=C_{k+1}𝔼[X_{k+1}-X_k|{ℱ}_k]=0.$$ (161)

Since ${(C\cdot X)}_k$ is ${ℱ}_k$ measurable,

$$𝔼[{(C\cdot X)}_{k+1}|{ℱ}_k]={(C\cdot X)}_k.$$ (162)

∎

We interpret this proposition: No sequence of bounded bets allows you to beat a fair game.

Another question is: can you quit the game when you are ahead to get advantages in a fair game?

Definition 9.8 (Stopping times).

A random variable $\tau \mathrm{:}\mathrm{\Omega }\mathrm{\to }{\mathbb{Z}}_{\mathrm{+}}\mathrm{\cup }\mathrm{\{}\mathrm{+}\mathrm{\infty }\mathrm{\}}$ is a stopping time, if $\mathrm{\{}\tau \mathrm{\le }k\mathrm{\}}$ is ${ℱ}_k$ measurable for each $k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}$.

Remark. The meaning of this definition is that after game $k$, you have enough information to decide whether the stopping criterion is triggered.

Definition 9.9 (Stopped process).

Let $\mathrm{(}{X}_k\mathrm{)}$ be an adapted process and $\tau$ be a stopping time. The stopped process is the sequence

$$(X_{k\wedge \tau }:k\in {\mathbb{Z}}_{+}),\text{𝑤ℎ𝑒𝑟𝑒}k\wedge \tau =\min \{k,\tau \}.$$ (163)

The idea of this definition is that your winnings freeze after you stop gambling.

Definition 9.10 (Stopped martingales.).

If $\mathrm{(}{X}_k\mathrm{)}$ is a martingale, $\tau$ is the stopping time, then the stopped process $\mathrm{(}{X}_{k\mathrm{\wedge }\tau }\mathrm{)}$ is a martingale.

Remark. This means you cannot gain an advantage in a fair game by quitting strategically.

Proof.

Consider a previsible process $(C_k:k\in \mathbb{N})$,

$$C_k=\{\begin{array}{cc}1,k\le \tau ,\hfill & \\ 0,k>\tau .\hfill & \end{array}$$ (164)

Since $C_k$ is previsible and bounded, the martingale ${(C\cdot X)}_k$ is a martingale with an initial value 0. This means

$${(C\cdot X)}_k=\sum _{i=1}^k{C}_i(X_i-X_{i-1})=\sum _{i=1}^{k\wedge \tau }(X_i-X_{i-1})=X_{k\wedge \tau }-X_0.$$ (165)

Therefore,

$$𝔼[X_{k\wedge \tau }|{ℱ}_k]=X_0.$$ (166)

∎

Warning: It is not true that $𝔼[X_{\tau }]=𝔼[X_0]$ as $\tau$ is a random variable dependent on the outcomes of $(X_k)$. For example, we stop when $X_k\ge 1$, then $𝔼[X_{\tau }]\ge 1$.

However, with the following theorem, we circumvent this paradox by restricting the horizon of our game plays.

Theorem 9.11 (Optional stopping).

Let $\mathrm{(}{X}_k\mathrm{)}$ be a martingale. and $\tau$ be a stopping time. If $\tau \mathrm{\le }B$ for a fixed $B$ almost surely, then

$$𝔼[X_{\tau }]=𝔼[X_0].$$ (167)

Proof.

By the proposition on the stopped martingales,

$$𝔼[X_0]=𝔼[X_{k\wedge \tau }]\text{for each}k$$ (168)

Choose $k=B$, so

$$𝔼[X_0]=𝔼[X_{B\wedge \tau }]=𝔼[X_{\tau }].$$ (169)

∎

9.4 Convergence of martingales

Martingales are flavored by probability theorists because they converge to a stable equilibrium under weak assumptions.

Theorem 9.12 (Doob’s convergence theorem).

Let $\mathrm{(}{X}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ be a martingale sequence that is uniformly bounded in ${\mathrm{L}}_{\mathrm{1}}$, i.e., there exists a positive $R$, such that $𝔼\mathit{}\mathrm{[}\mathrm{|}{X}_k\mathrm{|}\mathrm{]}\mathrm{\le }R$ for all $k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}$.

Then almost surely, $X_{\mathrm{\infty }}\mathit{}\mathrm{(}\omega \mathrm{)}\mathrm{:=}{\lim }_{k\mathrm{\to }\mathrm{\infty }}{X}_k\mathit{}\mathrm{(}\omega \mathrm{)}$ exists, and is finite. That is, $X_k$ converges to $X_{\mathrm{\infty }}$ almost surely.

Remark. It is not true in general that $𝔼[X_k]$ converges to $𝔼[X_{\mathrm{\infty }}].$

Lemma 5 (Interval sandwich).

A nonrandom real-valued sequence $\mathrm{(}{x}_k\mathrm{)}$ fails to converge if and only if

(170)

for some $a\mathrm{,}b\mathrm{\in }\mathbb{Q}$.

We define “upcrossing” of a sequence to an interval.

Definition 9.13.

Let $\mathrm{(}{x}_k\mathrm{)}$ be a nonrandom real sequence. Fix . The number $u_N\mathit{}a\mathrm{,}b$ of upcrossings before time $N$ is the largest $m$, such that

(171)

where and $x_{t_i}\mathrm{>}b$.

The total number of upcrossings:

$$u_{\mathrm{\infty }}[a,b]=\underset{N\to \mathrm{\infty }}{lim}{u}_N[a,b].$$ (172)

Lemma 6.

Equation 171 implies $u_{\mathrm{\infty }}\mathit{}\mathrm{[}a\mathrm{,}b\mathrm{]}\mathrm{=}\mathrm{\infty }$. If $u_{\mathrm{\infty }}\mathit{}\mathrm{[}a\mathrm{,}b\mathrm{]}$ is finite for all rational pairs $\mathrm{(}a\mathrm{,}b\mathrm{)}$ with , then $\mathrm{(}{x}_k\mathrm{)}$ converges in $ℝ$.

9.4.1 Proof of Doob’s convergence

Idea: if a martingale crosses an interval $[a,b]$ infinitely times, we can make money by betting on the upcrossings. This is impossible.

Specifically, we keep betting below $b$, and start betting when $x_k$ gets below $a$. We formalize it as below.

Fix . Let .

Let .

We can check that $(c_k)$ is positive, bounded, and previsible. Then the martingale transform $Y_k={(C\cdot X)}_k$ is a null-martingale.

Define $U_N[a,b](\omega )$ as the number of upcrossings of $[a,b]$ up to time $N$ by the sample path $X_k(\omega )$, and $U_{\mathrm{\infty }}[a,b](\omega )={lim}_{N\to \mathrm{\infty }}{U}_N[a,b](\omega )$.

Note that

$$Y_N(\omega )\ge (b-a)U_N[a,b](\omega )-(X_N(\omega )-a)$$ (173)

Since $𝔼[Y_n]=0$, so we have the following proposition:

Proposition 9.14 (Snell upcrossing inequality).

Let $\mathrm{(}{X}_k\mathrm{)}$ be a martingale and be real numbers.

$$(b-a)𝔼[U_N[a,b]]\le 𝔼[(X_N-a)]$$ (174)

As $𝔼[|X_N|]\le R$, then for any ,

$$\mathbb{P}\{U_{\mathrm{\infty }}[a,b]=\mathrm{\infty }\}=0.$$ (175)

Define an event $E=\{\omega :X_k(\omega )\text{does not converge in }ℝ\}$,

(176)

Therefore, $\mathbb{P}(E)$, because rational number set $\mathbb{Q}$ is countable. Thus, $X_{\mathrm{\infty }}(\omega )={lim}_{k\to \mathrm{\infty }}{X}_k(\omega )$ with probability 1. Moreover,

$𝔼|X_{\mathrm{\infty }}|$ $=𝔼[lim\underset{k\to \mathrm{\infty }}{inf}|X_k|]\le lim\underset{k\to \mathrm{\infty }}{inf}𝔼|X_k|\le R.$ (177)

9.5 Concentration inequalities for martingales

What is the probability that a martingale ever deviates much from its mean value?

Begin with submartingales: $𝔼[X_{k+1}|{ℱ}_k]\ge X_k$ a.s.

Theorem 9.15 (Doob’s maximal inequality for submartingales).

Consider a positive submartingale $\mathrm{(}{X}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$. For each $N\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}$,

$$\mathbb{P}\{\underset{0\le k\le N}{sup}{X}_k>t\}\le \frac{𝔼X_N}{t}.$$ (178)

Moreover, if $X_n\mathrm{\to }{X}_{\mathrm{\infty }}$ in $L_{\mathrm{1}}$, then it’s true for $N\mathrm{=}\mathrm{\infty }$.

Remark. Though this statement looks like Markov’s inequality, we cannot derive it directly from Markov’s inequality.

Proof.

We want to bound the probability that the martingale escapes a band. We define the stopping time $\tau :\mathrm{\Omega }\to {\mathbb{Z}}_{+}\cup \{\mathrm{\infty }\}$,

$$\tau :=inf\{k\le N:X_k>t\}.$$ (179)

Therefore, the event

(180)

Then,

$𝔼X_N$ $\ge 𝔼X_{N\wedge \tau }$

$\ge 𝔼[X_{N\wedge \tau }{\mathrm{𝟙}}_E]$

$=𝔼[X_{\tau }{\mathrm{𝟙}}_E]$

$>t\mathbb{P}[E]$ (181)

Therefore,

$$\mathbb{P}(\underset{k\le N}{sup}{X}_k>t)\le \frac{𝔼[X_N]}{t}.$$ (182)

Moreover, $E_N:=\{{sup}_{k\le N}{X}_k>t\}$ mono-increasingly converges to $E_{\mathrm{\infty }}$, and $𝔼X_N\to 𝔼[X_{\mathrm{\infty }}]$ by $L_1$ convergence. By dominated convergence theorem the statement holds for $N=\mathrm{\infty }$. ∎

Proposition 9.16 (Martingale: convex transformation.).

Consider a martingale $\mathrm{(}{M}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$. For any convex function $\phi \mathrm{:}ℝ\mathrm{\to }ℝ$, the sequence

$$X_k:=\phi (M_k)$$ (183)

is a submartingale, provided that .

Proof.

By conditional Jensen’s inequality. ∎

We can then generalize Chebyshev’s inequality to Martingales,

Theorem 9.17 (Kolmogorov’s inequality).

Let $\mathrm{(}{M}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ be a martingale in $L_{\mathrm{2}}$. For $N\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}$,

$$\mathbb{P}\{\underset{k\le N}{\max }{(X_k-𝔼X_k)}^2>t\}\le \frac{Var[X_N]}{t}.$$ (184)

Proof.

The sequence $(X_k-𝔼X_k)$ is an $L_2$ martingale, so ${(X_k-𝔼X_k)}^2$ is a submartingale, due to Proposition 9.16. Using Doob’s maximal inequality the statement follows. ∎

Remark. Define ${\mathrm{\Delta }}_k=X_k-X_{k-1}$. Then

$$Var[X_n]=\sum _{k=1}^N𝔼[{\mathrm{\Delta }}_k^2].$$ (185)

Proposition 9.18 (Exponential maximal inequality).

Let $\mathrm{(}{X}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ be a bounded martingale. For $N\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}$,

$$\mathbb{P}\{\underset{k\le N}{\max }{X}_k>t\}\le \underset{\theta >0}{inf}\exp \left(-\theta t+{\xi }_{X_N}(\theta )\right),$$ (186)

where ${\xi }_X\mathit{}\mathrm{(}\theta \mathrm{)}\mathrm{=}\log \mathit{}𝔼\mathit{}{e}^{\theta \mathit{}X}$ is the cgf of $X$.

Theorem 9.19 (Azuma-Hoeffding: uniform version).

Consider a martingale $\mathrm{(}{X}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ whose difference sequence ${\mathrm{\Delta }}_k\mathrm{:=}{X}_k\mathrm{-}{X}_{k\mathrm{-}\mathrm{1}}$ is bounded, $\mathrm{|}{\mathrm{\Delta }}_k\mathrm{|}\mathrm{\le }{a}_k$. Let the variance proxy ${\nu }_N\mathrm{:=}{\mathrm{\sum }}_{k\mathrm{=}\mathrm{1}}^N{a}_k^{\mathrm{2}}$.

$$\mathbb{P}\{\underset{k\le N}{\max }|X_k-X_0|>t\}\le 2\exp \left(-t^2/2{\nu }_N\right).$$ (187)

Proof.

Hoeffding lemma: If $Y$ is a real random variable with $𝔼Y=0$, $|Y|\le a$, then its mgf ${\xi }_Y(\theta )\le \frac{1}{2}{\theta }^2{a}^2$. As $X_N-X_0={\sum }_{k=1}^N{\mathrm{\Delta }}_k$,

$m_{X_N-X_0}(\theta )$ $=𝔼[e^{\theta {\mathrm{\Delta }}_N}\mathrm{\dots }{e}^{\theta {\mathrm{\Delta }}_1}]$

$=𝔼[𝔼[e^{\theta {\mathrm{\Delta }}_N|{ℱ}_{N-1}}]e^{\theta {\mathrm{\Delta }}_{N-1}}\mathrm{\dots }{e}^{\theta {\mathrm{\Delta }}_1}]$

$\le e^{{\theta }^2{\mathrm{\Delta }}_N/2}𝔼[e^{\theta {\mathrm{\Delta }}_{N-1}}\mathrm{\dots }{e}^{\theta {\mathrm{\Delta }}_1}]$

$\le \mathrm{\cdots }\le e^{{\theta }^2{\nu }_N/2}.$ (188)

Therefore,

$${\xi }_{X_N-X_0}(\theta )\le \frac{1}{2}{\theta }^2{\nu }_N.$$ (189)

Using this result with $\theta =t/{\nu }_n$ in the Exponential maximal inequality proves the theorem. ∎

Theorem 9.20 (Ville’s inequality).

Let $\mathrm{(}{X}_k\mathrm{:}k\mathrm{\in }{\mathbb{Z}}_{\mathrm{+}}\mathrm{)}$ be a positive supermartingale. Then

$$\mathbb{P}\{\underset{k\in {\mathbb{Z}}_{+}}{sup}{X}_k>t\}\le \frac{𝔼X_0}{t}.$$ (190)