\documentclass[12pt]{article}
\input{macros-course}

\begin{document}
\handout{final-appendix}{Appendix for Final Exam}{Dec 12, 2001}{\stamp}
%\section{Appendix}

This handout lists many of the formulas covered in the course.  The Final
Exam will be \textbf{closed book}, but you can count on this list
appearing in an Appendix to the Final Exam.  The actual Appendix may
include additional definitions needed for particular questions, as in
Quizzes 1 \& 2.

% \subsubsection*{Dilworth Theorem:}
% If $t$ is the length of the longest chain in a poset $(A, \preceq)$
% then $A$ can be partitioned into $t$ antichains.

\subsection{Combinatorics}

\subsubsection{Summation}
\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*}

\subsubsection{Counting}
Given a set of $n$ elements:
\begin{closeitemize}
\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{closeitemize}

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

\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^{r_1} x^{r_2} \ldots x^{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} | \bigcap_{i
\in S} A_i |\right)\]


\subsubsection{Stirling's Approximation}
\[
n! = \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n e^{a_n}
\]
where
\[
1/(12n+1) \leq a_n \leq 1/(12n).
\]

\subsection{Probability}

\subsubsection{Events}
\begin{eqnarray*}
\pr{\lgunion_{n \in \nats} A_n} & = & \sum_{n \in \nats} \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*}

\subsubsection{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}.
\]

\subsubsection{Expectation}
\begin{align*}
\expect{R} & \eqdef  \sum_{r \in \reals} r \cdot \pr{R = r}\\
\expect{R} & =  \sum_{r \in \nats} \pr{R > r} & \text{$R$ natural number valued}\\
\expect{\sum_{n \in \nats} R_n} & =  \sum_{n \in \nats} \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*}

\subsubsection{Conditional 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 \expectcond{X}{B_i} \pr{B_i}
\]
provided that all the expectations exist and are finite.

\subsubsection{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*}

\subsubsection{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$, $a_n$ is from Stirling's
formula, 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$.

\subsubsection{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*}

\subsubsection{Markov's Theorem}
If $R:S\rightarrow \reals^+$ is a random variable, then for all $x \geq 0$,
\[\pr{R \geq  x}\leq \frac{\expect{R}}{x}. \]


\subsubsection{The Chebychev Bound}
For any random variable R and $x > 0$,
\begin{eqnarray*}
\pr{\abs{R-\expect{R}}\geq x} & \leq & \frac{\variance{R}}{x^2},\\
%\pr{\abs{R-\expect{R}}\geq x\sigma_R} & \leq & \frac{1}{x^2},\\
\pr{R - \expect{R} \geq x} & \leq & \frac{\variance{R}}{\variance{R}+x^2}.
\quad \mbox{[One-sided version]}
\end{eqnarray*}

% $$ \pr{R - \expect{R} \leq -x} \leq \frac{\variance{R}}{\variance{R}+x^2}$$

\subsubsection{Chernoff 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$,
\[
  \pr{T \geq c \expect{T}} \leq e^{- (c\ln c -c + 1) \expect{T}}.
\]

%% DO WE INCLUDE THESE ??
\iffalse
\subsubsection{Wald's Theorem}

\begin{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}.
\]
\end{theorem}

\subsubsection{Weak Law of Large Numbers}

\begin{theorem*}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent variables with the same mean, $\mu$, and deviation, $\sigma$.
Then
\begin{equation}\label{Sndev}
\pr{\abs{\frac{S_n}{n} - \mu} \geq x} \leq \frac{1}{n}
\left(\frac{\sigma}{x}\right)^2.
\end{equation}
\end{theorem*}

\subsubsection{Central Limit Theorem}

\begin{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
\begin{equation}\label{normal}
\lim_{n\rightarrow\infty} \pr{S^*_n \leq \beta}= N(\beta)
\end{equation}
for any real number $\beta$, where $N$ is the Normal Distribution.
\end{theorem}
\fi

\end{document}
