\documentclass[11pt]{report}
\usepackage{smstc,probability,color,mathrsfs}
\usepackage{showkeys}
%% amsmath, amssymb, cite, fancybox, graphicx, ifthen, minitoc, url, xspace
\Streamname{Probability}  
\Unitname{} 
\Thisyear{2007/08}  
\AuthorFt{Takis Konstantopoulos, Heriot-Watt University}

\newtheorem{drill}{Drill}
\newtheorem{example}{Example}[section]
\newtheorem{definition}{Definition}[section]
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\FF{\mathscr{F}}
\def\CC{\mathscr{C}}
\def\RR{\mathscr{R}}
\def\AA{\mathscr{A}}
\def\SS{\mathscr{S}}
\def\TT{\mathscr{T}}
\def\BB{\mathscr{B}}
\def\VV{\mathscr{V}}
\def\LL{\mathcal{L}}
\def\Qr{\mathbf{Q}}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\1}{{\text{\Large $\mathfrak 1$}}}
\renewcommand{\comp}{\raisebox{0.1ex}{\scriptsize $\circ$}}
\newcommand{\cadlag}{{c\`adl\`ag} }
\renewcommand{\var}{\operatorname{var}}
\renewcommand{\cov}{\operatorname{cov}}
\renewcommand{\limsup}{\varlimsup}
\renewcommand{\liminf}{\varliminf}
\renewcommand{\d}{\text{\rm\,d}}
\newcommand{\eqdist}{\stackrel{\text{d}}{=}}
\newcommand{\dirac}{\text{\large $\mathfrak d$}}
\newcommand{\Ri}{\Rightarrow}
\def\iid{{i.i.d.}\xspace}
\def\jid{{i.i.d.}}
\def\ie{{i.e.}\xspace}
\def\eg{{e.g.}\xspace}
%A \xrightarrow[n]{} 0
\def\bigtimes{\text{\LARGE$\times$}}
\def\xor{\text{\footnotesize$\bigtriangleup$}}
\def\prob{\operatorname{\bf prob}}

\parskip \smallskipamount
\parindent 5mm


\begin{document} \initdoc 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{3}{Random variables}

 Random variables and their distributions.				TK
      Distribution functions, probability (mass) functions,
      probability density functions, moments, simple inequalities
      (Markov, Chebychev), transformations.  Moment generating
      functions (briefly).

\noindent{\sf Organisation: This chapter contains simple exercises throughout
the text, called ``drills'', and more substantial exercises at the end. The
Glossary section summarises notation and basic maths needed. Without this
kind of maths, there is no way you can learn Probability.}

\section{Motivation}

\section{Random variables are functions}


{\sc A random variable is a measurable function}
 $X$ between two measurable spaces,
an ``abstract'' one $(\Omega, \FF)$ and a ``concrete''\footnote{
The adjectives in quotes have nothing to do with Mathematics but, rather, with
our human interpretation of it. 
}
one $(S, \SS)$.
In other words, we require that the inverse image by $X$ of each element 
of $\SS$ be an element of $\FF$.
We denote this situation by 
\[
X : (\Omega, \FF) \to (S, \SS).
\]
Many a times $(\Omega, \FF)$ could (or should) be left unspecified but 
$(S, \SS)$ should be chosen specifically;
for example it could be $(\R, \BB)$, where $\BB=\BB(\R)$ is the class of
Borel sets on $\R$. In such a case we call $X$ {\sc ONE (real) random variable},
omiting the numeral ONE when not necessary. As another example, let
$(S, \SS) = (\R^2, \BB(\R^2))$, where $\BB(\R^2)$ are the Borel sets on $\R^2$.
In this case we refer to $X$ as {\sc TWO (real) random variables}, because 
we may,
by choosing Cartesian co\"ordinates on $\R^2$, represent
$X$ by $(X_1, X_2)$, where $X_1$ is one random variable and $X_2$ is
also one random variable.
More generally, we may let $(S, \SS) =(\R^d, \BB(\R^d))$, and then
we refer to $X$ a {\sc random ($d$-dimensional real) vector}.

Terminology: we say that $X$ is a random variables IN $S$ or
that $X$ is a random element OF $S$.
If $S$ is a concrete space with a name ``abc'' then we call $X$ a random
``abc''. For instance, if $S$ is the space of triangles on the plane, then
a random variable in $X$ is called random triangle.


\begin{drill}
\label{drill1}
Show that if $X: (\Omega, \FF) \to (S, \SS)$, $H: (S, \SS) \to (T, \TT)$
are random variables then $H \comp X$ is a random variable.
\end{drill}

The following lemma, useful in checking that a function is a random variable:
\begin{lemma}
\label{bang}
If $X : \Omega \to S$ is a function, $\FF$ a $\sigma$-field on $\Omega$
and $\SS$ a  $\sigma$-field on $S$ generated by the collection of
sets $\CC$ then $X$ is a random variable if and ony if 
$X^{-1}(B) \in \FF$ for all
$B \in \CC$.
\end{lemma}
\begin{proof}
Let $\SS' := \{ B \subset S:~ X^{-1}(B) \in \FF\}$.
This is a $\sigma$-field. Indeed, if $B \in \SS'$ then
$X^{-1}(B^c) = X^{-1}(B)^c \in \FF$ because $X^{-1}(B) \in \FF$.
If $B_1, B_2, \ldots \in \SS'$ then $X^{-1} (\cap_j B_j)
= \cap_j X^{-1}(B_j) \in \FF$ because each $X^{-1}(B_j) \in \FF$.
Suppose that $X^{-1}(B) \in \FF$ for all $B \in \CC$.
This means that $\CC$ is contained in $\SS'$.
But then $\SS$ which is the smallest $\sigma$-field containing $\CC$
must be contained in $\SS'$ for the latter is a $\sigma$-field.
In symbols, $\SS \subset \SS'$. But, by definition of $\SS'$, this means
that $X^{-1}(B) \in \FF$ for any $B \in \SS$.
\end{proof}

Recall that the notation
\[
\{X \in B\} = X^{-1}(B)
\]
is used all the time, so we will stick to it when we can.
\begin{corollary}
If $X: \Omega \to \R$ is a function and $\FF$ a $\sigma$-field on $\Omega$,
then $X$ is one random variable 
$\iff$ $\{X \le x\} \in \FF$ for all $x \in \R$
$\iff$ $\{X < x\} \in \FF$ for all $x \in \R$
$\iff$ $\{X > x\} \in \FF$ for all $x \in \R$.
\end{corollary}

The real fun of course starts when $(S, \SS)$ is chosen to be a large 
(but concrete) space, for example, $S$ can be a subset of
a space of real-valued functions on the real line and $\SS$ a suitable
$\sigma$-field. 
In such a case, $X$ is called {\sc random function} or {\sc stochastic process}
(stochastic being a synonym of random and process being a synonym
of function; therefore, random process or stochastic function
are also acceptable terminologies for the same thing).


\section{Continuous functions of random variables}
\begin{lemma}
If $X$ is a random vector in $\R^d$ and $f: \R^d \to \R^k$ is
a continuous function then $f \comp X$ is a random vector in $\R^k$.
\end{lemma}
\begin{proof}
Let $B$ be an open subset of $\R^k$. Then $f^{-1}(B)$ is an open
subset of $\R^d$ because $f$ is continuous. Hence $f^{-1}(B)$
is a Borel subset of $\R^d$ and so $f$ is measurable. Now use Drill
\ref{drill1}.
\end{proof}

An application of this is that all usual algebraic operations
on random variables will result random variables. So
\[
X_1 + X_2,
\quad
X_1 \cdot X_2,
\quad
X_1 \wedge X_2
\]
are all random variables.




A more important result is that we can go beyond algebraic operations
and retain measurability. So
\begin{lemma}
\label{balg}
If $X_1, X_2, \ldots$ are random variables in $\R$ then
\[
\inf_j X_j, \quad \liminf_j X_j,
\quad
\sup_j X_j, \quad \limsup_j X_j
\]
are random variables in $\R \cup\{+\infty, -\infty\}$.
\end{lemma}
\begin{proof}
Indeed,
\[
\{\inf_j X_j \le a\} = \cap_j \{X_j \le a\}
\]
and, since $\{X_j \le a\} \in \FF$ for all $j$, and $\FF$ is a $\sigma$-field,
then the interesection also belongs to $\FF$.
For the second variable, we simply observe that $\sup_j X_j = - \inf_j (-X_j)$
is also a random variable and so $\liminf_j X_j = \sup_j \inf_{k \ge j} X_k$
is also a random variable.
\end{proof}


\section{Induced $\sigma$-fields; measurability}
The $\sigma$-field {sc generated} or {\sc induced}
by a random variable $X : (\Omega, \FF) \to
(S, \SS)$ is defined by
\[
\sigma(X) = \{X^{-1}(B), B \in \SS\}.
\]
It is easy to see that 
\begin{lemma}
(i) $\sigma(X)$ is a $\sigma$-field,
(ii) $\sigma(X)$ is the intersection of all $\sigma$-fields
$\GG \subset \FF$ such that $X: (\Omega, \GG) \to (S, \SS)$ is 
a random variable,
(iii) $X$ is a random variable if and only if $\sigma(X) \subset \FF$.
\end{lemma}

\begin{lemma}
If $X_i : (\Omega, \FF) \to (S_i, \SS_i)$, $i=1,2, \ldots,d$
are random variables, then $(X_1, \ldots, X_d) : (\Omega, \FF)
\to (S, \SS)$  is a random variable (vector), 
where $S= S_1 \times \cdots \times
S_d$, $\SS = \SS_1 \otimes \cdots \otimes \SS_d$.
%The $\sigma$-field generated by $(X_1, \ldots, X_d)$
%is, as above,
%\[
%\sigma(X_1, \ldots, X_d) = \{(X_1, \ldots, X_d)^{-1}(B), B \in \BB(\R^d)\}.
%\]
Furthermore,
\[
\sigma(X_1, \ldots, X_d) = \sigma(X_1) \vee \cdots \vee \sigma(X_d).
\]
\end{lemma}
\begin{proof}
We just have to check that $(X_1,\ldots,X_d)^{-1}(B) \in \FF$ for
$B$ ranging in a suitable $\pi$-system. We take this $\pi$-system
(and it is immediate to see that it is so)
to be all sets of the form $B_1 \times \cdots \times B_d$, 
where $B_j \in \SS_j$ for all $1 \le j \le d$.
Then $(X_1,\ldots,X_d)^{-1}(B_1 \times \cdots \times B_d)
= \{(X_1,\ldots,X_d) \in B_1 \times \cdots \times B_d\}
= \{X_1 \in B_1\} \cap \cdots \cap \{X_d \in B_d\} \in \FF$.
\end{proof}

Moreover, and more importantly for all the theory
of stochastic processes, we can carry this to infinity. 
\begin{lemma}
Suppose that for each $i \in \N$,  $X_i: (\Omega, \FF) \to (S_i, \SS_i)$
is a random variable. 
Let $S = \bigtimes_{i=1}^\infty S_i$ and let $X=(X_1, X_2, \ldots):
(\Omega, \FF) \to (S, \SS)$, where $\SS = \bigotimes_{i=1}^\infty  \SS_i$
is the product-sigma field.
Then $X$ is a random variable.
Moreover,
\[
\sigma(X_1, X_2, \ldots) = \bigvee_{i=1}^\infty \sigma(X_i)
= \bigvee_{i=1}^\infty \bigvee_{k=1}^j \sigma(X_1, \ldots, X_k).
\]
\end{lemma}
\begin{proof}
Consider the $\pi$-system consisting of sets of the form
$\cap_{i=1}^\infty B_i$ where $B_i \in \SS_i$ for all $i$,
and where $B_i = S_i$ for all but finitely many indices $i$.
\end{proof}

We should view $\sigma(X)$ as the essential information contained in $X$.
We explain: If $\Omega$ is a set and $X : \Omega \to S$ a function then
just by looking at the values of $X$ we may not be able to distinguish
elements of $\Omega$, simply because $X$ may take the same value on
different points of $\Omega$. In other words, unless $X$ is one-to-one, 
the set $X(\Omega) = \{X(\omega), \omega \in \Omega\}$
contains ``less information'' than $\Omega$.
Take a trivial example: Let $\Omega =\{-N, -N+1, \ldots, N-1, N\}$, 
and let $X(i) = i^3$ for all $i \in \Omega$.
Then $X(\Omega)$ contains precisely
the same information as $\Omega$. But if $Y(i) = i^2$ then $Y(\Omega)$ is
less informative than $\Omega$ because the sign is lost.
In some sense, we are not interested in the exact values of a random
variable but only on whether the values can distinguish elements of $\Omega$.

Take an abstract set $\Omega$ (for example think of $\Omega$ as a square
in the 2-dimensional Euclidean plane), let $A \subset \Omega$ and consider
the random variable $\1_A$. This takes only two values, $0$ and $1$, so the
information conveyed by it is not that large. Indeed,
\[
\sigma(\1_A) = \{\varnothing, A, A^c, \Omega\}
\]
We may represent $\sigma(\1_A)$ as a partition of $\Omega$, the partition
consisting of $A$ and its complement. Thus, $\1_A$ can only tell
us whether we are on $A$ or on its complement: very little information indeed.
But we may as well use any function of $\1_A$ that does
not compress it further, for example, $c \cdot \1_A$, where $c$ is a nonzero
constant. 
\begin{drill}
\label{drill4}
Consider two subsets $A_1, A_2$ of $\Omega$ and prove that the 
$\sigma$-field generated by $c_1\1_{A_1} + c_2 \1_{A_2}$ is
\begin{multline*}
\{\varnothing,~ \Omega,~
A_1,~ A_2,~ 
A_1^c,~ A_2^c,~ 
A_1A_2,~ A_1 A_2^c,~ A_1^c A_2,~ A_1^c A_2^c,~
\\
A_1 \cup A_2,~ A_1 \cup  A_2^c,~ A_1^c \cup  A_2,~ A_1^c \cup  A_2^c,~
A_1 \xor A_2,~
(A_1 \xor A_2)^c
\}.
\end{multline*}
\end{drill}
It is more convenient to represent this $\sigma$-field by the 
partition of $\Omega$ induced by $A_1, A_2$, i.e.\ by the
collection of disjoint sets
\[
\{
A_1 A_2, ~ A_1 \setminus A_2, ~ A_2 \setminus A_1, ~ (A_1 A_2)^c
\}.
\]
\begin{drill}
Any nonempty set in Drill \ref{drill4} can be obtained as union of
elements of this partition.
\end{drill}
\begin{drill}
\label{drill6}
Given a partition $\CC =\{C_1, \ldots, C_n\}$ of $\Omega$ show that
the $\sigma$-field generated by $\CC$ consists of the empty set and
all sets that can be obtained by taking unions of sets in $\CC$.
Assuming that none of the $C_i$ is empty, this $\CC$ contains 
exactly $2^n$ sets.
Also show that any random variable that takes value $b_i$ on $C_i$ for each $i$
generates a $\sigma$-field which is contained in $\sigma(\CC)$. Show
that if the values $b_i$ are distrinct then $\sigma(X) = \sigma(\CC)$.
\end{drill}

Unfortunately, this partition point of view does not carry over to
big spaces. It works well for finite $\Omega$ or for general $\Omega$ but
small $\sigma$-fields, but fails in richer situations. However, the intuition
obtained remains, in some sense, valid.
Let us explore this further.


If $X, Y$ are random variables on a common measurable space $(\Omega, \FF)$
(and values in arbitrary sets)
we say that {\sc $Y$ is measurable with respect to $X$} if 
\[
\sigma(Y) \subset \sigma(X).
\]
We often write this as
\[
Y \in \sigma(X).
\]
For example, if $X$ is one random variable then $X^2$ is measurable
with respect to $X$ (but not vice-versa); if
$(X_1, X_2, X_3)$ are three random variables then 
$(X_1, X_2)$ is measurable with respect to $(X_1, X_2, X_3)$ and
so is $(\cos(X_1 + X_2), - X_3 + \log|X_1|)$.
If it appears that ``measurability with respect to'' means
``(suitable) function of'' then this is because it really is so:
\begin{lemma}
\label{fof}
If $X: (\Omega, \FF) \to (S, \SS)$, $Y: (\Omega, \FF) \to (\R, \BB)$
are random variables, and if $Y \in \sigma(X)$, then
there exists a random variable (measurable map) 
$H: (S, \SS) \to (\R, \BB)$ such that $Y = H \comp X$.
\end{lemma}
(The proof is deferred until the next page or so.)
To understand why let us consider first a trivial situation: suppose
that $X$ takes only finitely many values; let $x_1, \ldots, x_n$ be these
(distinct) values.
\begin{drill}
Show that if $X(\Omega)=\{x_1, \ldots, x_n\}$ is a finite set
then $\sigma(X)$ is generated by the partition 
$\big\{\{X=x_i\}, ~ i=1,\ldots,n\big\}$ of $\Omega$.
\end{drill}
\begin{drill}
Using Drill \ref{drill6} show that any $Y$, measurable with respect to
$X$, must be of the form
\[
Y = \sum_{i=1}^n c_i \1(X=x_i).
\]
\end{drill}
We then see that what is claimed in Lemma \ref{fof} is correct, in this
special situation with $X$ being finitely-valued. Indeed, let
$H(x) = \sum_{i=1}^n c_i \1(x=x_i)$ and, obviously, $Y = H \comp X$.


The general case requires an approximation result that says that
any measurable random variable $X: (\Omega, \FF) \to (\R, \BB)$ can
be approximated by simple random variables. A {\sc simple random
variable} is a random variable with finitely many values.
%\begin{drill}
%Show that a simple random variable $X:(\Omega, \FF) \to (\R, \BB)$
%is a random variable of the form
%\[
%X = \sum_{i=1}^k c_i \1_{A_i},
%\]
%where $c_i \in \R$, $A_i \in \FF$, $1\le i \le k$, $k \in \N$.
%Show that this representation may not be unique. However, if the
%sets are disjoint
%\end{drill}
\begin{lemma}
\label{sa}
Let $X : (\Omega, \FF) \to (\R, \BB)$. Then there exists
a sequence $X_1, X_2, \ldots$ of simple random variables such that
$\lim_{n\to\infty} X_n(\omega) = X(\omega)$.
If $X(\omega) \ge 0$, $\omega \in \Omega$, we can choose the sequence so that
$0 \le X_n(\omega) \le X_{n+1}(\omega)$ for each $n$ and $\omega$.
\end{lemma}
\begin{proof}
First suppose $X(\omega) \ge 0$ for all $\omega \in \Omega$.
Let $\lceil x\rceil$ denote the smallest integer $k$ such that 
$k \ge x$. Define
\begin{gather}
\label{tau}
\tau_n(x) := 2^{-n} \lceil 2^n x\rceil  \wedge n.\\
X_n(\omega):= \tau_n(X(\omega)). 
\end{gather}
That $X_n(\omega) \to X(\omega)$ as $n \to \infty$ is obvious.
Since $\lceil a \rceil \le a$ we have $2\lceil a \rceil \le \lceil 2a \rceil$
and so $2\lceil 2^n X \rceil \le \lceil 2^{n+1} X \rceil$. Dividing both sides with $2^{n+1}$
we have $2^{-n}\lceil 2^n X \rceil \le 2^{-n-1} \lceil 2^{n+1} X \rceil$ and so $X_n \le X_{n+1}$. 
Next do not place any requirement on the sign of $X$ but observe that
\[
X = X^+ - X^-.
\]
Then reduce to the previous case.
\end{proof}

\noindent{\bf Proof of Lemma \ref{fof} }
Suppose first that $Y=\1_A$ for some $A \in \FF$ and that $Y \in \sigma(X)$. 
This means that $A \in \sigma(X)$. By definition of $\sigma(X)$, there
is a $B \in \BB$ such that $A = X^{-1}(B)$. Define $H(x) =\1(x \in B)$,
$x \in \R$. Then $H(X(\omega)) = \1(X(\omega) \in B) = 
\1(\omega \in X^{-1}(B)) = \1(\omega \in A) = Y(\omega)$ and
so $H \comp X = Y$, as required.
Suppose next that $Y$ is a simple random variable. Thus $Y=\sum_{i=1}^k
c_i \1_{A_i}$ where $A_i \in \FF$. By the previous case, there
are $H_i :(S, \SS) \to (\R, \BB)$, such that $\1_{A_i} = H_i(X)$.
Define $H(x) = \sum_{i=1}^k c_i H_i(x)$. Then, clearly, $H(X) = Y$.
Finally, suppose that $Y: (\Omega, \FF) \to (\R, \BB)$ is a 
positive random variable. Then, by lemma \ref{sa}, we can find
simple $Y_n: (\Omega, \FF) \to (\R, \BB)$, for all $n \in \N$,
such that $Y = \sup_n Y_n$.
By the case analysed above, we have, for each $n$,
a measurable function $H_n$ such that $Y_n = H_n \comp X$.
Define $H = \sup_n H_n$. By Lemma \ref{balg}, $H$ is measurable.
Also, $H \comp X = (\sup_n H_n) \comp X
= \sup_n (H_n \comp X) = \sup_n Y_n = Y$, as required.
In the general case, write $Y = Y^+-Y^-$ and reduce to the above one.
$\Box$

\begin{drill}
Let $X$ be one random variable in $\R$. Show that $\sigma(X^2)$
is a strict subset of $\sigma(X)$.
\end{drill}

\noindent{\bf Remark }
Lemma \ref{fof} is very important in enhancing our understanding of
measurability. Measurability, in Probability Theory (as well as in other
areas of Mathematics like Descriptive Set Theory) is not an abstract
notion but conveys precisely the idea of ``information'' contained in
a measurement. 
%When a physicist performs an experiment he does not
%want to distinguish between all of his subatomic particles but merely
%measure some
It should also be stressed that 
$Y$ in Lemma \ref{fof} does not have to be restricted to take values in $\R$.
It could very well be a random vector (values in $\R^d$) or, more
generally, a random element of a fairly arbitrary space known as 
Polish space. We shall not enter into such advanced details here.

\begin{lemma}
Let $(S, \SS)$ be a measurable space and $T$ an index set.
Let $S^T$ be the set of functions from $T$ to $S$ equipped
with the product $\sigma$-field $\SS^T = \bigotimes_{t \in T} \SS$.
Let $V \subset S^T$. Let $\VV:=\{B \cap V:~ B \in \SS^T\}$.
Let $\pi_t: S^T \to S$ be the projection function on the $t$-th coordinate,
i.e.\ let $\pi_t(f_u, u \in T) = f_t$.
Then $X: \Omega \to V$ is a random variable if and only if
for all $t \in T$, $X_t = \pi_t(X): \Omega \to S$ is a random variable.
\end{lemma}
\begin{proof}
See Exercise \ref{one}.
\end{proof}


\section{Law of a random variable}
The reader will of course have noticed that 
the concept of ``random variable'' has nothing to 
do with randomness. The adjective ``random'' is attached because, 
in addition to the above, we also consider some probability (measure) 
$\Pr$ on $(\Omega, \FF)$ .
As a mathematical definition, the concept of random variable is
purely functional.
So let us do that: let $\Pr$ be a probability on $(\Omega, \FF)$.
The {\sc distribution} or {\sc law}
of the random variable $X$ is a probability $\Pr_X$ on
$(S, \SS)$ which is induced, in the most natural fashion, by $X$:
\[
\Pr_X(B) = \Pr(X^{-1}(B)), \quad B \in \SS.
\]
Note that $\Pr_X$ depends on two functions: the function $\Pr$ and 
the function $X$. 
\begin{drill}
Show that if $(\Omega, \FF, \Pr)$ is a probability space
and $X: (\Omega, \FF) \to (S, \SS)$ a random variable then
$(S, \SS, \Pr_X)$ is a probability space.
Hence if $X$ is a random vector then $X_1$ is a random variable.
\end{drill}
\begin{drill}
With the notation of Drill \ref{drill1}, show that the law of $H \comp X$
as a random variable on the probability space $(\Omega, \FF, \Pr)$ is
the same as the law of $H$ as a random variable on $(S, \SS, \Pr_X)$.
\end{drill}
So the role of a random variable is to transform an abstract probability space
into a concrete one.

In practice, one is often given\footnote{
Actually, one is seldom given anything. Either one derives something from
some basic principles/requirements or one performs an experiment 
whereby measurements are collected and a probability measure is 
stipulated. The latter is the subject of Statistics}
a probability measure $\Qr$ on some 
$(S, \SS)$ and one may (or may not)
want to construct a probability space $(\Omega, \FF, \Pr)$ and
a random variable $X:(\Omega, \FF) \to (S, \SS)$ such that $\Pr_X=\Pr$. 
In the absence of any further requirement we follow Occam's razor
and consider the so-called {\sc canonical construction}: take
$\Omega=S$, $\FF=\SS$, $\Pr=\Qr$ and let $X(\omega) \equiv \omega$.
Then, obviously, $\Pr_X = \Qr$.
If this appears to be silly then this is because it is. But silly things
are often quite useful. On the other hand, if other requirements are
needed to be satisfied, choosing the ``right'' probability space
and the ``right'' random variable is an art.
The freedom in the choice of probability space can be roughly compared
to the freedom of choice of an appropriate co\"ordinate system in $\R^3$
when dealing, e.g.\ with the solution of a certain physical problem expressed
in terms of a partial differential equation. For example, when we study
the motion of fluid in a cylinder we may want to choose cylindrical
co\"ordinates.





\section{Law of a discrete random variable}
\label{law}
A {\sc discrete random variable} $X : (\Omega, \FF) \to (S, \SS)$
is, by definition, one that takes countably many values.
In other words, if $\Pr$ is a probability on $(\Omega, \FF)$ then
$X$ is discrete if and only if there is a countable set $D \in \SS$
such that $\Pr(X \in D)=1$.
We also assume that $D$ and all its subsets are members of $\SS$.
Hence the law $\Pr_X$ of $X$ is a probability on $D$.
We know that a probability on a countable set $D$ can be defined by
defining its values on singletons. These values form the so-called (in baby
Probability talk) {\sc Probability Mass Function} (a terminology which
will become obsolete once adulthood is reached).
Thus, the probability mass function is
\[
p (x) 
= \Pr_X\{x\}
= \Pr(X =x) ,
\quad x \in D.
\]
Clearly, if $B \subset D$ then 
\[
\Pr_X(B) = \Pr_X\bigg(\bigcup_{x \in B} \{x\}\bigg) =
\sum_{x \in B} p(x).
\]
So $p$ is sufficient for computing $\Pr_X$.
\begin{example}
A box contains $n$ socks labelled 1 through $n$. 
Pick two socks at random and let $X$ be the pair of their labels.
Then $X$ is a discrete random variable taking values $(i,j)$ where
$1 \le i, j \le n$, $i \neq j$. The probability mass function is
\[
p(i,j) = 1/n(n-1).
\]
But what is the probability space? First, we should realise that we do not
necessarily need to consider it. Second, we should realise that the article
``the'' is wrong, for there are many choices for a probability space.
Having said that, a reasonable choice for $\Omega$ is the
set of permutations $\omega$ of $\{1, \ldots, n\}$, i.e.\
$\omega=(\omega_1, \ldots, \omega_n)$ where all the $\omega_i$ take
values in $\{1, \ldots, n\}$ and are distinct. The $\sigma$-field $\FF$ 
should be rich enough to contain all singletons, i.e.\ $\FF=2^\Omega$. The
probability  $\Pr$ should be defined as $\Pr(\{\omega\}) = 1/n!$ for all
$\omega$.
To be honest we should check that $p(i,j) = \Pr\{\omega\in \Omega: \omega_1=i,
\omega_2=j\}$.
We have 
\[
\Pr\{\omega\in \Omega: \omega_1=i, \omega_2=j\}
= \frac{1}{n!} ~\sharp \{\omega\in \Omega: \omega_1=i, \omega_2=j\}
= \frac{(n-1)!}{n!} = \frac{1}{n(n-1)},
\]
as required. So $(\Omega, \FF, \Pr)$ is a probability space,
$X$ is a random variable (check this!), $\Pr_X$ is its law,
and $p$ is its probability mass function.
\end{example}

\begin{example}
Consider the experiment of picking $k$ integers at random
(with replacement) from the set $\{1, \ldots, n\}$. Our
$(\Omega, \FF)$ here can be taken to be
\[
\Omega = \{1, \ldots, n\}^k, \quad \FF = 2^\Omega,
\]
and the probability corresponding to the experiment should be
defined as 
\[
\Pr\{(\omega_1, \ldots, \omega_k)\} = \frac{1}{n^k}.
\]
Note here that $\{(\omega_1, \ldots, \omega_k)\}$ is a set containing
a single point, namely the ordered $k$-tuple 
$\omega=(\omega_1, \ldots, \omega_k)$.
For more general sets $B$ we take, as required, $\Pr(B) = \sum_{\omega \in B}
\Pr\{\omega\} = \frac{\sharp B}{n^k}$.
Define a random variable representing the maximum number picked:
\[
X(\omega) = \max(\omega_1, \ldots, \omega_k).
\]
Clearly, $X$ takes values in $\{1, \ldots, n\}$ and trivially,
$X$ is a measurable function from $(\Omega, \FF)$ to $(\{1, \ldots, n\}, 
2^{\{1, \ldots, n\}})$. (The inverse image of a subset of $\{1, \ldots, n\}$
under $X$ is, of course, a subset of $\Omega$, i.e.\ an element of $\FF$.)
Let us compute the probability mass function for $X$.
For $x \in \{1,\ldots,n\}$ we have
\begin{align*}
p(x) &= \Pr(X^{-1}(x)) = \Pr(X = x) 
= \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k)=x\}
\\
&=  \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x
\text{ but } \max(\omega_1, \ldots, \omega_k) \not \le x-1\}
\\
&= \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x\}
- \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x-1\}
\\
&= \frac{1}{n^k} \sharp\{\omega \in \Omega:~ \omega_1\le x , \ldots, \omega_k \le x\}
-\frac{1}{n^k}  \sharp\{\omega \in \Omega:~ \omega_1 \le x-1, \ldots, \omega_k \le x-1\}
\\
&= \frac{x^k-(x-1)^k}{n^k}.
\end{align*}
\end{example}

%If we were to deal ONLY with discrete random variables then there would be
%no need to introduce many of the concepts introduced above. However, one
%soon realises that one has to move...

\section{Tossing coins}
Consider the experiment of flipping fair coins ``independently''. Since
we have not defined independence yet, it is only fair not to refer to it.
A coin takes 2 values, heads or tails with probablity $1/2$ each.\footnote{
But since I assume that every reader has seen the fact before, he or
she will not find the definitions below unreasonable.}
Label heads by 1 and tails by 0. 
Let $\omega_1$ be the first outcome, $\omega_2$ the second, etc.
We stipulate that:
\begin{description}
\item[]
A coin flipped $n$ times
yields a string $(\omega_1,\ldots,\omega_n)$ 
of $n$ 0s or 1s with probability $1/2^n$ each.
\end{description}
For example $(0,1,0)$ should have probability $1/8$, while $(1,1,0,0,1)$
should have probability $1/32$.
In other words, we are {\em trying} to define a probability $\Pr$ by
saying that the $\Pr$ of an event that specifies the first $n$ outcomes
completely should be $1/2^n$, for each $n \in \N$.
Consider our desire to find out when
we will get our first 1 (head), i.e.\ let 
\[
T = \inf\{n \in \N:~ \omega_n=1\}.
\]
This {\em appears} to be a random variable. But on which measurable space?
We cannot pick $\Omega$ to be $\{0,1\}^n$ for some finite $n$, because
we have no bound on $T$.
%But we feel that $T$ should be finite.
%So it seems reasonable to consider 
%\[
%\Omega_0 = \bigcup_{n=1}^\infty \{0,1\}^n.
%\]
%(Remember the indexing convention: $\infty$ is not part of the index set--see
%Glossary.)
%$\Omega_0$ is a countable set because it is countable union of finite sets.
%We can thus define $\Pr$ by definining $\Pr$ on each singleton. We've done
%that:
%\[
%\Pr(\omega_1, \ldots, \omega_n) = 2^{-n}, \quad n \in \N.
%\]
%Since $\sum_{n=1}^\infty 2^{-n} = 1$, $\Pr$ is a probability measure
%on $(\Omega_0, 2^{\Omega_0})$.
%Notice that $\Omega$ is the union of disjoint sets. Indeed
%$\{0,1\}^n \cap \{0,1\}^m = \varnothing$ if $n \neq m$.
%So any function $T(\omega)$ is defined by definining what it equals to
%for all $\omega \in \{0,1\}^n$, and for all $n \in \N$.
%Well, we can define
%\[
%T\(\omega_1, \ldots, \omega_n) =
%\begin{cases}
%\infty 
%\min\{1 \le k \le n:~ \omega_k=1\}, & \text{ if }
%\end{cases}
%\]
We can, however, pick 
\[
\Omega = \{0,1\}^\N,
\]
i.e.\ the set of
all infinite-length sequences $\omega=(\omega_1, \omega_2, \ldots)$,
where $\omega_n =0 $ or $1$ for all $n$.
This is our {\sc coin-flip space}.
\begin{drill}
Show that the coin-flip space is uncountable.
\end{drill}
To put what we said in some notation, let 
\[
R(i_1, \ldots, i_n) := \{ \omega \in \Omega:~
\omega_1 = i_1, \ldots, \omega_n=i_n\}.
\]
To this set we should assign probability $2^{-n}$:
\begin{equation}
\label{int}
\operatorname{\bf prob} (R(i_1, \ldots, i_n) ) = 2^{-n}.
\end{equation}
We use the symbol $\prob$ rather than $\Pr$ because we have not yet
verified that this is a probability.
%Try to understand $R(i_1, \ldots, i_n)$ means. It is the set (event)
%that the first coin toss give $i_1$, the second $i_2$, and so on, until
%the $n$-th toss which gives $i_n$. 
%For example, $R(0,1,1)$ means 
%that the first three tosses are ``tails, heads, heads''.
Let $\RR$ be the class of such sets (together with the empty set):
\[
\RR := \{\varnothing\} \cup \{R(i_1, \ldots, i_n):~
i_1, \ldots, i_n \in \{0,1\},~ n \in \N \}.
\]
Formula \eqref{int}  defines the  function
\[
\prob : \RR \to \R.
\]
It is by no means true that 
$\RR$ contains all subsets of $\Omega$ (far from that):
\begin{drill}
Show that 
\[
R(1) \cup
R(0,1) \cup
R(0,0,1) \cup \cdots \not \in \RR.
\]
Show that this set is the set $\{\omega\in \Omega: ~ T(\omega) < \infty\}$.
Show that the intersection of two elements of $\RR$ is in $\RR$, but
not the union.
\end{drill}
%Indeed, suppose $n \le m$,
%and consider $C_{i_1, \ldots, i_n} \cap C_{j_1, \ldots, j_m}$. This is
%$\varnothing$ unless $(i_1, \ldots, i_n) = (j_1, \ldots, j_n)$, in which case
%it is equal to $C_{i_1, \ldots, i_n, j_{n+1}, \ldots, j_m}$.
\begin{drill}
\label{drill12}
Second, the complement of any set in $\RR$ is written as a finite disjoint
union of sets in $\RR$.
(For example $R(0,1)^c = \{\omega: \omega_1=1\} \cup \{\omega: \omega_2=0\}
= R(1) \cup \{\omega: \omega_2=0\} = R(1) \cup R(1,0) \cup R(0,0)$.)
\end{drill}
What kind of properties does $\prob$ have? We would like $\prob$ to be, at least,
additive, i.e.\ to satisfy 
%the probability formula\footnote{
%``Total Probability Formula'' is another name for ``Finite Additivity''.}
$\prob(G_1 \cup \cdots \cup G_k)  = \prob(G_1)+\cdots+\prob(G_k)$
if $G_1, \ldots G_k$ are mutually disjoint elements of $\RR$.
There is an issue here: as we saw, the union of elements
of $\RR$ may not be in $\RR$.  So this last additivity property is
completely meaningless for $\prob$. We remedy this by enlarging $\RR$:
\[
\CC := \{G_1\cup \cdots \cup G_k:~ G_1, \ldots, G_k \text{ are mutually
disjoint elements of } \RR, ~ k \in \N\},
\]
and by extending $\prob$ to $\CC$ in the most natural way:
\[
\Pr_0(G_1\cup \cdots \cup G_k) := \sum_{j=1}^k \prob(G_j).
\]
\begin{lemma}
\label{exta}
(i) $\CC$ is a field.
(ii) $\Pr_0$ is well-defined and additive over $\CC$. 
\end{lemma}
\begin{proof}
(i)  Let $A, B \in \CC$. Then $A = \cup_{i=1}^n G_i$, 
$B = \cup_{j=1}^m H_j$,
where the $G_i$ are mutually disjoint (m.d.) elements of $\CC$,
and so are the $H_j$.
We have 
\[
A B = \cup_{i,j} G_i H_j
\]
and, clearly, the $G_iH_j$ are m.d.\ elements of $\RR$; so $AB \in \CC$.
Also, 
\[
A^c = \cap_j G_i^c,
\]
each $G_i^c$ is an element of $\CC$ (Drill \ref{drill12}), and because
we just proved that $\CC$ is closed under intersections, we have 
$A^c \in \CC$. So $\CC$ is a field.
\\
(ii)
To show that $\Pr_0$ is well-defined means to show that if we can
write the same $A \in \CC$ in two different ways, say
$A= \cup_{i=1}^n G_i = \cup_{j=1}^m H_j$ where both the $G_i$ and the
$H_j$ are m.d.\ elements of $\RR$, we have
$\sum_i \prob(G_i) = \sum_j \prob(H_j)$.
But notice that $G_i = \cup_j G_i H_j$ and so
$\prob(G_i) = \sum_j \prob(G_i H_j)$,
and, similarly, 
$\prob(H_j) = \sum_i \prob(G_i H_j)$. This proves the claim that $\Pr_0$
is well-defined on $\CC$. Now, to show additivity, suppose that
$A_1, \ldots, A_n$ are m.d.\ elements of $\CC$. We must show that
$\Pr_0(\cup_i) = \sum_i \Pr_0(A_i)$.
%Indeed, fix $i_1, \ldots, i_n \in \{0,1\}$  and notice that
%$\big\{C_{i_1, \ldots, i_n; j_1, \ldots, j_m}, ~ j_1, \ldots, j_m \in \{0,1\}\big\}$
%are mutually disjoint with 
%\[
%C_{i_1, \ldots, i_n} = \bigcup_{j_1, \ldots, j_m}C_{i_1, \ldots, i_n; j_1, \ldots, j_m}.
%\]
%But $\prob(C_{i_1, \ldots, i_n; j_1, \ldots, j_m}) = 2^{-n-m}$
%and $\sum_{j_1, \ldots, j_m}  2^{-n-m} = 2^m  2^{-n-m} = 2^{-n}
%= \Pr(C_{i_1, \ldots, i_n})$.
Now, to show additivity, suppose that
$A_1, \ldots, A_n$ are m.d.\ elements of $\CC$. We must show that
$\Pr_0(\cup_i A_i) = \sum_i \Pr_0(A_i)$.
But each $A_i$ is itself a finite union of m.d.\ elements of $\RR$,
say $A_i = \cup_j H_{ij}$, and, by the definition of $\Pr_0$, we have
$\Pr_0(A_i) = \sum_j \prob(H_{ij})$.
So 
$\sum_i \Pr_0(A_i) = \sum_i \sum_j \prob(H_{ij})$.
On the other hand, $\cup_i A_i = \cup_{i,j} H_{ij}$ and the
$H_{ij}$ are m.d.\ elements of $\RR$. Hence, by the definition
of $\Pr_0$ again, we have $\Pr_0(\cup_i A_i) =  \sum_i \sum_j \prob(H_{ij})$.
\end{proof}

To put in words, what we have shown so far is that,
starting merely from the intuitive definition \eqref{int},
we can compute probabilities of sets that can be expressed 
using finitely many outcomes, i.e.\ that involve $\omega_i$
up to some finite index.
Mathematically, Lemma \ref{exta} has enabled us to define
a function
\[
\Pr_0: \CC \to \R
\]
in such a way that
\[
\Pr_0(G) = \prob(G), \quad \text { if }
G \in \RR
\]
and
\[
\Pr_0(G_1 \cup \cdots \cup G_k)  = \Pr_0(G_1)+\cdots+\Pr_0(G_k),
\quad \text{if $G_1, \ldots G_k$ are mutually disjoint elements of $\RR$}
\]
(a property which, as remarked, is meaningless for $\prob$).


But there are many sets, whose probability we would like to know,
but which do not belong to $\CC$. 
\begin{example}
The following (useful) sets do not belong to $\CC$:
\\
(i)
$A_1:= \displaystyle \{\omega:~ T(\omega) < \infty\}$
(i.e.\ the event that a head will occur at some point). Indeed, this
equals $\cup_{n=1}^\infty \{\omega\in \Omega:~\omega_n=1\}$ and does not 
belong to $\CC$ because it involves infinitely many coordinates.
\\
(ii)
$A_2:=\displaystyle \{\omega: \omega_n = 1 \text{ for infinitely many } n\}$.
This, obviously, does not belong to $\CC$. Formally the set equals
\[
\displaystyle \{\omega:~ \forall n ~ \exists m \ge n ~ \omega_m=1\}
= \bigcap_n \bigcup_{m \ge n} 
\{\omega:~ \omega_m=1\}
= \bigcap_n \bigcup_{m \ge n} \bigcup_{i_1,\ldots,i_m \in \{0,1\}}
R(i_1, \ldots, i_{m-1},1).
\]
And so it is explicitly seen that we need infinitely many sets
from $\RR$ to construct $A_2$.
\\
Although we feel that both $A_1$ and $A_2$ should be assigned probability
$1$, we {\em cannot} write $\Pr_0(A_1)=1$, neither $\Pr_0(A_2)=1$,
simply because neither of the two sets belongs to the domain of the function
$\Pr_0$.
\end{example}
So our desire to deal with these sets forces us to carry the story further.
\begin{drill}
Read Exercise \ref{count} NOW. 
\end{drill}
Let us then define a class of sets which includes the sets
of the last example:
\begin{equation}
\label{FF1}
\FF = \text{$\sigma$-field generated by } \CC.
\end{equation}
It is not difficult to see that, also,
\begin{equation}
\label{FF2}
\FF = \text{$\sigma$-field generated by } \RR.
\end{equation}
%One could try to define an the probability of sets in $\FF$ by taking
%limits.
%So, why don't we consider the class of sets which are limits
%of sets from $\CC$? 
%Let's call this class $\CC_2$. Unfortunately,
%$\CC_2$ is not equal to $\FF$, neither is it  a $\sigma$-field.
%If $A \in \CC_2$, then $A = \lim A_n$ with $A_n \in \CC$. So
%we can define $\Pr_2(A) = \lim \Pr_0(A_n)$. It turns out that
%this function is well-defined and countably additive over $\CC_2$.
%Can we go further? Sure. Let us define $\CC_3$ to be the class of sets
%which are limits of sets from $\CC_2$. Unfortunately,
%$\CC_3$ is not equal to $\FF$, neither is it  a $\sigma$-field.
%If $A \in \CC_3$, then $A = \lim A_n$ with $A_n \in \CC_2$. So
%we can define $\Pr_3(A) = \lim \Pr_2(A_n)$.  It turns out that
%this function is well-defined and countably additive over $\CC_3$.
%Well, if we continue like this we may, at some point, reach $\FF$.
%Unfortunately, this point is never reached 
%%\footnote{Archimedes did that ca.\ 2000 years ago in another area,
%%in Geometry, to compute the area of a circle.} 
%%However this procedure is not easy (it requires a so-called transfinite
%%induction) and is beyond the scope of these lectures. 
The following theorem completes the story: 
\begin{theorem}
\label{ouf}
Let $\Omega = \{0,1\}^\N$.  Let $\RR$ be the class of sets of
the form $R(i_1, \ldots,i_n)
:=\{ \omega \in \Omega:~ \omega_1 = i_1, \ldots, \omega_n=i_n\}$.
Define $\prob(R(i_1, \ldots,i_n))=2^{-n}$. 
Let $\FF$ be the $\sigma$-field generated by $\RR$. 
Then there exists a unique probability $\Pr$ on $(\Omega, \FF)$
such that $\Pr(G) = \prob(G)$ for every $G \in \RR$.
\end{theorem}
\begin{proof} [sketch]
See Appendix B.
We can first show that $\Pr_0$ is countably additive on $\CC$.
We then define $\Pr_1$ on $D(\CC)$
and $\Pr_2$ on $D^2(\CC)$.
We show that if $A \in \FF$ there exist $G, H \in D^2(\CC)$ such that
$G \subset A \subset H$ and $\Pr_2(G) = Pr_2(H)$.
We define $\Pr(A)$ to be this common value and show that $\Pr$
is countably additive on $\sigma(\CC)$.
\end{proof}

For details of THIS proof, see, e.g.\ \cite{fg}.
For a classical approach, see, e.g.\ \cite{wil}.



This theorem tells us that $(\{0,1\}^\N, \FF, \Pr)$ is a probability
space, so we can use all the good things we know about them.
For example, $T(\omega) = \inf\{n \in \N:~ \omega_n=1\}$ defines
a measurable function $T: (\Omega, \FF) \to (\R, \BB)$ and,
since $\{T \le n\}$ are increasing sets with union equal to the 
set $\{T < \infty\}$, we have $\Pr(T< \infty) = \lim_{n\to\infty}
\Pr(T \le n)$. But $\{T > n\} = R(0,\ldots,0)$ ($n$ 0's inside the parenthesis)
and  so $\Pr(T>n) = \prob(R(0,\ldots,0)) = 2^{-n}$. Thus $\Pr(T< \infty)
= \lim_n (1-2^{-n})=1$.




\section{A random variable with density}
We will now construct our first non-discrete random variable.
Consider the probability space $(\Omega=\{0,1\}^\N, \FF, \Pr)$
of the coin tossing experiment. Define
\begin{equation}
\label{U}
U(\omega) = 
\frac{\omega_1}{2} +
\frac{\omega_2}{2^2} +
\frac{\omega_3}{2^3} + \cdots = \sum_{k=1}^\infty \frac{\omega_k}{2^k}.
\end{equation}
Let $U_n(\omega) := \sum_{k=1}^n \frac{\omega_k}{2^k}$: these are simple
random variables. Since 
$U(\omega) = \lim_{n \to \infty} U_n(\omega)$, we have, by Lemma \ref{balg},
that $U: (\Omega, \FF) \to (\R, \BB)$ is measurable (i.e.\ a random
variable). It is ONE random variable because it takes values in $\R$.
More specifically, observe that
\[
0 \le U(\omega) \le \sum_{k=1}^\infty \frac{1}{2^k} = 1.
\]
So $U(\Omega) \subset [0, 1]$.
Our first observation is
\begin{lemma} 
\label{dyad}
For any integer $0 \le a < 2^n$ and any $n \in \N$, we have
\[
U > \frac{a}{2^n} \iff U_n > \frac{a}{2^n}
\text{ or } U = \frac{a+1}{2^n}.
\]
\end{lemma}
\begin{proof}
One direction is obvious since $U \ge U_n$. 
To show the other direction it suffices to show the implication
$U > a/2^n$, $U_n \le a/2^n \Rightarrow U=(a+1)/2^n$.
So, assume that $U > a/2^n$ and $U_n \le a/2^n$.
Since $2^n U$ is an integer the first inequality actually
says $U \ge (a+1)/2^n$. On the other hand,
we always have $U-U_n \le \sum_{k \ge n+1} 2^{-k} = 1/2^n$. 
So $U = U_n + (U-U_n) \le (a/2^n) + (1/2^n) = (a+1)/2^n$.
\end{proof}

Next, we compute the following probabilities:
\begin{lemma}
For any integer $0 \le a < 2^n$ and any $n \in \N$, we have
\[
\Pr(U \le a/2^n) = a/2^n.
\]
\end{lemma}
\begin{proof}
First observe that $\Pr(U=b/2^n)=0$ for any integer $b \le 2^n$.
To see this notice that if $b < 2^n$ and $U(\omega) = b/^n$ then, necessarily,
$\omega_i=0$ for all $i \ge n+1$. But the latter event is
the limit of the events
\[
\{\omega \in \Omega:~ \omega_{n+1}= \cdots = \omega_\ell=0\},
\quad \ell > n,
\]
as $\ell \to \infty$. The probability of these events is $2^{-(\ell-n)}$ which
tends to $0$ as $\ell \to \infty$. Hence $\Pr(U=b/2^n)=0$.
If $b = 2^n$ then $b/2^n=1$ and, for the same reason, $\Pr(U=1)=0$.
Using this and Lemma \ref{dyad} we find that
\[
\Pr(U \le a/2^n) = \Pr(U_n \le a/2^n).
\]
We prove that $\Pr(U_n \le a/2^n) = a/2^n$, for all $a < 2^n$, 
by induction on $n$.
To start, let $n=1$. We take $a < 2$, i.e.\ $a=0$ or $1$. There
is nothing new to prove when $a=0$, so let $a=1$ and observe that
$\Pr(U_1 \le 1/2) = \Pr(\omega_1=1)=1/2$, as required.
Now assume the statement to be true up to index $n-1$.
Write
\begin{align*}
U_n(\omega) &= \frac{\omega_1}{2} + \frac{1}{2} Y_{n-1}(\omega),
\\
Y_{n-1}(\omega) &= \frac{\omega_2}{2} + \frac{\omega_3}{2^2} + \cdots
+ \frac{\omega_{n-1}}{2^n}.
\end{align*}
Therefore
\begin{align*}
\Pr(U_n \le a/2^n) 
&= \Pr(\omega_1=0,~ Y_{n-1} \le a/2^{n-1})
+
\Pr(\omega_1=1,~ Y_{n-1} \le a/2^{n-1}-1)
\\
&= \tfrac{1}{2} \Pr(Y_{n-1} \le a/2^{n-1}) +
\tfrac{1}{2} \Pr(Y_{n-1} \le a/2^{n-1}-1)
\end{align*}
By the induction hypothesis, $\Pr(Y_{n-1} \le c/2^{n-1}) = c/2^{n-1}$
for all $c < 2^{n-1}$ (why?).
If $a \le 2^{n-1}$, the second term in the display is $0$ and
the first equals $(1/2) \times (a/2^{n-1}) = a/2^n$, as needed.
If $2^{n-1} < a < 2^n$, the first term equals $1/2$ and the second
equals $(1/2) \times (a/2^{n-1}-1)$; the sum gives again $a/2^n$.
\end{proof}

Finally, we have
\begin{lemma}
\label{udf}
For any real number $x \in [0,1]$,
\[
\Pr(U < x)
=
\Pr(U \le x) = x.
\]
\end{lemma}
\begin{proof}
%There is nothing to prove actually when $x$ is of the form $a/2^n$
%where $a$ is integer: it was proved earlier. So suppose $x$ is not
%of this form. 
Let $[y]$ denote the largest integer not exceeding
the real number $y$. Define, recursively,
\begin{gather*}
z_1=x, \quad \xi_1=[2z],\\
z_{n+1} = z_n - \frac{\xi_n}{2^n}, \quad
\xi_{n+1} = [ 2^{n+1} z_{n+1}].
\end{gather*}
We have $2^n z_{n+1} = 2^n z_n - \xi_n =
2^n z_n - [2^n z_n] \le 1$, so $z_{n+1} \le 1/2^n$ for all $n$.
Therefore the sequence $z_n$ converges to $0$ and the numbers $\xi_n$
are either $0$ or $1$.
We also have
\[
x_n:=
\frac{\xi_1}{2} +
\frac{\xi_2}{2^2} +
\cdots +
\frac{\xi_n}{2^n} 
=(z_1-z_2)+(z_2-z_3) + \cdots + (z_n-z_{n_+1}) = x-z_{n+1},
\]
and so $x_n \to x$, as $n \to \infty$. Also, $x_n$ is of the
form $a/2^n$, where $a$ is an integer.
So $\Pr(U \le x_n) = x_n$. Since $x_n$ actually increases to $x$,
we have $\cup_{n=1}^\infty \{U \le x_n\} = \{U < x\}$, and
so taking limits we get $\Pr(U < x) = x$, for all $x \le 1$.
This also implies $\Pr(U \le x+1/n) = x+1/n$ for all $n$ sufficiently
large. But $\cap_n \{U \le x+1/n\} = \{ U \le x\}$ and so, taking limits,
$\Pr(U \le x) = x$.
\end{proof}
\begin{corollary}
\[
\Pr(U=x) =0, \text{ for all } x \in [0, 1].
\]
\end{corollary}
So the random variable $U$ takes no specific value with positive probability.
Yet, $U$ exists (we constructed it). 
This is curious, but we can (must)
get used to it. 
Any real random variable with this property
is called {\sc continuous random variable}. 
In books, $U$ has a name: it is called {\sc 
uniform random variable on the interval $[0,1]$}.
\begin{corollary}
Let $\Q$ be the set of all rational numbers in $[0,1]$.
Then
\[
\Pr(U \in \Q) = 0.
\]
\end{corollary}
\begin{proof}
The set $\Q$ is enumerable (has countably many points). Hence
\[
\Pr(U \in \Q) = \Pr( \cup_{q \in \Q} \{ U =q\})
= \sum_{q \in \Q} \Pr(U=q) = 0.
\]
\end{proof}





\section{Probability, revisited}
Recall, once more, that a probability $\Pr$ defined on a $\sigma$-field
$\FF$ of subsets of a set $\Omega$ is a function $\Pr: \FF \to \R$
such that (i) $\Pr(\Omega)=1$, and (ii) $\Pr(\cup_n A_n) = \sum_n \Pr(A_n)$,
if the $A_n$ are mutually disjoint elements of $\FF$.

If $\Omega$ is a countable set then we know that it suffices to define $\Pr$
on singletons, i.e.\ knowledge of $\Pr\{\omega\}$ for all $\omega \in \Omega$
implies knowledge of $\Pr(A)$ for all $A \in \FF$. Indeed,
\[
\Pr(A) = \sum_{\omega \in A} \Pr\{\omega\}.
\]
We saw, in the previous section, the necessity to define $\Pr$ on sets
which are not countable. We can't we define $\Pr\{\omega\}$ for
all $\omega$ in this case? The argument is simple. Suppose we did do so.
Let $\Omega_+ := \{\omega \in \Omega:~ \Pr\{\omega\} > 0\}$, and,
for each $n \in \N$,
$\Omega_n = \{\omega \in \Omega:~ \Pr\{\omega\} \ge 1/n\}$.
This is a finite set with at most $n$ points.
Observe that $\cup_n \Omega_n = \Omega_+$. But this tells us that 
$\Omega_+$ is a countable set.
So this poses a ``philosophical'' problem: If we want to define
a random variable that is uniformly distributed on the uncountable set
$[0,1]$ by defining probabilities of singletons,
then we'd have to pick a countable subset of $[0,1]$ and define probabilities
of points there. But which one to pick? We cannot give preference to
any particular countable subset. 

The way out is not to define probabilities on single points, but, rather,
on sets, as we did in the previous section. We then do not give preference
to any particular countable subset, but we lose something ``intuitive'':
we assign zero probability to every individual point.
This is what needs to be done, both for physical and mathematical reasons,
and this is what shall be done hereafter: We will be defining
probabilities on sets.

But another burden appears now: whereas, in the countable case,
 we were free to define probabilities of points at will (as long as
they summed up to something finite), in the general case we cannot define
probabilities of sets at will: we must respect the countable additivity
property (ii) above. 
Since there are far too many sets, we will try to see how to define
$\Pr$ on a class of selected few of them. So read the next section.




\section{Distribution functions}
Consider a real random variable $X: (\Omega, \FF) \to (\R, \BB)$
and put a probability $\Pr$ on $\Omega$. Recall the definition of
the law $\Pr_X$ of $X$:
\[
\Pr_X(B) = \Pr(X \in B), \quad B \in \BB.
\]
Up until the middle of the 19th century, a function was an object that
was given by a formula. Nowadays, of course, a function is more abstract: we
certainly need no formulae to comprehend what a function is. However, let
us take the old-fashioned point of view. Clearly, $\Pr_X$ is a function
whose arguments are sets (elements of $\BB$). These are a lot of arguments!
And, as we know, we don't need all of them because, for example,
if $B = B_1 \cup B_2$ and $B_1 \cap B_2 = \varnothing$,
then $\Pr_X(B) = \Pr_X(B_1) + \Pr_X(B_2)$. To put it pedantically, 
we can't define $\Pr_X(B)$ anyway we like. We must make sure
that it is consistent (countable additivity must hold).
So the question is: can we throw away some (many) of its arguments
without losing information? The answer is yes. It suffices to
know $\Pr_X(B)$ only for $B$ of  specific form. There are many choices.
One choice is to take 
\[
B=(-\infty , x],
\]
where $x$ ranges from $-\infty$ to $\infty$ and consider only
\begin{equation}
\label{DF}
F(x) := \Pr_X(-\infty, x], \quad x \in \R.
\end{equation}
So I claim that:
\begin{lemma}
Knowledge of $\Pr_X$ on this class of sets only (semi-infinite
intervals) implies knowledge of $\Pr_X$ on the whole of $\BB$. 
\end{lemma}
This is a big claim. But we shall prove it by construction. 
First, let us see the properties of $F$.
\begin{lemma}
\label{kkk}
(i) $x_1 < x_2 \Rightarrow F(x_1) \le F(x_2)$,
(ii) $\lim_{x\to-\infty} F(x) =0$,
(iii) $\lim_{x\to+\infty} F(x) =1$,
(iv) $\lim_{n \to \infty} F(x+1/n) = F(x)$. 
\end{lemma}
\begin{proof}
(i) If $x_1 < x_2$ we have $(-\infty, x_1] \subset (-\infty, x_2]$
and so $\Pr_X (-\infty, x_1] \le \Pr_X (-\infty, x_2]$.
(ii)\&(iii) Since $F$ is monotonic with values between $0$ and $1$
it has a limit both as $x$ tends to $-\infty$ and $+\infty$.
We have $\cap_{n \in\Z} (-\infty, n] = \varnothing$, so $\Pr_X(-\infty, n]
\to 0$ as $n \to -\infty$. Similarly, $\cup_{n \in \Z} (-\infty,n] = \R$,
so $\Pr_X(-\infty, n] \to \Pr_X(\R)=1$ as $n \to +\infty$.
(iv) $\cap_n(-\infty, x+1/n]= (-\infty, x]$.
\end{proof}

\noindent{\bf Remarks:}\\
1. Notice that $F(x-1/n)$ does NOT necessarily converge to $F(x)$
becase $\cup_n(-\infty, x-1/n] = (-\infty, x)$, and so $\lim_{n\to\infty}
F(x-1/n) = \Pr_X(-\infty, x)$ which will be different from $\Pr_X(-\infty, x]$
if $\Pr_X\{x\} > 0$.
\\
2. There is no good reason that we chose this class of sets, other than
people have been using it by convention. For instance, we could have
chosen open semi-infinite interval $(-\infty, x)$, in which case (iv) of
Lemma \ref{kkk} would be replaced by $\lim_{n \to \infty} F(x-1/n) = F(x)$.


\noindent{\bf Proof of Lemma \ref{kkk}}
Consider the coin-flip $\Omega=\{0,1\}^\N$.
$U(\omega) = \sum_{n=1}^\infty
\frac{\omega_n}{2^n}$. 
Then $U$ is a random variable and
$\Pr$ is, indeed, a probability on $(\Omega, \FF)$,
where $\FF$ is defined through \eqref{FF1} or \eqref{FF2}.
We also showed that $\Pr(U \le u) = u$ for all $u \in [0,1]$.
Suppose now that $F$, as in \eqref{DF}, is given.
Define
\begin{equation}
\label{FI}
F^{-1} (u) := \sup\{x \in \R: ~ F(x) \le u \}.
\end{equation}
By Lemma \ref{balg}, $F^{-1}(U)$ is a random variable. In other words,
$F^{-1} \comp U : (\Omega, \FF) \to (\RR, \BB)$ is measurable.
Suppose that, for some $u, t$, we have $F^{-1}(u) \le t$.
This means that $t$ is an upper bound of the set 
$\{x \in \R: ~ F(x) \le u \}$.
Hence for all $x \in \R$, if $F(x) \le u$ then $ x \le t$.
Equivalently, for all $x \in \R$, if $ x > t$ then $F(x) > u$.
Equivalently, for all $\epsilon > 0$, $F(t+\epsilon) > u$.
Equivalently, for all $n \in \N$, $F(t+1/n) > u$.
Thus,
\[
\{\omega \in \Omega:~ F^{-1}(U(\omega)) \le t\} = 
\{\omega \in \Omega:~ \forall n \in \N ~ F(t+1/n) > U(\omega)\}.
\]
Hence the probabilities of the two sets (notice they both belong
to $\FF$) are the same:
\[
\Pr(F^{-1}(U) \le t) = \Pr (\forall n \in \N ~ F(t+1/n) > U).
\]
By the fact that $\Pr(A_n) \to \Pr(A)$ if $A_n$ is a decreasing sequence
of sets with intersection $A$, we have
\[
\Pr (\forall n \in \N ~ F(t+1/n) > U)
= \lim_{n \to \infty} \Pr(U < F(t+1/n)).
\]
By Lemma \ref{udf}, and the right-continuity of $F$ (Lemma \ref{kkk}),
\[
\lim_{n \to \infty} \Pr(F(t+1/n) > U) = \lim_{n \to \infty} F(t+1/n)
= F(t).
\]
Thus the random variable $F^{-1} \comp U$ has the same law as $X$.
Hence, for all $B \in \BB$, 
\[
\Pr_X(B) = \Pr(F^{-1}(U) \in B)
= \Pr\{\omega\in \{0,1\}^\N:~ F^{-1}(U(\omega)) \in B\}
\]
So, knowledge of $\Pr_X$ on sets of the form $(-\infty, x]$ implies
knowledge of $\Pr_X(B)$ for all $B \in \BB$ by the explicit formula
of the last display.
$\Box$

\begin{definition}
A function $F : \R \to \R$ is called distribution function iff
(i) $x_1 < x_2 \Rightarrow F(x_1) \le F(x_2)$,
(ii) $\lim_{x\to-\infty} F(x) =0$,
(iii) $\lim_{x\to+\infty} F(x) =1$,
(iv) $\lim_{n \to \infty} F(x+1/n) = F(x)$.
\end{definition}

\begin{corollary}
If $F$ is a distribution function then there exists a probability $\Qr$
on $(\R, \BB)$ such that $\Qr(-\infty, x] = F(x)$ for all $x \in \R$.
\end{corollary}
\begin{proof}
Let $\Omega = \{0,1\}^\N$.
Let $\FF$ be as in \eqref{FF1} or \eqref{FF2}.
Let $\Pr$ be the probability on $(\Omega, \FF)$ as in Theorem \ref{ouf}.
Let $U : (\Omega, \FF) \to (\RR, \BB)$ be the random variable
defined by $U(\omega) = \sum_{n=1}^\infty 2^{-n} \omega_n$.
Let $F^{-1}$ be defined by \eqref{FI}. 
Let $X = F^{-1} \comp U$. Then $\Qr = \Pr_X$.
\end{proof}

\begin{lemma}
Let $X$ be one real random variable with law $P_X$ and distribution function
$F(x) = \Pr_X(-\infty, x]$, $x \in \R$.
Then (i) $\Pr(X \in (a, b]) = F(b)-F(a)$, (ii) $\Pr(X \in (a,b)) = F(b-)-F(a)$,
(iii) $\Pr(X \in [a, b]) = F(b) - F(a-)$,
(iv) $\Pr(X=a) = F(a)-F(a-)$.
\end{lemma}
\begin{proof}
(i) 
\[
(a, b] = (-\infty , b] - (-\infty, a].
\]
(ii)
\[
(a, b) = \cup_{n \in \N} (a, b-1/n]
\]
(iii)
\[
[a, b] = \cap_{n \in \N} (a+1/n, b].
\]
(iv)
\[
\{a\} = [a, a].
\]
\end{proof}


\section{Types of distribution functions}
In this section we discuss the various kinds of distribution functions
on $\R$.
\subsection{Discrete distribution functions}
A discrete distribution function is the distribution function of
a discrete random variable $X$ with values in some countable subset $S$ of $\R$.
Assume that $p(s) = \Pr(X = s) > 0$ for all $s \in S$.
Such a distribution function
satisfies $F(s)-F(s-) > 0$ for all $s \in S$.
Indeed, $F(s) - F(s-) = \Pr(X=s)$.
Also, if $(a,b)$ is an open interval containing no points 
of $S$, then $F$ is constant on $(a,b)$. Indeed,
if $a < x < b$ then $F(x)-F(a) = \Pr(a < X \le x) = \sum_{s \in S, a < s \le x}
\Pr(X=s) =0$. 
\begin{example}
Let $X$ be a random variable such that $\Pr(X=n) = 2^{-n}$, $n \in \N$.
Then its distribution function looks like
\begin{center}
FIGURE
\end{center}
\end{example}
\begin{example}
Let $X$ be a random variable such that for every rational number
of the form $m/n$ where $m, n$ are integers with no common factors,
we have $\Pr(X=m/n) = c 2^{-(m+n)}$ where $c$ is chosen
so that $\Pr(X \in \Q) =1$.
Its distribution function is discrete because $\Q$ is countable.
Unfortunately, I can't draw it. (There are no intervals $(a, b)$ containing
no rational points.)
\end{example}

\subsection{Continuous distribution functions}
A distribution function $F$ is continuous if it is a continuous function,
i.e.\ if $F(x) - F(x-) =0$ for all $x \in \R$.
\begin{example}
Consider the random variable $U$ with $\Pr(U \le u) = u$ for all $u \in [0,1]$.
Such a random variable exists (we constructed it). Its distribution function
looks like
\begin{center}
FIGURE
\end{center}
\end{example}
Excepting the points $0, 1$ we have that it is also differentiable
with derivative $f(u) = 1$ if $0 < u < 1$ and $0$ otherwise..
If we arbitrarily define $f(0) = f(1) =0$, we also have 
$\int_{-\infty}^u f(t) dt = F(u)$ for all $u \in \R$.
We like such distribution functions:
\subsubsection{Absolutely continuous distribution functions}
A distribution function $F$ is called {\sc absolutely continuous}
if there exists a function $f$ (called {\sc density} of $F$) such that
\[
F(x) = \int_{-\infty}^x f(t) dt, \quad x \in \R.
\]
But not all continuous distribution functions are absolutely continuous:
\subsubsection{Singularly continuous distribution functions}
A distribution function $F$ is called {\sc singularly continuous}
if it is continuous but not absolutely continuous.
We need to show that there are such functions.
\begin{example}
\end{example}

\subsection{General distribution functions}
Suppose that $F, G$ are distribution functions. Then, for any
$\lambda \in (0,1)$, the function $\lambda F + (1-\lambda G)$ is
a distribution function. (Probabilistically,  if $X, Y$ are random variables
with distribution functions $F, G$, respectively, then we can define
a new random variable $Z$ which equals $X$ with probability $\lambda$
or $Y$ with probability $1-\lambda$.)
So, if $F$ is discrete and $G$ continuous then $\lambda F + (1-\lambda G)$
is neither discrete nor continuous: it is mixed.
The question is: Can we exhaust all distribution functions by taking
mixtures of the three types mentioned above?
The answer is yes:
\begin{theorem}
Let $F$ be a distribution function on $\R$. Then $F$ can be {\em uniquely}
written as 
\[
F= \lambda_d F_d + \lambda_{ac} F_{ac} + \lambda_{sc} F_{sc}
\]
where $F_d, F_{ac}, F_{sc}$ are discrete, absolutely continuous, singularly
continous distribution functions, respectively, and where the coefficients
are nonnegative such that $\lambda_d + \lambda_{ac} + \lambda_{sc}=1$.
\end{theorem}
The last two terms of this decomposition are known as the
continuous part of $F$. The first two terms are known as the
singular part of $F$. We will not prove this theorem, but refer, e.g.\
to \cite{hs}.

\subsection{Differentiation: a word of caution}
The subject of densities involves the concept of a derivative of
functions that are not necessarily everywhere differentiable. 
Mimicking the definition of a density, we will say that a function $G$
has density $g$ if $G'(x) = g(x)$ for almost all $x$. The latter statement
means that it holds true that $G'(x) = g(x)$ for all $x$ in some set $A$
whose complement is small in the sense that for all $\epsilon > 0$
there exist intervals $I_n$, $n \in \N$ with lengths $\lambda_n$, $n \in \N$,
such that $\sum_n \lambda_n < \epsilon$ and $A^c \subset \cup_n I_n$.
We take this latter statement as a definition:
\begin{definition}
\label{mz}
(i) We say that a set $B \subset \R$ has {\sc measure zero} if
all $\epsilon > 0$
there exist intervals $I_n$, $n \in \N$ with lengths $\lambda_n$, $n \in \N$,
such that $\sum_n \lambda_n < \epsilon$ and $B \subset \cup_n I_n$.
\\
(ii) A function $G : \R \to \R$ is said to be {\sc almost everywhere
differentiable} if $G'(x)$ exists for all $x \in A$ where $A^c$ has
measure zero.
\end{definition}
We can verify the following:
\begin{itemize}
\item
Any countable set has measure zero.
\item
A set $B \subset [0,1]$ has measure zero if and only if a
uniform random variable $U$ in $[0,1]$ satisfies $\Pr(U \in B)=0$.
\item
An absolutely continuous distribution function is almost
everywhere differentiable.
\end{itemize}
What kind of functions $G$ are almost everywhere differentiable with a 
derivative $g$ that can be used to recover the function? That is, for what
kind of functions $G$ can we apply the Fundamental Theorem of Calculus (FTC),
i.e.\ the statement that $G(b)-G(a) = \int_a^b g(x) dx$?
Calculus tells us that if $G$ is differentiable everywhere then this is true.
However, we saw, by means of distribution functions, not only
that the FTC holds more generally but it is desirable to understand
it more generally because random variables with not everywhere differentiable
distribution functions abound in theory and in practice.
Here is a definition.
\begin{definition}
A function $G: \R \to \R$ is called {\sc absolutely continuous}
if for all $\epsilon > 0$ there exists a $\delta>0$
such that for any finite collection of disjoint intervals $[a_k, b_k]$
we have $\sum_k|G(b_k)-G(a_k)| < \epsilon$
provided that  the sum of the lengths of the intervals is less than $\delta$.
\end{definition}
\begin{drill}
A differentiable function is absolutely continuous.
An absolutely continuous function is continuous.
\end{drill}
\begin{theorem}
Any absolutely continuous function $G$ is differentiable almost everywhere
and if $g$ is its derivative then the FTC holds.
\end{theorem}
For a proof see \cite{hs}.
Alternatively, one can use Probability Theory to prove all that,
provided that one has understood the theory of Martingales, a subject
of a later chapter. Indeed, much of this generalised differentiation
theory achieves a beautiful interpretation and becomes comprehensible
in probabilistic terms, via Martingale Theory.




\section{Transformation rules and densities}
Consider a random variable $X : (\Omega, \FF) \to (\RR, \BB)$.
Suppose $\Pr$ is a probability on $(\Omega, \FF)$. We are interested
in the distribution $\Pr_X$ of $X$. Suppose, for some reason, we don't like
it and want to change it to something else. There are two ways to do this.
First, we can change the probability $\Pr$ and replace it by some other
probability $\Qr$. Then $\Pr_X$ will be replaced by $\Qr_X$.
Second, we can take a function $H: (\RR, \BB) \to (\RR, \BB)$
and replace $X$ by $H\comp X$. Then $\Pr_X$ is replaced by 
$\Pr_{H \comp X}$. The two procedures are not, in general, equivalent.

Suppose, for instance, that $X$ is a discrete random variable. Then 
any one-to-one function $H$ will not change the probabilities of
singletons $\{s\}$ such that $\Pr_X\{s\}>0$, but, merely, will
rename them: $\{s\}$ will be transformed to $\{H(s)\}$ and its
probability will remain the same.
Even if $H$ is not one-to-one, there is not much that $H$ can do to
change the probabilities. Consider, for instance, a random variable $X$
with values $1, 2, 3$ and probabilities $p_1, p_2, p_3$, respectively.
Then the most a function $H$ can do is either be one-to-one, in
which case $H(1), H(2), H(3)$ will retain the old probabilities,
or map two points, say $1, 2$, to a single point,
with probability $p_1+p_2$ and leave the the third intact.
Thus, the types of changes in the distribution of of
 a discrete $X$ that can be achieved by taking a function 
of it are quite restricted. To really change its distribution {\em ad libitum},
we need to change the underlying probability $\Pr$.

For the case of absolutely continuous random variables, the story is
different: a merely one-to-one function $H$ can simultaneously
change the values and the distribution in a quite general fashion.

\begin{theorem}
Let $X$ be an absolutely continuous random variable in $\R$ with density $f$.
Let $\phi : \R \to \R$ be strictly increasing differentiable function
and let $\psi$ be its inverse function.
Then $\phi(X)$ a random variable with absolutely continuous
distribution function and density
\[
\psi'  \cdot f \comp \psi \text{ on } \phi(\R),
\]
and $0$ elsewhere.
\end{theorem}
\begin{proof}
Since $\phi$ is strictly increasing, its inverse function exists
and has domain $\phi(\R)$. Then, the distribution function
of $\phi(X)$ is, for any $t \in  \phi(\R)$,
\[
\Pr(\phi(X) \le t) = \Pr (X \le \psi(t)) = \int_{-\infty}^{\psi(t)}
f(x) dx.
\]
By changing variable in the integral we have
\[
 \int_{-\infty}^{\psi(t)} f(x) dx
= \int_{-\infty}^t f(\psi(s)) {\psi}'(s) ds,
\]
where we set $\psi'(s) =0$ for $s \not \in \phi(\R)$.
{From} the definition of an absolutely continuous distribution function we see
that, indeed, $\phi(X)$ has absolutely continuous distribution function
and its density is the function inside the last integral.
\end{proof}


\section{Expectation} 
The expectation of one real random variable is, if it can be defined,
an important numerical aspect of the random variable. It is justified,
for instance, by the Theorem (Law) of Large Numbers which will be
proved at a later chapter.

It is easy to define the expectation of a discrete random variable $X$
with values in $\R$ and probability mass function $p(x)$. Let
$S$ be the set of $x$ such that $p(x) > 0$. Then
\[
\E X   = \sum_{x \in S} x p(x),
\]
provided that this sum can be defined.
We know from Analysis (see \cite{hs}) that the sum of postive numbers
can be defined irrespective of which order we sum the numbers up. However,
not all the summands above are necessarily positive. So let us
consider the positive and negative terms separately and try to define
\[
\E X = \sum_{x \in S_+} x p(x) - \sum_{x \in S_-} (-x) p(x),
\]
where $S_+ := \{ x \in S:~ p(x) > 0\}$, 
where $S_- := \{ x \in S:~ p(x) < 0\}$.
Each of the two sums, separately, is a sum of positive terms, hence it
is well-defined. The only ``problem'' is that such a sum can take 
value $+\infty$. If both sums are finite then $\E X$ is a finite number.
If the first sum is $+\infty$ but the second finite then $\E X =
+\infty$. Similarly, if the first is finite but the second infinite,
then $\E X = -\infty$. The only case where we cannot talk (cannot define)
$\E X$ is when both sums are infinite.

When $X$ has absolutely continuous distribution function with density $f$,
one can define $\E X$ similarly:
\[
\E X = \int_0^{\infty} x f(x) dx - \int_{-\infty}^0 (-x) f(x) dx,
\]
provided that not both integrals are infinity.

In the general case, we need to be more prudent. We will treat the general
case, not only because there are random variables which are neither
discrete or absolutely continuous but because we can seldom (very seldom
indeed) rely on knowledge of the probability mass function or density 
function. 





\subsection{Definition of expectation}
We are going to define the expectation of a random variable 
$X: (\Omega, \FF) \to (\R, \BB)$ with respect to a probability $\Pr$
sitting on $(\Omega, \FF)$. We will use the notation $\E_\Pr X$
or, simply, $\E X$ is the probability $\Pr$ is understood
from the context. After constructing this, we will see
that it does not depend on the choice of probability space,
but only on the law of $X$, namely, we shall show that 
if $X' : (\Omega', \FF') \to (\R, \BB)$ is another random variable
and $\Pr'$ a probability on $(\Omega', \FF')$ such that
$\Pr_X = \Pr'_{X'}$ then $\E_{\Pr} X = \E_{\Pr'} X'$.

\subsubsection{SIMPLE RANDOM VARIABLES}
The simplest possible random variable is 
\[
\1_A(\omega) = \begin{cases}
1, & \text{ if } \omega \in A,\\
0, & \text{ if } \omega \not \in A
\end{cases}
\]
Since $\1_A$ takes value $1$ with probability $\Pr(A)$ or $0$ with 
the complementary probability, it is only reasonable to define
\[
\E \1_A = \Pr(A).
\]
We ``know'' that the expectation should be linear. So we can extend this
definition to linear combinations of indicators (simple random variable)
and define
\begin{equation}
\label{Es}
\E (a_1 \1_{A_1} + \cdots + a_m \1_{A_m})
= a_1 \Pr(A_1) + \cdots + a_m\Pr(A_m).
\end{equation}
Is this a good definition? There is a slight issue here because 
a simple random variable can be written as linear combination of indicators
in two different ways. For example
\[
8 \1_{A} -3 \1_B = 8 \1_{A \setminus B} -3 \1_{B \setminus A}
+ 5 \1_{AB}.
\]
Using the left side we should define the expectation of it
$8 \Pr(A) -3\Pr(B)$, while, using the rigght side, as
$8 \Pr(A \setminus B) - 3 \Pr(B \setminus A)+ 5 \Pr(AB)$.
So we must have
\[
8 \Pr(A) -3\Pr(B) = 8 \Pr(A \setminus B) - 3 \Pr(B \setminus A)+ 5 \Pr(AB).
\]
This is true because of additivity of $\Pr$. Indeed, write $\Pr(A) =
\Pr(A\setminus B) + \Pr(AB)$, $\Pr(B) = \Pr(B\setminus A) + \Pr(AB)$,
substitute in the left side, and you obtain the right side.
This argument extends to the general case and so the definition \eqref{Es}
is good.

%Let us restrict to {\em nonnegative} simple random variables. 
%We will use Greek letters $\xi, \eta, \ldots$ to denote simple random 
%variables.
\begin{lemma}[algebraic properties]
\label{alg}
Suppose  $\xi, \eta$ are simple random variables on the same
probability space $(\Omega, \FF, \Pr)$. Then:\\
(i) If $\Pr(A)=0$ then $\E \xi \1_A = 0$.
\\
(ii) $\E (c \xi) = c \E(\xi)$ for all $c \in \R$.
\\
(iii) $\E(\xi+\eta) = \E \xi + \E \eta$.
\\
(iv) If $\Pr(\xi \ge 0)=1$ then $\E \xi \ge 0$.
If $\Pr(\xi \le \eta)=1$ then $\E \xi \le \E \eta$.
\end{lemma}
\begin{proof}
(i) Suppose $A$ is an event in $\FF$ with $\Pr(A)=0$. Then $\E \xi \1_A =0$
because: If $\xi=\sum_k a_k \1_{A_k}$ then $\xi \1_A =
\sum_k a_k \1_{A_k A}$ and so $\E \xi \1_A  = \sum_k a_k \Pr(A A_k)$.
But $\Pr(A A_k) \le \Pr(A) = 0$, for all $k$.
%Suppose next $\Pr(\xi \not = \eta)=0$ and let $A = \{\xi \not = \eta\}$.
%Write $\xi = \xi \1_A + \xi \1_{A^c}$, $\eta = \eta \1_A + \eta \1_{A^c}$.
\\
(ii), (iii), (iv) (Almost) immediate from the definition \eqref{Es}.
\end{proof}

We now concentrate to nonnegative simple random variables. We allow
such a random variable to take value $+\infty$. In other words,
$\xi$ is a nonnegative simple random variable if $\xi=\sum_{i=1}^m
a_i \1_{A_i}$, with $a_i \in \R \cup \{+\infty\}$ for all $i$.
The expectation of such a random variable is defined as before:
$\E \xi= \sum_{i=1}^m a_i \Pr(A_i)$ and the possibility that one of the values
may be equal to $+\infty$ worries us not, for all numbers are nonnegative,
so the worst that can happen is that $\E\xi$ may be $+\infty$.

\begin{lemma}[analytical properties]
\label{anal}
Suppose $\xi, \xi_1, \xi_2, \ldots$, 
$\eta_1, \eta_2, \ldots$ are simple random variables, and $A \in \FF$.
Then:\\
(i) If $\xi_n$ is an increasing sequence with limit $\1_A$ then
$\E \xi_n$ has limit $\Pr(A)$.\\
(ii) If $\xi_n$ is an increasing sequence with limit $\xi$ then
$\E \xi_n$ has limit $\E \xi$.\\
(iii) If both $\xi_n$, $\eta_n$ are increasing sequences such that
$\lim_n \xi_n(\omega) = \lim_n \eta_n(\omega)$ for all $\omega\in \Omega$, then
$\E \xi_n$, $\E \eta_n$ converge to the same limit.
\end{lemma}
\begin{proof}
(i) Let $\epsilon > 0$. If $\omega \in A$,
then $\xi_n(\omega)$ converges to $1$ and so, for all large $n$,
$\xi_n(\omega) > 1-\epsilon$. In other words,
the sequence of events $\{ \xi_n > 1-\epsilon\}$ 
is increasing with union $A$.
Hence $\Pr(\xi_n > 1-\epsilon)$ increases and has limit $\Pr(A)$. But
\[
\1_A \ge \xi_n \ge (1-\epsilon) \1(\xi_n > 1-\epsilon).
\]
Therefore, by Lemma \ref{alg}(iv),
\[
\Pr(A) \ge \E \xi_n \ge (1-\epsilon) \Pr(\xi_n > 1-\epsilon).
\]
Since the last term converges to $\Pr(A)$ and since $\epsilon$ 
is arbitrary, we have that $\E \xi_n$ converges to $\Pr(A)$.
\\
(ii) Let $a_1, a_2, \ldots, a_m$ be the distinct nonzero 
values of $\xi$. Then $\xi = \sum_{i=1}^m a_i \1(\xi = a_i)$.
Since $\xi_n \uparrow \xi$, we have $\xi_n \1(\xi=a_i) \uparrow \xi\1(\xi=a_i)
=a_1 \1(\xi=a_i)$, and so, $a_i^{-1} \xi_n \1(\xi=a_i) \uparrow \1(\xi=a_i)$.
Applying (i), we have $\E [ a_i^{-1} \xi_n \1(\xi=a_i) ]
\uparrow P(\xi=a_i)$, and so, by Lemma \ref{alg}(ii), 
$\E [\xi_n \1(\xi=a_i) ] \uparrow a_i P(\xi=a_i)$, for all $i=1, \ldots, m$.
Summing over $i$, we have
\[
\sum_{i=1}^m \E [\xi_n \1(\xi=a_i) ] \uparrow \sum_{i=1}^m a_i P(\xi=a_i).
\]
By Lemma \ref{alg}(iii), the left side equals $\E \xi_n$,
while, by the definition \eqref{Es}, the right side equals $\E \xi$.
\\
(iii)
Since both sequences are icnreasing and have the same limit we have
\[
\lim_{m \to \infty} (\xi_n \wedge \eta_m) = \xi_n,
\quad 
\lim_{n \to \infty} (\xi_n \wedge \eta_m) = \eta_m.
\]
By (ii), we have
\[
\lim_{m \to \infty} \E(\xi_n \wedge \eta_m) = \E \xi_n,
\quad 
\lim_{n \to \infty} \E (\xi_n \wedge \eta_m) = \E \eta_m.
\]
Since the numerical sequence $\E (\xi_n \wedge \eta_m) $ is increasing in
both arguments, we have that the limits over $n$ and over $m$ can be
interchanged and so $\lim_{n \to \infty} \E \xi_n =
\lim_{m \to \infty} \E \eta_m$.
\end{proof}


\subsubsection{NONNEGATIVE RANDOM VARIABLES}
Suppose that $X$ is a nonnegative random variable that may,
possibly, take value $+\infty$.
We define
\[
\E X:= \sup\{ \E \xi:~ \xi \text{ is simple nonnegative, and } \xi \le X\}.
\]
We immediately have that there exists a sequence $\eta_n$ of simple random
variables such that $\eta_n \le X$ for all $n$ and $\E \eta_n \to \E X$.
\begin{lemma}
\label{EU}
For ANY sequence $\xi_n$ of simple nonnegative random variables such that
$\xi_n \uparrow X$, we have $\E \xi_n \uparrow \E X$.
\end{lemma}
\begin{proof}
As we just pointed out,
there is one sequence $\eta_n$ of nonnegative simple RVs 
such that $\eta_n \le X$ and $\E\eta_n \uparrow \E X$.
Let $\xi_n$ be a sequence 
of simple random nonnegative variables such that $\xi_n \uparrow X$.
Define
$\zeta_n = \max(\eta_1, \ldots, \eta_n, \xi_n)$.
Clearly, $\zeta_n$ is simple, and $\zeta_n \le X$. Also, $\zeta_n$ 
is increasing with limit $X$. 
Since both $\xi_n$ and $\zeta_n$ increase to the same limit,
by Lemma \ref{anal}(iii), $\E \xi_n$ and $\E \zeta_n$ have the same limit.
But $\eta_n \le \zeta_n \le X$. Hence $\E \eta_n \le \E \zeta_n \le \E X$.
Since $\E \eta_n$ has limit $\E X$, we conclude that $\E \zeta_n$ has limit
$\E X$. Therefore $\E \xi_n$ has limit $\E X$ also. 
\end{proof}

In the course of the proof we said that we can find a sequence of simple
functions that increases to $X$. This is done through, for example,
 the functions  $\tau_n$ defined by \eqref{tau}.
\[
\tau_n(x) := 2^{-n} \lceil 2^n x\rceil  \wedge n.
\]
Since
\[
\lceil x\rceil = \sum_{k=1}^\infty \1(k-1 \le x < k), \quad x \ge 0
\]
we can write
\[
\tau_n(x) := \sum_{k=1}^{n 2^n} 2^{-n}  k \1(k-1 \le 2^n x < k), \quad x \ge 0.
\]
Each $\tau_n$ is left-continuous and $\tau_n(x) \to x$ as $n \to \infty$
for each $x$. Moreover, $\tau_n(x) \le \tau_{n+1}(x)$ for all $x$.
Therefore, for any nonnegative RV $X$, we have that $\tau_n(X)$ is an 
increasing sequence of simple nonnegative RVs with $\tau_n(X) \uparrow X$
and, by Lemma \ref{EU}, 
\[
\E X = \lim_{n \to \infty}  \sum_{k=1}^{n 2^n} 
\frac{k}{2^n} \Pr\bigg(\frac{k-1}{2^n} \le X < \frac{k}{2^n}\bigg).
\]

Extending Lemma \ref{EU}, we obtain
\begin{theorem}[monotone convergence theorem]
\label{mct}
For ANY sequence $X_n$ of nonnegative random variables such that
$X_n \uparrow X$, we have $\E X_n \uparrow \E X$.
\end{theorem}
\begin{proof}
By Lemma \ref{EU}, $\E X = \lim_{m \to \infty} \E \tau_m(X)$. By
the left-continuity of $\tau_m$, we have $\tau_m(X_n) \uparrow \tau_m(X)$,
as $n \to \infty$, and by Lemma \ref{EU}, the same is true after taking  
expectations. So:
\[
\E X = \lim_{m \to \infty} \lim_{n \to \infty} \E \tau_m(X_n).
\]
Because the numerical sequence $\E \tau_m(X_n)$ is increasing in both
indices $m$ and $n$, we can interchange the limits:
\[
\E X = \lim_{n \to \infty} \lim_{m \to \infty} \E \tau_m(X_n)
= \lim_{n \to \infty} \E X_n,
\]
where the last equality follows, again, from Lemma \ref{EU}. 
\end{proof}

\begin{lemma}
Let $X, Y$ be nonnegative random variables on $(\Omega, \FF, \Pr)$. Then:
\\
(i) $\E X = 0$ if and only if $\Pr (X>0)=0$.
\\
(ii) $\E (c X) = c \E X$ for all $c \ge 0$.
\\
(iii) $\E(X+Y) = \E X + \E Y$.
\\
(iv) 
If $\Pr(X \le Y)=1$ then $\E X \le \E Y$.
\end{lemma}
\begin{proof}
We only prove half of (i). The rest are easy. We have $\{X > 0\}$ is the limit
of $\{X > 1/n\}$, as $n \to \infty$. Hence $P(X>0) = \lim_{n \to \infty}
P(X > 1/n)$. If $P(X>0) > 0$ then $P(X > 1/n) > 0$ for some $n$ and,
since $X \ge (1/n) \1(X>1/n)$ we have $\E X \ge (1/n) \Pr(X>1/n)$,
i.e.\ $\E X > 0$.
\end{proof}

\subsubsection{GENERAL RANDOM VARIABLES}
Suppose now $X$ is a random variable with values in $\R$. We say
that $X$ has an expectation if not both $X^+ = \max(X,0)$
and $X^-:=-(-X)^+$ have infinite expectations. In this case,
we define
\[
\E X = \E X^+ - \E X^-.
\]
The definition is, of course, well-motivated: for any number $x$, we have
$x = x^+ - x^-$.

We say that $X$ is integrable (with respect to $\Pr$) if
both $\E X^+$ and $\E X^-$ are finite or, equivalently,
if $\E |X| < \infty$. (The latter follows from the identity
$|x| = x^+ + x^-$.)

\begin{lemma}
Let $X, Y$ be integrable random variables on $(\Omega, \FF, \Pr)$. Then:
\\
(i) $\E (c X) = c \E X$ for all $c \in \R$.
\\
(iii) $\E(X+Y) = \E X + \E Y$.
\\
(iv)
If $\Pr(X \le Y)=1$ then $\E X \le \E Y$.
\end{lemma}

If $A \in \FF$ we can define the expectation of $X$ on $A$ by:
\[
\E (X; A) := \E(X \1_A).
\]
If $\Pr(A) > 0$ we can define the expectation of $X$ given $A$ by:
\[
\E(X | A) := \frac{\E(X; A)}{\Pr(A)}.
\]
We remark that $\E(X|A)$ is expectation with respect to the restriction
$\Pr_A$ of $\Pr$ on $A$, i.e.\ with respect to the probability 
\[
\Pr_A : \FF \to \R; \qquad \Pr_A(B) := \Pr(AB), \quad B \in \FF.
\]
In other words,
\[
\E(X | A) = \E_{\Pr_A} X.
\]

\subsection{Substitution rule} % and chain rules}
\begin{lemma}
Consider the measurable functions
\[
(\Omega, \FF) \xrightarrow[]{Z} (S, \SS) \xrightarrow[]{H} (\R, \BB).
\]
Let $\Pr$ be a probability on $(\Omega, \FF)$. Let $\Pr_Z$ be the law
of $Z$.
Then
\[
\E_{\Pr} H \comp Z = \E_{\Pr_Z} H,
\]
whenever wither side exists.
(Here, $H \comp Z$ is one real random variable on the
probability space $(\Omega, \FF, \Pr)$ and
$H$ is one real random variable on the probability space $(S, \SS, \Pr_Z)$.)
\end{lemma}
\begin{proof}
Suppose $H$ is an indicator random variable, i.e.\ $H = \1_B$ for
some $B \in \SS$. Then $\E_{\Pr_Z} \1_A = \Pr_Z(A)$ by the definition
of the expectation of a simple random variable. On the other hand,
$H \comp Z = \1_A(Z)$ is an indicator random variable on $(\Omega, \FF)$: it
is the indicator of the set $\{\omega \in \Omega:~ Z(\omega) \in A\}$.
Hence, again by the by the definition
of the expectation of a simple random variable,
$\E_{\Pr} H \comp Z = \Pr(Z \in A)$.
But $\Pr_Z(A) = \Pr(Z \in A)$ by the definition of the law
of the random variable $Z$ (see section \ref{law}).
Suppose next that $H$ is a simple random variable. Use the above and
linearity of expectation to get the result.
Suppose that $H$ is a nonnegative random variable.
Use Lemma \ref{mct}.
Finally, suppose that $H$ has no sign restriction, and use the
definition of expectation.
\end{proof}

\begin{corollary}
\label{iii}
If $X$ is a real random variable on $(\Omega, \FF, \Pr)$ with expectation
$\E_{\Pr} X$ and law $\Pr_X$ then
\[
\E_{\Pr} X = \E_{\Pr_X}\iota
\]
where $\iota: \R \to \R$ is the identity function: $\iota(x) \equiv x$.
\end{corollary}
Therefore, the expectation of a random variable depends only on its law.

Suppose that $X$ is a discrete random variable with values in
a finite set $S \subset \R$ and probability mass
function $p(x), x \in S$.
Since $X = \sum_{x \in S} x \1(X=x)$ is a simple random variable, 
we immediately have that $\E X = \sum_{x \in S} x \Pr(X=x) = \sum_{x \in S}
x p(x)$, as needed.
The same formula holds for a discrete random variable with values
in a countable set $S$: Simply enumerate the elements of $S$
and use monotonone convergence theorem.

Let us now consider an absolutely continuous random variable $X$
with density $f$. We would like to show that $\E X$ is compatible with
the definition given at the begining of the section, namely that it
equals $\int_\R x f(x) dx$. To do this, we need to revisit the
notion of an integral:

\subsection{Lebesgue Integration}
Let $h: (\R, \BB) \to (\R, \BB)$ be measurable and suppose $h \ge 0$.
Consider the random variable $U$ on the coin-flip space
$(\Omega=\{0,1\}^\N, \FF, \Pr)$, defined by  \eqref{U}.
We define $\int_\R h(x) dx$ by
\[
\int_\R h(x) dx := \sum_{n \in \Z} \E h(U+n).
\]
This is called the Lebesgue integral of $h$.
We also define $\int_a^b h(x) dx$ by
\[
\int_a^b h(x) dx := \int_\R h(x) \1(a \le x \le b) dx,
\]
and, more generally, for any $B \in \BB$,
\[
\int_B h(x) dx := \int_\R h(x) \1(x \in B) dx.
\]
If $h$ has no restriction on sign, we define $\int_a^b h(x) dx$
as $\int_a^b h^+(x) dx - \int_a^b h^-(x) dx$ 
provided that not both terms are infinite.
The following theorem connects what one learns in basic Calculus
with what we just defined.
\begin{theorem}
\label{RL}
(i) If $h$ is Riemann integrable on $[a, b]$ then the Lebesgue
integral $\int_a^b h(x) dx$ exists and coincides with the Riemann integral.
\\
(ii) If $h$ is bounded and measurable then it is Riemann integrable on $[a,b]$
if the set of discontinuities of $h$ have measure zero, in the sense
of Definition \ref{mz}.
\end{theorem}

For example, if $h$ is piecewise continuous, then its discontinuities
have measure zero and so it is Riemann integrable.

As a countexample, consider the function $h(x) = \1(x \in \Q)$,
$0 \le x \le 1$. This function is discontinuous on every
point of $[0,1]$. The interval $[0,1]$ does not have measure zero.
Hence it is not Riemann integrable. However, $h$ is measurable and nonnegative,
and so it does have a Lebesgue integral. Its integral equals $\E h(U)
= \Pr(U\in \Q) = 0$.

Theorem \ref{RL} enables us to use all rules we learn in basic Integration
Calculus to the case of Lebesgue integration when the two integrals
coincide.


Suppose now that $X$ is a random variable with absolutely continuous
distribution function $F$ and density $f$. 
Consider the function $\Qr : \BB \to \R$ defined by 
\[
\Qr(B) := \int_B f(x) dx.
\]
Since $\Qr(B)= \Pr_X(B)$ for $B = (-\infty, x]$, we have
that $\Qr=\Pr_X$.
More generally,
\begin{lemma}
\label{chainrule}
Let $\Pr_X$ be the law of a random variable $X$ with density $f$.
Then, for any measurable $g : (\R, \BB) \to (\R, \BB)$,
\[
\int_\R g(x) f(x) dx = \E_{\Pr_X} g
\]
provided that wither side exists.
\end{lemma}
\begin{proof} 
If $g = \1_B$, then this is what was discussed before the Lemman.
For $g$ simple, we use linearity. For general $g$ we approximate.
\end{proof}

\begin{corollary}
Let $\Pr_X$ be the law of an integrable random variable $X$ with density $f$.
\\
(i) If $\iota$ is the identity function on $\R$ then
\[
\int_\R x f(x) dx = E_{\Pr_X} \iota.
\]
(ii) 
\[
\E X = \int_\R x f(x) dx.
\]
\end{corollary}
\begin{proof}
(i) follows from Lemma \ref{chainrule} with $g = \iota$.
(ii) follows from corollary \ref{iii}
\end{proof}





\section{Inequalities}
Mathematics needs inequalities probably mored than equalities. Probability,
in particular, which, in some sense, contains a lot of approximation 
ideas needs inequalities. This section discusses some basic ones.

\subsection{Markov, Chebyshev, Chernoff}
\begin{lemma}[Markov inequality]
If $X$ is a nonnegative random variable then
\[
\Pr(X \ge t) \le \frac{\E X}{t}, \quad t > 0.
\]
\end{lemma}
\begin{proof}
We have
\[
t \1(X \ge t) \le X
\]
and $\E$ is preserved by $\le$.
\end{proof}

\begin{definition}
The variance of a real random variable $X$ with $\E X^2 < \infty$ is
defined by
\[
\var X := \E (X- \E X)^2.
\]
\end{definition}

\begin{lemma}[Chebyshev inequality]
If $X$ is a real random variable with $\E X^2 < \infty$
then
\[
\Pr(|X - \E X| \ge t) \le \frac{\var X}{t}
\]
\end{lemma}
\begin{proof}
Apply the Markov inequality to $|X - \E X|$.
\end{proof}

\begin{lemma}[Chernoff inequality]
If $X$ is a real random variable then
\[
\Pr(X \ge t) \le \inf_g \frac{g(\E X)}{g(t)}
\]
where the infimum is taken over all positive increasing functions $g$.
\end{lemma}
\begin{proof}
Since $g$ is increasing,
\[
\{X \ge t\} \subset \{g(X) \ge g(t)\}
\]
Now apply the Markov inequality to $g(X)$.
\end{proof}



\subsection{Jensen inequality}
A function $\phi: \R \to \R$ is convex if
\[
\varphi(p a + (1-p) b) \le p \varphi(a) + (1-p) \varphi(b)
\]
for all $a, b \in \R$ and all $0 \le p \le 1$.
Notice that if $\xi$ is a random variable with $\Pr(\xi=a)=p$, $\Pr(\xi=b)=1-p$,
this definition can be written as
\[
\phi(\E \xi) \le \E \phi(\xi).
\]
Jensen's inequality generalises this observation:
\begin{lemma}
\label{jensen}
Let $X$ be a real integrable random variable and $\phi$ a convex function. Then
\[
\phi(\E X) \le \E \phi(X).
\] 
\end{lemma}
Geometrically, a convex function is such that the graph of
the function on the interval $[a, b]$ lies below the sraight segment
with endpoints $(a, \phi(a))$, $(b, \phi(b))$.
\begin{center}
FIGURE
\end{center}
If we take a staight line with slope equal to the slope
of this segment and move it down, at some point it will be entirely
below the whole graph of $\phi$. Moreover, if we consider the set
of all straight lines that are below the graph of $\phi$ and take
their envelope (the maximum) then this equals $\phi$.
Namely, 
\begin{equation}
\label{hb}
\phi(x) = \max_{\ell \in L(\phi)} \ell(x), \quad x \in \R,
\end{equation}
where $L(\phi)$ is the collection of all functions 
$\ell(x) \equiv \alpha x+\beta$ such that $\ell \le \phi$.
To show this rigorously, observe that 
\[
a < b < c \Rightarrow
\frac{\phi(b)-\phi(a)}{b-a}
\le
\frac{\phi(c)-\phi(b)}{c-b},
\]
by the definition of convexity.
Let $\epsilon> 0$,  $a=b-\epsilon$, $c=b+\epsilon$
and so
\[
D_-\phi(b) := \lim_{\epsilon \downarrow 0}\frac{\phi(b)-\phi(b-\epsilon)}{\epsilon}
\le
\lim_{\epsilon \downarrow 0}\frac{\phi(b+\epsilon)-\phi(b)}{\epsilon}:= D_+\phi(b),
\]
where the limits exist by monotonicity.
Let $\alpha$ be between $D_-\phi(b)$ and $D_+\phi(b)$. Then, if $x > b+\epsilon$,
we have
\[
\frac{\phi(b+\epsilon)-\phi(b)}{\epsilon}
\le 
\frac{\phi(x)-\phi(b)}{x-b},
\]
and so
\[
\alpha \le D_+\phi(b) \le \frac{\phi(x)-\phi(b)}{x-b}, \quad x > b,
\]
or $\alpha(x-b) + \phi(b) \le \phi(x)$, for all $x \ge b$. Arguing similarly 
for all $x \le b$, we have
\[
\alpha(x-b) + \phi(b) \le \phi(x), \quad x \in \R.
\]
Thus, the function $\ell(x) := \alpha(x-b) + \phi(b) \le \phi(x)$ belongs
to $L(\phi)$ and also, $\ell(b) = \phi(b)$.
This proves \eqref{hb}.

\noindent{\bf Proof of Lemma \ref{jensen}:}
\[ 
\phi(\E X) = \max_{\ell \in L(\phi)} \ell(\E X)
=
\max_{\ell \in L(\phi)} \E \ell(X)
\le
\E \max_{\ell \in L(\phi)} \ell(X)
=
\E \phi(X).
\]
The first equality is due to \eqref{hb}.
The second uses linearity of expectation.
The third uses monotonicity of expectation.
The last reuses \eqref{hb}.
$\Box$



\section{Moments}
\begin{definition}
When $r > 0$, the {\sc $r$-moment} of a nonnegative RV $X$ is defined as 
the quantity $\E X^r$.
The $r$-norm of a real RV $X$ is defined as $ ||X||_r:=(\E |X|^r)^{1/r}$.
\end{definition}

\begin{lemma}
The $r$-norm of $X$ is increasing in $r$.
\end{lemma}
\begin{proof}
Let $r < s$ and $\phi(x) = x^{s/r}$, $x > 0$. Notice that $\phi$
is convex. (This follows from the fact that its second derivative is positive.)
Now apply the Jensen inequality.
\end{proof}

\begin{corollary}
If $\E |X|^p < \infty$ for some $p > 0$ then $\E |X|^r < \infty$ for
all $0 < r < p$.
\end{corollary}




\section{H\"older and Minkowski}

\begin{lemma}[H\"older inequality]
Let $X, Y$ be real random variables. Then
\[
|\E(XY)| \le ||X||_p ||Y||_q,
\]
for any $p, q > 0$, $p^{-1} + q^{-1} =1$, as long as all 
terms involved exist and are finite.
\end{lemma}

\begin{lemma}[Minkowski inequality]
Let $X, Y$ be real random variables. Then
\[
||X+Y ||_p \le ||X||_p + ||Y||_p,
\]
for any $p > 1$, as long as all
terms involved exist and are finite.
\end{lemma}













\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip








{\sf
\section*{Appendix A: Glossary}
I summarise here some notation, and terminology.
\begin{description}
\item[$\bullet$]
The minimum between two real numbers $a, b$ is denoted by $a \wedge b$,
and the maximum as $a \vee b$. We have $-(a \vee b) = (-a) \wedge (-b)$.
In particular, we write $a^+ = a \vee 0$, $a^- = -(a \wedge 0)$.
\item[$\bullet$]
We express the statement that $x$ is an element of (or belongs to)
a set $A$ by $x \in A$. The negation of the latter is denoted by 
$x \not \in A$.
We write $A \subset B$ for to express
the statement ``$x \in  A \Rightarrow x \in B$''.
We let $A \cap B$ be the intersection
and $A \cup B$ the union of $A$ and $B$. To save space, we often write
$AB$ in lieu of $A \cap B$ and $ABC$ in lieu of $A \cap B \cap C$.
The set $A^c$ is defined through \\
$``x \in A^c \iff x \not \in A$''\\
Nai\"ve set theory and first order logic are algebraically equivalent
through the above and through: \\
``$A \cap B \iff x \in A \text{ and } x \in B$''\\
``$A \cup B \iff x \in A \text{ or } x \in B$''\\
We let $B \setminus A = B \cap A^c$
and we write $B-A$ for $B \setminus A$ if $A \subset B$.
If $\{A_j, j \in J\}$ is a collection of sets we let $\cap_{j \in J} A_j$ 
be their
intersection and $\cup_{j \in J} A_j$ their union. Here, $J$ is an 
arbitrary set. If $J=\N$ we write
$\cap_{j \in \N} A_j = \cup_{j=1}^\infty A_j$, and, as usually in Mathematics,
the convention is that the symbol $\infty$ appearing on top is not part
of the index set ($\infty$ is not a natural number). 
(Compare this with a sum of numbers: $\sum_{j=1}^\infty x_j$
means that $j$ runs over $1,2,\ldots$ but does not take the value $\infty$.)
%We have $B \setminus \cap_j A_j = \cup_j (B\setminus A_j)$.
Here is an example of how we translate elementary logic (i.e.\ ordinary 
language, say English) in Mathematics: Consider the sentence \\
$\text{\sf S}=$``after some day it will never rain again in Glasgow''.\\
If we let $\text{ \sf R}_i$ denote the sentence ``it rains on the $i$-th day in Glasgow''
we can write the sentence above as\\
$\text{\sf S}=$``$\exists i ~\forall j ~\ge i \text{ not} R_i$''.\\
Taking the negation of this sentence (to which, I think, I can
safely assign the truth value) we get:\\
$\text{not\sf S}=$$\text{not}[\exists i ~\forall j ~\ge i \text{ not} R_i]
= [\forall i~ \exists j \ge i ~ R_i]$.
\\
Translating this back into English, it reads:\\
$\text{not\sf S}=$``for all days there will be a day in the future at which it rains in Glasgow''\\
and, since this is too unpalatable even for the literati, we can express
it, equivalently, as\\
$\text{not\sf S}=$``it rains in Glasgow infinitely often''.\\
What does this have to do with sets? Well, imagine there is a big set (the
``universe'')--call it $\Omega$--containing all possible states of Glasgow at
all days. At the minimum we want to know whether it rains or not
on each day. So we decide to let an element of $\Omega$ be the sequence
$(\omega_1, \omega_2, \ldots)$ of states of Glasgow, where $\omega_i$
takes values ``rain'' or `doesntrain'' and represents what happens
on the $i$-th day in Glasgow. So $\Omega$ is the set of all these
sequences, mathematically written as $\Omega = \{\text{rain},
\text{doesntrain}\}^\N$. Then $R_i$ can be taken to be the set of
all sequences $\omega \in \Omega$ such that $\omega_i=\text{rain}$.
You can then check that the set (subset of $\Omega$)\\
$S = \cup_i \cap_{j \ge i} R_i^c$ corresponds to the statement S,\\
$S^c = \cap_i \cup_{j \ge i} R_i$ corresponds to the statement notS.
\\
In this sense, the so-called Kolmogorov model of Probability merely puts
within a mathematical framework (that of Set Theory)
what we intuitively feel as assigning numbers representing chance to 
statements, to events, to situations describable by ordinary language.
So Probability Theory is ordinary logic together with numbers
assigned to statements. In the language of Set Theory this is called
Measure Theory.
\item[$\bullet$]
If $A$ is a set then $2^A$ is the set of its subsets.
A set of sets (or ``collection'' of sets) is a subset of $2^A$.
If $A$ has $n$ elements then $2^A$ has $2^n$ elements. 
If $\N$ is the set of natural numbers then $2^\N$ has as many elements
as the set of real numbers.
(And why, on earth, should we use the symbol $2^A$? To explain, consider
a simple set, say $A=\{x,y,z\}$. I can form a subset of $A$ by putting
a $1$ to each element I pick or $0$ to each element I do not pick.
For instance, $011$ means ``do not pick $x$, pick $y$, pick $z$'', i.e.\
it refers to the subset $\{y,z\}$. We thus see there is a correspondence
between subsets of $A$ and triples of $0$'s and $1$'s. How many such triples
do we have? Obviously, $2 \times 2 \times 2 = 2^3$. This explains why
we have $2^3=8$ subsets. If $A$ had $n$ elements, you see there are $2^n$
subsets and so the notation $2^A$ is suggestive of this, and we carry it on
even to cases where $A$ has infinite number of elements.)
\item[$\bullet$]
If $f:X \to Y$ is a function then, for any $B \subset Y$ we define
$f^{-1}(B) = \{x \in X: f(x) \in B\}$, and for any $A \subset X$ we define
$f(A) = \{f(x): x \in A\}$.
Thus $f$ can be lifted as a map from $2^X$ into $2^Y$ and we also have
a map $f^{-1}$ from $2^Y$ into $2^X$. We always have
$f (f^{-1}(B)) \subset B$ and $f^{-1}(f(A)) \supset A$.
Also, $f^{-1}(\cap_j B_j) = \cap_j f^{-1} (B_j)$
$f^{-1}(\cap_j B_j) = \cap_j f^{-1} (B_j)$,
$f^{-1}(B^c) = f^{-1}(B)^c$. However, $f$ as a map on sets does not behave
that well (fortunately!) because 
$f(\cap A_j) \subset \cap_j f(A_j)$ (equality, in general, fails), but
$f(\cup A_j) = \cup_j f(A_j)$; also, $f(A_2-A_1) \subset f(A_2) - f(A_1)$.
\item[$\bullet$]
The set of functions from $X$ into $Y$ is denoted by $Y^X$. The notation
is motivated by the fact that the set of functions from $\{1, \ldots, n\}$ into
$\R$ is ``the same'' as $\R^n$.
Consider, for example, the set of functions from a set $A$ into $\{0,1\}$.
This is denoted as $\{0,1\}^A$. Since there is a one-to-one correspondence
between this set of functions and the collection of subsets $2^A$ of
$A$ (as explained
above), the surprise that you may have just experienced with this new notation
should not be as high.
\item[$\bullet$]
If $A \subset \R$ then $\sup A$ is the least of all 
$b \in \R \cup \{+\infty\}$ such that $a \le b$ for all $a \in b$.
We let $\inf A = -\sup(-A)$, where $-A=\{-a: a \in A\}$.
If $x_n$, $n=1,2, \ldots$ is a countable collection of real numbers (i.e.\
a sequence) then $\sup x_n$ is written in lieu of $\sup\{x_1, x_2, \ldots\}$.
Similarly, for $\inf x_n$.
The upper limit of $x_n$ is defined by $\limsup_{n \to \infty} x_n
= \inf_{n \ge 1} \sup_{k \ge n} x_k$.
The lower limit is defined by $\liminf_{n \to \infty} x_n
= - \limsup_{n \to \infty} (-x_n)$.
The sequence converges (in an extended sense) if $\limsup x_n
= \liminf x_n$. This common number is denoted as $\lim_{n \to \infty}
x_n$ and can be a real number of $\pm \infty$. We say that the sequence
converges (in a real sense) if $\limsup x_n
= \liminf x_n$ and this common number is a real number.
\item[$\bullet$]
A $\pi$-system $\CC$ on a set $\Omega$ is a subset of $2^\Omega$ such that
$A, B \in \CC \Rightarrow A \cap B \in \CC$.
\item[$\bullet$]
A field $\AA$ or field on a set $\Omega$  is a $\pi$ system
such that $A \in \AA \Rightarrow A^c \in \AA$.
\item[$\bullet$]
A $\sigma$-field or $\sigma$-field $\FF$ on a set $\Omega$ is a subset
of $2^\Omega$ such that (i) $A \in \FF \Rightarrow A^c \in \FF$,
and (ii) $A_1, A_2, \ldots \in \FF \Rightarrow \cap_{j=1}^\infty A_j \in \FF$.
\item[$\bullet$]
If $\{\FF_j\}$ is a collection of $\sigma$-fields on the same set
then $\cap_j \FF_j$ is a $\sigma$-field too: it is the largest
$\sigma$-field contained in all of them.
(The intersection of $\sigma$-fields is never empty because every
$\sigma$-field contains the empty set.)
However the union of $\sigma$-fields is not a nice object and we
don't consider it. Instead, we define $\vee_j \FF_j$ to
be the smallest $\sigma$-field containing all the $\FF_j$.
\item[$\bullet$]
If $A, B$ are sets, then $A \times B$ is the set of all ordered
pairs $(a,b)$ where $a \in A$ and $b \in B$. 
%One may wonder
%what an ordered pair is, but one may define it as $\{a, \{a,b\}\}$.
Similarly, if $\{A_j, j \in \N\}$ is a sequence of sets
then $\bigtimes_{j=1}^\infty A_j$ is the set of all 
sequences $(a_1, a_2, \ldots)$ where $a_j \in A_j$ for 
all $j$.
Finally, if $\{A_t, t \in T\}$ is an arbitrary collection of sets
we may defined $\bigtimes_{t \in T} A_t$ as the collection of
functions $f \in A^T$, where $A=\cup_{t \in T} A_t$ such that
$f(t) \in A_t$ for all $t \in T$.
Notice that this definition does not respect any ``order'' in the index
set $T$ even if this is there; the order imposed in the definition
of the Cartesian product of finitely or countably many sets
is an extra bag that we have been forced to carry (for good reasons).
\item[$\bullet$]
When $A = \bigtimes_{j \in J} A_j$ is a cartesian product, we can define,
for each $i\in J$  the projection function
$\pi_i : A \to A_i$ by assigning each $(a_j, j \in J)$ the element 
$a_i$ of $A_i$.


\item[$\bullet$]
Let $(\Omega_1, \FF_1)$, $(\Omega_2, \FF_2)$ be measurable spaces.
Then $\FF_1 \otimes \FF_2$ is 
the $\sigma$-field on $\Omega_1 \times \Omega_2$
generated by sets of the form $A_1 \times A_2$, where $A_1 \in \FF_1$,
$A_2 \in \FF_2$.
The definition is extended for any finite product.

\item[$\bullet$]
The Borel $\sigma$-field $\BB$ on $\R$ is the $\sigma$-field
generated by intervals $[a, b]$.
The Borel $\sigma$-field $\BB(\R^2)$ on $\R^2 = \R \times \R$
is defined by $\BB(\R^2) = \BB \otimes \BB$.
Similarly, we define $\BB(\R^d)$ for any natural number $d$.

\item[$\bullet$]
Let $(S_i, \SS_i)$, $i \in \N$ be measurable spaces,  and let
$S= \bigtimes_i S_i$.
A rectangle is a subset of $S$ of the form
$B_1 \times \cdots \times B_j \times \cdots$.
A finite-dimensional rectangle is a rectangle such that
$B_k = S_k$ for all $k$ greater than some index $j$.
A cylinder set is a subset of $S$ of the form
$A \times S_{j+1} \times S_{j+2} \times \cdots$, where
$A \in \SS_1 \otimes \cdots \otimes \SS_j$.
A finite-dimensional rectangle is a rectangle and a cylinder set.
A rectangle is not necessarily a cylinder set.
The collection of rectangles is $\pi$-system (the intersection of two rectangles
is still a rectangle; but the union of two rectangles is not a rectangle;
the complement of a rectangle is not a rectangle).
Ditto for finite-dimensional rectangles.
The collection of cylinder sets is a field (the intersection of
two cylinder sets is a cylinder set and the complement of a cylinder
set is a cylinder set), but not a $\sigma$-field.
On $S$ we can put a natural $\sigma$-field, denoted by $\bigotimes_i \SS_i$:
it is the $\sigma$-field generated by cylinder sets; it is also
generated by rectangles; it is also generated by finite-dimensional rectangles;
it is also the smallest $\sigma$-field such that every projection
$\pi_i : (S, \SS) \to (S_i, \SS_i)$ is a random variable.
\item[$\bullet$]
If $A \subset \Omega$ we define $\1_A: \Omega \to \R$ by $\1_A(\omega)=1$
if $\omega \in A$; $\1_A(\omega)=0$ if $\omega \not \in A$.
\item[$\bullet$]
If $A$ is a finite set then $\sharp A$ is the number of its elements (its
cardinality).
\item[$\bullet$]
Let $A_n$ be a sequence of subsets of $\Omega$. We define \\
$\limsup_{n \to \infty} A_n = \cap_n \cup_{m\ge n} A_m$,
\\
$\liminf_{n \to \infty} A_n = \cup_n \cap_{m\ge n} A_m$,
\\
and notice that $(\limsup_{n \to \infty} A_n)^c 
=\liminf_{n \to \infty} A_n^c$. 
\\ 
We say that $\lim_{n \to \infty} A_n = A$ (we also write $A_n \to A$)
if, by definition,
$\limsup_{n \to \infty} A_n =  \liminf_{n \to \infty} A_n$,
and write this also as $A_n \to A$.
For example, if $A_n$ is an increasing sequence of sets then (show this!)
$\lim_{n \to \infty} A_n = \cup_n A_n$ and if $A_n$ is decreasing
then $\lim_{n \to \infty} A_n = \cap_n A_n$.
If 
\item[$\bullet$]
If $\Omega$ is a set and $\FF \subset 2^\Omega$ is a $\sigma$-field, then
a function $\Pr: \FF \to [0,1]$ is called probability (measure) if
$\Pr(\Omega)=1$ and $\Pr(\cup_{n=1}^\infty A_n) = \sum_{n=1}^\infty \Pr(A_n)$,
whenever the sets $A_n \in \FF$ are mutually disjoint.
Some important consequences of this definition are:
(i) $\Pr(\varnothing)=0$, (ii) if $A \subset B$ then $\Pr(A) \le \Pr(B)$,
(iii) $\Pr(A \cup B) = \Pr(A)+\Pr(B)-\Pr(A \cap B)$,
(iv) $\Pr(\cup_n A_n) \le \sum_n \Pr(A_n)$ (no restriction on the
sets $A_n$ here),
(v)
$\Pr(A_n) \to 0$ if $A_n \supset A_{n+1}$ for all $n$ and 
$\cap_n A_n = \varnothing$.

\item[$\bullet$]
Let $(\Omega, \FF, \Pr)$ by any probability space. If $A_n$ is
a sequence of sets in $\FF$ such that $A_n \to A$ as $n \to \infty$
then $\Pr(A_n) \to \Pr(A)$ as $n \to \infty$.

\end{description}
}


{\sf
\section*{Appendix B: Set theoretic results}
Let $\Omega$ be a set and $\CC$ a field of subsets of it.
The function $\Pr_0 \CC \to [0,1]$ with $\Pr_0\Omega)=1$ is additive if
$\Pr_0A \cup B) = \Pr_0A)+\Pr_0B)$ if $AB = \varnothing$.
It is countably additive if for any $A \in \CC$ for which
there exist mutually disjoint $A_n \in \CC$ with $A = \cup_n A_n$
we have $\Pr_0A) = \sum_n \Pr_0A_n)$.


\noindent{\bf Lemma B1:}
{\em
The following are equivalent:
\\
(i)
$\Pr_0$ is countably additive on the field $\CC$.
\\
(ii)
$\Pr_0(A_n) \to 0$ for all decreasing sequences $A_n \in \CC$ with
$\cap_n A_n=\varnothing$.
\\
(iii)
$\Pr_0(A_n) \to 0$ for all sequences $A_n \in \CC$ with
$A_n \to \varnothing$.
}
\\
\begin{proof}
Suppose (i) holds. Let $A_n$ decrease to $\varnothing$. We have
\begin{align*}
\Pr_0(A_1) &= \sum_{k=1}^\infty \Pr_0(A_k - A_{k+1})\\
&= \lim_{n \to \infty} \sum_{k=1}^{n-1} [\Pr_0(A_k)-\Pr_0(A_{k+1})]
\\
&= \lim_{n \to \infty} [\Pr_0(A_1)-\Pr_0(A_n)],
\end{align*}
i.e.\ $\Pr_0(A_n) \to 0$.
Suppose (ii) holds. Let $A_n$ be mutually disjoint elements
of $\CC$ with $\cup_n A_n \in \CC$. By finite additivity,
\[
\Pr_0(\cup_k A_k) = \sum_{k=1}^n\Pr_0(A_k) + \Pr_0(\cup_{k>n} A_k).
\]
Since $\cup_{k>n} A_k$ decreases to $\varnothing$ we have
$\Pr_0(\cup_{k>n} A_k) \to 0$, and so we obtain countable additivity.
We omit the proof of the last part.
\end{proof}


\noindent{\bf Lemma B2:}
Suppose that $\Pr_0$ is countably additive on the field $\CC$.
\\
{\em
(i)
If $A_n$ is a sequence in $\CC$ that has a limit (but which is not
necessarily in $\CC$, then $\Pr_0(A_n)$ has a limit.
\\
(ii)
If $A_n$, $B_n$ are sequences in $\CC$ with the same limit (not
necessarily in $\CC$) then $\Pr_0(A_n)$, $\Pr_0(B_n)$
have the same limit.
}
\\
\begin{proof}: Omitted \end{proof}


\noindent{\bf Lemma B3:}
Suppose that $\Pr_0$ is countably additive on the field $\CC$.
Let $D(\CC)$ be the class of subsets of $\Omega$
that are limits of sets in $\CC$.
Define $\Pr_1$ on $D(\CC)$ by
\[
\Pr_1(\lim_n A_n) = \lim_n \Pr_0(A_n), \quad A_n \in \CC.
\]
Then
\\
{\em
(i)
$D(\CC)$ is a field.
\\
(ii)
The definition $\Pr_1$ is valid.
\\
(iii)
$\Pr_1$ is countably additive on $D(\CC)$.
}
\\
\begin{proof}
(i) Easy.
\\
(ii) Follows from Lemma B2.
\\
(iii)
From Lemma B1, it suffices to show that if $A_n$ is a sequence of
elements of $D(\CC)$ such that $A_n \downarrow \varnothing$
then $\Pr_1(A_n) \to 0$.
Since $A_m \in D(\CC)$ we can write
\[
A_m = \lim_n B_{m,n}.
\]
Then we also have
\[
A_m = \lim_n (B_{1,n} \cap \cdots \cap B_{m,n}).
\]
Choose a sequence of integers $n_m$ increasing
to $\infty$ such that
\[
\lim_m [\Pr_1(A_m) - \Pr_0(B_{1,n_m} \cap \cdots \cap B_{m,n_m})]=0.
\]
Since
\[
\lim_m (B_{1,n_m} \cap \cdots \cap B_{m,n_m}) = \varnothing,
\]
we have
\[
\lim_m \Pr_0(B_{1,n_m} \cap \cdots \cap B_{m,n_m})=0,
\]
and so 
\[
\lim_m \Pr_1(A_m) =0.
\]
\end{proof}

\noindent{\bf Lemma B4:}
Suppose that $\Pr_0$ is countably additive on the field $\CC$.
Let $D(\CC)$ be the class of subsets of $\Omega$
that are limits of sets in $\CC$.
Let $D^2(\CC)$ be the class of subsets of $\Omega$
that are limits of sets in $D(\CC)$.
Define $\Pr_2$ on $D^2(\CC)$ by
\[
\Pr_2(\lim_n A_n) = \lim_n \Pr_1(A_n), \quad A_n \in D(\CC).
\]
Then
\\
{\em
(i)
$D^2(\CC)$ is a field.
\\
(ii)
The definition $\Pr_2$ is valid.
\\
(iii)
$\Pr_2$ is countably additive on $D^2(\CC)$.
}
\\
\begin{proof}
Repretition of the proof of Lemman B3.
\end{proof}



}




\section*{Exercises}
\begin{exercise}
\item
\label{one}
Suppose that $(S_j, \SS_j)$ are measurable spaces, for all $j \in J$.
Show that if $S=\prod_{j \in J} S_j$ then the cylinder $\sigma$-field $\SS$
on $S$ is the smallest $\sigma$-field such that each projection map 
$\pi_j : S \to S_j$ becomes measurable.
In other words, $\SS = \bigvee_{j \in J} \sigma(\pi_j)$.
\item
Suppose that the random variable $X$ takes $n$ distinct values (i.e.\
$X(\Omega)$ is a set with $n$ elements). Show that $\sigma(X)$ has
$2^{2^n}$ elements and describe (give a procedure for describing) them.
\item
\label{count}
Consider the space $\Omega=\{0,1\}^\N$ and the class of sets $\CC_0$ defined
in the tossing coins section. 
(i) Show that $\CC_0$ is a countable set, i.e.\
there is a one-to-one correspondence between $\CC_0$ and $\N$.
(ii) Show that $\CC_1$, the field generated by $\CC_0$ is also countable.
(iii) Consider $\FF$, the $\sigma$-field generated by $\CC_0$ (and also by 
$\CC_1$) and show that it is uncountable; more specifically, show that
there is a one-to-one correspondence between $\FF$ and $2^\N$.
(iv) Consider the class $2^\Omega$ of all subsets of $\Omega$ and show that
there is a one-to-one correspondence between $2^\Omega$ and
$2^{2^\N}$ (the class of subsets of the set of subsets of $\N$.)
It is known \cite{kf} that the set of subsets of a set is strictly larger than
the set itself. Using this, conclude that there $2^\Omega$ is strictly
larger than $\FF$. In fact MUCH larger: In some sense, most subsets of 
$\Omega$ are outside $\FF$! This means that most sets of sequences
of coin tosses cannot be expressed using countably many operations on
elmentary sets (i.e.\ sets from $\CC_0$). The CURIOUS thing though is
that we know very few of these sets: although the majority of them
are outside $\FF$, somehow, it is very heard to come up with an example.\footnote{In some sense, this exercise is a baby version of G"odel's theorem which
says, naively speaking, that most theorems cannot be proved. Except that
we hardly ever encounter them.}
\end{exercise}




\end{unit}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{4}{Joint distributions (a silly name for a chapter) and independence}
\end{unit}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{5}{Important special distributions (a silly name for a chapter)}
\end{unit}

\noindent
\hrulefill

\begin{thebibliography}{9}
\bibitem{fg}
{\sc B. Fristedt \& L. Gray}
{\em A Modern Approach to Probability Theory},
Birkh\"auser, 1997.
\bibitem{hs}
{\sc E. Hewitt \& K. Stromberg}
{\em Real and Abstract Analysis},
Springer, 1965.
\bibitem{kf}
{\sc A. N. Kolmogorov \& S. V. Fomin}, 
{\em Introductory Real Analysis}, 
Dover, 1975.
\bibitem{wil}
{\sc D. Williams},
{\em Probability with Martingales},
Cambridge, 1991.
\end{thebibliography}


\end{document}
