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

\renewcommand{\coursecopyrightyear}{2002}
\renewcommand{\coursecopyrightnames}{Prof. Albert~R.~Meyer}

%\renewcommand{\problemdata}[5]{}

\begin{document}
\inclassproblems{13M}

%generalized weak law

\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance22.tex}

\begin{problem}
In this problem you will check a proof of the following:
\begin{theorem}\label{th:none}
Let $A_1, A_2, \dots A_n$ be independent events, and let $T$ be the
number of these events that occur.  The probability that none of the
events occur is at most $e^{-\expect{T}}$.
\end{theorem}

To prove Theorem~\ref{th:none}, note that
\begin{equation}\label{Tsum}
T = T_1 + T_2 + \dots + T_n,
\end{equation}
where $T_i$ is the indicator variable for the event $A_i$.  Also, remember
that
\begin{equation} \label{1+xeleq}
1 + x \leq e^x
\end{equation}
for all $x$ and
\begin{equation}
1 + x  \sim e^x \label{1+xesim}.
\end{equation}
Both~(\ref{1+xeleq}) and~(\ref{1+xesim}) follow from the Taylor's
expansion of $e^x$.

\bparts

\ppart
Justify each line in the following derivation:

\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \bar{A_1 \union A_2 \union \cdots \union A_n}\\
  & =  \pr{\bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_n}}\\
  & =  \prod_{i=1}^n \pr{\bar{A_i}}\\
  & =  \prod_{i=1}^n 1 - \pr{A_i}\\
  & \leq  \prod_{i=1}^n e^{-\pr{A_i}}\\
  & =  e^{-\sum_{i=1}^n \pr{A_i}}\\
  & =  e^{-\sum_{i=1}^n \expect{T_i}}\\
  & =  e^{-\expect{T}}.
\end{align*}
\end{proof}

\solution{
\begin{proof}
\begin{align*}
\pr{T = 0}
  & = \bar{A_1 \union A_2 \union \cdots \union A_n} & \text{(def. of $T$)}\\
  & =  \pr{\bar{A_1} \cap \bar{A_2} \cap \dots \cap \bar{A_n}} &
          \text{(De Morgan's law)}\\
  & =  \prod_{i=1}^n \pr{\bar{A_i}} & \text{(mutual independence of $A_i$'s)}\\
  & =  \prod_{i=1}^n 1 - \pr{A_i} & \text{(complement rule)}\\
  & \leq  \prod_{i=1}^n e^{-\pr{A_i}} & \text{(by~(\ref{1+xeleq}))}\\
  & =  e^{-\sum_{i=1}^n \pr{A_i}} & \text{(exponent algebra)}\\
  & =  e^{-\sum_{i=1}^n \expect{T_i}} & \text{(expectation of indicator variable)}\\
  & =  e^{-\expect{T}}. & \text{((\ref{Tsum}) \& linearity of expectation)}
\end{align*}
\end{proof}
}

\eparts

Two special cases of Theorem~\ref{th:none} are worth singling out
because they come up all the time.
\begin{corollary}\label{1/mtrials}
Suppose an event has probability $1/m$.  Then the probability that the
even will occur at least once in $m$ independent trials is approximately
$1- 1/e \approx 63\%$.  There is a 50\% chance the event will occur in $n
= \log 2 m \approx 0.69m$ trials.
\end{corollary}

\bparts

\ppart
Prove Corollary~\ref{1/mtrials}.

\solution{
In this case, $\pr{A_i}=1/m$ for $1\leq i \leq n$ and
\[
\expect{\text{\# occurrences}} = n \frac{1}{m} = \frac{n}{m}.
\]
So by Theorem~\ref{th:none},
\[
\pr{\text{no occurrence}} \leq e^{-(n/m)},
\]
and therefore
\begin{equation}\label{1-enm}
\pr{\text{at least one occurrence}} \geq 1 - e^{-(n/m)}.
\end{equation}
In fact, it follows from by~(\ref{1+xesim}), that the $\geq$
in~(\ref{1-enm}) is an approximate equality.

So if the number, $n$ of trials is $m$, we have
\[
\pr{\text{at least one occurrence}} \approx 1- e^{-(m/m)} = 1-\frac{1}{e}.
\]

If we want
\[
1 - e^{-(n/m)} \approx \pr{\text{at least one occurrence}} \approx
\frac{1}{2},
\]
then we need
\[
e^{-(n/m)} \approx \frac{1}{2},
\]
so taking log's we conclude
\[
n \approx m\log 2.
\]
}
\eparts

\end{problem}


%infinite variance
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance24.tex}
%carried over from 12F, with slight revision

\begin{problem}
(carried over from Friday)

Describe a natural-number valued random variable $R$ such that
$\expect{R}$ is finite but $\variance{R}$ is not.
\hint $\sum_{i=0}^\infty i/i^3 < \infty$, but $\sum_{i=0}^\infty i^2/i^3
= \infty$.

\solution{
Let $d = \sum_{i=1}^\infty \frac{1}{i^3}$.  Define $\pr{R=i} = \eqdef
1/di^3$ for $i>0$ and $\pr{R=0} \eqdef 0$.  This ensures
$\sum_{i=0}^\infty \pr{R=i} =1$ as required by the definition of random
variable.

So
\[
\expect{R} = \sum_{i=0}^\infty i \pr{R = i} = \sum_{i=1}^\infty
\frac{i}{di^3} = \sum_{i=1}^\infty \frac{1}{di^2} = c
\]
for some constant $c$.  But
\[
\variance{R} = \expect{R^2}-\expectsq{R} = 
(\sum_{i=0}^\infty i^2 \pr{R = i}) - c^2 =
(\sum_{i=1}^\infty \frac{i^2}{di^3}) - c^2 =
\frac{\sum_{i=1}^\infty \frac{1}{i}}{d} - c^2 = \infty.
\]}

\iffalse

\ppart Find such an $R$ where $\expect{R} =1$.

\solution{
Let $d = \sum_{i=1}^\infty \frac{1}{i^3}$.  Revise the
definition of $R$ above so that $\pr{R=i} = \eqdef 1/di^3$ for $i>0$ and
$\pr{R=0} \eqdef 0$.

Let $c = \sum_{i=1}^\infty \frac{1}{i^2}$.

 then we would have
\[
\expect{R} = \sum_{i=0}^\infty i \pr{R = i} =
\sum_{i=1}^\infty\frac{1}{ci^2} = 1.
\]
Because $c>1$, the number  }
\fi

\end{problemparts}
\end{problem}


%variance of |X+Y| independent uniform
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance13.tex}

%variance of X^2 uniform
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance14.tex}

%binomial tail re markov, cheby, chern
\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance7.tex}

%compare bounding formulas algebraically
\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance20.tex}

%keys in pocket; better for pset
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance15.tex}

%sample variance, better for pset
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance16.tex}

%spider for Chernoff bound
\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance18.tex}

%derive 1-sided, Chebyshev, better for pset
%\input{/a/class/6.042/spring02/freshRepository/probability-variance/variance23.tex}

\appendix
\section{Appendix}
\setcounter{secnumdepth}{0}

\subsection{Bounds on Deviation from the Mean}

\begin{theorem*}[Markov's Theorem]
 If R is a nonnegative random variable, then for all $x > 0$
\begin{equation}\label{M}
\pr{R \geq x} \leq \frac{\expect{R}}{x}.
\end{equation}
\end{theorem*}

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

\subsection{Weak Law of Large Numbers}
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$.

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

\begin{proof}
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{n\mu}{n} = \mu.
\]

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

Now Chebyshev's Bound tells us that for any random variable, $R$,
\[
\pr{\abs{R - \expect{R}} \geq x} \leq \frac{\variance{R}}{x^2}.
\]
So, letting $R$ be $S_n/n$ yields~(\ref{Sndev}), as required.

\end{proof}


\begin{theorem*}[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$,
\begin{equation}\label{Cher}
\pr{T \geq c \expect{T}} \leq \textup{exp}(- (c\ln c -c + 1) \expect{T}).
\end{equation}
\end{theorem*}

\end{document}
