%% LyX 1.6.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[british]{article}
\usepackage{lmodern}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{geometry}
\geometry{verbose,a4paper,tmargin=2cm,bmargin=2cm,lmargin=3cm,rmargin=3.5cm}
\usepackage{verbatim}
\usepackage{framed}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{esint}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage[bookmarksnumbered,colorlinks,linkcolor=black,urlcolor=blue]{hyperref}

\usepackage{enumerate}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{claim}{Claim}

\newcommand{\defterm}[1]{{\it #1}}

\newcommand{\cD}{{\mathcal D}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cG}{{\mathcal G}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cJ}{{\mathcal J}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\cT}{{\mathcal T}}

\newcommand{\C}{{\mathbb C}}
\newcommand{\E}{{\mathbb E}}
\newcommand{\N}{{\mathbb N}}
\renewcommand{\P}{{\mathbb P}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Z}{{\mathbb Z}}

\newcommand{\mS}{{\mathrm{m}\cS}}
\newcommand{\mSp}{{\mS^+}}

\newcommand{\var}{\mathop{\mathrm{Var}}}
\newcommand{\cov}{\mathop{\mathrm{Cov}}}

\newcommand{\titlesigma}{{\texorpdfstring{$\sigma$}{sigma}}}
\newcommand{\titleSigma}{{\texorpdfstring{$\sigma$}{Sigma}}}

% The only way I can find to get LyX to give me a math environment
% inside an equation tag
\newcommand{\mtag}[1]{\tag{$#1$}}

\usepackage{babel}

\begin{document}

\title{Probability and Measure}


\author{Martin Orr}

\maketitle

\subsection{Introduction}

This is a set of notes for the Probability and Measure course in Part
II of the Cambridge Mathematics Tripos. They were written as my own
attempt to understand the course.

These notes are currently only a draft, so many things could be improved.
Please send me your comments or corrections. If you can't find something
in which is claimed to be in the Appendix, that is because the Appendix
has only partially been written yet. \medskip{}


These notes are intended to be used in combination with Prof Rogers'
examples sheets (at \url{http://www.statslab.cam.ac.uk/~chris/}).
However, I have sometimes included results which are on the example
sheets and I have made no attempt to ensure that material is presented
here in a sensible order for doing the example sheets.

The main sources for these notes were Williams' \textit{Probability
with Martingales}, Billingsley's \textit{Probability and Measure}
and my lecture notes from Prof Rogers' lectures in Michaelmas 2007.
Thanks are also due to my supervisor Dr Tehranchi for helping me to
understand much of the material, and to Jacob Davis for comments and
corrections.

Responsibility for the material in here, including errors, is entirely
my own. Some of my own biases will have shown through. In particular,
these are unashamedly the notes of a pure mathematician and I tend
to emphasise analysis rather than probability.


\section{Sets and measures}

%
\begin{framed}%
{[}4{]} Measure spaces, $\sigma$-algebras, $\pi$-systems and uniqueness
of extension, statement {*}and proof{*} of Carathéodory's extension
theorem. Construction of Lebesgue measure on $\mathbb{R}$. The Borel
$\sigma$-algebra of $\mathbb{R}$. Existence of non-measurable subsets
of $\mathbb{R}$.\end{framed}


\subsection{Probability: A reminder}

In probability theory, we work with a \defterm{sample space} $\Omega$
of possible \defterm{outcomes}. An \defterm{event} is a subset $A$
of $\Omega$ to which we assign a probability $\P(A)$. This should
satisfy the following axioms:
\begin{enumerate}
\item $0\leq\P(A)\leq1$ for all events $A$
\item $\P(\Omega)=1$
\item If $\{A_{n}\}$ is a finite or countable collection of pairwise disjoint
events, \\
then $\P(\bigcup_{n}A_{n})=\sum_{n}\P(A_{n})$
\end{enumerate}
If $\Omega$ is finite or countable, then we can quite happily let
all subsets of $\Omega$ be events, and indeed specifying $\P(\{\omega\})$
for each singleton $\{\omega\}$ is sufficient to determine the probability
of all subsets by the above axioms.


\subsection{Non-measurable sets}

When we turn to uncountable $\Omega$ things are not so simple. Suppose
we try to model the uniform distribution on $\Omega=(0,1]$. By \defterm{uniform distribution}
I mean that probabilities are unchanged by translations: for any fixed
$t$, $\P(\{\omega\in\Omega|\omega+t\bmod1\in A\})=\P(A)$. It turns
out that (as long as we assume the Axiom of Choice) it is not possible
to define a probability for all subsets of $(0,1]$ which satisfies
this condition as well as the above axioms.

\begin{theorem}[Vitali's Theorem]There is no translation-invariant
probability defined on all subsets of $(0,1]$.\end{theorem}

\begin{proof}Suppose we have a translation-invariant probability
$\P$ defined on all subsets of $(0,1]$.

Define an equivalence relation $\sim$ on $(0,1]$ by $x\sim y$ if
$x-y\in\Q$. By the Axiom of Choice, we can form a set $A$ which
contains one element of each equivalence class.

For each $q\in\Q$, let $A_{q}=\{a\in(0,1]|a+q\bmod1\in A\}$. Then
the $A_{q}$ are disjoint, have union $(0,1]$ and there are countably
many. So $\sum_{q}\P(A_{q})=\P((0,1])=1$.

However, $\P(A_{q})=\P(A)$ for all $q\in\Q$. So if $\P(A)=0$ then
$\sum_{q}\P(A_{q})=0$ while if $\P(A)=\epsilon>0$ then $\sum_{q}\P(A_{q})=\infty$,
giving a contradiction.\end{proof}

Another property we might expect the uniform distribution to have
is that $\P((a,b])=b-a$ for all $a,b$. It is not too hard to show
that this is implied by translation invariance, but does the reverse
implication hold? Does there exist a probability on $(0,1]$ which
takes the right value on all intervals? In fact this turns out to
lead deep into set theory and be undecidable with the usual axioms.
For those who care about such things, the existence of such a probability
is equiconsistent with the existence of a measurable cardinal.


\subsection{\titleSigma-fields}

Since we can't satisfactorily assign a probability to all subsets
of $(0,1]$, we restrict our notion of what an event is. Let $\cF\subset\wp(\Omega)$
be the set of events. To properly define the $\cF$ we will work on,
we need to take a much more abstract approach, and write down the
properties we would like $\cF$ to have, then define $\cF$ to be
the smallest collection of sets with these properties. This has the
benefit that it allows us to develop a more general theory that can
be applied to any collection of sets with the required properties,
not just subsets of $(0,1]$.

The main properties we require of $\cF$ are that the sets mentioned
in the axioms for probability should exist. It also seems natural
that if $A$ is an event, $\text{not-}A$ should be as well. So the
properties are:
\begin{enumerate}
\item $\Omega\in\cF$.
\item If $A\in\cF$ then $A^{c}\in\cF$ (complement with respect to $\Omega$).
\item If $\{A_{n}\}$ is a finite or countable subcollection of $\cF$,
then $\bigcup_{n}A_{n}\in\cF$.
\end{enumerate}
Any collection $\cF\subset\wp(\Omega)$ with these properties is called
a \defterm{$\sigma$-field}. Note that, by 2 and 3, $\cF$ is closed
under countable intersections as well.

A \defterm{measurable space} is a pair $(\Omega,\cF)$ where $\Omega$
is some set and $\cF$ is a $\sigma$-field on $\Omega$. 

A subset $A$ of $\Omega$ is a \defterm{measurable set} with respect
to a $\sigma$-field $\cF$ if $A\in\cF$. (This is the same as the
probabilistic term \defterm{event}.)

A \defterm{measure} is a function $\mu:\cF\rightarrow[0,\infty]$
on a $\sigma$-field s.t. if $\{A_{n}\}\subset\cF$ is finite or countable
and the $A_{n}$ are pairwise disjoint, then $\mu(\bigcup_{n}A_{n})=\sum_{n}\mu(A_{n})$.

$\mu$ is a \defterm{probability (measure)} if $\mu(\Omega)=1$ (note
that this agrees with the earlier definition of probability).

$\mu$ is a \defterm{finite measure} if $\mu(\Omega)<\infty$ .

$\mu$ is a \defterm{$\sigma$-finite measure} if there are countably
many sets $A_{n}$, each with $\mu(A_{n})<\infty$, s.t. $\bigcup_{n}A_{n}=\Omega$.

A \defterm{measure space} is a triple $(\Omega,\cF,\mu)$ where $\Omega$
is a set, $\cF$ is a $\sigma$-field on $\Omega$ and $\mu$ is a
measure on $\cF$.


\subsection{The Borel \titlesigma-field}

To continue with the scheme outlined in the previous section, we want
to define our uniform probability on the smallest $\sigma$-field
on $(0,1]$ containing the half-open intervals. What does this mean?

Observe that for any collection of $\sigma$-fields on some base set
$\Omega$, their intersection is itself a $\sigma$-field (it is straightforward
to check the definition). So, given any collection $C$ of subsets
of~$\Omega$, $\bigcap\{\sigma\textrm{-fields containing }C\}$ is
itself a $\sigma$-field. It is contained in every $\sigma$-field
containing $C$, so it makes sense to call this the smallest $\sigma$-field
containing $C$. Note that this really exists because $\wp(\Omega)$
is itself a $\sigma$-field, so there is at least one $\sigma$-field
containing $C$. (Compare this with defining the closure of a subset
$S$ of a topological space as the smallest closed set containing
$S$.)

The smallest $\sigma$-field containing $C$ is called the \defterm{$\sigma$-field generated by $C$},
written $\sigma(C)$.

For a topological space $(X,T)$, the \defterm{Borel $\sigma$-field}
is $\sigma(T)$, the $\sigma$-field generated by the open sets.

\begin{lemma}The $\sigma$-field on $(0,1]$ generated by half-open
intervals $(a,b]$ is the same as $B((0,1])$.\end{lemma}

\begin{proof}Let $S$ be the set of half-open intervals $(a,b]$
and $T$ the open sets of $(0,1]$.

If $b<1$, then $(a,b]=\bigcap_{n}(a,b+1/n)\in B((0,1])$ and if $b=1$,
certainly, $(a,b]\in B((0,1])$. So $S\subset B((0,1])$, so as $B((0,1])$
is a $\sigma$-field, $\sigma(S)\subset B((0,1])$.

The open interval $(a,b)=\bigcup_{n}(a,b-1/n]\in\sigma(S)$, and any
interval $(a,1]\in\sigma(S)$. Every open subset of $(0,1]$ can be
written as a countable union of open intervals and sets of the form
$(a,1]$ (since every connected component of our open set contains
a rational). So $T\subset\sigma(S)$, and $B((0,1])=\sigma(T)\subset\sigma(S)$.\end{proof}


\subsection{Carathéodory Extension Theorem}

Now we have our $\sigma$-field $B((0,1])$ of events, we have to
ensure that there is in fact a suitable measure defined on them. We
do this using the Carathéodory Extension Theorem.

In order to state this theorem, we need weaker versions of some of
the definitions concerning measures. There are several definitions
of families of sets obeying certain closure properties, most of which
are unimportant and I have relegated to a table at the end of this
section. What we need now is a \defterm{field}, with the properties:
\begin{enumerate}
\item If $A\in\cF$ then $A^{c}\in\cF_{0}$ (complement with respect to
$\Omega$).
\item $\Omega\in\cF_{0}$.
\item If $\{A_{n}\}$ is a finite subcollection of $\cF_{0}$, then $\bigcup_{n}A_{n}\in\cF_{0}$.
\end{enumerate}
A function $\mu_{0}:\cF_{0}\rightarrow[0,\infty]$ on a field $\cF_{0}$
is \defterm{countably additive} if whenever $\{A_{n}\}\subset\cF_{0}$
is finite or countable, the $A_{n}$ are pairwise disjoint and $\bigcup_{n}A_{n}\in\cF_{0}$,
then $\mu_{0}(\bigcup_{n}A_{n})=\sum_{n}\mu_{0}(A_{n})$. (So a measure
is a countably additive function on a $\sigma$-field.) \defterm{Finitely additive}
is defined similarly, with the condition only applied to finite subfamilies
$\{A_{n}\}$.

\begin{theorem}[Carathéodory Extension Theorem]If $\cF_{0}$ is a
field and $\mu_{0}:\cF_{0}\rightarrow[0,\infty]$ is countably additive,
then there is a measure $\mu$ on $\sigma(\cF_{0})$ s.t. $\mu(A)=\mu_{0}(A)$
for all $A\in\cF_{0}$.\end{theorem}

The proof of this theorem is starred in the schedules, and is boring
and mostly technical, so it is given in the Appendix. (Note that the
unstarred sentence in the schedules {}``Construction of Lebesgue
measure on $\R$'' might require the definition of outer measure.)




\subsection{Uniqueness of extension}

That's all very well; this tells us that, given a countably additive
function on a field, there is some measure on the generated $\sigma$-field
which extends it. But there might be more than one such measure. We
want to prove that there is only one. To do this requires defining
a couple more types of sets, and some fairly abstract manipulation
of them. I find it impossible to visualise the sets worked with here,
which are larger than $\R$, but this doesn't really matter: you can
just follow the properties defining them and only care about what
they actually contain at the beginning and end.

A \defterm{$\pi$-system} is a family $\cG$ of subsets of $\Omega$
s.t. if $A,B\in\cG$ then $A\cap B\in\cG$. Note that any field is
a $\pi$-system.

A \defterm{$d$-system} is a family $\cD$ of subsets of $\Omega$
s.t.
\begin{enumerate}
\item $\Omega\in\cD$.
\item If $A,B\in\cD$ and $A\supset B$ then $A\setminus B\in\cD$.
\item If $\{A_{n}\}\subset\cD$ is countable and $A_{n}\uparrow A$ (i.e.
$A_{n}\subset A_{n+1}\forall n$ and $A=\bigcup_{n}A_{n}$) then $A\in\cD$.
\end{enumerate}
It is easy to check that the intersection of a family of $d$-systems
is a $d$-system, so for any collection $C$ of subsets of $\Omega$
we can define $d(C)$, the \defterm{$d$-system generated by $C$},
as the smallest $d$-system containing $C$, just as with $\sigma$-fields.

These are connected to $\sigma$-fields by the following two lemmas.

\begin{lemma}A collection $\cG$ of subsets of $\Omega$ is a $\sigma$-field
iff it is both a $\pi$-system and a $d$-system.\end{lemma}

\begin{proof}The forwards direction is easy.

Now suppose $\cG$ is both a $\pi$-system and a $d$-system.

From the definition of a $d$-system, $\Omega\in\cG$ and for $A\in\cG$,
$A^{c}=\Omega\setminus A\in\cG$.

Suppose $\{A_{n}\}\subset\cG$ is countable. Then $A_{n}^{c}\in\cG$
for each $n$, so as $\cG$ is a $\pi$-system, we have\[
\left(\bigcup_{n=1}^{N}A_{n}\right)^{c}=\bigcap_{n=1}^{N}A_{n}^{c}\in\cG\]


So $\bigcup_{n=1}^{N}A_{n}\in\cG$ for each $N$. Hence as $\bigcup_{n=1}^{N}A_{n}\uparrow\bigcup_{n}A_{n}$,
we get $\bigcup_{n}A_{n}\in\cG$.

So $\cG$ is a $\sigma$-field.\end{proof}

\begin{lemma}[Dynkin's Lemma]If $\cI$ is a $\pi$-system, then $d(\cI)=\sigma(\cI)$.\end{lemma}

\begin{proof}Certainly, $\sigma(\cI)$ is a $\sigma$-field, so a
$d$-system, containing $\cI$, so $\sigma(\cI)\supset d(\cI)$.

We need to show that $d(\cI)$ is a $\pi$-system. Then by the previous
lemma, it is a $\sigma$-field, so $d(\cI)\supset\sigma(\cI)$.

To show this, we will construct a subset of $d(\cI)$ and show that
the subset is itself a $d$-system containing $\cI$, so containing,
and therefore equal to, $d(\cI)$. We will need to do this twice.

Let\[
\cD_{1}=\{A\in d(\cI)\colon A\cap X\in d(\cI)\forall X\in\cI\}\]


Certainly $\Omega\in\cD_{1}$.

If $A,B\in\cD_{1}$ and $A\supset B$, then $(A\setminus B)\cap X=(A\cap X)\setminus(B\cap X)\in d(\cI)$
for all $X\in\cI$, so $A\setminus B\in\cD_{1}$.

If $\{A_{n}\}\subset\cD_{1}$ is countable and $A_{n}\uparrow A$,
then $(A_{n}\cap X)\uparrow(A\cap X)$ so $A\cap X\in d(\cI)$ for
all $X\in\cI$, so $A\in\cD_{1}$.

So $\cD_{1}$ is a $d$-system. Also, since $\cI$ is a $\pi$-system,
$\cI\subset\cD_{1}$.

So $d(\cI)\subset\cD_{1}$; and by definition, $\cD_{1}\subset d(\cI)$.
So $d(\cI)=\cD_{1}$.

Now let\[
\cD_{2}=\{B\in d(\cI)\colon B\cap Y\in d(\cI)\forall Y\in d(\cI)\}\]


By the same argument as before, $\cD_{2}$ is a $d$-system.

If $X\in\cI$, then $A\cap X\in d(\cI)$ for all $A\in\cD_{1}=d(\cI)$,
so $X\in\cD_{2}$.

Hence $\cI\subset\cD_{2}$ so $d(\cI)\subset\cD_{2}$ so $d(\cI)=\cD_{2}$.

Hence $d(\cI)$ is closed under finite intersections, so is a $\pi$-system.\end{proof}

With those out of the way, the following theorem tells us that if
two measures agree on a $\pi$-system, then they agree on the $\sigma$-field
generated by the $\pi$-system.

\begin{theorem}\label{lemma:pi-unique-measure}If $\cI$ is a $\pi$-system
and $\mu_{1},\mu_{2}$ are measures on $\sigma(\cI)$ with $\mu_{1}(\Omega)=\mu_{2}(\Omega)<\infty$
and $\mu_{1}(A)=\mu_{2}(A)$ for all $A\in\cI$, then $\mu_{1}=\mu_{2}$.\end{theorem}

\begin{proof}Let \[
\cD=\{A\in\cI\colon\mu_{1}(A)=\mu_{2}(A)\}\]


We show that $\cD$ is a $d$-system. We are given that $\cI\subset\cD$,
so then $\cD\supset d(\cI)=\sigma(\cI)$.

We are given that $\Omega\in\cD$.

If $A,B\in\cD$ and $A\supset B$ then \[
\mu_{1}(A\setminus B)=\mu_{1}(A)-\mu_{1}(B)=\mu_{2}(A)-\mu_{2}(B)=\mu_{2}(A\setminus B)\]
so $A\setminus B\in\cD$.

If $\{A_{n}\}\subset\cD$ is countable and $A_{n}\uparrow A$, then
let $B_{n}=A_{n}\setminus\bigcup_{m=1}^{n-1}A_{m}$.

Then the $B_{n}$ are pairwise disjoint, $A_{N}=\bigcup_{n=1}^{N}B_{n}$
and $A=\bigcup_{n=1}^{\infty}B_{n}$ so\[
\mu_{j}(A)=\sum_{n=1}^{\infty}\mu_{j}(B_{n})=\lim_{N\rightarrow\infty}\sum_{n=1}^{N}\mu_{j}(B_{n})=\lim_{N\rightarrow\infty}\mu_{j}(A_{N})\]
 for $j=1,2$, so as $\mu_{1}(A_{N})=\mu_{2}(A_{N})$ for each $N$,
we get $\mu_{1}(A)=\mu_{2}(A)$ so $A\in\cD$.

So $\cD$ is a $d$-system.\end{proof}


\subsection{Borel measure on $\R$}

To apply this theory to $B((0,1])$, let $\cF_{0}$ be the family
of finite unions of half-open intervals i.e. sets of the form $\bigcup_{i=1}^{n}(a_{i},b_{i}]$.
This is clearly a field, and $\sigma(\cF_{0})=B((0,1])$. Every element
of $\cF_{0}$ can be written as a finite union of disjoint intervals,
and we can define $\mu_{0}(\bigcup_{i=1}^{n}(a_{i},b_{i}])=\sum_{i=1}^{n}(b_{i}-a_{i})$
if the intervals $(a_{i},b_{i}]$ are disjoint. It is straightforward
to check that this is well-defined and finitely additive, but we need
to check that it is countably additive.

\begin{lemma}$\mu_{0}$ is countably additive.\end{lemma}

\begin{proof}We begin by noting an alternative definition of countably
additive: a function on a field is countably additive iff it is finitely
additive and for any countable sequence $\{F_{n}\}\subset\cF_{0}$
s.t. $F_{n}\downarrow\emptyset$ (i.e. $F_{n}\supset F_{n+1}\forall n$
and $\bigcap_{n}F_{n}=\emptyset$), we have $\mu_{0}(F_{n})\downarrow0$.
This is because for any countable collection $\{A_{n}\}\subset\cF_{0}$
of disjoint sets s.t. $A=\bigcup_{n}A_{n}\in\cF_{0}$, we have $F_{n}=A\setminus\bigcup_{i=1}^{n}A_{i}\in\cF_{0}$
with $F_{n}\downarrow0$ and $\mu_{0}(F_{n})=\mu_{0}(A)-\sum_{i=1}^{n}\mu_{0}(A_{n})$.

So given a sequence $\{F_{n}\}\subset\cF_{0}$ s.t. $F_{n}\downarrow0$
and $\epsilon>0$, we need to show that $\mu_{0}(F_{n})<\epsilon$
for large enough $n$.

Each $F_{n}$ is a finite union of disjoint half-open intervals; we
can make these intervals slightly smaller to get $G_{n}\in\cF_{0}$
such that $\mu_{0}(F_{n}\setminus G_{n})<\epsilon2^{-n}$ and $\overline{G}_{n}\subset F_{n}$
(the closure of $G_{n}$ in the topological sense).

$\overline{G}_{n}$ are closed subsets of the compact space $[0,1]$,
and $\overline{G}_{n}\downarrow\emptyset$ so there is some $N$ for
which\[
\bigcap_{n=1}^{N}\overline{G}_{n}=\emptyset\]


Now\[
F_{N}=F_{N}\setminus\bigcap_{n=1}^{N}G_{n}=\bigcup_{n=1}^{N}(F_{N}\setminus G_{n})\subset\bigcup_{n=1}^{N}(F_{n}\setminus G_{n})\]


so \[
\mu_{0}(F_{N})\leq\sum_{n=1}^{N}\mu_{0}(F_{n}\setminus G_{n})<\sum_{n=1}^{N}\epsilon2^{-n}<\epsilon\]
\end{proof}

The Carathéodory Extension Theorem then tells us that we can extend
$\mu_{0}$ to $\sigma(\cF_{0})=B((0,1])$. Because $\cF_{0}$ is a
$\pi$-system, the extension is unique. This gives us the \defterm{Borel measure}
on $B((0,1])$. 


\subsection{Lebesgue measure on $\R$: Final details}

To get Lebesgue measure, there is one more step (which is rarely important).
Let $(\Omega,\cF,\mu)$ be a measure space. If $N\subset M\subset\Omega$
and $\mu(M)=0$, then we would expect that $\mu(N)=0$. However, $N$
need not be in $\cF$. So let the set of \defterm{null sets} be \[
\cN=\{N\subset\Omega\colon N\subset M\text{ for some }M\text{ with }\mu(M)=0\}\]


Then define $\cF^{*}=\{A\cup N\colon A\in\cF,N\in\cN\}$, the \defterm{completion of $\cF$ with respect to $\mu$}.
You can check that $\cF^{*}$ is a $\sigma$-field, and there is a
unique extension of $\mu$ to $\cF^{*}$ (example sheet 1, question
9).

The \defterm{Lebesgue $\sigma$-field} of $\R$ is defined to be the
completion of the Borel $\sigma$-field with respect to Borel measure,
and \defterm{Lebesgue measure} the corresponding measure.

We know that Lebesgue measure satisfies $\mu((a,b])=b-a$. But we
started off looking for a measure satisfying the stronger condition
of translation-invariance. You can check that in fact Lebesgue measure
is translation-invariant, using example sheet 1, question 10.

Note also that we can define Lebesgue measure on all of $\R$, not
just $(0,1]$, by taking a copy on $(n,n+1]$ for each $n\in\Z$,
and letting a general set's measure be given by summing the measures
of its intersections with each interval $(n,n+1]$.


\subsection{$\liminf$ and $\limsup$}

$\liminf$ and $\limsup$ are operations on sequences from elementary
analysis. They are not part of the schedules for any IA or IB course,
so I will define them now.

\[
\limsup_{n\rightarrow\infty}x_{n}=\lim_{n\rightarrow\infty}\sup_{m\geq n}x_{m}\]
\[
\liminf_{n\rightarrow\infty}x_{n}=\lim_{n\rightarrow\infty}\inf_{m\geq n}x_{m}\]


The values $\sup_{m\geq n}x_{m}$ are decreasing as $n$ increases,
so the $\limsup$ always exists, providing we allow it to take the
values $\pm\infty$. These have the properties:\[
\liminf x_{n}\leq\limsup x_{n}\]
\[
\liminf x_{n}=\limsup x_{n}\mbox{ iff }x_{n}\mbox{ converges, in which case they are equal to }\lim x_{n}\]


Also useful are similar definitions for sequences of sets:\[
\limsup_{n\rightarrow\infty}A_{n}=\bigcap_{n}\bigcup_{m\geq n}A_{n}\]
\[
\liminf_{n\rightarrow\infty}A_{n}=\bigcup_{n}\bigcap_{m\geq n}A_{n}\]


When the $A_{n}$ are events, $\limsup A_{n}$ is the event {}``$A_{n}$
happens infinitely often'' (i.e. for infinitely many $n$) and $\liminf A_{n}$
is the event {}``eventually $A_{n}$ always happens'' (i.e. for
all $n$ greater than some $n_{0}$).


\subsection{Set table}

The different types of families of subsets of $\Omega$ are shown
in the table. Note that a ring of sets is a ring in the algebraic
sense, with symmetric difference as the addition operation and intersection
as the multiplication. A field of sets is not an algebraic field.

\begin{center}
\begin{tabular}{|c|c|c|}
\hline 
Type of set & Closed under (definition) & Implies closed under\tabularnewline
\hline
\hline 
ring & symmetric difference & subtraction\tabularnewline
 & finite intersection & finite union\tabularnewline
\hline 
$\sigma$-ring & symmetric difference & subtraction\tabularnewline
 & countable intersection & countable union\tabularnewline
\hline 
field & contains $\Omega$ & finite intersection\tabularnewline
(also called & complement & symmetric difference\tabularnewline
algebra) & finite union & subtraction\tabularnewline
\hline 
$\sigma$-field & contains $\Omega$ & countable intersection\tabularnewline
(or $\sigma$-algebra) & complement & symmetric difference\tabularnewline
 & countable union & subtraction\tabularnewline
\hline 
$\pi$-system & finite intersection & \tabularnewline
\hline 
$d$-system & contains $\Omega$ & complement\tabularnewline
 & subtraction (where $A\supset B)$ & \tabularnewline
 & increasing countable union & \tabularnewline
\hline
\end{tabular}
\par\end{center}


\section{Random variables}

%
\begin{framed}%
{[}2{]} Lebesgue-Stieltjes measure and probability distribution functions.

Measurable functions, random variables.\end{framed}


\subsection{Measurable functions}

Having defined measure spaces, we now define their structure-preserving
maps. This definition is essentially the same as the definition of
continuous maps from one topological space to another:

For measurable spaces $(S_{1},\cS_{1}),(S_{2},\cS_{2})$, a function
$f:S_{1}\rightarrow S_{2}$ is \defterm{measurable} (or properly
\defterm{$\cS_1$/$\cS_2$-measurable}) if $f^{-1}(A)\in\cS_{1}$ for
all $A\in\cS_{2}$.

The equivalent probabilistic concept is a \defterm{random variable},
defined as a measurable function from a probability space to $(\R,B(\R))$.

\begin{lemma}If $\cS_{2}=\sigma(\cT)$ and $f:S_{1}\rightarrow S_{2}$
satisfies $f^{-1}(A)\in\cS_{1}$ for all $A\in\cT$, then $f$ is
measurable.\end{lemma}

\begin{proof}Note that $f^{-1}$ preserves set operations: $f^{-1}(\bigcup_{i}A_{i})=\bigcup_{i}f^{-1}(A_{i})$
etc., so $\cG=\{A\subset S_{2}\colon f^{-1}(A)\in\cS_{1}\}$ has the
same closure properties as $\cS_{1}$, so is a $\sigma$-field.

We are given that $\cG\supset\cT$, so $\cG\supset\sigma(\cT)=\cS_{2}$,
so $f$ is $\cS_{1}$/$\cS_{2}$-measurable.\end{proof}

This lemma makes it easier to prove that functions are measurable
by telling us two things:
\begin{enumerate}
\item If the two spaces are the Borel $\sigma$-fields of topological spaces,
and $f$ is continuous, then $f$ is measurable. (Apply the lemma
with $\cT=\{\text{open sets of }S_{2}\}$.)
\item If $(S_{2},\cS_{2})=(\R,B(\R))$, then we only need to check that
$f^{-1}((-\infty,c))$ is measurable for all $c\in\R$, since $B(\R)=\sigma(\{(-\infty,c)\})$.
\end{enumerate}
Measurable functions with range $(\R,B(\R))$ are the most common
case, and we should check that these are closed under arithmetic operations.

\begin{lemma}If $f_{1},f_{2}:(S_{1},\cS_{1})\rightarrow(\R,B(\R))$
are measurable, then $f_{1}+f_{2}$, $f_{1}f_{2}$ (pointwise multiplication)
and $\lambda f_{1}(\lambda\in\R)$ are measurable.\end{lemma}

\begin{proof}We will only do $f_{1}+f_{2}$ here. The others are
similar.

\[
f_{1}(\omega)+f_{2}(\omega)<c\;\;\mbox{iff}\;\; f_{1}(\omega)<q<c-f_{2}(\omega)\mbox{ for some }q\in\Q\]


so\begin{align*}
(f_{1}+f_{2})^{-1}((-\infty,c)) & =\bigcup_{q\in\Q}\{\omega:f_{1}(\omega)<q\mbox{ and }f_{2}(\omega)<c-q\}\\
 & =\bigcup_{q\in\Q}\left(f_{1}^{-1}((-\infty,q))\cap f_{2}^{-1}((-\infty,c-q))\right)\in\cS_{1}\end{align*}
\end{proof}

If $\{f_{n}\}$ is a countable sequence of measurable functions, then
$\inf f_{n},\sup f_{n},\liminf f_{n},\limsup f_{n}$ are also measurable.


\subsection{Distributions and distribution functions}

Let $X:\Omega\rightarrow\R$ be a random variable. The \defterm{distribution}
of $X$ is the measure $\mu_{X}=\P\circ X^{-1}$ on $(\R,B(\R))$.%
\begin{comment}
It should be made clear that $X^{-1}$ is a function on sets - consult
PwM p.33.
\end{comment}
{} (Probabilists also call this the \defterm{law} of $X$.) You should
check that this defines a probability measure.

For any Borel set $A$, we have $\mu_{X}(A)=\P(X^{-1}(A))=\P(\{\omega\in\Omega\colon X(\omega)\in A\})$.
For convenience, we abbreviate this to $\P(X\in A)$. (Other expressions
of the form $\P(\mbox{logical statement})$ should be interpreted
similarly.)

The \defterm{(cumulative) distribution function} $F_{X}:\R\rightarrow[0,1]$
of $X$ is\[
F_{X}(c)=\P(X\leq c)=\P\circ X^{-1}((-\infty,c])\]


The intervals $(-\infty,c]$ form a $\pi$-system generating $B(\R)$,
so knowing $F_{X}$ uniquely determines the distribution of $X$ (by
Lemma \ref{lemma:pi-unique-measure}).

Distribution functions have some important properties:
\begin{enumerate}
\item $F_{X}$ is increasing
\item $F_{X}$ is right-continuous (since $\{\omega:X\leq c+1/n\}\downarrow\{\omega\colon X\leq c\}$)
\item ${\displaystyle \lim_{c\rightarrow-\infty}}F_{X}(c)=0$ and ${\displaystyle \lim_{c\rightarrow+\infty}}F_{X}(c)=1$
\end{enumerate}
Conversely, given a function $F$ with these properties, it is the
distribution function of some random variable. We can construct this
random variable by taking Lebesgue measure on $(0,1]$ as our probability
space and setting\[
X(\omega)=\inf\{t\colon\omega\leq F(t)\}\]


\begin{claim}This gives us an r.v. $X$ with $F_{X}=F$.\end{claim}

\begin{proof}Fix $\omega$. We can find $t>X(\omega)$ and arbitrarily
close to $X(\omega)$ s.t. $F(t)\geq\omega$. So by the right-continuity
of $F$, $F(X(\omega))\geq\omega$.

So if $X(\omega)\leq c$, then as $F$ is increasing, $\omega\leq F(X(\omega))\leq F(c)$.

Conversely, if $\omega\leq F(c)$, then it is immediate from the definition
of $X$ that $X(\omega)\leq c$.

Hence $\{\omega:X\leq c\}=\{\omega:\omega\leq F(c)\}$, which is measurable,
so $X$ is measurable and\[
F_{X}(c)=\P(X\leq c)=\P(0<\omega\leq F(c))=F(c)\qedhere\]
\end{proof}

The distribution of $X$ gives us a measure $\mu_{F}$ for which the
random variable $I(\omega)=\omega$ has distribution function $F$.

This is called the \defterm{Lebesgue-Stieltjes measure} corresponding
to $F$.

You can also construct the Lebesgue-Stieltjes measure by starting
from $\mu_{F}((a,b])=F(b)-F(a)$ and following the same procedure
as for the construction of Lebesgue measure, using the Carathéodory
Extension Theorem. The only bit which requires a bit of extra work
is checking that given a finite union of half-open intervals you can
fit a compact set inside it while reducing its measure by less than
$\epsilon2^{n}$, which uses the right-continuity of $F$.


\subsection{Generated \titlesigma-fields}

For a function $f:\Omega\rightarrow(S_{2},\cS_{2})$, the \defterm{$\sigma$-field generated by $f$},
$\sigma(f)$, is defined to be the smallest $\sigma$-field on $\Omega$
with respect to which $f$ is measurable. This can be defined, as
with the $\sigma$-field generated by a set, as the intersection of
all $\sigma$-fields for which $f$ is measurable, but more directly\[
\sigma(f)=\{f^{-1}(A)\colon A\in\cS_{2}\}\]
This is because $\{f^{-1}(A)\colon A\in\cS_{2}\}$ certainly must
be contained in a $\sigma$-field for $f$ to be measurable, but you
can check that it is itself a $\sigma$-field.

If $X$ is a random variable on $(\Omega,\cF)$, then of course $\sigma(X)\subset\cF$,
but it can be much smaller. For example, if $(\Omega,\cF)=((0,1],B((0,1]))$
and\[
X(\omega)=\begin{cases}
0 & \text{if }0<\omega\leq\frac{1}{2}\\
1 & \text{if }\frac{1}{2}<\omega\leq1\end{cases}\]


then $\sigma(X)$ is just $\{\emptyset,(0,\frac{1}{2}],(\frac{1}{2},1],(0,1]\}$.

More generally, given a collection $\{f_{\lambda}\colon\lambda\in\Lambda\}$
of functions $\Omega\rightarrow(S_{2},\cS_{2})$, the \defterm{$\sigma$-field generated by $\{f_\lambda\}$},
$\sigma(\{f_{\lambda}\})$, is the smallest $\sigma$-field on $\Omega$
with respect to which all the $f_{\lambda}$ are measurable.

Intuitively, if $X_{\lambda}$ are random variables, then $\sigma(X_{\lambda})$
is the set of events $A$ for which, if we know the values of all
the variables $X_{\lambda}$, then we know whether $A$ occurred or
not.


\section{Independence}

%
\begin{framed}%
{[}2{]} Independence of events, independence of $\sigma$-algebras.
The Borel-Cantelli lemmas. Kolmogorov's 0-1 law.

Independence of random variables.\end{framed}


\subsection{Definitions}

So far, the ideas we have covered are interesting both from a pure
mathematical and from a probabilistic perspective, although probability
has often provided the easiest motivations and examples. Independence
however is a fundamentally probabilistic concept. We work on a probability
space $(\Omega,\cF,\P)$.

A sequence $(A_{n})$ of events is \defterm{independent} if for any
distinct $n_{1},\ldots,n_{k}$, we have\[
\P(A_{n_{1}}\cap\ldots\cap A_{n_{k}})=\prod_{j=1}^{k}\P(A_{n_{j}})\]


A sequence $(\cG_{n})$ of sub-$\sigma$-fields of $\cF$ is \defterm{independent}
if for any distinct $n_{1},\ldots,n_{k}$ and events $A_{j}\in\cG_{n_{j}},$
we have\[
\P(A_{1}\cap\ldots\cap A_{k})=\prod_{j=1}^{k}\P(A_{j})\]


The same definition will apply for $\pi$-systems (or indeed any families
of events). We only really care about $\sigma$-fields, but having
the definition for $\pi$-systems makes it easier to show that $\sigma$-fields
are independent, using the following lemma. It is proved here only
for two $\pi$-systems, but can be extended to all sequences (to get
it for infinite sequences, use the fact that a sequence of $\sigma$-fields/$\pi$-systems
is independent iff all its finite subsequences are).

A sequence $(X_{n})$ of random variables is \defterm{independent}
if the $\sigma$-fields $\sigma(X_{n})$ are independent.

\begin{lemma}\label{lemma:pi-independent}If $\cI,\cJ$ are independent
$\pi$-systems with $\sigma(\cI)=\cG,\sigma(\cJ)=\cH$, then $\cG,\cH$
are independent.\end{lemma}

\begin{proof}Fix $A\in\cI$.

Define measures $\mu_{1},\mu_{2}$ on $\cH$ by\[
\mu_{1}(B)=\P(A\cap B),\:\mu_{2}(B)=\P(A)\P(B)\]


It is easy to check that these are measures. We are given that $\mu_{1}(B)=\mu_{2}(B)$
for all $B\in\cJ$, and of course $\mu_{1}(\Omega)=\mu_{2}(\Omega)$,
so by Lemma \ref{lemma:pi-unique-measure}, $\mu_{1}=\mu_{2}$.

Applying this for all $A\in\cI$, we get $\P(A\cap B)=\P(A)\P(B)$
for all $A\in\cI,B\in\cH$.

Now we repeat the other way round: fix $B\in\cH$ and define measures
$\mu_{3},\mu_{4}$ on $\cG$ by\[
\mu_{3}(A)=\P(A\cap B),\:\mu_{4}(A)=\P(A)\P(B)\]


We have just shown that $\mu_{3}(A)=\mu_{4}(A)$ for all $A\in\cI$,
so using Lemma \ref{lemma:pi-unique-measure} again, we get $\mu_{3}=\mu_{4}$.

Again, this holds for arbitrary $B$, so $\P(A\cap B)=\P(A)\P(B)$
for all $A\in\cG,B\in\cH$.\end{proof}


\subsection{The Borel-Cantelli lemmas}

The two Borel-Cantelli lemmas are useful tools to prove results about
sequences of events. The proof of the first lemma appears very quick
and simple, but it is probably the more important of the two. There
are many problems where, if you don't quote this lemma, you will re-write
its proof from scratch -- and it's harder to come up with in the context
of a particular problem than as a general statement. Note that the
first lemma does not require independence. Indeed it holds not only
in probability spaces, but in general measure spaces.

\begin{lemma}[First Borel-Cantelli Lemma]If $(A_{n})$ is a sequence
of events with $\sum\P(A_{n})<\infty$, then $\P(\limsup A_{n})=0$.\end{lemma}

\begin{proof}\[
\P(\limsup A_{n})=\P(\bigcap_{k}\bigcup_{n\geq k}A_{n})\leq\P(\bigcup_{n\geq k}A_{n})\leq\sum_{n\geq k}\P(A_{n})\rightarrow0\text{ as }k\rightarrow\infty\qedhere\]
\end{proof}

The second lemma does require independence. This is easy to see because
for example if $A_{n}$ is the same event for all $n$, then $\sum\P(A_{n})=\infty$
but $\P(\limsup A_{n})\neq1$. The proof is more involved and will
use the following lemma.

\begin{lemma}If $(p_{n})$ is a real sequence with $0\leq p_{n}\leq1$
and $\sum p_{n}=\infty$, then $\prod(1-p_{n})=0$.\end{lemma}

\begin{proof}\[
1-x\leq exp(-x)\]
 so\[
\prod_{n=1}^{N}(1-p_{n})\leq\prod_{n=1}^{N}exp(-p_{n})=exp(-\sum_{n=1}^{N}p_{n})\rightarrow0\mbox{ since }\sum p_{n}\rightarrow\infty\qedhere\]
\end{proof}

\begin{lemma}[Second Borel-Cantelli Lemma]If $(A_{n})$ is a sequence
of independent events with $\sum\P(A_{n})=\infty$, then $\P(\limsup A_{n})=1$.\end{lemma}

\begin{proof}It is usually easier to prove that a probability is
zero rather than one, so we consider $(\limsup A_{n})^{c}=\liminf A_{n}^{c}$
instead. Note that if $(A_{n})$ is independent, then so is $(A_{n}^{c})$.

Let $p_{n}=\P(A_{n})$. For any $k$,\[
\P(\bigcap_{n\geq k}A_{n}^{c})\leq\P(\bigcap_{n=k}^{m}A_{n}^{c})=\prod_{n=k}^{m}\P(A_{n}^{c})=\prod_{n=k}^{m}(1-p_{n})\rightarrow0\mbox{ as }m\rightarrow\infty\]


by the previous lemma. So \[
\P(\bigcap_{n\geq k}A_{n}^{c})=0\]


for all $k$, and taking a countable union,\[
\P(\liminf A_{n}^{c})=\P(\bigcup_{k}\bigcap_{n\geq k}A_{n}^{c})=0\qedhere\]


\end{proof}


\subsection{Tail \titlesigma-fields}

Given a sequence $(X_{n})$ of random variables, let $\cT_{n}=\sigma(X_{n},X_{n+1},\ldots)$.

Then the \defterm{tail $\sigma$-field} of the sequence is $\cT=\bigcap_{n}\cT_{n}$.

So $\cT$ is the $\sigma$-field of events which are determined by
the values of $X_{n}$, but are not affected by any finite number
of these values. For example, the event {}``$\lim X_{n}$ exists''
is in $\cT$, and the random variables $\limsup X_{n}$, $\liminf X_{n}$
are $\cT$-measurable.

Kolmogorov's 0-1 Law tells us that if the $X_{n}$ are independent,
then a tail event has probability either 0 or 1. However, it may not
be easy to tell which. (Sometimes, but not always, the Borel-Cantelli
lemmas can help.)

A $\sigma$-field $\cF$ is \defterm{trivial} (with respect to a
probability measure $\P$) if $\P(A)=0\mbox{ or }1$ for all $A\in\cF$.
The usual way to prove that a $\sigma$-field is trivial is to show
that it is independent of itself, as then for any $A\in\cF$,\[
\P(A)=\P(A\cap A)=\P(A)\P(A)\]


\begin{theorem}[Kolmogorov's 0-1 Law]The tail $\sigma$-field of
a sequence of independent random variables is trivial.\end{theorem}

\begin{proof}Let $\cF_{n}=\sigma(X_{1},\ldots,X_{n})$.

First we show that $\cF_{n}$ and $\cT_{n+1}$ are independent (i.e.
the first $n$ variables are independent of all the rest).

Let \[
\cI_{n}=\{\{\omega\colon X_{1}\leq c_{1},\ldots,X_{n}\leq c_{n}\}\colon c_{1},\ldots,c_{n}\in\R\},\]
 \[
\cJ_{n}=\{\{\omega\colon X_{n}\leq c_{n},\ldots,X_{n+r}\leq c_{n+r}\}\colon c_{n},\ldots,c_{n+r}\in\R,r\in\N\}\]
 

Then $\cI_{n},\cJ_{n+1}$ are $\pi$-systems, generate $\cF_{n},\cT_{n+1}$
respectively, and are certainly independent. So by lemma \ref{lemma:pi-independent},
$\cF_{n}$ and $\cT_{n+1}$ are independent.

Since $\cT\subset\cT_{n+1}$, we get that $\cT$ is independent of
$\cF_{n}$ for all $n$. This is certainly what we would expect intuitively:
tail events are independent of finite subsequences of $(X_{n})$.\medskip{}


Now we show that $\cT$ is independent of $\cT_{1}=\sigma(X_{1},X_{2},\ldots)$.

Because $\cF_{n}\subset\cF_{n+1}$ and they are closed under intersection,
the union $\cI_{\infty}=\bigcup_{n}\cF_{n}$ is a $\pi$-system. It
must be contained in any $\sigma$-field on which all $X_{n}$ are
measurable, so $\cI_{\infty}\subset\cT_{1}$; and all $X_{n}$ are
measurable on any $\sigma$-field containing $\cI_{\infty}$, so $\sigma(\cI_{\infty})\supset\cT_{1}$.
So $\sigma(\cI_{\infty})=\cT_{1}$.

If $A\in\cI_{\infty}$ and $B\in\cT$, then $A\in\cF_{n}$ for some
$n$ and $\cF_{n}$ is independent of $\cT$, so $\P(A\cap B)=\P(A)\P(B)$.
So $\cI_{\infty}$ and $\cT$ are independent, so $\cT_{1}$ and $\cT$
are independent.

Finally $\cT\subset\cT_{1}$, so $\cT$ is independent of itself.\end{proof}

It follows that if $Y$ is a tail-measurable random variable, then
$\P(Y\leq c)=0\mbox{ or }1$ for all $c\in\R$, so $Y$ is almost
surely constant.


\section{Integration}

%
\begin{framed}%
{[}2{]} Construction of the integral, expectation.

Fatou's lemma, monotone and dominated convergence, differentiation
under the integral sign.\end{framed}


\subsection{Definition of integration}

Let $(S,\cS,\mu)$ be a $\sigma$-finite measure space and write $\mS$
for the set of measurable functions $(S,\cS)\rightarrow(\R,B(\R))$
and $\mSp$ for the set of non-negative measurable functions. For
$f\in\mSp$, we aim to define the \defterm{integral} of $f$ with
respect to $\mu$. (Allowing $f$ to take negative values introduces
complications we will consider later.) There are a confusingly large
number of notations for this:\[
\mu(f)=\int_{S}fd\mu=\int_{S}f(x)\mu(dx)\]


In probability, the equivalent concept is expectation. For a random
variable $X:(\Omega,\cF,\P)\rightarrow\R$, the \defterm{expectation}
of $X$ is \[
\E(X)=\int_{\Omega}Xd\P\]


We begin with the indicator functions of measurable sets. For these,
if $A$ is measurable, then\[
\int I_{A}d\mu=\mu(A)\]
 (In probabilistic terms, this is the statement $\E(I_{A})=\P(A)$.)

The integration operator should be linear, so we can extend this to
finite combinations of indicators. A function $f:S\rightarrow\R$
is \defterm{simple} if\[
f=\sum_{k=1}^{n}\alpha_{k}I_{A_{k}}\mbox{ for some measurable sets }A_{k}\mbox{ and constants }\alpha_{k}\in\R\]
The set of simple functions is denoted $SF$, and of non-negative
simple functions $SF^{+}$. For $f\in SF^{+}$, we define\[
\int\left(\sum_{k=1}^{n}\alpha_{k}I_{A_{k}}\right)d\mu=\sum_{k=1}^{n}\alpha_{k}\mu(A_{k})\]
We need to check that this is well-defined, because a single simple
function will have many different representations of the form $f=\sum_{k=1}^{n}\alpha_{k}I_{A_{k}}$.
This is fairly boring and routine. Note that we can always find such
a representation with the sets $A_{k}$ disjoint, as a simple function
can take only finitely many values $c_{1},\ldots,c_{k}$; then let
$A_{k}=f^{-1}(\{c_{k}\})$. Note also that (by writing the functions
on each side as suitable sums of indicators) if $f_{j}$ are simple
functions and $\beta_{j}\geq0$ then \[
\int\left(\sum_{j=1}^{n}\beta_{j}f_{j}\right)d\mu=\sum_{j=1}^{n}\beta_{j}\int f_{j}d\mu\]
 

The simple functions are good enough to approximate all measurable
functions from below: given $f\in\mSp$, let\[
f_{n}(x)=2^{-n}\left\lfloor 2^{n}\min\{f(x),n\}\right\rfloor =2^{-n}\sum_{j=1}^{n2^{n}}I_{\{x:f(x)\geq j2^{-n}\}}\]
Then $f_{n}$ is an increasing sequence which converges to $f$ pointwise,
and indeed $f_{n}\rightarrow f$ uniformly on any set of the form
$\{x\colon f(x)\leq k\}$.

So for general $f\in\mSp$, we define\[
\int fd\mu=\sup\{{\textstyle \int}gd\mu\colon g\leq f,g\in SF^{+}\}\]
This may be $+\infty$. $f\in\mSp$ is \defterm{integrable} if $\int fd\mu<\infty$.


\subsection{Monotone Convergence Theorem}

The key theorem about integrals is the Monotone Convergence Theorem:

\begin{theorem}[Monotone Convergence Theorem]If $f_{n}\in\mSp$ and
$f_{n}\uparrow f$ (pointwise) then\[
\int f_{n}d\mu\:\big\uparrow\int fd\mu\]
\end{theorem}

To prove this theorem, we go through a couple of restricted versions.

\begin{lemma}If $f_{n}\in SF^{+},A\in\cS$ and $f_{n}\uparrow I_{A}$,
then $\int f_{n}d\mu\uparrow\mu(A)$.\end{lemma}

\begin{proof}Certainly $\int f_{n}d\mu\leq\mu(A)$ for each $n$
and $\int f_{n}d\mu$ is increasing. We just need to show that $\int f_{n}d\mu$
becomes arbitrarily close to $\mu(A)$.

Given $\epsilon>0$, let $A_{n}=\{\omega\colon f_{n}(\omega)\geq1-\epsilon\}$.

Since $f_{n}\uparrow I_{A}$, $A_{n}\uparrow A$ and so $\mu(A_{n})\uparrow\mu(A)$.

Hence we can choose $n$ s.t. $\mu(A_{n})\geq(1-\epsilon)\mu(A)$.

Note that, by the definition of $A_{n}$, $f_{n}\geq(1-\epsilon)I_{A_{n}}$,
so\[
\int f_{n}d\mu\geq(1-\epsilon)\mu(A_{n})\geq(1-\epsilon)^{2}\mu(A)\]


Since $\epsilon$ is arbitrary, we are done.\end{proof}

\begin{corollary}If $f_{n},f\in SF^{+}$ and $f_{n}\uparrow f$,
then $\int f_{n}d\mu\uparrow\int fd\mu$.\end{corollary}

\begin{proof}Write $f=\sum_{k}\alpha_{k}I_{A_{k}}$ where $A_{k}$
are disjoint measurable sets. Then $f_{n}I_{A_{k}}\uparrow\alpha_{k}I_{A_{k}}$
for each $k$, so we can apply the lemma for each $k$ and add up.\end{proof}

\begin{lemma}If $f_{n}\in SF^{+},f\in\mSp$ and $f_{n}\uparrow f$
then $\int f_{n}d\mu\uparrow\int fd\mu$.\end{lemma}

\begin{proof}Again$\int f_{n}d\mu\leq\int fd\mu$ for all $n$ and
$\int f_{n}d\mu$ is increasing, so we just need to check that $\int f_{n}d\mu$
becomes arbitrarily close to $\int fd\mu$.

Given $\epsilon>0$, there exists some $g\in SF^{+}$ s.t. $g\leq f$
and $\int gd\mu>\int fd\mu-\epsilon$ (by the definition of $\int fd\mu$).

Let $g_{n}=\min\{g,f_{n}\}$. Now $g_{n}\uparrow g$ and $g_{n},g$
are simple, so by the above corollary we have $\int g_{n}d\mu\uparrow\int gd\mu$.

Then for large enough $n$, 

\[
{\textstyle \int}f_{n}d\mu\geq{\textstyle \int}g_{n}d\mu>{\textstyle \int}gd\mu-\epsilon>{\textstyle \int}fd\mu-2\epsilon\qedhere\]
\end{proof}

Now we are ready for the main theorem. The proof uses the following
lemma from elementary analysis, left as an exercise:

\begin{lemma}If $(a_{nk})_{n,k\in\N}$ are real numbers increasing
with both $n$ and $k$, then\[
\lim_{n\rightarrow\infty}\lim_{k\rightarrow\infty}a_{nk}=\lim_{n\rightarrow\infty}a_{nn}\]
\end{lemma}

\begin{theorem}[Monotone Convergence Theorem]If $f_{n}\in\mSp$ and
$f_{n}\uparrow f$ then $\int f_{n}d\mu\uparrow\int fd\mu$.\end{theorem}

\begin{proof}First note that $f^{-1}((-\infty,c])=\bigcap_{n}f_{n}^{-1}((-\infty,c])$
so $f$ is measurable and $\int fd\mu$ is defined.

For each $n$, let $(g_{nk})_{k\in\N}$ be a sequence of simple functions
s.t. $g_{nk}\uparrow f_{n}$ as $k\rightarrow\infty$.

For each $n,k$, let $h_{nk}=\max\{g_{mk}:m\leq n\}$. The $h_{nk}$
are certainly increasing in both $n$ and $k$, and since $g_{nk}\leq h_{nk}\leq f_{n}$,
$h_{nk}\uparrow f_{n}$.

So for each $\omega$ we get\[
\lim_{n\rightarrow\infty}h_{nn}(\omega)=\lim_{n\rightarrow\infty}\lim_{k\rightarrow\infty}h_{nk}(\omega)=\lim_{n\rightarrow\infty}f_{n}(\omega)=f(\omega)\]


So $h_{nn}\uparrow f$. Since $h_{nk}$ is the max of a finite collection
of simple functions, $h_{nk}$ is itself simple. So by the earlier
lemma, we get\[
\int fd\mu=\lim_{n\rightarrow\infty}\int h_{nn}d\mu=\lim_{n\rightarrow\infty}\lim_{k\rightarrow\infty}\int h_{nk}d\mu=\lim_{n\rightarrow\infty}\int f_{n}d\mu\qedhere\]
\end{proof}


\subsection{Integration of functions with negative values, and $\cL^{1}$}

Functions which can take negative values require a little more care.

Write the positive and negative parts of $f$ as $f^{+}=\max\{f,0\},f^{-}=\max\{-f,0\}$,
so that $f=f^{+}-f^{-}$ and $|f|=f^{+}+f^{-}$.

Then $f\in\mS$ is \defterm{integrable} if $\int|f|d\mu<\infty$,
and\[
\int fd\mu=\int f^{+}d\mu-\int f^{-}d\mu\]


It is necessary to rule out $\int f^{+}d\mu=\int f^{-}d\mu=\infty$
to avoid an undefined $\infty-\infty$, and to rule out cases in which
just one of $\int f^{+}d\mu,\int f^{-}d\mu=\infty$ to ensure that
the set of integrable functions is closed under addition and subtraction.

Write $\cL^{1}(S,\cS,\mu)$ for the set of integrable functions on
a $\sigma$-finite measure space $(S,\cS,\mu)$.

The monotone convergence theorem extends to functions in $\cL^{1}$,
as long as $\lim\int f_{n}d\mu$ is finite.


\subsection{Other convergence theorems}

There are a number of important consequences of the monotone convergence
theorem. Note that the first applies only to nonnegative functions.

\begin{lemma}[Fatou's Lemma]If $f_{n}\in\mSp$ then \[
\int\liminf f_{n}d\mu\leq\liminf\int f_{n}d\mu\]
\end{lemma}

\begin{proof}Let $g_{n}={\displaystyle \inf_{m\geq n}}f_{m}$. (This
is why we need that $f_{n}\geq0$ -- it follows that $g_{n}\geq0$
too, so $\int g_{n}$ is defined. If we allowed functions with negative
values then $g_{n}$ need not be integrable.)

Then $g_{n}\uparrow\liminf f_{n}$ so by MCT, $\int g_{n}d\mu\uparrow\int\liminf f_{n}d\mu$.

Also $\int g_{n}d\mu\leq\int f_{m}d\mu$ for all $m\geq n$ so\[
{\textstyle \int}g_{n}d\mu\leq\inf_{m\geq n}{\textstyle \int}f_{m}d\mu\]


And so \[
{\textstyle \int}\liminf f_{n}d\mu=\lim{\textstyle \int}g_{n}d\mu\leq\liminf{\textstyle \int}f_{m}d\mu\qedhere\]
\end{proof}

\begin{lemma}[Reverse Fatou's Lemma]If $f_{n}\in\cL^{1}$ and there
exists an integrable function $g$ s.t. $f_{n}\leq g$ for all $n$,
then\[
\int\limsup f_{n}d\mu\geq\limsup\int f_{n}d\mu\]
\end{lemma}

\begin{proof}Apply Fatou's lemma to the non-nonnegative functions
$g-f_{n}$.\end{proof}

\begin{theorem}[Dominated Convergence Theorem]If $f_{n}\in\cL^{1}$,
there exists an integrable $g$ s.t. $\vert f_{n}\vert\leq g$ for
all $n$, and $f_{n}\rightarrow f$ (pointwise) then \[
\int|f_{n}-f|d\mu\rightarrow0\]
\end{theorem}

\begin{proof}Since $f_{n}\rightarrow f$ we have $\limsup|f_{n}-f|=0$.

Also, by the triangle inequality, \[
|f_{n}-f|\leq2g\]


so we can apply reverse Fatou to get\[
0={\textstyle \int}\limsup|f_{n}-f|d\mu\geq\limsup{\textstyle \int}|f_{n}-f|d\mu\geq0\]


and so \[
{\textstyle \int}|f_{n}-f|d\mu\rightarrow0\qedhere\]
\end{proof}

\begin{corollary}[Bounded Convergence Theorem]If $X_{n}$ are random
variables on a probability space $(\Omega,\cF,\P)$, there is a constant
$K$ s.t. $\vert X_{n}\vert\leq K$ for all $n$, and $X_{n}\rightarrow X$
(pointwise) then $\E(|X_{n}-X|)\rightarrow0$.\end{corollary}

\begin{proof}Because $\P(\Omega)$ is finite, the constant random
variable $K$ is integrable. So we can simply apply the dominated
convergence theorem.\end{proof}


\subsection{The standard machine}

The standard machine refers to a technique for proving general facts
about integrals, by working through the stages of the definition:
indicator functions (perhaps starting with indicators of special sets
e.g. intervals), simple functions, non-negative functions (using monotone
convergence), and finally general integrable functions. As an illustration
of the technique, we shall prove that integration is linear and that
if $X,Y$ are independent random variables, then $\E(XY)=\E(X)\E(Y)$.

\begin{theorem}If $f,g\in\cL^{1}(S,\cS,\mu)$ then $\int(\alpha f+\beta g)d\mu=\alpha\int fd\mu+\beta\int gd\mu$.\end{theorem}

\begin{proof}We have observed that this fact holds whenever $f,g$
are simple, directly from the definition of integration.

If $f,g\in\mSp$ and $\alpha,\beta\geq0$, then let $f_{n}\uparrow f,g_{n}\uparrow f$
be sequences of simple functions. Then $\alpha f_{n}+\beta g_{n}\uparrow\alpha f+\beta g$
so by the Monotone Convergence Theorem,\[
\int\alpha f+\beta gd\mu=\lim\int\alpha f_{n}+\beta g_{n}d\mu=\lim\left(\alpha\int f_{n}d\mu+\beta\int g_{n}d\mu\right)=\alpha\int fd\mu+\beta\int gd\mu\]


Finally, for $f,g\in\cL^{1}$: assume that $\alpha,\beta\geq0$, by
switching the sign of $\alpha$ and $f$ or $\beta$ and $g$ if necessary.

Let $A=\{x:\alpha f(x)+\beta g(x)\geq0\},B=\{x:\alpha f(x)+\beta g(x)\leq0\}$.

Now $(\alpha f+\beta g)^{+}=(\alpha f^{+}I_{A}+\beta g^{+}I_{A})-(\alpha f^{-}I_{A}+\beta g^{-}I_{A})$
and $(\alpha f+\beta g)^{+},(\alpha f^{-}I_{A}+\beta g^{-}I_{A})\geq0$
so using what we have just proved,\[
\int(\alpha f+\beta g)^{+}d\mu+\int(\alpha f^{-}I_{A}+\beta g^{-}I_{A})d\mu=\int(\alpha f^{+}I_{A}+\beta g^{+}I_{A})d\mu\]
\[
\therefore\int(\alpha f+\beta g)^{+}d\mu=\alpha\int f^{+}I_{A}d\mu+\beta\int g^{+}I_{A}d\mu-\alpha\int f^{-}I_{A}d\mu-\beta\int g^{-}I_{A}d\mu\]


Similarly $-(\alpha f+\beta g)^{-}=(\alpha f^{+}I_{B}+\beta g^{+}I_{B})-(\alpha f^{-}I_{B}+\beta g^{-}I_{B})$,
so\[
-\int(\alpha f+\beta g)^{-}d\mu=\alpha\int f^{+}I_{B}d\mu+\beta\int g^{+}I_{B}d\mu-\alpha\int f^{-}I_{B}d\mu-\beta\int g^{-}I_{B}d\mu\]


We also have $f^{+}=f^{+}I_{A}+f^{+}I_{B}$ and similarly for $f^{-},g^{+},g^{-}$,
so putting these together (and using linearity for nonnegative functions
again) gives\[
\int(\alpha f+\beta g)^{+}d\mu-\int(\alpha f+\beta g)^{-}d\mu=\alpha\int f^{+}d\mu+\beta\int g^{+}d\mu-\alpha\int f^{-}d\mu-\beta\int g^{-}d\mu\]
which is what we want.\end{proof}

\begin{theorem}If $X,Y$ are independent r.v.s and $g,h:\R\rightarrow\R$
measurable functions s.t. $g(X),h(Y)$ are integrable, then $\E(g(X)h(Y))=\E(g(X))\E(h(Y))$.\end{theorem}

\begin{proof}Stating the theorem in this form, rather than just $\E(XY)=\E(X)\E(Y)$
allows us to apply the standard machine to $g,h$.

If $g,h$ are both indicators of measurable sets, say $g=I_{A},h=I_{B}$,
then\[
\begin{aligned}\E(g(X)h(Y)) & =\P(X\in A\mbox{ and }Y\in B)\\
 & =\P(X\in A)\P(Y\in B)\mbox{ by definition of independence for }X,Y\\
 & =\E(g(X))\E(h(Y))\end{aligned}
\]


By linearity, this extends to $g,h$ simple functions.

If $g,h\geq0$, then take sequences $g_{n},h_{n}$ of simple functions
s.t. $g_{n}\uparrow g,h_{n}\uparrow h$. Then $g_{n}(X)h_{n}(Y)\uparrow g(X)h(Y)$
so by the Monotone Convergence Theorem,\[
\E(g(X)h(Y))=\lim_{n\rightarrow\infty}\E(g_{n}(X)h_{n}(Y))=\lim_{n\rightarrow\infty}\E(g_{n}(X))\E(h_{n}(Y))=\E(g(X))\E(h(Y))\]


Finally for general $g,h$, let $f(\omega)=g(X)h(Y)$.

Then $f^{+}=g^{+}(X)h^{+}(Y)+g^{-}(X)h^{-}(Y)$ and $f^{-}=g^{+}(X)h^{-}(Y)+g^{-}(X)h^{+}(Y)$
so\[
\begin{aligned}\E(g(X)h(Y)) & = &  & \E(f^{+})-\E(f^{-})\\
 & = &  & \E(g^{+}(X)h^{+}(Y))+\E(g^{-}(X)h^{-}(Y))\\
 & = &  & \E(g^{+}(X))\E(h^{+}(Y))+\E(g^{-}(X))\E(h^{-}(Y))\\
 &  &  & -\E(g^{+}(X))\E(h^{-}(Y))-\E(g^{-}(X))\E(h^{+}(Y))\\
 & = &  & (\E(g^{+}(X))-\E(g^{-}(X)))(\E(h^{+}(X))-\E(h^{-}(X)))\\
 & = &  & \E(g(X))\E(h(Y))\end{aligned}
\]
\end{proof}


\subsection{Differentiation under the integral sign}

This is fairly unimportant but is explicitly required by the schedules.

Suppose we have a function $f(s,x)$ of two variables, and let $F(x)=\int f(s,x)\mu(ds)$.
It would be nice if we could obtain $F'(x)$ by interchanging the
order of differentiation and integration, and getting $F'(x)=\int\frac{\partial}{\partial x}f(s,x)\mu(ds)$.

Here we give conditions for this to be valid:

\begin{theorem}Let $f:(S,\cS,\mu)\times\R\rightarrow\R$ be a function
s.t.

\begin{enumerate}[(i)]

\item For each $x\in\R$, $s\mapsto f(s,x)$ is a $\cS$-measurable
function (so $F(x)$ has a chance of existing).

\item For each $s\in S$, $x\mapsto f(s,x)$ is differentiable.

\item $s\mapsto f(s,x)\in L^{1}(S,\cS,\mu)$ (so $F(0)$ exists and
is finite).

\item There is a function $g\in L^{1}(S,\cS,\mu)$ s.t. $\left|\dfrac{f(s,x)-f(s,y)}{x-y}\right|\leq g(s)\forall x\neq y$
(so approximations to $\frac{\partial}{\partial x}f(s,x)$ are dominated
by $g$).

\end{enumerate}

Then $F(x)=\int_{S}f(s,x)\mu(ds)$ is differentiable, and $F'(x)=\int\frac{\partial}{\partial x}f(s,x)\mu(ds)$.\end{theorem}

\begin{proof}Condition (iii) together with (iv) with $y=0$ ensures
that $F(x)$ exists and is finite for all $x\in\R$.

Now for fixed $x$,\begin{align*}
\frac{F(x+h)-F(x)}{h} & =\int_{S}\frac{f(s,x+h)-f(s)}{h}\mu(ds)\\
 & \rightarrow\int_{S}\frac{\partial}{\partial x}f(s,x)\mu(ds)\mbox{ as }h\rightarrow0\end{align*}
 by dominated convergence.\end{proof}


\section{Modes of convergence}

%
\begin{framed}%
{[}1{]} Convergence in measure and convergence almost everywhere. \end{framed}


\subsection{Convergence almost everywhere}

A sequence of functions $f_{n}:S\rightarrow\R$ converges \defterm{$\mu$-almost everywhere}
to $f$ if\[
\mu(\{\omega\colon f_{n}(\omega)\not\rightarrow f(\omega)\})=0\]
In other words, $f_{n}\rightarrow f$ pointwise except on a set of
measure zero. In probability, this is called \defterm{almost sure convergence}.
So far as we are concerned in measure theory, this is just as good
as pointwise convergence; in particular the Monotone and Dominated
Convergence Theorems continue to hold if we replace pointwise convergence
with almost everywhere convergence (just consider $f_{n}I_{A}\rightarrow fI_{A}$
where $A=\{\omega\colon f_{n}(\omega)\rightarrow f(\omega)\}$).


\subsection{\label{subsec:convergence-in-measure}Convergence in measure}

A sequence of functions $f_{n}:S\rightarrow\R$ converges \defterm{in $\mu$-measure}
to $f$ if, for any $\epsilon,\delta>0$, there exists $N$ s.t. for
all $n\geq N$, \[
\mu(\{\omega\colon|f_{n}(\omega)-f(\omega)|>\epsilon\})<\delta\]
In probability, this is called \defterm{convergence in probability}.
This is a weak definition of convergence and does not imply that $f_{n}(\omega)\rightarrow f(\omega)$
at any point, as the sets $\{\omega:|f_{n}(\omega)-f(\omega)|>\epsilon\}$
must become small in measure but they can jump back and forward across
the entire space.

For example, let\[
\begin{array}{cccc}
f_{1}=I_{(0,1]},\\
f_{2}=2I_{(0,\frac{1}{2}]}, &  & f_{3}=2I_{(\frac{1}{2},1]}\\
f_{4}=4I_{(0,\frac{1}{4}]}, & f_{5}=4I_{(\frac{1}{4},\frac{1}{2}]}, & f_{6}=4I_{(\frac{1}{2},\frac{3}{4}]}, & f_{7}=4I_{(\frac{3}{4},1]}\end{array}\]
 and so on.

For small $\epsilon$ we have $\mu(\{\omega:|f_{n}(\omega)|>\epsilon\})=2^{-k}$
when $2^{k}\leq n<2^{k+1}$, so $f_{n}\rightarrow0$ in measure, but
$f_{n}(\omega)\not\rightarrow0$ for any $\omega\in(0,1]$. Also $\int f_{n}d\mu=1$
for all $n$, so $\int f_{n}d\mu\not\rightarrow0$.

\begin{theorem}If $(S,\cS,\mu)$ is a finite measure space and $f_{n}\rightarrow f$
a.e., then $f_{n}\rightarrow f$ in measure.\end{theorem}

\begin{proof}Fix $\epsilon>0$. Let $A_{n}=\{\omega\colon|f_{m}(\omega)-f(\omega)|\leq\epsilon\mbox{ for all }m\geq n\}$.

Then $A_{n}\uparrow A$ where $A=\{\omega\colon f_{n}(\omega)\rightarrow f(\omega)\}$,
and as $f_{n}\rightarrow f$ a.e., $\mu(A)=\mu(A_{n})$.

So $\mu(A_{n})\uparrow\mu(S)$.

Since $\mu(S)$ is finite, $\mu(A_{n}^{c})=\mu(S)-\mu(A_{n})\downarrow0$.

Now $\{\omega\colon|f_{n}(\omega)-f(\omega)|>\epsilon\}\subset A_{n}^{c}$,
so $f_{n}\rightarrow f$ in measure.\end{proof}

\begin{theorem}If $f_{n}\rightarrow f$ in measure, then there is
a subsequence $(f_{n_{k}})$ s.t. $f_{n_{k}}\rightarrow f$ almost
everywhere.\end{theorem}

\begin{proof}Say that $(f_{n})$ \defterm{converges fast in measure}
to $f$ if for all $\epsilon>0$,\[
\sum_{n}\mu(\{\omega\colon|f_{n}(\omega)-f(\omega)|>\epsilon\})<\infty\]
This is clearly a strengthening of the definition of convergence in
measure, and it rules out things like the above counter-example because
the sets on which it is far from zero get small too slowly. In fact
it is a sufficient strengthening that fast convergence in measure
implies almost-everywhere convergence (proved below).

It addition it is not too hard to show that if a sequence converges
in measure, then it has a subsequence which converges fast in measure:
just choose $n_{k}$ such that, for all $n\geq n_{k}$,.\[
\mu(\{\omega\colon|f_{n}(\omega)-f(\omega)|>2^{-k}\})<2^{-k}\]


For any $\epsilon>0$, choose $K$ s.t. $2^{-K}<\epsilon$, and then\[
\sum_{k=K}^{\infty}\mu(\{\omega\colon|f_{n_{k}}(\omega)-f(\omega)|>\epsilon\})<\sum_{k=K}^{\infty}2^{-k}<\infty\]


To complete the proof, suppose that $f_{n}\rightarrow f$ fast in
measure. We show that $f_{n}\rightarrow f$ a.e.

For any $\epsilon>0$, Borel-Cantelli I gives us\[
\mu(\limsup_{n\rightarrow\infty}\{\omega\colon|f_{n}(\omega)-f(\omega)|>\epsilon\})=0\]


Now\[
f_{n}(\omega)\not\rightarrow f(\omega)\Leftrightarrow\exists\epsilon>0\mbox{ s.t. for infinitely many }k,|f_{n}(\omega)-f(\omega)|>\epsilon\]
\[
\therefore\{\omega\colon f_{n}(\omega)\not\rightarrow f(\omega)\}=\bigcup_{m}\limsup_{n\rightarrow\infty}\{\omega\colon|f_{n}(\omega)-f(\omega)|>1/m\}\]
\[
\therefore\mu(\{\omega\colon f_{n}(\omega)\not\rightarrow f(\omega)\})\leq\sum_{m}\mu(\limsup_{n\rightarrow\infty}\{\omega\colon|f_{n}(\omega)-f(\omega)|>1/m\})=0\qedhere\]
\end{proof}


\subsection{The space $L^{1}$}

Recall that $\cL^{1}(S,\cS,\mu)=\{f\in\mS\colon\int\vert f\vert d\mu<\infty\}$.
This is a vector space and $f\mapsto\int fd\mu$ is a linear functional
on $\cL^{1}$.

Defining $\Vert f\Vert=\int\vert f\vert d\mu$ gives something which
almost satisfies the definition of a normed space, except that $\Vert f\Vert=0\not\Rightarrow f=0$,
only that $f=0$ almost everywhere. Such a space is called a \defterm{seminormed space}
and we can get a normed space by taking the subspace $W=\{f\in\cL^{1}\colon f=0\mbox{ a.e.}\}$
and letting $L^{1}(S,\cS,\mu)$ be the quotient space $\cL^{1}/W$.
You should check that this does give a well-defined normed space.

Now $\Vert f\Vert=\int\vert f\vert d\mu$ is a norm on $L^{1}$, and
$f\rightarrow\int fd\mu$ is still a well-defined linear functional
on $L^{1}$.

I don't promise to always be careful about distinguishing between
$\cL^{1}$ and $L^{1}$.


\subsection{Convergence in $L^{1}$}

We can define convergence in $L^{1}$ in the usual way for normed
spaces: $f_{n}$ \defterm{converges in $L^1$} to $f$ if $\Vert f_{n}-f\Vert\rightarrow0$,
or in other words $\int\vert f_{n}-f\vert d\mu\rightarrow0$. In probability,
this is called \defterm{convergence in mean}.

Note that this is not the same thing as simple convergence of the
means or integrals: $\int f_{n}d\mu\rightarrow\int fd\mu$ tells us
very little, and the $f_{n}$ can vary wildly so long as positive
and negative parts of $f_{n}-f$ cancel out. Considering $\vert f_{n}-f\vert$
prevents this. However, $f_{n}\rightarrow f$ in $L^{1}$ does imply
that $\int f_{n}d\mu\rightarrow\int fd\mu$ (an analyst would describe
this by saying that $\int\cdot\, d\mu$ is a continuous function $L^{1}\rightarrow\R$).

How does this relate to our earlier types of convergence? Convergence
almost everywhere does not imply $L^{1}$ convergence -- this is just
the fact from Analysis II that pointwise convergence does not imply
convergence of integrals. The example in Section \ref{subsec:convergence-in-measure}
shows that convergence in measure does not imply $L^{1}$ convergence,
and a slight modification of this example (taking each $f_{n}$ to
be the indicator of an interval, instead of $2^{k}$ times an indicator)
shows that $L^{1}$ convergence does not imply almost everywhere convergence.
However we do have: 

\begin{theorem}If $f_{n}\rightarrow f$ in $L^{1}$, then $f_{n}\rightarrow f$
in measure.\end{theorem}

\begin{proof}Given $\epsilon,\delta>0$, we can use $L^{1}$ convergence
to find $N$ s.t. for all $n>N$,

\[
\epsilon\delta>\int\vert f_{n}-f\vert d\mu\geq\epsilon\mu(\{\omega\colon\vert f_{n}(\omega)-f(\omega)\vert>\epsilon\})\]


Then\[
n>N\Rightarrow\mu(\{\omega\colon\vert f_{n}(\omega)-f(\omega)\vert>\epsilon\})<\delta\qedhere\]
\end{proof}

\begin{lemma}[Scheffé's Lemma]If $f_{n},f\in L^{1}$, $f_{n}\geq0$,
$f_{n}\rightarrow f$ a.e., and $\int f_{n}d\mu\rightarrow\int fd\mu$,
then $f_{n}\rightarrow f$ in $L^{1}$.\end{lemma}

\begin{proof}Consider the positive and negative parts of $f_{n}-f$
separately.

We have $0\leq(f_{n}-f)^{-}=(f-f_{n})^{+}\leq f$ a.e. (using $f_{n}\geq0$)
and $(f_{n}-f)^{-}\rightarrow0$ a.e. so by DCT, $\int(f_{n}-f)^{-}d\mu\rightarrow0$.

We are given that $\int(f_{n}-f)^{+}d\mu-\int(f_{n}-f)^{-}d\mu=\int(f-f_{n})d\mu\rightarrow0$,
so $\int(f_{n}-f)^{+}d\mu\rightarrow0$.

Now $\int\vert f-f_{n}\vert d\mu=\int(f_{n}-f)^{+}d\mu+\int(f_{n}-f)^{-}d\mu\rightarrow0$.\end{proof}


\section{Fubini's theorem}

%
\begin{framed}%
{[}1{]} Discussion of product measure and statement of Fubini's theorem.\end{framed}


\subsection{Product \titlesigma-fields}

Let $(S_{1},\cS_{1},\mu_{1}),(S_{2},\cS_{2},\mu_{2})$ be two finite
measure spaces.

We define a product $\sigma$-field $\cS$ on $S=S_{1}\times S_{2}$
in essentially the same way as we would define the product of topological
spaces, with continuous functions replaced by measurable: it is the
smallest $\sigma$-field on which the projections $\pi_{1},\pi_{2}$
are measurable; in other words it is $\sigma(A\times S_{2}\colon A\in\cS_{1},S_{1}\times B\colon B\in\cS_{2})$.

This will certainly contain $\cI=\{B_{1}\times B_{2}\colon B_{i}\in\cS_{i}\}$,
so $\cS=\sigma(\cI)$ (which again is like the definition of product
topology as the topology generated by products of open sets).


\subsection{Product measures}

This is the hard bit in this section.

Let $\mu_{1},\mu_{2}$ be finite measures on $(S_{1},\cS_{1}),(S_{2},\cS_{2})$.

To define the product measure $\mu$ on $(S,\cS)$, we start with
$\mu(B_{1}\times B_{2})=\mu_{1}(B_{1})\mu_{2}(B_{2})$ on $\cI$ (think
of our two starting spaces as $[0,1]$ so $S$ is the unit square,
and $\mu$ is area). Since $\cI$ is a $\pi$-system generating $\cS$,
there is at most one finite measure extending this.

If you were an applied mathematician, you might try to write the product
measure of a general set by integrating the measures of {}``slices''
through it:\[
\mu(A)=\int_{S_{1}}\mu_{2}(\{s_{2}\in S_{2}\colon(s_{1},s_{2})\in A\})\mu_{1}(ds_{1})\]
 or the same thing with 1 and 2 swapped.

We shall do the same, but we have to do some work with $d$-systems
and $\sigma$-fields to show that it is valid.

Let $J_{1A}(s_{1})=\mu_{2}(\{s_{2}\in S_{2}\colon(s_{1},s_{2})\in A\})$.
We need to check that the slices involved are measurable. This is
true because all $s_{1}$-slices through sets in $\cI$ are certainly
$\cS_{2}$-measurable, and the family of subsets of $S$ whose $s_{1}$-slices
are measurable is closed under complements and countable unions, so
is a $\sigma$-field, so contains $\sigma(\cI)$.

\begin{lemma}$J_{1A}$ is $\cS_{1}$-measurable for all $A\in\cS$.\end{lemma}

\begin{proof}Let $\cD=\{A\in\cS\colon J_{1A}\mbox{ is }\cS_{1}\mbox{-measurable}\}$.
We shall show that $\cD$ is a $d$-system.

Certainly $S\in\cD$.

If $A,B\in\cD$ with $A\supset B$ then $J_{1(A\setminus B)}=J_{1A}-J_{1B}$
is $\cS_{1}$-measurable, so $A\setminus B\in\cD$.

If $A_{n}\uparrow A$ and $A_{n}\in\cD$ then $J_{1A_{n}}\uparrow J_{1A}$
so $J_{1A}$ is $\cS_{1}$-measurable and $A\in\cD$.

So $\cD$ is a $d$-system; and it certainly contains the $\pi$-system
$\cI$, so $\cD\supset d(\cI)=\sigma(\cI)=\cS$.\end{proof}

Hence $\mu(A)=\int_{S_{1}}J_{1A}d\mu_{1}$ is well-defined.

It is finitely additive because $\mu_{2}$ is and because integration
is linear, and it is countably additive because if $A=\bigcup_{n}A_{n}$
($A_{n}$ pairwise disjoint) then\[
\sum_{j=1}^{n}\mu(A_{j})=\int_{S_{1}}\sum_{j=1}^{n}J_{1A_{j}}d\mu_{1}\uparrow\int_{S_{1}}\sum_{j=1}^{\infty}J_{1A_{j}}d\mu_{1}=\mu(A)\]
 by the Monotone Convergence Theorem.

So $\mu$ is a measure on $(S,\cS)$, it takes the right values on
$\cI$, and it is finite because $\mu(S)=\mu_{1}(S_{1})\mu_{2}(S_{2})<\infty$.

We could alternatively have defined $J_{2A}(s_{2})=\mu_{1}(\{s_{1}\in S_{1}\colon(s_{1},s_{2})\in A\}),\mu(A)=\int_{S_{2}}J_{2A}d\mu_{2}$,
and because there is a unique measure taking the right values on $\cI$,
this gives the same thing.

We have set this all up for finite measures, which is necessary in
order to use the uniqueness of extension lemma, but it can now be
extended to $\sigma$-finite measures $\mu_{1},\mu_{2}$ just by working
on an increasing sequence of finite subspaces whose union is all of
$S_{1}$ or $S_{2}$.


\subsection{Integration on product spaces}

The results of Fubini's and Tonelli's theorems tell us that a function
$f$ on the product space can be integrated by integrating it in one
variable first, then the other, provided that $f\geq0$ or $\vert f\vert$
is $\mu$-integrable. An important consequence is that it doesn't
matter which order the integrations are performed in.

The proofs of these are rather easy, now that we have shown how to
define the product measure by one-dimensional integrals.

\begin{theorem}[Tonelli's Theorem]If $f\colon S\rightarrow\R$ is
$\cS$-measurable and $f\geq0$ then\[
\int_{S}fd\mu=\int_{S_{1}}\left(\int_{S_{2}}f(s_{1},s_{2})\mu_{2}(ds_{2})\right)\mu_{1}(ds_{1})=\int_{S_{2}}\left(\int_{S_{1}}f(s_{1},s_{2})\mu_{1}(ds_{1})\right)\mu_{2}(ds_{2})\]
\end{theorem}

\begin{proof}We use the standard machine.

First suppose that $f$ is the indicator function of a $\cS$-measurable
set $A$. Then this is just the statement $\mu(A)=\int_{S_{1}}J_{1A}(s_{1})\mu_{1}(ds_{1})=\int_{S_{2}}J_{2A}(s_{2})\mu_{2}(ds_{2})$.

By linearity, the theorem holds for non-negative simple functions
on $(S,\cS)$.

For general $f\in\mSp$, take a sequence $f_{n}$ of nonnegative simple
functions s.t. $f_{n}\uparrow f$.

Then by monotone convergence, $\int_{S_{2}}f_{n}(s_{1},s_{2})\mu_{2}(ds_{2})\uparrow\int_{S_{2}}f(s_{1},s_{2})\mu_{2}(ds_{2})$
and so \[
\int_{S_{1}}\left(\int_{S_{2}}f_{n}(s_{1},s_{2})\mu_{2}(ds_{2})\right)\mu_{1}(ds_{1})\,\big\uparrow\int_{S_{1}}\left(\int_{S_{2}}f(s_{1},s_{2})\mu_{2}(ds_{2})\right)\mu_{1}(ds_{1})\]


(And similarly with 1 and 2 swapped.)

Also by monotone convergence, $\int_{S}f_{n}d\mu\uparrow\int_{S}fd\mu$.\end{proof}

\begin{theorem}[Fubini's Theorem]If $f\in\cL^{1}(S,\cS,\mu)$ (i.e.
$\int_{S}\vert f\vert d\mu<\infty$) then\[
\int_{S}fd\mu=\int_{S_{1}}\left(\int_{S_{2}}f(s_{1},s_{2})\mu_{2}(ds_{2})\right)\mu_{1}(ds_{1})=\int_{S_{2}}\left(\int_{S_{1}}f(s_{1},s_{2})\mu_{1}(ds_{1})\right)\mu_{2}(ds_{2})\]
\end{theorem}

\begin{proof}Just apply Tonelli's theorem to $f^{+}$ and $f^{-}$.\end{proof}

Note that the two theorems can be used together: to show that a general
$f$ satisfies the condition $\int_{S}\vert f\vert d\mu<\infty$ in
Fubini's theorem, check that $\int_{S_{1}}\left(\int_{S_{2}}\vert f\vert\mu_{2}(ds_{2})\right)\mu_{1}(ds_{1})<\infty$
and use Tonelli on $\vert f\vert$. In Cambridge, it is common to
combine the two theorems together and call them both Fubini's theorem.


\subsection{Borel-Cantelli from Tonelli}

Fubini's and Tonelli's theorems are more powerful than they may at
first appear (as indeed is true of a lot of measure theory), because
you can choose to apply it to a wide range of measure spaces. As an
illustration, we will derive the first Borel-Cantelli lemma from Tonelli.

Let $(\Omega,\cF,\P)$ be a probability space and $(\N,\wp(\N),\#)$
be the natural numbers with counting measure (i.e. $\mu(A)$ is simply
the number of elements of $A$; then $\int_{\N}fd\#=\sum_{n=1}^{\infty}f(n)$).

Given a sequence $(A_{n})$ of events in $\cF$, we define a function
$f:\Omega\times\N\rightarrow\R$ by $f(\omega,n)=I_{A_{n}}(\omega)$.

This is nonnegative, so Tonelli's theorem gives us\[
\begin{aligned}\int_{\Omega\times\N}fd(\P,\mu) & =\int_{\N}\int_{\Omega}fd\P d\#=\int_{\N}\P(A_{n})\#(dn)=\sum_{n=1}^{\infty}\P(A_{n})\\
 & =\int_{\Omega}\int_{\N}fd\#d\P=\int_{\Omega}\sum_{n=1}^{\infty}I_{A_{n}}d\P=\E(N)\end{aligned}
\]
 where $N(\omega)$ is the number of values $n\in\N$ s.t. $\omega\in A_{n}$.

The condition of BCI is that $\sum_{n=1}^{\infty}\P(A_{n})<\infty$.
Then we get that $\E(N)<\infty$, so $\P(N=\infty)=0$. But the event
$\{N=\infty\}$ is precisely $\limsup A_{n}$.


\section{Uniform integrability}

%
\begin{framed}%
{[}1{]} Uniform integrability.\end{framed}


\subsection{Definition of uniform integrability}

I shall only deal with probability spaces here because that is the
important case; at least some of this extends to $\sigma$-finite
measure spaces, but it becomes a bit more complicated.

A family $\{X_{\lambda}\}$ of random variables is \defterm{uniformly integrable}
if, for all $\epsilon>0$, there is some $K$ s.t. for all $\lambda$,\[
\int_{\vert X_{\lambda}\vert>K}\vert X_{\lambda}\vert d\P<\epsilon\]
Intuitively this says that the tails of the distributions of all the
random variables become small together. (Uniform integrability is
related to compactness in some way which I haven't figured out yet,
but note that the next theorem looks a bit like the Ascoli-Arzelà
theorem). Uniform integrability is defined for any set of random variables,
but we usually apply it to sequences.

The following theorem gives an equivalent characterisation which is
often more useful.

\begin{theorem}A family $\{X_{\lambda}\}$ of random variables is
uniformly integrable iff both the following conditions 

hold:

\begin{enumerate}[(i)]

\item The set $\{X_{\lambda}\}$ is bounded in $L^{1}$ (i.e. $\exists M$
s.t. $\forall\lambda\;\E(\vert X_{\lambda}\vert)<M$).

\item For every $\epsilon>0$, there is some $\delta>0$ s.t. for
all $\lambda$ and all events $A$ with $\P(A)<\delta$, we have\[
\int_{A}\vert X_{\lambda}\vert d\P<\epsilon\]


\end{enumerate}\end{theorem}

\begin{proof}First suppose that $\{X_{\lambda}\}$ is UI.

For (i), choose $K$ s.t. for all $\lambda$, \[
\int_{\vert X_{\lambda}\vert>K}\vert X_{\lambda}\vert d\P<1\]
Then $\E(\vert X_{\lambda}\vert)=\int_{\vert X_{\lambda}\vert\leq K}\vert X_{\lambda}\vert d\P+\int_{\vert X_{\lambda}\vert>K}\vert X_{\lambda}\vert d\P<K+1$.

For (ii), given $\epsilon>0$, choose $K$ as in the definition of
uniform integrability, and $\delta$ s.t. $K\delta<\epsilon$. Then
for $\P(A)<\delta$,\[
\int_{A}\vert X_{\lambda}\vert d\P=\int_{A\cap\{\vert X_{\lambda}\vert\leq K\}}\vert X_{\lambda}\vert d\P+\int_{A\cap\{\vert X_{\lambda}\vert>K\}}\vert X_{\lambda}\vert d\P<K\P(A)+\epsilon<2\epsilon\]


In the other direction, suppose that (i) and (ii) hold.

Given $\epsilon>0$, choose suitable $\delta$ as in (ii), and $M$
as in (i). Set $K=M/\delta$.

Now $M>\E(\vert X_{\lambda}\vert)\geq K\P(\vert X_{\lambda}\vert>K)$
so $\P(\vert X_{\lambda}\vert>K)<\delta$ for all $\lambda$. So putting
$A=\{\vert X_{\lambda}\vert>K\}$ in (ii) gives exactly what is required.\end{proof}


\subsection{Sufficient conditions for uniform integrability}

A single integrable random variable $X$ is UI since the random variables
$Z_{n}=\vert X\vert I_{\{\vert X|>n\}}$ are dominated by $X$ and
converge a.s. to $0$, so by DCT,\[
\int_{\vert X\vert>n}\vert X\vert d\P=\E(Z_{n})\rightarrow0\]


Any finite set $\{X_{1},\ldots,X_{n}\}$ of integrable r.v.s is UI
since for each $\epsilon>0$, we can find $K_{1},\ldots,K_{n}$ for
which $\int_{\vert X_{n}\vert>K_{n}}\vert X_{n}\vert d\P<\epsilon$,
then take $K=\max\{K_{1},\ldots,K_{n}\}$.

If there is some $X\in L^{1}$ s.t. $\vert X_{\lambda}\vert\leq\vert X\vert$
for all $\lambda$, then $\{X_{\lambda}\}$ is UI, since given $\epsilon>0$,
we may choose $K$ s.t. $\int_{\vert X\vert>K}\vert X\vert d\P<\epsilon$.
Then for each $\lambda$, $\{\omega\colon\vert X_{\lambda}\vert>K\}\subset\{\omega\colon\vert X\vert>K\}$,
so\[
\int_{\vert X_{\lambda}|>K}\vert X_{\lambda}\vert d\P\leq\int_{\vert X|>K}\vert X_{\lambda}\vert d\P\leq\int_{\vert X|>K}\vert X\vert d\P<\epsilon\]


If $\{X_{\lambda}\}$ and $\{Y_{\lambda'}\}$ are UI, then $\{X_{\lambda}+Y_{\lambda'}\}$
is UI, by the alternative characterisation.


\subsection{$L^{1}$ convergence and uniform integrability}

\begin{theorem}A sequence $(X_{n})$ of integrable random variables
converges to $X$ in $L^{1}$ iff $X_{n}\rightarrow X$ in probability
and $\{X_{n}\}$ is UI.\end{theorem}

\begin{proof}First suppose that $X_{n}\rightarrow X$ in $L^{1}$. 

Then $X\in L^{1}$ so $\{X_{n}-X\}$ UI implies that $\{X_{n}\}$
is UI, so we may assume wlog that $X=0$.

We already know that $X_{n}\rightarrow0$ in probability.

Given $\epsilon>0$, we can choose $N$ s.t. $n>N\Rightarrow\E(\vert X_{n}\vert)<\epsilon$,
so certainly $\int_{\vert X_{n}\vert>K}\vert X_{n}\vert d\P<\epsilon$
for any $K$. 

So we just have to choose $K$ s.t.$\int_{\vert X_{n}\vert>K}\vert X_{n}\vert d\P<\epsilon$
for $1\leq n\leq N$, which we can do since the finite set $\{X_{1},\ldots,X_{N}\}$
is UI.\medskip{}


Now suppose that $X_{n}\rightarrow X$ in probability and $\{X_{n}\}$
is UI.

First we show that $X\in L^{1}$ (which seems to take several lines,
but they are quite easy).

Take a subsequence $(X_{n_{k}})$ s.t. $X_{n_{k}}\rightarrow X$ almost
surely.

Let $Y_{n_{k}}=\min\{X_{n_{k}}^{+},X^{+}\}$ so $Y_{n_{k}}\uparrow X^{+}$
a.s. and by MCT $\E(Y_{n_{k}})\uparrow\E(X^{+})$.

$\E(Y_{n_{k}})\leq\E(\vert X_{n_{k}}\vert)\leq M$ for some $M$ since
$\{X_{n_{k}}\}$ is UI, so $\E(X^{+})\leq M$.

In particular, $\E(X^{+})<\infty$ and likewise $\E(X^{-})<\infty$
so $X\in L^{1}$.\medskip{}


Hence $\{X_{n}\}$ UI implies that $\{X_{n}-X\}$ is UI, so we may
assume wlog that $X=0$.

Given $\epsilon>0$, choose $\delta$ s.t. $\P(A)<\delta\Rightarrow\int_{A}\vert X_{n}\vert d\P<\epsilon$.

Then, by convergence in probability, choose $N$ s.t. $n>N\Rightarrow\P(\vert X_{n}\vert>\epsilon)<\delta$.

Now for $n>N$, we have \[
\E(\vert X_{n}\vert)=\int_{\vert X_{n}\vert\leq\epsilon}\vert X_{n}\vert d\P+\int_{\vert X_{n}\vert>\epsilon}\vert X_{n}\vert d\P<\epsilon\P(\vert X_{n}\vert\leq\epsilon)+\epsilon<2\epsilon\qedhere\]
\end{proof}

Because a sequence dominated by an integrable r.v. is UI, this theorem
strengthens the Dominated Convergence Theorem to require only convergence
in probability rather than almost sure convergence.


\section{Inequalities and Banach spaces}

%
\begin{framed}%
{[}3{]} Chebyshev's inequality, tail estimates. Jensen's inequality.
Completeness of $L^{p}$ for $1\leq p\leq\infty$. The Hölder and
Minkowski inequalities.\end{framed}




\subsection{Chebyshev's inequality}

\begin{theorem}[Chebyshev's Inequality]If $f$ is a measurable function
$S\rightarrow\R$ then \[
\mu(\{\omega\colon\vert f(\omega)\vert\geq t\})\leq\frac{1}{t^{2}}\int_{S}f^{2}d\mu\]
\end{theorem}

\begin{proof}\[
\int_{S}f^{2}d\mu\geq\int_{\vert f\vert\geq t}f^{2}d\mu\geq t^{2}\mu(\{\omega\colon\vert f(\omega)\vert\geq t\})\qedhere\]
\end{proof}

In the probability case where $X$ is a random variable, this becomes
$\P(|X-\E X|\geq t)\leq\frac{1}{t^{2}}\var(X)$, where $\var(X)$
has the usual definition of $\E((X-\E X)^{2})$.


\subsection{Jensen's inequality}

Jensen's inequality is an important result concerning the averaging
of convex functions. A \defterm{convex function} is a function $\varphi:\R\rightarrow\R$
s.t. whenever $0\leq a,b\leq1$ and $a+b=1$, $\varphi(ax+by)\leq a\varphi(x)+b\varphi(y)$.
It is often easiest to test this using the fact that twice-differentiable
function is convex iff $\varphi''(x)\geq0$ for all $x$, or just
by drawing a graph.

Note that this result holds only in probability spaces; it cannot
even be generalised (like most of the results I have given for probability
spaces) to finite measure spaces.

\begin{theorem}[Jensen's Inequality]If $X$ is an integrable random
variable and $\varphi$ a measurable convex function $\R\rightarrow\R$,
then \[
\varphi(\E(X))\leq\E(\varphi(X))\]
\end{theorem}

\begin{proof}Properly we need a condition that $\E(\varphi(X))$
exists.

The key step in the proof is that through every point $(x,\varphi(x))$
in the graph of $\varphi$, there is a line which is always below
or on the graph. If $\varphi$ is differentiable at $x$, this is
just the tangent. If not, then we have to work a bit harder.

Given $z\in\R$, define $\psi_{z}(x)={\displaystyle \frac{\varphi(x)-\varphi(z)}{x-z}}$
for $x\neq z$.

From the definition of convexity, $\psi_{z}$ is increasing, and in
particular, if $x_{1}<z<x_{2}$, then $\psi_{z}(x_{1})\leq\psi_{z}(x_{2})$.

Set $\alpha_{z}={\displaystyle \sup_{x<z}}\psi_{z}(x)$ and $\beta_{z}$
s.t. the line $y=\alpha_{z}x+\beta_{z}$ goes through $(z,\varphi(z))$.

Then $\psi_{z}(x)\leq\alpha_{z}$ for all $x<z$ and $\psi_{z}(x)\geq\alpha_{z}$
for all $x>z$, so $\alpha_{z}x+\beta_{z}\leq\varphi(x)$ for all
$x$.

Now apply this result with $z=\E(X)$.

By the choice of $\beta_{z}$, we have $\varphi(\E(X))=\varphi(z)=\alpha_{z}z+\beta_{z}=\alpha_{z}\E(X)+\beta_{z}$.

But also $\alpha_{z}x+\beta_{z}\leq\varphi(x)$ for all x, so taking
expectations,\[
\varphi(\E(X))=\alpha_{z}\E(X)+\beta_{z}\leq\E(\varphi(X))\qedhere\]
\end{proof}


\subsection{Hölder's inequality}

There are many proofs of this important inequality. Analysts like
to prove it again and again, once for finite sequences, once for infinite
sequences ($l^{p}$ spaces), once for integrable functions ($L^{p}$
spaces). The measure theoretic version gives us all of these at once,
by taking a suitable underlying measure space (a finite set with counting
measure, $\N$ with counting measure, Lebesgue measure). This proof
uses Jensen's inequality, but on a specially defined probability measure,
so the theorem still holds for general $\sigma$-finite measure spaces.

\begin{theorem}[Hölder's Inequality]If $f,g\in\mS$, $1<p,q$ and
$p^{-1}+q^{-1}=1$, then\[
\int\vert fg\vert d\mu\leq\left(\int\vert f\vert^{p}d\mu\right)^{1/p}\left(\int\vert g\vert^{q}d\mu\right)^{1/q}\]
\end{theorem}

\begin{proof}All the functions we are integrating are all nonnegative,
so there is no need to worry about whether the integrals exist (provided
we allow the value $+\infty$).

The inequality is obvious if $\int\vert g\vert^{q}d\mu$ is $0$ or
$\infty$.

Otherwise, we define a probability measure $\mu_{g}$ on $(S,\cS)$
by\[
\mu_{g}(A)=\frac{\int I_{A}\vert g\vert^{q}d\mu}{\int\vert g\vert^{q}d\mu}\]


(this is countably additive by MCT) so that, applying the standard
machine,\[
\int fd\mu_{g}=\frac{\int f\vert g\vert^{q}d\mu}{\int\vert g\vert^{q}d\mu}\]


The function $\varphi(x)=x^{p}$ is convex for $x\geq0$, so applying
Jensen to $\varphi$ and the function $\vert fg^{1-q}\vert$ we get\[
\left(\int\vert fg^{1-q}\vert d\mu_{g}\right)^{p}\leq\int\vert fg^{1-q}\vert^{p}d\mu_{g}\]


The rest is just simplifying this, using the fact that $p+q-pq=0$.\[
\left(\frac{\int\vert f\vert\vert g\vert^{1-q}\vert g\vert^{q}d\mu}{\int\vert g\vert^{q}d\mu}\right)^{p}\leq\frac{\int\vert f\vert^{p}\vert g\vert^{(1-q)p}\vert g\vert^{q}d\mu}{\int\vert g\vert^{q}d\mu}\]


\[
\therefore\left(\int\vert f\vert\vert g\vert d\mu\right)^{p}\leq\left(\int\vert f\vert^{p}\vert g\vert^{p+q-pq}d\mu\right)\left(\int\vert g\vert^{q}d\mu\right)^{p-1}\]
\[
\therefore\int\vert fg\vert d\mu\leq\left(\int\vert f\vert^{p}d\mu\right)^{1/p}\left(\int\vert g\vert^{q}d\mu\right)^{1/q}\qedhere\]
\end{proof}


\subsection{The space $L^{p}$}

For $1<p<\infty$ and $f\in\mS$, define the \defterm{$L^p$ norm}
by $\Vert f\Vert_{p}=\left(\int\vert f\vert^{p}d\mu\right)^{1/p}$.

Then let the space of \defterm{$p$-integrable functions} be $\cL^{p}(S,\cS,\mu)=\{f\in\mS\colon\int\vert f\vert^{p}d\mu<\infty\}$.

We need to check that this is a vector space, and in particular that
it is closed under addition. This holds because $\vert f+g\vert^{p}\leq(2\max(\vert f\vert,\vert g\vert))^{p}\leq2^{p}(\vert f\vert^{p}+\vert g\vert^{p})$.

Now we form a normed space $L^{p}(S,\cS,\mu)$ in the same way as
we formed $L^{1}$ from $\cL^{1}$: let $W=\{f\in\cL^{p}\colon f=0\mbox{ a.e.}\}$
and $L^{p}=\cL^{p}/W$.

To show that $\Vert\cdot\Vert_{p}$ is a norm on $L^{p}$, we just
need to check the triangle inequality. This is given by:

\begin{theorem}[Minkowski's Inequality]If $f,g\in\mS,1<p<\infty$,
then $\Vert f+g\Vert_{p}\leq\Vert f\Vert_{p}+\Vert g\Vert_{p}$.\end{theorem}

\begin{proof}If $\int\vert f+g\vert^{p}d\mu=0$ the inequality is
obvious; if it is $\infty$, then so is the RHS, because $\cL^{p}$
is closed under addition.

Otherwise, set $q$ s.t. $p^{-1}+q^{-1}=1$. Then by Hölder's inequality,\[
\int\vert f\vert\vert f+g\vert^{p-1}d\mu\leq\left(\int\vert f\vert^{p}d\mu\right)^{1/p}\left(\int\vert f+g\vert^{(p-1)q}d\mu\right)^{1/q}\]


so \begin{align*}
\int\vert f+g\vert^{p}d\mu & \leq\int\vert f\vert\vert f+g\vert^{p-1}d\mu+\int\vert g\vert\vert f+g\vert^{p-1}d\mu\\
 & \leq\left(\left({\textstyle \int}\vert f\vert^{p}d\mu\right)^{1/p}+\left({\textstyle \int}\vert g\vert^{p}d\mu\right)^{1/p}\right)\left({\textstyle \int}\vert f+g\vert^{p}d\mu\right)^{1/q}\end{align*}


and we simply divide through by $\left({\textstyle \int}\vert f+g\vert^{p}d\mu\right)^{1/q}$.\end{proof}


\subsection{Completeness of $L^{p}$}

The spaces $L^{p}\;(1\leq p<\infty)$ are in fact Banach spaces (i.e.
complete normed spaces).

\begin{theorem}If $1\leq p<\infty$ and $f_{n}$ is a Cauchy sequence
in $L^{p}$ then there exists $f\in L^{p}$ s.t. $f_{n}\rightarrow f$
in $L^{p}$.\end{theorem}

\begin{proof}%
\begin{comment}
Should number sections to make structure clearer.
\end{comment}
{}We begin by showing that $f_{n}$ is {}``Cauchy in measure''.

Given $\epsilon,\delta>0$, choose $N$ s.t. $m,n>N\Rightarrow\Vert f_{m}-f_{n}\Vert_{p}<\delta^{1/p}\epsilon$.

Now $\Vert f_{m}-f_{n}\Vert_{p}^{p}\geq\epsilon^{p}\mu(\{\omega\colon\vert f_{m}(\omega)-f_{n}(\omega)\vert>\epsilon\})$
so $m,n>N\Rightarrow\mu(\{\omega\colon\vert f_{m}(\omega)-f_{n}(\omega)\vert>\epsilon\})<\delta$.

\medskip{}


We earlier had a theorem that if a sequence converges in measure,
then a subsequence converges almost everywhere (compare the next part
of this proof to the proof of that theorem). In fact, it is sufficient
for the sequence to be Cauchy in measure.

Choose a subsequence $(f_{n_{k}})$ s.t. $m,n\geq n_{k}\Rightarrow\mu(\{\omega\colon\vert f_{m}(\omega)-f_{n}(\omega)\vert>2^{-k}\})<2^{-k}$,
so that\[
\sum_{k}\mu(\{\omega\colon\vert f_{n_{k}}(\omega)-f_{n_{k+1}}(\omega)\vert>2^{-k}\})<\infty\]
 and so by Borel-Cantelli I, $\mu(A)=0$ where\[
A=\limsup_{k\rightarrow\infty}\{\omega\colon\vert f_{n_{k}}(\omega)-f_{n_{k+1}}(\omega)\vert>2^{-k}\}\]


Unpacking the definition of $A$ says that if $\omega\in A^{c}$,
then there is some $k$ (depending on $\omega$) s.t. $j\geq k\Rightarrow\vert f_{n_{j}}(\omega)-f_{n_{j+1}}(\omega)\vert\leq2^{-j}$,
and so $i,j\geq k\Rightarrow\vert f_{n_{i}}(\omega)-f_{n_{j}}(\omega)\vert\leq\sum_{j\geq k}2^{-j}=2^{-k+1}$.

Hence for $\omega\in A^{c}$, the sequence $(f_{n_{k}}(\omega))$
is Cauchy (in $\R$), so has a limit.

\medskip{}


Define $f(\omega)=\limsup f_{n_{k}}(\omega)$. This is measurable,
and if $\omega\in A^{c}$ then $f(\omega)=\lim f_{n_{k}}(\omega)$
so $f_{n_{k}}\rightarrow f$ almost everywhere.

We need to check that $f\in L^{p}$. This follows from Fatou since
$\vert f\vert^{p}=\liminf_{k}\vert f_{n_{k}}\vert^{p}$ a.e., so $\int\vert f\vert^{p}d\mu\leq\liminf_{k}\int\vert f_{n_{k}}\vert^{p}d\mu$
and $\int\vert f_{n_{k}}\vert^{p}d\mu\leq(\Vert f_{n_{k}}-f_{n_{1}}\Vert_{p}+\Vert f_{n_{1}}\Vert_{p})^{p}\leq(1+\Vert f_{n_{1}}\Vert_{p})^{p}$
for all $k$.

\medskip{}


Finally we show that $\Vert f_{n}-f\Vert_{p}\rightarrow0$.

Given $\epsilon>0$, choose $k$ s.t. $m,n\geq n_{k}\Rightarrow\Vert f_{n}-f_{m}\Vert_{p}<\epsilon$.

For $m\geq n_{k}$, $\vert f_{m}-f\vert^{p}=\lim_{k}\vert f_{m}-f_{n_{k}}\vert^{p}=\liminf_{k}\vert f_{m}-f_{n_{k}}\vert^{p}$
a.e. so by Fatou, \[
\int\vert f_{m}-f\vert^{p}d\mu\leq\liminf_{k\rightarrow\infty}\int\vert f_{m}-f_{n_{k}}\vert^{p}d\mu\leq\epsilon^{p}\]


So $m\geq n_{k}\Rightarrow\Vert f_{m}-f\Vert_{p}\leq\epsilon$.\end{proof}


\subsection{The space \texorpdfstring{$L^\infty$}{L-infinity} }

There is one more space to consider: the space $L^{\infty}$ of essentially
bounded functions.

A function $f\in\mS$ is \defterm{essentially bounded} if there is
some $K$ s.t. $\mu(\{\omega\colon\vert f\vert>K\})=0$.

We define a norm (the \defterm{essential supremum}) by $\Vert f\Vert_{\infty}={\displaystyle \inf_{N\in\cS,\mu(N)=0}\sup_{\omega\not\in N}\vert f(\omega)\vert}$.

Let $\cL^{\infty}$ be the set of essentially bounded functions $(S,\cS)\rightarrow\R$,
and identify a.e.-equal functions to form the quotient $L^{\infty}$
as before. $\Vert\cdot\Vert_{\infty}$ is a norm on $L^{\infty}$;
the triangle inequality is a piece of straightforward analysis.

A sequence $f_{n}\rightarrow f$ in $L^{\infty}$ iff there is a null
set $N$ s.t. $f_{n}\rightarrow f$ uniformly on $S\backslash N$
(this uses the fact that a countable union of null sets is null).
The relationship between $L^{\infty}$ convergence and uniform convergence
is the same as the relationship between almost everywhere convergence
and pointwise convergence.

We can use this to show that $L^{\infty}$ is complete, by showing
that a Cauchy sequence in $L^{\infty}$ is uniformly Cauchy except
on a null set, then using the completeness of the uniform norm.


\section{$L^{2}$ and conditional expectation}

%
\begin{framed}%
{[}1{]} $L^{2}$ as a Hilbert space. Orthogonal projection, relation
with conditional probability. Variance and covariance.\end{framed}


\subsection{Conditional probability}

In elementary probability, for an event $B$ with $\P(B)>0$, and
for any event $A$, we define the \defterm{conditional probability of $A$ given $B$}
as\[
\P(A|B)=\frac{\P(A\cap B)}{\P(B)}\]


Suppose we perform an experiment with a finite set of possible outcomes,
with events $B_{1},\ldots,B_{n}$ corresponding to each outcome (these
events are disjoint and cover $\Omega$, and must all have non-zero
probability). After gaining this information, we want to know the
probability of some other event $A$; this will be $\P(A|B_{j})$
for the appropriate $j$. Hence our guess as to the probability of
$A$ after the experiment is itself a random variable:\[
g(\omega)=\P(A\cap B_{j})/\P(B_{j})\mbox{ when }\omega\in B_{j}\]


Now consider a more sophisticated experiment, where the set of possible
outcomes may be infinite and may contain zero-probability events.
Let $\cG$ be the set of all events for which the experiment tells
us whether they occur or not; these form a sub-$\sigma$-field of
$\cF.$ (In the above finite case, $\cG=\sigma(B_{1},\ldots,B_{n})$
is the set of all possible unions of the $B_{j}$. If the experiment
measures some random variable $X$, then $\cG=\sigma(X)$.)

Again, we want a random variable $g$ which gives the probability
of $A$ after knowing the results of this experiment.

The value of $g$ must of course depend only on events in $\cG$;
for example, in the case $\cG=\sigma(B_{1},\ldots,B_{n})$, $g$ is
constant on each $B_{j}$. This condition is made precise by saying
that $g$ must be $\cG$-measurable (note that since $\cG\subset\cF$,
this is a stronger condition than being $\cF$-measurable).

Secondly, consider $\P(A\cap B)$ for any $B\in\cG$. Once we have
performed the experiment, we know either that $B$ did not occur,
so $A\cap B$ certainly does not occur, or $B$ did occur, in which
case $A\cap B$ occurs with conditional probability $g(\omega)$.
If we add (integrate) this for all $\omega$, then we should get $\P(A\cap B)$:
$\int_{B}gd\P=\P(A\cap B)$.

\medskip{}


So we define a \defterm{(version of the) conditional probability of $A$ given $\cG$}
to be a random variable $\P(A|\cG)$ s.t.
\begin{enumerate}
\item $\P(A|\cG)$ is $\cG$-measurable
\item For any $B\in\cG$, $\int_{B}\P(A|\cG)d\P=\P(A\cap B)$
\end{enumerate}
It is not at all obvious that such a random variable exists in general,
or that it is unique (hence the need to talk about versions); we shall
worry about this later.


\subsection{Conditional expectation}

If we fix $\cG$ and $\omega$, and allow $A$ to vary, then $\P(A|\cG)(\omega)$
gives a probability measure on $(\Omega,\cF)$. We can integrate with
respect to this measure to get the conditional expectation of a random
variable $X$:\[
\E(X|\cG)(\omega)=\int_{\Omega}Xd(\P(-|\cG)(\omega))\]


Now fixing $X$ and considering this as a function of $\omega$, we
get a new random variable $\E(X|\cG)$. This will have the properties
(these follow from the corresponding properties for conditional probability,
by the standard machine):
\begin{enumerate}
\item $\E(X|\cG)$ is $\cG$-measurable
\item For any $B\in\cG$, $\int_{B}\E(X|\cG)d\P=\int_{B}Xd\P$
\end{enumerate}
We define a \defterm{(version of the) conditional expectation of $X$ given $\cG$}
to be a random variable with these two properties.

Again it is not clear that such a random variable exists. And it is
only unique up to almost sure equality: if $g$ is a version of $\E(X|\cG)$
and $f$ a $\cG$-measurable r\@.v\@. which is zero almost surely,
then $g+f$ is still a version of $\E(X|\cG)$.

However, if $g_{1},g_{2}$ are two versions of $\E(X|\cG)$, then
let $B=\{\omega:g_{1}(\omega)\geq g_{2}(\omega)+\epsilon\}$. $B\in\cG$
since $g_{1},g_{2}$ are $\cG$-measurable so $\int_{B}g_{1}d\P=\int_{B}Xd\P=\int_{B}g_{2}d\P$
but $\int_{B}(g_{1}-g_{2})d\P\geq\epsilon\P(B)$ so $\P(B)=0$ for
any $\epsilon$. Hence $g_{1}=g_{2}$ almost surely.


\subsection{$L^{2}$ as a Hilbert space}

We shall prove the existence of conditional expectation for square-integrable
random variables, by exploiting the fact that $L^{2}(\Omega,\cF,\P)$
is a Hilbert space i.e. its norm is given by an inner product. (Linear
Analysis yields more light on why this is the case, specifically that
$L^{2}$ is self-dual). The inner product is \[
\left\langle f,g\right\rangle =\int fgd\mu\]
 which is finite for $f,g\in L^{2}$ by Hölder (the case $p=q=2$,
often called the Schwarz or Cauchy-Schwarz inequality).

In the case of probability, the inner product has an interpretation
in terms of covariance: the \defterm{covariance} of $X,Y\in L^{2}$
is $\cov(X,Y)=\left\langle X-\E X,Y-\E Y\right\rangle =\left\langle X,Y\right\rangle -\E(X)\E(Y)$.

The \defterm{variance} of a random variable is $\var(X)=\cov(X,X)=\Vert X-\E X\Vert_{2}^{2}$,
which is finite iff $X\in L^{2}$.

The benefit of Hilbert space is that we can apply geometrical ideas.
In particular there is an idea of orthogonality: $f,g\in L^{2}$ are
\defterm{orthogonal} if $\left\langle f,g\right\rangle =0$. We also
have the parallelogram law: \[
\Vert f+g\Vert^{2}+\Vert f-g\Vert^{2}=2(\Vert f\Vert^{2}+\Vert g\Vert^{2})\]



\subsection{Orthogonal projection}

An important geometrical property of Hilbert spaces is the following,
proved in Linear Analysis:

\begin{theorem}If $G$ is a closed subspace of a Hilbert space $H$,
then there is a unique continuous linear map $\pi:H\rightarrow G$
s.t. $\left\langle f-\pi f,g\right\rangle =0$ for all $f\in H,g\in G$.
This map has the properties:
\begin{enumerate}
\item $\Vert f-\pi f\Vert\leq\Vert f-g\Vert$ for all $g\in G$
\item $\pi g=g$ for all $g\in G$
\item $\left\langle \pi f,g\right\rangle =\left\langle f,\pi g\right\rangle $
for all $f,g\in H$
\end{enumerate}
\end{theorem}

This map $\pi$ is called the \defterm{orthogonal projection} from
$H$ to $G$. Note that {}``$G$ a closed subspace'' means that
$G$ must be closed in the topology on $H$ and must be a subspace
of $H$ as a vector space.

Work with $H=L^{2}(\Omega,\cF,\P)$ and let $\cG$ be a sub-$\sigma$-field
of $\cF$. The space $G=L^{2}(\Omega,\cG,\P)$ is a closed subspace
of $H$ (closed because it is complete), so we may let $\pi$ be the
orthogonal projection $H\rightarrow G$.

For any $X\in H$, $\pi(X)$ is $\cG$-measurable since $\pi(X)\in G$.
And for any $B\in\cG$, $I_{B}\in G$ so\[
\int_{B}\pi(X)d\P=\left\langle I_{B},\pi(X)\right\rangle =\left\langle \pi(I_{B}),X\right\rangle =\left\langle I_{B},X\right\rangle =\int_{B}Xd\P\]


Hence $\pi(X)$ is a conditional expectation of $X$ given $\cG$.
Since we are working with $L^{2}$ rather than $\cL^{2}$, this is
only defined up to almost sure equality, corresponding to the uniqueness
property of conditional expectation.

Intuitively, a projection is an operation into a subspace which discards
information lying outside that subspace: for example, consider $\R^{n}$
with basis $\{e_{1},\ldots,e_{n}\}$. The orthogonal projection onto
the subspace generated by $\{e_{1},\ldots,e_{m}\}$ corresponds to
throwing away coordinates after the $m$-th. In the conditional expectation
case, $\pi$ is throwing away information not contained in the $\sigma$-field
$\cG$.

The property $\Vert X-\E(X|\cG)\Vert_{2}\leq\Vert X-Y\Vert_{2}$ for
all $Y\in G$ shows that for $X\in L^{2}$, $\E(X|\cG)$ is the best
estimate we can give for $X$ after knowing the information represented
by $\cG$, if we measure {}``best'' by minimising $\E(\vert X-Y\vert^{2})$.


\section{Ergodicity}

%
\begin{framed}%
{[}4{]} The strong law of large numbers, proof for independent random
variables with bounded fourth moments. Measure preserving transformations,
Bernoulli shifts. Statements {*}and proofs{*} of maximal ergodic theorem
and Birkhoff's almost everywhere ergodic theorem, proof of the strong
law.\end{framed}


\subsection{Strong law of large numbers}

\begin{theorem}[Strong law of large numbers]If $X_{n}$ are i.i.d.
r.v.s with $\E\vert X_{1}\vert<\infty$ then\[
\overline{X}_{n}=\frac{X_{1}+\ldots+X_{n}}{n}\rightarrow\E X_{1}\mbox{ almost surely.}\]
\end{theorem}

The strong law of large numbers tells us that if we take finite samples
from some probability distribution, as we increase the sample size,
the sample mean converges almost surely to the expectation of the
distribution. This is important because it justifies the intuitive
understanding of expectation and many applications in statistics.

The weak law is a strictly weaker result than the strong law: it says
that, with the same hypothesis, the sample mean converges in probability
to the expectation. It may still be useful because it has a simpler
proof than the strong law. Indeed it is non-trivial that $\{\omega\colon\overline{X}_{n}\rightarrow\E X_{1}\}$
is measurable; this holds because $\overline{X}_{n}$ is certainly
measurable, so $\limsup_{n}\overline{X}_{n},\liminf_{n}\overline{X}_{n}$
are measurable, and so $\{\limsup\overline{X}_{n}=\liminf\overline{X}_{n}=\E X_{1}\}$
is measurable. This is not a problem for the weak law, which only
talks about events $\{\vert\overline{X}_{n}-\E X_{1}\vert>\epsilon\}$.

There are many proofs of the strong law, which vary in the conditions
they require and techniques they use. We begin with an easy proof,
subject to the assumption that the random variables have bounded fourth
moments. Note that this proof does not require the variables to be
identically distributed; the condition that $\E X_{n}=0$ is just
for simplicity and can be obtained by translating.

\begin{theorem}If $X_{n}$ are independent r.v.s with $\E X_{n}=0$
and $\E(X_{n}^{4})<c<\infty$ then $\overline{X}_{n}\rightarrow0$
a.s.\end{theorem}

\begin{proof}Given $\epsilon>0$, we show that $\P(\vert\overline{X}_{n}\vert>\epsilon\mbox{ infinitely often})=0$.
Then we are done because $\overline{X}_{n}\not\rightarrow0\Leftrightarrow((\overline{X}_{n}>\vert j^{-1}\vert\mbox{ infinitely often})\mbox{ for some }j\in\N)$,
expressing $\overline{X}_{n}\not\rightarrow0$ as a countable union
of probability $0$ events.

Let $S_{n}=X_{1}+\ldots+X_{n}$ and consider $S_{n}^{4}=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}X_{i}X_{j}X_{k}X_{l}$.

If there is one of $i,j,k,l$ not equal to any of the rest (say $i$)
then by independence, $\E(X_{i}X_{j}X_{k}X_{l})=\E(X_{i})\E(X_{j}X_{k}X_{l})=0$.

So the only non-zero terms in the expansion of $\E(S_{n}^{4})$ have
form $\E(X_{i}^{2}X_{j}^{2})$ or $\E(X_{i}^{4})$.

By Hölder, $\E(X_{i}^{2}X_{j}^{2})\leq\left(\E(X_{i}^{4})\right)^{1/2}\left(\E(X_{j}^{4})\right)^{1/2}<c$.

There are $3n(n-1)$ terms $X_{i}^{2}X_{j}^{2}$ in $S_{n}^{4}$ and
$n$ terms $X_{i}^{4}$, so we get $\E(S_{n}^{4})<3n^{2}c$.

Now $\epsilon^{4}n^{4}\P(S_{n}^{4}>\epsilon^{4}n^{4})\leq\E(S_{n}^{4})<3n^{2}c$.

So $\P(\vert S_{n}\vert/n>\epsilon)<3c\epsilon^{-4}n^{-2}$ and $\sum_{n}\P(\vert S_{n}\vert/n>\epsilon)<3c\epsilon^{-4}\sum n^{-2}<\infty$.

Borel-Cantelli I gives us $\P(\limsup\{\vert\overline{X}_{n}\vert>\epsilon\})=0$.\end{proof}


\subsection{Measure-preserving transformations}

A \defterm{measure-preserving transformation} is a measurable function
$T:(S,\cS,\mu)\rightarrow(S,\cS)$ s.t. $\mu(T^{-1}A)=\mu(A)$ for
all $A\in\cS$. (Measurability of $T$ ensures that $T^{-1}A$ is
always measurable. Note that the definition contains $T^{-1}$ rather
than $T$.)

We can restate this definition in terms of measurable functions on
$(S,\cS)$ using the standard machine: for any $A\in\cS$, $\omega\in T^{-1}A\Leftrightarrow T\omega\in A$
so \[
\int I_{A}d\mu=\int I_{T^{-1}A}d\mu=\int(I_{A}\circ T)d\mu\]
Linearity and monotone convergence give us $\int fd\mu=\int(f\circ T)d\mu$
for all measurable $f\colon S\rightarrow\R$. The converse is also
true: if $\int fd\mu=\int(f\circ T)d\mu$ for all measurable $f\colon S\rightarrow\R$
then $f$ is measure-preserving.

A measurable set $A$ is \defterm{$T$-invariant} if $\mu(A\triangle T^{-1}A)=0$
($\triangle$ is symmetric difference). In other words, $A$ is almost
the same as $T^{-1}A$, except for a null set. Note that if $\mu$
is finite then the $T$-invariant sets form a $\sigma$-field.


\subsection{Stationary sequences}

An important example of measure-preserving transformations comes from
stationary sequences.

A sequence of random variables $(X_{n})$ is \defterm{stationary}
if $(X_{n})_{n\geq1}$ has the same distribution as $(X_{n+1})_{n\geq1}$.

Examples of stationary sequences are any i.i.d. sequence and the values
of an aperiodic positive-recurrent Markov chain with an invariant
distribution as the initial distribution.

Instead of considering $(X_{n})$ as a sequence of functions $\Omega\rightarrow\R$,
it is convenient to consider it as a single function taking values
in $\R^{\N}$, the space of real-valued sequences. We use the product
$\sigma$-field $B(\R^{\N})$ on $\R^{\N}$; this is defined as the
smallest $\sigma$-field on which all the projection maps (picking
out one element of the sequence) are measurable; since we are taking
a product of only countably many copies of $\R$, this is the same
as the $\sigma$-field generated by sets of the form $\prod_{n=1}^{\infty}A_{n}$
where $A_{n}\in B(\R)$. Hence we can define a \defterm{random sequence}
to be a function $X\colon(\Omega,\cF,\P)\rightarrow\R^{\N}$ which
is measurable w.r.t. $B(\R^{\N})$. Then $X=(X_{1},X_{2},\ldots)$
is a random sequence iff $X_{1},X_{2},\ldots$ are random variables.

To obtain a measure-preserving transformation from a stationary sequence,
consider the \defterm{Bernoulli shift}: the map $S:\R^{\N}\rightarrow\R^{\N}$
which throws away the first element of the sequence, i.e. $S(x_{1},x_{2},\ldots)=(x_{2},x_{3},\dots)$.
Note that this need not correspond to any transformation on the original
probability space $\Omega$ (i.e. there need not be any transformation
$T:\Omega\rightarrow\Omega$ such that $X\circ T=S\circ X$).

Nevertheless, the sequence $X$ induces a measure $\P\circ X^{-1}$
on $(\R^{\N},B(\R^{\N}))$. We can then consider the Bernoulli shift
as a transformation $(\R^{\N},B(\R^{\N}),\P\circ X^{-1})\rightarrow(\R^{\N},B(\R^{\N}))$.
$S$ is always measurable w.r.t. $B(\R^{\N})$, and it is easy to
see that $S$ preserves the measure $\P\circ X^{-1}$ iff the sequence
is stationary (simply restating definitions).

Conversely, any measure-preserving transformation $T$ on $(\Omega,\cF,\P)$
together with a random variable $f:(\Omega,\cF)\rightarrow(\R,B(\R))$
gives rise to a stationary sequence defined by $X_{n}(\omega)=f(T^{n}(\omega))$.


\subsection{Ergodic theorems}

Birkhoff's (pointwise) ergodic theorem is a generalisation of the
strong law of large numbers which applies to general stationary sequences.
The maximal ergodic theorem is used as a lemma in the proof, and I
believe it has other applications in analysis but I don't know about
them. The proofs are in the Appendix.

\begin{theorem}[Maximal Ergodic Theorem]If $T:(S,\cS,\mu)\rightarrow(S,\cS,\mu)$
is measure-preserving, $f\in L^{1}(S,\cS,\mu)$, $S_{n}(\omega)=\sum_{k=1}^{n}f(T^{k-1}\omega)$
and $A=\{\omega\colon\sup S_{n}>0\}$, then $\int_{A}fd\mu\geq0$.\end{theorem} 

\begin{theorem}[Birkhoff's Ergodic Theorem]If $T:(\Omega,\cF,\P)\rightarrow(\Omega,\cF,\P)$
is measure-preserving, $\cI$ is the invariant $\sigma$-field of
$T$, and $f\in L^{1}$ then\[
\frac{1}{n}\sum_{k=1}^{n}f(T^{k-1}\omega)\rightarrow\E(f|\cI)\mbox{ almost surely.}\]
\end{theorem} 

This can also be viewed from the point of view of dynamics: we take
our probability space as the space of states for some dynamical system
and let $T$ be the transformation corresponding to advancing by a
single unit of time (Liouville's theorem in dynamics tells us that
this transformation is measure-preserving). The invariant $\sigma$-field
$\cI$ consists of the components of the state space which a particle
(almost surely) does not enter or leave.

Then $\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=1}^{n}f(T^{k-1}\omega)$
is the average over time of the value of $f$ for a single particle,
and $\E(f|\cI)$ is the average value of $f$ over all points in a
component of the state space, at an instant in time. Birkhoff's ergodic
theorem tells us that the time average and space average are the same.


\subsection{Ergodic transformations}

The $\E(f|\cI)$ on the right hand side of Birkhoff's ergodic theorem
suggests that we should be particularly interested in transformations
for which $\cI$ is trivial (i.e. $\P(A)=0\mbox{ or }1\;\forall A\in\cI$).
Since $\E(f|\cI)$ is a $\cI$-measurable r.v., for such a $\sigma$-field
it will be almost surely constant. So we define:

A measure-preserving transformation $T$ is \defterm{ergodic} if
its invariant $\sigma$-field is trivial.

Note that the value which an a.s. constant r.v. takes with probability
1 must be equal to its expectation. So $\E(f|\cI)=\E(\E(f|\cI))=\E(f)$
almost surely.

So to prove the strong law of large numbers, all we need to prove
is:

\begin{lemma}If $(X_{1},X_{2},\ldots)$ is a sequence of i.i.d. r.v.s,
then the shift operator $S$ is ergodic.\end{lemma}

\begin{proof}As observed above, we are treating $S$ as a measure-preserving
transformation on the probability space $(\R^{\N},B(\R^{\N}),\P\circ X^{-1})$.

Call a measurable set $A$ \defterm{strictly invariant} (non-standard
terminology) if $S^{-1}A=A$. The strictly invariant sets form a $\sigma$-field
$\cJ$.

We shall show that $\cJ$ is contained in the tail $\sigma$-field
$\cT$ so by Kolmogorov's 0-1 law $\cJ$ is trivial. We shall also
show that an invariant set differs from a strictly invariant set by
a null set, so $\cI$ is trivial and $S$ is ergodic.

Informally, what we do is observe that $\omega\in A\Leftrightarrow S\omega\in A$
and that whether $S\omega$ is in $A$ can be determined by looking
at just $X_{2},X_{3},\ldots$, so $A\in\sigma(X_{2},X_{3},\ldots)$.

Doing this formally requires quite a bit of manipulation of $\sigma$-fields:

Note that $X_{n}(S\omega)=X_{n+1}(\omega)$ so $X_{n}\circ S=X_{n+1}$.
So the functions $X_{n}\circ S$ are all measurable on $\sigma(X_{2},X_{3},\ldots)$,
and $\sigma(X_{1}\circ S,X_{2}\circ S,\ldots)\subset\sigma(X_{2},X_{3},\ldots)$.

Let $\cF_{0}=\{A\subset\Omega\colon S^{-1}A\in\sigma(X_{1}\circ S,X_{2}\circ S,\ldots)\}$.
It is straightforward to check that this is a $\sigma$-field. If
$B$ is a measurable subset of $\R$, then $S^{-1}(X_{n}^{-1}(B))=(X_{n}\circ S)^{-1}(B)\in\sigma(X_{1}\circ S,X_{2}\circ S,\ldots)$
so $X_{n}^{-1}(B)\in\cF_{0}$ for all $n$. So $X_{n}$ is $\cF_{0}$-measurable
for all $n$, so $\cF_{0}\supset\sigma(X_{1},X_{2},\ldots)$.

Now given $A\in\cJ$, we have $A\in\sigma(X_{1},X_{2},\ldots)\subset\cF_{0}$
so $A=S^{-1}A\in\sigma(X_{2},X_{3},\ldots)$.

Similarly, $A\in\sigma(X_{n},X_{n+1},\ldots)$ for all $n$, so $A\in\cT$.

\medskip{}


Given $A\in\cI$, we need to check that there is $B\in\cJ$ s.t. $A\triangle B$
is a null set. There ought to be an easier way than the following,
but this is the best I have come up with.

Let $B=\limsup_{n\geq0}S^{-n}A$. Then $S^{-1}B=\limsup_{n\geq1}S^{-n}A=B$
so $B\in\cJ$.

By lots of set chasing, \begin{align*}
A\triangle B=(A\setminus B)\cup(B\setminus A) & =\liminf(A\setminus S^{-n}A)\cup\limsup(S^{-n}A\setminus A)\\
 & \subset\liminf(A\triangle S^{-n}A)\cup\limsup(A\triangle S^{-n}A)\\
 & =\limsup(A\triangle S^{-n}A)\end{align*}


Now $A\triangle S^{-n}A\subset\bigcup_{k=1}^{n}(S^{-k+1}A\triangle S^{-k}A)$
and as $S$ is measure-preserving, \[
\mu(S^{-k+1}A\triangle S^{-k}A)=\mu(S^{-1}A\triangle A)=0\]
 so $\mu(A\triangle S^{-n}A)=0$ for all $n$.

Hence $\mu(A\triangle B)=0$.\end{proof}


\section{Characteristic functions}

%
\begin{framed}%
{[}2{]} The Fourier transform of a finite measure, characteristic
functions, uniqueness and inversion. Weak convergence, statement of
Lévy's convergence theorem for characteristic functions.\end{framed}This discussion of Fourier transforms is of course more rigorous than
the treatment in IB Methods, but it is still not entirely satisfactory.
For example, there is annoying asymmetry between the domains on which
the Fourier transform and the inverse Fourier transform are defined.


\subsection{Fourier transforms}

The \defterm{Fourier transform} of a finite measure $\mu$ on $(\R,B(\R))$
is the function $\hat{\mu}:\R\rightarrow\C$ \[
\hat{\mu}(t)=\int e^{itx}\mu(dx)\]
 (Note of course the usual variety of conventions in defining Fourier
transforms: it may be defined as the conjugate of this, or with a
constant multiplier. Note also that we extend integration from real-valued
to complex-valued functions just by adding real and imaginary parts,
so long as $\int\vert f\vert d\mu<\infty$.)

The Fourier transform defined in applied maths as $\hat{f}(t)=\int_{-\infty}^{\infty}e^{itx}f(x)dx$
is the Fourier transform in this sense of the measure with density
function $f$. (Not all measures have density functions; I will add
a definition and discussion of them somewhere eventually.)

In the case of a random variable $X$, the Fourier transform with
respect to its Lebesgue-Stieltjes measure is the \defterm{characteristic function}
$\varphi_{X}(t)=\E(e^{itX})$.

Note that $\hat{\mu}(0)=\mu(\R)$ and $\vert\hat{\mu}(t)\vert\leq\mu(\R)$
for all $t$.

\begin{lemma}The Fourier transform $\varphi$ of a finite measure
$\mu$ is uniformly continuous.\end{lemma}

\begin{proof}We have $\vert e^{itx}-1\vert\rightarrow0$ as $t\rightarrow0$,
$\vert e^{itx}-1\vert\leq2$ for all $t$, and the constant $2$ is
integrable since $\mu$ is finite, so by the Dominated Convergence
Theorem, \[
\int\vert e^{itx}-1\vert\mu(dx)\rightarrow0\mbox{ as }t\rightarrow0\]


Now given $\epsilon>0$, we can find $\delta>0$ s.t. $\vert h\vert<\delta\Rightarrow\int\vert e^{ihx}-1\vert\mu(dx)<\epsilon$.
For any $t,h\in\R$ with $\vert h\vert<\delta$, we have \[
\vert\hat{\mu}(t+h)-\hat{\mu}(t)\vert=\left|\int e^{itx}(e^{ihx}-1)\mu(dx)\right|\leq\int\vert e^{itx}\vert\vert e^{ihx}-1\vert\mu(dx)=\int\vert e^{ihx}-1\vert\mu(dx)<\epsilon\]
\end{proof}


\subsection{Inverse of Fourier transform}

Given a function $\hat{\mu}:\R\rightarrow\C$ which is the Fourier
transform of some finite measure $\mu$, we would like to recover
$\mu$; in particular it will be important to know that there is only
one measure with given Fourier transform. (We do not consider here
conditions for such a measure to exist; we simply assume that the
$\hat{\mu}$ we are given is the transform of some measure.)

Recall the inversion formula from Methods: $f(x)=\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-itx}\hat{f}(t)dt$.
But we do not know that the RHS is integrable; or from another point
of view, this formula constructs a density $f$ for $\mu$, so can
only work if $\mu$ has a density function.

To allow us to use this formula, we smooth out $\mu$ so that it does
have a density. This can be done by convolving with a \defterm{mollifier},
a smooth function with properties that allow us to reconstruct the
original measure by taking a limit. This convolution of course corresponds
to multiplication of Fourier transforms.

A suitable function to use (both this function and its Fourier transform
are smooth) is $\exp(-\epsilon t^{2}/2)$. As $\epsilon\rightarrow0$,
this tends to 1 and so $\exp(-\epsilon t^{2}/2)\hat{\mu}(t)\rightarrow\hat{\mu}(t)$.
(Another way of looking at this is that we are mixing a small amount
of Gaussian noise into the distribution.)

Now we can define\[
f_{\epsilon}(x)=\frac{1}{2\pi}\int e^{-itx}\exp(-\epsilon t^{2}/2)\hat{\mu}(t)dt\]
 This integral is defined and finite because $e^{-itx}\exp(-\epsilon t^{2}/2)\hat{\mu(t)}$
is continuous, so measurable, and it is dominated by $\exp(-\epsilon t^{2}/2)\mu(\R)$
which is integrable.

Now $f_{\epsilon}(x)$ should be an approximate density for $\mu$.
In fact we have \begin{align*}
f_{\epsilon}(x) & =\frac{1}{2\pi}\int e^{-itx}\exp(-\epsilon t^{2}/2)\left(\int e^{itx'}\mu(dx')\right)dt\\
 & =\frac{1}{2\pi}\int\int\exp(it(x'-x)-\epsilon t^{2}/2)\mu(dx')dt\\
 & =\frac{1}{2\pi}\int\int e^{it(x'-x)}\exp(-\epsilon t^{2}/2)dt\,\mu(dx')\mbox{ by Fubini}\end{align*}
(The application of Fubini is justified because the integrand is dominated
by $\exp(-\epsilon t^{2}/2)$ and $\mu$ is finite, so $\int\int\exp(-\epsilon t^{2}/2)\mu(dx')dt<\infty$.)

This contains the Fourier transform of a Gaussian (just with different
labels), which we know how to compute, so we get\[
f_{\epsilon}(x)=\frac{1}{\sqrt{2\pi\epsilon}}\int\exp(-(x'-x)^{2}/2\epsilon)\mu(dx')\]


This is the density of an approximation to $\mu$, so we get the measure
by integrating. Note that $g_{\epsilon}(x,x')=\exp(-(x'-x)^{2}/2\epsilon)$
is non-negative, so we can apply Tonelli's (a.k.a. Fubini's) theorem
without having to check that the integrals involved are finite. Define\begin{align*}
F_{\epsilon}(a) & =\int_{-\infty}^{a}f_{\epsilon}(x)dx\\
 & =\frac{1}{\sqrt{2\pi\epsilon}}\int_{-\infty}^{a}\int\exp(-(x'-x)^{2}/2\epsilon)\mu(dx')dx\\
 & =\frac{1}{\sqrt{2\pi\epsilon}}\int\int_{-\infty}^{a}\exp(-(x-x')^{2}/2\epsilon)dx\,\mu(dx')\mbox{ (Tonelli)}\\
 & =\int\Phi\left(\frac{a-x'}{\sqrt{\epsilon}}\right)\mu(dx')\end{align*}
 where $\Phi(x)=\int_{-\infty}^{x}\exp(-t^{2}/2)dt$ is the standard
Gaussian distribution function.

Now as $\epsilon\rightarrow0$, \[
\Phi\left(\frac{a-x'}{\sqrt{\epsilon}}\right)\rightarrow\begin{cases}
0 & \mbox{if }a<x'\\
\frac{1}{2} & \mbox{if }a=x'\\
1 & \mbox{if }a>x'\end{cases}\]
 and it is dominated by 1, so by DCT we get \[
F_{\epsilon}(a)\rightarrow\int{\textstyle \frac{1}{2}}I_{\{a=x'\}}+I_{\{a>x'\}}\mu(dx')=\mu((-\infty,a))+{\textstyle \frac{1}{2}}\mu(\{a\})\]


This is sufficient to determine $\mu$ on the $\pi$-system $\{(-\infty,a):a\in\R\}$,
using the fact that $\mu((-\infty,a))$ is increasing and right-continuous,
and so to determine $\mu$.


\subsection{Weak convergence}

The modes of convergence we considered earlier were convergence of
functions. Now we consider a form of convergence of measures.

Let $(S,\cS)$ be a metric space with its Borel $\sigma$-field.

A sequence of measures $\mu_{n}$ on $(S,\cS)$ \defterm{converges weakly}
to $\mu$ if $\int fd\mu_{n}\rightarrow\int fd\mu$ for all bounded,
continuous functions $f:S\rightarrow\R$. We write this $\mu_{n}\Rightarrow\mu$.

Note that weak convergence can be considered as a mode of convergence
of random variables, by treating it as weak convergence of the corresponding
Lebesgue-Stieltjes measure. Regarded in this way, weak convergence
of r.v.s is implied by convergence in probability, and so by any of
the modes of convergence considered earlier.

There is an alternative characterisation of weak convergence which
is often easier to prove:

\begin{theorem}$\mu_{n}\Rightarrow\mu$ iff $\mu(A)\leq\liminf\mu_{n}(A)$
for all open sets $A$.\end{theorem}

\begin{proof}Suppose that $\mu_{n}\Rightarrow\mu$ and let $A$ be
an open set.

Consider the function $h_{n}(x)=\inf\{1,n\vert x-y\vert\colon y\in A^{c}\}$,
which is a bounded and continuous approximation to $I_{A}$. $(A^{c}$
closed ensures that $\inf\{\vert x-y\vert:y\in A^{c}\}>0$ for $x\in A$.)

Specifically, $0\leq h_{n}\uparrow I_{A}$.

So for any $k$ we have\begin{align*}
\liminf\mu_{n}(A)\geq\liminf{\textstyle \int}h_{k}d\mu_{n} & ={\textstyle \int}h_{k}d\mu &  & \mbox{(weak convergence)}\\
 & \uparrow{\textstyle \int}I_{A}d\mu=\mu(A) &  & \mbox{(monotone convergence)}\end{align*}


Conversely, suppose that $\mu(A)\leq\liminf\mu_{n}(A)$ for all open
sets $A$ and let $f$ be a bounded, continuous function. Since $f$
is bounded, we can add a constant to it to get $f\geq0$.

The integral of a measurable function is defined by looking at sums
of indicators of measurable sets. Here we only know things about the
measure of open sets, but on the other hand $f$ is continuous so
can be approximated by sums of indicators of open sets. (Essentially
we are computing the Riemann instead of the Lebesgue integral of $f$.)

Fix $m\in\N$ (higher $m$ means better approximation of $f$).

For $j\in\N$, let $A_{j}=\{\omega\colon f(\omega)>j/m\}$, which
is open.

Now $I_{A_{j}}(\omega)=1$ iff $1\leq j<mf(\omega)$ so \[
\sum_{j=1}^{\infty}I_{A_{j}}(\omega)\leq mf(\omega)\leq\sum_{j=1}^{\infty}I_{A_{j}}(\omega)+1\mtag{\dagger}\]
\label{eq:weak-convergence-proof-inequality}

Integrating (using monotone convergence on the LHS) gives\[
\sum_{j=1}^{\infty}\mu_{n}(A_{j})\leq m\int fd\mu_{n}\]
 so \[
\sum_{j=1}^{\infty}\mu(A_{j})\leq\liminf_{n\rightarrow\infty}\sum_{j=1}^{\infty}\mu_{n}(A_{j})\leq\liminf_{n\rightarrow\infty}m\int fd\mu_{n}\]


We can also integrate ($\dagger$) with respect to $\mu$ to get\[
m\int fd\mu\leq\sum_{j=1}^{\infty}\mu(A_{j})+\mu(S)\]
 so combining these,\[
\int fd\mu\leq\liminf_{n\rightarrow\infty}\int fd\mu_{n}+\frac{1}{m}\mu(S)\]


We can apply the same argument to $-f$ to get\[
\limsup_{n\rightarrow\infty}\int fd\mu_{n}-\frac{1}{m}\mu(S)\leq\int fd\mu\]


Since these hold for all $m\in\N$, we have $\lim_{n\rightarrow\infty}\int fd\mu_{n}=\int fd\mu$.\end{proof}


\subsection{Convergence in distribution}

A sequence of distribution functions $F_{n}$ \defterm{converges in distribution}
to a distribution function $F$ if $F_{n}(x)\rightarrow F(x)$ for
all $x$ at which $F$ is continuous.

\begin{theorem}Let $F_{n},F$ be distribution functions, with Lebesgue-Stieltjes
measures $\mu_{n},\mu$. Then $F_{n}\rightarrow F$ in distribution
iff $\mu_{n}\Rightarrow\mu$.\end{theorem}

\begin{proof}Suppose $\mu_{n}\Rightarrow\mu$, and consider $c\in\R$,
s.t. $F$ is continuous at $c$.

We want to show that $F_{n}(c)\rightarrow F(c)$ or in other words
that $\mu_{n}((-\infty,c])\rightarrow\mu((-\infty,c])$.

For any $\delta>0$, we have $\mu((-\infty,c-\delta))\leq\liminf\mu_{n}((-\infty,c-\delta))\leq\liminf\mu_{n}((-\infty,c])$.

Since $F$ is continuous at $c$, $F(c-2\delta)\uparrow F(c)$ as
$\delta\rightarrow0$ and $F(c-2\delta)\leq\mu((-\infty,c-\delta))\leq F(c)$,
so $\mu((-\infty,c-\delta))\uparrow\mu((-\infty,c])$.

Hence $\mu((-\infty,c])\leq\liminf\mu_{n}((-\infty,c])$.

Also, $\mu((c,\infty))\leq\liminf\mu_{n}((c,\infty))$ so $\mu((-\infty,c])\geq\limsup\mu_{n}((-\infty,c])$.

Hence $\lim\mu((-\infty,c])=\mu((-\infty,c])$.\medskip{}


Now the other way. Suppose that $F_{n}\rightarrow F$, and let $A$
be an open subset of $\R$. We want to show that $\mu(A)\geq\liminf\mu_{n}(A)$.

All open subsets of $\R$ are a union of countably many disjoint open
intervals, so $A=\bigcup_{n}(a_{n},b_{n})$.

It is enough to show that $\mu((a,b))\leq\liminf\mu_{n}((a,b))$ for
a single open interval $(a,b)$, as we can then add these up.

$F$ has only countably many points of discontinuity, so there is
a sequence $a_{m}\downarrow a$ s.t. $F$ is continuous at $a_{m}$
for all $m$. Then $\limsup F_{n}(a)\leq\limsup F_{n}(a_{m})=F(a_{m})$
for all $m$, so by right continuity of $F$, $\limsup F_{n}(a)\leq F(a)$.

Similarly, there is a sequence $b_{m}\uparrow b$ s.t. $b_{m}<b$
and $F$ is continuous at all $b_{m}$. Then $\liminf F_{n}(b-)\geq\liminf F_{n}(b_{m})=F(b_{m})$
for all $m$, and $F(b_{m})\uparrow F(b-)$ so $\liminf F_{n}(b-)\geq F(b-)$.

Combining these gives \begin{align*}
\mu((a,b))=F(b-)-F(a) & \leq\liminf F_{n}(b-)-\limsup F_{n}(a)\\
 & =\liminf(F_{n}(b-)-F_{n}(a))=\liminf\mu_{n}((a,b))\end{align*}


Note that this still works if either $a$ or $b$ is infinite.\end{proof}


\subsection{Lévy's convergence theorem}

This theorem connects weak convergence and Fourier transforms, and
gives one perspective on why weak convergence is an interesting concept
(though the reasons for this come much more strongly from functional
analysis). It will be a key step in the proof of the central limit
theorem. The proof is non-examinable and is included in the Appendix.

\begin{theorem}[Lévy's convergence theorem]$\mu_{n}\Rightarrow\mu$
iff $\hat{\mu}_{n}\rightarrow\hat{\mu}$ pointwise.\end{theorem}


\subsection{Smoothness of Fourier transforms}

The next result illustrates the principle that if a distribution has
thin tails, then its Fourier transform is smooth at 0. In particular,
if $\vert x\vert^{n}$ is integrable w.r.t. $\mu$, then $\hat{\mu}$
is differentiable $n$ times at zero, and its derivatives are given
by the moments of $\mu$ (up to factors of $i$). Besides being of
general interest, the result is important in the proof of the central
limit theorem.

The result essentially comes from the Taylor expansion of $\exp(itx)$,
but we need to use dominated convergence to ensure that the integrals
converge. Before proving the main result, we will need bounds on the
error in this Taylor expansion. Let $R_{n}(x)=\exp(ix)-\sum_{j=0}^{n}(ix)^{j}/j!$

\begin{lemma}For $x\in\R$, $\vert R_{n}(x)\vert\leq2\vert x\vert^{n}/n!$
and $\vert R_{n}(x)\vert\leq\vert x\vert^{n+1}/(n+1)!$\end{lemma}

\begin{proof}We have $R_{n}(x)=\int_{0}^{x}iR_{n-1}(y)dy$, so $\vert R_{n}(x)\vert\leq\int_{0}^{x}\vert R_{n-1}(y)\vert dy$.

For $n=0$, we have $\vert R_{0}(x)\vert=\vert\exp(ix)-1\vert\leq2$.

Also$\vert R_{0}(x)\vert=\vert\int_{0}^{x}i\exp(iy)dy\vert\leq\int_{0}^{x}1dy=x$.

So the claims hold for $n=0$, and then for all $n$ by induction.\end{proof}

\begin{lemma}If $\int\vert x\vert^{n}\mu(dx)<\infty$, then \[
\hat{\mu}(t)=\sum_{j=0}^{n}\left(\frac{(it)^{j}}{j!}\int x^{j}\mu(dx)\right)+o(\vert t\vert^{n})\]
\end{lemma}

\begin{proof}\begin{align*}
\frac{1}{\vert t\vert^{n}}\left|\hat{\mu}(t)-\sum_{j=0}^{n}\left(\frac{(it)^{j}}{j!}\int x^{j}\mu(dx)\right)\right| & =\left|t^{-n}\int(\exp(itx)-\sum_{j=0}^{n}(itx)^{j}/j!)\mu(dx)\right|\\
 & =\left|t^{-n}\int R_{n}(tx)\mu(dx)\right|\\
 & \leq\int\vert t^{-n}R_{n}(tx)\vert\mu(dx)\end{align*}


By the previous lemma, $\vert t^{-n}R_{n}(tx)\vert\leq\vert t\vert\vert x\vert^{n+1}/(n+1)!\rightarrow0$
as $t\rightarrow0$, and $\vert t^{-n}R_{n}(tx)\vert$ is dominated
by $2\vert x\vert^{n}/n!$, which we have assumed to be integrable.
So by dominated convergence, $\int\vert t^{-n}R_{n}(tx)\vert\mu(dx)\rightarrow0$
as $t\rightarrow0$.\end{proof}

In probabilistic language, this becomes $\varphi_{X}(t)=\sum_{j=0}^{n}\frac{(it)^{j}}{j!}\E(X^{j})+o(\vert t\vert^{n})$.


\section{Gaussian random variables}

%
\begin{framed}%
{[}1{]} Gaussian random variables, the multivariate normal distribution.

The central limit theorem.\end{framed}


\subsection{Normal distribution}

The one-dimensional normal (or Gaussian) distribution $N(\mu,\sigma^{2})$
is the distribution on $\R$ with distribution function $F(a)=\frac{1}{\sigma\sqrt{2\pi}}\int_{-\infty}^{a}\exp(-(x-\mu)^{2}/2\sigma^{2})dx$.

A $d$-dimensional random variable $\mathbf{X}:(\Omega,\cF,\P)\rightarrow(\R^{d},B(\R^{d}))$
has a \defterm{multivariate normal distribution} if $\mathbf{a}.\mathbf{X}$
is normally distributed for every vector $\mathbf{a}\in\R^{d}$.

If we add a constant vector $\mathbf{b}$ to a MVN r.v. $\mathbf{X}$,
then $\mathbf{X}+\mathbf{b}$ still has multivariate normal distribution.
So given any MVN r.v. $\mathbf{X}=(X_{1},\ldots,X_{n})$, we can let
$\pmb\mu=(\E(X_{1}),\ldots,\E(X_{n}))$ and then $\mathbf{Y}=\mathbf{X}-\pmb\mu$
is multivariate normal with mean 0.

In one dimension, we require only one parameter, the variance, to
describe a normal distribution with mean 0. In higher dimensions,
we require not only the variance of each component but also more parameters
to describe the correlations between components.

We use the \defterm{covariance matrix} $V_{ij}=\E(Y_{i}Y_{j})$.
We can write all these equations at once by saying $V=\E(\mathbf{Y}\mathbf{Y}^{T})$.

Note that this matrix is symmetric, and it is positive semidefinite,
as for any $\mathbf{a}\in\R^{d}$,\[
\mathbf{a}^{T}V\mathbf{a}=\sum_{i}\sum_{j}a_{i}\E(Y_{i}Y_{j})a_{j}=\E((\sum_{i}a_{i}Y_{i})^{2})\geq0\]


Since $V$ is symmetric, it can be diagonalised by an orthogonal matrix,
say $V=RDR^{T}$ with $R$ orthogonal and $D$ diagonal.

Let $\mathbf{Z}=R^{T}\mathbf{Y}$. For any $\mathbf{a}\in\R^{d}$,
$\mathbf{a}.\mathbf{Z}=(R\mathbf{a}).\mathbf{Y}$ so $\mathbf{Z}$
is still MVN; but now $\E(\mathbf{Z}\mathbf{Z}^{T})=\E(R^{T}\mathbf{Y}\mathbf{Y}^{T}R)=R^{T}VR=D$,
so $\mathbf{Z}$ has diagonal covariance matrix, and its components
are uncorrelated.

Now suppose that $V$ is positive definite (and not just positive
semidefinite). The diagonal entries of $D$ are all now positive,
so have square roots, and there is a diagonal matrix $E$ with positive
entries on the diagonal s.t. $E^{2}=D$. If we let $\widetilde{\mathbf{Z}}=E^{-1}\mathbf{Z}$
then $\E(\widetilde{\mathbf{Z}}\widetilde{\mathbf{Z}}^{T})=\E(E^{-1}\mathbf{Z}\mathbf{Z}^{T}E^{-1})=E^{-1}DE^{-1}=I$.
So all MVN variables with positive definite covariant matrix can be
reduced by linear transformations to an MVN variable with covariance
matrix $I$.

We know that the components of $\widetilde{\mathbf{Z}}$ are uncorrelated,
because they have zero covariance. In fact, for components of an MVN
variable, we have a stronger property: they are independent.

\begin{theorem}If $\widetilde{\mathbf{Z}}$ is a MVN r.v. with $\E\widetilde{\mathbf{Z}}=0$
and $\E(\widetilde{\mathbf{Z}}\widetilde{\mathbf{Z}}^{T})=I$, then
the components of $\widetilde{\mathbf{Z}}$ are independent $N(0,1)$
random variables.\end{theorem}

\begin{proof}We need to extend the idea of a characteristic function
to $d$-dimensional random variables: if $\mathbf{X}:\Omega\rightarrow\R^{d}$
is a random variable then its characteristic function is $\varphi_{\mathbf{X}}:\R^{d}\rightarrow\C$
given by $\varphi_{\mathbf{X}}(\mathbf{a})=\E(\exp(i\mathbf{a}.\mathbf{X}))$.

In the case of MVN $\widetilde{\mathbf{Z}}$, $\mathbf{a}.\widetilde{\mathbf{Z}}$
is $N(0,1)$, so from what we know about the characteristic function
the one-dimensional normal distribution, $\varphi_{\widetilde{\mathbf{Z}}}(\mathbf{a})=\E(\exp(i\mathbf{a}.\widetilde{\mathbf{Z}}))=\exp(-(\mathbf{a}.\widetilde{\mathbf{Z}})^{2}/2)=\exp(-\mathbf{a}^{T}\widetilde{\mathbf{Z}}\widetilde{\mathbf{Z}}^{T}\mathbf{a}/2)=\exp(-\mathbf{a}^{T}I\mathbf{a}/2)=\exp(-\vert\mathbf{a}\vert^{2}/2)$.

If $U_{1},\ldots,U_{d}$ are independent $N(0,1)$ variables, then\begin{align*}
\varphi_{\mathbf{U}}(\mathbf{a}) & =\E(\exp(i\mathbf{a}.\mathbf{U}))=\E\left(\prod_{j}\exp(ia_{k}U_{k})\right)=\prod_{j}\E(\exp(ia_{k}U_{k})\\
 & =\prod_{j}\varphi_{U_{k}}(a_{k})=\prod_{j}\exp(-a_{k}^{2}/2)=\exp(-\vert\mathbf{a}\vert^{2}/2)=\varphi_{\widetilde{\mathbf{Z}}}(\mathbf{a})\end{align*}


So as distributions are uniquely determined by their characteristic
functions, $\widetilde{\mathbf{Z}}$ and $\mathbf{U}$ have the same
distribution.\end{proof}


\subsection{Central limit theorem}

\begin{theorem}[Central Limit Theorem] Let $(X_{n})$ be an i.i.d.
sequence with $\E(X_{n})=0,\var(X_{n})=\sigma^{2}<\infty$. Let $S_{n}=X_{1}+\ldots+X_{n}$
and $Z_{n}=\dfrac{S_{n}}{\sigma\sqrt{n}}$. Then $Z_{n}$ converges
in distribution to $N(0,1)$.\end{theorem}

\begin{proof}Let $\varphi_{n}$ be the characteristic function of
$Z_{n}$ and $\psi$ the characteristic function of the standard normal
distribution. We will show that $\varphi_{n}\rightarrow\psi$ pointwise,
and then the Lévy convergence theorem and equivalence of weak convergence
to convergence in distribution give the result.

Note that $\psi(t)=\exp(-t^{2}/2)$.

Let $\varphi$ be the characteristic function of $X_{1}$. Then\begin{align*}
\varphi_{n}(t)=\E(e^{itZ_{n}}) & =\E(e^{it(X_{1}+\ldots+X_{n})/\sigma\sqrt{n}})\\
 & =\E(e^{itX_{1}/\sigma\sqrt{n}})\ldots\E(e^{itX_{n}/\sigma\sqrt{n}})\mbox{ since }X_{1},\ldots,X_{n}\mbox{ are independent}\\
 & =(\E(e^{itX_{1}/\sigma\sqrt{n}}))^{n}\mbox{ since }X_{1},\ldots,X_{n}\mbox{ are identically distributed}\\
 & =(\varphi(t/\sigma\sqrt{n}))^{n}\end{align*}


We now seek to estimate $\varphi(t/\sigma\sqrt{n})^{n}$ using our
earlier {}``Taylor'' estimate of the values of characteristic functions.

We have $\E(X)=0$ and $\E(X^{2})=\sigma^{2}<\infty$, so $\varphi(t)=1-t^{2}\sigma^{2}/2+o(\vert t\vert^{2})$
as $t\rightarrow0$.

This gives $\varphi_{n}(t)=(1-t^{2}/2n+o(t^{2}/\sigma^{2}n))^{n}$
as $t/\sigma\sqrt{n}\rightarrow0$ (i.e. as $n\rightarrow\infty)$.

Taking logs, \begin{align*}
\log\varphi_{n}(t) & =n\log((1-t^{2}/2n+o(t^{2}/n))\\
 & =n(-t^{2}/2n+o(t^{2}/n))\mbox{ by Taylor's theorem for }\log(1+x)\\
 & \rightarrow-t^{2}/2\mbox{ as }n\rightarrow\infty\end{align*}


So $\varphi_{n}(t)\rightarrow\exp(-t^{2}/2)$, as required.\end{proof}

\appendix

\section{Ergodic theorems}

I did not find these proofs very enlightening, but they are the standard
proofs which appear in most books.

\begin{theorem}[Maximal Ergodic Theorem]If $T:(S,\cS,\mu)\rightarrow(S,\cS,\mu)$
is measure-preserving, $f\in L^{1}(S,\cS,\mu)$, $S_{n}(\omega)=\sum_{k=1}^{n}f(T^{k-1}\omega)$
and $A=\{\omega\colon\sup S_{n}>0\}$, then $\int_{A}fd\mu\geq0$.\end{theorem} 

\begin{proof}Let $M_{n}=\max\{0,S_{1},\ldots,S_{n}\}$, and $A_{n}=\{\omega\colon M_{n}>0\}$.
Then $M_{n}$ is increasing, and $A_{n}\uparrow A$ so $fI_{A_{n}}\rightarrow fI_{A}$.
And $\vert fI_{A_{n}}\vert\leq\vert f\vert\in L^{1}$ so by the Dominated
Convergence Theorem,\[
\int_{A_{n}}fd\mu\rightarrow\int_{A}fd\mu\]


Hence we just need to show $\int_{A_{n}}fd\mu\geq0$ for each $n$.

Consider the shifted sums $S_{n}'=S_{n}\circ T=\sum_{k=1}^{n}f(T^{k}\omega)$.

Let $M_{n}'=M_{n}\circ T=\max\{0,S_{1}',\ldots,S_{n}'\}$ and $A_{n}'=T^{-1}(A_{n})=\{\omega\colon M_{n}'>0\}$.

Now $S_{n}=f+S_{n-1}'$ so if $M_{n}>0$ then $M_{n}=f+\max\{S_{1}',\ldots,S_{n-1}'\}\leq f+M_{n-1}'$.

Hence $M_{n}I_{A_{n}}-M_{n-1}'I_{A_{n}}\leq fI_{A_{n}}$.

But we can control $M_{n-1}'I_{A_{n}}$ using $M_{n-1}'I_{A_{n}}\leq M_{n}'I_{A_{n}}\leq M_{n}'I_{A_{n}'}=(M_{n}I_{A_{n}})\circ T$,
so\[
\int_{A_{n}}f\geq\int(M_{n}-M_{n-1}')I_{A_{n}}\geq\int M_{n}I_{A_{n}}-\int(M_{n}I_{A_{n}})\circ T=0\]
(the last equality since $T$ is measure-preserving).\end{proof}

\begin{theorem}[Birkhoff's Ergodic Theorem]If $T:(\Omega,\cF,\P)\rightarrow(\Omega,\cF,\P)$
is measure-preserving, $\cI$ is the invariant $\sigma$-field of
$T$, and $f\in L^{1}$ then\[
\frac{1}{n}\sum_{k=1}^{n}f(T^{k-1}\omega)\rightarrow\E(f|\cI)\mbox{ almost surely.}\]
\end{theorem} 

\begin{proof}Assume wlog that $\E(f|\cI)=0$.

Let $X_{n}=f(T^{n-1}\omega),S_{n}=\sum_{k=1}^{n}X_{k}$.

Given $\epsilon>0$, let $A=\{\omega\colon\limsup_{n}S_{n}/n>\epsilon\}$.
We need to show that $\P(A)=0$.

Let $f'=(f-\epsilon)I_{A}$, $X_{n}'=(X_{n}-\epsilon)I_{A}$ and $S_{n}'=\sum_{k=1}^{n}X_{n}'=(S_{n}-n\epsilon)I_{A}$.

Now if $A$ occurs then $S_{n}>n\epsilon$ for some (in fact infinitely
many) $n$, so $\sup S_{n}'>0$.

And if $\sup S_{n}'>0$, then $I_{A}=1$ so $A$ occurs.

So $A=\{\omega\colon\sup S_{n}'>0\}$.

Now for any fixed $\omega$, $X_{1}/n\rightarrow0$ as $n\rightarrow\infty$
so $\limsup_{n}S_{n}/n=\limsup_{n}S_{n-1}'/n=\limsup_{n}S_{n}'/n$.
Hence $A=T^{-1}(A)$ and $X_{n}'$ is stationary.

Hence by the maximal ergodic theorem, \[
0\leq\int_{A}X_{1}'d\P=\int_{A}X_{1}d\P-\epsilon\P(A)\]


Now $A\in\cI$ so the definition of conditional probability gives
\[
\int_{A}X_{1}d\P=\int_{A}\E(X_{1}|\cI)d\P=0\]
 so we get $\epsilon\P(A)\leq0$ giving $\P(A)=0$.\end{proof}
\end{document}
