Expected Value and Linearity of Expectation

Expected Value Definition:

For a random Variable X, Expected Value E(X) is the weighted average or arithmetic mean of X over a large number of independent experiments or trials.

Let’s say X can take on values like X₁, X₂, X₃,…..,X_N with probabilitiees P(X₁), P(X₂), P(X₃),…,P(X_n) respectively, then E(X) can be be given as:

Let’s take some classic examples of Expected Value to understand this further.

Example 1: What is the Expected value of a fair 6-sided die?

As the die is fair, each of the 6 numbers are equally likely. So the probability for each of the numbers from 1 to 6 will be 1/6. From the definition of Expected value, we can easily calculate E(X) as:

This can be written in another way as:

As we can clearly note that this in fact is an average of all 6 numbers from 1 to 6. That’s why we term Expected Value as “Weighted Average” of X.

Thus after doing a large number of trials with a fair 6 sided die, we can get average value as 3.5.

Example 2: What is the expected number of trials with a fair die until a 6 turn up?

We can get a 6 on the first roll itself. This can occur with a probability (1/6).

Now say we don’t get 6 on the first roll, but we get it on the second roll. So probability of a 6 not turning up on the first roll will be 5/6 and probability of 6 on second roll will be 1/6. So the final probability will be (5/6)*(1/6).

Similarly, P(6 on third roll) = P(Not Getting 6 on first 2 rolls) * P(6 on 3rd roll) = (5/6)*(5/6)*(1/6). So finally, E(X) can be given as:-

So this is an infinite AP GP series. AP because of common difference 1 and GP because of common ratio (5/6). But how do we solve this? It can be done by somehow getting out that AP factor out of this series. Let’s see how.

Multiply the first equation by (1/6) on both sides:

Now substracting equation 2 from 1, we get:-

Now multiplying 6 on both sides,

This is a infite GP. We know the sum for infinte GP, with first term a and common ration r, is:-

Hence E(X) will finally turn out as:-

Thus the expected number of rolls of a single die until a 6 turns up is 6. This was a long way of proving it. The same thing can be proved using the following theorem:-

Theorem 1: If an event has a probability of p to occur in a trial, then the expected number of trials to obtain the first occurrence of this event in a sequence of trials is 1/p

Example 3: What is the expected number of trials with a fair coin until a head turns up?

The above theorem can be easily used to solve this. The probability of head turning up on the first flip is p=1/2. So the Expected number of trials for getting a single head will be E(X)=1/p=2.

Example 4: What is the expected number of trials with a fair die until all numbers turn up?

On first roll, any of the 6 numbers can turn up with equal probability. Expected number of rolls will be 1. Now for the second roll, we want any of the other five numbers that were not turned up on the first roll. Probability of this is 5/6 and hence, Expected number of rolls will be 1/p=6/5.

Similarly, for the third roll, we want any number that was not turned up on first 2 rolls. With probability 4/6, Expected number of rolls for this happening will be 6/4. Thus we can do the same thing for getting the remaining numbers.

Linearity of Expectation

This is the most important property of Expected Value and using this we can solve a wide range of sums. It states that:-

Theorem 2: For two random variables X and Y regardless of whether they are independent, E(X) can be given as,

E(X+Y) = E(X) + E(Y)

Example 5: What is the expected number of trials with a fair coin until two head turns up?

Let Head be H. This question is a variation of Example 3. We already found that the expected number of rolls to get a single Head E(H)=2. Now, using the Linearity of Expectation, we can easily solve this question.

E( H+H) = E(H) + E(H) = 2 + 2 = 4

Example 6: What is the Expected value of sum of two fair 6-sided dice throws?

There are 36 equally dice configurations when we throw 2 dice each with probability of 1/36. These can be (1,1),(1,2),…..(6,6). Thus the sum on the two dice can range from 2 to 12.

E(X) = 2*(1/36) + 3*(2/36) + 4*(3/36) + 5*(4/36) + 6*(5/36) + 7*(6/36) + 8*(5/36) + 9*(4/36) + 10*(3/36)+11*(2/36)+12*(1/36) = 7

But this is the long way of doing it. But what is the shortcut? In Example 1 we found that the expected value of single dice throw E(Single Die) = 3.5

So by Linearity of Expectation, we can find that:

E(2 Dice Throws)= E(Single Die) + E(Single Die) = 3.5 + 3.5 = 7

Example 7: There are 25 students in a classroom each having independent birthdays at any given day of the year with equal probability. What is the expected number of days such that at least two students have birthday on the same day?

Let P(X_i) be the probability such that the i^th day has birthday.

Let’s first calculate the Probability that at least 2 students have birthdays on 1^st January. We can easily infer that:-

P(X₁ having at least 2 birthdays) = 1 – P(X₁ having no birthdays) – P(X₁ having exactly 1 birthday)

Probability that a single student doesn’t have birthday on 1^st January is (364/365). So probability that none of them have birthdays on 1^st January is:-

Probability that there is exactly one birthday on 1^st January = (Number of ways of select 1 student from 25)*(Probability that exactly one student has a birthday) * (Probability that the rest of the 24 students don’t have birthdays).

Okay we got the Probability for 1st January and we know that this probability will be same for January 2^nd, January 3^rd till December 31^st. What about the Expected number for the full year?

Using Linearity of Expectation, we can say that:-

Thus the expected number of days such that at least two students have birthdays on the same day is:-

This sums up the tutorial on Expected value and Linearity of Expectation. There is a very interesting problem based on Expected Value recently asked in Google Kickstart 2020. Check out this post to know more about it.