\documentclass{beamer}

%\usepackage[table]{xcolor}
\mode<presentation> {
  \usetheme{Boadilla}
%  \usetheme{Pittsburgh}
%\usefonttheme[2]{sans}
\renewcommand{\familydefault}{cmss}
%\usepackage{lmodern}
%\usepackage[T1]{fontenc}
%\usepackage{palatino}
%\usepackage{cmbright}
  \setbeamercovered{transparent}
\useinnertheme{rectangles}
}
%\usepackage{normalem}{ulem}
%\usepackage{colortbl, textcomp}
\setbeamercolor{normal text}{fg=black}
\setbeamercolor{structure}{fg= black}
\definecolor{trial}{cmyk}{1,0,0, 0}
\definecolor{trial2}{cmyk}{0.00,0,1, 0}
\definecolor{darkgreen}{rgb}{0,.4, 0.1}
\usepackage{array}
\beamertemplatesolidbackgroundcolor{white}  \setbeamercolor{alerted
text}{fg=red}

\setbeamertemplate{caption}[numbered]\newcounter{mylastframe}

%\usepackage{color}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage{colortbl}
%\usepackage[usenames, dvipsnames]{color}
%\setbeamertemplate{caption}[numbered]\newcounter{mylastframe}c
%\newcolumntype{Y}{\columncolor[cmyk]{0, 0, 1, 0}\raggedright}
%\newcolumntype{C}{\columncolor[cmyk]{1, 0, 0, 0}\raggedright}
%\newcolumntype{G}{\columncolor[rgb]{0, 1, 0}\raggedright}
%\newcolumntype{R}{\columncolor[rgb]{1, 0, 0}\raggedright}

%\begin{beamerboxesrounded}[upper=uppercol,lower=lowercol,shadow=true]{Block}
%$A = B$.
%\end{beamerboxesrounded}}
\renewcommand{\familydefault}{cmss}
%\usepackage[all]{xy}

\usepackage{tikz}
\usepackage{lipsum}

 \newenvironment{changemargin}[3]{%
 \begin{list}{}{%
 \setlength{\topsep}{0pt}%
 \setlength{\leftmargin}{#1}%
 \setlength{\rightmargin}{#2}%
 \setlength{\topmargin}{#3}%
 \setlength{\listparindent}{\parindent}%
 \setlength{\itemindent}{\parindent}%
 \setlength{\parsep}{\parskip}%
 }%
\item[]}{\end{list}}
\usetikzlibrary{arrows}
%\usepackage{palatino}
%\usepackage{eulervm}
\usecolortheme{lily}

\newtheorem{com}{Comment}
\newtheorem{lem} {Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{cor}{Corollary}
\newtheorem{obs}{Observation}
 \numberwithin{equation}{section}


\title[Methodology I] % (optional, nur bei langen Titeln nötig)
{Math Camp}

\author{Justin Grimmer}
\institute[Stanford University]{Associate Professor\\Department of Political Science \\  Stanford University}
\vspace{0.3in}

\date{September 22nd, 2016}

\begin{document}

\begin{frame}
\maketitle
\end{frame}



\begin{frame}
\frametitle{Inequalities and Limit Theorems}


\alert{Limit Theorems}
\begin{itemize}
\item[-] What happens when we consider a long sequence of random variables ?
\item[-] What can we reasonably infer from data?
\begin{itemize}
\item[-] Laws of large numbers: averages of random variables converge on expected value?
\item[-] Central Limit Theorems: sum of random variables have normal distribution?
\end{itemize}
\item[-] We'll focus on intuition for both, but we'll prove some stuff too.  
\end{itemize}

\alert{Review Session}


\end{frame}


\begin{frame}
\frametitle{Weak Law of Large Numbers}

Proof plan: 
\begin{itemize}
\item[-] Markov's Inequality
\item[-] Chebyshev's Inequality
\item[-] Weak Law of Large Numbers 
\end{itemize}


\end{frame}



\begin{frame}
\frametitle{Markov's Inequality}

\begin{prop}
Suppose $X$ is a random variable that takes on non-negative values.  Then, for all $a>0$, 
\begin{eqnarray}
P(X\geq a) & \leq & \frac{E[X]}{a} \nonumber 
\end{eqnarray}
\end{prop}

\end{frame}


\begin{frame}
\frametitle{Markov's Inequality} 


\begin{proof}
For $a>0$,  \pause 
\begin{eqnarray}
\invisible<1>{E[X] & = & \int_{0}^{\infty} x f(x) dx \nonumber \\} \pause 
 \invisible<1-2>{& = & \int_{0}^{a} x f(x) dx + \int_{a}^{\infty} x f(x) dx \nonumber } \pause 
\end{eqnarray}

\invisible<1-3>{Because $X\geq 0$, } \pause 

\begin{eqnarray}
\invisible<1-4>{E[X] \geq \int_{a}^{\infty} x f(x) dx  \geq \int_{a}^{\infty} a f(x)dx = a P(X \geq a )\nonumber \\} \pause 
\invisible<1-5>{\frac{E[X]}{a} \geq P(X \geq a )\nonumber } 
\end{eqnarray}


\end{proof}



\end{frame}

\begin{frame}
\frametitle{Chebyshev's Inequality} 

\begin{prop} 
If $X$ is a random variable with mean $\mu$ and variance $\sigma^2$, then, for any value $k>0$, 
\begin{eqnarray}
P(|X - \mu| \geq k) & \leq & \frac{\sigma^2}{k^2} \nonumber 
\end{eqnarray}

\end{prop}


\end{frame}

\begin{frame}
\frametitle{Chebyshev's Inequality} 


\begin{proof}
Define the random variable 
\begin{eqnarray}
 Y & = & (X - \mu)^2 \nonumber 
\end{eqnarray}

Where $\mu = E[X]$. 

\pause 

\invisible<1>{Then we know $Y$ is a non-negative random variable.  Set $a = k^2$.  \\} \pause 
\invisible<1-2>{Applying the inequality:} \pause 
\begin{eqnarray}
\invisible<1-3>{P(Y \geq k^2) \leq \frac{E[Y]}{k^2} \nonumber \\} \pause 
\invisible<1-4>{P( (X- \mu)^2 \geq k^2) \leq \frac{E[(X - \mu)^2]}{k^2} \nonumber \\} \pause 
\invisible<1-5>{P( (X- \mu)^2 \geq k^2) \leq \frac{\sigma^2}{k^2}\nonumber } 
\end{eqnarray}

\end{proof}

\end{frame}


\begin{frame}
\frametitle{Chebyshev's Inequality} 


Further we know that, 
\begin{eqnarray}
(X - \mu)^2  \geq k^2 \nonumber 
\end{eqnarray}

\pause 

\invisible<1>{Implies that } \pause 
\begin{eqnarray}
\invisible<1-2>{|X - \mu| \geq k \nonumber } \pause 
\end{eqnarray}

\invisible<1-3>{Thus, we have shown } \pause 
\begin{eqnarray}
\invisible<1-4>{P( |X- \mu| \geq k) \leq \frac{\sigma^2}{k^2}\nonumber } 
\end{eqnarray}

\end{frame}



\begin{frame}
\frametitle{Sequence of Random Variables}

Sequence of Independent and Identically, Distributed Random variables.
\begin{itemize}
\item[-] Sequence: $X_{1}, X_{2}, \hdots, X_{n}, \hdots $
\item[-] Think of a sequence as sampled \alert{data}:
\begin{itemize}
\item[-] Suppose we are drawing a sample of $N$ observations
\item[-] Each observation will be a random variable, say $X_{i}$
\item[-] With realization $x_{i}$ 
\end{itemize}
\end{itemize}

\end{frame}


\begin{frame}
\frametitle{Mean/Variance of Sample Mean}

\begin{prop}
Let $X_{1}, X_{2}, \hdots, X_{n}$ be a random sample from a distribution with mean $\mu$ and variance $\sigma^2$.  Let $\bar{X}_{n}$ be the sample mean.  Then 
$E[\bar{X}_{n}] = \mu$ and var$(\bar{X}_{n}) = \frac{\sigma^2}{n}$
\end{prop}

\pause 
\begin{proof}

\begin{eqnarray}
\invisible<1>{E[\bar{X}_{n}] & = & \frac{1}{n}\sum_{i=1}^{n} E[X_{i}] \nonumber \\} \pause 
\invisible<1-2>{& = & \frac{1}{n} n \mu  = \mu \nonumber } 
\end{eqnarray}



\end{proof}


\end{frame}


\begin{frame}
\frametitle{Mean/Variance of Sample Mean}


\pause 
\begin{eqnarray}
\invisible<1>{\text{var}(\bar{X}_{n}) & = & \frac{1}{n^2} \text{var}(\sum_{i=1}^{n} X_{i}) \nonumber \\} \pause 
 \invisible<1-2>{&= & \frac{1}{n^2} \sum_{i=1}^{n} \text{var}(X_{i}) \nonumber \\} \pause 
  \invisible<1-3>{& = & \frac{1}{n^2} n \sigma^2 = \frac{\sigma^2}{n} \nonumber } 
\end{eqnarray}


\end{frame}



\begin{frame}
\frametitle{Weak Law of Large Numbers} 

\begin{prop}
Suppose $X_{1}, X_{2}, \hdots, X_{n}$ is a random sample from a distribution with mean $\mu$ and $Var(X_{i})= \sigma^2$.  Then, for all $\epsilon >0$, 
\begin{eqnarray}
P\left\{ \left| \frac{X_{1} + X_{2} + \hdots + X_{n} }{n} -\mu \right| \geq \epsilon \right\} \rightarrow 0 \text{ as } n \rightarrow \infty \nonumber 
\end{eqnarray}

\end{prop}


\end{frame}


\begin{frame}
\frametitle{Weak Law of Large Numbers}

\begin{proof}
From our previous proposition \pause 
\begin{eqnarray}
\invisible<1>{\frac{\text{E}[X_{1} + X_{2} + \cdots + X_{n} ]}{n} & = & \frac{\sum_{i=1}^{n} E[X_{i}] }{n}  = \mu \nonumber} \pause 
\end{eqnarray}
\invisible<1-2>{Further, } \pause 
\begin{eqnarray}
\invisible<1-3>{\text{E}[ (\frac{\sum_{i=1}^{n} X_{i} - \mu}{n} )^2] = \frac{\text{Var}(X_{1} + X_{2} + \cdots + X_{n} )}{n^2} & = & \frac{ \sum_{i=1}^{n} \text{Var}(X_{i}) }{n^2} = \frac{\sigma^2}{n} \nonumber } \pause 
\end{eqnarray}
\invisible<1-4>{Apply Chebyshev's Inequality: } \pause 
\begin{eqnarray}
\invisible<1-5>{P\left\{ \left| \frac{X_{1} + X_{2} + \hdots + X_{n} }{n} -\mu \right| \geq \epsilon \right\}\leq \frac{\sigma^2}{n \epsilon^2} \nonumber }
\end{eqnarray}

\end{proof}


\end{frame}

\begin{frame}
Suppose $X_{1}, X_{2}, \hdots$ are iid normal distributions,
\begin{eqnarray}
X_{i} & \sim & \text{Normal}(0, 10) \nonumber 
\end{eqnarray}

\begin{eqnarray} 
P\left\{ \left| \frac{X_{1} + X_{2} + \hdots + X_{n} }{n} -\mu \right| \geq 0.1 \right\} \text{ as } n \rightarrow \infty\nonumber 
\end{eqnarray}
\pause 


\only<1-2>{\invisible<1>{\begin{center}
\scalebox{0.4}{\includegraphics{c8fig.pdf}}
\end{center}

}

}

\only<3-6>{Suppose we want to guarantee that we have at most a $0.01$ probability of being more than $0.1$ away from the true $\mu$.  How big do we need $n$?\pause 
\begin{eqnarray}
\invisible<1-3>{0.01 & = & \frac{10}{n (0.1^2) } \nonumber} \pause  \\
\invisible<1-4>{n & = & \frac{1000}{0.01} \nonumber } \pause \\
\invisible<1-5>{n & = & 100,000 } \nonumber 
\end{eqnarray}
}


\end{frame}

%
%\begin{frame}
%\frametitle{Strong Law of Large Numbers}
%Statement\\
%Difference: this says equality, other says that it gets really close (but fails to establish equality) \\
%Give intuition for this 
%\end{frame}
%
%
%
%\begin{frame}
%\frametitle{Central Limit Theorem} 
%
%Statement, intuition, and examples.  
%
%
%\end{frame}



\begin{frame}
\frametitle{Sequences and Convergence} 

Sequence (refresher):\\
\begin{eqnarray}
\left\{a_{i} \right\}_{i=1}^{\infty} & =  & \left\{a_{1}, a_{2}, a_{3}, \hdots, a_{n}, \hdots, \right\} \nonumber 
\end{eqnarray}


\begin{defn}
We say that the sequence $\left\{a_{i} \right\}_{i=1}^{\infty} $ converges to real number $A$ if for each $\epsilon>0$ there is a positive integer $N$ such that for $n\geq N$, $|a_{n} - A| < \epsilon$
\end{defn}


\end{frame}

\begin{frame}
\frametitle{Sequences and Convergence} 


Sequence of functions: 
\begin{eqnarray}
\left\{ f_{i} \right\}_{i=1}^{\infty}  & = & \left\{f_{1}, f_{2}, f_{3}, \hdots, f_{n}, \hdots, \right\}\nonumber 
\end{eqnarray}

\begin{defn}
Suppose $f_{i}: X \rightarrow \Re$ for all $i$.  Then $\left\{ f_{i} \right\}_{i=1}^{\infty} $ converges \alert{pointwise} to $f$ if, for all $x \in X$ and $\epsilon> 0$, there is an $N$ such that for all $n\geq N$,  
\begin{eqnarray}
|f_{n} (x)  - f(x)|<\epsilon \nonumber 
\end{eqnarray}
\end{defn}

This is as strong of a statement as we're likely to make in statistics \\



\end{frame}





\begin{frame}
\frametitle{Convergence Definitions}

Define $\widehat{\theta}_{n}$ to be estimator for $\theta$ based on $n$ observations.  \pause  \\
\invisible<1>{\alert{Sequence} of estimators: increasing sample size} \pause \\
\begin{eqnarray}
\invisible<1-2>{\left\{\widehat{\theta}_{i}\right\}_{i=1}^{n} &= & \left\{\widehat{\theta}_{1}, \widehat{\theta}_{2},    \widehat{\theta}_{3}, \hdots, \widehat{\theta}_{n} \right\} \nonumber} \pause  
 \end{eqnarray}

\invisible<1-3>{Question: What can we say about $\left\{\widehat{\theta}_{i}\right\}_{i=1}^{n}$ as $n\rightarrow \infty$? } \pause 
\begin{itemize}
\invisible<1-4>{\item[-] What is the probability $\widehat{\theta}_{n}$ differs from $\theta$?  } \pause 
\invisible<1-5>{\item[-] What is the probability $\left\{\widehat{\theta}_{i}\right\}_{i=1}^{n} $ converges to $\theta$? } \pause 
\invisible<1-6>{\item[-] What is sampling distribution of $\widehat{\theta}_{n}$ as $n \rightarrow \infty$ ? } 
\end{itemize}


\end{frame}


\begin{frame}
\frametitle{Convergence in Probability}

\pause 
\invisible<1>{\begin{defn} 
We will say the sequence $\widehat{\theta}_{n}$ converges in probability to $\theta$ (perhaps a non-degenerate RV)  if, 
\begin{eqnarray}
\lim_{n\rightarrow\infty} Prob(|\widehat{\theta}_{n} - \theta | > \epsilon ) = 0 \nonumber 
\end{eqnarray}
For any $\epsilon>0$
\end{defn}} \pause 

\begin{itemize}
\invisible<1-2>{\item[-] $\epsilon$ is a tolerance parameter: how much error around $\theta$?} \pause 
\invisible<1-3>{\item[-] In the limit, convergence in probability implies sampling distribution collapses on a spike at $\theta$} \pause 
\invisible<1-4>{\item[-] $\left\{\widehat{\theta}_{i}\right\}$ need not actually converge to $\theta$, only P($|\theta_{n}$ - $\theta| > \epsilon) = 0 $ } 
\end{itemize}

\end{frame}


\begin{frame}
\frametitle{Example (Cassella and Burger)} 
\pause 
\invisible<1>{Suppose $S \sim $ Uniform(0,1).  Define $X(s) = s$. } \pause \\
\invisible<1-2>{Suppose $X_{n}$ is define as follows: } \pause 
\begin{eqnarray}
\invisible<1-3>{X_{1}(s) = s + I(s \in [0,1]) & ,&  X_{2} (s)  = s +  I(s \in [0,1/2]) \nonumber \\} \pause
\invisible<1-4>{ X_{3}(s)  = s + I(s \in [1/2, 1])& ,&  X_{4}(s) = s + I(s \in [0,1/3]) \nonumber \\} \pause
\invisible<1-5>{ X_{5} (s)  =  s + I(s \in [1/3,2/3]) & ,&  X_{6}(s) = s + I(s \in [2/3, 1]) \nonumber } \pause
\end{eqnarray}
\invisible<1-6>{Does $X_{n}(s)$ pointwise converge to $X(s)$? \\} \pause
\invisible<1-7>{Does $X_{n}(s) $ converge in probability to $X(s)$?} \pause

\begin{eqnarray}
\invisible<1-8>{P(|X_{n} - X | > \epsilon)  & = &P ( s \in [l_{n}, u_{n} ] ) \nonumber } \pause
\end{eqnarray} 

\invisible<1-9>{Length of $[l_{n}, u_{n}] \rightarrow 0  \Rightarrow P ( s \in [L_{n}, U_{n} ] )   = 0 $} 


\end{frame}





\begin{frame}
\frametitle{Almost Sure Convergence} 

\pause 
\begin{defn} 
\invisible<1>{We will say the sequence $\widehat{\theta}_{n}$ converges almost surely to $\theta$ if, 
\begin{eqnarray}
Prob(\lim_{n \rightarrow \infty} |\widehat{\theta}_{n} - \theta| > \epsilon ) = 0 \nonumber } \pause 
\end{eqnarray}

\end{defn}


\begin{itemize}
\invisible<1-2>{\item[-] Stronger: says that sequence converges to $\theta$ (almost everywhere) ) } \pause 
\invisible<1-3>{\item[-] Think about definition of random variable: $\widehat{\theta}_{n}$ is a function from sample space to real line.} \pause 
\invisible<1-4>{\item[-]  Almost sure says that, for all outcomes ($s$)  in  sample space ($S$) $s \in S$, } \pause 
\begin{eqnarray} 
\invisible<1-5>{\widehat{\theta}_{n}(s) & \rightarrow& \theta(s) \nonumber } \pause 
\end{eqnarray}
\invisible<1-6>{\item[] Except for a subset $\mathcal{N} \subset S $ such that $P(\mathcal{N}) = 0 $.  } 
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Example (Cassella and Burger)} 

Suppose $S \sim $ Uniform(0,1).\\
Suppose $X_{n}$ is define as follows: 
\begin{eqnarray}
X_{1}(s) = s + I(s \in [0,1]) & ,&  X_{2} (s)  = s +  I(s \in [0,1/2]) \nonumber \\
 X_{3}(s)  = s + I(s \in [1/2, 1])& ,&  X_{4}(s) = s + I(s \in [0,1/3]) \nonumber \\
 X_{5} (s)  =  s + I(s \in [1/3,2/3]) & ,&  X_{6}(s) = s + I(s \in [2/3, 1]) \nonumber 
\end{eqnarray}
Does $X_{n}(s) $ converge almost surely to $X(s) = s$?\pause 

\invisible<1>{\alert{No!}: the sequence doesn't converge for each $s$} \pause \\
\invisible<1-2>{For each value of $s$ the sequence varies between $s$ and $s + 1$ infinitely often } 
\end{frame}







\begin{frame}
\frametitle{Convergence in Distribution}
We've talked about $\widehat{\theta}_{n}$'s sampling distribution converging to a normal distribution.\pause   \\
\invisible<1>{This is \alert{convergence in distribution} }\pause 

\begin{defn}
\invisible<1-2>{$\widehat{\theta}_{n}$, with cdf $F_{n}(x)$,  converges in distribution to random variable $Y$ with cdf $F(x)$ if 
\begin{eqnarray}
\lim_{n\rightarrow \infty} |F_{n} (x) - F(x) | = 0 \nonumber 
\end{eqnarray} 
For all $x \in \Re$ where $F(x)$ is continuous.  } \pause 
\end{defn}

\begin{itemize}
\invisible<1-3>{\item[-] Weakest form of convergence almost sure $\rightarrow$ probability $\rightarrow$ distribution } \pause 
\invisible<1-4>{\item[-] Says that cdfs are equal, says nothing about convergence of underlying RV } \pause 
\invisible<1-5>{\item[-] Useful for justifying use of some sampling distributions } 
\end{itemize}

\end{frame}


\begin{frame}
\frametitle{Convergence in Distribution $\not \Rightarrow$ Convergence in Probability}

Define $X \sim N(0,1)$ and each $X_{n} = - X$.  Then:

$X_{n} \sim N(0,1)$ for all $n$ so $X_{n}$ trivially converges to $X$. But, 
\begin{eqnarray}
P(|X_{n} - X| > \epsilon ) & = & P(|X + X| > \epsilon) \nonumber \\
							& = & P( |2X| > \epsilon) \nonumber \\
						    & =  & P(|X| > \epsilon/2) \not \leadsto 0 \nonumber 
\end{eqnarray}						    





\end{frame}


\begin{frame}
\frametitle{Central Limit Theorem}

\begin{prop}
Let $X_{1}$, $X_{2}, \hdots$ be a sequence of independent random variables with mean $\mu$ and variance $\sigma^2$.  Let $X_{i}$ have a cdf $P(X_{i} \leq x) = F(x)$ and moment generating function $M(t) = E[e^{tX_{i}}]$ .  Let $S_{n} = \sum_{i=1}^{n} X_{i}$.  Then 

\begin{eqnarray}
\lim_{n\rightarrow \infty} P\left( \frac{S_{n} - \mu n }{\sigma\sqrt{n}} \leq x \right) &  = &  \frac{1}{\sqrt{2\pi} } \int_{-\infty}^{x} \exp\left( -\frac{z^{2} }{2} \right) dz \nonumber 
\end{eqnarray}


\end{prop}

\pause 
\invisible<1>{Proof plan:}
\begin{itemize}
\invisible<1>{\item[1)] Rely on Fact that convergence of MGFs$\leadsto$ convergence in CDFs}
\invisible<1>{\item[2)] Show that MGFs, in limit, converge on normal MGF}
\end{itemize}


\end{frame}


\begin{frame}

\begin{prop}
Let $F_{n}$ be a sequence of cumulative distribution functions with the corresponding moment generating functions $M_{n}$.  $F$ be a cdf with the moment generating functions $M$.  If $\lim_{n\rightarrow \infty} M_{n}(t) \rightarrow M(t)$ for all $t$ in some interval, then $F_{n}(x) \leadsto F(x)$ for all $x$ (when $F$ is continuous).  
\end{prop}

\pause 
\invisible<1>{\begin{prop}
Suppose $\lim_{n\rightarrow \infty} a_{n} \rightarrow a$, then 
\begin{eqnarray}
\lim_{n\rightarrow \infty} \left( 1 + \frac{a_{n}}{n}\right)^{n}  & = & e^{a} \nonumber 
\end{eqnarray}

\end{prop}
}

\pause 

\invisible<1-2>{\begin{prop}
Suppose $M(t)$ is a moment generating function some random variable $X$.  Then $M(0) = 1$.  
\end{prop}}



\end{frame}




\begin{frame}
\frametitle{Proof of Central Limit Theorem (Courtsey of Swarthmore Notes)}

\large{Proof.}
Suppose $X_{1}, \hdots, X_{n}$ are iid variables with $E[X] = 0 $, variance $\sigma^{2}_{x}$, Moment Generating Function (MGF) $M_{x}(t)$. \pause  \\

\invisible<1>{Let $S_{n} = \sum_{i=1}^{n} X_{i}$ and $Z_{n} = \frac{S_{n}}{\sigma_{x} \sqrt{n}}$. } \pause \\
\invisible<1-2>{$M_{S_{n}}  = (M_{x}(t))^{n} $ and $M_{Z_{n}} (t) = \left(M_{x} \left(\frac{t}{\sigma_{x} \sqrt{n}}    \right)    \right)^{n}$} \pause \\
\invisible<1-3>{Using Taylor's Theorem we can write
\begin{eqnarray}
M_{x} (s) & = & M_{x} (0)  + s M^{'}_{x}(0) + \frac{1}{2} s^2 M_{x}^{''}(0) + e_{s} \nonumber 
\end{eqnarray}
$e_{s}/s^2 \rightarrow 0 $ as $s\rightarrow 0$.  } 

\end{frame}


\begin{frame}
\begin{eqnarray}
M_{x} (s) & = & M_{x} (0)  + s M^{'}_{x}(0) + \frac{1}{2} s^2 M_{x}^{''}(0) + e_{s} \nonumber 
\end{eqnarray}

Filling  in the values we have 
\begin{eqnarray}
M_{x} (s) & = & 1  + 0 + \frac{\sigma_{x}^{2}}{2} s^2  + \underbrace{e_{s}}_{\text{Goes to zero}} \nonumber 
\end{eqnarray}

Set $s = \frac{t}{\sigma_{x} \sqrt{n}} $ $\lim_{n\rightarrow \infty} s \rightarrow 0$.  Then 

\begin{eqnarray}
M_{Z_{n}}(t) & = & \left(1 + \frac{\sigma_{x}^{2}}{2}\left( \frac{t}{\sigma_{x} \sqrt{n}} \right)^{2} \right)^{n} \nonumber \\
& = & \left( 1 + \frac{t^{2}/2}{n} \right)^{n} \nonumber \\
\lim_{n\rightarrow \infty} M_{Z_{n}}(t) & = & e^{\frac{t^2}{2}}\nonumber 
\end{eqnarray}

\end{frame}


\begin{frame}
\alert{Review Time}

\end{frame}




\end{document}



\begin{frame}
\frametitle{Interpreting Causal Effects}

Rubin Causal Model: \pause 
\begin{itemize}
\invisible<1>{\item[-] $Y_{i}(1)$: response under treatment} \pause 
\invisible<1-2>{\item[-] $Y_{i}(0)$: response under control } \pause 
\end{itemize}
\invisible<1-3>{Individual Treatment Effect: $Y_{i}(1) - Y_{i}(0)$} \pause  \\
\invisible<1-4>{Fundamental problem of causal inference:}\pause \\
\only<1-6>{\invisible<1-5>{$Y_{i}(1) - Y_{i}(0)$}} \pause
\only<7->{\invisible<8>{$Y_{i}(1)$} - \invisible<1-7>{$Y_{i}(0)$}} \pause \pause \pause \\
\invisible<1-9>{ATE $= E[Y(1) - Y(0)]$ } 




\end{frame}






\begin{frame}
\frametitle{Observational Studies and Causal Inference}


\alert{Experimental} studies:\pause 
\begin{itemize}
\invisible<1>{\item[-] Treatment under control of analyst} 
\invisible<1>{\item[-] Random assignment, estimate
\begin{eqnarray}
\widehat{ATE} = E[Y(1)| T = 1] - E[Y(0) | T=0] \nonumber 
\end{eqnarray}
Because $E[Y(1)] = E[Y(1)|T= 1] = \alert{E[Y(1)| T = 0]} $ and $E[Y(0)] = E[Y(0)|T= 0] = \alert{E[Y(0)| T = 1]} $

}  \pause 
\end{itemize}
\invisible<1-2>{\alert{Observational} } \pause 
\begin{itemize}
\invisible<1-3>{\item[-] Units (people, countries) control their treatment status} \pause 
\invisible<1-4>{\item[-] \alert{Selection}: treatment and control groups differ systematically} \pause 
\begin{itemize}
\invisible<1-5>{\item[-] $E[Y(1)|T=1] \neq E[Y(1) |T = 0] $, $[EY(0)|T =0 ] \neq E[Y(0)|T = 1] $} \pause 
\invisible<1-6>{\item[-] Observables: things we can see, measure, and use in our study} \pause 
\invisible<1-7>{\item[-] Unobservables: not observables (big problem)} \pause 
\end{itemize}
\invisible<1-8>{\item[-]  Naive difference in means will be biased} \pause 
\invisible<1-9>{\item[-] Many, many, potential strategies for limiting bias} \pause 
\invisible<1-10>{\item[-] \alert{Regression is just one method}} 
\end{itemize}



\end{frame}


\begin{frame}
\frametitle{The Problem of Selection} 

\begin{eqnarray} 
\text{ATE} &= & E[Y(1) - Y(0) ] \nonumber  \pause \\
\invisible<1>{& = & E[Y(1)] - E[Y(0) ] \nonumber } \pause \\
\invisible<1-2>{ & =& \{\alert{E[Y(1) | T = 1]}  \alert{Pr(T= 1)} + \textcolor{blue}{E[Y(1) | T = 0 ]}  \alert{Pr(T = 0 )} \}   \nonumber \\
 & &- \{ \alert{E[Y(0) | T= 0 ] Pr(T =0 )} +  \textcolor{blue}{E[Y(0) | T=1]} \alert{Pr(T = 1)} \} \nonumber } \pause 
\end{eqnarray}

\invisible<1-3>{\alert{There is no assumption free method for estimating quantities in} \textcolor{blue}{blue}\\} \pause
\invisible<1-4>{Experiments:} \pause
\begin{itemize}
\invisible<1-5>{\item[-] Control assignment, learn about counterfactual values} \pause
\end{itemize}
\invisible<1-6>{Observational studies:} \pause
\begin{itemize}
\invisible<1-7>{\item[-] Assignment not controlled} \pause
\invisible<1-8>{\item[-] \alert{Problem}: how do we learn about counterfactuals in the face of selection?} 
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Manski Bound} 

What can we learn in the face of selection?  \pause \\
\invisible<1>{Suppose that we have a dichotomous dependent variable } \pause 
\begin{itemize}
\invisible<1-2>{\item[-] Smallest ATE: $-1$ } \pause 
\invisible<1-3>{\item[-] Largest ATE: $1$} \pause 
\invisible<1-4>{\item[-] Length: $2$ } \pause 
\invisible<1-5>{\item[-] $-1< ATE<1$} \pause 
\end{itemize}
\invisible<1-6>{\alert{Manksi Bounds}: \\} \pause 
\begin{itemize}
\invisible<1-7>{\item[-] Interval that contains true ATE with probability 1} \pause 
\invisible<1-8>{\item[-] Reduces interval length to $1$ } \pause 
\invisible<1-9>{\item[-] \alert{Requires no additional assumptions} } 
\end{itemize}


\end{frame}

\begin{frame}
\frametitle{Manski Bound} 
Note that: \\
$0\leq E[Y(1) | T = 0 ] \leq 1$ \pause \\
\invisible<1>{And that: \\
$0 \leq E[Y(0)| T=1] \leq 1$} \pause 

\invisible<1-2>{And recall that, } \pause 
\footnotesize
\begin{eqnarray}
\invisible<1-3>{ATE & =& \{\alert{E[Y(1) | T = 1]}  \alert{Pr(T= 1)} + \textcolor{blue}{E[Y(1) | T = 0 ]}  \alert{Pr(T = 0 )} \}   \nonumber \\
 & &- \{ \alert{E[Y(0) | T= 0 ] Pr(T =0 )} +  \textcolor{blue}{E[Y(0) | T=1]} \alert{Pr(T = 1)} \} \nonumber \\
 & = & \alert{E[Y(1) | T = 1] \pi} + \textcolor{blue}{E[Y(1) | T = 0 ]} \alert{(1- \pi)} \nonumber \\
 & & - \alert{E[Y(0) | T= 0 ] (1- \pi)} - \textcolor{blue}{E[Y(0) | T=1]}\alert{\pi} \nonumber } \pause 
 \end{eqnarray}
\invisible<1-4>{So, we can form bounds } \pause 
\begin{eqnarray} 
\invisible<1-5>{E[Y(1)|T=1] \pi -  (1-\pi) E[Y(0)| T= 0] - \pi } & & \nonumber  \\
\invisible<1-5>{<  ATE} \pause \invisible<1-6>{  < & & \nonumber \\
 E[Y(1)|T= ] \pi - (1-\pi) E[Y(0)| T= 0] + 1 - \pi   } & &\nonumber 
\end{eqnarray} 

\end{frame}

\begin{frame}
\frametitle{Manski Bound} 

The Manski bound \pause \\
\invisible<1>{$[\text{Average(Treat)} \pi -  (1-\pi) \text{Average(Control)}- \pi , $\\
\hspace{1in} $\text{Average(Treat)}\pi -  (1-\pi) \text{Average(Control)} + 1 - \pi ]$\\
 and has length $1$.  }\pause 


\invisible<1-2>{From Keele 2009: Presidential Visits + Congressional Wins} \pause 
\begin{itemize}
\invisible<1-3>{\item[-] $\pi = 0.06$} \pause 
\invisible<1-4>{\item[-] $E[Y(1)|T=1] = 18/21 = 0.857$} \pause 
\invisible<1-5>{\item[-] $E[Y(0)|T = 0] = 163/(327) =0.498$} \pause 
\end{itemize}
\invisible<1-6>{Bound is then:} \pause 
\begin{eqnarray}
\invisible<1-7>{&&[0.86\times 0.06 - 0.94\times 0.498 - 0.06  \textbf{,}  0.86\times 0.06 - 0.94\times 0.498 + 0.94] \nonumber \\
&&[-0.476  ,  0.523 ] \nonumber } \pause 
\end{eqnarray}



\begin{itemize}
\invisible<1-8>{\item[-] Further assumptions can narrow bounds} \pause 
\invisible<1-9>{\item[-] \alert{Law of Decreasing Credibility}: the credibility of inference decreases with the strength of the assumptions maintained} 
\end{itemize} 


\end{frame}

\begin{frame}
\frametitle{Causal Inference Via Stratification} 

Selection on observables:\pause 
\begin{itemize}
\invisible<1>{\item[-] Suppose that treatment is systematically related to outcomes (not ignorable) } \pause 
\begin{itemize}
\invisible<1-2>{\item[-] $E[Y(1)|D=1] \neq E[Y(1)|D =0]$ } \pause 
\invisible<1-3>{\item[-] $E[Y(0)|D=1] \neq E[Y(0)|D =0] $} \pause 
\invisible<1-4>{\item[-] Implies that Naive difference is not an unbiased estimate of ATE.  } \pause 
\end{itemize}
\invisible<1-5>{\item[-] Suppose there exists dichotomous variable $S$ such that,} \pause 
\begin{itemize}
\invisible<1-6>{\item[1)] $E[Y(1)|D=1, S]  =  E[Y(1)|D =0, S]$ } \pause 
\invisible<1-7>{\item[2)]  $E[Y(0)|D=1, S]  =  E[Y(0)|D =0, S] $} \pause 
\end{itemize}
\end{itemize}

\invisible<1-8>{\begin{prop} 
Suppose there exists $S$ such that $1)$ and $2)$ hold.  Then, we can obtain unbiased estimates for 
\begin{itemize}
\item[1)] $E[ATE|S=1] \equiv$ ATE, Given $S = 1$
\item[2)] $E[ATE|S =0] \equiv$ ATE, Given $S = 0$
\item[3)] ATE
\end{itemize}
\end{prop}}

\end{frame}

\begin{frame}
Idea: \pause 
\begin{itemize}
\invisible<1>{\item[1)] Average Treatment effect with strata, $S=1$} \pause 
\begin{itemize}
\invisible<1-2>{\item[-] Average(Treatment) - Average(Control) , for all units with $S=1$} \pause 
\end{itemize}
\invisible<1-3>{\item[2)] Average Treatment effect with strata, $S=0$} \pause 
\begin{itemize}
\invisible<1-4>{\item[-] Average(Treatment) - Average(Control) , for all units with $S=0$} \pause 
\end{itemize}
\invisible<1-5>{\item[3)] Average Treatment Effect} \pause 
\begin{itemize}
\invisible<1-6>{\item[-] Calculate Average(Treatment) - Average(Control) within each strata, $E[ATE|S]$} \pause 
\invisible<1-7>{\item[-] $ATE = \sum_{s=0}^{1} E[ATE|S]\times Pr(S) $} 
\end{itemize}
\end{itemize}

\end{frame}



\begin{frame}

\frametitle{Proof}
$E[Y(1)|S =1, D=1 ] - E[Y(0) | S=0, D= 0 ]$\pause 
\begin{eqnarray}
 \invisible<1>{& = & \{\text{Pr}(D=1|S=1)E[Y(1)|S=1, D=1] \nonumber \\
 & &+  \text{Pr}(D=0|S=1) E[Y(1)|S=1, D=1] \}\nonumber \\
& &-  \{\text{Pr}(D=1|S=1) E[Y(0)|S=1, D=0] \nonumber \\
&  &+   \text{Pr}(D=0|S=1) E[Y(0)| S= 1, D= 0 ] \} \nonumber \\} \pause 
\invisible<1-2>{ & = & \{\text{Pr}(D=1|S=1)E[Y(1)|S=1, D=1] \nonumber \\
 & &+  \text{Pr}(D=0|S=1) E[Y(1)|S=1, D=0] \}\nonumber \\
& &-  \{\text{Pr}(D=1|S=1) E[Y(0)|S=1, D=1] \nonumber \\
&  &+   \text{Pr}(D=0|S=1) E[Y(0)| S= 1, D= 0 ] \} \nonumber \\} \pause 
\invisible<1-3>{& = & E[ATE|S=1] \nonumber } 
\end{eqnarray}

\end{frame}







\begin{frame}
\frametitle{Causal Inference via Stratification: Example}

We are interested in the causal effect of \alert{incumbency} on reelection.  \\
\begin{itemize}
\item[-] $T=1$, Incumbent
\item[-] $T= 0$, Challenger
\end{itemize}
$Y_{i}(T)$ result of election. \\
Incumbency obviously not assigned at random.   \\
But suppose we have a dichotomous measure of candidate quality 
\begin{itemize}
\item[-] $S=1$, High quality
\item[-] $S=0$, Low quality
\end{itemize}
And that incumbency is as good as random, given $S$.  \\
We're interested in obtaining
\begin{eqnarray}
ATE & = & E[Y(1) - Y(0) ] \nonumber 
\end{eqnarray}

What if we don't condition on candidate quality?


\end{frame}

\begin{frame}

Joint Distribution of Treat and Strata

\small
\begin{tabular}{c|c|c|c}
\hline
 & T = 1 & T = 0 &  P(S)\\
 \hline
 S = 1 & 0.4 & 0.2 & 0.6 \\
 \hline
 S = 0 & 0.1 & 0.3 & 0.4 \\
 \hline
P(T) & 0.5  & 0.5 & \\
\hline 
\end{tabular}
\pause 

\invisible<1>{Potential Outcomes} \pause 
\invisible<1-2>{\begin{tabular}{c|c|c|c}
 & Control & Treat & ATE$|S$ \\
 \hline
 S = 1 &  $E[Y(0)|S = 1 ]$ = 0.5 & $E[Y(1)|S = 1]$ = 0.7 & 0.2 \\
 \hline
 S = 0 & $E[Y(0) | S= 0 ]$ = 0.38 & $E[Y(1)| S = 0 ]$= 0.4 & 0.02 \\
 \end{tabular}} \pause 
 \footnotesize
 
\invisible<1-3>{True $ATE$  = $0.2 \times 0.6 + 0.02 \times 0.4$ = \textcolor{blue}{0.128} } \pause \\
\invisible<1-4>{Naive difference in means: } \pause 
\begin{eqnarray}
\invisible<1-5>{E[Y(1)|T= 1] & = & 0.7 \times P(S=1|D=1) \nonumber \\
 & & + 0.4 \times P(S=0 | D= 1) \nonumber \\} \pause 
 \invisible<1-6>{& = & 0.7 \times \frac{4}{5} + 0.4 \times \frac{1}{5} = \alert{0.64} \nonumber \\} \pause 
\invisible<1-7>{ E[Y(0)|T= 0] & =& 0.5 \times \frac{2}{5} + 0.3\times\frac{3}{5} = \alert{0.38} \nonumber \\} \pause 
\invisible<1-8>{ E[Y(1)|T=1] - E[Y(0)|T= 0] & =& 0.64 - 0.38 \nonumber \\} \pause 
\invisible<1-9>{  & =& \alert{0.26} \nonumber } \pause
\end{eqnarray}


\invisible<1-10>{\alert{Why?}: those with bigger treatment effects more likely to select into treatment \\} \pause 
\invisible<1-11>{\alert{Confound} effect of $T$ with differences across $S$}
\end{frame}


\begin{frame}
\frametitle{With Stratification}
\pause 
\begin{eqnarray}
\invisible<1>{E[Y(1)|T=1, S= 1]  & = & 0.7 \nonumber \\
E[Y(0)|T=0, S =1] & = & 0.5 \nonumber \\
E[Y(1)|T =1, S= 0] & = & 0.4 \nonumber \\
E[Y(0)|T =0 , S =0 ] & = & 0.38 \nonumber } \pause 
\end{eqnarray}
\invisible<1-2>{$ \sum_{i=1}^{2}\left(E[Y(1)|S=i, T=1]  - E[Y(0)|S=i, T=0]\right) \text{Pr}(S=i) = $  \\} \pause 
\invisible<1-3>{$\left(0.7 - 0.5\right) \times 0.6  + \left(0.4 - 0.38\right)\times 0.4 = \alert{0.128}$} 
\end{frame}


\begin{frame}
\frametitle{Stratification and Matching}

Exact stratification is \alert{Exact Matching} \pause \\
\invisible<1>{Exact Matching, Basic idea: } \pause 
\begin{itemize}
\invisible<1-2>{\item[-] Identify all \alert{characteristics} (covariates) that affect both outcome and treatment assignment (hint, more than 1!)} \pause 
\invisible<1-3>{\item[-] For all treated units, identify \alert{control} unit with same characteristics} \pause 
\invisible<1-4>{\item[-] Exact match: units in the same strata} 
\end{itemize}

\end{frame}


\begin{frame}
\frametitle{What do we do?}

\alert{Most strata are empty, or only a few observations}
\begin{itemize}
\item[-] \alert{Bias}-\alert{Variance} tradeoff
\begin{itemize}
\item[-] Bias: assume same casual effect across strata
\item[-] Variance: assume different causal effect across strata
\end{itemize}
\item[-] \alert{Modeling} $E[Y|X_{1}, X_{2}, X_{3}, \hdots, X_{K}]$
\begin{itemize}
\item[-] Nonparametric (loess): different curse of dimensionality problem
\item[-] \alert{High dimensional space is sparse}, hard to borrow across
\end{itemize}
\end{itemize}

Solution: specify a model of how covariates relate to treatment


\end{frame}

\begin{frame}
\frametitle{Linear Regression}
Consider one continuous covariate $S_{i}$ and a continuous dependent variable $Y_{i}$. \pause   \\
\invisible<1>{Assume the following, relationship, } \pause 
\begin{eqnarray}
\invisible<1-2>{E[Y_{i}|S_{i}]  & = & \beta_{0} + \beta_{1} S_{i} \nonumber } \pause 
\end{eqnarray} 
\invisible<1-3>{What does this say?} \pause 
\begin{itemize}
\invisible<1-4>{\item[-] \alert{Stratifying} (conditioning): examining means of $Y$ given values of $S$} \pause 
\invisible<1-5>{\item[-] \alert{Borrowing} information across bins:} \pause 
\begin{itemize}
\invisible<1-6>{\item[-] \alert{Assuming} that means have a \alert{global} and \alert{linear} movement with $S$, $\beta_{1}$} 
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Linear Regression}


\begin{columns}[]

\column{0.5\textwidth}
\only<1>{\scalebox{0.5}{\includegraphics{Figure1.pdf}}}
\only<2>{\scalebox{0.5}{\includegraphics{Figure2.pdf}}}
\only<3>{\scalebox{0.5}{\includegraphics{Figure3.pdf}}}
\only<4>{\scalebox{0.5}{\includegraphics{Figure4.pdf}}}

\column{0.5\textwidth}
\begin{itemize}
\invisible<1>{\item[-] $E[Y|S]$ with no stratification: every point is in its own ``bin"} 
\invisible<1-2>{\item[-] $E[Y|S]$ after binning the data--no assumed relationship} 
\invisible<1-3>{\item[-] $E[Y|S] = \beta_{0} + \beta_{1} S_{i} $} 
\end{itemize}

\end{columns}
\pause \pause \pause 

\end{frame}



\begin{frame}

For every random variable $Y$ and $S$ we can always write the random variable as, \pause 
\begin{eqnarray}
\invisible<1>{Y_{i} & = & \underbrace{Y_{i} - E[Y|S]}_{\epsilon_{i}} + E[Y|S] \nonumber \\} \pause 
\invisible<1-2>{Y_{i} & = & E[Y|S] + \epsilon_{i} \nonumber \\} \pause 
\invisible<1-3>{Y_{i} & = & \beta_{0} + \beta_{1}S_{i} + \epsilon_{i}  \nonumber } \pause
\end{eqnarray}
\invisible<1-4>{Where we have used our assumption about $E[Y|S] = \beta_{0} + \beta_{1}S_{i}$} \pause


\invisible<1-5>{We'll define our residuals to be,} \pause
\begin{eqnarray}
\invisible<1-6>{\epsilon_{i} & = & Y_{i} - (E[Y|X] ) \nonumber \\} \pause
\invisible<1-7>{& = & Y_{i} - (\beta_{0} + \beta_{1} S_{i}) \nonumber } \pause
\end{eqnarray}


\invisible<1-8>{We are going to find the  $\beta_{0}^{*}, \beta_{1}^{*}$ that minimize the sum of squared residuals, } \pause
\begin{eqnarray}
\only<10>{\invisible<1-9>{(\beta_{0}^{*}, \beta_{1}^{*}) & = & {\tt argmin}_{\beta_{0}, \beta_{1} } \sum_{i=1}^{N} \epsilon_{i}^2 \nonumber } \pause\\}
\only<11>{\invisible<1-10>{(\beta_{0}^{*}, \beta_{1}^{*}) & = & {\tt argmin}_{\beta_{0}, \beta_{1} } \sum_{i=1}^{N} (Y_{i} - \beta_{0} - \beta_{1} S_{i} )^2 \nonumber } \pause}
\end{eqnarray}




\end{frame}






\begin{frame}

Graphically: 

\begin{columns}[]

\column{0.5\textwidth}
\only<1>{\scalebox{0.4}{\includegraphics{LinReg.pdf}}}
\only<2>{\scalebox{0.4}{\includegraphics{LinReg2.pdf}}}

\column{0.5\textwidth}

\large
$\beta_{0}^{*}  = \overline{Y} - \beta^{*}_{1} \overline{S}$\\
\large
$\beta_{1}^{*} = \frac{\sum_{i=1}^{N} (S_{i} - \overline{S})Y_{i} }{\sum_{i=1}^{n} (S_{i} - \overline{S})^2 }$ \\
\large
$\beta_{1}^{*} = \frac{\text{cov}(S, Y )}{var(S) }$ \\
{\tt regress<- lm(Y~S) } 






\end{columns}



\end{frame}

\begin{frame}
\frametitle{How To Interpret a Regression?}
\pause 
\invisible<1>{Suppose (again) dichotomous treatment $T_{i}$ and a host of \alert{covariates} $X_{i1}, X_{i2}, \hdots, X_{iK}$.} \pause \\
\invisible<1-2>{Common to specify, } \pause 
\begin{eqnarray}
\invisible<1-3>{Y_{i} & = & \beta_{0} + \alpha T_{i}  + \beta_{1} X_{1} + \beta_{2} X_{2} + \hdots + \beta_{K}X_{k} + \epsilon_{i} \nonumber } \pause
\end{eqnarray}

\begin{itemize}
\invisible<1-4>{\item[-] $\alpha$ is an estimate of the ATE} \pause
\invisible<1-5>{\item[-] $\alpha$ will be a consistent estimate of ATE (converge in probability) if there are no \alert{omitted variables}} \pause
\invisible<1-6>{\item[-] $\alpha$ will be a consistent estimate of ATE (converge in probability) if treatment is as good as randomly assigned, given model} \pause
\begin{itemize}
\invisible<1-7>{\item[1)] $X$'s are \alert{pre-treatment} (not consequences of treatment)} \pause
\invisible<1-8>{\item[2)] We know the $X$'s that are related to treatment assignment + outcome} \pause
\invisible<1-9>{\item[3)] The linear model is right (not more complex functional forms)} \pause
\end{itemize}
\end{itemize}
\invisible<1-10>{\alert{You get one causal effect per regression}:} \pause
\begin{itemize}
\invisible<1-11>{\item[-] The whole point of the $X$'s is \alert{just} to replicate experimental conditions} \pause
\invisible<1-12>{\item[-] \alert{Not} to estimate separate causal effects} 
\end{itemize}


\end{frame}


\begin{frame}


\scalebox{0.5}{\includegraphics{RegressionTable.png}}




\end{frame}



\begin{frame}


\huge

Good luck!

\end{frame}



\end{document}




\begin{proof} 
For $a>0$ define the random variable $I$, \pause 
\begin{eqnarray}
\invisible<1>{I & = & 1 \text{ , if $X\geq a$ } \nonumber \\} \pause 
\invisible<1-2>{& = & 0 \text{ , otherwise } \nonumber } \pause 
\end{eqnarray}

\invisible<1-3>{Since $X\geq 0$, } \pause 
\begin{eqnarray}
\invisible<1-4>{I & \leq & \frac{X}{a} \nonumber } \pause 
\end{eqnarray}
\invisible<1-5>{Taking expectations of both sides, } \pause 
\begin{eqnarray}
\invisible<1-6>{E[I] & = & P(X\geq a) \leq \frac{E[x]}{a} \nonumber } 
\end{eqnarray}

\end{proof} 
