\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

\newcommand{\union}{\cup}
\newcommand{\intersect}{\cap}
\newcommand{\Union}{\bigcup}

\begin{document}
\handout{reviewsheet}{Notes for Final Exam}{May 20, 1999}

\subsubsection*{Summation}
\begin{eqnarray*}
\sum_{i=0}^{n} x^i & = & \frac{1- x^{n+1}}{1 - x}\\
\sum_{i=0}^{n} i^2 & = & \frac{n(n+1)(2n+1)}{6}\\
\frac{1}{1-x} & = & 1 + x + x^2 + x^3 + \ldots\\
\sum_{i=1}^{n} i x^i & = & \frac{x - (n+1)x^{n+1} + n x^{n+2}}{(1 - x)^2}\\
%\frac{x}{(1-x)^2} & = & x + 2x^2 + 3x^3 + 4x^4 + \ldots\\
e^x & = & 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots\\
- \ln (1-x) & = & \int \frac{1}{1-x}\ =\ x + \frac{x^2}{2} +
\frac{x^3}{3} + \frac{x^4}{4} + \ldots
\end{eqnarray*}


\subsubsection*{Master Theorem}
For  $T,f:\naturals\to \naturals$, and constants $a > 0, b >1$, if
\[T(n) = aT(\ceil{n/b}) + f(n),\]
then
\[
T(n) = \left\{ \begin{array}{ll}
\Theta(n^\beta) & \mbox{ if } f(n) = O(n^{\beta - \epsilon})
\mbox{ for some } \epsilon >  0,\\
\Theta(n^\beta \log n) & \mbox{ if } f(n) = \Theta(n^\beta),\\
\Theta(f(n)) & \mbox{ if } af(n/b) \leq cf(n)
\mbox{ for some $c < 1$ and all large $n$.}
\end{array} \right.
\]
where $\beta ::= \log_b a$.

\subsubsection*{Linear Recurrences}
A homogeneous linear recurrence of order $d$,
\[f(n) =  a_1 f(n-1) + a_2 f(n-2) + \cdots + a_d f(n-d),\]
has characteristic polynomial:
\[p(\alpha) ::= \alpha^d - a_1 \alpha^{d-1} - a_2
\alpha^{d-2} - \ldots - a_{d-1} \alpha - a_d,\]
and characteristic equation $p(\alpha) = 0$.
If $r$ is a root of $p$ with
multiplicity $m>0$, then all of
\[r^n,\ n r^n,\ n^2 r^n,\ \ldots,\ n^{m-1} r^n\]
are solutions to the recurrence.  Every solution to the equation is a
linear combination of the $d$ terms obtained in this way from the
characteristic equation.

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

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

\item $r$-combination without replacement:
\[\binom{n}{r} ::= \frac{n!}{(n-r)! \ r!}\]

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

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

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


\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)\]


\iffalse
\subsubsection*{Generating Functions}

Let $A(x) = a_0 + a_1 x + a_2 x^2 + \ldots$ and $B(x) = b_0 + b_1 x +
\ldots$ be ordinary generating functions for the number of ways to choose
items from disjoint sets ${\cal A}$ and ${\cal B}$.  The generating
function for the number of ways to choose objects from the union ${\cal A}
\cup {\cal B}$ is the product $A(x) \cdot B(x)$.  The coefficient of $x^n$
in the product is
\[c_n ::= a_0 b_n + a_1 b_{n-1} + a_2 b_{n-2} + \ldots a_n b_0.\]


The sequence
$<c_0, c_1, c_2, \ldots>$ is the {\em convolution} of sequences $<a_0,
a_1, a_2, \ldots>$ and $<b_0, b_1, b_2, \ldots>$.


A random variable $R$ taking nonnegative integer values has Probability
Generating Function:
\begin{eqnarray*}
G_R(x) & ::= & \sum_{i=0}^{\infty}\pr{R=i}x^i,\\
\expect{R} & = & G_R^\prime(1),\\
G_{R_1+R_2} & = & G_{R_1}\cdot G_{R_2} \quad \mbox{for independent }R_1, R_2.
\end{eqnarray*}
\fi

\subsection*{Probability}

\subsubsection*{Events}
\begin{eqnarray*}
\pr{\Union_{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{\overline{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}}$
%
\pr{A \mid 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*{Expectation}
\begin{eqnarray*}
\expect{R} & ::= & \sum_{r \in \reals} r \cdot \pr{R = r}\\
\expect{\sum_{n \in \nats} R_n} & = & \sum_{n \in \nats} \expect{R_n} \quad
 \mbox{for convergent} \sum_{n=1}^\infty \abs{R_n}\\
\expect{R_1R_2} & = & \expect{R_1}\expect{R_2} \quad \mbox{for independent }R_1, R_2
\end{eqnarray*}


\subsubsection*{Variance}
\begin{eqnarray*}
\variance{R} & ::=& \expect{(R-\expect{R})^2}\ =\ \expect{R^2}-\expectsq{R},\\
\sigma_R & ::= & \sqrt{\variance{R}}
\quad \mbox{ [$\sigma_R ::=$ 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) & ::= & \binom{n}{k} p^k (1-p)^{n-k}\\
F_{n,p}(k) & ::= & \sum_{i=0}^k f_{n,p}(i)\\
f_{n,p}(\alpha n) & = &
        2^{\left(\alpha     \log_2\left( \frac{p}{\alpha} \right) +
              (1-\alpha) \log_2\left( \frac{1-p}{1-\alpha} \right)\right) \cdot n}
              \overbrace{e^{a_n - a_{\alpha n} - a_{n-\alpha n}}}^{\sim 1}
             \frac{1}{\sqrt{2 \pi \alpha (1 - \alpha) n}}\\
F_{n, p}(\alpha' n) & \leq &
\frac{1 - \alpha'}{1 - \alpha'/p} f_{n, p}(\alpha' n)
\end{eqnarray*}
where $0 < \alpha < 1, 0 < \alpha' < p$, and $a_n$ from Stirling's formula.

\subsubsection*{Wald's Theorem}
Let $Q$ be a non-negative integer valued random variable such that
$\expect{Q}$ is finite, and let $R_1, R_2, \ldots$ be a countable sequence
of nonnegative random variables.  Let $T$ be the sum $R_1 + R_2 + \cdots +
R_Q$.  Suppose that every variable $R_k$ has the same expectation,
conditioned on being included in the sum, as $R_1$, and also suppose that
$\expect{R_1}$ is finite.  Then, $\expect{T} = \expect{Q} \cdot
\expect{R_1}$.

\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,
\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$, be a sum of $n$ independent 0-1-valued random
variables.  Then for all $c>1$
\begin{eqnarray*}
\pr{T\geq e \expect{T}} & \leq  & e^{- \expect{T}},\\
\pr{T\geq c \expect{T}} & \leq & e^{-\alpha c \expect{T}},
\end{eqnarray*}
where $e \approx 2.72$ is the base of the natural logarithms and $\alpha
::=\ln c + 1/c-1$.

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

\end{document}



