Iterated expectation

Expectation (Iterated)

Let X and Y be two random variables. If Y is being held fixed (Y = y), the expectation of X conditionally to Y = y, denoted E[X | Y = y], is a number (see here).

Now, if Y is not being held fixed, E[X | Y = y] becomes a random variable, denoted E[X | Y ]. The expectation of this r.v. has a very important property expressed by the following formula :

E[X] = E[E[X | Y]]

This expression is known as the "Theorem of Iterated Expectation" or "Theorem of double expectation".

It is a compact way to state that :

In the discrete case :
E[X] = Σ_y E[X | Y = y].P{Y = y}
In the continuous case :

or in words :

Let X and Y be two random variables. Then the (unconditional) expectation of X may be obtained as follows :

For every value y of Y, calculate E[X | Y = y], that is, the conditional expection of X given Y = y. It is a function of y only, that is denoted by :

E[X | Y]

Now calculate the mean of that function.
The result is just the expectation of X.

This result has the following graphic interpretation :

1) The upper image displays p(x, y), the joint probability density function of (X, Y).

2) p(x, y) is cut into a series of infinitely thin "slices" defined by (y₀ , y₀ +dy ). Each slice has a barycenter :

Whose position on the x axis is E[x | Y = y₀] (vertical blue line in the lower image),
and whose weight is p_Y(y₀), the marginal probability density of Y for y = y₀.

3) The barycenter of p(x, y) is calculated as the barycenter of the barycenters of the slices.

4) The expectation of X is the projection of the barycenter of p(x, y) on the x axis.

These points are formalized in the first Tutorial below.

-----

The Theorem of Iterated Expectation provides an indirect but powerful way of calculating the expectation of a r.v. X via its coupling with another appropriately chosen "auxiliary" r.v. Y through the conditional expectation E[X | Y]. It turns out to be extremely useful in situations where a direct calculation of E[X] is difficult. It can also be used for calculating probabilities, or more complex quantities, like moment generating functions.

____________________________________________________

Tutorial 1

In the first Tutorial :

We give two demonstrations of the Theorem of Iterated Expectation :

The first one is a direct demonstration.
The second one calls on the "Law of The Unconscious Statistician" (LOTUS).

We then give a simple and academic example where the expectation of a r.v. is calculated first by the "traditional method", and then by using the Theorem of Iterated Expectation. We go over this example in great detail to illustrate the roles of marginal and conditional distributions, as well as of the conditional expectation.
We calculate the expected length of the final piece in the broken stick problem. This calculation will turn our to be much easier than that resorting to the probability density of the length of this piece (which we derive here). Note that we calculate the variance of this length here, calling on the Law of conditional variance.

THEOREM OF ITERATED EXPECTATION

AND FIRST EXAMPLES

The Theorem of Iterated Expectation

Direct demonstration

Demonstration by LOTUS

A simple example

The problem

Direct method

Method of iterated expectation

The broken stick problem

TUTORIAL

___________________________________________________

Tutorial 2

In this second Tutorial, we move on to slightly more sophisticated examples.

We first calculate the mean of the geometric distribution. It is quite remarkable that this short and elegant proof ignores the analytic expression of the probability mass function or of the moment generating function. It relies exclusively on the memoryless property of the geometric distribution. On second thought, this should not be altogether surprising as the memoryless property is characteristic of the geometric distribution (for discrete distributions).

We then give another example of calculation of an (unconditional) expectation that uses the Theorem of iterated expectation. More specifically, the theorem is used in the course of calculating the Covariance of N_i and N_j , with N_i the number of trials resulting in outcome i for a multinomial distribution (and similarly for N_j).

MORE EXAMPLES OF APPLICATIONS OF THE

THEOREM OF ITERATED EXPECTATION

Mean of the geometric distribution

Covariance of two modalities of a multinomial distribution

TUTORIAL

_____________________________________________________

Tutorial 3

In the next Tutorial, we address two classical problems that both involve a random number N of independent random variables {X_i}of identical expectations.

* We first calculate the expectation of the sum of a random number of such variables, with a remarkably simple result.

The same result is obtained here in the special case of iid non negative, integer valued r.v.s by using the properties of the generating function.

* We then calculate the expectation of the product of a random number of such variables. In general, the result is not in a closed form, but we show that when N is Poisson distributed, then it is in a closed and simple form.

-----

In both cases, the Theorem of iterated expectation will be the cornerstone of the calculation.

EXPECTATIONS OF THE SUM AND OF THE PRODUCT

OF A RANDOM NUMBER OF R.V.

Expectation of the sum of a random number of r.v.s

The problem

Expectation of the random sum

Expectation of the product of a random number of r.v.s

The problem

Expectation of the random product

Special case : N is Poisson distributed

TUTORIAL

_______________________________________________________

Tutorial 4

So far, we have used the Theorem of Iterated Expectation for the purpose of calculating expectations. But it can also be used for calculating probabilities, as we show now.

We first establish a general result linking the probability of an event A to the probabilities of this event conditionally to the values of a random variable X.
We then give two examples of applications :

Given two independent r.v.s X and Y, we calculate the probability of the event {X < Y}. We apply the result to the case of exponentially distributed variables (note that we also address this problem here with a different method). The problem has important implications in reliability theory.
Given two independent r.v.s X and Y, we calculate the probability of the event {X + Y < a}. We deduce from the result the cumulative distribution function of their sum (note that we also address the problem here with a different method). We appply the result to the case where X and Y iid exponential variables.

CALCULATING PROBABILITIES WITH

THE THEOREM OF ITERATED EXPECTATION

Expectation and conditional expectation of an indicator variable

Probability of the event {Y < X}

Demonstration

Example : independent exponential r.v.

Probability of the event {X + Y < a}

Demonstration

Example : sum of iid exponential r.v.

TUTORIAL

____________________________________________________________

Tutorial 5

We now use the Theorem of iterated expectation to calculate moment generating functions (mgf), the next best thing to a complete probability distribution function. More precisely, we are going to revisit the problem of the properties of a random number of r.v. (see here).

We already calculated the expectation of the sum of a random number of r.v.s under the assumption of identical expectations. We are now going to calculate the mgf of this sum under the stronger assumption that the variables are iid (this result will later be used here).

-----

Of course, we will then derive again the expectation of the sum, but we will go one step further as we will also be able to calculate the variance of this sum.

_____________

We calculate here the generating function of a random sum of non-negative, integer-valued random variables.

MOMENT GENERATING FUNCTION

OF THE SUM OF A RANDOM NUMBER OF iid R.V.

Moment generating function Φ(t) of the sum of a random number of iid r.v.s

The problem

Notations

Principle of the calculation

Calculating Φ(t )

Mean and variance of the sum of a random number of iid r.v.s

Differentiating the mgf Φ(t )

First derivative

Second derivative

Mean of the sum of a random number of iid r.v.s

Variance of the sum of a random number of iid r.v.s

TUTORIAL

_____________________________________________________________________

Tutorial 6

After this somewhat hefty material, we'll relax a bit with a nice little problem known as the "Miner's problem". We first address a simplified version of the problem :

Roll a die until "1" turns up, and then stop.
Keep track of all the numbers on the upper face of the die after each roll, and add all these numbers (including the final "1"). Denote by X this sum.
X is a random variable. What is its moment generating function?

Again, the easy solution will be to use the Theorem of iterated expectation. That's what we do in this Tutorial.

-----

We'll then generalize the problem, and show that :

The standard "Miner's problem", as well as
Calculating the moment generating function of the geometric distribution,

are special cases of the general problem.

As was the case when we calculated the mean of the distribution, it will appear that only the memoryless property of the geometric distribution is needed to obtain the result.

THE MINER'S PROBLEM

Rolling a die until "1" turns up : mgf of the sum of the outcomes

Generalization

Special cases

The "Miner's problem"

Mgf of the geometric distribution

TUTORIAL

_______________________________________________________

Related readings :

Expectation
Conditional expectation
Conditional variance

Download this Glossary

In the next Tutorial, we address two classical problems that both involve a random number N of independent random variables {Xi}of identical expectations.

In both cases, the Theorem of iterated expectation will be the cornerstone of the calculation.

In the next Tutorial, we address two classical problems that both involve a random number N of independent random variables {X_i}of identical expectations.