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

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

\tableofcontents
\newpage

\section{Induction}

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

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

\begin{axiom*}[Least Number Principle]
Every nonempty subset, $S \subseteq \naturals$, has a smallest element.
\end{axiom*}

\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 $\not\exists b\in A [b R a\wedge b\neq a]$
\item $a$ is a \emph{maximal element} of $A$ if $\not\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}

If $R$ is a relation on $A \times B$, then the \emph{inverse of $R$} is
the relation on $B\times A$ given by 
\[R^{-1} = \set{(b,a) \mid (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
\begin{displaymath}
  R_2 \circ R_1 =\{(a,c) \mid
  (\exists b) ((a,b) \in R_1) \wedge ((b,c) \in R_2)\}.
\end{displaymath}

A \emph{path} in a relation $R$ 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$.  We
call $k$ the \emph{length} of the path.


Let $R$ be a relation on the set $A$ and $n \in \naturals$.  Then
\[
R^n =
\begin{cases}
R & \mathrm{if}\ n=1\\
R^{n-1} \circ R & \mathrm{if}\ n>1
\end{cases}
\]

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


\subsection{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}

\begin{lemma*}
Let $R$ be a relation on the set $A$.
\begin{itemize}
\item The reflexive closure of $R$ is $S=R \cup \set{(a,a), \forall a \in A}$.\\
\item The symmetric closure of $R$ is $S=R \union R^{-1}$.
\item The transitive closure of a relation $R$ is the set 
\[
S = \{(a,b) \in A\times A 
\mbox{ given there is a path from $a$ to $b$ in $R$}\}.
\]
\end{itemize}
\end{lemma*}

The \emph{reflexive and transitive closure} (also called the \emph {connectivity
relation}) of $R$ is 
\[
R^* = \{(a,b) \in A\times A \mid 
\mbox{ there exists a path from $a$ to $b$ in $R$}\}.
\] or, equivalently, $R^* = \bigcup_{n=1}^\infty R^n.$ 

\begin{lemma*}
If $R$ is a reflexive relation on a finite set $A$ then $R^* =
R^{\card{A}} $.
\end{lemma*}

\subsection{Dilworth Theorem}

\begin{theorem*}
Given any finite poset $(A, R)$ for which the longest chain
has length $t$, $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{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 & \leqslant & 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 \geqslant x} h(y).$} $f = O(g)$ iff
$\limsup_{x \rightarrow \infty} \abs{f(x)}/g(x) < \infty.$

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


\section{Graphs}

\subsection{Edges \& Paths}

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 where $E$ is a set of \emph{simple edges} on $V$.  A
\emph{simple edge} on $V$ is a set of two vertices.

A \emph{directed graph} or \emph{digraph} is a pair of sets of $(V,E)$
where $E \subseteq V\times V$.  In other words, an edge $(a,b) \in E$ is
an \emph{ordered pair} of 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
\geqslant 0$ vertices such that $v_i$ and $v_{i+1}$ are adjacent for
$0 \leqslant 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 \leqslant i <
j \leqslant n$.  The path is a \emph{simple cycle} if $n>2$, $v_0,
v_1, \dots, v_{n-1}$ is a simple path, and $v_n=v_0$.

Two vertices $u,v \in V$ are \emph{connected} iff there is a path between
them, \viz a path $v_0, v_1, \dots, v_n$ with $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 Tours and Hamiltonian Paths}
An \emph{Euler tour} of an undirected graph $G$ is a circuit that traverses
every edge of $G$ exactly once.

\begin{theorem*}
If undirected graph $G$ has Euler tour, then $G$ is connected and every
vertex has even degree.
\end{theorem*}

A \emph{Hamiltonian path} of an undirected graph $G$ is  simple path that
traverses every vertex exactly once.

\subsection{Common graphs}

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

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

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

The \emph{wheel} on $n \geqslant 4$ vertices $W_n$ is the graph consisting of
$C_{n-1}$ plus an additional vertex connected to every other vertex.

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

\subsection{Trees}

A \emph{tree} is any simple graph $G=(V,E)$, such that any of these
(equivalent) conditions hold:
\begin{itemize}
\item $G$ is connected and $\card{E} = \card{V}-1$.
\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}

A \emph{rooted tree} is a tree $T$ together with a distinguiched 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{Colourings}

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

\subsection{Hall's Theorem}
Given a bipartite graph $G = (V, E)$ coloured yellow and blue, let
$V_1$ and $V_2$ denote the set of yellow and the set of blue vertices
respectively.  

A \emph{perfect matching} for $G$ is an injection $f: V_1 \to
V_2$ s.t. ${v, f(v)} \in E$ for all $v \in V_1$.

For a subset $A$ of $V_1$, define the \emph{neighbour set} to be
\[
 N(A) ::= \{ v | \exists a \in A \{a, v\} \in E \}
\]

A set $A \subset V_1$ is called a \emph{bottleneck} if $|A| \geqslant |N(A)|$.

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

\section{State Machines}

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 derived variable $f : Q \to \reals$ is \emph{strictly decreasing} iff
\[
q \rightarrow q' \text{  implies  } f(q') < 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*}
\textbf{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{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.

\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{Identities}
\subsubsection{Sum Rule}
If $A_i$ are disjoint finite sets, then $|A_1 \cup A_2 \cup ... A_n| =
|A_1| + |A_2| + ... |A_n|$.
\subsubsection{Product Rule}
If $A_i$ are finite sets, then $|A_1 \cross A_2 \cross ... A_n| =
|A_1| \cdot |A_2| \cdot ... |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}
\[|A \cup B| = |A| + |B| - |A \cap B|\]
\[|A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n
(-1)^{k+1} \left( \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} \left| \bigcap_{i
\in S} A_i \right|\right)\]
%\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 \left(\frac{n}{e}\right)^n \sqrt{2 \pi n}\]
%\[
%n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{a_n}
%\]
%where
%\[
%1/(12n+1) \leqslant a_n \leqslant 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{eqnarray*}
\pr{\bigcup_{n \in \naturals} A_n} & = & \sum_{n \in \naturals} \pr{A_n}
\mbox{ for pairwise disjoint } A_n \quad \mbox{[Sum Rule]}\\
%\item $\pr{A-B}  & = &  \pr{A} - \pr{A \intersect B}$
%
% \item $\pr{A \intersect B}  \le  \pr{A}, \label{ab<a}$
%
\pr{\bar{B}}  & = &  1 - \pr{B} \label{1-b} \quad \mbox{[Complement rule]}\\
\pr{A \union B}  & = &  \pr{A} + \pr{B} - \pr{A \intersect B}\\
\pr{A \union B} & \leqslant & \pr{A}+ \pr{B} \quad \mbox{[Boole's inequality]} \\
%
%\item $\pr{\Intersect_n A_n} \ge 1 - \sum_n \pr{\overline{A_n}}$
%
\prcond{A}{B}  & = &  \frac{\pr{A \intersect B}}{\pr{B}}\\
%\pr{A \mid B} & = & \frac{\pr{B\mid A}\pr{A}}{\pr{B}} quad \mbox{[Bayes Rule]}\\
\end{eqnarray*}

\subsection{Law of Total Probability}
Let $B_0, B_1, \ldots$ be disjoint events whose union is the
entire sample space.  Then for all events $A$,
\[\pr{A} = \sum_i \pr{A \cap B_i}\]
or equivalently
\[\pr{A} = \sum_i \pr{B_i}\prcond{A}{B_i}\]

\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{R_1R_2} & =  \expect{R_1}\expect{R_2} && \mbox{for independent }R_1, R_2
\end{align*}

\subsection{Conditional Expectation}
\[
\expcond{R}{A}\eqdef \sum_{r \in \range{R}} r \cdot \prcond{R = r}{A}
\]
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 \expcond{X}{B_i} \pr{B_i}
\]
provided that all the expectations exist and are finite.

%% DO WE INCLUDE THESE ??
%\iffalse
\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 \geqslant i} = \mu
\]
for some $\mu \in \reals$ and for all~$i \geqslant 1$.  Then
\[
\expect{C_1 + C_2 + \cdots + C_Q} = \mu \expect{Q}.
\]

\subsection{Density \& Cumulative Distribution}

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 \leqslant a}.
\]


\subsection{Variance}
\begin{eqnarray*}
\variance{R} & \eqdef& \expect{(R-\expect{R})^2}\ =\ \expect{R^2}-\expectsq{R},\\
\sigma_R & \eqdef & \sqrt{\variance{R}}
\quad \mbox{(the \emph{standard deviation} of $R$)},\\
\variance{aR+b} & = & a^2\variance{R}, \mbox{ for } a, b \in \reals,\\
\variance{R_1+ \cdots + R_n} & = & \variance{R_1}+ \cdots + \variance{R_n}
\quad \mbox{for pairwise independent } R_1,\ldots,R_n.
\end{eqnarray*}

\subsection{Binomial Distribution}
\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) & \leqslant & 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) \leqslant a_k \leqslant 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*}

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

%\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 \geqslant x} \leqslant \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}} \geqslant x} \leqslant \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 \geqslant 1$,
        \begin{equation}
\pr{T \geqslant c \expect{T}} \leqslant \textup{exp}(- (c\ln c -c + 1) \expect{T}).
\end{equation}

\subsection{Pairwise Independent Sampling}
Let $G_1, \dots, G_n$ be pairwise independent variables with the same
mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Snx}
\pr{\abs{\frac{\sum_{i=1}^n G_i}{n} - \mu} \geqslant x}
    \leqslant \frac{1}{n} \left(\frac{\sigma}{x}\right)^2.
\end{equation}

\subsection{Weak Law of Large Numbers}
Let $G_1, \dots, G_n, \dots$ be independent variables with the same
distribution and the same expectation, $\mu$.  For any $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{\sum_{i=1}^n G_i}{n} - \mu}
\leqslant \epsilon} = 1.
\]

%Cut, because these were optional in the course

\subsection{Central Limit Theorem}
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$,
and let $S^*_n \eqdef (S_n-\mu)/\sigma$ be the normalized version of
$S_n$.  Then
\[\lim_{n\rightarrow\infty} \pr{S^*_n \leqslant \beta}= N(\beta)\]
for any real number $\beta$, where $N$ is the standard Normal Distribution.

%\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}
