%% ================================================================
\newpage
\section{Probability}

%% ================================================================
\subsection{Events}

%% ================================================================
\subsubsection{Fundamental definitions}

\begin{defns}
When we do an \bfidx{experiment}, we obtain an \bfidx{outcome}.  The set of all
outcomes, conventionally written $\Omega$, is called the \bfidx{sample space}.
(Mathematically, we only require $\Omega$ to be a set.)
\end{defns}

\begin{defn}
\label{defn:event}
An \bfidx{event} is, intuitively, any subset of the sample space.
Technically, it is any \emphidx{measurable subset} of the sample space.
\end{defn}

\begin{ex}
The experiment is rolling a 6-sided die once.  The outcome is the number of
pips on the top face after the roll.  The sample space $\Omega$ is
$\{1,2,3,4,5,6\}$.  Example events are ``the result of the roll is a 3'' and
``the result of the roll is odd''.
\end{ex}

\begin{defn}
Events $A$ and $B$ are \bfidx{disjoint} if $A \cap B = \emptyset$.
\end{defn}

\begin{defn}
\label{defn:sigma_field}
A collection $\mcF$ of subsets of $\Omega$ is called a \bfidx{$\sigma$-field}
or \bfidx{event space} if $\emptyset \in \mcF$, $\mcF$ is closed under
countable unions, and $\mcF$ is closed under complements.
(Note in particular that this means $\Omega \in \mcF$ and $\mcF$
is closed under countable intersections.)
\end{defn}

\begin{rem}
There is a superficial resemblance with topological spaces: A topological space
$X$ has a topology $\mcT$ which is a collection of ``open'' subsets that is
closed under complements, \emph{finite} (rather than countable) intersection
and \emph{arbitrary} (rather than countable) union.
\end{rem}

\begin{exs}
The smallest (or \emphidx{coarsest}) $\sigma$-field for any $\Omega$ is
$\{\emptyset, \Omega\}$; the largest (or \emphidx{finest}) is $2^\Omega$, the
set of all subsets of $\Omega$.  There may be many $\sigma$-fields in between.
For example, if $A$ is any subset of $\Omega$ which isn't $\emptyset$ or
$\Omega$, then one can check that the 4-element collection $\{\emptyset, A,
A^c, \Omega\}$ is a $\sigma$-field.
\end{exs}

\begin{defn}
\label{defn:probability_measure}
A \bfidx{probability measure} $P$ is a function from a $\sigma$-field $\mcF$
to $[0,1]$ such that:
\begin{itemize}
\item For all $A \in \mcF$, $P(A) \ge 0$;
\item $P(\Omega) = 1$ and $P(\emptyset) = 0$;
\item If $A_1, A_2, \ldots,$ is a finite or countable subset of $\mcF$,
	with the $A_i$'s all (pairwise) disjoint, then
	$$
		P(\cup_{i} A_i) = \sum_i P(A_i).
	$$
	This is the \bfidx{countable additivity} property of the probability
	measure $P$.
\end{itemize}
\end{defn}

\begin{rem}
For uncountable $\Omega$, $2^\Omega$ is a $\sigma$-field, but it is impossible
to define a probability measure on it; it is ``too big''.  Consult your
favorite textbook on Lebesgue measure for the reason why.  For finite or
countable $\Omega$, on the other hand, $2^\Omega$ is in fact what we think of
for $\mcF$.
\end{rem}

\begin{defn}
A \bfidx{probability space} is a triple $(\Omega, \mcF, P)$ of a sample space
$\Omega$, a $\sigma$-field $\mcF$ on $\Omega$, and a probability measure $P$ on
$\mcF$.
\end{defn}

\begin{rem}
Technically, a probability space is nothing more than a measure space $\Omega$
with the additional requirement that $P(\Omega)=1$.
\end{rem}

%% ================================================================
\subsubsection{Conditioning and independence}
\label{sec:drv_condn_indep}

\begin{defn}
\label{defn:conditional_probability}
Let $A,B$ be two events with $P(B)>0$.  Then we define the
\bfidx{conditional probability} of $A$ \bfidx{given} $B$ to be
$$
	P(A|B) = \frac{P(A\cap B)}{P(B)}.
$$
Mnemonic:  \emph{intersection over given}.
\end{defn}

\begin{notn}
We will often write $P(A,B)$ in place of $P(A \cap B)$.
\end{notn}

%[xxx \bfidx{trees} ... maybe include a picture?]

\begin{defn}
\label{defn:indep_events}
Two events $A$ and $B$ are
\bfidx{independent} (or \bfidx{pairwise independent}) if
$$
	P(A \cap B) = P(A) P(B).
$$
Mnemonic: write down $P(A) = P(A|B) = P(A\cap B)/P(B)$ and clear the
denominators.
\end{defn}

\begin{rem}
This is not the same as disjoint.  If $A$ and $B$ are disjoint, then by
countable additivity of $P$, we have
$$
	P(A \cup B) = P(A) + P(B).
$$
\end{rem}

\begin{defn}
Events $A_1, \ldots, A_n$ are
\bfidx{independent} if for all $I \subseteq \{1, 2, \ldots, n\}$,
$$
	P(\cap_{i\in I} A_i) = \prod_{i\in I} P(A_i).
$$
Mnemonic:  We just look at all possible factorizations.
\end{defn}

\begin{ex}
Three events $A$, $B$, and $C$ are independent if
$$
	P(A\cap B) = P(A)P(B),
	P(A\cap C) = P(A)P(C),
	P(B\cap C) = P(B)P(C), \qand
	P(A\cap B \cap C) = P(A)P(B)P(C).
$$
\end{ex}

\begin{thm}[Partition theorem, or law of total probablity]
\label{thm:partition}
Let\index{partition theorem}
\index{law of total probability}
\index{total probability, law of}
$\{B_i\}$ be a countable partition of $\Omega$ and
let $A$ be an event.  Then
$$
	P(A) = \sum_{i} P(A|B_i) P(B_i).
$$
\begin{proof}
Note that
$$
	P(A) = \sum_{i} P(A \cap B_i)
$$
since the $B_i$'s partition $\Omega$.
\end{proof}
\end{thm}

%\begin{defn}[]
%[xxx \bfidx{continuity} \ldots did we ever use this definition for anything
%else?]
%\end{defn}

%% ================================================================
\newpage
\subsection{Discrete random variables}

%% ================================================================
\subsubsection{Definitions}

\begin{defn}
\label{defn:drv}
A \bfidx{random variable} $X$ is a function $X:\Omega \to \R$.  We say $X$ is a
\bfidx{discrete random variable} if its range, $X(\Omega)$, is finite or
countable.
\end{defn}

\begin{ex}
Roll two 6-sided dice and let $X$ be their sum.
\end{ex}

\begin{defn}
Given a random variable $X$, the
\bfidx{probability mass function} or \bfidx{PMF} of $X$,
written $f(x)$ or $f_X(x)$, is
$$
	f_X(x) = P(X=x) = P(X^{-1}(x)).
$$
This is the probability that $X$'s value is some specific real number $x$.
Note that $X^{-1}(x)$, the \bfidx{preimage} of $x$, is an event and so we can
compute its probability using the probability measure $P$.
\end{defn}

\begin{defn}
\label{defn:ID}
Let $X_1$ and $X_2$ be two random variables on two probability spaces
$(\Omega_1, \mcF_1, P_1)$ and $(\Omega_2, \mcF_2, P_2)$, respectively.  Then
$X_1$ and $X_2$ are \bfidx{identically distributed} if $X_1(x) = X_2(x)$ for
all $x \in \R$.
\end{defn}

\begin{rem}
\label{rem:ID_same_PMF}
Identically distributed discrete random variables $X$ and $Y$ have the
same PMF.
\end{rem}

\begin{rem}
Just as with events, which have a general measure-theoretic definition
(definition \ref{defn:event}), there is also a general measure-theoretic
definition for random variables: they are simply measurable functions from a
probability space to a measurable space.
\end{rem}

%% ================================================================
\subsubsection{Catalog of discrete random variables}
\label{sec:drv_catalog}

Note:  \bfidx{mean} and \bfidx{variance} are defined in section
\ref{sec:drv_expns}.  They are included here for ready reference.

\bfidxtwo{Bernoulli}{Bernoulli distribution} DRV:
\begin{itemize}
\item Parameter $p \in [0,1]$.
\item Range $X=\{0,1\}$.
\item PMF $P(X=0)=p$, $P(X=1) = 1-p$.
\item Example:  Flip a $p$-weighted coin once.
\item Mean: $1-p$.
\item Variance: $p(1-p)$.
\end{itemize}

\bfidxtwo{Binomial}{binomial distribution} DRV:
\begin{itemize}
\item Two parameters: $p \in [0,1]$ and $n \in \Z^+$.
\item Range $X=\{0,1,2, \ldots, n\}$.
\item PMF $P(X=k)={n \choose k}p^k(1-p)^{n-k}.$
\item Example:  Flip a $p$-weighted coin $n$ times; $X$ is the number of heads.
\item Mean: $np$.
\item Variance: $np(1-p)$.
\end{itemize}

\begin{rem}
There is a trick to see that the sum of probabilities is 1 --- recognize the
sum of probabilities as the expansion of $(p+(1-p))^n$ using the binomial
theorem:
$$
	1 = 1^n = (p+(1-p))^n = \sum_{k=0}^n {n \choose k}p^k(1-p)^{n-k}.
$$
\end{rem}

\bfidxtwo{Poisson}{Poisson distribution} DRV:
\begin{itemize}
\item Parameter $\lambda > 0$.
\item Range $X=\{0,1,2, \ldots\}$.
\item PMF $P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda}$.
\item Example:  Limiting case of binomial random variable with large $n$,
	small $p$, and $\lambda=np \approx 1$.
\item Mean: $\lambda$.
\item Variance: $\lambda$.
\end{itemize}

\bfidxtwo{Geometric}{geometric distribution} DRV:
\begin{itemize}
\item Parameter $p\in[0,1]$.
\item Range $X=\{1,2,3, \ldots\}$.
\item PMF $P(X=k)=p(1-p)^{k-1}$.
\item Example: Flip a $p$-weighted coin until you get heads; $X$ is the number
	of flips it takes.  (Note:  some authors count the number of tails
	\emph{before} the head.)
\item Mean:  $1/p$.
\item Variance: $(1-p)/p^2$.
\end{itemize}

\bfidxtwo{Negative binomial}{negative binomial distribution} DRV:
\begin{itemize}
\item Two parameters $p\in[0,1]$ and $n=1,2,3, \ldots$.
\item Range $X=\{n,n+1,n+2, \ldots\}$.
\item PMF $P(X=k)={{k-1}\choose{n-1}}p^n (1-p)^{k-n}$.
\item Example: Flip a $p$-weighted coin until you get $n$ heads; $X$ is the
	number of flips it takes.
\item Note: Deriving the ${{k-1}\choose{n-1}}$ factor is a non-trivial
	counting problem; it is deferred until later in the course.
\item Mean: $n/p$.
\item Variance: $n(1-p)/p^2$.
\end{itemize}

%% ================================================================
\subsubsection{Expectations}
\label{sec:drv_expns}

\begin{defn}
Functions of a discrete random variable:
If $X:\Omega \to \R$ and $g:\R\to\R$ then $g(X):\Omega \to \R$ is another
random variable.  Let $Y=g(X)$.
\end{defn}

To find the PMF of $g(X)$ given PMF of $(X)$:  write the latter as $f_X(x) =
P(X=x)$.  Then
$$
	P(g(X)=y)
	= \sum_{x \in g^{-1}(y)} P(X=x)
	= \sum_{x \in g^{-1}(y)} f_X(x).
$$

\begin{defn}
Let $X$ be a discrete random variable with PMF $f_X(x)$.
If
$$
	\sum_x |x|f_X(x) < \infty
$$
(i.e. if we have absolute convergence) then we define the \bfidx{expected
value} (also call \bfidx{expectation} or \bfidx{mean}) of $X$ to be
$$
	E[X]
	= \sum_x x f_X(x)
	= \sum_x x P(X=x).
$$
Mnemonic:  This is just the weighted sum of possible $X$ values, weighted by
their probabilities.
\end{defn}

%xxx expectations for our catalog \ldots 1-26 notes.

\begin{thm}[Law of the Unconscious Statistician]
\label{thm:lous_drv}
Let\index{Law of the Unconscious Statistician} $X$ be a discrete random
variable and $g:\R \to \R$.  Let $Y=g(X)$.  If
$$
	\sum_x |g(x)|\, f_X(x) < \infty
$$
then
$$
	E[Y] = \sum_x g(x) f_X(x).
$$
\end{thm}

\begin{defn}
\label{defn:drv_variance}
The \bfidx{variance} of $X$, written $\sigma^2(X)$ or $\Var(X)$, is
$$
	\sigma^2(X) = E[(X-E[X])^2].
$$
\end{defn}

\begin{defn}
The square root of the variance is the \bfidx{standard deviation}, written
$\sigma(X)$ or $\sigma_X$.
\end{defn}

\begin{prop}
Let $\mu = E[X]$.  Then
$$
	\sigma^2(X) = E[X^2] - E[X]^2.
$$
\begin{proof}
FOIL, and use linearity of expectation.
\end{proof}
\end{prop}

\begin{prop}
\label{prop:Var_c2}
$\Var(cX) = c^2\Var(X)$.
\begin{proof}
{} {}
$$
	\Var(cX) = E[c^2X^2] - E[cX]^2
	= c^2 E[X^2] - c^2 E[X]^2
	= c^2 \left(E[X^2] - E[X]^2\right)
	= c^2 \Var(X).
$$
\end{proof}
\end{prop}

\begin{thm}
Let $X$ be a discrete random variable; let $a,b \in \R$.  Then
\begin{itemize}
\item[(i)]  $E[aX+b] = aE[X]+b$.
\item[(ii)] If $P(X=b)=1$ then $E[X]=b$.
\item[(iii)] If $a \le X \le b$ then $a \le E[X] \le b$.
\item[(iv)] If $g,h: \R \to \R$ and $g(X),h(X)$ have finite means,
	then $E[g(X)+h(X)]=E[g(X)]+E[h(X)]$.
\end{itemize}
\end{thm}

\begin{defn}
Let $X$ be a discrete random variable and let $B$ be an event.
The \bfidx{conditional PMF} of $X$ given $B$ is
$$
	f(x|B) = P(X=x|B).
$$
The \bfidx{conditional expectation} of $X$ given $B$ is
$$
	E[X|B] = \sum_x x f(x|B)
$$
provided (as usual) that the sum converges absolutely.
\end{defn}

\begin{thm}[Partition theorem, or law of total expectation]
\label{thm:partition_thm}
Let\index{partition theorem}
\index{law of total expectation}
\index{total expectation, law of}
$\{B_i\}$ be a countable partition of $\Omega$ and
let $X$ be a random variable.  Then
$$
	E[X] = \sum_i E[X|B_i] P(B_i).
$$
\end{thm}

%% ================================================================
\newpage
\subsection{Multiple discrete random variables}

%% ================================================================
\subsubsection{Definitions}

%In terms of the PMFs $f_X(x)$ and $f_Y(y)$,
\begin{defn}
We define the \bfidx{joint PMF} or
\bfidx{joint density} of $X$ and $Y$ to be
$$
	f_{X,Y}(x,y) = P(X=x,Y=y).
$$
\end{defn}

\begin{prop}
For $A \subseteq \R^2$ we have
$$
	P((x,y) \in A) = \sum_{(x,y) \in A} f_{X,Y}(x,y).
$$
\end{prop}

\begin{cor}
Let $g(x,y) : \R^2 \to \R$.
Let $X$ and $Y$ be discrete random variables and let $Z=g(X,Y)$.  Then
$$
	f_Z(z) = P(Z=z) = \sum_{z \in g^{-1}(x,y)} f_{X,Y}(x,y).
$$
\end{cor}

We can use joint densities to recover \bfidx{marginal} densities:
\begin{cor}
\label{cor:marginal_drv}
Let $X$ and $Y$ be discrete random variables with joint density
$f_{X,Y}$.  Then
$$
	f_X(x) = \sum_{y} f_{X,Y}(x,y) \qqand
	f_Y(y) = \sum_{x} f_{X,Y}(x,y).
$$
\end{cor}

%% ================================================================
\subsubsection{Expectations}

\begin{thm}[Law of the Unconscious Statistician]
\label{thm:lous_mdrv}
Let \index{Law of the Unconscious Statistician} $X$ and $Y$ be discrete random
variables and let $g(x,y):\R^2 \to \R$.  Let $Z=g(X,Y)$.  Then
$$
	E[Z] = \sum_{x,y} g(x,y) f_{X,Y}(x,y).
$$
\begin{proof}
As in the single-variable case (theorem \ref{thm:lous_mdrv}).
\end{proof}
\end{thm}

\begin{cor}
Let $X$ and $Y$ be discrete random variables, and let $a,b \in \R$.
Then
$$
	E[aX+bY] = aE[X] + bE[Y].
$$
\begin{proof}
Use $g(x,y)=ax+by$, and use the theorem twice.
\end{proof}
\end{cor}

%% ================================================================
\subsubsection{Independence}

Recall definition \ref{defn:indep_events} of independent events: $A$ and $B$
are independent if $P(A \cap B) = P(A)P(B)$.  We use this to define
independence of discrete random variables.

\begin{defn}
\label{defn:indep_drvs}
Two discrete random variables $X$ and $Y$ are \bfidx{independent} if,
for all $x$ and $y$,
$$
	P(X=x, Y=y) = P(X=x) P(Y=y).
$$
Using PMF notation, we say $X$ and $Y$ are independent if
$$
	f_{X,Y}(x,y) = f_X(x) f_Y(y)
$$
for all $x$ and $y$, i.e. if the joint PMF \bfidx{factors}.
\end{defn}

\begin{notn}
\label{notn:IID}
We often abbreviate \emph{independent and identically distributed}
(definitions \ref{defn:indep_drvs} and \ref{defn:ID}) as \bfidx{IID}.
\end{notn}

Question:  given only the joint density of $X$ and $Y$, can we tell if
$X$ and $Y$ are independent?  From corollary \ref{cor:marginal_drv},
we can recover the PMFs of $X$ and $Y$:
$$
	f_X(x) = \sum_{y} f_{X,Y}(x,y) \qqand
	f_Y(y) = \sum_{x} f_{X,Y}(x,y).
$$
Then we can multiply them back together and see if we get the joint
density back.

Point:
\begin{itemize}
\item If $X$ and $Y$ are independent, then we can go from marginals to joint
	PMFs by multiplying.
\item We can always go from joint PMFs to marginals by summing as above.
\end{itemize}

\begin{thm}
\label{thm:drv_EXY_EX_EY}
If $X$ and $Y$ are independent discrete random variables, then
$$
	E[XY] = E[X]E[Y].
$$
\end{thm}

\begin{thm}
If $X$ and $Y$ are independent discrete random variables and $g,h:\R\to\R$ then
$g(X)$ and $h(Y)$ are independent discrete random variables.
\end{thm}

\begin{cor}
In particular,
$$
	E[g(X)h(Y)] = E[g(X)]E[h(Y)]
$$
provided $g(X)$ and $h(Y)$ have finite mean.
\end{cor}

\begin{thm}
\label{thm:drv_Var_X_Y_Var_X_Var_Y}
If $X$ and $Y$ are independent discrete random variables then
$$
	\Var(X+Y) = \Var(X) + \Var(Y).
$$
\begin{proof}
Use definition \ref{defn:drv_variance} and theorem \ref{thm:drv_EXY_EX_EY}.
\end{proof}
\end{thm}

\begin{defn}
We say that $X$ and $Y$ are \bfidx{uncorrelated} if
$$
	E[XY] = E[X] E[Y].
$$
\end{defn}

\begin{rem}
Independent implies uncorrelated but not vice versa.
\end{rem}

\begin{rem}
Theorem \ref{thm:drv_Var_X_Y_Var_X_Var_Y} holds for uncorrelated
discrete random variables.
\end{rem}

%% ================================================================
\subsubsection{Sample mean}

\begin{defn}
Let $X_1$, \ldots, $X_n$ be independent and identically distributed.
(Think of multiple trials of the same experiment.)
Since each $X_i$ has the same expectation, we call their common mean the
\bfidx{population mean} and denote it by $\mu$.
Likewise, we call their common variance the \bfidx{population variance} and
denote it by $\sigma^2$.
Let
$$
	\Xbar = \frac{\sum_{i=1}^n X_i}{n}.
$$
This is a new random variable, called the \bfidx{sample mean}
of $X_1,\ldots,X_n$.
\end{defn}

By linearity of expectation,
$$
	E[\Xbar] = \frac{1}{n} \sum_{i=1}^n E[X_j] = \mu.
$$
Recall from proposition that the variance scales as
$\Var(cX) = c^2\Var(X)$.  Also, since the $X_i$'s are independent,
their variances add.  Thus
$$
	\Var(\Xbar)
	= \Var\left(\frac{\sum_{i=1}^n X_i}{n} \right)
	= \frac{1}{n^2} \Var\left(\sum_{i=1}^n X_i\right)
	= \frac{n}{n^2} \sigma^2
	= \frac{\sigma^2}{n}.
$$

%% ================================================================
\subsubsection{Moment-generating functions and characteristic functions}

\begin{defns}
\label{defns:discrete_MGF_and_CF}
Let $X$ be a discrete random variable.  Then the \bfidx{moment-generating
function} or \bfidx{MGF} of $X$ is
$$
	M_X(t) = E[e^{tX}].
$$
By the Law of the Unconscious Statistician (theorem \ref{thm:lous_drv}), this
is
$$
	M_X(t) = \sum_x e^{tx} f_X(x).
$$
Likewise, the \bfidx{characteristic function} of $X$ is
$$
	\beta_X(t) = E[e^{itX}]
$$
which is
$$
	\beta_X(t) = \sum_x e^{itx} f_X(x).
$$
\end{defns}

\begin{rem}
These functions are just computational tricks.  There is no intrinsic meaning
in these functions.
\end{rem}

\begin{prop}
Let $M_X(t)$ be the moment-generating function for a discrete random variable
$X$.  Then
$$
	E[X^k] = M_X^{(k)}(0) = \frac{d^k}{dt^k} M_X(t) \bigg|_{t=0}.
$$
\end{prop}

\begin{prop}
If $X$ and $Y$ are identically distributed, they have the same PMF (remark
\ref{rem:ID_same_PMF}) and thus they also have the same MGF.
\end{prop}

\begin{prop}
Let $X$ and $Y$ be independent discrete random variables and let $Z=X+Y$.
Then
$$
	M_Z(t) = M_X(t) M_Y(t).
$$
\end{prop}

%% ================================================================
\subsubsection{Sums of discrete random variables}

Moment-generating functions are perhaps a better approach than the
following.

Let $X$ and $Y$ be discrete random variables and let $Z=X+Y$.  We can find the
PMF of $Z$ by
$$
	f_Z(z) = P(Z=z) = P(X+Y=z) = \sum_{x+y=z} f_{X,Y}(x,y)
	= \sum_x \sum_{y=z-x} f_{X,Y}(x,y)
	= \sum_x f_{X,Y}(x,z-x).
$$
Now further suppose that $X$ and $Y$ are independent.  Then
$$
	f_{X,Y}(x,z-x) = f_X(x) f_Y(z-x)
$$
so
$$
	f_Z(z) = \sum_x f_X(x) f_Y(z-x).
$$
This is the \bfidx{convolution} of $f_X$ and $f_Y$.
Note that, as always in convolutions, we are summing over all the ways in
which $x$ and $y$ can add up to $z$.

%% ================================================================
\newpage
\subsection{Continuous random variables}

\subsubsection{Definitions}

A continuous random variable, mimicking definition \ref{defn:drv}, is a
function from $\Omega$ to $\R$ with the property that for all $x \in \R$,
$P(X=x)=0$.  Thus, the PMF which we used for discrete random variables is not
useful.  Instead we first define another function, namely, $P(X\le x)$.

\begin{defn}
The \bfidx{cumulative distribution function} or \bfidx{CDF} for a random
variable (whether discrete or continuous) is
$$
	F_X(x) = P(X \le x).
$$
\end{defn}

%[xxx plot CDF for fair six-sided die.]

\begin{thm}
The CDF $F_X(x)$ for a random variable satisfies the following properties:
\begin{itemize}
\item $0 \le F_X(x) \le 1$, and $F_X$ is non-decreasing.
\item $\lim_{x\to -\infty} F_X(x)=0$ and $\lim_{x\to +\infty} F_X(x)=1$.
\item $F_X(x)$ is right-continuous (in the sense from introductory calculus).
\end{itemize}
\end{thm}

\begin{defn}
A random variable $X$ is a \bfidx{continuous random variable} if there exists a
function $f_X(x)$, called the \bfidx{probability density function} of
\bfidx{PDF}, such that the CDF $F_X(x)$ is given by
$\int_{-\infty}^{+\infty} f_X(x)\,dx$.
\end{defn}

\begin{rem}
Note that the integral is done using Lebesgue measure (or, for the purposes of
this course, Riemann integration).  If we allow counting measure and require
countable range, then we can subsume discrete random variables into this
definition.  However, that is outside the scope of this course.
\end{rem}

\begin{rem}
%[xxx type up.]
Some random variables are neither discrete nor continuous; these appear
for example in dynamical systems.
%[xxx type up with graphs:  a CDF can have continuous and discontiuous
%parts.  Such random variables are not discussed in this course.]
% xxx absolutely continuous w/r/t Lebesgue measure -- ?
\end{rem}

\begin{rem}
The PDF and CDF are related as follows (making use of the second
fundamental theorem of calculus):
\begin{eqnarray*}
	F_X(x) &=& \int_{-\infty}^x f_X(t)\,dt \\
	f_X(x) &=& \frac{d}{dx} F_X(x).
\end{eqnarray*}
\end{rem}

\begin{rem}
The PDF of $X$ is the probability that $X$ lies in some interval.  E.g.
$$
	P(a \le X \le b) = \int_a^b f_X(x) \, dx.
$$
Thus PDFs are non-negative and have integral 1.
\end{rem}

\begin{rem}
We can now neatly define some terminology from statistics.  Namely:
\begin{itemize}
\item Let $X$ be a random variable from $\R$ to $\R$ with CDF $F_X(x)$ and
$f_X(x)$.
\item The \bfidx{mean} of $X$ is the expectation value $E[X]$ as defined below.
\item The \bfidx{median} of $X$ is $F_X^{-1}(0.5)$.
\item A \bfidx{mode} of $X$ is a local maximum of $f_X(x)$.
	If the PDF has two local maxima, we say that $X$ is \bfidx{bimodal}.
	If the PDF has a single maximum, we call it \emph{the} mode of $X$.
\end{itemize}
\end{rem}

%% ================================================================
\subsubsection{Catalog of continuous random variables}
\label{sec:crv_catalog}

Note:  \bfidx{mean} and \bfidx{variance} are defined in section
\ref{sec:crv_expns}.  They are included here for ready reference.  I thought
about including graphs of the PDFs and CDFs, but instead I will refer you to
the excellent Wikipedia article on \emph{Probability distribution}, and the
pages linking from there.

\bfidxtwo{Uniform}{uniform distribution} CRV:
\begin{itemize}
\item Parameters $a < b$.
\item Range $[a,b]$.
\item PDF
	$$
		f_X(x) = \begin{cases}
		\frac{1}{b-a}, & a \le x \le b \\
		0, \textrm{elsewhere}.
		\end{cases}
	$$
\item CDF
	$$
		F_X(x) = \begin{cases}
		0, & x < a \\
		\frac{x-a}{b-a}, & a \le x < b \\
		0, & b \le x \\
		\end{cases}
	$$
%\item xxx graphs of PDF and CDF.
\item Mean: $(a+b)/2$.
\item Variance: $(b-a)^2/12$.
\end{itemize}

\bfidxtwo{Exponential}{exponential distribution} CRV:
\begin{itemize}
\item Parameter $\lambda > 0$.
\item Range $X=\{0,\infty\}$.
\item PDF
	$$
		f_X(x) = \begin{cases}
		\lambda e^{-\lambda x}, & x \ge 0 \\
		0, & x < 0.
		\end{cases}
	$$
\item CDF
	$$
		F_X(x) = \begin{cases}
		1 - e^{-\lambda x}, & x \ge 0 \\
		0, & x < 0.
		\end{cases}
	$$
%\item xxx graphs of PDF and CDF.
\item Mean: $1/\lambda$.
\item Variance: $1/\lambda^2$.
\end{itemize}

\bfidxtwo{Cauchy}{Cauchy distribution} CRV:
\begin{itemize}
\item No parameters.
\item Range $X=\{-\infty,\infty\}$.
\item PDF
	$$
		f_X(x) = \frac{1}{\pi(1+x^2)}.
	$$
\item CDF
	$$
		F_X(x) = \frac{\tan^{-1}(x)}{\pi} + \frac{1}{2}.
	$$
%\item xxx graphs of PDF and CDF.
\item Mean: infinite.
\item Variance: infinite.
\end{itemize}

\bfidxtwo{Normal}{normal distribution} CRV (see section
	\ref{sec:normal_distrib}):
\begin{itemize}
\item Parameters $\mu \in \R$, $\sigma > 0$.
\item Note:  with $\mu=0$ and $\sigma=1$ we have the \bfidx{standard normal
	distribution}.  One says it has \emph{zero mean and unit variance}.
\item Range $X=\{-\infty,\infty\}$.
\item PDF
	$$
		f_X(x) = \frac{1}{\sigma\sqrt{2\pi}}
		\exp\left[\frac{-1}{\;\;\;2}\left(\frac{x-\mu}{\sigma}\right)^2\right].
	$$
\item CDF:  No closed-form expression.  Related to $\mathrm{erf}(x)$ but
	not quite the same:  The standard normal CDF is
	$\frac{1}{2}(1+\mathrm{erf}(x/\sqrt{2}))$.  Note that some computing
	systems may have $\mathrm{erf}(x)$ but not \texttt{normalcdf}, or
	vice versa.  Thus this conversion formula comes in handy.
	%$$
	%\frac{1+\mathrm{erf}(x/\sqrt(2))}{2}
	%$$
%\item xxx graphs of PDF and CDF.
\item Mean: $\mu$.
\item Variance: $\sigma^2$.
\end{itemize}

\bfidxtwo{Gamma}{gamma distribution} CRV (see section \ref{sec:gamma_distrib}):
\begin{itemize}
\item Parameters $\lambda>0$, $w>0$.
\item Range $x \ge 0$.
\item PDF
	$$
		f_X(x) = \frac{\lambda^w}{\Gamma(w)}\, x^{w-1} e^{-\lambda x}, x \ge 0.
	$$
\item CDF TBD.
\item Mean: $w/\lambda$.
\item Variance: $w/\lambda^2$.
\end{itemize}

\bfidxtwo{Beta}{beta distribution} CRV:
\begin{itemize}
\item Parameters $\alpha>0$, $\beta>0$.
\item Range $x \in [0, 1]$.
\item PDF
	$$
		f_X(x) = \frac{x^\alpha (1-x)^\beta}{B(\alpha,\beta)}.
	$$
\item CDF TBD.
\item Mean: $\alpha/(\alpha+\beta)$.
\item Variance: $\alpha\beta...$
\end{itemize}

%% ----------------------------------------------------------------
\subsubsection{The normal distribution}
\label{sec:normal_distrib}

\begin{defn}
The \bfidx{normal distribution} has two parameters: real $\mu$ and positive
$\sigma$.  A random variable with the normal distribution has PDF
$$
	%f(x) = \frac{1}{\sigma\sqrt{2 \pi}} \exp\left(-(x-\mu)^2/2\sigma^2\right).
	f(x) = \frac{1}{\sigma\sqrt{2\pi}}
	\exp\left[\frac{-1}{\;\;\;2}\left(\frac{x-\mu}{\sigma}\right)^2\right].
$$
\end{defn}

\begin{rem}
The normal distribution has mean $\mu$ and variance $\sigma^2$.
\end{rem}

\begin{defn}
With $\mu=0$ and $\sigma=1$ we have the \bfidx{standard normal distribution}.
\end{defn}

%% ----------------------------------------------------------------
\subsubsection{The gamma distribution}
\label{sec:gamma_distrib}

\begin{defn}
The \bfidx{gamma function} is defined by
$$
	\Gamma(\omega) = \int_0^\infty x^{w-1} e^{-x} dx.
$$
\end{defn}

\begin{rem}
Integration by parts shows that $\Gamma(n) = (n-1)!$.  Thus, the gamma function
is a generalized \plainidx{factorial} function.
\end{rem}

\begin{defn}
The \bfidx{gamma distribution} has two parameters $\lambda,w>0$.  A random
variable with the gamma distribution has PDF
$$
	f(x) = \begin{cases}
		\frac{\lambda^w}{\Gamma(w)} x^{w-1} e^{-\lambda x}, & x \ge 0 \\
		0, & x < 0.
		\end{cases}
$$
\end{defn}

\begin{rem}
With $w=1$ we have an exponential distribution.  Thus, the gamma distribution
generalizes the exponential distribution.
\end{rem}

\begin{prop}
The gamma distribution has mean $w/\lambda$.
\end{prop}

%% ----------------------------------------------------------------
\subsubsection{Functions of a single random variable}
\label{sec:fcn_of_crv}

Given a continuous random variable $X$ and $g(x):\R\to\R$, we have a new
continuous random variable $Y=g(X)$.  Often one wants to find the PDF of $Y$
given the PDF of $X$.  The \bfidx{method} is to first find the CDF of $Y$, then
differentiate to find the PDF.

\begin{ex}
Let $X$ be uniform on $[0,1]$ and let $Y=X^2$.  The CDF of $Y$ is
$$
	P(Y \le y) = P(X^2 \le y) = P(X \le \sqrt y) = \int_{0}^{\sqrt y} 1 \,dx
	= \sqrt y
$$
i.e.
$$
	F_Y(y) = \begin{cases}
		0, & y < 0 \\
		\sqrt y, & 0 \le y < 1 \\
		1, & 1 \le y. \\
	\end{cases}
$$
Then the PDF is
$$
	f_Y(y) = \begin{cases}
		0, & y < 0 \\
		\frac{1}{2\sqrt y}, & 0 \le y < 1 \\
		0, & 1 \le y. \\
	\end{cases}
$$
\end{ex}

The critical step in the method is going from
$P(X^2 \le y)$ to $P(X \le \sqrt y)$.

%% ----------------------------------------------------------------
\subsubsection{Expectations}
\label{sec:crv_expns}

\begin{defn}
Let $X$ be a continuous random variable with PDF $f_X(x)$.
If
$$
	\int_{-\infty}^{+\infty} |x|f_X(x)\,dx < \infty
$$
(i.e. if we have absolute convergence) then we define the \bfidx{expected
value} (also call \bfidx{expectation} or \bfidx{mean}) of $X$ to be
$$
	E[X] =
	\int_{-\infty}^{+\infty} x\,f_X(x)\,dx.
$$
Mnemonic:  As in the discrete case, this is just the weighted sum of possible
$X$ values, weighted by their probabilities.
\end{defn}

\begin{defn}
\label{defn:var}
Let $X$ be a continuous random variable.
The \bfidx{variance} of $X$ is
$$
	E[(X-\mu)^2]
$$
where $\mu=E[X]$.
By the corollary to the Law of the Unconscious Statistician (below),
$$
	\Var(X) = E[X^2] - E[X]^2.
$$
\end{defn}

\begin{thm}[Law of the Unconscious Statistician]
\label{thm:lous_crv}
Let\index{Law of the Unconscious Statistician} $X$ be a continuous random
variable and $g:\R \to \R$.  Let $Y=g(X)$.  If
$$
	\int_{-\infty}^{+\infty} |g(x)| \,f_X(x) \, dx < \infty
$$
then
$$
	E[Y] = 
	\int_{-\infty}^{+\infty} g(x) \,f_X(x) \, dx < \infty
$$
\end{thm}

\begin{cor}
If $g,h:\R\to\R$ and $a,b\in\R$ then
$$
	E[ag(X)+bh(X)] = aE[g(X)]+bE[h(X)].
$$
\end{cor}

%% ================================================================
\newpage
\subsection{Multiple continuous random variables}

%% ----------------------------------------------------------------
\subsubsection{Definitions}

\begin{defn}
Given two continuous random variables $X$ and $Y$, we define their
\bfidx{joint CDF} to be
$$
	F_{X,Y}(x,y) = P(X\le x,Y\le y).
$$
\end{defn}

\begin{defn}
Two random variables $X$ and $Y$ are \bfidx{jointly continuous} if there exists
a function $f_{X,Y}(x,y)$ (their \bfidx{joint PDF}) such that
$$
	F_{X,Y}(x,y) = \int_{-\infty}^{x} \int_{-\infty}^y f_{X,Y}(u,v)\,dv\,du.
$$
\end{defn}

The \bfidx{joint PDF} is thought of as
$$
	P(a \le X \le b, c \le Y \le d) =
	\int_{x=a}^{x=b} \int_{y=c}^{y=d} f_{X,Y}(x,y) \,dy \,dx
$$
and more generally for $A \subseteq \R^2$
$$
	P((x,y) \in A) = \int\int_A f_{X,Y}(x,y) \,dy \,dx.
$$

The joint CDF and joint PDF are related by
\begin{eqnarray*}
	f_{X,Y}(x,y) &=& \frac{\D^2}{\Dx \Dy} F_{X,Y}(x,y)\\
	F_{X,Y}(x,y) &=& \int_{-\infty}^x \int_{-\infty}^y \,f(u,v)\, dv \,du.
\end{eqnarray*}

%Given a
%joint PDF $f_{X,Y}(x,y)$ or a joint CDF $F_{X,Y}(x,y)$ we may recover
%the \bfidx{marginal} CDFs $F_X(x)$ and $F_Y(y)$ by
%\begin{eqnarray*}
%	F_X(x) &=& P(X \le x) = P(X \le x, Y < +\infty) \\
%	&=& \int_{-\infty}^{+\infty} \int_{-\infty}^{x}
%		f_{X,Y}(u,v) \,dv \,du \\
%	&=& \lim_{y\to +\infty}\int_{-\infty}^{y} \int_{-\infty}^{x}
%		f_{X,Y}(u,v) \,dv \,du \\
%	&=& \lim_{y \to +\infty} F_{X,Y}(x,y)
%\end{eqnarray*}
%and similarly for $F_Y(y)$.
%That is:
%\begin{itemize}
%\item Given a joint PDF, integrate away one variable.
%\item Given a joint CDF, set one variable to $+\infty$.
%\end{itemize}

Given a joint CDF $F_{X,Y}(x,y)$ we may recover
the \bfidx{marginal} CDFs $F_X(x)$ and $F_Y(y)$ by
$$
	F_X(x) = \lim_{y \to +\infty} F_{X,Y}(x,y)
$$
and similarly for $F_Y(y)$.

How do we recover the \bfidx{marginal} PDFs given the joint PDFs?
To derive the formula, differentiate the CDF:
\begin{eqnarray*}
	f_X(x) &=& \frac{d}{dx} F_X(x)
	= \frac{d}{dx} F_{X,Y}(x,+\infty) \\
%
	&=& \frac{d}{dx} \int_{-\infty}^{+\infty}
		\left[ \int_{-\infty}^x f_{X,Y}(u,v) \,du \right] \,dv \\
	&=& \frac{d}{dx} \int_{-\infty}^{x}
		\left[ \int_{-\infty}^{+\infty} f_{X,Y}(u,v) \,dv \right] \,du \\
	&=& \int_{-\infty}^{+\infty} f_{X,Y}(x,v)\,dv
\end{eqnarray*}
i.e. the formula is
$$
	f_X(x) = \int_{-\infty}^{+\infty} f_{X,Y}(x,y)\,dy.
$$
That is, we \bfidx{integrate away} one variable.

%% ----------------------------------------------------------------
\subsubsection{Independence}

\begin{defn}
\label{defn:indep_crvs}
Two continuous random variables $X$ and $Y$ are \bfidx{independent}
iff their CDFs factor:
$$
	F_{X,Y}(x,y) = F_X(x) F_Y(y).
$$
\end{defn}

\begin{rem}
For discrete random variables, we defined independence (definition
\ref{defn:indep_drvs}) in terms of the factoring of the PMFs; for continuous
random variables, we define independence in terms of the factoring of the CDFs.
Factorization of PDFs does hold (as shown in the following theorem), but it is
a consequence rather than a definition.
\end{rem}

\begin{thm}
Two continuous random variables $X$ and $Y$ are \bfidx{independent}
iff their PDFs factor:
$$
	f_{X,Y}(x,y) = f_X(x) f_Y(y).
$$
\begin{proof}
\begin{eqnarray*}
	%F_{X,Y}(x,y) &=& F_X(x) F_Y(y) \\
	f_{X,Y}(x,y) &=& \frac{\D^2}{\Dx\Dy} F_{X,Y}(x,y) \\
	&=& \frac{\D^2}{\Dx\Dy} \left[F_X(x) F_Y(y)\right] \\
	&=& \frac{\D}{\Dx} \left[F_X(x)\right] \;
		\frac{\D}{\Dy} \left[F_Y(y)\right] \\
	&=& f_X(x) f_Y(y).
\end{eqnarray*}
\end{proof}
\end{thm}

%% ----------------------------------------------------------------
\subsubsection{Expectations}

\begin{thm}[Law of the Unconscious Statistician]
\label{thm:lous_mcrv}
Let\index{Law of the Unconscious Statistician} $X$ and $Y$ be continuous
random variables and $g(x,y):\R^2 \to \R$.  Let $Z=g(X,Y)$.  If
$$
	\int_{-\infty}^{+\infty}
	\int_{-\infty}^{+\infty}
	|g(x,y)| \,f_{X,Y}(x,y) \,dx \,dy < \infty
$$
then
$$
	E[Z] = 
	\int_{-\infty}^{+\infty}
	\int_{-\infty}^{+\infty}
	g(x,y) \,f_{X,Y}(x,y) \,dx \,dy.
$$
\end{thm}

\begin{cor}
Let $X$ and $Y$ be continuous random variables and let $a,b \in \R$.  Then
$$
	E[aX+bY]=aE[X]+bE[Y].
$$
\end{cor}

\begin{thm}
Let $X$ and $Y$ be independent continuous random variables and let
$g,h:\R\to\R$.  Then
$$
	E[g(X)h(Y)] = E[g(X)]E[h(Y)].
$$
\end{thm}

\begin{cor}
Let $X$ and $Y$ be independent continuous random variables.
Then
$$
	E[XY]=E[X]E[Y].
$$
\end{cor}

\begin{cor}
Let $X$ and $Y$ be independent continuous random variables.
Then
$$
	\Var(X+Y)=\Var(X)+\Var(Y).
$$
\begin{proof}
Computation.
\end{proof}
\end{cor}

\begin{rem}
Expectations always add.  They multiply only when $X$ and $Y$ are independent.
Variances add only when $X$ and $Y$ are independent.
\end{rem}

\begin{thm}
Let $X$ and $Y$ be independent random variables and let $g,h: \R \to \R$.  Then
$g(X)$ and $h(Y)$ are independent.
\end{thm}

%% ----------------------------------------------------------------
\subsubsection{The IID paradigm: $S_n$ and $\Xnbar$}
\label{sec:Sn_and_Xnbar}
%
%Run an experiment $n$ times with IID random variables $X_1, \ldots, X_n$.
%Call $X_1=X$.
%
%\begin{defn}
%The \bfidx{sample mean} of $X_1$ through $X_n$ is
%$$
%	\Xnbar = \frac{1}{n} \sum_{i=1}^n X_i.
%$$
%\end{defn}
%
%Then $\Xnbar$ is a new random variable.  It has
%$$
%	E[\Xnbar] = \frac{1}{n} \sum_{i=1}^n E[X_i] = \frac{nE[X]}{n} = E[X] = \mu
%$$
%and
%$$
%	\Var(\Xnbar) = \frac{1}{n^2} \sum_{i=1}^n \Var(X_i)
%	= \frac{n}{n^2} \Var(X) = \frac{\Var(X)}{n}.
%$$

\textbf{Notation:}
Let $X_n$ be a sequence of IID random variables, with common mean
$\mu$ and common variance $\sigma^2$.  We write
$$
	S_n = \sum_{i=1}^n X_n
$$
and
$$
	\Xnbar = \frac{1}{n}\sum_{i=1}^n X_n.
$$
The latter is called the \bfidx{sample mean} of the $X_n$'s.

\textbf{Mean and variance of $S_n$:}
We already know
$$
	E[S_n]
	= E\left[ \sum_{i=1}^n X_i \right]
	= \sum_{i=1}^n E[X_i]
	= n\mu
$$
and (using independence of the trials to split up the variance)
$$
	\Var(S_n)
	= \Var\left(\sum_{i=1}^n X_i\right)
	= \sum_{i=1}^n \Var(X_i)
	= n\sigma^2.
$$

\textbf{Mean and variance of $\Xnbar$:}
Likewise,
$$
	E[\Xnbar]
	= E\left[ \frac{1}{n} \sum_{i=1}^n X_i \right]
	= \frac{1}{n} \sum_{i=1}^n E[X_i]
	= \frac{1}{n} n\mu
	= \mu
$$
and (using independence of the trials to split up the variance)
$$
	\Var(\Xnbar)
	= \Var\left(\frac{1}{n} \sum_{i=1}^n X_i\right)
	= \frac{1}{n^2} \Var\left(\sum_{i=1}^n X_i\right)
	= \frac{1}{n^2} \sum_{i=1}^n \Var(X_i) = \frac{n\sigma^2}{n^2}
	= \frac{\sigma^2}{n}.
$$

%% ----------------------------------------------------------------
\subsubsection{Functions of multiple random variables}

Let $X,Y$ be continuous random variables and let $g(x,y):\R^2 \to \R$.  Let
$Z=g(X,Y)$.  How do we find the PDF of $Z$?  As in the univariate case (section
\ref{sec:fcn_of_crv}), the \bfidx{method} is to first find the CDF of $Z$, then
differentiate.

%[xxx type up the example from 3-21.]
[Need to type up the example from 3-21.]

%[xxx convolution notes for independent $X,Y$ from 3-23.]
[Need to type up convolution notes for independent $X,Y$ from 3-23.]

$$
	f_Z(z) = \int f_X(x) f_Y(z-x) dx.
$$

%% ----------------------------------------------------------------
\subsubsection{Moment-generating functions and characteristic functions}

\begin{defn}
Much as\index{moment-generating function}\index{characteristic function} in the
discrete case (definitions \ref{defns:discrete_MGF_and_CF}),
$$
	M_X(t) = E[e^{tX}] = \int_{-\infty}^{+\infty} e^{tx} f_X(x) dx
$$
and
$$
	\beta_X(t) = E[e^{itX}] = \int_{-\infty}^{+\infty} e^{itx} f_X(x) dx.
$$
\end{defn}

\begin{prop}
We have:
\begin{enumerate}
\item $M_X^{(k)}(0) = E[X^k]$.
\item If $Y=aX+b$, then $M_Y(t) = e^{bt} M_X(at)$.
\item If $X$ and $Y$ are independent, then $M_{X+Y}(t) = M_X(t) M_Y(t)$.
\end{enumerate}
\end{prop}

\begin{ex}
The standard normal random variable $Z$ has (tedious computations omitted here)
moment-generating function
$$
	M_Z(t) = \exp(t^2/2).
$$
The general normal random variable $X=\mu+\sigma Z$ has
moment-generating function
$$
	M_X(t) = \exp(\mu t + \sigma^2 t^2/2).
$$
\end{ex}

\begin{prop}
Let $X_1, \ldots, X_n$ be independent normal random variables
with means $\mu_i$ and variances $\sigma_i^2$.  Then
$Y=\sum X_i$ has normal distribution with mean $\sum \mu_i$
and variance $\sum \sigma_i^2$.
\end{prop}

%% ----------------------------------------------------------------
\subsubsection{Change of variables}

Let\index{change of variables} $X$ and $Y$ be continuous random variables.  If
$T:\R^2\to\R^2$ is invertible, sending $(U,V)=T(X,Y)$, then
$$
	\int_D f(x,y) \,dx \,dy =
	\int_{T(D)} f(x(u,v),y(u,v)) \;|J(u,v)|\; du\,dv
$$
where $J(u,v)$ is the \bfidx{Jacobian matrix}
$$
	J(u,v) = \begin{pmatrix}
		\Dx/\Du & \Dx/\Dv \\
		\Dy/\Du & \Dy/\Dv \\
	\end{pmatrix}.
$$

%xxx this needs an example.

\begin{thm}
Let $X$ and $Y$ be jointly continuous random variables with
PDF $f_{X,Y}(x,y)$.  Let
$$
	D = \{(x,y) : f_{X,Y}(x,y) > 0\}
$$
i.e. the \bfidx{range} of $X,Y$.  Suppose $T:D\to S \subseteq \R^2$ is 1-1 and
onto.  Define new random variables $U$ and $V$ by $(U,V)=T(X,Y)$.  Then
$$
	f_{U,V}(u,v) = \begin{cases}
		f_{X,Y}(x(u,v),y(u,v)) \; |J(u,v)| & \mathrm{ if } (u,v) \in S \\
		0 & \mathrm{otherwise} \\
	\end{cases}
$$
where $J(u,v)$ is as above.
\end{thm}

%% ----------------------------------------------------------------
\subsubsection{Conditional density and expectation}
\label{sec:conditional_expectation}

Given two continuous random variables $X$ and $Y$, we want to define
$P(X|Y=y)$.  Since $Y=y$ is a null event, the usual intersection-over-given
notion of conditional probability (see section \ref{sec:drv_condn_indep}) will
give us zero divided by zero.  Somewhat as in l'H\^opital's rule in calculus,
we can nonetheless make sense of it.

\begin{defn}
Let $X,Y$ be jointly continuous with PDF $f_{X,Y}(x,y)$.  The
\bfidx{conditional density} of $X$ given $Y$ is
$$
	f_{X|Y}(x|y) = \begin{cases}
	\frac{f_{X,Y}(x,y)}{f_Y(y)}, & f_Y(y) \ne 0 \\
	0, & f_Y(y) = 0.
	\end{cases}
$$
\end{defn}

\begin{rem}
Recall that
$$
	f_Y(y) = \int_{x=-\infty}^{x=\infty} f_{X,Y}(x,y) dx
$$
so we can think of the conditional density of $X$ given $Y$ as being
$$
	f_{X|Y}(x|y) = 
	\frac{f_{X,Y}(x,y)}{\int_{x=-\infty}^{x=+\infty} f_{X,Y}(x,y) dx}
$$
whenever the denominator is non-zero.
\end{rem}

\begin{defn}
Let $X,Y$ be jointly continuous with PDF $f_{X,Y}(x,y)$.  The
\bfidx{conditional expectation} of $X$ given $Y$ is
$$
	E[X|Y=y] = \int_{x=-\infty}^{x=+\infty} x\, f_{X|Y}(x|y) \, dx.
$$
\end{defn}

\begin{defn}
$E[X|Y=y]$ is a function of $y$; it must depend only on $y$.  Call it $g(y)$.
Then $g(Y)$ is a random variable, which we write as
$$
	E[X|Y].
$$
\end{defn}

This new random variable has the following properties.

\begin{thm}
Let $X,Y,Z$ be random variables, $a,b \in \R$, and $g:\R \to \R$.
Then
\begin{itemize}
\item $E[a|Y] = a$.
\item $E[aX+bZ|Y] = eE[X|Y]+bE[Z|Y]$.  (Note:  this is linearity on the
	left; linearity on the right emphatically does \emph{not} hold.)
\item If $X \ge 0$ then $E[X|Y] \ge 0$.
\item If $X,Y$ are independent then $E[X|Y] = E[X]$.
	(Mnemonic:  $Y$ gives no information about $X$.)
\item $E[E[X|Y]]=E[X]$.  (This is the partition theorem in disguise.
	See below.)
\item $E[Xg(Y)|Y]=g(Y)E[X|Y]$.  (Mnemonic:  given a specific $y$, $g(y)$ is
	constant.)
\item Special case:  $E[g(Y)|Y]=g(Y)$.
\end{itemize}
\end{thm}

%xxx type up example from 4-25 notes.

%% ----------------------------------------------------------------
\subsubsection{The bivariate normal distribution}

If $X$ and $Y$ are independent and standard normal, then their joint
PDF is
$$
	f_{X,Y}(x,y) = \frac{1}{2\pi} \exp\left(-\frac{x^2+y^2}{2}\right).
	\qquad \qquad \qquad (*)
$$
It is possible for $X$ and $Y$ to \emph{not} be independent, while their
marginals \emph{are} still standard normal.  In fact, there is a 1-parameter
family of such $X,Y$ pairs.

\begin{defn}
Let $-1 < \rho < 1$.  The \bfidx{bivariate normal distribution} with
parameter $\rho$ has PDF
$$
	f_{X,Y}(x,y) \frac{1}{2\pi\sqrt{1-\rho^2}}
	\exp\left(
	-\frac{x^2-2\rho xy + y^2}{2(1-\rho^2}
	\right).
$$
\end{defn}

\begin{rem}
Note the following:
\begin{itemize}
\item It is straightforward but tedious to verify that $\int\int
f_{X,Y}(x,y)=1$.

\item With $\rho=0$ we obtain equation (*) as a special case.

\item One may complete the square and use translation invariance of the
integral to find that the marginals are in fact univariate standard normals.

\item Again completing the square, one finds that $f_{Y|X}(y|x)$
is normal with $\mu=\rho x$ and $\sigma^2 = 1-\rho^2$.

\end{itemize}
\end{rem}

%% ----------------------------------------------------------------
\subsubsection{Covariance and correlation}

\begin{defn}
Let $X$ and $Y$ be random variables with means $\mu_X$ and $\mu_Y$,
respectively.  The \bfidx{covariance} of $X$ and $Y$ is
$$
	\Cov(X,Y) = E[(X-\mu_X)(Y-\mu_Y)] = E[XY] = E[XY]-E[X]E[Y].
$$
\end{defn}

\begin{mnem}
With $Y=X$ we recover the familiar formula (definition \ref{defn:var}) for the
variance of $X$: $E[X^2]-E[X]^2$.
\end{mnem}

\begin{thm}
Let $X$ and $Y$ be random variables.  Then
$$
	\Var(X+Y) = \Var(X) + 2 \Cov(X,Y) + \Var(Y).
$$
\end{thm}

\begin{rem}
Bill Faris calls this the ``most important theorem in probability''.
\end{rem}

\begin{cor}
If $\Cov(X,Y)=0$ then $\Var(X+Y)=\Var(X)+\Var(Y)$.
\end{cor}

\begin{thm}
If $X$ and $Y$ are independent then $\Cov(X,Y)=0$.  The converse does not
hold.
\end{thm}

\begin{defn}
Let $X$ and $Y$ be random variables with variances $\sigma_X^2$ and
$\sigma_Y^2$, respectively.
The \bfidx{correlation coefficient} of $X$ and $Y$ is
$$
	\rho(X,Y) = \frac{\Cov(X,Y)}{\sigma_X \sigma_Y}.
$$
\end{defn}

\begin{rem}
The covariance is quadratic in $X$ and $Y$ (with respect to linear rescaling);
the correlation coefficient is scale-invariant.
\end{rem}

\begin{thm}
The correlation coefficient satisfies
$$
	-1 \le \rho(X,Y) \le 1.
$$

\begin{rem}
Equivalently\index{covariance}\index{variance},
$$
	\Cov(X,Y)^2 \le \Var(X) \Var(Y).
$$
\end{rem}

\begin{proof}
It suffices to show $|\rho(X,Y)| \le 1$, which is equivalent to showing
$|\Cov(X,Y)| \le \sigma_X \sigma_Y$.

This follows abstractly from the \plainidx{Cauchy-Schwarz inequality},
\begin{align*}
	|\langle f, g \rangle| &\le \|f\|\,\|g\|,
\end{align*}
with $f=X-\mu_X$ and $g=Y-\mu_Y$.  Namely,
\begin{align*}
	\langle f, g \rangle^2 &\le \|f\|^2\,\|g\|^2
		= \langle f,f \rangle \langle g,g \rangle \\
	\left( \int_\Omega (X-\mu_X)(Y-\mu_Y) \,dP \right)^2 &\le
		\int_\Omega (X-\mu_X)^2 \,dP \int_\Omega (Y-\mu_Y)^2 \,dP \\
	E[(X-\mu_X)(Y-\mu_Y)]^2 &\le 
		E[(X-\mu_X)^2]\,E[(Y-\mu_Y)^2] \\
	\Cov(X,Y)^2 &\le \Var(X) \Var(Y).
\end{align*}

Faris sketches another route, which I complete here.
\bfidxtwo{Normalize}{normalize} $X$ and $Y$ as follows.  Let $\mu_X$, $\mu_Y$,
$\sigma_X$, and $\sigma_Y$ be their means and standard deviations,
respectively.  Then
$$
	\frac{X-\mu_X}{\sigma_X} \qand
	\frac{Y-\mu_Y}{\sigma_Y}
$$
each have zero mean and unit standard deviation.  (In particular this will
mean, below, that their second moments are 1.) We can create a new pair of
random variables
$$
	\left(\frac{X-\mu_X}{\sigma_X} \; \pm \;
	\frac{Y-\mu_Y}{\sigma_Y}\right)^2.
$$
Since each takes non-negative values, the means are non-negative as well [xxx
xref forward to where this is proved \ldots it seems obvious but actually
requires proof]:
$$
	E \left[\left(\frac{X-\mu_X}{\sigma_X} \; \pm \;
	\frac{Y-\mu_Y}{\sigma_Y}\right)^2\right] \ge 0.
$$
FOILing out we have
$$
	E \left[
		\left(\frac{X-\mu_X}{\sigma_X}\right)^2
		\; \pm \;
		\frac{2 (X-\mu_X)(Y-\mu_Y)}{\sigma_X\sigma_Y}
		+
		\left(\frac{Y-\mu_Y}{\sigma_Y}\right)^2
	\right] \ge 0.
$$
Using the linearity of expectation and recalling that the normalized variables
have second moments equal to 1, we have
\begin{eqnarray*}
	2 \;\pm\; 2E\left[\frac{(X-\mu_X)(Y-\mu_Y)}{\sigma_X\sigma_Y}\right]&\ge&0\\
	-1 \le E\left[\frac{(X-\mu_X)(Y-\mu_Y)}{\sigma_X\sigma_Y}\right] &\le& 1\\
	-\sigma_X\sigma_Y \le
		E\left[(X-\mu_X)(Y-\mu_Y)\right] &\le&
		\sigma_X\sigma_Y \\
	-\sigma_X\sigma_Y \le \Cov(X,Y) &\le& \sigma_X\sigma_Y \\
	|\Cov(X,Y)| &\le& \sigma_X\sigma_Y.
\end{eqnarray*}
\end{proof}
\end{thm}

%% ================================================================
\newpage
\subsection{Laws of averages}

Here is a statistics paradigm.  Run an experiment $n$ with IID random variables
$X_n$ (whether continuous or discrete).  The $n$-tuple $(X_1,\ldots,X_n)$ is
called a \bfidx{sample}.  The average of $X_1$ through $X_n$ is called the
\bfidx{sample mean}, written $\Xnbar$; it is also a random variable.

The big question is: what does $\Xnbar$ look like as $n$ gets large?  For
example, roll a 6-sided die (so $\mu=3.5$) a million times.  What is the
probability of the event $|\Xnbar - 3.5| > 0.01$?  One would hope this
probability would be small, and would get smaller as $n$ increases.

We have two main theorems here:
\begin{itemize}
\item The law of large numbers says that $\Xnbar \to \mu$, although we need
	to define the notion of convergence of a random variable to a real number.
	There are two flavors of convergence:  weak and strong.
\item The central limit theorem describes the PDF of $\Xnbar$.
\end{itemize}

%% ----------------------------------------------------------------
\subsubsection{The weak law of large numbers}

\begin{defn}
Let $X_n$ and $X$ be random variables.  We say $X_n \to X$ \bfidx{in
probability}\index{convergence in probability} if for all $\veps > 0$,
$$
	\lim_{n\to\infty} P\left(\left\{
		\omega \in \Omega:
		|X_n(\omega)-X(\omega)| \ge \veps
		\right\}\right) = 0.
$$
More tersely, we may write
$$
	P(|X_n-X| \ge \veps) \to 0
	\qqor
	P(|X_n-X| < \veps) \to 1.
$$
\end{defn}

\begin{thm}[Weak law of large numbers]
Let\index{law of large numbers, weak}\index{weak law of large numbers} $X_n$ be
an IID sequence with common mean $\mu$ and finite variance $\sigma^2$.  Then
$$
	\Xnbar = \frac{1}{n} \sum_{i=1}^n X_i \to \mu
$$
in probability.
\end{thm}

Here is another notion of convergence.

\begin{defn}
Let $X_n$ and $X$ be random variables.  We say $X_n \to X$
\bfidx{in mean square}\index{convergence in mean square} if
$$
	E[(X_n-X)^2] \to 0.
$$
\end{defn}

\begin{thm}[Chebyshev's inequality]
Let\index{Chebyshev's inequality} $X$ be a random variable with finite
variance.  Let $a>0$.  Then
$$
	%P(|X|\ge a) \le \frac{1}{a^2}E[X^2].
	P(|X-\mu|\ge a) \le \frac{ E[(X-\mu)^2] }{a^2}
$$
\begin{rem}
This means
$$
	P(|X-\mu|\ge a) \le \frac{\Var(X)}{a^2}.
$$
\end{rem}
\begin{proof}
Use the partition theorem with two partitions on some as-yet-unspecified
event $A$:
$$
	E[(X-\mu)^2]
	= E\left[(X-\mu)^2 \,\Big|\, A\right] P(A)
	\;+\; E\left[(X-\mu)^2 \,\Big|\, A^c\right] P(A^c).
$$
Regardless of what $A$ is, the last term is non-negative.  So we have
$$
	E[(X-\mu)^2]
	\;\ge\; E\left[(X-\mu)^2 \,\Big|\, A\right] P(A).
$$
Now let $A$ be the particular event that $|X-\mu| \ge a$.  Then we have
\begin{eqnarray*}
	E[(X-\mu)^2]
	&\ge& E\left[(X-\mu)^2 \,\Big|\, |X-\mu|\ge a\right] P(|X-\mu|\ge a) \\
	&=& E\left[(X-\mu)^2 \,\Big|\, (X-\mu)^2\ge a^2\right] P(|X-\mu|\ge a) \\
	&\ge& a^2 P(|X-\mu|\ge a).
\end{eqnarray*}
Dividing through by $a^2$ we have
$$
	P(|X-\mu|\ge a) \le \frac{E[(X-\mu)^2]}{a^2}
$$
as desired.
\end{proof}
\end{thm}

\begin{thm}
Convergence in mean square implies convergence in probability.
\begin{proof}
Let $\veps > 0$.  We need to show $P(|X_n-X|>\veps) \to 0$.
By Chebyshev's inequality,
$$
	P(|X_n-X|>\veps) \ge \frac{1}{\veps^2} E[(X_n-X)^2].
$$
\end{proof}
\end{thm}

\begin{rem}
Notes about Chebyshev's inequality:
\begin{itemize}
\item It is used in the proof of the weak law, which I am omitting.
\item The bounds provided by Chebyshev's inequality are rather loose, but
	they are certain.  The central limit theorem gives tighter bounds,
	but only probabilistically.
\end{itemize}
\end{rem}

%% ----------------------------------------------------------------
\subsubsection{The strong law of large numbers}

Here is a third notion of convergence.

\begin{defn}
We say $X_n \to X$ \bfidx{with probability one} (w.p. 1) or \bfidx{almost
surely} (a.s.) if
$$
	P\left(\left\{
		\omega \in \Omega: \lim_{n\to\infty} X_n(\omega) = X(\omega)
	\right\}\right) = 1.
$$
More tersely, we may write
$$
	P(X_n \to X) = 1.
$$
\end{defn}

\begin{thm}[Strong law of large numbers]
Let\index{law of large numbers, strong}\index{strong law of large numbers}
$X_n$ be an IID sequence with common mean $\mu$.  Then $\Xnbar \to \mu$ with
probability 1.
\end{thm}

\begin{thm}
$X_n\to X$ w.p. 1 implies $X_n \to X$ in probability.
\end{thm}

\begin{rem}
This means the strong law is stronger than the weak law.
\end{rem}

%% ----------------------------------------------------------------
\subsubsection{The central limit theorem}
\label{sec:CLT}

\begin{motivn*}
Let $X_n$ be an IID sequence and let $S_n = \sum X_n$.  We know from section
\ref{sec:Sn_and_Xnbar} that $E[S_n]=n\mu$ and $\Var(S_n) = n\sigma^2$.  We
expect the PDF of $S_n$ to be centered at $n\mu$ with width approximately
$\sqrt{n} \sigma$.  Likewise, if $\Xnbar=\sum X_n/n$ then we know that
$E[\Xnbar]=\mu$ and $\Var(\Xnbar) = \sigma^2/n$.  We expect the PDF of $S_n$ to
be centered at $n\mu$ with width approximately $\sigma/\sqrt{n}$.  For various
distributions, one finds empirically that these PDFs look approximately normal
if $n$ is large.
\end{motivn*}

\begin{defn}
\label{defn:stdizn}
Let $X$ be a random variable with mean $\mu$ and variance $\sigma^2$.  The
\bfidx{standardization} or \bfidx{normalization} of $X$ is
$$
	\frac{X-\mu}{\sigma}.
$$
\end{defn}

In particular, if we standardize $S_n$, we get
$$
	Z_n = \frac{S_n-n\mu}{\sigma\sqrt{n}}
$$
with mean 0 and variance 1:
$$
	\Var(Z_n) = \frac{1}{\sigma^2 n} \Var(S_n-n\mu)
	= \frac{1}{\sigma^2 n} \Var(S_n) = \frac{n\sigma^2}{n\sigma^2} = 1.
$$

Likewise, if we standardize $\Xnbar$, we get
$$
	\frac{\Xnbar - \mu}{\sigma\sqrt{n}}.
$$

The \bfidx{central limit theorem} says that the standardizations of $S_n$ and
$\Xnbar$ both approach standard normal for large $n$.

\begin{defn}
Let $\Phi(x)$ be the CDF of the standard normal:
$$
	\Phi(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{+\infty}
		e^{-x^2/2}dx.
$$
\end{defn}

\begin{thm}
Let $X_n$ be an IID sequence with finite mean $\mu$ and finite non-zero
variance $\sigma^2$.  Let $Z_n$ be the standardization of $S_n$ as above.
Then
$$
	P(Z_n \le x) \to \Phi(x)
$$
for all $x$.
\end{thm}

\begin{rem}
This convergence is called \bfidx{convergence in distribution}\index{in
distribution}.
\end{rem}

xxx include some examples here.

%% ----------------------------------------------------------------
\subsubsection{Confidence intervals}
\label{sec:confidence_intervals}

Here is an application of the Central Limit Theorem to statistics.  The
\bfidx{population} is a random variable $X$.  A \bfidx{sample} of size $n$ is
$n$ IID copies of $X$.  The random variable $X$ has a (true) \bfidx{population
mean} $\mu_X$ but we do not know what it is; all we have is the \bfidx{sample
mean} $\Xnbar = \sum_{k=1}^n X_k/n$, which is an estimate of the population
mean.  We would like to put some error bars on this estimate.

We quantify this problem using the notion of \bfidx{confidence intervals}.  We
look for $\veps > 0$ such that
$$
	P\left(|\Xnbar-\mu_X| \ge \veps\right) = 0.05
$$
or, alternatively,
$$
	P\left(|\Xnbar-\mu_X| < \veps\right) = 0.95.
$$
(Five percent is a conventional value in statistics.)

Using the CLT, we treat $\Xnbar$ as being approximately normal.  We standardize
it (statisticians call this\index{$z$-score} \emph{taking the $z$-score})
in the usual way:
$$
	Z = \frac{\Xnbar - \mu_\Xnbar}{\sigma_\Xnbar}
	= \frac{\Xnbar - \mu_X}{\sigma_X/\sqrt{n}}.
$$
Then
\begin{align*}
	P(|\Xnbar-\mu_X|\ge \veps) &= P\left(|\Xnbar-\mu_X|\ge \veps\right) \\
	&= P\left(\frac{|\Xnbar-\mu_X|}{\sigma_X/\sqrt{n}}
		\ge \frac{\veps}{\sqrt n}\right) \\
	&\approx P\left(Z \ge \frac{\veps}{\sqrt n}\right) = 0.05.
\end{align*}
It's worth memorizing (or you can compute it if you prefer) that the standard
normal curve has area 0.95 for $Z$ running from $-1.96$ to $+1.96$.  So,
$\veps/(\sigma_X/\sqrt{n})$ should be 1.96.  Solving for $\veps$ in terms of
$n$ gives
$$
	\veps = \frac{1.96\sigma_X}{\sqrt{n}}.
$$
Note that this requires the population standard deviation to be known.  (We can
compute the sample standard deviation and use that as an estimate of the
population standard deviation $\sigma_X$, but we've not developed any theory as
to the error in \emph{that} estimate.)

\beginex
Let $X$ have the Bernoulli distribution with parameter $p$ --- flip a coin with
probability $p$ of heads; assign the value 0 to tails and 1 to heads.  Recall
from section \ref{sec:drv_catalog} that $X$ has mean $p$.  (In section
\ref{sec:drv_catalog} we took tails to be 1; I have changed the convention.)
Suppose you flip the coin 1000 times (i.e. $n=1000$) and obtain 520 heads.
Then $\Xnbar = 0.520$.  Then
$$
	\veps = \frac{1.96\sqrt{p(1-p)}}{\sqrt{1000}} \approx 0.0619 \sqrt{p(1-p)}.
$$
For $p=0.5$, $\veps\approx 0.031$.  Thus we are 95\% certain that $\mu_X$ is
within $0.031$ on either side of $0.520$, i.e. between $0.489$ and $0.551$.
\mendex

%% ================================================================
\newpage
\subsection{Stochastic processes}

xxx Examples:

\begin{itemize}
\item Sequence of die rolls (independent).
\item Sequence of die tips (non-independent but Markov).
\item Sequence of coin flips (independent).
\item Sum of coin flips (Martingale).
\end{itemize}

%% ----------------------------------------------------------------
\subsubsection{Die tips}
\label{sec:die_tips}

%% ----------------------------------------------------------------
\subsubsection{Coin flips}
\label{sec:sum_of_coin_flips}

$$
	\Omega = \{1,-1\}^\infty, \qquad
	X_n = \omega_n \qquad
	S_n = \sum_{j=1}^n X_j.
$$

$n=3$:
$$
\begin{tabular}{|r||r|r|r|r|}
\hline    $k$ &  $0$ &  $1$ & $2$ & $3$ \\
\hline $2k-n$ & $-3$ & $-1$ & $1$ & $3$ \\
\hline
\end{tabular}
$$

$$
	P(S_n=2k-n) = {n \choose k} p^k (1-p)^{n-k}.
$$

%% ----------------------------------------------------------------
\subsubsection{Filtrations}
\label{sec:filtrations}

Show the filtration tree (refinement of partitions of $\Omega$) for the sum of
coin flips.

Have done sigma of finite generating set; show the size is $2^{2^n}$.

%% ----------------------------------------------------------------
\subsubsection{Markov processes}

Homogeneous (die tips).

Non-homogeneous (sum of coin flips).

xref back to the partition theorem.

Key point:  PMFs which evolve in time.

Show some matrix products for the sum of coin flips.

%% ----------------------------------------------------------------
\subsubsection{Martingales}

Sum of coin flips.

sub and super and at, depending on $p$.

% Elementary explicit counterexamples:
%
% 1. The process dX_t = (\int_0^t X_s ds) dW_t is a martingale but is not
%    Markov.
%
% 2. The process dX_t = a dt + \sigma dW_t is Markov but is not a martingale.
%
% In the equations above, W_t denotes Brownian motion. 

% ---> Find something much more elementary.

% X_n is Markov but not a martingale.
