\documentclass[12pt]{article}
\usepackage{latex-macros/course}

\begin{document}

\inclassproblems{15, Mon.}

\begin{problem}
The Pairwise Independent Sampling Theorem generalizes easily to sequences
of pairwise independent random variables, possibly with \emph{different}
means and variances, as long as their variances are bounded by some
constant:

\begin{theorem*}[Generalized Pairwise Independent Sampling]
Let $X_1, X_2, \dots$ be a sequence of pairwise independent random
variables such that $\variance{X_i} \leq b$ for some $b\geq 0$ and all
$i\geq 1$.  Let
\begin{align*}
A_n & \eqdef \frac{X_1 + X_2 + \cdots + X_n}{n},\\
\mu_n & \eqdef \expect{S_n}.
\end{align*}
Then for every $\epsilon > 0$,
\begin{equation}\label{gpis}
\pr{\abs{A_n - \mu_n} > \epsilon} \leq \frac{b}{\epsilon^2} \cdot \frac{1}{n}.
\end{equation}
\end{theorem*}

\begin{problemparts}
\problempart  Prove the Generalized Pairwise Independent Sampling Theorem. 
\hint The proof of the Pairwise Independent Sampling Theorem from
the Notes is repeated in the Appendix.

\solution{Essentially identical to the proof attached, except that
$\variance{G_i}$ gets replaced by $b$, and the equality becomes $\leq$
where the $b$ is first used.}

\problempart Conclude

\begin{corollary*}[Generalized Weak Law of Large Numbers]
For every $\epsilon > 0$,
\[
\lim_{n \rightarrow \infty}
        \pr{\abs{A_n - \mu_n}  > \epsilon} = 0.
\]
\end{corollary*}

\solution{For any fixed $\epsilon$, the righthand side of~(\ref{gpis})
approaches 0 as $n$ approaches infinity.}

\end{problemparts}

\end{problem}

\begin{problem}
Write out a proof that
\[
\variance{aR} = a^2\variance{R}.
\]
\end{problem}

\begin{problem}
Finish discussing the ``Explain sampling to a jury question'' from last 
Friday.
\end{problem}


\instatements{\newpage}
\section{Appendix}

\subsection{Chebyshev's Theorem}

\begin{theorem*}[Chebyshev]
Let $R$ be a random variable, and let $x$ be a positive real number.
Then
\begin{equation}\label{Chb}
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\end{equation}
\end{theorem*}


\subsection{Pairwise Independent Sampling}

\begin{theorem*}[Pairwise Independent Linearity of Variance]
If $R_1, R_2, \ldots, R_n$ are \emph{pairwise} independent random
variables, then
\[
\variance{R_1 + R_2 + \cdots + R_n} = \variance{R_1} + \variance{R_2} +
  \cdots + \variance{R_n}.
\]
\end{theorem*}

\begin{theorem*}[Pairwise Independent Sampling]
Let
\[
A_n \eqdef \frac{\sum_{i=1}^n G_i}{n}
\]
where $G_1, \dots, G_n$ are pairwise independent random variables with the
same mean, $\mu$, and deviation, $\sigma$.  Then
\begin{equation}\label{Sndev}
\pr{\abs{A_n - \mu} > x} \leq 
\paren{\frac{\sigma}{x}}^2 \cdot \frac{1}{n}.
\end{equation}
\end{theorem*}

\begin{proof}
By linearity of expectation,
\[
\expect{A_n} = \frac{\expect{\sum_{i=1}^n G_i}}{n}
   = \frac{\sum_{i=1}^n \expect{G_i}}{n}
   = \frac{n\mu}{n} = \mu.
\]

Since the $G_i$'s are pairwise independent, their variances will also add,
so
\begin{align*}
\variance{A_n}  = & \paren{\frac{1}{n}}^2 \variance{\sum_{i=1}^n G_i}
                        & (\variance{aR} = a^2\variance{R})\\
 = & \paren{\frac{1}{n}}^2 \sum_{i=1}^n \variance{G_i}
                        & \text{(linearity of variance)}\\
 = & \paren{\frac{1}{n}}^2 n\sigma^2\\
 = & \frac{\sigma^2}{n}.
\end{align*}

Now letting $R$ be $A_n$ in Chebyshev's Bound~(\ref{Chb})
yields~(\ref{Sndev}), as required.

\end{proof}


\end{document}
