% This is a simple LaTex sample document that gives a submission format
%   for IEEE PAMI-TC conference submissions.  Use at your own risk.

% Make two column format for LaTex 2e.


\documentclass[11pt,twocolumn]{article} %
\usepackage[dvips]{graphicx,graphics,color}
\usepackage{times,amsmath,amsfonts}
%\usepackage{pancyhdr}
\setlength{\textheight}{10.5in} \setlength{\textwidth}{7in}
\setlength{\columnsep}{0.3in} \setlength{\topmargin}{-0.5in}
\setlength{\headheight}{-0.2in} \setlength{\headsep}{0in}
\setlength{\parindent}{1pc}
\setlength{\oddsidemargin}{-.2in}  % Centers text.
\setlength{\evensidemargin}{-.2in}

% Add the period after section numbers.  Adjust spacing.
\newcommand{\Section}[1]{\vspace{-8pt}\section{\hskip -1em.~~#1}\vspace{-3pt}}
\newcommand{\SubSection}[1]{\vspace{-3pt}\subsection{\hskip -1em.~~#1}
        \vspace{-3pt}}


\newcommand{\bqn}{\begin{eqnarray}}
\newcommand{\eqn}{\end{eqnarray}}
\newcommand{\bq}{\begin{eqnarray*}}
\newcommand{\eq}{\end{eqnarray*}}


\begin{document}

% Don't want date printed
% Make title bold and 14 pt font (Latex default is non-bold, 16pt)

\title{Stat 311-Lecture 06, Expectation}
% For single author (just remove % characters)
%\author{\Large Probability}
\vspace{-2cm}
\date{ }
% For two authors (default example)
\maketitle \thispagestyle{empty}

Sept 22, 2005


\begin{enumerate}

\item The {\em expected value} of a discrete random variable $X$
is defined as $\mathbb{E} X = \sum_{x \in S} xp(x)$.


\item {\em Problem.} A man with $n$ keys wants to open his door and tries the keys at random.
Exactly one key will open the door. Find the expected number of trials until he opens the door if unsuccessful keys are eliminated.\\
{\it solution.} Let $X$ be the number of trials. Then $P(X=1) =
\frac{1}{n}, P(X=2) = \frac{n-1}{n}\frac{1}{n-1}=\frac{1}{n},\cdots,
P(X=n)=\frac{n-1}{n}\dots \frac{1}{2}=\frac{1}{n}.$ The random
varialble $X$ is said to be {\em uniformly} distributed (or a
discrete uniform random variable).
$$\mathbb{E}X=\sum_{x=1}^n \frac{x}{n} = \frac{1}{n}\sum_{x=1}^n x= \frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}.$$
%$$\mathbb{E}X^2 = \sum_{x=1}^n \frac{x^2}{n} =\frac{1}{n}\frac{n(n+1)(2n+1)}{6}.$$
%So ${\bf Var} X = \frac{(n+1)(2n+1)}{6} - \frac{(n+1)^2}{4}.$

\item {\em Geometric distribution.} Toss a coin until the first head is obtained. Let $X$ be the
number of tosses. The probability function of $X$ is given by $P(x)
= (1-p)^{x-1}p$. This is called the geometric distribution.
$\mathbb{E} X = 1/p$.


%\item $\mathbb{V} X = \mathbb{E} X^2 - (\mathbb{E} X)^2$.
%$\mathbb{V} (aX+b) = a^2 \mathbb{V} X$.


\item Two players $A$ and $B$ flip a biased coin alternately and the first player to
 obtain a head wins. The probability of obtaining a head is $p > 0$ at each toss.
 If $A$ flips first, find the expected number of tosses that $A$ must make before $A$ wins.\\
{\it solution.} Let $X$ be the number of tosses $A$ makes until the
game terminates. $A$ wins the game if $H,TTH, TTTTH, \cdots$ occur.
Then the probability distribution for $X$ is $p(x) = (1-p)^{2x-2}p,
x=1,2, \cdots$. So the expection is ${\bf E} X = \sum_{x=1}^\infty
x(1-p)^{2x-2}p$. Let $q=1-p$. Then \bq {\bf E} X &=& \frac{p}{2q}
\sum_{x=1}^\infty 2xq^{2x-1} = \frac{p}{2q} \frac{d}{dq}
\sum_{x=1}^\infty q^{2x} \\&=&  \frac{p}{2q}
\frac{d}{dq}\Big(\frac{q^2}{1-q^2}\Big) = \frac{1}{p(2-p)^2}.\eq



\item The expected value of function $Y=h(X)$ is
\bq \mathbb{E} h(X) &=& \sum_{y} yP(h(X)=y)\\
&=& \sum_{x} h(x)P(h(X)=h(x))\\
&=&\sum_{x} h(x)P(X=x)=\sum_{x} h(x)p(x).\eq

\item Theorem. $\mathbb{E} (aX + b) =
a\mathbb{E} X + b$.


\item For $X \sim
Binomial(n,p)$, $\mathbb{E}X=np$. $$\mathbb{E}X(X-1)=n(n-1)p^2.$$


\item {\em Problem.} Find a value $c$ that minimizes $\mathbb{E}(X-c)^2$ for a discrete random variable X.\\
{\it solution.} Let $f(c) = \mathbb{E}(X-c)^2 = c^2 -(2\mathbb{E}X)c
+ \mathbb{E}X^2$. Then $f(c)$ is minimum at a point where $f'(c)=0$.
$f'(c)=2c-2\mathbb{E}X=0$. So $c=\mathbb{E}X$ will give the minimum.
%Note that $\mathbb{E}X^3 = \mathbb{E}X(X-1)(X-2) -3\mathbb{E}X^2 + 2\mathbb{E} = n(n-1)(n-2)p^3$. \\
%{\it solution 2.} The moment generating function is defined as
%$M_X(t) = \sum_{x=0}^n e^{tx}{n \choose x}p^x(1-p)^{n-x}=
%[pe^t+1-p]^n$ using the Binomial expansion. Then
%$$M_X^{(2)}(t) = npe^t[pe^t+1-p]^{n-1}+n(n-1)p^2e^{2t}[pe^t+1-p]^{n-2}.$$
%$$\mathbb{E}(X^3) = M_X^{(3)}(0) = np + 3n(n-1)p^2 - n(n-1)(n-2)p^3$$


\item The variance of random variable $X$ is
$$\mathbb{V} X = \mathbb{E} (X - \mathbb{E} X)^2 = \mathbb{E} X^2 - (\mathbb{E} X)^2.$$
$$\mathbb{V} (aX+b) = a^2 \mathbb{V} X.$$


\item A man with $n$ keys wants to open his door and tries the keys at random.
Exactly one key will open the door. Find the mean and the variance
of the number of trials if unsuccessful keys are {\em not}
eliminated.

{\em solution}. Let $X$ be the number of trials until he opens the
door. Note that $P(X=1)= \frac{1}{n},
P(X=2)=\frac{n-1}{n}\frac{1}{n},
P(X=3)=(\frac{n-1}{n})^2\frac{1}{n}$. In general,
$P(X=i)=(\frac{n-1}{n})^{i-1}\frac{1}{n}$. So $X$ is a geometric
random variable with $p=\frac{1}{n}$. The expectation $\mathbb{E} X
= \frac{1}{p} = n$. ${\bf Var} X = \frac{1-p}{p^2}= n^2-n$.


\end{enumerate}




\end{document}