Expectation

Recall, the expected value of a random variable $X$ is $E[X]={\sum }_x^{}xp(x)$ if $X$ is discrete and $E[X]={\int }_{-\infty }^{\infty }xf(x)dx$ if $X$ is continuous

If $P\{a\le X\le b\}=1$ for some a and $b$ then $a\le E[X]\le b$

If $X$ and $Y$ have a joint probability mass function $p(x,y)$ then $E[g(X,Y)]={\sum }_y^{}{\sum }_x^{}g(x,y)p(x,y)$

The continuous analog to this is $E[g(X,Y)]={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }g(x,y)f(x,y)dxdy$

We can apply this to find $E[X+Y]={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }(x+y)f(x,y)dxdy={\int }_{-\infty }^{\infty }x{f}_X(x)dx+{\int }_{-\infty }^{\infty }y{f}_Y(y)dy$
$=E[X]+E[Y]$

An inductive argument shows $E[X_1+\cdots +X_n]=E[X_1]+\cdots +E[X_n]$. This property is extremely useful, and is often referred to as linearity of expectation.

We can break down a binomial random variable $X$ into Bernoulli random variables to show that $E[X]=np$

We can break down a negative binomial random variable $X$ into geometric random variables with parameter $p$ (and expectation $E[X_i]=1/p$) to show that $E[X]=\frac{r}{p}$

We can also break down a hypergeometric random variable into indicator variables $Y_i=1$ if the $i$th ball selected is white and $0$ otherwise. Any ball is equally likely to be the $i$th ball, so $E[Y_i]=\frac{m}{N}$ and $E[X]=\frac{nm}{N}$

Example: Analyzing Quick-Sort

Let $f$ be a function on a finite set $A$ and suppose we want to find $m={\max }_{s\in A}f(s)$. We can find a lower-bound probabilistically, since $m\ge E[f(S)]$

The textbook uses this to find bounds on Hamiltonian paths in an example

Observe: If $X$ is the number of events that occur from $A_1,\dots ,A_n$, then $\left(\genfrac{}{}{0ex}{}{X}{2}\right)$ is the number of pairs of events that occur. We can see that $\left(\genfrac{}{}{0ex}{}{X}{2}\right)=\sum _{i<j}{I}_i{I}_j$

We get $E[X^2]-E[X]=2\sum _{i<j}P(A_i{A}_j)$

An extension of this is $E[(\genfrac{}{}{0ex}{}{X}{k})]=\sum _{i_1<i_2<\cdots <i_k}P(A_{i_1}{A}_{i_2}\dots A_{i_k})$

These can help let us calculate $\text{Var}(X)$ and $E[X^k]$

We can also write $E[g(X)h(Y)]=E[g(X)]E[h(Y)]$

Definition: The covariance between $X$ and $Y$ is defined as $\text{Cov}(X,Y)=E[(X-E[X])(Y-E[Y])]$. Expanding this yields $\text{Cov}(X,Y)=E[XY]-E[X]E[Y]$.

If $X$ and $Y$ are independent, then $\text{Cov}(X,Y)=0$, however the converse is not true

We have some simple properties,

1. $\text{Cov}(X,Y)=\text{Cov}(Y,X)$
2. $\text{Cov}(X,X)=\text{Var}(X)$
3. $\text{Cov}(aX,Y)=a\text{Cov}(X,Y)$
4. $\text{Cov}({\sum }_{i=1}^n{X}_i,{\sum }_{j=1}^m{Y}_j)={\sum }_{i=1}^n{\sum }_{j=1}^m\text{Cov}(X_i,Y_j)$

With 4., we can derive $\text{Var}\left({\sum }_{i=1}^n{X}_i\right)={\sum }_{i=1}^n\text{Var}(X_i)+2{\sum }_{i<j}\text{Cov}(X_i,X_j)$

If $X_1,\dots ,X_n$ are pairwise independent then $\text{Var}({\sum }_{i=1}^n{X}_i)={\sum }_{i=1}^n\text{Var}(X_i)$

The correlation of two random variables $X$ and $Y$, denoted by $\rho (X,Y)$ is defined as $\rho (X,Y)=\frac{\text{Cov}(X,Y)}{\sqrt{\text{Var}(X)\text{Var}(Y)}}$.

We can prove that $-1\le \rho (X,Y)\le 1$ pretty simply. Say $X$ and $Y$ have variances given by ${\sigma }_x^2$ and ${\sigma }_y^2$,
$0\le \text{Var}\left(\frac{X}{{\sigma }_x}+\frac{Y}{{\sigma }_y}\right)$
$=\frac{\text{Var}(X)}{{\sigma }_x^2}+\frac{\text{Var}(Y)}{{\sigma }_y^2}+\frac{2\text{Cov}(X,Y)}{{\sigma }_x{\sigma }_y}$
$=2[1+\rho (X,Y)]⟹-1\le \rho (X,Y)$

$\rho$ behaves similarly to covariance but is nice and bounded. It can also be viewed as a measure of the degree of linearity between $X$ and $Y$, since $\rho (X,Y)=-1$ implies $\text{Var}\left(\frac{X}{{\sigma }_x}+\frac{Y}{{\sigma }_y}\right)=0$, which means $\frac{X}{{\sigma }_x}+\frac{Y}{{\sigma }_y}$ is constant.

Conditional Expectation

Remember that we have $p_{X\mid Y}(x\mid y)=\frac{p(x,y)}{p_Y(y)}$
It makes sense to also define $E[X\mid Y=y]=\sum _{x}x{p}_{X\mid Y}(x\mid y)$

We denote $E[X\mid Y]$ as a function of $Y$ (whose value at $y$ is $E[X\mid Y=y]$). This means $E[X\mid Y]$ is also a random variable.

Theorem: $E[X]=E[E[X\mid Y]]$
This implies $E[X]=\sum _{y}E[X\mid Y=y]P\{Y=y\}$ (or $E[X]={\int }_{-\infty }^{\infty }E[X\mid Y=y]f_Y(y)dy$ for a continuous variable), which is just the law of total probability

We can also interpret this theorem as taking the weighted average of the conditional expected value of $X$ for each $Y=y$

This theorem can help us calculate probabilities by conditioning on indicator variables

Conditional variance is also well-defined, as $\text{Var}(X\mid Y)=E[(X-E[X\mid Y]{)}^2\mid Y]$

To go with it, there’s a useful identity $\text{Var}(X)=E[\text{Var}(X\mid Y)]+\text{Var}(E[X\mid Y])$

Note: If we want to predict $Y$ given $X$ with a function $g$, our best predictor is $E[Y\mid X]$

Definition: The moment generating function $M(t)$ of $X$ is defined for all $t$ as $M(t)=E[e^{tX}]$. It’s called the moment generating function because all moments can be obtained by differentiating $M(T)$ and evaluating at $t=0$.

This assumes that $\frac{d}{dt}E[e^{tX}]=E\left[\frac{d}{dt}{e}^{tX}\right]$, which is generally true

The moment generating function of joint variables $X_1,\dots ,X_n$ is a multivariable function $M(t_1,\dots ,t_n)=E[e^{t_1{X}_1+\cdots +t_n{X}_n}]$. It can be proven that this function uniquely determines the join distribution of $X_1,\dots ,X_n$. This function can also be used to find the individual moment generating functions of $X_i$.