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

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

\tableofcontents
\newpage

\section{Relations}
\subsection{Equivalence}

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

$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{Dilworth 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{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{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\\
H_n & \eqdef & \sum_{i=1}^n \frac{1}{i} \quad\quad \text{(Harmonic Numbers)}\\
H_n &\sim& \ln n
\end{eqnarray*}
\subsection{Asymptotics}

%\begin{definition*}
For functions $f,g:\reals\to\reals$, we say 

\begin{itemize}
\item 
$f(x) \sim g(x)$, 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{lub}_{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}


%\iffalse
\section{Simple Graphs}
%\subsection{Definitions}

\subsection{Edges \& Paths}

A \emph{simple graph} is an undirected graph with no self-loops and no
multiple edges.  Formally, a 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.

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$.  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$.

%A \emph{connected component} of a graph $G=(V, E)$ is a maximal sized
%subset $V_1\subset V$ such that for any distinct $u, v\in V_1$ there
%is a path from $u$ to $v$ in $G$.

\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.

\iffalse

%\subsection{Properties}
%\begin{definition*}
A simple graph $G=(V,E)$ is \emph{connected} iff for every pair of
distinct vertices $u,v\in V$ there is a path from $u$ to $v$ in~$G$.
%\end{definition*}
\fi

\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.

\section{Combinatorics}

\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}
%\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{Inclusion-Exclusion}
\[|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)\]
\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) \leq a_n \leq 1/(12n).
%\]
%\end{description}

\section{Probability}

\subsection{Events}
\begin{eqnarray*}
\pr{\bigcup_{n \in \naturals} A_n} & = & \sum_{n \in \naturals} \pr{A_n}
\mbox{ for pairwise disjoint } A_n\\
%\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}\\
\pr{A \union B}  & = &  \pr{A} + \pr{B} - \pr{A \intersect B}\\
\pr{A \union B} & \leq & \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 \in \naturals} \pr{A \cap 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 \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{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 \leq 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) & \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*}

\[
F_{n, p}(\alpha n) \leq \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 \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 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} \geq x}
    \leq \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}
\leq \epsilon} = 1.
\]

\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 \leq \beta}= N(\beta)
\]
for any real number $\beta$, where $N$ is the standard Normal Distribution.
%\fi

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