Massachusetts Institute of Technology Handout 59 6.042J/18.062J: Mathematics for Computer Science December 4, 1998 Professors N. Lynch and S. Devadas

Notes for Recitation 12 (12/4/98)

1 Conditional Expectation

We can define conditional expectation, or the expectation of a random variable, conditioned on a particular event as follows:

Definition 1.1. The conditional expectation of a random variable R given an event A is defined as

E[R | A] = ∑_{r∈Range(R)} r · P r(R = r | A).

Example: Let R be the outcome of a die. What is the expected value of R given that R ≤ 4 ?

E[R | R ≤ 4] = ∑_{r=1}^{4} rP r(R = r | R ≤ 4)

But P r(R = r | R ≤ 4) = \frac{1}{4}. So,

E[R | R ≤ 4] = \frac{1}{4} ∑_{r=1}^{4} r = 2.5

One use of conditional expectation is to compute an expectation. The following theorem breaks down the expectation into conditional expectations.

Theorem 1.2. Let A_{1}, A_{2}, …, A_{n} be a set of disjoint events whose union is the the sample space. Then for any random variable R,

E[R] = ∑_{i=1}^{n} E[R | A_{i}]P r(A_{i})

Notice that this is analogous to the theorem of total probability:

Theorem 1.3. Let A_{1}, A_{2}, …, A_{n} be a set of disjoint events whose union is the the sample space. Then for any event B,

P r(B) = ∑_{i=1}^{n} P r(B ∩ A_{i}).

Proof of Theorem 1.

E[R] = ∑_{r} r · P r(R = r)

= ∑_{r} r · (∑_{i=1}^{n} P r(R = r ∩ A_{i}))

= ∑_{r} r · (∑_{i=1}^{n} P r(R = r | A_{i})P r(A_{i}))

= ∑_{i=1}^{n} (∑_{r} r · P r(R = r | A_{i})) P r(A_{i})
= ∑_{i} E[R | A_{i}]P r(A_{i})

The first step uses the theorem of total probability with B being the event R = r. The second step is by the definition of conditional probability.

Example: (Assembly plants)

Suppose there are two computer assembly plants F and S. Plant F is fast but sloppy: It makes 70% of the computers, but a computer from F has a 2% probability of breaking down on any given day of use.

Plant S is slow and careful: It makes 30% of the computers, but the breakdown probability is only 1%.

These computers get randomly mixed, so I buy one at random from the store. What is the expected number of days my computer works?

Let D be the random variable giving the number of days my computer works. Let I_{S} be the event that I bought the computer from S, and let I_{F} be that I bought it from F. We solve this problem using conditional expectations. We calculate separately the conditional expectation of the number of working days conditioned on I_{S} and on I_{F}, then combine using the conditional expectation theorem.

The expected number of working days for a computer from S with probability of failure p = 0.01 is just

E[D | I_{S}] = \frac{1}{p} − 1 = 99

Note that mean time to failure is \frac{1}{p}, hence the number of working days is \frac{1}{p} − 1. Similarly, the expected number of working days for a computer from F is

E[D | I_{F}] = \frac{1}{.02} − 1 = 49

.

Now to calculate the expected number of working days for the computer when we don’t know which factory it came from, we use the conditional expectation theorem:

E[D] = E[D|I_{S}]P r(I_{S}) + E[D|I_{F}]P r(I_{F}) = 99(.30) + 49(.70) = 64

2 Covariance

We saw in class that the variance of a random variable is a measure of how it deviates from the mean. Covariance is another statistical measure. It quantifies the similarity of the distributions of two random variables.

Definition 2.1. The covariance of random variables R_{1} and R_{2} is

Cov [R_{1}, R_{2}] ::= E [R_{1}R_{2}] − E [R_{1}] E [R_{2}] .

If the covariance of R_{1} and R_{2} is positive, we will say that they are “positively correlated”, and if their covariance is negative we say that they are “negatively correlated”. Intuitively, positively correlated random variables tend to have close values, while negatively correlated variables tend to have values far apart. Independent random variables have zero correlation.

Examples: Let R_{1} and R_{2} be uniform in the range [1, 6].

1. R_{1} = R_{2}. In this case,

Cov [R_{1}, R_{2}] = E [R_{1}^{2}] − E^{2} [R_{1}] = Var [R_{1}] = 2\frac{11}{12}.

The variables are positively correlated. This is not a surprise — they are always equal.

2. R_{2} = 7 − R_{1}. Now,

Cov [R_{1}, R_{2}] = E [R_{1}(7 − R_{1})] − E [R_{1}] E [7 − R_{1}]
= 7E [R_{1}] − E [R_{1}^{2}] − 7E [R_{1}] + E^{2} [R_{1}]
= −E [R_{1}^{2}] + E^{2} [R_{1}]
= −Var [R_{1}] = −2\frac{11}{12}

The variables are negatively correlated, i.e., when one is high the other is low. This is reflected by the negative covariance.

3. R_{1} are R_{2} are independent (e.g., consecutive coin tosses). Then

Cov [R_{1}, R_{2}] = E [R_{1}R_{2}] − E [R_{1}] E [R_{2}] = E [R_{1}] E [R_{2}] − E [R_{1}] E [R_{2}] = 0.

The correlation of independent random variables is zero.

So if the variables are independent then, indeed their covariance is zero. What about the converse? If the covariance is zero, are the variables independent? The answer is no. For example, let R_{1}, R_{2} be in the range [1, 3] such that Pr [R_{1} = i&R_{2} = j] = 1/8 for all (i, j) except (2, 2) and Pr [R_{1} = R_{2} = 2] = 0. We can check that this gives valid probability distributions for R_{1} and R_{2}:

Pr [R_{1} = 1] = \frac{3}{8}, Pr [R_{1} = 2] = \frac{2}{8}, Pr [R_{1} = 3] = \frac{3}{8},

which add up to 1.

The distribution of R_{1} is the same as the distribution of R_{2} but since Pr [R_{1} = 2 | R_{2} = 2] = 0 ≠ Pr [R_{1} = 2], R_{1} and R_{2} are not independent. However,

Cov [R_{1}, R_{2}] = E [R_{1}R_{2}] − E [R_{1}] E [R_{2}]
= ∑_{i,j∈[1,3]} ijPr [R_{1} = i&R_{2} = j] − ( ∑_{i∈[1,3]} iPr [R_{1} = i])^{2}

= \frac{1}{8}(1 + 2 + 3 + 2 + 6 + 3 + 6 + 9) − (\frac{3}{8}(1 + 3) + \frac{2}{8}2)^{2}
= 4 − 4 = 0

Theorem 2.2. For random variables R_{1} and R_{2},

Var [R_{1} + R_{2}] = Var [R_{1}] + Var [R_{2}] + 2Cov [R_{1}, R_{2}] .

Proof.

Var [R_{1} + R_{2}] = E [(R_{1} + R_{2})^{2}] − E^{2} [R_{1} + R_{2}]
= E [R_{1}^{2} + 2R_{1}R_{2} + R_{2}^{2}] − (E [R_{1}] + E [R_{2}])^{2}
= E [R_{1}^{2}] + 2E [R_{1}R_{2}] + E [R_{2}^{2}] − E^{2} [R_{1}] − 2E [R_{1}] E [R_{2}] − E^{2} [R_{2}]
= (E [R_{1}^{2}] − E^{2} [R_{1}]) + (E [R_{2}^{2}] − E^{2} [R_{2}]) + 2(E [R_{1}R_{2}] − E [R_{1}] E [R_{2}])
= Var [R_{1}] + Var [R_{2}] + 2Cov [R_{1}, R_{2}]

3 Variance of Sums

As a corollary to the previous theorem we have:

Corollary 3.1. If R_{1} and R_{2} are independent, then

Var [R_{1} + R_{2}] = Var [R_{1}] + Var [R_{2}]

Proof. If R_{1}, R_{2} are independent, then Cov [R_{1}, R_{2}] = 0.

A similar result holds for the sum of many independent random variables — but only needs that the variables are pairwise independent.

Theorem 3.2. If R_{1}, …, R_{n} are pairwise independent random variables, then

Var [R_{1} + ⋯ + R_{n}] = Var [R_{1}] + ⋯ + Var [R_{n}] .

The proof is simple and is left to the reader. (Calculations will be easier if one defines new random variables D_{i} ::= R_{i} − E [R_{i}]. Then Var [∑_{i} R_{i}] = E [(∑_{i} D_{i})^{2}], E [D_{i}] = 0, and Var [R_{i}] = E [D_{i}^{2}], which will simplify the expressions.)

Using this result we can now derive the variance of a binomial distribution. Let R have an n, p binomial distribution, i.e.,

Pr [R = k] = \binom{n}{k}p^{k}(1 − p)^{n−k}.

We can think of R as the sum of n Bernoulli independent random variables. That is, the number of heads in n tosses with the probability of heads equal to p:

R = R_{1} + R_{2} + … + R_{n}, Pr [R_{i} = 1] = p, and Pr [R_{i} = 0] = 1 − p.

Now

Var [R_{i}] = E [R_{i}^{2}] − E^{2} [R_{i}] = p − p^{2}.

Hence from the theorem,

Var [R] = ∑_{i=1}^{n} Var [R_{i}] = nVar [R_{i}] = p(1 − p)n.

4 Sum of Pairwise Independent Random Variables

Let V_{1}, …, V_{n} be pairwise independent random variables such that Pr [V_{i} = 0] = 1/2 and Pr [V_{i} = 1] = 1/2 (i.e. each V_{i} is an uniformly distributed Bernoulli variable.) Then Var [∑_{i} V_{i}] = ∑_{i} Var [x_{i}] = n/4, and Chebyshev inequality implies that

Pr [|∑_{i} V_{i} − n/2| ≥ ϵn] ≤ \frac{1}{4ϵ^{2}n}.

In particular, for ϵ = 1/2,

Pr [∑_{i} V_{i} = 0 or ∑_{i} V_{i} = n] ≤ \frac{1}{n}.

If the random variables V_{i} are mutually independent, then the previous bound can be strengthened to 2 · 2^{−n}. We will see that this is not possible in general, i.e., under the sole condition of pairwise independence, the bound implied by Chebyshev’s inequality is essentially the best possible.

Consider independent uniformly distributed Bernoulli variables X_{1}, …, X_{k}. Let n ::= 2^{k} − 1; we shall define n new random variables Y_{S}, one for any non-empty subset S ⊆ {1, …, k}, as follows:

Y_{S} = ( \begin{matrix}1 & if ∑_{i∈S} X_{i} is odd, \\ 0 & otherwise. \end{matrix}

It is easy to verify that for every non-empty S, the random variable Y_{S} is a uniformly distributed Bernoulli random variable (Y_{S} can be thought of as the indicator variable of the event “make k consecutively numbered coin tosses and get an odd number of heads among the coin tosses whose numbers are in S.” Such an event happens with probability 1/2 as long as S is not empty.)

We now proceed to show that for every two different non-empty set S ≠ T ⊆ {1, …, k}, the random variables Y_{S} and Y_{T} are independent. Fix two boolean values b_{1}, b_{2} ∈ {0, 1}, we want to show that

P r(Y_{S} = b_{1}|Y_{T} = b_{2}) = P r(Y_{S} = b_{1})

5 Team Problems

Problem 1. The Petersburg Casino offers the following game: the gambler bets a fixed wager, and then the dealer flips a fair coin (dealers do not flip coins in US casinos, but they do in Petersburg) until it comes up heads. The gambler receives $1 if the coin shows heads the first time, $2 if it shows the first head at second toss, and in general $2^{k−1} if the dealer tosses the coin k times to get the first head. The fixed wager is $100,000.

(a) What is the expected amount of money that the Petersburg Casino is going to pay to a gambler that plays this game? What about the variance? Is it reasonable for the gambler to risk $100,000 dollars in a game where there is a 50% chance of getting only one dollar back (this is not really a mathematical question: just think about that.)

(b) What is the probability that the gambler does not lose money in this game, i.e. what is the probability that he gets back from the Casino more than $100,000?

Problem 2. A Harvard student, lost in the underground corridors of MIT, finds himself in a room containing three doors. Door 1 leads him to freedom (out of MIT) after an hour of travel; door 2 returns him to the same room after four hours travel, and door 3 returns him to the room after seven hours travel. Each time he finds himself in the room, the Harvard student picks a door with equal probability. Let T denote the time until he finds the exit.

(a) Define a sequence of independent identically distributed random variables R_{i} and a stopping rule Q such that

T = ∑_{i=1}^{Q} R_{i}

(b) Argue that R_{k} is independent of the event that Q ≥ k. Is R_{k} independent of Q?

(c) Use Wald’s Theorem to find E [T].

(d) Now suppose that an MIT student is also lost and finds herself in a similar situation to the Harvard student. The MIT student never chooses the same door twice. What is E [T] for the MIT student?

6 Solutions

Problem 1 Solution

Let V be the random variable corresponding to the amount of money that the gambler is paid by the dealer. The distribution of V is as follows: for any n ≥ 1,

Pr [V = 2^{n−1}] = 2^{−n},

where the probability refers to the event that the dealer tosses n − 1 tails followed by a head. The average of V is

E [V] = ∑_{n=1}^{∞}[2^{−n}2^{n−1}] = ∑_{n=1}^{∞} 1/2 = ∞.

The variance is not defined for a random variable having infinite expectation. It does not sound too bad to risk $100,000 on a game where we expect to win an infinite amount of money. However the probability of recovering the money of the wager is only

Pr [X ≥ 100, 000] = Pr [X ≥ 2^{17}]
= Pr [ there are 17 consecutive tails ]
= \frac{1}{131, 072}

Problem 2 Solution

We view this an experiment where at each step the student makes a choice between three equally likely outcomes. We define R_{i} as the number of hours to return to the same room, or to escape, starting at the ith step. The experiment does not end. That is, as soon as the student escapes, he is doomed, like Sisyphus, to be stuck back in the room and start trying to escape again. This ensures that there is an ith step for all i ≥ 0, and that the R_{i} are identically distributed (they are also independent, though this fact is not needed in applying Wald’s Theorem). In particular, Pr [R_{i} = 1] = Pr [R_{i} = 4] = Pr [R_{i} = 7] = 1/3, and E [R_{i}] = (1 + 4 + 7)/3 = 4.

Define Q to be the number of steps from the first step until the escape door is selected for the first time. Now Q is geometrically distributed with probability 1/3 and E [Q] = 3.

Assuming Wald’s Theorem is applicable, we conclude

E [T] = E [∑_{i=1}^{Q} R_{i}] = 3 × 4 = 12.

To justify the use of Wald’s Theorem, we establish that R_{i} is independent of the event that Q ≥ i.

It’s worth noting that R_{i} is not independent of Q. For example, if Q = i, then it must be that the student found the escape door at the ith step, and so Pr [R_{i} = 1|Q = i] = 1 ≠ 1/3 = Pr [R_{i} = 1].

However, suppose we are given that the student has never managed to escape before the ith step, that is, that Q ≥ i. Then we can observe that the experiment starting at the ith step has exactly the same structure as the experiment at the first step—where we were given, implicitly, that the student had not escaped before the first step. So we can conclude that the distribution of R_{i} given Q ≥ i is the same as that of R_{1} given that Q ≥ 1, that is, the same as R_{1}, which we already observed is the same as R_{i}. In other words, R_{i} is independent of the event that Q ≥ i, as required. (This informal argument can be justified rigorously as in Handout 54 on “Probabilities in a Dice Game,” by explicitly describing the sample space for the problem along with a suitable bijection between the whole sample space and the event Q ≥ i.)

Regarding the MIT student, the problem can be solved by complete enumeration; call A the door that leads out, B the door that leads back in four hours, and C the door that leads back in seven hours. The possible events are

• A with probability 1/3, in which case T = 1

• BA with probability \frac{1}{2} · \frac{1}{3} = \frac{1}{6}, in which case T = 5;

• BCA with probability \frac{1}{2} · \frac{1}{3} · 1 = \frac{1}{6}, in which case T = 12;

• CA with probability \frac{1}{2} · \frac{1}{3} = \frac{1}{6}, in which case T = 8;

• CBA with probability \frac{1}{2} · \frac{1}{3} · 1 = \frac{1}{6}, in which case T = 12.

The average of T this time is E [T] = 39/6 = 6.5.