Massachusetts Institute of Technology Lecture 25 6.042J/18.062J: Mathematics for Computer Science December 7, 2000 Professors Nancy Lynch and Srinivas Devadas

Variance and Bounds on Tails of Distributions

Topics for today:

• Variance

• Markov’s Theorem

• Chebyshev’s Theorem

• Chernoff Bounds

Reading: Rosen Section 4.4, 4.5; Ross, “A First Course in Probability”, Prentice-Hall, Sections 4.6, 8.2, 8.5

1 Overview

So far, our work on random variables has focused on the mean, or expectation. But the mean isn’t the only interesting statistic. We might like to know the probability that the value of the random variable is within a certain bound b of the mean, or more than b away from the mean.

For instance, suppose that the 6 million voters in Florida perform a random experiment to determine whether they vote for Bush or for Gore. E.g., each voter may toss a coin independently; or they may form groups and toss one coin for each group; or half may decided ahead of time, with an even split, and the other half may toss independent coins; or maybe the Florida Supreme Court tosses one coin for the whole state. There are many possibilities. Anyway, we might want to know the likelihood that the number of Floridians who voted for Bush is within 300 of the mean.

We begin with a preliminary section that presents the notion of variance of a random variable.

Then we move to results that bound the “tails” of probability distributions terms of features like the mean and variance. The first result is Markov’s Theorem, which gives a simple but coarse upper bound on the probability that the value of the random variable is more than a certain multiple of the mean. Then we move to Chebyshev’s Theorem, which gives a more refined result that takes into account the variance of the distribution as well as the mean. Finally, we give “Chernoff Bounds”, which give still more refined results, taking into account still more information. These deal with the situation where the distribution is of a particular form—resulting from a series of independent experiments (e.g., voters all tossing independent coins).

2 Variance

The variance of a random variable R is a measure of its tendency to deviate from the mean.

2.1 Definition

Definition The variance of a random variable R is denoted Var(R) and is defined as follows:

Var(R) = Ex((R − Ex(R))^{2})

The expression Ex((R − Ex(R))^{2}) is a bit cryptic; the best approach is to work through it from the inside out. The innermost expression, R − Ex(R), is precisely the deviation of R from the mean. Squaring this, we obtain, (R − Ex(R))^{2}. This is a random variable that is near 0 when R is close to the mean and is a large positive number when R deviates far above or below the mean. The variance is just the average of this random variable, Ex((R − Ex(R))^{2}). Therefore, intuitively, if R is always close to the mean, then the variance will be small. If R is often far from the mean, then the variance will be large. For this reason, variance is useful in studying the probability that a random variable deviates far from the mean.

2.2 Example: Gambling Games

The relevance of variance is apparent when we compare the following two gambling games.

Game A: We win $2 with probability \frac{2}{3} and lose $1 with probability \frac{1}{3}.

Game B: We win $1002 with probability \frac{2}{3} and lose $2001 with probability \frac{1}{3}.

Which game is more better financially? We have the same probability (\frac{2}{3}) of winning each game, but that does not tell the whole story. What about the expected return for each game? Let random variables A and B be the payoffs for the two games. For example, A is 2 with probability \frac{2}{3} and -1 with probability \frac{1}{3}. We can compute the expected payoff for each game as follows:

Ex(A) = 2 · \frac{2}{3} + (−1) · \frac{1}{3} = 1

Ex(B) = 1002 · \frac{2}{3} + (−2001) · \frac{1}{3} = 1

The expected payoff is the same for both games, but they are obviously very different! This difference is hidden by expected value, but captured by variance. We can compute the Var(A) and Var(B) by working “from the inside out” as follows:

A − Ex(A) = \{ \begin{matrix}1 & with probability \frac{2}{3} \\ −2 & with probability \frac{1}{3} \end{matrix}
(A − Ex(A))^{2} = \{ \begin{matrix}1 & with probability \frac{2}{3} \\ 4 & with probability \frac{1}{3} \end{matrix}
Ex(A − Ex(A))^{2} = 1 · \frac{2}{3} + 4 · \frac{1}{3}
Var(A) = 2

B − Ex(B) = \{ \begin{matrix}1001 & with probability \frac{2}{3} \\ −2002 & with probability \frac{1}{3} \end{matrix}
(B − Ex(B))^{2} = \{ \begin{matrix}1, 002, 001 & with probability \frac{2}{3} \\ 4, 008, 004 & with probability \frac{1}{3} \end{matrix}
Ex(B − Ex(B))^{2} = 1, 002, 001 · \frac{2}{3} + 4, 008, 004 · \frac{1}{3}
Var(A) = 2, 004, 002

The variance of Game A is 2 and the variance of Game B is more than two million! Intuitively, this means that the payoff in Game A is usually close to the expected value of $1, but the payoff in Game B can deviate very far from this expected value.

High variance is often associated with high risk. For example, in ten rounds of Game A, we expect to make $10, but could conceivably lose $20 instead. On the other hand, in ten rounds of game B, we also expect to make $10, but could actually lose more than $20,000!

2.3 Why Variance?

The definition of variance looks rather arbitrary:

Var(R) = Ex((R − Ex(R))^{2})

This says that variance is the average of the square of the deviation from the mean. (For this reason, variance is sometimes called the “mean squared deviation”.) But why bother squaring? Why not simply compute the average deviation from the mean? That is, why not define variance to be Ex(R − Ex(R))?

The problem with this definition is that the positive and negative deviations from the mean exactly cancel. By linearity of expectation, we have:

Ex(R − Ex(R)) = Ex(R) − Ex(Ex(R))

Since Ex(R) is a constant, its expected value is itself.

= Ex(R) − Ex(R)
= 0

By this definition, every random variable has zero variance. That is not useful! Because of the square in the conventional definition, both positive and negative deviations from the mean increase the variance; positive and negative deviations do not cancel.

Of course, we could also prevent positive and negative deviations from cancelling by taking an absolute value. That is, we could define variance to be Ex(|R−Ex(R)|). There is no great reason not to use this definition. However, the conventional version of variance has some pleasant mathematical properties that the absolute value variant does not. For example, for independent random variables, the variance of a sum is the sum of the variances; that is, Var(R_{1} + R_{2}) = Var(R_{1}) + Var(R_{2}). We will prove this fact in the last section.

Nevertheless, due to squaring, the variance of a random variable may be very far from a typical deviation from the mean. For example, in Game B the deviation from the mean is 1000 in one outcome and -2003 in the other. But the variance is a whopping 2,004,002. From a dimensional analysis viewpoint, the “units” of variance are wrong: if the random variable is in dollars, then the expectation is also in dollars, but the variance is in square dollars. For this reason, people often describe random variables using standard deviation instead of variance:

Definition The standard deviation of a random variable R is denoted σ_{R} and defined as the square root of the variance:

σ_{R} = \sqrt{Var(R)} = \sqrt{Ex((R − Ex(R))^{2})}

The standard deviation is the square root of the mean of the square of the deviation, or the “root mean square” for short. It has the same units (dollars in our example) as the original random variable and as the mean. Intuitively, it measures the “expected (average) deviation from the mean,” since we can think of the square root on the outside as cancelling the square on the inside.

Example 2.1 The standard deviation of the payoff in Game B is:

σ_{B} = \sqrt{Var(B)}
= \sqrt{2, 004, 002}
≈ 1416

The random variable B actually deviates from the mean by either positive 1000 or negative 2003; therefore, the standard deviation of 1416 describes the situations reasonably well.

As can be seen in the next Figure 1, the standard deviation measures the “width” of the main part of the distribution graph.

2.4 An Alternative Definition of Variance

There is an equivalent way to define the variance of a random variable that is less intuitive, but often easier to use in both calculations and proofs. This alternative definition is stated below in the form of a theorem.

Theorem 2.2 If R is a random variable, then Var(R) = Ex(R^{2}) − Ex(R)^{2}.

Figure 1: The standad deviation of a distribution says how wide the “main” part of it is.

Remember that Ex(R^{2}) is generally not equal to Ex(R)^{2}. The expected value of a product is the product of the expected values only for independent variables, and R is generally not independent of itself.

Proof. Write μ = Ex(R). Then

Var(R) = Ex((R − μ)^{2})
= Ex(R^{2} − 2R · μ + μ^{2})
= Ex(R^{2}) − Ex(2R · μ) + Ex(μ^{2})
= Ex(R^{2}) − 2 Ex(R) · μ + μ^{2}
= Ex(R^{2}) − 2 Ex(R)^{2} + Ex(R)^{2} (definition of μ)
= Ex(R^{2}) − Ex(R)^{2}

The first step uses the definition of variance. In the second step, we multiply out the squared term. The third step uses linearity of expectation. There are two transformations on the fourth line. In the second term, we pull the constant 2μ out of the expectation. In the third term, we use the fact that the expectation of a constant, namely μ^{2}, is that constant. The final step is simplification.

This theorem gives a convenient way to compute the variance of a random variable: find the expected value of the square and subtract the square of the expected value. For example, we can compute the variance of the outcome of a fair die as follows:

Ex(R^{2}) = \frac{1}{6}(1^{2} + 2^{2} + 3^{2} + 4^{2} + 5^{2} + 6^{2}) = 15\frac{1}{6}

Ex(R)^{2} = (3\frac{1}{2})^{2} = 12\frac{1}{4}
Var(R) = Ex(R^{2}) − Ex(R)^{2}
= 15\frac{1}{6} − 12\frac{1}{4}
= 2\frac{11}{12}

2.5 Computing Variance on the Fly

Suppose that there is a random variable R defined on a uniform sample space. Now someone begins reading off the value of the random variable at each sample point. Each value is read exactly once. How can we compute the variance?

This problem might come up in practice if we wanted to compute the variance of a huge set of numbers archived on tapes. In effect, we “hear” each number just once, since we want to avoid multiple passes through the data!

With our original definition of variance, this problem is difficult. If the values of the variable are x_{1}, x_{2}, … x_{n}, then we must compute:

Var(R) = Ex((R − Ex(R))^{2})
= \frac{(x_{1} − Ex(R))^{2} + (x_{2} − Ex(R))^{2} + … + (x_{n} − Ex(R))^{2}}{n}

One approach would be to keep a running sum of the values in the numerator. When we are given value x_{i}, we compute (x_{i} − Ex(R))^{2} and add it to the running sum. At then end, we divide the running sum by n to obtain the variance. The problem with this approach is that we do not know the value of Ex(R) until after we have seen all of the data! Therefore, we need two passes, one to compute Ex(R) and a second to compute the variance.

A better approach is to use the second definition of variance. This requires that we compute:

Var(R) = Ex(R^{2}) − Ex(R)^{2}
= \frac{x_{1}^{2} + x_{2}^{2} + … + x_{n}^{2}}{n} − (\frac{x_{1} + x_{2} + … + x_{n}}{n} )^{2}

Now the problem is much easier. We maintain a sum of all numbers seen and also maintain a sum of the squares of all numbers seen. That is, we store two values, x_{1} +x_{2} +…+x_{i} and x_{1}^{2} +x_{2}^{2} +…+x_{i}^{2}. Then, when we get the (i + 1)-st number, we add x_{i+1} to the first sum and x_{i+1}^{2} to the second sum. After all numbers are heard, we can plug these two summations into the definition above to find the variance. Now finding the variance requires only a single pass through the data!

2.6 A Cute Corollary

The alternate definition of variance given in Theorem 2.2 has a cute implication:

Corollary 2.3 If R is a random variable, then Ex(R^{2}) ≥ Ex(R)^{2}.

Proof. We first defined Var(R) as an average of a squared expression, so Var(R) is non-negative. Then we proved that Var(R) = Ex(R^{2}) − Ex(R)^{2}. This implies that Ex(R^{2}) − Ex(R)^{2} is nonnegative. Therefore, Ex(R^{2}) ≥ Ex(R)^{2}.

In words, the expectation of a square is at least the square of the expectation. The two are equal exactly when the variance is zero:

Ex(R^{2}) = Ex(R)^{2}
⇔ Ex(R^{2}) − Ex(R)^{2} = 0
⇔ Var(R) = 0

2.7 Zero Variance

When does a random variable R have zero variance? When the random variable never deviates from the mean!

Theorem 2.4 The variance of a random variable R is zero if and only if R = Ex(R) for all outcomes with positive probability.

The final phrase is a technicality; for an outcome with zero probability, R can take on any value without affecting the variance.

Proof. By the definition of variance, Var(R) = 0 is equivalent to the condition:

Ex((R − Ex(R))^{2}) = 0

The inner expression, (R − Ex(R))^{2}, is always non-negative because of the square. As a result, Ex((R − Ex(R))^{2}) = 0 if an only if (R − Ex(R))^{2} = 0 for all outcomes with positive probability. Now, the conditions (R − Ex(R))^{2} = 0 and R = Ex(R) are also equivalent. Therefore, Var(R) = 0 iff R = Ex(R) for all outcomes with positive probability.

2.8 Dealing with Constants

The following theorem describes how the variance of a random variable changes when it is scaled or shifted by a constant.

Theorem 2.5 Let R be a random variable, and let a and b be constants.

Var(aR + b) = a^{2} Var(R)

This theorem makes two points. First, adding a constant b to a random variable does not affect the variance. Second, multiplying a random variable by a constant a changes the variance by an a^{2} factor.

Proof. We will transform the left side into the right side. The first step is to expand Var(aR + b) using the alternate definition of variance.

Var(aR + b) = Ex((aR + b)^{2}) − Ex(aR + b)^{2}

We will work on the first term and then the second term. For the first term, note that

Ex((aR + b)^{2}) = Ex(a^{2}R^{2} + 2abR + b^{2})
= (Ex(a^{2}R^{2}) + Ex(2abR) + Ex(b^{2}))
= (a^{2} Ex(R^{2}) + 2ab Ex(R) + b^{2})

In the first step, we multiply out the squared expression in the first term. The second step uses linearity of expectation, and in the third step, we pull all constants out of expectations. Now we work on the second term:

Ex(aR + b)^{2} = (a Ex(R) + b)^{2}
= (a^{2} Ex(R)^{2} + 2ab Ex(R) + b^{2})

In the first step, we pull the constants out of the expectation. In the second step, we multiply out the square.

Now we substract that (expanded) second term from the first. Cancelling terms, we find:

Var(aR + b) = a^{2} Ex(R^{2}) − a^{2} Ex(R)^{2}
= a^{2}(Ex(R^{2}) − Ex(R)^{2})
= a^{2} Var(R)

A similar rule holds for the standard deviation when a random variable is adjusted by a constant. Recall that standard deviation is the square root of variance. Therefore, adding a constant b to a random variable does not change the standard deviation. Multiplying a random variable by a constant a multiplies the standard deviation by a.

2.9 Variance of a Sum

Earlier, we claimed that for independent random variables, the variance of a sum is the sum of the variances. This is stated formally and proved below.

Theorem 2.6 If R_{1} and R_{2} are independent random variables, then

Var(R_{1} + R_{2}) = Var(R_{1}) + Var(R_{2})

Proof. We will transform the left side into the right side. We begin by applying the alternate definition of variance.

Var(R_{1} + R_{2}) = Ex((R_{1} + R_{2})^{2}) − Ex(R_{1} + R_{2})^{2}

We will work on the first term and then the second term.

For the first term, note

Ex((R_{1} + R_{2})^{2}) = Ex(R_{1}^{2} + 2R_{1}R_{2} + R_{2}^{2})
= (Ex(R_{1}^{2}) + Ex(2R_{1}R_{2}) + Ex(R_{2}^{2}))
= (Ex(R_{1}^{2}) + 2 Ex(R_{1}) Ex(R_{2}) + Ex(R_{2}^{2}))

First, we multiply out the squared expression. The second step uses linearity of expectation. In the last step, we break the expectation of the product R_{1}R_{2} into a product of expectations; this is where we use the fact that R_{1} and R_{2} are independent. Now we work on the second term.

Ex(R_{1} + R_{2})^{2} = (Ex(R_{1}) + Ex(R_{2}))^{2}
= (Ex(R_{1})^{2} + 2 Ex(R_{1}) Ex(R_{2}) + Ex(R_{2})^{2})

The first step uses linearity of expectation, and in the second step we multiply out the squared expression. Now we subtract the (expanded) second term from the first. Cancelling and rearranging terms, we find:

Var(R_{1} + R_{2}) = (Ex(R_{1}^{2}) − Ex(R_{1})^{2}) + (Ex(R_{2}^{2})) − Ex(R_{2})^{2})
= Var(R_{1}) + Var(R_{2})

The independence condition in the theorem is necessary. If we ignored this condition and took R_{1} and R_{2} to be the same random variable, then we would conclude:

Var(R + R) = Var(R) + Var(R)

However, by Theorem 2.5, the left side is equal to 4 Var(R), whereas the right side is 2 Var(R). Therefore, if we remove the condition that R_{1} and R_{2} be independent, then the theorem is false.

The preceding theorem extends to a collection of pairwise independent random variables. Recall that pairwise independence is actually a much weaker condition than mutual independence.

Theorem 2.7 If R_{1}, R_{2}, …, R_{n} are pairwise independent random variables, then

Var(R_{1} + R_{2} + … + R_{n}) = Var(R_{1}) + Var(R_{2}) + … + Var(R_{n})

The proof is by induction and is routine, so we will skip it.

2.10 Variance of a Binomial Distribution

We now have enough tools to find the variance of a binomial distribution. Recall that if a random variable R has a binomial distribution, then

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

where n and p are parameters such that n ≥ 1 and 0 < p < 1.

We can think of R as the sum of n independent Bernoulli variables. For example, we can regard R as the number of heads that come up when we toss n independent coins, where each coin comes up heads with probability p. Formally, we can write

R = R_{1} + R_{2} + … + R_{n}

R_{i} = \{ \begin{matrix}1 & with probability p \\ 0 & with probability 1 − p \end{matrix}

Now we can compute the variance of the binomially distributed variable R.

Var(R) = Var(R_{1}) + Var(R_{2}) + … + Var(R_{n})
= n Var(R_{i})
= n(Ex(R_{i}^{2}) − Ex(R_{i})^{2})
= n(Ex(R_{i}) − Ex(R_{i})^{2})
= n(p − p^{2})

The first equation uses Theorem 2.7, and the second uses the fact that all variables R_{i} are identically distributed and therefore have the same variance. We then expand Var(R_{i}) using the alternate definition of variance. In the fourth step, we observe that R_{i}^{2} and R_{i} are the same random variable. This is always true for a Bernoulli random variable, because 0^{2} = 0 and 1^{2} = 1. The last step uses the fact that the expectation of a Bernoulli variable is the probability that the variable is 1; in this case, R_{i} is 1 with probability p.

This shows that the binomial distribution has variance p(1−p)n and standard deviation \sqrt{p(1 − p)n}. In the special case of an unbiased binomial distribution (p = \frac{1}{2}), the variance is \frac{n}{4} and the standard deviation is \frac{\sqrt{n}}{2}.

3 Markov’s Theorem

Now we consider the problem of bounding the probability that the value of a random variable is far away from the mean. The first theorem, Markov’s theorem, gives a very rough estimate, based only on the value of the mean.

3.1 Dice Examples

These examples illustrate different distributions that have the same mean.

Suppose that we roll a fair die. This gives a random variable uniformly distributed on 1, 2, … 6. The mean, or expected value, is 3.5. Of course, this random variable never takes on exactly the expected value; in fact, the outcome deviates from the mean by at least 0.5 with probability 1. Furthermore, there is a \frac{2}{3} probability that the outcome deviates from the mean by at least 1.5 (roll 1, 2, 5, or 6), a \frac{1}{3} probability that the outcome deviates by at least 2.5 (roll 1 or 6), and zero probability that the outcome deviates by more than 2.5.

A random variable with the binomial distribution is much less likely to deviate far from the mean. For example, suppose we flip 100 fair, mutually independent coins and count the number of heads. The expected number of heads is 50. There is an 8% chance that the outcome is exactly the mean, and the probability of flipping more than 75 heads or fewer than 25 is less than 1 in a billion.

The probability distribution functions for the two preceding examples are graphed in Figure 2 and Figure 3. There is a big difference! For the uniform distribution, the graph is flat; that is, outcomes far from the mean are as likely as outcomes close to the mean. However, the binomial distribution has a peak centered on the expected value and the tails fall off rapidly. This shape implies that outcomes close to the expected value are vastly more likely than outcomes far from the expected value. In other words, a random variable with the binomial distribution rarely deviates far from the mean.

Figure 2: This is a graph of the uniform distribution arising from rolling a fair die. Outcomes within the range of the distribution are equally likely, regardless of distance from the mean.

On the other hand, we can define a random variable that always deviates substantially from its expected value. Suppose that we glue 100 coins together, so that with probability 1/2 all are heads and with probability 1/2 all are tails. The graph of the probability distribution function for the number of heads is shown in Figure 4. While the expected value of this random variable is 50, the actual value is always 0 or 100.

Even in this last example, however, the random variable is twice the mean with probability only \frac{1}{2}. In fact, we will see that this is a worst-case distribution with respect to deviation from the mean.

3.2 Theorem statement and examples

Markov’s Theorem says that a non-negative random variable cannot greatly exceed its mean.

Figure 3: This is a rough graph of the binomial distribution given by the number of heads that come up when we flip 100 fair, mutually independent coins. Outcomes close to the mean are much more likely than outcomes far from the mean.

Figure 4: This is the nasty distribution corresponding to the number of heads that come up when we flip 100 coins that are all glued together. The outcome always differs from the mean by at least Theorem 3.1 (Markov’s Theorem) If R is a non-negative random variable, then for all x > 0

Pr(R ≥ x) ≤ \frac{Ex(R)}{x}

Markov’s Theorem is often in expressed in an alternative form, stated below as a corollary.

Corollary 3.2 If R is a non-negative random variable, then for all c > 0

Pr(R ≥ c · Ex(R)) ≤ \frac{1}{c}

Proof. In Markov’s Theorem, set x = c · Ex(R). This gives:

P r(R ≥ c · Ex(R)) ≤ \frac{Ex(R)}{c · Ex(R)} = \frac{1}{c}

Before we prove Markov’s Theorem, let’s apply it to the three examples in the preceding subsection. First, let the random variable R be the number that comes up when we roll a fair die. By Markov’s Theorem, the probability of rolling a 6 is at most:

Pr(R ≥ 6) ≤ \frac{Ex(R)}{6} = \frac{3.5}{6} = 0.583 …

This conclusion is true, but weak. The actual probability of rolling a 6 is \frac{1}{6} = 0.166 . . ..

This is typical of Markov’s Theorem. The theorem is easy to apply because it requires so little information about a random variable, only the expected value and non-negativity. But as a consequence, Markov’s Theorem often leads to weak conclusions like the one above.

Suppose that we flip 100 mutually independent, fair coins. Markov’s Theorem says that the probability of throwing 75 or more heads is at most:

Pr(heads ≥ 75) ≤ \frac{Ex(heads)}{75} = \frac{50}{75} = \frac{2}{3}

Markov’s Theorem says that the probability of 75 or more heads is at most \frac{2}{3}, but the actual probability is less than 1 in a billion!

These two examples show that Markov’s Theorem gives weak results for well-behaved random variables; however, the theorem is actually tight for some nasty examples. Suppose we flip 100 fair coins and use Markov’s Theorem to compute the probability of getting all heads:

Pr(heads ≥ 100) ≤ \frac{Ex(heads)}{100} = \frac{50}{100} = \frac{1}{2}

If the coins in are mutually independent, then the actual probability of getting all heads is a miniscule 1 in 2^{100}. In this case, Markov’s Theorem looks very weak. However, in applying Markov’s Theorem, we made no independence assumptions. In fact, if all the coins are glued together, then probability of throwing all heads is exactly \frac{1}{2}. In this nasty case, Markov’s Theorem is actually tight!

3.3 Proof of Markov’s Theorem

The intuition underlying Markov’s theorem can be drawn out by the famous quote about Lake Woebegone, where “the women are strong, the men are good looking, and all the children are above average.” People laugh at this description because they know the last part cannot be true: the average is obviously going to be somewhere “in the middle” of the distribution. In particular the minimum of the distribution is surely below the average:

Lemma 3.3 For a random variable R, the minimum value ever taken on by R, min R ≤ Ex(R).

Proof. Let y = min R.

Ex(R) = ∑ x · Pr(R = x)
≥ ∑ y · Pr(R = x)  since y ≤ x for every x
= y · ∑ Pr(R = x)
= y

We can get some similar intuition for why Markov’s Theorem is true. Let R be the weight of a person selected randomly and uniformly. Suppose that an average person weighs 100 pounds; that is, Ex(R) = 100. What is the probability that a random person weighs at least 200 pounds?

There is insufficient information for an exact answer. However, we can safely say that the probability that R ≥ 200 is most \frac{1}{2}. If more than half of the people weigh 200 pounds or more, then the average weight would exceed 100 pounds, even if everyone else weighed zero! Markov’s Theorem gives the same result:

Pr(R ≥ 200) ≤ \frac{Ex(R)}{200} = \frac{100}{200} = \frac{1}{2}

Reasoning similar to that above underlies the proof of Markov’s Theorem.

Proof. (of Markov’s Theorem) We must prove that if R is a non-negative random variable, then for all x > 0, we have

Pr(R ≥ x) ≤ \frac{Ex(R)}{x}

We will show that Ex(R) ≥ x · Pr(R ≥ x). Dividing both sides by x gives the desired result.

Ex(R) = ∑_{z∈Range(R)} z · Pr(R = z)
≥ ∑_{z≥x} z · Pr(R = z)
≥ ∑_{z≥x} x · Pr(R = z)
= x · ∑_{z≥x} Pr(R = z)
= x · Pr(R ≥ x)

In the first step, we use the definition of expected value to obtain a sum. Since R is a non-negative random variable, z is always non-negative, and so all terms in the sum are also non-negative. In the second step, we restrict the range of the summation to z ≥ x. This restriction cannot increase the value of the summation, since all terms are non-negative. In the third step, we replace z by x in the sum. The inequality follows because z ≥ x over the entire range of summation. In the fourth step, we pull x out of the summation, and the final step uses the definition of Pr(R ≥ x).

3.4 More Examples of Markov’s Theorem

Suppose that N men go to a dinner party and check their hats. At the end of the night, each man is given his own hat back with probability \frac{1}{N}. What is the probability that x or more men get the right hat?

We can compute an upper bound with Markov’s Theorem. Let the random variable R be the number of men that get the right hat. In a previous lecture, we used linearity of expectation to show that Ex(R) = 1. By Markov’s Theorem, the probability that x or more men get the the right hat is:

Pr(R ≥ x) ≤ \frac{Ex(R)}{x} = \frac{1}{x}

For example, there is no better than a 20% chance that 5 men get the right hat, regardless of the number of people at the dinner party.

The Chinese Appetizer problem is very similar. In this case, N people are eating Chinese appetizers arranged on a circular, rotating tray. Someone then spins the tray so that each person receives a random appetizer. What is the probability that everyone gets the same appetizer as before?

There are N equally likely orientations for the tray after it stops spinning. Everyone gets the right appetizer in just one of these N orientations. Therefore, the correct answer is \frac{1}{N}.

But what probability do we get from Markov’s Theorem? Let the random variable R be the number of people that get the right appetizer. We showed in a previous lecture that Ex(R) = 1. Applying Markov’s Theorem, we find:

Pr(R ≥ N) ≤ \frac{Ex(R)}{N}
= \frac{1}{N}

In this case, Markov’s Theorem is tight!

On the other hand, Markov’s Theorem gives the same 1/N bound for the probability everyone gets their hat in the hat check problem. But in reality, the probability of this event is 1/N!. So Markov’s Theorem is incredibly loose.

3.5 Why R Must be Non-Negative

The proof of Markov’s Theorem requires that the random variable R be non-negative. The following example shows that the theorem is false if this restriction is removed. Let R be -10 with probability \frac{1}{2} and 10 with probability \frac{1}{2}. Then we have:

Ex(R) = −10 · \frac{1}{2} + 10 · \frac{1}{2} = 0

Suppose that we now tried to compute Pr(R ≥ 5) using Markov’s Theorem:

Pr(R ≥ 5) ≤ \frac{Ex(R)}{5}
= \frac{0}{5}
= 0

This is the wrong answer! Obviously, R is at least 5 with probability \frac{1}{2}. Remember that Markov’s Theorem applies only to non-negative random variables!

3.6 Deviation Below the Mean

Markov’s Theorem says that a random variable is unlikely to greatly exceed the mean. There a similar theorem that says a random variable is unlikely to be very small.

Theorem 3.4 Let L be a real number and let R be a random variable such that R ≤ L. For all x < L, we have:

Pr(R ≤ x) ≤ \frac{L − Ex(R)}{L − x}

Proof. The event that R ≤ x is the same as the event that L − R ≥ L − x. Therefore:

Pr(R ≤ x) = Pr(L − R ≥ L − x)
≤ \frac{Ex(L − R)}{L − x}

In the second step, we applied Markov’s Theorem. This is permissible since L − R is a nonnegative random variable and L − x > 0.

For example, suppose that the class average on the 6.042 midterm was 75%. What fraction of the class scored below 50%?

There is not enough information here to answer the question exactly, but Theorem 3.4 gives an upper bound. Let R be the score of a random student. Since 100% is the highest possible score, we can set L = 100 to meet the condition in the theorem that R ≤ L. Applying Theorem 3.4, we find:

Pr(R ≤ 50) ≤ \frac{100 − 75}{100 − 50}
= \frac{1}{2}

That is, at most half of the class scored 50% or worse. This makes sense; if more than half of the class scored 50% or worse, then the class average could not be 75%, even if everyone else scored 100%. As with Markov’s Theorem, Theorem 3.4 often gives weak results. In fact, based on the data given, the entire class could have scored above 50%.

3.7 Using Markov To Analyze Non-Random Events

In the previous examples, we used a theorem about a random variable to conclude facts about non-random data. For example, we concluded that if the average score on a test is 75%, then at most \frac{1}{2} the class scored 50% or worse. There is no randomness in this problem, so how can we apply Theorem 3.4 to reach this conclusion?

The explanation is not difficult. For any set of scores S = {s_{1}, s_{2}, …, s_{n}}, we introduce a random variable R such that

Pr(R = s_{i}) = \frac{(# of students with score s_{i})}{n}

We then use Theorem 3.4 to conclude that Pr(R ≤ 50%) ≤ \frac{1}{2}. To see why this means (with certainty) that at most \frac{1}{2} of the students scored 50% or less, we observe that

Pr(R ≤ 50%) = ∑_{s_{i}≤50%} Pr(R = s_{i})

= ∑_{s_{i}≤50%} \frac{(# of students with score s_{i})}{n}

= \frac{1}{n}(# of students with score 50% or less)

Therefore Pr(R ≤ 50%) ≤ \frac{1}{2} implies that the number of students with score 50% or less is at most \frac{n}{2}.

3.8 The probability of at least one event

Let A_{1}, A_{2}, …, A_{N} be events over the same sample space. Let the random variable T be the number of these events that occur. What is Pr(T ≥ 1), the probability that at least 1 event occurs? We can obtain a weak upper bound on this probability using Markov’s Theorem:

Pr(T ≥ 1) ≤ \frac{Ex(T)}{1}

Markov’s Theorem applies because the random variable T is non-negative. All that remains is to compute Ex(T), the expected number of events that occur. We do this by introducing an indicator variable T_{i} for each event A_{i}; that is, T_{i} = 1 if event A_{i} occurs, and T_{i} = 0 if event A_{i} does not occur. Then T, the total number of events that occur, is the sum of these indicator variables:

T = T_{1} + T_{2} + … + T_{N}

We compute the expected value of T as follows:

Ex(T) = Ex(T_{1} + T_{2} + … + T_{N})
= Ex(T_{1}) + Ex(T_{2}) + … + Ex(T_{N})
= Pr(A_{1}) + Pr(A_{2}) + … Pr(A_{N})

In the first step, we take the expected value of both sides of the preceding equation. The second step uses linearity of expectation. In the last step, we use the fact that the expected value of an indicator variable is the probability that the indicator is 1.

Substituting the expression for Ex(T) into the inequality from Markov’s Theorem gives the following bound on the probability that some event occurs:

Fact 1 Let A_{1}, A_{2}, …, A_{N} be events over the same sample space, and let the random variable T be the number of these events that occur. Then

Pr(T ≥ 1) ≤ ∑_{i=1}^{n} Pr(A_{i}).

This is a formula well worth remembering. In words, the probability that at least one of the events occurs is at most the sum of the event probabilities.

This result is weak for events with sizable probabilities. For example, if we flip a fair coin three times, then we can conclude that the probability of flipping heads at least once is at most \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}, which is not front-page news.

Nevertheless, Fact 1 is useful if the events A_{i} all have relatively low probability. A key advantage is that the events A_{i} need not be independent. (The only tools that we used in the derivation were Markov’s Theorem and linearity of expectation, and neither of these requires independence.) This makes the result easy to apply.

For example, suppose that we want to compute the probability of a meltdown at MIT’s nuclear plant on Albany Street. First, we enumerate all events A_{i} that could lead to a meltdown, e.g. operator error, earthquake, terrorist attack, meteor strike, etc. Next, we somehow determine the probability of each type of catastrophe. Then Fact 1 says that the probability of a meltdown is at most the sum of these event probabilities. Thankfully, we can totally ignore tricky independence issues such as, what if the terrorist team is wiped out by a meteor strike?

The previous method gives an upper bound on Pr(T ≥ 1). We can get a lower bound by computing the maximum of Pr(A_{i}) over all i.

Fact 2 Let A_{1}, A_{2}, …, A_{N} be events over the same sample space, and let the random variable T be the number of these events that occur. Then

Pr(T ≥ 1) ≥ max_{1≤i≤n} Pr(A_{i}).

The left side is Pr(A_{1}∪A_{2}∪…∪A_{n}). Since every event A_{i} is a subset of the union A_{1}∪A_{2}∪…∪A_{n}, we have Pr(A_{1} ∪ A_{2} ∪ … ∪ A_{n}) ≥ Pr(A_{i}) for all i. In particular, this holds for the i that maximizes Pr(A_{i}).

We will be able to get a better lower bound in the case where the events are independent. We will come back to this in tutorial.

4 Chebyshev’s Theorem

Markov’s Theorem uses too little information about a random variable to always give good bounds on deviation from the mean. With more information, we can obtain tighter bounds. Chebyshev’s Theorem takes the variance into account.

4.1 Theorem statement and proof

Theorem 4.1 Let R be a random variable, and let x be a positive real number. Then

Pr(|R − Ex(R)| ≥ x) ≤ \frac{Var(R)}{x^{2}}

Proof. The proof uses Markov’s Theorem. Note that the event |R − Ex(R)| ≥ x is the same as the event (R − Ex(R))^{2} ≥ x^{2}, since the latter inequality is obtained by squaring both sides of the former and both sides of the former are positive. Therefore, these two events have equal probability:

Pr(|R − Ex(R)| ≥ x) = Pr((R − Ex(R))^{2} ≥ x^{2})
≤ \frac{Ex((R − Ex(R))^{2})}{x^{2}}
= \frac{Var(R)}{x^{2}}

We can apply Markov’s Theorem on the second line, since the random variable (R − Ex(R))^{2} is non-negative. The third step follows from the definition of variance.

There is a nice reformulation of Chebyshev’s Theorem in terms of standard deviation.

Corollary 4.2 Let R be a random variable, and let c be a positive real number.

Pr(|R − Ex(R)| ≥ cσ_{R}) ≤ \frac{1}{c^{2}}

Proof. Substituting x = cσ_{R} in Chebyshev’s Theorem gives:

Pr(|R − Ex(R)| ≥ cσ_{R}) ≤ \frac{Var(R)}{(cσ_{R})^{2}}
= \frac{1}{c^{2}}

The last equality holds because variance is the square of standard deviation; in particular, Var(R) = σ_{R}^{2}.

4.2 Example

Suppose that the average I.Q. is 100 and the standard deviation is 10. How rare is an I.Q. of 200 or more?

Let the random variable R be the I.Q. of a random person. We are supposing that Ex(R) = 100 and σ_{R} = 10. Furthermore, let’s assume that everyone has an I.Q. that is positive. We want to compute Pr(R ≥ 200).

Since R is non-negative, we can get an upper bound using Markov’s Theorem as shown below.

Pr(R ≥ 200) ≤ \frac{Ex(R)}{200}
= \frac{100}{200}
= \frac{1}{2}

Markov’s Theorem says that at most half of the people have I.Q. 200 or more; this sounds like a very loose upper bound! Suppose that we now apply Chebyshev’s Theorem to the same problem.

Pr(R ≥ 200) = Pr(|R − 100| ≥ 100)
≤ \frac{Var(R)}{100^{2}}
= \frac{10^{2}}{100^{2}}
= \frac{1}{100}

The purpose of the first step is to express the desired probability in the form required by Chebyshev’s Theorem. (There is equality because R is positive.) We actually apply Chebyshev’s Theorem in the second step. The remaining work is substitution and simplification.

Chebyshev’s Theorem says that at most one person in a hundred has an I.Q. of 200 or more. Chebyshev’s Theorem gives a much tighter bound because it uses additional information, the variance of R.

4.3 A One-Sided Bound

Chebyshev’s Theorem gives a “two-sided bound”. That is, it bounds the probability that a random variable deviates above or below the mean by some amount. What if we want only a one-sided bound? For example, what is the probability that a random variable deviates above the mean by some amount?

This question is often answered incorrectly. The erroneous argument runs as follows. By Chebyshev’s Theorem, R deviates above or below the mean by some amount with probability p. Therefore, R deviates above the mean by this amount with probability \frac{p}{2}, and R deviates below the mean by this amount with probability \frac{p}{2}.

The error in this argument is that a random variable may be more likely to deviate above the mean than below. For example, in the I.Q. question, some people deviate 100 points above the mean; that is, there are people with I.Q. greater than 200. However, by assumption everyone has a positive I.Q.; no one deviates 100 points below the mean. (The argument above is correct, however, for a probability distribution function that is symmetric about the mean.)

The following theorem is analogous to Chebyshev’s Theorem, but gives (correct!) one-sided bounds. We will not give a proof.

Theorem 4.3 Let R be a random variable, and let x be a positive real number.

Pr(R − Ex(R) ≥ x) ≤ \frac{Var(R)}{Var(R) + x^{2}}
Pr(R − Ex(R) ≤ −x) ≤ \frac{Var(R)}{Var(R) + x^{2}}

This theorem has a corollary analogous to Corollary 4.2.

Corollary 4.4 Let R be a random variable, and let c be a positive real number.

Pr(R − Ex(R) ≥ cσ_{R}) ≤ \frac{1}{1 + c^{2}}
Pr(R − Ex(R) ≤ −cσ_{R}) ≤ \frac{1}{1 + c^{2}}

Proof. Substitute x = cσ_{R} in the preceding theorem.

We can use this theorem to improve our solution to the I.Q. problem just slightly. Recall that R is the I.Q. of a random person and that Ex(R) = 100 and σ_{R} = 10.

Pr(R ≥ 200) = Pr(R − 100 ≥ 100)
≤ \frac{Var(R)}{Var(R) + 100^{2}}
= \frac{10^{2}}{10^{2} + 100^{2}}
= \frac{1}{101}

This shows that at most 1 person in 101 has an I.Q. of 200 or more.

4.4 Exam Problems

The following example shows the difference between one-sided and two-sided bounds. On the 6.042 final, what fraction of the class can score two standard deviations or more above or below the class average? Surprisingly, we can answer this question without any assumptions about the range or distribution of scores!

In this case, we want a two-sided bound. Let R be the score of a random student. By Corollary 4.2, the probability is at most:

Pr(|R − Ex(R)| ≥ 2σ) ≤ \frac{1}{2^{2}} = \frac{1}{4}

What fraction of the class can score two standard deviations or more above the class average? Now we want a one-sided bound. By Corollary 4.4, the probability is at most:

Pr(R − Ex(R) ≥ 2σ) ≤ \frac{1}{1 + 2^{2}} = \frac{1}{5}

This makes sense; the probability of deviating above the mean (\frac{1}{5}) should be smaller than the probability of deviating above or below the mean (\frac{1}{4}).

4.5 Deviation of an Unbiased Binomial Distribution

Chebyshev’s Theorem applies to any random variable. However, for a specific distribution, we can sometimes prove a stronger bound on deviation from the mean. For example, a very strong bound is possible for an unbiased binomial distribution.

Fact 3 For a random variable R with an unbiased binomial distribution

Pr(R − Ex(R) ≥ cσ_{R}) < e^{−c^{2}/2}

Note that the bound in Chebyshev’s Theorem is polynomial (\frac{1}{c^{2}} ), but the bound above is exponential (e^{−c^{2}/2}).

For example, suppose that the 6.042 final consists entirely of true/false questions^{1} and students guess answers uniformly and mutually independently. A student’s score on each question is a uniform Bernoulli variable (0 or 1). A student’s exam score is a sum of these Bernoulli variables, and so is a random variable with an unbiased binomial distribution.

Given these assumptions, what is the probability that a student scores two standard deviations above the mean? By Chebyshev’s Theorem the probability is at most 1 in 4. However, we can get a better bound using the fact above.

Pr(R − Ex(R) ≥ 2σ_{R}) < e^{−2^{2}/2}
= e^{−2}

The probability that a student scores 2 standard deviations above the mean on this exam is less than 1 in 7.

The difference is more striking if we look at greater deviations. For example, the probability that a student scores 6 standard deviations above the mean is at most e^{−6^{2}/2} = e^{−18}, which is less than one in 65 million. The corresponding bound from Corollary 4.4 is \frac{1}{37}.

5 Chernoff Bounds

5.1 Probability of at least k events

Now let A_{1}, A_{2}, …, A_{N} be mutually independent events over the same sample space. Let the random variable T be the number of these events that occur. What is the probability that at least k events occur? That is, what is Pr(T ≥ k)? (This generalizes the question asked in Section 3.8 to k events rather than 1; however, note that we have also added the assumption of mutual independence.) For example, suppose we want to know the probability that at least k heads come up in N tosses of a coin. Here A_{i} is the event that that the coin is heads on the i-th toss, T is the total number of heads, and Pr(T ≥ k) is the probability that at least k heads come up.

1Ha! Fat chance.

As a second example, suppose that we want the probability of a student answering at least k questions correctly on an exam with N questions. In this case, A_{i} is the event that the student answers the i-th question correctly, T is the total number of questions answered correctly, and Pr(T ≥ k) is the probability that the student answers at least k questions correctly.

There is an important difference between these two examples. The first example is a special case in that all events A_{i} have equal probability; that is, the coin is as likely to come up heads on one flip as on another. In particular, suppose that the coin comes up heads with probability p. Then all events A_{i} have probability p, and T has the now-familiar binomial distribution:

Pr(T = k) = \binom{n}{k}p^{k}(1 − p)^{n−k} = f_{n,p}(k)

We studied the binomial distribution extensively two weeks ago. Therefore, we already have an answer to the question posed above in the special case where all events A_{i} have equal probability.

In the second example, however, some exam questions might be more difficult than others. If question 1 is easier than question 2, then the probability of event A_{1} is greater than the probability of event A_{2}. This lecture focuses on questions of this more general type in which the events A_{i} may have different probabilities.

We will prove that the number of events that occur is almost always not much greater than the expectation. This result is called the Chernoff Bound. For example, if we toss N coins, the expected number of heads is \frac{N}{2} heads. The Chernoff Bound implies that for sufficiently large N, the number of heads is almost always not much greater than \frac{N}{2} .

A nice feature of the Chernoff Bound is that we do not even need to know the probability of each event A_{i} or even the number of events N; rather, we need only the expected number of events that occur and the fact that the events are mutually independent.

5.2 The theorem

The theorem is stated below in terms of Bernoulli variables instead of events. However, we can regard T_{i} as an indicator for the event A_{i}.

Theorem 5.1 (Chernoff Bound) Let T_{1}, T_{2}, …, T_{N} be mutually independent Bernoulli variables, and let T = T_{1} + T_{2} + … + T_{N}. Then for all c ≥ 1, we have

Pr(T ≥ c Ex(T)) ≤ e^{−αc Ex(T)}

where α = ln c + \frac{1}{c} − 1.

The formula for α is a little awkward. The situation is simpler when c = e = 2.718 …, as in the following corollary.

Corollary 5.2 Let T_{1}, T_{2}, …, T_{N} be mutually independent Bernoulli variables, and let T = T_{1} + T_{2} + … + T_{N}.

Pr(T ≥ e Ex(T)) ≤ e^{− Ex(T)}

Proof. Setting c = e in the Chernoff Bound gives:

Pr(T ≥ e Ex(T)) ≤ e^{−(ln e+ \frac{1}{e} −1)e Ex(T)}
= e^{− Ex(T)}

We will prove the Chernoff Bound shortly. First, let’s see an example of how it is used.

5.3 Pick 4

There is a lottery game called Pick 4. In this game, each player picks 4 digits, defining a number in the range 0 to 9999. A winning number is drawn each week. The players who picked the winning number win some cash. A million people play the lottery, so the expected number of winners each week is \frac{1}{10,000} · 1, 000, 000 = 100. However, on some lucky day thousands of people might all pick the winning number, costing the lottery operators loads of money. How likely is this?

Assume that all players pick numbers uniformly and mutually independently. Let T_{i} be an indicator variable for the event that the i-th player picks the winning number. Let T = T_{1} + T_{2} + … + T_{N}. Then T is the total number of players that pick the winning number. As noted above, an average of 100 people win each week, so Ex(T) = 100. We can use Corollary 5.2 to bound the probability that number of winners is greater than 272 as follows:

Pr(T ≥ 272) ≤ Pr(T ≥ e Ex(T))
≤ e^{−Ex(T)}
= e^{−100}

The probability of 272 or more people winning is absurdly small! It appears that the lottery operators should not worry that ten thousand people will pick correctly one day!

But there is a catch. The assumption that people choose Pick 4 numbers uniformly and mutually independently is empirically false; people choose certain “favorite” numbers far more frequently than others.

Chernoff used this fact in devising a scheme to actually make money on the lottery. In this case, a fraction of all money taken in by the lottery was divided up equally among the winners. A bad strategy would be to pick a popular number. Then, even if you pick the winning number, you must share the cash with many other players. A better strategy is to pick a lot of unpopular numbers. You are just as likely to win with an unpopular number, but will not have to share with anyone. Chernoff found that peoples’ picks were so highly correlated that he could actually turn a 7% profit by picking unpopular numbers!

5.4 The constant in the exponent

For general c, what can we say about the constant α = ln c + \frac{1}{c} − 1 in the exponent? First, note that when c = 1, the constant α = 0: the Chernoff bound cannot say anything useful about the probability of exceeding the mean. However, the constant is increasing with c > 1: the derivative with respect to c is

\frac{dα}{dc} = \frac{1}{c} − \frac{1}{c^{2}} > 0

when c > 1. Therefore, for any c > 1, you get some α > 0 in the exponent.

In particular, consider the case of c close to 1; let’s say c = 1 + ϵ. Then a Taylor expansion of α gives:

α = ln(1 + ϵ) + \frac{1}{1 + ϵ} − 1

= (ϵ − ϵ^{2}/2 + ϵ^{3}/3 − ⋯) + (1 − ϵ + ϵ^{2} − ϵ^{3} + ⋯) − 1

= \frac{1}{2}ϵ^{2} − \frac{2}{3}ϵ^{3} − \frac{3}{4}ϵ^{4} + ⋯

In particular, for very small ϵ, we have

α ≈ ϵ^{2}/2.

In fact one can prove the following:

Lemma 5.3 For any ϵ < 1,

Pr(T ≥ (1 + ϵ Ex(T)) < e^{−ϵ^{2} Ex(T)/3}

In other words, the probability of deviation by ϵ decays exponentially in the expected value, for any ϵ > 0.

Another useful observation is that the Chernoff bound starts to “kick in” when ϵ ≈ 1/\sqrt{Ex(T)}. In other words, the typical deviation of our random variable is going to be about the square root of its expectation. This is in line with our analysis of binomial random variables: the number of heads in n unbiased coin flips has expectation n/2, but has standard deviation \sqrt{n}/2, our roughly the square root of the expectation.

5.5 Proof of the Chernoff Bound

The Chernoff Bound has the most difficult proof of the course. The intuition is in the first two steps; the rest is algebraic chicanery.

Pr(T ≥ c Ex(T)) = Pr(c^{T} ≥ c^{c Ex(T)})
≤ \frac{Ex(c^{T})}{c^{c Ex(T)}}

The first step is a shocker; we raise both sides of the inequality in the probability to the power c. Since the new inequality describes the same event as the old, the probabilities are the same. The second step uses Markov’s Theorem.

Recall that Markov’s Theorem sometimes gives weak bounds and sometimes gives tight bounds. The motivation for the first step is to alter the distribution of the random variable T to hit the “sweet spot” of Markov’s Theorem. That is, Markov’s Theorem gives a tighter bound on the random variable c^{T} than on the original variable T. We used the same trick in Chebyshev’s theorem: we looked at the expectation of T^{2} instead of that of T, because that gave us more powerful results.

All that remains is to evaluate Ex(c^{T}). This leads to a lot of algebra.

Ex(c^{T}) = Ex(c^{T_{1}+T_{2}+...+T_{N}})
= Ex(c^{T_{1}}) · Ex(c^{T_{2}}) ⋯ Ex(c^{T_{N}})
= ∏_{i=1}^{N} Ex(c^{T_{i}})

In the first step, we expand T according to its definition. The second step is where we use the crucial independence assumption: since the variables T_{i} are independent, the variables e^{cT_{i}} are also independent, which means the expectation of the product is the product of the expectations. To simplify the product, we can rewrite Ex(c^{T_{i}}) as follows.

Ex(c^{T_{i}}) = c^{1} Pr(T_{i} = 1) + c^{0} Pr(T_{i} = 0)
= c^{1} Pr(T_{i} = 0) + c^{0}(1 − Pr(T_{i} = 1))
= 1 + (c − 1) Pr(T_{i} = 0)
≤ e^{(c−1) Pr(T_{i}=1)}
= e^{(c−1) Ex(T_{i})}

The first step uses the definition of expected value. The second step uses the fact that the probability of an event is one minus the probability of the complement. The third step is simplification. The fourth line uses the inequality 1+x ≤ e^{x} which follows from the Taylor series e^{x} = 1+x+\frac{x^{2}}{2!} +\frac{x^{3}}{3!} +. . .. The last line relies on the fact that the expected value of a Bernoulli variable is equal to the probability that the variable is 1.

We can now substitute this bound on Ex(c^{T_{i}}) into the product for Ex(c^{T}). The motivation for the approximation 1 + x ≤ e^{x} used above is that terms of the form e^{x} are easy to work with inside a product.

Ex(c^{T}) ≤ ∏_{i=1}^{N} e^{(c−1) Ex(T_{i})}
= e^{∑_{i=1}^{N}(c−1) Ex(T_{i})}
= e^{(c−1) ∑_{i=1}^{N} Ex(T_{i})}
= e^{(c−1) Ex(∑_{i=1}^{N} T_{i})}
= e^{(c−1) Ex(T)}

In the first step, we substitute the bound on Ex(c^{T_{i}}) into the expression for Ex(c^{T}). The second equality follows from an exponent rule. In the third step, we pull the constant (c − 1) out of the summation. The fourth step uses linearity of expectation, and the last step uses the definition of the random variable T.

Now we can substitute this bound on Ex(c^{T}) into the expression derived from Markov’s Theorem. All of the remaining steps are simplifications.

Pr(T ≥ c Ex(T)) ≤ \frac{e^{(c−1) Ex(T)}}{c^{c Ex(T)}}
= e^{(c−1) Ex(T)−c ln c Ex(T)}
= e^{−(ln c+ \frac{1}{c} −1)c Ex(T)}
= e^{−αc Ex(T)}  where α = ln c + \frac{1}{c} − 1

5.6 Example: A Phone Network Problem

Suppose that there is a phone network that handles a billion calls a day. Some of these call are routed through a certain switch. The exact number of calls passing through this switch is somewhat random and fluctuates over time, but on average the switch handles a million calls a day.

Our problem is to set the capacity of the switch; that is, we must determine the number of calls that a switch is able to handle in a day. If we make the capacity too small, then some phone calls will not go through. On the other hand, if we make the capacity too large, then we are wasting money. Of course, we cannot rule out a freak situation in which a huge number of calls are all coincidentally routed through the same switch, thus overloading it. However, we would like to guarantee that a switch is rarely overloaded.

Assume that each call has some probability of passing through a particular switch. In particular, let T_{i} be an indicator variable for the event that the i-th call passes through the switch. That is, T_{i} = 1 if the call is routed through the switch, and T_{i} = 0 if the call does not pass through the switch. Then the total call load on the switch is T = T_{1} + T_{2} + … + T_{N}. We do not know the exact probability that the switch handles the i-th call, but we are given that the switch handles an average of a million calls a day; that is, Ex(T) = 1, 000, 000.

We will make the crucial assumption that the random variables T_{i} are mutually independent; that is, calls do or do not pass through the switch mutually independently.

5.6.1 How to Build One Switch

We can now compute the probability that the load on a switch fluctuates upwards by 1% due to the randomness of calling patterns. Substituting c = 1.01 and Ex(T) = 1, 000, 000 into the Chernoff Bound gives:

Pr(particular switch overloaded) = Pr(T ≥ 1.01 · 1, 000, 000)
≤ e^{−1.01(ln 1.01+ \frac{1}{1.01} −1)·1,000,000}
< e^{−1.01(0.00004934)·1,000,000}
< 2.3 · 10^{−22}

The probability that the load on the switch ever rises by even 1% is unbelievably small! (A terrorist attack on Albany Street during an earthquake is far more likely.) If we build the switch with capacity only 1% above the average load, then the switch will (almost) never be overloaded.

The strength of this result relies on the huge expected number of calls. For example, suppose that the average number of calls through the switch were 100 per day instead of 1,000,000. Then every million in the above calculation would be replaced by a hundred; no other numbers change. The final probability of overloading the switch would then be bounded above not by 2.3 · 10^{−22}, but by 0.995! If the switch handles only 100 calls on an average day, then the call load can very often fluctuate upward by 1% to 101 or more.

5.6.2 How to Build the Network

We now know that building 1% excess capacity into a switch ensures that it is effectively never overloaded. The next problem is to guarantee that no switch in the entire network is overloaded. Suppose that that are 1000 switches, and every switch handles an average of a million calls a day.

In Section 3.8 we saw that the probability that some event occurs is at most the sum of the event probabilities. In particular, the probability that some switch is overloaded is at most the sum of the probabilities that each of the 1000 switches is overloaded. Therefore, we have:

Pr(some switch overloaded) ≤ 1000 · Pr(particular switch overloaded)
< 2.3 · 10^{−19}

This means that building 1% excess capacity into every switch is sufficient to ensure that no switch is ever overloaded.

The above results are of limited practical value, however. One problem is that calls do not pass through a switch mutually independently. For example, after an earthquake on Albany Street, everyone would call through the eastern Cambridge switchboard to check on friends and family. Furthermore, there are many more phone calls on certain dates like Mother’s Day. On such occasions, 1% excess capacity is insufficient.