Expectation

The expected value of random variable $X$ is defined as

${\mathbb E}[X] = \sum_{a \in \Omega} X(a) {\mathbb P}[a]$

It is easy to check that

${\mathbb E}[X] = \sum_{u \in {\mathbb R}} u \cdot {\mathbb P}[X= u] = \sum_{u \in {\sf range}(X)} u \cdot {\mathbb P}[X=u]$

where the notation ${\sf range}(X)$ is defined as $\{X(a): a \in \Omega\}$. Since we consider a finite sample space, the range of $X$ is always finite. Denote by $\min X$ and $\max X$ the minimum and maximum values in ${\sf range}(X)$ respectively.

Example 40

It is easy to check that $\min X \leq {\mathbb E}[X] \leq \max X$. This is simply because for every $u \in {\sf range}(X)$, we have $u \geq \min X$, so

${\mathbb E}[X] =\sum_{u \in {\sf range}(X)} u \cdot {\mathbb P}[X=u] \geq (\min X) \cdot \sum_{u \in {\sf range}(X)} {\mathbb P}[X=u] = \min X$

Theorem 41 (Additivity of expectation)

Let $X$ and $Y$ be random variables. Then

${\mathbb E}[X+Y] = {\mathbb E}[X] + {\mathbb E}[Y]$

Exercise 107 (Linearity of expectation)

If $c_1,\ldots, c_k$ are real numbers and $X_1,\ldots, X_k$ are random variables, then

${\mathbb E}[\sum_i c_i X_i] = \sum_i c_i {\mathbb E}[X_i]$

The indicator variable of event $E \subseteq \Omega$ is a random variable that takes $0/1$ values, i.e., $\zeta_E: \Omega \rightarrow \{0,1\}$ such that

$$\zeta_E(a) = \begin{cases} 1, & \text{if}\ a \in E \\ 0, & \text{otherwise} \end{cases}$$

In other words, this is the (random) predicate indicating whether $a \in E$. It is easy to check that the expected value of an indicator variable $\zeta_E$ is the probability of $E$ (do you see why?).

${\mathbb E}[\zeta_E] = {\mathbb P}[E]$

Indicator variables play a central role in probability.

Exercise 108

Prove: Every random variable can be written as a linear combination of indicator variables.

Example 41

Let $X = \sum_i X_i$ where $X_i$ is an indicator random variable $\zeta_{E_i}$ for event $E_i$. Therefore, ${\mathbb E}[X] = \sum_i {\mathbb P}[E_i]$. This just follows from the linearity of expectation.

Example 42

In a random graph probability space $(\Gamma_n, {\mathbb P})$, calculate the expected number of edges.

Proof:

Let $X$ be the number of edges. So we can write $X$ as a sum of the pairs $X(i,j)$ where $X(i,j)$ is an indicator of whether there is an edge connecting $i$ and $j$. That is, $X= \sum_{\{i,j\} \in {[n] \choose 2}} X(i,j)$. By the linearity of expectation:

${\mathbb E}[X] = \sum_{i,j} {\mathbb E}[X(i,j)] = {n \choose 2}/2$

Exercise 109

Calculate the following expectations for the probability space $(\{0,1\}^n, f_p)$ (see Coin tossing).

• The number of heads.
• The number of runs of $k$ consecutive heads (e.g., $110111$ has 3 runs of $2$ consecutive heads).

Exercise 110

Calculate the expected number of Hamiltonian cycles (contain every vertex) in a random graph.