Expectation

The expectation or expected value of a random variable $X$ is given by $E[X] = \sum_x x P_r[X = x]$. This is essentially an average value of $X$ weighted by probability, and it only makes sense if $X$ takes on values that can be summed in this way (e.g., real or complex values, or vectors in a real- or complex-valued vector space). Even if the expectation makes sense, it may be that a particular random variable $X$ does not have an expectation, because the sum fails to converge.

For example, if $X$ and $Y$ are two independent fair six-sided dice, then

	$$E[X] = E[Y]$$	$$= \sum_{i=1}^6 i(\frac{1}{6})$$
		$$= \frac{21}{6}$$
		$$=\frac{7}{2},$$	(8.4)

while $E[X + Y]$ from table  is:

	$$\sum_{i=2}^{12} i.P_r[X+Y=i]$$	$$= \frac{2.1+3.2+4.3+5.4+6.5+7.6+8.5+9.4+10.3+11.2+12.1}{36}$$
		$$=\frac{252}{36}=7$$	(8.5)

The fact that $7 = \frac{7}{2}+\frac{7}{2}$ here is not a coincidence.

The choice of appropriate random variable lies at the heart of the analysis of any randomized algorithm. An idea which is most often used is the linearity of expectations. Let $X$ and $Y$ be random variables. Then we have the following equality:

$$E[X + Y] = E[X] +E[Y]$$ (8.6)

It is important to note that this equation does not require independence between $X$ and $Y$. This idea lets us simplify calculations that would be quite complex otherwise.

Example 8.2   Suppose there are 26 students in a classroom and the professor has alphabet cards with him - each card has a different letter of the alphabet on it. Suppose the professor randomly gives one card per student. Then what is the expected number of people who get a card with the same letter as the first letter of their name?

Solution: To answer this question, consider the random variables: $X_1, X_2, \dots, X_{26}$, where for each $i$, $1\leq i \leq 26$, we define $X_i = 1$ if $i$th person gets the correct letter, 0 otherwise. Since the cards were distributed randomly, the probability that the person gets the correct letter is $\frac{1}{26}$. Therefore, we have: $E[X_i]= \frac{1}{26}$ for all $i$. Finally, the expected number of people who get correct letters is given by $E[X_1 + X_2 + \dots + X_{26}]=1$. Note that there was no assumption made whatsoever about the first letters of peoples’ names. $\Box$

Why Randomization works? The reason why randomized algorithms are successful in finding the solution is that often the problem instance has a lot of witnesses for yes or no. For example, in the case of checking whether a multi-variate polynomial is the zero polynomial, when the input polynomial is indeed a zero polynomial, then it evaluates to zero at all the points. When the polynomial is not zero, then there are a lot of points where the polynomial is non-zero. Hence, finding one witness out of the many is achieved easily by random sampling.