\documentclass[12pt]{article}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.7in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{9in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{5pt plus 2pt minus 3pt}
\setlength{\parindent}{0in}


\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{ifthen}
\usepackage{amsmath}

%\usepackage{cleveref}

\usepackage [pagewise, mathlines, displaymath]{lineno}

%begin local defs
\newcommand{\comment}[1]{}
\newcommand{\bm}[1]{\mbox{\boldmath$#1$}}%
\newcommand{\bms}[1]{\mbox{\boldmath$\scriptstyle #1$}}%
\def\utwi#1{\lower1.0ex\hbox{${\textstyle #1}\atop{\textstyle
\mathaccent"707E {\hspace{1em}}}$}\raise1.0ex\hbox{\hspace{-.25em}}}
\def\stwi#1{\lower0.5ex\hbox{${\lower0.5ex\hbox{$\scriptstyle #1$}}
\atop{\scriptstyle
\mathaccent"707E {\hspace{.8em}}}$}\raise0.5ex\hbox{\hspace{-.2em}}}
\def\sstwi#1{\lower0.3ex\hbox{${\lower0.6ex\hbox{$
\scriptscriptstyle #1$}}\atop{\scriptscriptstyle
\mathaccent"707E {\hspace{.6em}}}$}\raise0.3ex\hbox{\hspace{-.2em}}}
\def\utwide#1{\lower1.0ex\hbox{${\textstyle #1}\atop{\textstyle
\mathaccent"0365 {\hspace{1em}}}$}\raise1.0ex\hbox{\hspace{-.25em}}}
\newcommand{\half}{\raisebox{.1em}{\footnotesize $\frac{1}{2}$}}
\newcommand{\ssmb}[1]{_{\mbox{\scriptsize #1}}}
\newcommand{\bhv}{\utwi{\hat{\beta}}}
\renewcommand{\ae}{\mbox{a.e.}}
\newcommand{\as}{\mbox{a.s.}}
\newcommand{\io}{\mbox{i.o.}}
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\D}{{\cal D}}
\newcommand{\E}{{\cal E}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
\renewcommand{\H}{{\cal H}}
\newcommand{\I}{{\cal I}}
\newcommand{\J}{{\cal J}}
\renewcommand{\L}{{\cal L}}
\newcommand{\M}{{\cal M}}
\newcommand{\N}{{\cal N}}
\renewcommand{\O}{{\cal O}}
\renewcommand{\P}{{\cal P}}
\newcommand{\Q}{{\cal Q}}
\newcommand{\R}{{\cal R}}
\renewcommand{\S}{{\cal S}}
\newcommand{\T}{{\cal T}}
\newcommand{\U}{{\cal U}}
\newcommand{\V}{{\cal V}}
\newcommand{\W}{{\cal W}}
\newcommand{\X}{{\cal X}}
\newcommand{\Y}{{\cal Y}}
\newcommand{\Z}{{\cal Z}}
\newcommand{\Exv}{\mbox{\rm E}}
\newcommand{\Var}{\mbox{\rm Var}}
\newcommand{\Cov}{\mbox{\rm Cov}}
\renewcommand{\vec}[1]{\mbox{\bf #1}}
\newcommand{\mat}[1]{\mbox{\boldmath $#1$}}
\newcommand{\vecs}[1]{\mbox{\scriptsize\bf #1}}
\newcommand{\cd}{\stackrel{{\cal D}}{\rightarrow}}
\newcommand{\cp}{\stackrel{P}{\rightarrow}}
\newcommand{\cas}{\stackrel{\rm a.s.}{\rightarrow}}
\newcommand{\sif}{$\sigma$-field}
\newcommand{\sifs}{$\sigma$-fields}
\newcommand{\sfi}{$\sigma$-finite}
\newcommand{\pari}{\hspace{\parindent}}
\newcommand{\bmat}{\left(\begin{array}}
\newcommand{\emat}{\end{array}\right)}
\newcommand{\bsmat}{\left[\begin{array}}
\newcommand{\esmat}{\end{array}\right]}
\newcommand{\bfun}{\left\{\begin{array}{ll}}
\newcommand{\efun}{\end{array}\right.}
\newcommand{\Alpha}{{\rm A}}
\newcommand{\Beta}{{\rm B}}
\newcommand{\Eta}{{\rm H}}
\newcommand{\Mu}{{\rm M}}
\newcommand{\Tau}{{\rm T}}
\renewcommand{\th}{\mbox{\rm th}}
\newcommand{\rd}{\mbox{\rm rd}}
\newcommand{\nd}{\mbox{\rm nd}}
\newcommand{\st}{\mbox{\rm st}}
\newcommand{\Xbar}{\overline{X}}
\newcommand{\xbar}{\overline{x}}
\newcommand{\Ybar}{\overline{Y}}
\newcommand{\ybar}{\overline{y}}
\newcommand{\lni}{\lim_{n\rightarrow\infty}}
\newcommand{\sn}{\sum_{i=1}^n}
\def\Real{\hbox{I\kern-.1667em\hbox{R}}}
\def\Reals{\hbox{\scriptsize I\kern-.1667em\hbox{R}}}
\def\Int{\hbox{\sf Z\kern-.3em\hbox{\sf Z}}}
% end of local defs
\newcommand{\emindex}[1]
{ \emph{#1} \index{#1} }

\renewcommand{\emptyset}{\varnothing}


\usepackage{epsfig}
\newenvironment{lproof*}[1]{\par{\sc Proof of #1.}}{}
\newenvironment{cproof}[1]{\par{\sc Proof of #1 continued.}}{\hfill $\Box$}
\newcommand{\oReal}{\overline{\Real}}
\newcommand{\theoremn}[2]{{\sc \tref{#1}.\ }{\it #2}}




\begin{document}


\renewcommand{\baselinestretch}{1.1}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[equation]{Exercise}
\newtheorem{proposition}[equation]{Proposition}
% to get nice proofs ...
\newcommand{\qedsymb}{\mbox{ }~\hfill~{\rule{2mm}{2mm}}}
\newenvironment{proof}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent Proof: }]
}{\qedsymb\end{trivlist}}


\begin{table}\centering
\begin{tabular*}{6.5in}{@{\extracolsep{\fill}}|llr|} \hline
36-752 & \hspace*{0.5 in} & Spring 2014 \\
Advanced Probability Overview & & \\
 & & \\
\multicolumn{3}{|c|}{
{{\large {\bf Lecture Notes Set 1: Course Overview, $\sigma$-Fields, and Measures}}}} \\
 & & \\
Instructor: Jing Lei & &\\ \hline
\end{tabular*}
\end{table}

 Associated reading: Sec 1.1-1.4 of Ash and Dol\'{e}ans-Dade;  Sec 1.1 and A.1 of Durrett.

\section{Introduction}

How is this course different from your earlier probability courses?
There are some problems that simply can't be handled with
finite-dimensional sample spaces and random variables that are either
discrete or have densities.

\begin{example}
Try to express the strong law of large numbers without using an
infinite-dimensional space.  Oddly enough, the weak law of large
numbers requires only a sequence of finite-dimensional spaces, but the
strong law concerns entire infinite sequences.
\end{example}

\begin{example}
Consider a distribution whose cumulative distribution function (cdf)
increases continuously part of the time but has some jumps.  Such a
distribution is neither discrete nor continuous.  How do you define
the mean of such a random variable? Is there a way to
treat such distributions together with discrete and continuous ones in
a unified manner?
\end{example}

\paragraph{\bf General Measures} Both of the above examples are accommodated
by a generalization of the
theories of summation and integration.  Indeed, summation becomes a
special case of the more general theory of integration.  It all begins
with a generalization of the concept of ``size'' of a set.

\begin{example}
One way to measure the size of a set is to count its elements.  All
infinite sets would have the same size (unless you distinguish
different infinite cardinals).
\end{example}

\begin{example}
Special subsets of Euclidean spaces can be measured by length, area,
volume, etc.  But what about sets with lots of holes in them?  For
example, how large is the set of irrational numbers between 0 and 1?
\end{example}

We will use measures to say how large sets are.  First, we have to
decide which sets we will measure.

\section{$\sigma$-fields}
\begin{definition}[fields and $\sigma$-fields]
Let $\Omega$ be a set.  A collection
$\F$ of subsets of $\Omega$ is called a \emph{field} if it satisfies
\begin{itemize}
\item $\Omega\in\F$,
\item for each $A\in\F$, $A^C\in\F$,
\item for all $A_1,A_2\in\F$, $A_1\cup A_2\in\F$.
\end{itemize}
A field $\F$ is a \emph{\sif} \index{\sif} if, in addition, it satisfies
\begin{itemize}
\item for every sequence $\{A_k\}_{k=1}^\infty$ in $\F$,
$\bigcup_{k=1}^\infty A_k\in\F$.
\end{itemize}
\end{definition}


We will define measures on fields and \sif's.
\begin{definition}[Measurable Space]
  A set $\Omega$ together
with a \sif\
$\F$ is called a \emph{measurable space} \index{measurable!space} $(\Omega,\F)$, and the elements of
$\F$ are called \emph{measurable sets} \index{measurable!set}.
\end{definition}

\begin{example}[Intervals on $\mathbb R^1$]\label{exa:intervals}
Let $\Omega=\Real$ and define $\U$ to be the collection of all unions
of finitely many disjoint intervals of the form $(a,b]$ or
$(-\infty,b]$ or $(a,\infty)$ or $(-\infty,\infty)$, together with
$\emptyset$.  Then $\U$ is a field.
\end{example}

\begin{example}[Power set]
\index{power set}
Let $\Omega$ be an arbitrary set.
The collection of all subsets of $\Omega$ is a \sif.  It is denoted
$2^\Omega$ and is called the {\em power set of $\Omega$}.
\end{example}

\begin{example}[Trivial \sif]
Let $\Omega$ be an arbitrary set. Let $\F=\{\Omega,\emptyset\}$.  This
is the {\em trivial \sif}.
\end{example}

\begin{exercise}\label{ex2_1}
Let ${\cal F}_1,\:{\cal F}_2, \ldots$ be classes of sets in a common space $\Omega$
such that ${\cal F}_n \subset {\cal F}_{n+1}$ for each $n$.
Show that if each ${\cal F}_n$ is a field, then $\cup_{n=1}^\infty {\cal F}_n$
is also a field.

If each ${\cal F}_n$ is a $\sigma$-field, then is $\cup_{n=1}^\infty {\cal F}_n$
also necessarily a $\sigma$-field? Think about the following case: $\Omega$ is the set
of nonnegative integers and
  $ {\cal F}_n \equiv \sigma\!\left(\big\{\{0\}, \{1\}, \ldots, \{n\}\big\}\right)$.
\end{exercise}

\paragraph{Generated $\sigma$-fields} A field is closed under finite set theoretic operations whereas a $\sigma$-field  is closed under countable set theoretic operations. In a problem dealing with probabilities, one usually deals with a small class of subsets $\A$, for example the class of subintervals of $(0, 1]$. It is possible that if we perform countable operations on such a class $\A$ of sets, we might end up operating on sets outside the class $\A$. Hence, we would like to define a class denoted by $\sigma(\A)$ in which we can safely perform countable set-theoretic operations. This class $\sigma(\A)$ is called the $\sigma$-field generated by $\A$, and it is defined as the intersection of all the $\sigma$-fields containing $\A$ (exercise: show that this is a $\sigma$-field). $\sigma(\A)$ is the smallest $\sigma$-field containing $\A$.

\begin{example}
Let $\C=\{A\}$ for some nonempty $A$ that is not itself $\Omega$.
Then $\sigma(\C)=\{\emptyset,A,A^C,\Omega\}$.
\end{example}

\begin{example}\label{exa:int2}
Let $\Omega=\Real$ and let $\C$ be the collection of all intervals of
the form $(a,b]$.  Then the field generated by $\C$ is $\U$ from
Example \ref{exa:intervals} while $\sigma(\C)$ is larger.
\end{example}

\begin{example}[Borel \sif]
Let $\Omega$ be a topological space and let $\C$ be the collection of
open sets.  Then $\sigma(\C)$ is called the {\em Borel \sif}.  If
$\Omega=\Real$, the Borel \sif\ is the same as $\sigma(\C)$ in
Example \ref{exa:int2}. The Borel \sif\ of
subsets of $\Real^k$ is denoted $\B^k$.
\end{example}

\begin{exercise}\label{ex2_2}
Give some examples of classes of sets $\C$ such that $\sigma(\C) = \B^1$.
\end{exercise}

\begin{exercise}\label{ex2_3}
Are there subsets of $\Real$ which are not in $\B^1$?
\end{exercise}


\section{Measures}

\begin{notation}[Extended Reals] The {\em extended reals} is the set of all real
  numbers together with $\infty$ and $-\infty$.  We shall denote this
  set $\oReal$.  The {\em positive extended reals}, denoted
  $\oReal^+$ is $(0,\infty]$, and the {\em nonnegative
  extended reals}, denoted $\oReal^{+0}$ is $[0,\infty]$.
\end{notation}

\begin{definition}
Let $(\Omega,\F)$ be a measurable space.  Let
$\mu:\F\rightarrow\oReal^{+0}$ satisfy
\begin{itemize}
\item $\mu(\emptyset)=0$,
\item for every sequence $\{A_k\}_{k=1}^\infty$ of mutually disjoint
  elements of $\F$, $\mu(\bigcup_{k=1}^\infty A_k)=\sum_{k=1}^\infty\mu(A_k)$.
\end{itemize}
Then $\mu$ is called a \emindex{measure} on $(\Omega,\F)$ and
$(\Omega,\F,\mu)$ is a
{\em measure space}.  If $\F$ is merely a field, then a $\mu$ that
satisfies the above two conditions whenever
$\bigcup_{k=1}^\infty A_k\in\F$ is called a {\em measure on the field} $\F$.
\end{definition}

% {\bf Remark:} If $\mu$ is allowed to take values in $\oReal$, with the countably additive property,
% then it is called a \emph{signed measure}.

\begin{example}
Let $\Omega$ be arbitrary with $\F$ the trivial \sif.  Define
$\mu(\emptyset)=0$ and $\mu(\Omega)=c$ for arbitrary $c>0$ (with
$c=\infty$ possible).
\end{example}

\begin{example}[Counting measure]
Let $\Omega$ be arbitrary and $\F=2^\Omega$.  For each finite subset $A$
of $\Omega$, define $\mu(A)$ to be the number of elements of $A$.  Let
$\mu(A)=\infty$ for all infinite subsets.  This is called
\emindex{counting measure} on $\Omega$.
\end{example}

\begin{definition}[Probability measure]
Let $(\Omega,\F,P)$ be a measure space.
If $P(\Omega)=1$, then $P$ is called a {\em probability},
$(\Omega,\F,P)$ is a {\em probability space}, and elements of $\F$
are called {\em events}.
\end{definition}

Sometimes, if the name of the probability $P$ is understood or is not
even mentioned, we will denote $P(E)$ by $\Pr(E)$ for events $E$.

Infinite measures pose a few unique problems.  Some infinite
measures are just like finite ones.

\begin{definition}[\sfi\ measure]
Let $(\Omega,\F,\mu)$ be a measure space, and let $\C\subseteq\F$.
Suppose that there exists a
sequence $\{A_n\}_{n=1}^\infty$ of elements of $\C$ such that
$\mu(A_n)<\infty$ for all $n$ and $\Omega=\bigcup_{n=1}^\infty A_n$.
Then we say that $\mu$ is {\em \sfi\ on $\C$}. If $\mu$ is \sfi\ on
$\F$, we merely say that $\mu$ is {\em \sfi}.
\end{definition}

\begin{example}\label{sigfinex}
Let $\Omega=\Int$ with $\F=2^\Omega$ and $\mu$ being counting
measure.  This measure is \sfi.  Counting measure on an uncountable
space is not \sfi.
\end{example}

\begin{exercise}\label{ex2_4}
Prove the claims in Example \ref{sigfinex}.
\end{exercise}

\subsection{Basic properties of measures}
There are several useful properties
of measures that are worth knowing.

First, measures are countably subadditive in the sense that
\index{countable subadditivity}
\begin{equation}\label{eq:subadd}
\mu\left(\bigcup_{n=1}^\infty
  A_n\right)\leq\sum_{n=1}^\infty\mu(A_n),
\end{equation}
for arbitrary sequences $\{A_n\}_{n=1}^\infty$.
The proof of this uses a standard trick for dealing with countable
sequences of sets.  Let $B_1=A_1$ and let
$B_n=A_n\setminus\bigcup_{i=1}^{n-1}B_i$ for $n>1$.  The $B_n$'s are
disjoint and have the same finite and countable unions as the $A_n$'s.
The proof of Equation \ref{eq:subadd} relies on the additional fact that
$\mu(B_n)\leq\mu(A_n)$ for all $n$.

Next, if $\mu(A_n)=0$ for all $n$, it follows that
$\mu\left(\bigcup_{n=1}^\infty A_n\right)=0$.  This gets used a lot in
proofs.  Similarly, if $\mu$ is a probability and $\mu(A_n)=1$ for all
$n$, then $\mu\left(\bigcap_{n=1}^\infty A_n\right)=1$.

%this is skipped in the lecture, will introduce in week 2, in the discussion of integrals
\begin{definition}[Almost sure/almost everywhere]
\index{almost sure}
\index{almost everywhere}
Suppose that some statement about elements of $\Omega$ holds for all
$\omega\in A^C$ where $\mu(A)=0$.  Then we say that the statement
holds {\em almost everywhere}, denoted \ae\ $[\mu]$.  If $P$ is a
probability, then almost everywhere is often replaced by {\em almost
  surely}, denoted \as\ $[P]$.
\end{definition}

\begin{example}
\index{convergence!almost sure}
Let $(\Omega,\F,P)$ be a probability space.
Let $\{X_n\}_{n=1}^\infty$ be a sequence of functions from $\Omega$ to
$\Real$.  To say that $X_n$ converges to $X$ \as\ $[P]$ (denoted
$X_n\cas X$) means that there is a set $A$ with $P(A)=0$ and
$\lni X_n(\omega)=X(\omega)$ for all $\omega\in A^C$.
\end{example}

\begin{proposition}[Linearity]\label{thm:prop1}
If $\mu_1,\mu_2,\ldots$ are all measures on $(\Omega,\F)$ and if
$\{a_n\}_{n=1}^\infty$ is a sequence of positive numbers, then
$\sum_{n=1}^\infty a_n\mu_n$ is a measure on $(\Omega,\F)$.
\end{proposition}

\begin{exercise}\label{ex2_5}
Prove Proposition \ref{thm:prop1}.
\end{exercise}

% \begin{definition}
% Define the {\em indicator function} $I_A\!: \Omega \rightarrow \{0,1\}$
% for the set $A \subseteq \Omega$ as $I_A(\omega) = 1$ if $\omega \in A$
% and $I_A(\omega) = 0$ if $\omega \in A^C$.
% \end{definition}

\subsection{Monotone sequences of sets and limits of measure}
\begin{definition}[Monotone sequences of sets]
\index{monotone sequence}
Let $(\Omega,\F,\mu)$ be a measure space.  A sequence
$\{A_n\}_{n=1}^\infty$ of elements of $\F$ is called {\em monotone
  increasing} if $A_n\subseteq A_{n+1}$ for each $n$.  It is \emph{
  monotone decreasing} if $A_n\supseteq A_{n+1}$ for each $n$.
% For a general sequence, we define
% \begin{eqnarray*}
% \limsup_{n\rightarrow\infty}A_n&=&\bigcap_{i=1}^\infty\bigcup_{n=i}^\infty
% A_n,\\
% \liminf_{n\rightarrow\infty}A_n&=&\bigcup_{i=1}^\infty\bigcap_{n=i}^\infty A_n.
% \end{eqnarray*}
% If $\limsup_{n\rightarrow\infty}A_n=\liminf_{n\rightarrow\infty}A_n$,
% the common set is called $\lni A_n$.  The set
% $\limsup_{n\rightarrow\infty}A_n$ is often called
% {\em $A_n$ infinitely often}
% \index{infinitely often}
% or $A_n$ \io\ because a point
% $\omega$ is in that set if and only if $\omega$ is in infinitely many
% of the $A_n$ sets.  The set $\liminf_{n\rightarrow\infty}A_n$ is often
% called {\em $A_n$ all but
% finitely often}
% \index{all but finitely often}
% or {\em $A_n$ eventually} ($A_n$ ev.).  This set has
% all those $\omega$  such that $\omega$ is in all of the $A_n$ except
% possibly finitely many of the $A_n$, i.e., eventually.
 \end{definition}
%
% \begin{exercise}\label{ex2_6}
% What is the relationship between the definition of the $\limsup$ and
% $\liminf$ of a sequence of reals $\{x_n\}_{n=1}^\infty$ and this
% definition of the $\limsup$ and $\liminf$ of a sequence of sets?
% \end{exercise}
%
% \begin{exercise}\label{ex2_7}
% Define $A_n$ to be the set $(-1/n,1]$ if $n$ is odd, and to be $(-1,1/n]$
% if $n$ is even. What are $\limsup_{n\rightarrow\infty}A_n$ and
% $\liminf_{n\rightarrow\infty}A_n$?
% \end{exercise}
%
% It is easy to establish some simple facts about these limiting sets.
% \begin{proposition}\label{thm:prop2}
% Let $\{A_n\}_{n=1}^\infty$ be a sequence of sets.
% \begin{itemize}
% \item $\liminf_{n\rightarrow\infty}A_n=\limsup_{n\rightarrow\infty}A_n$,
% if and only if, for each $\omega$, $\lni I_{A_n}(\omega)$ exists.
% \item If the sequence is monotone increasing, then $\lni
%   A_n=\bigcup_{n=1}^\infty A_n$.
% \item If the sequence is monotone decreasing, then $\lni
%   A_n=\bigcap_{n=1}^\infty A_n$.
% \end{itemize}
% \end{proposition}
%
% \begin{exercise}\label{ex2_8}
% Prove Proposition \ref{thm:prop2}.
% \end{exercise}

\begin{lemma}\label{thm:monotone}
Let $(\Omega,\F,\mu)$ be a measure space.  Let
$\{A_n\}_{n=1}^\infty$ be a monotone sequence of elements of $\F$.
Then $\lni\mu(A_n)=
\mu\left(\lni A_n\right)$ if either of the
following hold:
\begin{itemize}
\item the sequence is increasing,
\item the sequence is decreasing and $\mu(A_k)<\infty$ for some $k$.
\end{itemize}
\end{lemma}
\begin{proof}
Define $A_\infty=\lni A_n$.
In the first case, write $B_1=A_1$ and $B_n=A_n\setminus A_{n-1}$ for
$n>1$.
Then $A_n=\bigcup_{k=1}^nB_k$ for all $n$ (including
$n=\infty$). Then
$\mu(A_n)=\sum_{k=1}^n\mu(B_k)$, and
\[\mu\left(\lni A_n\right)=\mu(A_\infty)=\sum_{k=1}^\infty\mu(B_k)
=\lni\sum_{k=1}^n\mu(B_k)=\lni\mu(A_n).\]
In the second case, write $B_n=A_n\setminus A_{n+1}$ for all $n\geq
k$.  Then, for all $n> k$,
\begin{eqnarray*}
A_k\setminus A_n&=&\bigcup_{i=k}^{n-1} B_i,\\
A_k\setminus A_\infty&=&\bigcup_{i=k}^\infty B_i.
\end{eqnarray*}
By the first case,
\[\lni\mu(A_k\setminus A_n)=\mu\left(\bigcup_{i=k}^\infty
  B_i\right)=\mu(A_k\setminus A_\infty).\]
Because $A_n\subseteq A_k$ for all $n>k$ and $A_\infty\subseteq A_k$, it
follows that
\begin{eqnarray*}
\mu(A_k\setminus A_n)&=&\mu(A_k)-\mu(A_n),\\
\mu(A_k\setminus A_\infty)&=&\mu(A_k)-\mu(A_\infty).
\end{eqnarray*}
It now follows that $\lni\mu(A_n)=\mu(A_\infty)$.
\end{proof}

\begin{exercise}\label{ex3_1}
Construct a simple counterexample to show that the condition
$\mu(A_k)<\infty$ is required in the second claim of
Lemma \ref{thm:monotone}.
\end{exercise}

\subsection{Uniqueness of Measures} There is a popular method for
proving uniqueness theorems about measures.
The idea is to define a function $\mu$ on a convenient class $\C$ of sets
and then prove that there can be at most one extension of $\mu$ to
$\sigma(\C)$.

\begin{example}\label{normex}
Suppose it is given that for any $a \in \Real$,
\[
   P\!\left((-\infty,a]\right) = \int_{-\infty}^a \frac{1}{\sqrt{2\pi}}
   \exp\!\left(-u^2/2\right) du.
\]
Does that uniquely define a probability measure
on the class of Borel subsets of the line, ${\cal B}^1$?
\end{example}

\begin{definition}[$\pi$-system and $\lambda$-system]
A collection $\A$ of subsets of $\Omega$ is a {\em $\pi$-system} if, for
all $A_1,A_2\in\A$, $A_1\cap A_2\in\A$.  A class $\C$ is a
\emindex{$\lambda$-system} if
\begin{itemize}
\item $\Omega\in\C$,
\item for each $A\in\C$, $A^C\in\C$,
\item for each sequence $\{A_n\}_{n=1}^\infty$ of disjoint elements of
  $\C$, $\bigcup_{n=1}^\infty A_n\in\C$.
\end{itemize}
\end{definition}
\begin{example}\label{exa:pisys}
The collection of all intervals of the form $(-\infty,a]$ is a
$\pi$-system of subsets of $\Real$.  So too is the collection of all
intervals of the form $(a,b]$ (together with $\emptyset$).  The
collection of all sets of the form $\{(x,y):x\leq a,y\leq b\}$ is a
$\pi$-system of subsets of $\Real^2$.  So too is the collection of all
rectangles with sides parallel to the coordinate axes.
\end{example}
Some simple results about $\pi$-systems and $\lambda$-systems are the
following.
\begin{proposition}\label{thm:pilam1}
If $\Omega$ is a set and $\C$ is both a $\pi$-system and a
$\lambda$-system, then $\C$ is a \sif.
\end{proposition}
\begin{proposition} \label{thm:pilam2}
Let $\Omega$ be a set and let $\Lambda$ be a $\lambda$-system of subsets.
If $A\in\Lambda$ and $A\cap B\in\Lambda$ then $A\cap B^C\in\Lambda$.
\end{proposition}

\begin{exercise}\label{ex3_2}
Prove Propositions \ref{thm:pilam1} and \ref{thm:pilam2}.
\end{exercise}

\begin{lemma}[$\pi-\lambda$ theorem]\label{thm:pilam}
\index{$\pi-\lambda$ theorem}
Let $\Omega$ be a set and let $\Pi$ be a $\pi$-system and let
$\Lambda$ be a $\lambda$-system that contains $\Pi$.
Then $\sigma(\Pi)\subseteq\Lambda$.
\end{lemma}
\begin{proof}
Define $\lambda(\Pi)$ to be the smallest $\lambda$-system containing
$\Pi$.  For each $A\subseteq \Omega$, define ${\cal G}_A$ to be the
collection of all sets $B\subseteq \Omega$ such that $A\cap B\in\lambda(\Pi)$.

First, we show that ${\cal G}_A$ is a $\lambda$-system for each
$A\in\lambda(\Pi)$.  To see this, note that $A\cap \Omega\in\lambda(\Pi)$, so
$\Omega\in{\cal G}_A$.  If $B\in{\cal G}_A$, then $A\cap B\in\lambda(\Pi)$,
and Proposition \ref{thm:pilam2} says that $A\cap B^C\in\lambda(\Pi)$, so
$B^C\in{\cal G}_A$.  Finally, $\{B_n\}_{n=1}^\infty\in{\cal G}_A$ with
the $B_n$ disjoint implies that $A\cap B_n\in\lambda(\Pi)$ with $A\cap
B_n$ disjoint, so their union is in $\lambda(\Pi)$.  But their union
is $A\cap\left(\bigcup_{n=1}^\infty B_n\right)$.  So $\bigcup_{n=1}^\infty
B_n\in{\cal G}_A$.

Next, we show that $\lambda(\Pi)\subseteq{\cal G}_C$ for every
$C\in\lambda(\Pi)$. Let $A,B\in\Pi$, and notice that $A\cap B\in\Pi$,
so $B\in{\cal
G}_A$.  Since ${\cal G}_A$ is a $\lambda$-system containing $\Pi$, it
must contain $\lambda(\Pi)$.  It follows that $A\cap C\in\lambda(\Pi)$
for all $C\in\lambda(\Pi)$.  If $C\in\lambda(\Pi)$, it then follows
that $A\in{\cal G}_C$.  So, $\Pi\subseteq{\cal G}_C$ for all
$C\in\lambda(\Pi)$.  Since ${\cal G}_C$ is a $\lambda$-system
containing $\Pi$, it must contain $\lambda(\Pi)$.

Finally, if $A,B\in\lambda(\Pi)$, we just proved that $B\in{\cal G}_A$, so
$A\cap B\in\lambda(\Pi)$ and hence $\lambda(\Pi)$ is also a $\pi$-system.
By Proposition \ref{thm:pilam1}, $\lambda(\Pi)$ is a \sif\ containing
$\Pi$ and hence must contain $\sigma(\Pi)$.  Since
$\lambda(\Pi)\subseteq\Lambda$, the proof is complete.
\end{proof}

% I am guessing that at one time the definition of $\sigma$-finite
% was here - CMS
%We need one important property of measures before proving the
%uniqueness theorem.

\vspace{.1in}
The uniqueness theorem is the following.
\begin{theorem}[Uniqueness theorem]\label{thm:pilam3}
\index{Uniqueness theorem}
Suppose that $\mu_1$ and $\mu_2$ are measures on $(\Omega,\F)$ and $\F=\sigma(\Pi)$,
for a $\pi$-system $\Pi$.  If $\mu_1$ and
$\mu_2$ are both \sfi\ on $\Pi$ and they agree on $\Pi$,
then they agree on $\F$.
\end{theorem}
\begin{proof}
First, let $C\in\Pi$ be such that $\mu_1(C)=\mu_2(C)<\infty$, and define
${\cal G}_C$ to be the collection of all $B\in\F$ such
that $\mu_1(B\cap C)=\mu_2(B\cap C)$.  It is easy to see that ${\cal
  G}_C$ is a $\lambda$-system that
contains $\Pi$, hence it equals $\F$ by Lemma \ref{thm:pilam}.  (For
example, if $B\in{\cal G}_C$,
\[\mu_1(B^C\cap C)=\mu_1(C)-\mu_1(B\cap C)=\mu_2(C)-\mu_2(B\cap
C)=\mu_2(B^C\cap C),\]
so $B^C\in{\cal G}_C$.)

Since $\mu_1$ and $\mu_2$ are \sfi, there exists a sequence
$\{C_n\}_{n=1}^\infty\in\Pi$ such that $\mu_1(C_n)=\mu_2(C_n)<\infty$,
and $\Omega=\bigcup_{n=1}^\infty C_n$.  (Since $\Pi$ is only a $\pi$-system,
we cannot assume that the $C_n$ are disjoint.)  For each $A\in\F$,
\[\mu_j(A)=\lni\mu_j\left(\bigcup_{i=1}^n[C_i\cap A]\right)\mbox{ for
$j=1,2$}.\]
Since $\mu_j\left(\bigcup_{i=1}^n[C_i\cap A]\right)$ can be written as a linear
combination of values of $\mu_j$ at sets of the form $A\cap C$, where
$C\in\Pi$ is the intersection of finitely many of $C_1,\ldots,C_n$, it
follows from $A\in{\cal G}_C$ that $\mu_1\left(\bigcup_{i=1}^n[C_i\cap
A]\right)=\mu_2\left(\bigcup_{i=1}^n[C_i\cap A]\right)$ for all $n$,
hence $\mu_1(A)=\mu_2(A)$.
\end{proof}

\begin{exercise}\label{ex3_3}
Return to Example \ref{normex}. You should now be able to answer the question
posed there.
\end{exercise}

\begin{exercise}\label{ex3_4}
Suppose that $\Omega = \{a,b,c,d,e\}$ and I tell you the value of $P(\{a,b\})$
and $P(\{b,c\})$. For which subset of $\Omega$ do I need to define $P(\cdot)$
in order to have a unique extension of $P$ to a $\sigma$-field of subsets
of $\Omega$?
\end{exercise}


\section{Lebesgue Measure and Caratheodory's Extension Theorem}
Let $F$ be a
cdf (nondecreasing, right-continuous, limits equal 0 and
1 at $-\infty$ and $\infty$ respectively).  Let $\U$ be the field in
Example \ref{exa:intervals} (unions of finitely many disjoint intervals).   Define
$\mu:\U\rightarrow[0,1]$ by $\mu(A)=\sum_{k=1}^nF(b_k)-F(a_k)$ when
$A=\bigcup_{k=1}^n(a_k,b_k]$ and
$\{(a_k,b_k]\}$ are disjoint. This set-function is well-defined and
finitely additive.  % To see that it is well-defined, look at an alternative
% representation as $\mu(A)=\sum_{j=1}^mF(d_j)-F(c_j)$.  Consider the
% partition of $A$ into the refinement of the two partitions given.  The
% sum over the refinement is the same as both of the two sums we started
% with.

Is $\mu$ countably additive as probabilities are
supposed to be?  That is, if $A=\bigcup_{i=1}^\infty A_i$ where the
$A_i$'s are disjoint, each $A_i$ is a union of finitely many
disjoint intervals, and $A$ itself is the union of finitely many
disjoint intervals $(a_k,b_k]$ for $k=1,\ldots,n$, does
$\mu(A)=\sum_{i=1}^\infty\mu(A_i)$?  First, take the collection of
intervals that go into all of the $A_i$'s and split them, if
necessary, so that each is a subset of at most one of the $(a_k,b_k]$
intervals.  Then apply the following result to each $(a_k,b_k]$.

\begin{lemma}\label{thm:sum1}
Let $(a,b]=\bigcup_{k=1}^\infty(c_k,d_k]$ with the $(c_k,d_k]$'s disjoint.
Then $F(b)-F(a)=\sum_{k=1}^\infty F(d_k)-F(c_k)$.
\end{lemma}

\begin{proof}
Since $(a,b]\supseteq\bigcup_{k=1}^n(c_k,d_k]$ for all $n$, it follows
that $F(b)-F(a)\geq\sum_{k=1}^nF(d_k)-F(c_k)$ (because $(c_k, d_k)$'s are disjoint), hence
$F(b)-F(a)\geq\sum_{k=1}^\infty F(d_k)-F(c_k)$.  We need to prove the
opposite inequality.

Suppose first that both $a$ and $b$ are finite.
Let $\epsilon>0$.  For each $k$, there is
$e_k>d_k$ such that
\[F(d_k)\leq F(e_k)\leq F(d_k)+\frac{\epsilon}{2^k}.\]
Also, there is $f>a$ such that $F(a)\geq F(f)-\epsilon$.  Now, the
interval $[f,b]$ is compact and
$[f,b]\subseteq\bigcup_{k=1}^\infty(c_k,e_k)$.  So there are finitely
many $(c_k,e_k)$'s (suppose they are the first $n$) such that
$[f,b]\subseteq\bigcup_{k=1}^n(c_k,e_k)$.  Now,
\[F(b)-F(a)\leq F(b)-F(f)+\epsilon\leq\epsilon+\sum_{k=1}^nF(e_k)-F(c_k)
\leq2\epsilon+\sum_{k=1}^nF(d_k)-F(c_k).\]
It follows that $F(b)-F(a)\leq2\epsilon+\sum_{k=1}^\infty
F(d_k)-F(c_k)$.  Since this is true for all $\epsilon>0$, it is true
for $\epsilon=0$.

If $-\infty=a<b<\infty$, let $g>-\infty$ be such that
$F(g)<\epsilon$.
The above argument shows that
\[F(b)-F(g)\leq\sum_{k=1}^\infty F(d_k\vee g)-F(c_k\vee g)
\leq\sum_{k=1}^\infty F(d_k)-F(c_k).\]
Since $\lim_{g\rightarrow-\infty}F(g)=0$, it follows that
$F(b)\leq\sum_{k=1}^\infty F(d_k)-F(c_k)$.  Similar arguments work
when $a<b=\infty$ and $-\infty=a<b=\infty$.
\end{proof}


In Lemma \ref{thm:sum1} you can replace $F$ by an
arbitrary nondecreasing right-continuous function with only a bit more
effort.
(See the supplement following at the end of this lecture.)

The function $\mu$ defined in terms of a nondecreasing
right-continuous function is a measure on the field $\U$.
There is an extension theorem that gives conditions under which a
measure on a field can be extended to a measure on the generated
\sif.  Furthermore, the extension is unique.

\begin{example}[Lebesgue measure]
\index{Lebesgue measure}
Start with the function
  $F(x)=x$, form the measure $\mu$ on the field $\U$ and extend it to
  the Borel \sif.  The result is called {\em Lebesgue measure}, and it
  extends the concept of ``length'' from intervals to more general sets.
\end{example}

\begin{example}
Every distribution function for a random variable has a corresponding
probability measure on the real line.
\end{example}

% Another concept that is occasionally useful is that of a complete
% measure space.
%
% \begin{definition}\label{def:comp1}
% \index{complete}
% A measure space $(\Omega,\F,\mu)$ is \emindex{complete} if, for every
% $A\in\F$ such that $\mu(A)=0$ and every $B\subseteq A$, $B\in\F$.
% \end{definition}

\begin{theorem}[Caratheodory Extension]\label{thm:cet}
\index{Caratheodory extension theorem}
\index{extension theorem}
Let $\mu$ be a \sfi\ measure on the field $\C$ of subsets of $\Omega$.
Then $\mu$ has a unique extension to a measure on $\sigma(\A)$.%   Furthermore
% $(\Omega,\A,\mu^*)$ is a complete measure space.
\end{theorem}

\begin{exercise}\label{ex4_1}
In this exercise, we prove Theorem \ref{thm:cet}.  Note that the uniqueness of the extension is a direct
consequence of
Theorem \ref{thm:pilam3}.  We only need to prove the existence.

First,
for each $B\in2^\Omega$, define
\begin{equation}\label{eq:mustdef}
\mu^*(B)=\inf\sum_{i=1}^\infty\mu(A_i),
\end{equation}
where the $\inf$ is taken over all $\{A_i\}_{i=1}^\infty$ such that
$B\subseteq\bigcup_{i=1}^\infty A_i$ and $A_i\in\C$ for all $i$.
Since $\C$ is a field, we can assume that the $A_i$'s are mutually
disjoint without changing the value of $\mu^*(B)$. Let
\[\A=\{B\in2^\Omega: \mu^*(C)=\mu^*(C\cap B)+\mu^*(C\cap B^C),\mbox{ for
all $C\in2^\Omega$}\}.\]

Now take the following steps:
\begin{enumerate}
\item Show that $\mu^*$ extends $\mu$, i.e. that $\mu^*(A) = \mu(A)$ for
each $A \in {\cal C}$.
\item Show that $\mu^*$ is monotone and subadditive.
\item Show that ${\cal C} \subseteq {\cal A}$.
\item Show that ${\cal A}$ is a field.
\item Show that $\mu^*$ is finitely additive on ${\cal A}$.
\item Show that ${\cal A}$ is a $\sigma$-field.
\item Show that $\mu^*$ is countably additive on ${\cal A}$.
% \item Show that $\mu^*$ is the unique extension of $\mu$ to a measure of $(\Omega, {\cal A})$.
% \item Show that $(\Omega, {\cal A}, \mu^*)$ is a complete measure space.
\end{enumerate}
\end{exercise}

\newpage
\begin{center}
{\Large\bf Supplement: Measures from Increasing Functions}
\end{center}

Lemma \ref{thm:sum1} deals only with functions $F$ that are cdf's.  Suppose
that $F$ is an unbounded nondecreasing function that is continuous
from the right.  If $-\infty<a<b<\infty$, then the proof of
Lemma \ref{thm:sum1} still applies.  Suppose that
$(-\infty,b]=\bigcup_{k=1}^\infty(c_k,d_k]$ with $b<\infty$ nd all
$(c_k,d_k]$ disjoint.  Suppose that $\lim_{x\rightarrow-\infty}F(x)=-\infty$.
We want to show that $\sum_{k=1}^\infty F(d_k)-F(c_k)=\infty$.
If one $c_k=-\infty$, the proof is immediate, so assume that all
$c_k>-\infty$.  Then there must be a subsequence
$\{k_j\}_{j=1}^\infty$ such that
$\lim_{j\rightarrow\infty}c_{k_j}=-\infty$.  For each $j$, let
$\{(c'_{j,n},d'_{j,n}]\}_{n=1}^\infty$ be the subsequence of intervals that
cover $(c_{k_j},b]$.  For each $j$, the proof of Lemma \ref{thm:sum1}
applies to show that
\begin{equation}\label{eq:leb1}
F(b)-F(c_{k_j})=\sum_{n=1}^\infty F(d'_{j,n})-F(c'_{j,n}).
\end{equation}
As $j\rightarrow\infty$, the left side of Equation \ref{eq:leb1} goes to
$\infty$ while the right side eventually includes every interval in
the original collection.

A similar proof works for an interval of the form $(a,\infty)$ when
$\lim_{x\rightarrow\infty}F(x)=\infty$.  A
combination of the two works for $(-\infty,\infty)$.
\end{document} 