\documentclass[11pt]{article}
\usepackage{amsmath}
\input{/a/class/6.042/fall99/inputs/macros-course}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\def\medblank{\rule[-2pt]{1in}{.5pt}}
\def\relz{\mathbin{\, \rho \,}}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\begin{document}


\handout{final-appendix}{Final Exam Appendix}{December 11, 1999}

%\section*{Appendix}

\subsection*{Graphs}

A \textbf{simple graph} is an undirected graph with no self loops and at
most one edge between any two nodes.

A \textbf{tree} is a connected, acyclic simple graph.

An \textbf{Eulerian circuit} in a graph is a path beginning and ending at
the same vertex and containing each edge exactly once.

The \textbf{complete graph}, $K_n$, is the simple graph with $n$ vertices and
with an edge between every two vertices.

The \textbf{degree} of a vertex in a graph is the number of edges at the vertex.

A \emph{connected component} of a simple graph is an equivalence class of
vertices under the ``is connected by a path to'' relation on pairs of vertices.

\subsection*{Partial Orders}

\textbf{Lexicographic order}, $\preceq$, on pairs of natural numbers is
defined by the rule that
\[
(n_1,n_2) \preceq (m_1,m_2) \quad \mbox{iff} \quad [(n_1 < m_1) \mbox{ or } (n_1
= m_1 \mbox{ and } n_2 \leq m_2)].
\]

\subsection*{Sums}

\[
\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r-1}.
\]

\[
\sum_{i=0}^{n} ir^i = \frac{{r - (n+1) r^{n+1} + n r^{n+2}}}{(1-r)^2}.
\]

\[
\int \ln x dx = x \ln (x/e).
\]

\subsection{Combinatorics}

\textbf{Stirling's formula}:
\[
n! \sim  \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.
\]

\textbf{The Principle of Inclusion-Exclusion}:
\[
\card{A \union B} = \card{A}+ \card{B} - \card{A \intersect B}.
\]
For $n$ sets:
\[
\card{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \card{\Intersect_{j \in S} A_j}.
\]

Probabilistic version:
\[
\prob{A \union B} = \prob{A} + \prob{B} - \prob{A \intersect B}.
\]

\[
\prob{\Union_{i=1}^n A_i}
= \sum_{S \subset \set{1,\dots,n}}
           (-1)^{\card{S}} \prob{\Intersect_{j \in S} A_j}.
\]

\begin{eqnarray*}
n!  & \eqdef & n \cdot (n-1) \cdots 2 \cdot 1\\
0!  & \eqdef & 1\\
P(n,r)  & \eqdef & n \cdot (n-1) \cdots (n - (r-2) \cdot (n - (r - 1))\\
C(n,r) = \binom{n}{r}  & \eqdef & \frac{n!}{r!\, (n-r)!}
\end{eqnarray*}


\subsection*{Markov \& Chebyshev Bounds}

Markov bound:
\[
\prob{R \geq x} \leq \frac{\expect{R}}{x}.
\]


Chebyshev bound: for $c \geq 0$,
\[
\prob{\abs{R - \expect{R}} \geq c\sigma_R} \leq \frac{1}{c^2}.
\]

The ``one-way'' version of Chebyshev bound: for $c \geq 0$,
\[
\prob{R - \expect{R} \geq c\sigma_R} \leq \frac{1}{1+c^2}.
\]


\subsection*{Weak Law of Large Numbers for Bernoulli Variables}

A \emph{Bernoulli variable} is a 0-1-valued random variable.  For any
event $A$, the \emph{index variable}, $I_A$, is the Bernoulli variable
which is 1 exactly when event $A$ occurs.

Let $G_1, G_2, \dots, G_n$ independent Bernoulli variables, each with the
same probability $p$ of being equal to one.  In this case, $G_i=G_i^2$, so
\[
\expect{G_i^2} = \expect{G_i} = \prob{G_i=1} = p,
\]
and
\[
\variance{G_i} = \expect{G_i^2} - \expectsq{G_i} = p - p^2 = p(1-p).
\]
Let
\[
S_n \eqdef \sum_{i=1}^n G_i,
\]

We can use the random variable $S_n/n$ to estimate $p$.  This estimator
$S_n/n$ is a random variable with two critical properties:
\begin{eqnarray*}
\expect{\frac{S_n}{n}} & = & \expect{G_i} = p,\\
\variance{\frac{S_n}{n}} & = & \frac{\variance{G_i}}{n} = \frac{p(1-p)}{n}.
\end{eqnarray*}

To prove this, note that by linearity of expectation
\[
\expect{\frac{S_n}{n}} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{np}{n} = p.
\]

Also, since the $G_i$'s are independent, their variances will add, so
\begin{eqnarray*}
\variance{\frac{S_n}{n}} & = & (\frac{1}{n})^2 \variance{S_n}\\
& = & (\frac{1}{n})^2 \sum_{i=1}^n \variance{G_i}\\
& = & (\frac{1}{n})^2 n\variance{G_i}\\
& = & \frac{\variance{G}}{n}.
\end{eqnarray*}

Now Chebyshev's Bound tells us that
\begin{theorem}
Let $S_n \eqdef \sum_{i=1}^n G_i$ where $G_1, \dots, G_n$ are mutually
independent Bernoulli variables with the same probability $p$ of being
equal to one.
Then
\[
\prob{\abs{\frac{S_n}{n} - p} \geq x} \leq \frac{p(1-p)}{nx^2}.
\]
\end{theorem}

Now if we fix $p$ and $x$ and let $n$ approach infinity, we conclude that
the Weak Law of Large Numbers holds:

\[
\lim_{n \rightarrow \infty} \prob{\abs{\frac{S_n}{n} - p} \geq x} = 0.
\]


\end{document}
        
