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

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

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

\begin{document}
\inclassproblems{14W}

\begin{problem}(Carried over from Wednesday)

\begin{theorem*}[The strong law of large numbers] Let
$X_1,X_2,\dots$ be a sequence of independent and identically distributed
random variables, each having a finite mean $\mu=\expect{X_i}$.  Then,
with probability~1,
\[
\lim_{n\to\infty}\frac{X_1+X_2+\cdots+X_n}{n} = \mu.
\]
\end{theorem*}

To clarify the somewhat subtle difference between the Weak and Strong Laws
of Large Numbers, we will construct an example of a sequence
$X_1,X_2,\dots$ of mutually independent random variables that satisfies
the Weak Law of Large Numbers, but not the Strong Law.  The distribution
of $X_i$ will have to depend on $i$, because otherwise both laws would be
satisfied.\footnote{This problem is adapted from Grinstead \& Snell,
\emph{Intro. to Probability}, Ch.8, exercise 16, pp314--315, where is
credited to David Maslen.}

In particular, let $X_1,X_2,\dots$ be a sequence of mutually independent
random variables such that for each positive integer $i\geq 2$,
\[
\pr{X_i=i} = \frac{1}{2i\log i},\quad
\pr{X_i=-i} = \frac{1}{2i\log i},\quad
\pr{X_i=0} = 1 - \frac{1}{i\log i}.
\]
When $i=1$ we let $X_i=0$ with probability~1.  As usual, we let
$S_n \eqdef X_1+\cdots+X_n$.  Note that the mean of each $X_i$ is~0.

\bparts

\problempart
Show that $\variance{S_n} = \Theta(n^2/\log n)$.
\hint $n/\log n > i/\log i$ for $2 \leq i \leq n$. %$\int x/\log x\, dx = ???$

\solution{\begin{align}
\variance{S_n} & = \sum_{i=1}^\infty \variance{X_i} &\text{(independent variance
additivity)}\notag\\
  & = \variance{X_1}+ \sum_{i=2}^n \expect{X_i^2} - \expectsq{X_i}\notag\\
  & =  0+ \sum_{i=2}^n i^2\left( \frac{1}{i\log i} - 0\right)\notag\\
  & =  \sum_{i=2}^n \frac{i}{\log i}.\notag\\
  & = \Theta(n^2/\log n). & \text{(see below)}\label{Theta}
\end{align}

To justify~(\ref{Theta}), note that $x/\log x$ is increasing for $x>e$
since its derivative $(1/\log x) (1- 1/\log x)$ is positive.  So $n/\log n
\geq i/\log i$ for $2 \leq i \leq n$.  Therefore,
\begin{align*}
\frac{n^2}{\log n} & = \sum_{i=1}^n \frac{n}{\log n}\\
  & \geq \sum_{i=2}^n \frac{i}{\log i}\\
  & \geq \sum_{i=\ceil{n/2}}^n \frac{i}{\log i}\\
  & \geq \sum_{i=\ceil{n/2}}^n \frac{n/2}{\log n}\\
  & \geq \frac{n+1}{2} \frac{n/2}{\log n}\\
  & \geq \frac{1}{4}\frac{n^2}{\log n}.
\end{align*}
}

\problempart
Show that the sequence $X_1,X_2,\dots$ satisfies the Weak Law of Large
Numbers, \ie prove that for any $\epsilon>0$ 
\[
\lim_{n \to \infty} \pr{ \abs{\frac{S_n}{n}} \geq \epsilon } = 0.
\]

\solution{
\begin{align*}
\pr{\abs{\frac{S_n}{n}} \geq \epsilon} & =
  \pr{\abs{\frac{S_n}{n}-0} \geq \epsilon}\\
  &  \leq \variance{\frac{S_n}{n}}\frac{1}{\epsilon^2} & \text{(Chebychev Bound)}\\
  & = \frac{\variance{S_n}}{n^2}\frac{1}{\epsilon^2}\\
  & = \Theta(\frac{1}{\epsilon^2\log n}), & \text{(by~(\ref{Theta}))}
\end{align*}
which goes to zero as $n$ goes to $\infty$.
}

\end{problemparts}

We now show that the sequence $X_1,X_2,\dots$ does not satisfy the Strong
Law of Large Numbers.  Let $L$ be the event that $S_n/n\to 0$.  Then
because
\[
\frac{X_n}{n} =
\frac{S_n}{n} - \frac{n-1}{n}\frac{S_{n-1}}{n-1},
\]
we know that $L$ implies $X_n/n\to 0$.  From the definition of limits, we
conclude that if $L$ occurs, then the inequality $\abs{X_i}\geq i$ can
only be true for finitely many $i$.

\begin{problemparts}

\problempart\label{BC}
(The first Borel-Cantelli lemma.) 
Let $A_1,A_2,\dots$ be any infinite sequence of mutually independent
events such that
\begin{equation}\label{sai}
\sum_{i=1}^\infty \pr{A_i} = \infty.
\end{equation}
Prove that
\[
\pr{\text{infinitely many $A_i$ occur}} = 1.
\]
\hint We know from an in-class problem on Monday that the probability that
no $A_i$ with $i \geq r$ occurs is
\begin{equation}\label{-eT}
\leq  e^{-\expect{T_r}}
\end{equation}
where $T_r \eqdef \sum_{i=r}^\infty I_{A_i}$ is the number of events $A_i$
with $i\geq r$ that occur.

\solution{
\begin{align*}
\expect{T_r} & = \sum_{i=r}^\infty \expect{I_{A_i}}
         &\text{(linearity of expectation)} \\
  & = \sum_{i=r}^\infty \pr{A_i} & \text{(expectation of indicator
         variable)}\\
  & = \infty & \text{(by~(\ref{sai}))}.
\end{align*}
So it follows from~(\ref{-eT}) that the probability that no $A_i$ with $i
\geq r$ occurs is zero.  That is, the probability that only finitely many
$A_i$'s occur is zero, and hence the probability that infinitely many
occur is 1.
}

\problempart\label{divsum}
Show that
$\sum_{i=1}^\infty\pr{\abs{X_i}\geq i}$ diverges.  \hint $\int 1/(x
log x)\, dx = \log\log x$.

\solution{
$\pr{\abs{X_i}\geq i}= \frac{1}{i\log i}$, so
\begin{align*}
\sum_{i=1}^n \pr{\abs{X_i}\geq i} & = 0+ \sum_{i=2}^n \frac{1}{i\log i}\\
  & \geq \int_2^{n+1} \frac{1}{x\log x} dx\\
  & = \log\log (n + 1 ) - \log\log 2,
\end{align*}
and this last term approaches infinity and $n$ approaches infinity.
}

\problempart
Conclude that
\[
\pr{ \frac{S_n}{n} \to 0 }= 0,
\]
and hence that the Strong Law of Large Numbers fails for the
sequence $X_1,X_2,\dots$.  

\solution{
By parts~(\ref{BC}) and~(\ref{divsum}), the probability that $\abs{X_i}\geq i$
for only finitely many $i$ is zero.  Since $L$ implies that $\abs{X_i}\geq i$
for only finitely many $i$, we conclude $\pr{L}=0$.
}

\end{problemparts}
\end{problem}

\end{document}
