\documentclass[11pt]{article}
\usepackage{latex-macros/course}
\setlength{\itemsep}{0 cm}
%\setlength{\topmargin}{0.5in}
%\setlength{\headsep}{1cm}

\begin{document}
\paper{finapp}{}{Final Exam Appendix}

\tableofcontents
\newpage

\section{Induction and Least Number Inference Rules}

\begin{rul*}[Induction]
\Rule{P(0), \quad \forall m \in \naturals\; [P(m) \implies P(m+1)]}
{\forall n \in \naturals\ P(n).}
\end{rul*}

\begin{rul*}[Strong Induction]
\Rule{P(0), \quad \forall n \in \naturals\ [[\forall m \le n\ P(m)] \implies
P(n+1)]}
{\forall n \in \naturals\ P(n)}
\end{rul*}

\begin{rul*}[Least Number Principle]
\Rule{\exists n \in \naturals\ P(n)}
{\exists m \in \naturals\ [P(m) \land \forall n \in \naturals\ [P(n)
\implies m \leq n]]}
\end{rul*}

\section{Functions}

A function, $f:A \to B$, is an \emph{injection} iff $f(a_1)=f(a_2)$
implies $a_1=a_2$, for all $a_1,a_2 \in A$.

It is a \emph{surjection} iff $\forall b \in B\; \exists a \in A, f(a)=b$.

It is a \emph{bijection} iff it is both an injection and a surjection.

\section{Relations}
\subsection{Equivalence}

A binary relation, $R$, on a set $A$ is
\begin{itemize}
\item \emph{reflexive} iff $\forall x \in A (xRx)$.
\item \emph{symmetric} iff $\forall x,y \in A(xRy \implies yRx)$.
\item \emph{transitive} iff $\forall x, y, z \in A(xRy \land yRz \implies xRz)$.
\end{itemize}

$R$ is an \emph{equivalence relation} iff it is reflexive, symmetric and
transitive.

\subsection{Partial Order}
A binary relation, $R$, on a set $A$ is

\begin{itemize}
\item \emph{anti-symmetric} iff $xRy \land yRx \implies x = y$.
\item a \emph{partial order} iff it is transitive and
anti-symmetric.  
\item a \emph{total order} iff it is a partial order and for all
$x \neq y \in A$ either $x R y$ or $yRx$.
\end{itemize}

If $R$ is a partial order, then the set $A$ is called a \emph{partially
ordered set (poset)}.  In this case,
\begin{itemize}
\item $a$ is a \emph{minimal element} of $A$ if $\neg\exists b\in A [b R a\wedge b\neq a]$
\item $a$ is a \emph{maximal element} of $A$ if $\neg\exists b\in A [aR b\wedge b\neq a]$
\item a subset of $A$ is a \emph{chain} iff it is totally ordered by $R$.
\item elements $a_1,a_2 \in A$ are \emph{incomparable} iff neither
$a_1Ra_2$ nor $a_2Ra_1$ holds.
\item a subset of $A$ is an \emph{anti-chain} iff its elements are
pairwise incomparable.
\end{itemize}

\subsection{Operations}

The \emph{identity relation}, $\ident{A}$, on a set, $A$, is
\[
\ident{A} \eqdef \set{(a,a) \suchthat a \in A}.
\]

If $R \subseteq A \times B$, then, $R^{-1}$, the \emph{inverse of
$R$}, is the relation on $B\times A$ given by
\[
R^{-1} \eqdef \set{(b,a) \suchthat (a,b) \in R}.
\]

The \emph{composition} of relations $R_1 \subseteq A \times B$ and $R_2
\subseteq B \times C$ is the relation $R_2 \compose R_1 \subseteq A \cross C$
given by
\begin{displaymath}
  R_2 \compose R_1 \eqdef \set{(a,c) \suchthat
  \exists b\ (a,b) \in R_1 \wedge (b,c) \in R_2}.
\end{displaymath}

A \emph{path from $a_0$ to $a_k$} in a relation $R \subseteq A \cross A$
is a sequence $a_0,\dots,a_k$ with $k \ge 0$ such that $(a_i,a_{i+1}) \in
R$ for every $i < k$.  The \emph{length} of the path is $k$.
For $n \in \naturals$,
\[
R^n \eqdef
\begin{cases}
\ident{A} & \mathrm{if}\ n=0,\\
R^{n-1} \compose R & \mathrm{if}\ n>0.
\end{cases}
\]

\begin{lemma*}
$R^n = \set{(a,b) \suchthat
\exists \mbox{ a length $n$ path from $a$ to $b$ in $R$}}$.
\end{lemma*}


\iffalse
\subsection{Relation Closures}

The \emph{closure} of relation $R$ with respect to property $P$ is the relation
$S$ that 
\begin{enumerate}
\item\label{contains} contains $R$, 
\item\label{P} has property $P$, and 
\item  is contained in \emph{any} relation satisfying (\ref{contains}) and
(\ref{P}).  That is, $S$ is the ``smallest''relation satisfying
(\ref{contains}) and (\ref{P}).
\end{enumerate}
\fi

For $R \subseteq A \cross A$,
\begin{itemize}
\item The \emph{reflexive closure} of $R$ is $R \cup \ident{A}$.\\
\item The \emph{symmetric closure} of $R$ is $R \union R^{-1}$.
\item The \emph{transitive closure}, $R^{+}$, of $R$ is
\[
R^{+} \eqdef \bigcup_{n=1}^\infty R^n.
\]
\item The \emph{reflexive, transitive closure}, $R^*$, (also called the \emph
{connectivity relation}) of $R$ is
\[
R^* \eqdef \bigcup_{n=0}^\infty R^n = R^{+} \union \ident{A}.
\]
\end{itemize}

\begin{lemma*}
If $A$ is finite, then $R^* = (R\union \ident{A})^{\card{A}}$.
\end{lemma*}


\subsection{Dilworth Theorem}

\begin{theorem*}
If $(A, R)$ is a finite poset with longest chain of length $t$, then $A$
can be partitioned into $t$ antichains.
\end{theorem*}

\begin{theorem*}[Dilworth]
For all $t$, every poset with $n$ elements must have either a chain
of size greater than $t$ or an antichain of size at least $n / t$.
\end{theorem*}


\section{Graphs}

\subsection{Edges, Paths \& Cycles}

A \emph{simple graph} $G$ is a pair $(V, E)$ where $V$ is an arbitrary
nonempty set whose elements are called \emph{vertices} or \emph{nodes},
and $E$ is a set of \emph{simple edges} on $V$.  A \emph{simple edge} on
$V$ is a set of two vertices.

\begin{theorem*}
The sum of the degrees of the vertices in a simple graph equals twice the
number of edges.
\end{theorem*}

\begin{theorem*}[Handshake]
In every graph, there are an even number of vertices of odd degree.
\end{theorem*}

Two vertices $u,v \in V$ are \emph{adjacent} iff there is an edge of $G$
between them, \viz $\set{u,v} \in E$.

A \emph{path} in $G$ is any sequence $v_0, v_1, \dots, v_n$ of $n \geq 0$
vertices such that $v_i$ and $v_{i+1}$ are adjacent for $0 \leq i < n$.
The \emph{length} of the path is defined to be $n$.  The path is
\emph{simple} if $v_i \neq v_j$ for $0 \leq i < j \leq n$.

A \emph{cycle} is a path that begins and ends at the same vertex.

Two vertices $u,v \in V$ are \emph{connected} iff there is a path between
them, \ie $v_0=u$ and $v_n = v$.

\subsection{Complete \& Connected Graphs}

$G$ is \emph{complete} iff every two vertices are adjacent.

$G$ is \emph{connected} iff every two vertices is connected.

A subset, $C$, of vertices is a \emph{connected component} of $G$ iff
there is a vertex, $v \in C$, such that $C$ is the set of vertices
connected to $v$.  So $G$ is connected iff it has exactly one connected
component.

\subsection{Euler and Hamiltonian Paths}
Let $G$ be an undirected graph.  An \emph{Euler path} in $G$ is a path
that traverses every edge of $G$ exactly once.  A \emph{Hamiltonian path}
is a simple path that includes every vertex.

\begin{theorem*}
$G$ has an Euler cycle iff $G$ is finite, connected, and every vertex has
even degree.
\end{theorem*}


\subsection{Common graphs}

The \emph{empty graph} or \emph{anticlique}, $A_n$, on $n$ vertices is the
graph $A_n \eqdef (\set{v_1, v_2, \dots, v_n},\emptyset)$.

The \emph{line graph}, $L_n$, on $n$ vertices is the graph $L_n \eqdef
(\set{v_1, v_2, \dots, v_n}, \set{\set{v_1,v_2}, \set{v_2,v_3}, \dots,
\set{v_{n-1},v_n}})$.

The \emph{cycle graph}, $C_n$, on $n$ vertices is $L_n$ plus the edge
$\set{v_n,v_1}$.

The \emph{wheel}, $W_n$, on $n \geq 4$ vertices is the graph consisting of
$C_{n-1}$ plus one additional vertex connected to all the other vertices.

The \emph{complete graph} or \emph{clique}, $K_n$, on $n$ vertices has an
edge between every pair of vertices.

\subsection{Trees}

A \emph{tree} is a (possibly infinite) simple graph $G=(V,E)$, such that
any of these equivalent conditions hold:
\begin{itemize}
\item $G$ is connected, but removing any edge from $G$ leaves a
      disconnected graph.
\item $G$ is connected and acyclic.
\item There is a unique simple path between any two distinct vertices of $G$.
\end{itemize}
In addition, if $\card{V}$ is finite, then another equivalent condition is
\begin{itemize}
\item $G$ is connected and $\card{E} = \card{V}-1$.
\end{itemize}

A \emph{rooted tree} is a tree $T$ together with a distinguished node,
$r$, called the \emph{root} of $T$.

A rooted tree is called \emph{finite-path} iff it has no infinite paths
away from the root.

\subsection{Colorings}

A \emph{$k$-coloring} of $G$ is mapping from $V$ to a $k$-element
set, whose element are called \emph{colors}, such that no two
adjacent vertices are mapped to the same color.  $G$ is
\emph{$k$-colorable} iff it has a $k$-coloring.  $G$ is
\emph{bipartite} if it is $2$-colorable.  The \emph{chromatic number}
of $G$ is the smallest $k$ such that $G$ is $k$-colorable.

\subsection{Hall's Theorem}

\begin{definition*}
A \emph{bipartite graph}, $G = (V_1,V_2,E)$, is a simple graph whose
vertices are the disjoint union of $V_1$ and $V_2$ and whose edges go
between $V_1$ and $V_2$, \viz
\[
E \subseteq \set{ \set{v_1,v_2} \suchthat v_1 \in V_1 \text{ and } v_2 \in
V_2}.
\]
A \emph{perfect matching} in $G$ is an injection $f:V_1 \to V_2$ such that
$\set{v, f(v)} \in E$ for all $v \in V_1$.

For any set, $A$, of vertices, define the neighbor set,
\[
N(A) \eqdef \set{v \suchthat \exists a \in A\ \set{a,v} \in E}.
\]
A set $A \subseteq V_1$ is called a \emph{bottleneck} if $\card{A} >
\card{N(A)}$.
\end{definition*}

\begin{theorem*}
[Hall] A bipartite graph has a perfect matching iff it has no bottlenecks.
\end{theorem*}

\subsection{Directed Graphs}
A \emph{directed graph} or \emph{digraph} are defined in the same way as
undirected graphs, except that edges are \emph{ordered} pairs of vertices
instead of an (unordered) set of two vertices.  The definitions of
\emph{directed paths}, \etc carry over straightforwardly from the
undirected case, but now successive vertices in the path must be connected
by a directed edge from each vertex to the next one in the path.

\section{State Machines \& Invariants}

A \emph{state machine} has three parts:
\begin{enumerate}
\item a nonempty set, $Q$, whose elements are called \emph{states},
\item a nonempty subset $Q_0 \subseteq Q$, called the set of \emph{start states},
\item a binary relation, $\delta$, on $Q$, called the \emph{transition
relation}.
\end{enumerate}

An \emph{invariant} for a state machine is a predicate, $P$, on states,
such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$
for some state, $r$, then $P(r)$ holds.

\begin{theorem*}[Invariant Theorem]
Let $P$ be an invariant predicate for a state machine.  If $P$ holds for
all start states, then $P$ holds for all reachable states.
\end{theorem*}


A \emph{derived variable} is a function with domain $Q$.  If $f : Q \to P$
is a derived variable with partially ordered codomain, $(P,\preceq)$, then
$f$ is \emph{strictly decreasing} iff
\[
q \rightarrow q' \text{  implies  } f(q') \prec f(q),
\]
and $f$ is \emph{weakly decreasing} iff
\[
q \rightarrow q' \text{  implies  } f(q') \preceq f(q).
\]

\begin{theorem*}
If $f : Q \to \naturals$ is a strictly decreasing derived variable of a
state machine, then the length of any execution starting at a start state
$q$ is at most $f(q)$.
\end{theorem*}

\section{Well-founded Partial Orders}

\def\lexle{\mathrel{\preceq_{\text{lex}}}}
\def\lex<{\mathrel{\prec_{\text{lex}}}}
\def\coordle{\mathrel{\preceq_{\text{c}}}}
\def\coord<{\mathrel{\prec_{\text{c}}}}

If $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are posets, then the
\emph{lexicographic partial order}, $\lexle$, on $P_1 \cross P_2$ is
defined by the condition that
\begin{equation*}
(p_1,p_2) \lexle (q_1,q_2) \ \eqdef\quad p_1 \prec_1 q_1\text{ or
}(p_1=q_1 \land p_2 \preceq_2 q_2).
\end{equation*}

The \emph{coordinatewise partial order}, $\coordle$, on $P_1
\cross P_2$ is defined by the condition that
\begin{equation*}
(p_1,p_2) \coordle (q_1,q_2) \ \eqdef\quad (p_1 \preceq_1 q_1 \land p_2
\preceq_2 q_2).
\end{equation*}

A poset $(P,\preceq)$ is \emph{well-founded} iff every nonempty subset $S
\subseteq P$ has a \emph{minimal element}.

\begin{lemma*}
Suppose $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are posets.  Then
\begin{enumerate}

\item so are $(P_1 \cross P_2,\lexle)$ and $(P_1 \cross
P_2,\coordle)$.  Moreover,

\item if $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are both
well-founded, then so are $(P_1 \cross P_2,\lexle)$ and $(P_1 \cross
P_2,\coordle)$.

\item if $(P_1, \preceq_1)$ and $(P_2, \preceq_2)$ are both totally
ordered, then so is $(P_1 \cross P_2,\lexle)$.
\end{enumerate}
\end{lemma*}

\begin{lemma*}
A poset is well-founded iff it has no infinite decreasing chain.
\end{lemma*}

\begin{theorem*}
[Fundamental Theorem for two-person games of perfect information]
For games in which every play is finite and ends in win or lose, there is
a winning strategy for one of the players.
\end{theorem*}

\section{Summations and Asymptotic Notation}
\subsection{Summation Formulae}
\begin{eqnarray*}
\sum_{i=0}^{n} i^2 & = & \frac{n(n+1)(2n+1)}{6}\\
\sum_{i=0}^{n} x^i & = & \frac{1- x^{n+1}}{1 - x}\\
\sum_{i=0}^{\infty} x^i & = & \frac{1}{1-x}\\
\sum_{i=1}^{n} i x^i & = & \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}\\
\sum_{i=1}^{\infty} i x^i & = & \frac{x}{(1-x)^2}\\
\sum_{i=1}^\infty{i^2x^i} & = & \frac{x(1+x)}{(1-x)^3}\\
e^x & = & 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots\\
1 + x & \leq & e^x \quad\quad \text{for all real $x$}\\
H_n & \eqdef & \sum_{i=1}^n \frac{1}{i} \quad\quad \text{(Harmonic Numbers)}\\
H_n &\sim& \ln n
\end{eqnarray*}

\subsection{Asymptotics}
For functions $f,g:\reals\to\reals$, we say 

\begin{itemize}
\item 
$f \sim g$, or $f$ is asymptotically equal to $g$, iff
$\lim_{x \rightarrow \infty} f(x)/g(x) = 1$
\item
$f(x) = o(g(x))$, or $f$ is asymptotically smaller than $g$, iff
$\lim_{x \rightarrow \infty} f(x)/g(x) = 0$
\item
with $g$ nonnegative, we say that
\footnote{$\limsup_{x \rightarrow \infty} h(x) \eqdef \lim_{x
\rightarrow \infty} \text{sup}_{y \geq x} h(y).$} $f = O(g)$ iff
$\limsup_{x \rightarrow \infty} \abs{f(x)}/g(x) < \infty.$

equivalently, there exists a constant $c \geq 0$ and an $x_0$ such
that $\forall\;x \geq x_0,\abs{f(x)} \leq c g(x)$
\item
$f = \Theta(g)$ iff $f=O(g) \land g=O(f)$
\end{itemize}


\section{Combinatorics}

\subsection{Pigeonhole Principle}
\subsubsection{Pigeonhole Principle}
If there are more pigeons than pigeonholes, then there must be at
least two pigeons in one hole.
\subsubsection{Generalized Pigeonhole Principle}
If there are $m$ pigeons and $n$ pigeonholes, then there must be at
least $\ceil{m/n}$ pigeons in some hole.

\iffalse %%OMITTED BY OVERSIGHT

\subsection{Cardinality and Functions}

\begin{align*}
f:A \to B \text{ is an injection} \iff &\ [\forall a,a' \in A\ f(a)=f(a')
\implies a = a'],\\
f:A \to B \text{ is an injection} \implies &\ \card{A} \le \card{B}.\\
f:A \to B \text{ is a surjection} \iff &\ [\forall b \in B\,\exists a \in A\ f(a)=b],\\
f:A \to B \text{ is a surjection} \implies &\ \card{A} \ge \card{B}.\\
f:A \to B \text{ is a bijection} \iff &\ f \text{ is an injection and a surjection},\\
f:A \to B \text{ is a bijection} \implies &\ \card{A} = \card{B}.\\
\card{[A\to B]} = &\ \card{B}^{\card{A}},\\
\card{\set{ f \in [A\to A] \suchthat f \text{ is an bijection}}} = &\ \card{A}!,\\
\card{\set{ f \in [A\to B] \suchthat f \text{ is an injection}}} = &\
P(\card{B},\card{A}), & (\text{for} \card{A} \le \card{B}).
\end{align*}
\fi


\subsection{Counting}
Given a set of $n$ elements:
\begin{itemize}
\item number of $r$-permutations without replacement:
\[P(n, r) \eqdef n (n-1) \ldots (n-r+1) = \frac{n!}{(n-r)!}\]

\item $r$-combinations without replacement:
\[C(n,r) \eqdef \binom{n}{r} = \frac{n!}{(n-r)! \ r!}\]

\item $r$-permutations with replacement ($r$ distinct balls, $n$ distinct
bins):
\[
n^r
\]

\item $r$-combinations with replacement ($r$ identical balls, $n$ distinct
bins):
\[\binom{n+r-1}{r}\]

\item permutations with repetition:
\[\binom{n}{r_1, r_2, \ldots, r_k} \eqdef\frac{n!}{r_1!\ r_2! \ldots r_k!}\]
where $r_1 + r_2 + \cdots + r_k = n$.
\end{itemize}

\subsection{Combinatorial Identities}

\subsubsection{Sum Rule}
If $A_i$ are disjoint finite sets, then $|A_1 \cup A_2 \cup \cdots \union A_n| =
|A_1| + |A_2| + \cdots + |A_n|$.

\subsubsection{Product Rule}
If $A_i$ are finite sets, then $|A_1 \cross A_2 \cross \cdots \cross A_n| =
|A_1| \cdot |A_2| \cdots |A_n|$.

\subsubsection{Division Rule}
If $f: A \to B$ maps exactly $k$ elements of $A$ to each element of $B$,
then $|A| = k |B|$.

\subsubsection{Inclusion-Exclusion}
\begin{align*}
\card{\lgunion_{i=1}^n A_i} = &
  \sum_{\emptyset \neq S \subseteq \set{1,\dots,n}}
(-1)^{\card{S}+1} \card{\lgintersect_{i\in S} A_i}\\
          = & \sum_{k=1}^n (-1)^{k+1}
                 \sum_{S \subseteq \set{1,\dots,n}, \card{S} = k}
                     \card{\lgintersect_{i \in S} A_i}
\end{align*}

%\begin{description}

\subsubsection{Binomial Identity}
\[
\binom{n}{m} = \binom{n}{n-m}
\]

\subsubsection{Binomial Theorem}
\[
(x_1+x_2)^n=\sum_{i=0}^n\;\binom{n}{i}\;x_1^{n-i}x_2^i
\]

\subsubsection{Multinomial Theorem}
\[(x_1 + x_2 + \ldots + x_k)^n =
        \sum_{r_1 + r_2 + \ldots + r_k = n} \binom{n}{r_1, r_2, \ldots, r_k}
        x_1^{r_1} x_2^{r_2} \ldots x_k^{r_k}\]

\subsubsection{Stirling's Approximation}
\[
n! \sim \paren{\frac{n}{e}}^n \sqrt{2 \pi n}
\]

%\[
%n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{a_n}
%\]
%where
%\[
%1/(12n+1) \leq a_n \leq 1/(12n).
%\]
%\end{description}

\section{Probability}

\subsection{Probability Spaces}
A \emph{sample space} is a non-empty set $S$ whose elements are called \emph{outcomes}.  The \emph{events} are subsets of $S$.

A \emph{probability space} consists of a sample space $S$ together
with a \emph{probability function}, $\pr{}: P(S) \to [0,1]$ satisfying
the Sum Rule and such that $\pr{S} = 1$.

\subsection{Events}

\begin{align}
\pr{\lgunion_{n \in \naturals} A_n} = & \sum_{n \in \naturals} \pr{A_n}
& \mbox{ for pairwise disjoint } A_n  \tag{Sum Rule}\\
\pr{A-B}  = &  \pr{A} - \pr{A \intersect B} \tag{Difference Rule}\\
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  = &  1 - \pr{B}  \tag{Complement Rule}\\
\pr{A \union B}  = &  \pr{A} + \pr{B} - \pr{A \intersect B}
        \tag{Inclusion-Exclusion}\\
\pr{A \union B}  \leq & \pr{A}+ \pr{B} \tag{Boole's inequality} \\
\pr{A} \le & \pr{A \union B} \tag{Monotonicity}
%
%\item $\pr{\lgintersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\end{align}

\subsection{Law of Total Probability}
Suppose the sample space is the disjoint union of $B_0, B_1, \dots$.  Then
for all events $A$,
\begin{equation*}
\pr{A} = \sum_{i \in \naturals} \pr{A \cap B_i}.
\end{equation*}

\subsection{Conditional Probability}
\begin{align}
\prcond{A}{B} \eqdef &  \frac{\pr{A \intersect B}}{\pr{B}} \notag\\
\pr{A \intersect B} = & \prcond{A}{B} \pr{B} \tag{Product Rule}\\
\prcond{A}{B} = & \frac{\prcond{B}{A}\pr{A}}{\pr{B}} \tag{Bayes Rule}
\end{align}

\subsubsection{Conditional Total Probability}
Suppose the sample space is the disjoint union
of $B_0, B_1, \dots$.  Then for all events $A$,
\begin{equation*}
\pr{A} =  \sum_{i \in \naturals} \prcond{A}{B_i}\pr{B_i}.
\end{equation*}

\subsection{Independence}
\begin{definition*}
Events $A$ and $B$ are \emph{independent} iff
\[
\pr{A \intersect B} = \pr{A}\pr{B}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{mutually independent} iff for all
subsets $J \subset \naturals$,
\[
\pr{\lgintersect_{i\in J} A_i} = \prod_{i \in J} \pr{A_i}.
\]

Events $A_0,A_1,A_2,\dots$ are \emph{$k$-wise independent} iff $\set{A_i
\suchthat i\in J}$ are mutually independent for all subsets $J \subset
\naturals$ with $\card{J} = k$.
\end{definition*}


\subsection{Random Variables}

A \emph{random variable} over a given sample space, $\sspace$, is a
function from $\sspace \to \reals$.

The \emph{density function}, $f_R$, of a random variable, $R$, is
\[
f_R(a) \eqdef \pr{R = a}.
\]

The \emph{cumulative distribution function}, $F_R$, is
\[
F_R(a) \eqdef \pr{R \leq a}.
\]


\subsubsection{Indicator \& Uniform RV's}

For any event $A$, its \emph{indicator variable}, $I_A$, is the 0-1 valued
variable such that the event $[I_A = 1]$ is the same as the event $A$.

A random variable, $U$, is \emph{uniform} iff all its values are equally
likely.  That is
\[
\pr{U = a} = \pr{U=b}
\]
for all $a,b \in \range{U}$.

\subsubsection{Binomial Distribution}

A random variable, $B$, is \emph{binomial} with parameters $(n,p)$ iff its
pdf is the function $f_{n,p}: \naturals \to [0,1]$ defined by
\[
f_{n,p}(k) \eqdef \binom{n}{k} p^k (1-p)^{n-k}
\]
where parameter $n \in \naturals$ and $0 < p < 1$.  Equivalently, $B =
\sum_{k=1}^n B_k$ where $B_1,B_2,\dots,B_n$ are mutually independent
indicator variables with $\pr{B_i = 1} = p$.

\iffalse
\begin{eqnarray*}
f_{n,p}(k) & \eqdef & \binom{n}{k} p^k (1-p)^{n-k}\\
%F_{n,p}(k) & \eqdef & \sum_{i=0}^k f_{n,p}(i)\\
%%
\expect{f_{n,p}} & = & np\\
\variance{f_{n,p}} & = & np(1-p)\\

f_{n,p}(\alpha n) & \leq & 2^{-n(H(\alpha,p) - H(\alpha))}
\overbrace{e^{a_n - a_{\alpha n} - a_{(1-\alpha) n}}}^{\sim 1}/
\sqrt{2 \pi \alpha (1 - \alpha) n}
\end{eqnarray*}
where $0 < \alpha < 1$, $1/(12k+1) \leq a_k \leq 1/(12k)$, and
\begin{eqnarray*}
H(\alpha,p) & \eqdef & - (\alpha \log_2 p + (1 - \alpha) \log_2 (1 - p)),\\
H(\alpha) & \eqdef & H(\alpha,\alpha) = - (\alpha\log_2 \alpha + (1-\alpha)\log_2 (1-\alpha)).
\end{eqnarray*}
\fi

\[
F_{n, p}(\alpha n) \leq \frac{1 - \alpha}{1 - \alpha/p} f_{n, p}(\alpha n)
\]
where $0 < \alpha < p$.

\subsubsection{Independence}

Random variables $R_1, R_2, \dots$ are \emph{mutually independent} iff
\[
\pr{\lgintersect_{i} [R_i = x_i]} = \prod_{i} \pr{R_i = x_i},
\]
for all $x_1, x_2, \dots \in \reals$.  They are \emph{$k$-wise
independent} iff $\set{R_i \suchthat i\in J}$ are mutually independent for
all subsets $J \subset \naturals$ with $\card{J} = k$.

\subsection{Expectation}
\begin{align*}
\expect{R}  \eqdef & \sum_{r \in \range{R}} r \cdot \pr{R = r} &
   \text{definition in terms of random variables}\\
\expect{R}  \eqdef & \sum_{s \in \sspace} R(s) \cdot \pr{s} &
    \text{definition in terms of sample space}\\
\expect{R} = & \sum_{r \in \naturals} \pr{R > r} & \text{$R$ natural number valued}\\
\expect{\sum_{n \in \naturals} R_n} = & \sum_{n \in \naturals} \expect{R_n} &
 \mbox{providing } \sum_{n=1}^\infty \expect{\abs{R_n}} \text{ converges}\\
\expect{\prod_{n \in \naturals} R_n}  = &  \prod_{n \in \naturals} \expect{R_n}
& \mbox{for mutually independent }R_0,R_1,\dots
\end{align*}

For an random variable, $R$, and event, $A$, the \emph{conditional
expectation} of $R$ given $A$ is
\[
\expcond{R}{A} \eqdef \sum_{r \in \range{R}} r \cdot \prcond{R = r}{A}
\]

\subsubsection{Total Expectation}
Let $B_0, B_1, \dots$ be disjoint events whose union is the entire sample
space.  Then for any random variable, $X$,
\[
\expect{X} = \sum_{i \in \naturals} \expcond{X}{B_i} \pr{B_i}
\]
provided that all the expectations exist and are finite.


\subsection{Wald's Theorem}
Let $C_1, C_2, \dots,$ be a sequence of nonnegative random variables, and
let $Q$ be a positive integer-valued random variable, all with finite
expectations.  Suppose that
\[
\expcond{ C_i}{Q \geq i} = \mu
\]
for some $\mu \in \reals$ and for all~$i \geq 1$.  Then
\[
\expect{C_1 + C_2 + \cdots + C_Q} = \mu \expect{Q}.
\]

\subsection{Variance}
\begin{align*}
\variance{R}  \eqdef & \expect{(R-\expect{R})^2}\ =\ \expect{R^2}-\expectsq{R},\\
\variance{I_A} = & \pr{A}(1-\pr{A})\\
\variance{aR+b}  = & a^2\variance{R}, & \text{ for } a, b \in \reals,\\
\variance{R_1+ \cdots + R_n}  = & \variance{R_1}+ \cdots + \variance{R_n}
& \mbox{for pairwise independent } R_1,\dots,R_n\\
\sigma_R \eqdef & \sqrt{\variance{R}} &
 \mbox{(the \emph{standard deviation} of $R$)}
\end{align*}


%\subsection{Poisson Distribution}
%\begin{eqnarray*}
%\pr{X=k} & \eqdef &  e^{-\lambda}\frac{\lambda^k}{k!},\\
%%\binom{1/\delta}{k}(\lambda\delta)^k(1-\lambda\delta)^{1/\delta-k} 
%\expect{X} & = & \variance{X} = \lambda.
%\end{eqnarray*}

\subsection{Deviation from the Mean}
\subsubsection{Markov's Bound}
If R is a nonnegative random variable, then for all $x > 0$
  \begin{displaymath}
    \pr{R \geq x} \leq \frac{\expect{R}}{x}.
  \end{displaymath}

\subsubsection{Chebychev's Bound}
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]

\subsubsection{Chernoff's Bound}
Let $T_1, T_2, \dots, T_N$ be mutually independent Bernoulli variables,
and let $T \eqdef T_1 + T_2 + \cdots + T_N$.  Then for all $c \geq 1$,
        \begin{equation}
\pr{T \geq c \expect{T}} \leq \textup{exp}(- (c\ln c -c + 1) \expect{T}).
\end{equation}

\subsection{Pairwise Independent Sampling}
Let $G_1, \dots, G_n$ be pairwise independent random variables with
deviations bounded by a constant $b>0$.  Let
\[
A_n \eqdef \frac{\sum_{i=1}^n G_i}{n}.
\]
Then
\begin{equation}\label{Snx}
\pr{\abs{A_n - \expect{A_n}} \geq x} \leq \frac{1}{n} \paren{\frac{b}{x}}^2.
\end{equation}

\subsection{Weak Law of Large Numbers}
Let $G_1, \dots, G_n, \dots$ and $A_n$ be as in the Pairwise Independent
Sampling Theorem.  Then for any $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \pr{\abs{A_n - \expect{A_n}} < \epsilon} = 1.
\]

\subsection{Gambler's Ruin}

\begin{theorem*}
In the Gambler's Ruin game with probability $p$ of winning
each individual bet, with initial capital, $n$, and goal, $T$,
\begin{align}
\pr{\text{the gambler is a winner in the fair game}} = & \frac{n}{T},
        \label{fairwin}\\
\pr{\text{the gambler is a winner a biased game}} = &
        \frac{(q/p)^n-1}{(q/p)^T -1}, \label{biaswin}
\end{align}
where $q \eqdef (1-p)$.
\begin{equation}\label{intended-profit}
\pr{\text{the gambler is a winner in an unfair game}} \leq (p/q)^{T-n}.
\end{equation}
Let $Q$ be the number of bets till the game ends.
\begin{eqnarray}
\expect{\text{$Q$ in an unfair game}} & = &
     \frac{\pr{\text{gambler is a winner}}T-n}{2p-1},\notag\\
\expect{\text{$Q$ in a fair game}} & = & n(T-n). \label{Tn}
\end{eqnarray}

\end{theorem*}

To obtain formula~(\ref{biaswin}), let $p$ and $T$ be fixed, and let $w_n$
be the gambler's probabiliity of winning when his initial capital is $n$
dollars.  So $w_0 = 0$ and $w_T =1$.  For $0<n<T$, the Total Expectation
Theorem implies
\[
w_n = p w_{n+1} + q w_{n-1}.
\]
Solving this simple linear recurrence yields~(\ref{biaswin}).

\subsection{Central Limit Theorem}
\begin{definition*}
The \emph{normal density function} is the function 
\[
\eta(x) \eqdef \frac{1}{\sqrt{2\pi}}e^{-x^2/2},
\]
and the \emph{normal distribution function} is its integral
\[
N(y) \eqdef \int_{-\infty}^y \eta(x)dx = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^y
e^{-x^2/2}dx.
\]
\end{definition*}

The function $\eta(x)$ defines the standard \emph{Bell curve}, centered about
the origin with height $1/\sqrt{2\pi}$ and about two-thirds of its area
within unit distance of the origin.  The normal distribution function
$N(y)$ approaches 0 as $y \rightarrow -\infty$.  As $y$ approaches zero
from below, $N(y)$ grows rapidly towards $1/2$.  Then as $y$ continues to
increase beyond zero, $N(y)$ rapidly approaches 1.

\begin{theorem*}[Central Limit]
Let $S_n = \sum_{i=1}^n G_i$ where $G_1, \dots, G_i, \dots$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.
Let $\mu_n \eqdef \expect{S_n} = n\mu$, and $\sigma_n \eqdef \sigma_{S_n}
= n\sigma$.  Now let $S^*_n \eqdef (S_n-\mu_n)/\sigma_n$ be the normalized
version of $S_n$.  Then
\[
\lim_{n\rightarrow\infty} \pr{S^*_n \leq \beta}= N(\beta)
\]
for any real number $\beta$.
\end{theorem*}


%\subsection{Strong Law of Large Numbers}
%Let $X_1,X_2,\dots$ be a sequence of independent and identically
%distributed random variables, each having a finite mean
%$\mu=\expect{X_i}$.  Then the event
%\[
%\lim_{n\to\infty}\frac{X_1+X_2+\cdots+X_n}{n} = \mu,
%\]
%occurs with probability~1.

\end{document}


