Probability and Computing 2nd Edition
Probability and Computing 2nd Edition
Second Edition
www.cambridge.org
Information on this title: www.cambridge.org/9781107154889
10.1017/9781316651124
© Michael Mitzenmacher and Eli Upfal 2017
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2017
Printed in the United States of America by Sheridan Books, Inc.
A catalogue record for this publication is available from the British Library.
Library of Congress Cataloging in Publication Data
Names: Mitzenmacher, Michael, 1969– author. | Upfal, Eli, 1954– author.
Title: Probability and computing / Michael Mitzenmacher Eli Upfal.
Description: Second edition. | Cambridge, United Kingdom ;
New York, NY, USA : Cambridge University Press, [2017] |
Includes bibliographical references and index.
Identifiers: LCCN 2016041654 | ISBN 9781107154889
Subjects: LCSH: Algorithms. | Probabilities. | Stochastic analysis.
Classification: LCC QA274.M574 2017 | DDC 518/.1 – dc23
LC record available at https://lccn.loc.gov/2016041654
ISBN 978-1-107-15488-9 Hardback
Additional resources for this publication at www.cambridge.org/Mitzenmacher.
Cambridge University Press has no responsibility for the persistence or accuracy
of URLs for external or third-party Internet Web sites referred to in this publication
and does not guarantee that any content on such Web sites is, or will remain,
accurate or appropriate.
To
vii
contents
viii
contents
x
contents
13 Martingales 341
13.1 Martingales 341
13.2 Stopping Times 343
13.2.1 Example: A Ballot Theorem 345
13.3 Wald’s Equation 346
13.4 Tail Inequalities for Martingales 349
13.5 Applications of the Azuma–Hoeffding Inequality 351
13.5.1 General Formalization 351
13.5.2 Application: Pattern Matching 353
13.5.3 Application: Balls and Bins 354
13.5.4 Application: Chromatic Number 355
13.6 Exercises 355
xi
contents
xii
contents
xiii
Preface to the Second Edition
In the ten years since the publication of the first edition of this book, probabilistic
methods have become even more central to computer science, rising with the growing
importance of massive data analysis, machine learning, and data mining. Many of the
successful applications of these areas rely on algorithms and heuristics that build on
sophisticated probabilistic and statistical insights. Judicious use of these tools requires
a thorough understanding of the underlying mathematical concepts. Most of the new
material in this second edition focuses on these concepts.
The ability in recent years to create, collect, and store massive data sets, such as
the World Wide Web, social networks, and genome data, lead to new challenges in
modeling and analyzing such structures. A good foundation for models and analysis
comes from understanding some standard distributions. Our new chapter on the nor-
mal distribution (also known as the Gaussian distribution) covers the most common
statistical distribution, as usual with an emphasis on how it is used in settings in com-
puter science, such as for tail bounds. However, an interesting phenomenon is that in
many modern data sets, including social networks and the World Wide Web, we do not
see normal distributions, but instead we see distributions with very different proper-
ties, most notably unusually heavy tails. For example, some pages in the World Wide
Web have an unusually large number of pages that link to them, orders of magnitude
larger than the average. The new chapter on power laws and related distributions covers
specific distributions that are important for modeling and understanding these kinds of
modern data sets.
Machine learning is one of the great successes of computer science in recent years,
providing efficient tools for modeling, understanding, and making predictions based on
large data sets. A question that is often overlooked in practical applications of machine
learning is the accuracy of the predictions, and in particular the relation between accu-
racy and the sample size. A rigorous introduction to approaches to these important
questions is presented in a new chapter on sample complexity, VC dimension, and
Rademacher averages.
xv
preface to the second edition
We have also used the new edition to enhance some of our previous material. For
example, we present some of the recent advances on algorithmic variations of the pow-
erful Lovász local lemma, and we have a new section covering the wonderfully named
and increasingly useful hashing approach known as cuckoo hashing. Finally, in addi-
tion to all of this new material, the new edition includes updates and corrections, and
many new exercises.
We thank the many readers who sent us corrections over the years – unfortunately,
too many to list here!
xvi
Preface to the First Edition
Why Randomness?
Why should computer scientists study and use randomness? Computers appear to
behave far too unpredictably as it is! Adding randomness would seemingly be a dis-
advantage, adding further complications to the already challenging task of efficiently
utilizing computers.
Science has learned in the last century to accept randomness as an essential com-
ponent in modeling and analyzing nature. In physics, for example, Newton’s laws led
people to believe that the universe was a deterministic place; given a big enough calcu-
lator and the appropriate initial conditions, one could determine the location of planets
years from now. The development of quantum theory suggests a rather different view;
the universe still behaves according to laws, but the backbone of these laws is proba-
bilistic. “God does not play dice with the universe” was Einstein’s anecdotal objection
to modern quantum mechanics. Nevertheless, the prevailing theory today for subparti-
cle physics is based on random behavior and statistical laws, and randomness plays a
significant role in almost every other field of science ranging from genetics and evolu-
tion in biology to modeling price fluctuations in a free-market economy.
Computer science is no exception. From the highly theoretical notion of probabilis-
tic theorem proving to the very practical design of PC Ethernet cards, randomness
and probabilistic methods play a key role in modern computer science. The last two
decades have witnessed a tremendous growth in the use of probability theory in comput-
ing. Increasingly more advanced and sophisticated probabilistic techniques have been
developed for use within broader and more challenging computer science applications.
In this book, we study the fundamental ways in which randomness comes to bear on
computer science: randomized algorithms and the probabilistic analysis of algorithms.
Randomized algorithms: Randomized algorithms are algorithms that make random
choices during their execution. In practice, a randomized program would use values
generated by a random number generator to decide the next step at several branches
of its execution. For example, the protocol implemented in an Ethernet card uses ran-
dom numbers to decide when it next tries to access the shared Ethernet communication
xvii
preface to the first edition
medium. The randomness is useful for breaking symmetry, preventing different cards
from repeatedly accessing the medium at the same time. Other commonly used applica-
tions of randomized algorithms include Monte Carlo simulations and primality testing
in cryptography. In these and many other important applications, randomized algo-
rithms are significantly more efficient than the best known deterministic solutions.
Furthermore, in most cases the randomized algorithms are also simpler and easier to
program.
These gains come at a price; the answer may have some probability of being incor-
rect, or the efficiency is guaranteed only with some probability. Although it may seem
unusual to design an algorithm that may be incorrect, if the probability of error is suf-
ficiently small then the improvement in speed or memory requirements may well be
worthwhile.
Probabilistic analysis of algorithms: Complexity theory tries to classify computa-
tion problems according to their computational complexity, in particular distinguishing
between easy and hard problems. For example, complexity theory shows that the Trav-
eling Salesman problem is NP-hard. It is therefore very unlikely that we will ever know
an algorithm that can solve any instance of the Traveling Salesman problem in time that
is subexponential in the number of cities. An embarrassing phenomenon for the clas-
sical worst-case complexity theory is that the problems it classifies as hard to compute
are often easy to solve in practice. Probabilistic analysis gives a theoretical explanation
for this phenomenon. Although these problems may be hard to solve on some set of
pathological inputs, on most inputs (in particular, those that occur in real-life applica-
tions) the problem is actually easy to solve. More precisely, if we think of the input as
being randomly selected according to some probability distribution on the collection of
all possible inputs, we are very likely to obtain a problem instance that is easy to solve,
and instances that are hard to solve appear with relatively small probability. Probabilis-
tic analysis of algorithms is the method of studying how algorithms perform when the
input is taken from a well-defined probabilistic space. As we will see, even NP-hard
problems might have algorithms that are extremely efficient on almost all inputs.
The Book
with continuous probability and the Poisson process (Chapter 8). The material from
Chapter 4 on Chernoff bounds, however, is needed for most of the remaining material.
Most of the exercises in the book are theoretical, but we have included some pro-
gramming exercises – including two more extensive exploratory assignments that
require some programming. We have found that occasional programming exercises are
often helpful in reinforcing the book’s ideas and in adding some variety to the course.
We have decided to restrict the material in this book to methods and techniques based
on rigorous mathematical analysis; with few exceptions, all claims in this book are fol-
lowed by full proofs. Obviously, many extremely useful probabilistic methods do not
fall within this strict category. For example, in the important area of Monte Carlo meth-
ods, most practical solutions are heuristics that have been demonstrated to be effective
and efficient by experimental evaluation rather than by rigorous mathematical analy-
sis. We have taken the view that, in order to best apply and understand the strengths
and weaknesses of heuristic methods, a firm grasp of underlying probability theory and
rigorous techniques – as we present in this book – is necessary. We hope that students
will appreciate this point of view by the end of the course.
Acknowledgments
Our first thanks go to the many probabilists and computer scientists who developed
the beautiful material covered in this book. We chose not to overload the textbook
with numerous references to the original papers. Instead, we provide a reference list
that includes a number of excellent books giving background material as well as more
advanced discussion of the topics covered here.
The book owes a great deal to the comments and feedback of students and teaching
assistants who took the courses CS 155 at Brown and CS 223 at Harvard. In particular
we wish to thank Aris Anagnostopoulos, Eden Hochbaum, Rob Hunter, and Adam
Kirsch, all of whom read and commented on early drafts of the book.
Special thanks to Dick Karp, who used a draft of the book in teaching CS 174 at
Berkeley during fall 2003. His early comments and corrections were most valuable in
improving the manuscript. Peter Bartlett taught CS 174 at Berkeley in spring 2004, also
providing many corrections and useful comments.
We thank our colleagues who carefully read parts of the manuscript, pointed out
many errors, and suggested important improvements in content and presentation: Artur
Czumaj, Alan Frieze, Claire Kenyon, Joe Marks, Salil Vadhan, Eric Vigoda, and the
anonymous reviewers who read the manuscript for the publisher.
We also thank Rajeev Motwani and Prabhakar Raghavan for allowing us to use some
of the exercises in their excellent book Randomized Algorithms.
We are grateful to Lauren Cowles of Cambridge University Press for her editorial
help and advice in preparing and organizing the manuscript.
Writing of this book was supported in part by NSF ITR Grant no. CCR-0121154.
xx
chapter one
Events and Probability
This chapter introduces the notion of randomized algorithms and reviews some basic
concepts of probability theory in the context of analyzing the performance of simple
randomized algorithms for verifying algebraic identities and finding a minimum cut-set
in a graph.
Computers can sometimes make mistakes, due for example to incorrect programming
or hardware failure. It would be useful to have simple ways to double-check the results
of computations. For some problems, we can use randomness to efficiently verify the
correctness of an output.
Suppose we have a program that multiplies together monomials. Consider the prob-
lem of verifying the following identity, which might be output by our program:
?
(x + 1)(x − 2)(x + 3)(x − 4)(x + 5)(x − 6) ≡ x6 − 7x3 + 25.
There is an easy way to verify whether the identity is correct: multiply together the
terms on the left-hand side and see if the resulting polynomial matches the right-hand
side. In this example, when we multiply all the constant terms on the left, the result
does not match the constant term on the right, so the identity cannot be valid. More
generally, given two polynomials F (x) and G(x), we can verify the identity
?
F (x) ≡ G(x)
d i
by converting the two polynomials to their canonical forms i=0 ci x ; two polynomi-
als are equivalent if and only if all the coefficients in their canonical forms are equal.
From thisdpoint on let us assume that, as in our example, F (x) is given as a product
F (x) = i=1 (x − ai ) and G(x) is given in its canonical form. Transforming F (x) to
its canonical form by consecutively multiplying the ith monomial with the product of
1
events and probability
We turn now to a formal mathematical setting for analyzing the randomized algorithm.
Any probabilistic statement must refer to the underlying probability space.
Definition 1.1: A probability space has three components:
1. a sample space , which is the set of all possible outcomes of the random process
modeled by the probability space;
2. a family of sets F representing the allowable events, where each set in F is a subset1
of the sample space ; and
3. a probability function Pr : F → R satisfying Definition 1.2.
An element of is called a simple or elementary event.
In the randomized algorithm for verifying polynomial identities, the sample space
is the set of integers {1, . . . , 100d}. Each choice of an integer r in this range is a simple
event.
Definition 1.2: A probability function is any function Pr : F → R that satisfies the
following conditions:
1. for any event E, 0 ≤ Pr(E ) ≤ 1;
2. Pr() = 1; and
3. for any finite or countably infinite sequence of pairwise mutually disjoint events
E1 , E2 , E3 , . . . ,
Pr Ei = Pr(Ei ).
i≥1 i≥1
In most of this book we will use discrete probability spaces. In a discrete probability
space the sample space is finite or countably infinite, and the family F of allow-
able events consists of all subsets of . In a discrete probability space, the probability
function is uniquely defined by the probabilities of the simple events.
Again, in the randomized algorithm for verifying polynomial identities, each choice
of an integer r is a simple event. Since the algorithm chooses the integer uniformly at
random, all simple events have equal probability. The sample space has 100d simple
events, and the sum of the probabilities of all simple events must be 1. Therefore each
simple event has probability 1/100d.
Because events are sets, we use standard set theory notation to express combinations
of events. We write E1 ∩ E2 for the occurrence of both E1 and E2 and write E1 ∪ E2 for
the occurrence of either E1 or E2 (or both). For example, suppose we roll two dice. If
E1 is the event that the first die is a 1 and E2 is the event that the second die is a 1, then
E1 ∩ E2 denotes the event that both dice are 1 while E1 ∪ E2 denotes the event that at
least one of the two dice lands on 1. Similarly, we write E1 − E2 for the occurrence
1 In a discrete probability space F = 2 . Otherwise, and introductory readers may skip this point, since the events
need to be measurable, F must include the empty set and be closed under complement and union and intersection
of countably many sets (a σ -algebra).
3
events and probability
of an event that is in E1 but not in E2 . With the same dice example, E1 − E2 consists
of the event where the first die is a 1 and the second die is not. We use the notation Ē
as shorthand for − E; for example, if E is the event that we obtain an even number
when rolling a die, then Ē is the event that we obtain an odd number.
Definition 1.2 yields the following obvious lemma.
Notice that Lemma 1.2 differs from the third part of Definition 1.2 in that Definition
1.2 is an equality and requires the events to be pairwise mutually disjoint.
Lemma 1.1 can be generalized to the following equality, often referred to as the
inclusion–exclusion principle.
+1
− · · · + (−1) Pr Eir + ··· .
i1 <i2 <···<i r=1
If k = 2, it seems that the probability that the first iteration finds a root is at most 1/100
and the probability that the second iteration finds a root is at most 1/100, so the prob-
ability that both iterations find a root is at most (1/100)2 . Generalizing, for any k, the
probability of choosing roots for k iterations would be at most (1/100)k .
To formalize this, we introduce the notion of independence.
Definition 1.3: Two events E and F are independent if and only if
Pr(E ∩ F ) = Pr(E ) · Pr(F ).
More generally, events E1 , E2 , . . . , Ek are mutually independent if and only if, for any
subset I ⊆ [1, k],
Pr Ei = Pr(Ei ).
i∈I i∈I
If our algorithm samples with replacement then in each iteration the algorithm chooses
a random number uniformly at random from the set {1, . . . , 100d}, and thus the choice
in one iteration is independent of the choices in previous iterations. For the case where
the polynomials are not equivalent, let Ei be the event that, on the ith run of the algo-
rithm, we choose a root ri such that F (ri ) − G(ri ) = 0. The probability that the algo-
rithm returns the wrong answer is given by
Pr(E1 ∩ E2 ∩ · · · ∩ Ek ).
Since Pr(Ei ) is at most d/100d and since the events E1 , E2 , . . . , Ek are independent,
the probability that the algorithm gives the wrong answer after k iterations is
k k
d 1 k
Pr(E1 ∩ E2 ∩ · · · ∩ Ek ) = Pr(Ei ) ≤ = .
i=1 i=1
100d 100
The probability of making an error is therefore at most exponentially small in the num-
ber of trials.
Now let us consider the case where sampling is done without replacement. In this
case the probability of choosing a given number is conditioned on the events of the
previous iterations.
Definition 1.4: The conditional probability that event E occurs given that event F
occurs is
Pr(E ∩ F )
Pr(E | F ) = .
Pr(F )
The conditional probability is well-defined only if Pr(F ) > 0.
Intuitively, we are looking for the probability of E ∩ F within the set of events defined
by F. Because F defines our restricted sample space, we normalize the probabilities
by dividing by Pr(F ), so that the sum of the probabilities of all events is 1. When
Pr(F ) > 0, the definition can also be written in the useful form
Pr(E | F ) Pr(F ) = Pr(E ∩ F ).
6
1.2 axioms of probability
Because (d − ( j − 1))/(100d − ( j − 1)) < d/100d when j > 1, our bounds on the
probability of making an error are actually slightly better without replacement. You
may also notice that, if we take d + 1 samples without replacement and the two poly-
nomials are not equivalent, then we are guaranteed to find an r such that F (r) − G(r) =
0. Thus, in d + 1 iterations we are guaranteed to output the correct answer. However,
computing the value of the polynomial at d + 1 points takes (d 2 ) time using the stan-
dard approach, which is no faster than finding the canonical form deterministically.
Since sampling without replacement appears to give better bounds on the probability
of error, why would we ever want to consider sampling with replacement? In some
cases, sampling with replacement is significantly easier to analyze, so it may be worth
7
events and probability
We now consider another example where randomness can be used to verify an equality
more quickly than the known deterministic algorithms. Suppose we are given three
n × n matrices A, B, and C. For convenience, assume we are working over the integers
modulo 2. We want to verify whether
AB = C.
One way to accomplish this is to multiply A and B and compare the result to C. The sim-
ple matrix multiplication algorithm takes (n3 ) operations. There exist more sophisti-
cated algorithms that are known to take roughly (n2.37 ) operations.
Once again, we use a randomized algorithm that allows for faster verification – at the
expense of possibly returning a wrong answer with small probability. The algorithm is
similar in spirit to our randomized algorithm for checking polynomial identities. The
algorithm chooses a random vector r̄ = (r1 , r2 , . . . , rn ) ∈ {0, 1}n . It then computes ABr̄
by first computing Br̄ and then A(Br̄), and it also computes Cr̄. If A(Br̄) = Cr̄, then
AB = C. Otherwise, it returns that AB = C.
The algorithm requires three matrix-vector multiplications, which can be done in
time (n2 ) in the obvious way. The probability that the algorithm returns that AB = C
when they are actually not equal is bounded by the following theorem.
Theorem 1.4: If AB = C and if r̄ is chosen uniformly at random from {0, 1}n , then
1
Pr(ABr̄ = Cr̄) ≤ .
2
Proof: Before beginning, we point out that the sample space for the vector r̄ is the set
{0, 1}n and that the event under consideration is ABr̄ = Cr̄. We also make note of the
following simple but useful lemma.
Lemma 1.5: Choosing r̄ = (r1 , r2 , . . . , rn ) ∈ {0, 1}n uniformly at random is equiva-
lent to choosing each ri independently and uniformly from {0, 1}.
Proof: If each ri is chosen independently and uniformly at random, then each of the
2n possible vectors r̄ is chosen with probability 2−n , giving the lemma.
Let D = AB − C = 0. Then ABr̄ = Cr̄ implies that Dr̄ = 0. Since D = 0 it must have
some nonzero entry; without loss of generality, let that entry be d11 .
For Dr̄ = 0, it must be the case that
n
d1 j r j = 0
j=1
8
1.3 application: verifying matrix multiplication
or, equivalently,
n
j=2 d1 j r j
r1 = − . (1.1)
d11
Now we introduce a helpful idea. Instead of reasoning about the vector r̄, suppose
that we choose the rk independently and uniformly at random from {0, 1} in order,
from rn down to r1 . Lemma 1.5 says that choosing the rk in this way is equivalent to
choosing a vector r̄ uniformly at random. Now consider the situation just before r1 is
chosen. At this point, the right-hand side of Eqn. (1.1) is determined, and there is at
most one choice for r1 that will make that equality hold. Since there are two choices
for r1 , the equality holds with probability at most 1/2, and hence the probability that
ABr̄ = Cr̄ is at most 1/2. By considering all variables besides r1 as having been set, we
have reduced the sample space to the set of two values {0, 1} for r1 and have changed
the event being considered to whether Eqn. (1.1) holds.
This idea is called the principle of deferred decisions. When there are several random
variables, such as the ri of the vector r̄, it often helps to think of some of them as being
set at one point in the algorithm with the rest of them being left random – or deferred –
until some further point in the analysis. Formally, this corresponds to conditioning on
the revealed values; when some of the random variables are revealed, we must condition
on the revealed values for the rest of the analysis. We will see further examples of the
principle of deferred decisions later in the book.
To formalize this argument, we first introduce a simple fact, known as the law of
total probability.
n
n
Pr(B) = Pr(B ∩ Ei ) = Pr(B | Ei ) Pr(Ei ).
i=1 i=1
Proof: Since the events Ei (i = 1, . . . , n) are disjoint and cover the entire sample space
, it follows that
n
Pr(B) = Pr(B ∩ Ei ).
i=1
Further,
n
n
Pr(B ∩ Ei ) = Pr(B | Ei ) Pr(Ei )
i=1 i=1
9
events and probability
Now, using this law and summing over all collections of values (x2 , x3 , x4 , . . . , xn ) ∈
{0, 1}n−1 yields
Pr(ABr̄ = Cr̄)
= Pr (ABr̄ = Cr̄) ∩ ((r2 , . . . , rn ) = (x2 , . . . , xn ))
(x2 ,...,xn )∈{0,1}n−1
n
j=2 d1 j r j
≤ Pr r1 = − ∩ ((r2 , . . . , rn ) = (x2 , . . . , xn ))
d11
(x2 ,...,xn )∈{0,1}n−1
n
j=2 d1 j r j
= Pr r1 = − · Pr((r2 , . . . , rn ) = (x2 , . . . , xn ))
d11
(x2 ,...,xn )∈{0,1}n−1
1
≤ Pr((r2 , . . . , rn ) = (x2 , . . . , xn ))
2
(x2 ,...,xn )∈{0,1}n−1
1
= .
2
Here we have used the independence of r1 and (r2 , . . . , rn ) in the fourth line.
To improve on the error probability of Theorem 1.4, we can again use the fact that
the algorithm has a one-sided error and run the algorithm multiple times. If we ever
find an r̄ such that ABr̄ = Cr̄, then the algorithm will correctly return that AB = C. If
we always find ABr̄ = Cr̄, then the algorithm returns that AB = C and there is some
probability of a mistake. Choosing r̄ with replacement from {0, 1}n for each trial, we
obtain that, after k trials, the probability of error is at most 2−k . Repeated trials increase
the running time to (kn2 ).
Suppose we attempt this verification 100 times. The running time of the random-
ized checking algorithm is still (n2 ), which is faster than the known deterministic
algorithms for matrix multiplication for sufficiently large n. The probability that an
incorrect algorithm passes the verification test 100 times is at most 2−100 , an astronom-
ically small number. In practice, the computer is much more likely to crash during the
execution of the algorithm than to return a wrong answer.
An interesting related problem is to evaluate the gradual change in our confidence in
the correctness of the matrix multiplication as we repeat the randomized test. Toward
that end we introduce Bayes’ law.
Theorem 1.7 [Bayes’ Law]: Assume
that E1 , E2 , . . . , En are mutually disjoint events
in the sample space such that ni=1 Ei = . Then
Pr(E j ∩ B) Pr(B | E j ) Pr(E j )
Pr(E j | B) = = n .
Pr(B) i=1 Pr(B | Ei ) Pr(Ei )
As a simple application of Bayes’ law, consider the following problem. We are given
three coins and are told that two of the coins are fair and the third coin is biased, landing
heads with probability 2/3. We are not told which of the three coins is biased. We
permute the coins randomly, and then flip each of the coins. The first and second coins
come up heads, and the third comes up tails. What is the probability that the first coin
is the biased one?
10
1.3 application: verifying matrix multiplication
The coins are in a random order and so, before our observing the outcomes of the
coin flips, each of the three coins is equally likely to be the biased one. Let Ei be the
event that the ith coin flipped is the biased one, and let B be the event that the three coin
flips came up heads, heads, and tails.
Before we flip the coins we have Pr(Ei ) = 1/3 for all i. We can also compute the
probability of the event B conditioned on Ei :
2 1 1 1
Pr(B | E1 ) = Pr(B | E2 ) = · · = ,
3 2 2 6
and
1 1 1 1
Pr(B | E3 ) = · · = .
2 2 3 12
Applying Bayes’ law, we have
Pr(B | E1 ) Pr(E1 ) 2
Pr(E1 | B) = 3 = .
i=1 Pr(B | Ei ) Pr(Ei )
5
Thus, the outcome of the three coin flips increases the likelihood that the first coin is
the biased one from 1/3 to 2/5.
Returning now to our randomized matrix multiplication test, we want to evaluate
the increase in confidence in the matrix identity obtained through repeated tests. In the
Bayesian approach one starts with a prior model, giving some initial value to the model
parameters. This model is then modified, by incorporating new observations, to obtain
a posterior model that captures the new information.
In the matrix multiplication case, if we have no information about the process that
generated the identity then a reasonable prior assumption is that the identity is correct
with probability 1/2. If we run the randomized test once and it returns that the matrix
identity is correct, how does this change our confidence in the identity?
Let E be the event that the identity is correct, and let B be the event that the test
returns that the identity is correct. We start with Pr(E ) = Pr(Ē ) = 1/2, and since the
test has a one-sided error bounded by 1/2, we have Pr(B | E ) = 1 and Pr(B | Ē ) ≤ 1/2.
Applying Bayes’ law yields
Assume now that we run the randomized test again and it again returns that the
identity is correct. After the first test, I may naturally have revised my prior model, so
that I believe Pr(E ) ≥ 2/3 and Pr(Ē ) ≤ 1/3. Now let B be the event that the new test
returns that the identity is correct; since the tests are independent, as before we have
Pr(B | E ) = 1 and Pr(B | Ē ) ≤ 1/2. Applying Bayes’ law then yields
2/3 4
Pr(E | B) ≥ = .
2/3 + 1/3 · 1/2 5
11
events and probability
In general: if our prior model (before running the test) is that Pr(E ) ≥ 2i /(2i + 1)
and if the test returns that the identity is correct (event B), then
2i
2i + 1 2i+1 1
Pr(E | B) ≥ = i+1 + 1
= 1 − i+1 .
2i
1 1 2 2 +1
+
2i + 1 2 2i + 1
Thus, if all 100 calls to the matrix identity test return that the identity is correct, our
confidence in the correctness of this identity is at least 1 − 1/(2101 + 1).
a list of important keywords, the X j could be Boolean features where xij = 1 if the
jth listed keyword appears in Di and xij = 0 otherwise. In this case, the feature vector
of the document would just correspond to the set of keywords it contains. Finally, we
have a set C = {c1 , c2 , . . . , ct } of possible classifications for the object, and c(Di ) is the
classification of Di . For example, the classification set C could be a collection of labels
such as {“spam”, “no-spam”}. Given a document, corresponding to a web page or e-
mail, we might want to classify the document according to the keywords the document
contains.
The classification paradigm assumes that the training set is a sample from an
unknown distribution in which the classification of an object is a function of the m
features. The goal is, given a new document, to return an accurate classification. More
generally, we can instead return a vector (z1 , z2 , . . . , zt ), where z j is an estimate of the
probability that c(Di ) = c j based on the training set. If we want to return just the most
likely classification, we can return the c j with the highest value of z j .
Suppose to begin that we had a very, very large training set. Then for each vec-
tor y = (y1 , . . . , ym ) and each classification c j , we could use the training set to com-
pute the empirical conditional probability that an object with a features vector y is
12
1.4 application: naïve bayesian classifier
classified C j :
{|i : xi = y, c(Di ) = c j |}
py, j = .
{|i : xi = y)|}
Assuming that a new object D∗ with a features vector x∗ has the same distribution as
the training set, then px∗ , j is an empirical estimate for the conditional probability
Pr(c(D∗ ) = c j | x∗ = (x1∗ , . . . , xm
∗
)).
Indeed, we could compute these values ahead of time in a large lookup table and simply
return the vector (z1 , z2 , . . . , zt ) = (px∗ ,1 , px∗ ,2 , . . . , px∗ ,t ) after computing the features
vector x∗ from the object.
The difficulty in this approach is that we need to obtain accurate estimates of a large
collection of conditional probabilities, corresponding to all possible combination of
values of the m features. Even if each feature has just two values we would need to esti-
mate 2m conditional probabilities per class, which would generally require (|C|2m )
samples.
The training process is faster and requires significantly fewer examples if we assume
a “naïve” model in which the m features are independent. In that case we have for
Pr(x∗ | c(D∗ ) = c j ) · Pr(c(D∗ ) = c j )
Pr(c(D∗ ) = c j | x∗ ) = (1.2)
Pr(x∗ )
m
Pr(xk∗ = xi | c(D∗ ) = c j ) · Pr(c(D∗ ) = c j )
= k=1 . (1.3)
Pr(x∗ )
Here xk∗ is the kth component of the features vector x∗ of object D∗ . Notice that the
denominator is independent of c j , and can be treated as just a normalizing constant
factor.
With a constant number of possible values per feature, we only need to learn esti-
mates for O(m|C|) probabilities. In what follows, we use Pr ˆ to denote empirical prob-
abilities, which are the relative frequency of events in our training set of examples. This
notation emphasizes that we are taking estimates of these probabilities as determined
from the training set. (In practice, one often makes slight modifications, such as adding
1/2 to the numerator in each of the fractions to guarantee that no empirical probability
equals 0.)
The training process is simple:
r For each classification class c j , keep track of the fraction of objects classified as c j
to compute
∗ |{i | c(Di ) = c j }|
ˆ
Pr(c(D ) = cj) = ,
|D|
where |D| is the number of objects in the training set.
r For each feature Xk and feature value xk keep track of the fraction of objects with that
feature value that are classified as c j , to compute
Once we train the classifier, the classification of a new object D∗ with features vector
x∗ = (x1∗ , . . . , xm
∗
) is computed by calculating
m
∗ ∗
ˆ k = xk | c(D ) = c j ) Pr(c(D∗
Pr(x ˆ ) = cj)
k=1
for each c j and taking the classification with the highest value.
In practice, the products may lead to underflow values; an easy solution to that prob-
lem is to instead compute the logarithm of the above expression. Estimates of the
entire probability vector can be found by normalizing appropriately. (Alternatively,
instead of normalizing, one could provide probability estimates by also computing
estimates for Pr(x∗ = x) from the sample data. Under our independence assumption
Pr(x∗ = (x1∗ , . . . , xm
∗
)) = m ∗
k=1 Pr(xk = xk ), and one could estimate the denominator
of Equation 1.2 with the product of the corresponding estimates.)
The naïve Bayesian classifier is efficient and simple to implement due to the “naïve”
assumption of independence. This assumption may lead to misleading outcomes when
the classification depends on combinations of features. As a simple example consider
14
1.5 application: a randomized min-cut algorithm
A cut-set in a graph is a set of edges whose removal breaks the graph into two or
more connected components. Given a graph G = (V, E ) with n vertices, the minimum
cut – or min-cut – problem is to find a minimum cardinality cut-set in G. Minimum
cut problems arise in many contexts, including the study of network reliability. In the
case where nodes correspond to machines in the network and edges correspond to con-
nections between machines, the min-cut is the smallest number of edges that can fail
before some pair of machines cannot communicate. Minimum cuts also arise in clus-
tering problems. For example, if nodes represent Web pages (or any documents in a
hypertext-based system) and two nodes have an edge between them if the correspond-
ing nodes have a hyperlink between them, then small cuts divide the graph into clus-
ters of documents with few links between clusters. Documents in different clusters are
likely to be unrelated.
We shall proceed by making use of the definitions and techniques presented so far
in order to analyze a simple randomized algorithm for the min-cut problem. The main
operation in the algorithm is edge contraction. In contracting an edge (u, v) we merge
the two vertices u and v into one vertex, eliminate all edges connecting u and v, and
retain all other edges in the graph. The new graph may have parallel edges but no
self-loops. Examples appear in Figure 1.1, where in each step the dark edge is being
contracted.
The algorithm consists of n − 2 iterations. In each iteration, the algorithm picks an
edge from the existing edges in the graph and contracts that edge. There are many pos-
sible ways one could choose the edge at each step. Our randomized algorithm chooses
the edge uniformly at random from the remaining edges.
Each iteration reduces the number of vertices in the graph by one. After n − 2 iter-
ations, the graph consists of two vertices. The algorithm outputs the set of edges con-
necting the two remaining vertices.
It is easy to verify that any cut-set of a graph in an intermediate iteration of the
algorithm is also a cut-set of the original graph. On the other hand, not every cut-set of
the original graph is a cut-set of a graph in an intermediate iteration, since some edges
of the cut-set may have been contracted in previous iterations. As a result, the output of
the algorithm is always a cut-set of the original graph but not necessarily the minimum
cardinality cut-set (see Figure 1.1).
We now establish a lower bound on the probability that the algorithm returns a cor-
rect output.
15
events and probability
1 3 1
5 5 5 5
3,4 1,3,4 1,2,3,4
2 4 2 2
(a) A successful run of min-cut.
1 3 1 1 1
5 5
3,4 3,4,5
2,3,4,5
2 4 2 2
(b) An unsuccessful run of min-cut.
Figure 1.1: An example of two executions of min-cut in a graph with minimum cut-set of size 2.
Theorem 1.8: The algorithm outputs a min-cut set with probability at least
2/(n(n − 1)).
Proof: Let k be the size of the min-cut set of G. The graph may have several cut-sets
of minimum size. We compute the probability of finding one specific such set C.
Since C is a cut-set in the graph, removal of the set C partitions the set of vertices into
two sets, S and V − S, such that there are no edges connecting vertices in S to vertices in
V − S. Assume that, throughout an execution of the algorithm, we contract only edges
that connect two vertices in S or two vertices in V − S, but not edges in C. In that case,
all the edges eliminated throughout the execution will be edges connecting vertices in
S or vertices in V − S, and after n − 2 iterations the algorithm returns a graph with two
vertices connected by the edges in C. We may therefore conclude that, if the algorithm
never chooses an edge of C in its n − 2 iterations, then the algorithm returns C as the
minimum cut-set.
This argument gives some intuition for why we choose the edge at each iteration
uniformly at random from the remaining existing edges. If the size of the cut C is
small and if the algorithm chooses the edge uniformly at each step, then the probability
that the algorithm chooses an edge of C is small – at least when the number of edges
remaining is large compared to C.
iLet Ei be the event that the edge contracted in iteration i is not in C, and let Fi =
j=1 E j be the event that no edge of C was contracted in the first i iterations. We need
to compute Pr(Fn−2 ).
We start by computing Pr(E1 ) = Pr(F1 ). Since the minimum cut-set has k edges, all
vertices in the graph must have degree k or larger. If each vertex is adjacent to at least k
edges, then the graph must have at least nk/2 edges. The first contracted edge is chosen
uniformly at random from the set of all edges. Since there are at least nk/2 edges in the
graph and since C has k edges, the probability that we do not choose an edge of C in
the first iteration is given by
2k 2
Pr(E1 ) = Pr(F1 ) ≥ 1 − =1− .
nk n
16
1.6 exercises
Let us suppose that the first contraction did not eliminate an edge of C. In other
words, we condition on the event F1 . Then, after the first iteration, we are left with an
(n − 1)-node graph with minimum cut-set of size k. Again, the degree of each vertex
in the graph must be at least k, and the graph must have at least k(n − 1)/2 edges.
Thus,
k 2
Pr(E2 | F1 ) ≥ 1 − =1− .
k(n − 1)/2 n−1
Similarly,
k 2
Pr(Ei | Fi−1 ) ≥ 1 − =1− .
k(n − i + 1)/2 n−i+1
To compute Pr(Fn−2 ), we use
Pr(Fn−2 ) = Pr(En−2 ∩ Fn−3 ) = Pr(En−2 | Fn−3 ) · Pr(Fn−3 )
= Pr(En−2 | Fn−3 ) · Pr(En−3 | Fn−4 ) · · · Pr(E2 | F1 ) · Pr(F1 )
n−2
n−2
2 n−i−1
≥ 1− =
i=1
n−i+1 i=1
n−i+1
n−2 n−3 n−4 4 3 2 1
= ...
n n−1 n−2 6 5 4 3
2
= .
n(n − 1)
Since the algorithm has a one-sided error, we can reduce the error probability by repeat-
ing the algorithm. Assume that we run the randomized min-cut algorithm n(n − 1) ln n
times and output the minimum size cut-set found in all the iterations. The probability
that the output is not a min-cut set is bounded by
n(n−1) ln n
2 1
1− ≤ e−2 ln n = 2 .
n(n − 1) n
In the first inequality we have used the fact that 1 − x ≤ e−x .
1.6. Exercises
Exercise 1.1: We flip a fair coin ten times. Find the probability of the following events.
(a) The number of heads and the number of tails are equal.
(b) There are more heads than tails.
(c) The ith flip and the (11 − i)th flip are the same for i = 1, . . . , 5.
(d) We flip at least four consecutive heads.
Exercise 1.2: We roll two standard six-sided dice. Find the probability of the following
events, assuming that the outcomes of the rolls are independent.
(a) The two dice show the same number.
(b) The number that appears on the first die is larger than the number on the second.
17
events and probability
Exercise 1.4: We are playing a tournament in which we stop as soon as one of us wins
n games. We are evenly matched, so each of us wins any game with probability 1/2,
independently of other games. What is the probability that the loser has won k games
when the match is over?
Exercise 1.5: After lunch one day, Alice suggests to Bob the following method to
determine who pays. Alice pulls three six-sided dice from her pocket. These dice are
not the standard dice, but have the following numbers on their faces:
r die A – 1, 1, 6, 6, 8, 8;
r die B – 2, 2, 4, 4, 9, 9;
r die C – 3, 3, 5, 5, 7, 7.
The dice are fair, so each side comes up with equal probability. Alice explains that she
and Bob will each pick up one of the dice. They will each roll their die, and the one
who rolls the lowest number loses and will buy lunch. So as to take no advantage, Alice
offers Bob the first choice of the dice.
(a) Suppose that Bob chooses die A and Alice chooses die B. Write out all of the
possible events and their probabilities, and show that the probability that Alice
wins is greater than 1/2.
(b) Suppose that Bob chooses die B and Alice chooses die C. Write out all of the
possible events and their probabilities, and show that the probability that Alice
wins is greater than 1/2.
(c) Since die A and die B lead to situations in Alice’s favor, it would seem that Bob
should choose die C. Suppose that Bob does choose die C and Alice chooses die
A. Write out all of the possible events and their probabilities, and show that the
probability that Alice wins is still greater than 1/2.
Exercise 1.6: Consider the following balls-and-bin game. We start with one black ball
and one white ball in a bin. We repeatedly do the following: choose one ball from the
bin uniformly at random, and then put the ball back in the bin with another ball of the
same color. We repeat until there are n balls in the bin. Show that the number of white
balls is equally likely to be any number between 1 and n − 1.
18
1.6 exercises
Exercise 1.8: I choose a number uniformly at random from the range [1, 1,000,000].
Using the inclusion–exclusion principle, determine the probability that the number cho-
sen is divisible by one or more of 4, 6, and 9.
Exercise 1.9: Suppose that a fair coin is flipped n times. For k > 0, find an upper
bound on the probability that there is a sequence of log2 n + k consecutive heads.
Exercise 1.10: I have a fair coin and a two-headed coin. I choose one of the two coins
randomly with equal probability and flip it. Given that the flip was heads, what is the
probability that I flipped the two-headed coin?
Exercise 1.11: I am trying to send you a single bit, either a 0 or a 1. When I transmit
the bit, it goes through a series of n relays before it arrives to you. Each relay flips the
bit independently with probability p.
(a) Argue that the probability you receive the correct bit is
n/2
n 2k
p (1 − p)n−2k .
k=0
2k
(b) We consider an alternative way to calculate this probability. Let us say the relay
has bias q if the probability it flips the bit is (1 − q)/2. The bias q is therefore a
real number in the range [−1, 1]. Prove that sending a bit through two relays with
bias q1 and q2 is equivalent to sending a bit through a single relay with bias q1 q2 .
(c) Prove that the probability you receive the correct bit when it passes through n relays
as described before (a) is
1 + (1 − 2p)n
.
2
Exercise 1.12: The following problem is known as the Monty Hall problem, after
the host of the game show “Let’s Make a Deal”. There are three curtains. Behind one
curtain is a new car, and behind the other two are goats. The game is played as follows.
19
events and probability
The contestant chooses the curtain that she thinks the car is behind. Monty then opens
one of the other curtains to show a goat. (Monty may have more than one goat to choose
from; in this case, assume he chooses which goat to show uniformly at random.) The
contestant can then stay with the curtain she originally chose or switch to the other
unopened curtain. After that, the location of the car is revealed, and the contestant wins
the car or the remaining goat. Should the contestant switch curtains or not, or does it
make no difference?
Exercise 1.13: A medical company touts its new test for a certain genetic disorder.
The false negative rate is small: if you have the disorder, the probability that the test
returns a positive result is 0.999. The false positive rate is also small: if you do not
have the disorder, the probability that the test returns a positive result is only 0.005.
Assume that 2% of the population has the disorder. If a person chosen uniformly from
the population is tested and the result comes back positive, what is the probability that
the person has the disorder?
Exercise 1.15: Suppose that we roll ten standard six-sided dice. What is the probabil-
ity that their sum will be divisible by 6, assuming that the rolls are independent? (Hint:
Use the principle of deferred decisions, and consider the situation after rolling all but
one of the dice.)
Exercise 1.16: Consider the following game, played with three standard six-sided
dice. If the player ends with all three dice showing the same number, she wins. The
player starts by rolling all three dice. After this first roll, the player can select any one,
two, or all of the three dice and re-roll them. After this second roll, the player can
again select any of the three dice and re-roll them one final time. For questions (a)–(d),
assume that the player uses the following optimal strategy: if all three dice match, the
player stops and wins; if two dice match, the player re-rolls the die that does not match;
and if no dice match, the player re-rolls them all.
(a) Find the probability that all three dice show the same number on the first roll.
(b) Find the probability that exactly two of the three dice show the same number on
the first roll.
(c) Find the probability that the player wins, conditioned on exactly two of the three
dice showing the same number on the first roll.
20
1.6 exercises
(d) By considering all possible sequences of rolls, find the probability that the player
wins the game.
Exercise 1.17: In our matrix multiplication algorithm, we worked over the integers
modulo 2. Explain how the analysis would change if we worked over the integers mod-
ulo k for k > 2.
Exercise 1.19: Give examples of events where Pr(A | B) < Pr(A), Pr(A | B) = Pr(A),
and Pr(A | B) > Pr(A).
Exercise 1.21: Give an example of three random events X, Y, Z for which any pair are
independent but all three are not mutually independent.
Exercise 1.22: (a) Consider the set {1, . . . , n}. We generate a subset X of this set as
follows: a fair coin is flipped independently for each element of the set; if the coin lands
heads then the element is added to X, and otherwise it is not. Argue that the resulting
set X is equally likely to be any one of the 2n possible subsets.
(b) Suppose that two sets X and Y are chosen independently and uniformly at
random from all the 2n subsets of {1, . . . , n}. Determine Pr(X ⊆ Y ) and Pr(X ∪ Y =
{1, . . . , n}). (Hint: Use the part (a) of this problem.)
Exercise 1.23: There may be several different min-cut sets in a graph. Using the
analysis of the randomized min-cut algorithm, argue that there can be at most
n(n − 1)/2 distinct min-cut sets.
Exercise 1.25: To improve the probability of success of the randomized min-cut algo-
rithm, it can be run multiple times.
(a) Consider running the algorithm twice. Determine the number of edge contractions
and bound the probability of finding a min-cut.
(b) Consider the following variation. Starting with a graph with n vertices, first con-
tract the graph down to k vertices using the randomized min-cut algorithm. Make
copies of the graph with k vertices, and now run the randomized algorithm on this
reduced graph times, independently. Determine the number of edge contractions
and bound the probability of finding a minimum cut.
(c) Find optimal (or at least near-optimal) values of k and for the variation in (b) that
maximize the probability of finding a minimum cut while using the same number
of edge contractions as running the original algorithm twice.
Exercise 1.26: Tic-tac-toe always ends up in a tie if players play optimally. Instead,
we may consider random variations of tic-tac-toe.
(a) First variation: Each of the nine squares is labeled either X or O according to an
independent and uniform coin flip. If only one of the players has one (or more)
winning tic-tac-toe combinations, that player wins. Otherwise, the game is a tie.
Determine the probability that X wins. (You may want to use a computer program
to help run through the configurations.)
(b) Second variation: X and O take turns, with the X player going first. On the X
player’s turn, an X is placed on a square chosen independently and uniformly at
random from the squares that are still vacant; O plays similarly. The first player to
have a winning tic-tac-toe combination wins the game, and a tie occurs if neither
player achieves a winning combination. Find the probability that each player wins.
(Again, you may want to write a program to help you.)
22
chapter two
Discrete Random Variables
and Expectation
In this chapter, we introduce the concepts of discrete random variables and expectation
and then develop basic techniques for analyzing the expected performance of algo-
rithms. We apply these techniques to computing the expected running time of the well-
known Quicksort algorithm. In analyzing two versions of Quicksort, we demonstrate
the distinction between the analysis of randomized algorithms, where the probability
space is defined by the random choices made by the algorithm, and the probabilistic
analysis of deterministic algorithms, where the probability space is defined by some
probability distribution on the inputs.
Along the way we define the Bernoulli, binomial, and geometric random variables,
study the expected size of a simple branching process, and analyze the expectation of
the coupon collector’s problem – a probabilistic paradigm that reappears throughout
the book.
When studying a random event, we are often interested in some value associated with
the random event rather than in the event itself. For example, in tossing two dice we
are often interested in the sum of the two dice rather than the separate value of each
die. The sample space in tossing two dice consists of 36 events of equal probability,
given by the ordered pairs of numbers {(1, 1), (1, 2), . . . , (6, 5), (6, 6)}. If the quantity
we are interested in is the sum of the two dice, then we are interested in 11 events (of
unequal probability): the 11 possible outcomes of the sum. Any such function from the
sample space to the real numbers is called a random variable.
Definition 2.1: A random variable X on a sample space is a real-valued (mea-
surable) function on ; that is, X : → R. A discrete random variable is a random
variable that takes on only a finite or countably infinite number of values.
Since random variables are functions, they are usually denoted by a capital letter such
as X or Y, while real numbers are usually denoted by lowercase letters.
23
discrete random variables and expectation
For a discrete random variable X and a real value a, the event “X = a” includes all
the basic events of the sample space in which the random variable X assumes the value
a. That is, “X = a” represents the set {s ∈ | X (s) = a}. We denote the probability of
that event by
Pr(X = a) = Pr(s).
s∈: X (s)=a
If X is the random variable representing the sum of the two dice, then the event X = 4
corresponds to the set of basic events {(1, 3), (2, 2), (3, 1)}. Hence
3 1
Pr(X = 4) = = .
36 12
The definition of independence that we developed for events extends to random
variables.
Definition 2.2: Two random variables X and Y are independent if and only if
Pr((X = x) ∩ (Y = y)) = Pr(X = x) · Pr(Y = y)
for all values x and y. Similarly, random variables X1 , X2 , . . . , Xk are mutually inde-
pendent if and only if, for any subset I ⊆ [1, k] and any values xi , i ∈ I,
Pr (Xi = xi ) = Pr(Xi = xi ).
i∈I i∈I
A basic characteristic of a random variable is its expectation, which is also often called
the mean. The expectation of a random variable is a weighted average of the values
it assumes, where each value is weighted by the probability that the variable assumes
that value.
Definition 2.3: The expectation of a discrete random variable X, denoted by E[X], is
given by
E[X] = i Pr(X = i),
i
where
the summation is over all values in the range of X. The expectation is finite if
i |i| Pr(X = i) converges; otherwise, the expectation is unbounded.
For example, the expectation of the random variable X representing the sum of two
dice is
1 2 3 1
E[X] = ·2+ ·3+ · 4 + ··· + · 12 = 7.
36 36 36 36
You may try using symmetry to give simpler argument for why E[X] = 7.
As an example of where the expectation of a discrete random variable is unbounded,
consider a random variable X that takes on the value 2i with probability 1/2i for i =
1, 2, . . . . The expected value of X is
∞ ∞
1 i
E[X] = 2 = 1 = ∞.
i=1
2i i=1
24
2.1 random variables and expectation
Here we use the somewhat informal notation E[X] = ∞ to express that E[X] is
unbounded.
Theorem 2.1 [Linearity of Expectations]: For any finite collection of discrete ran-
dom variables X1 , X2 , . . . , Xn with finite expectations,
n n
E Xi = E[Xi ].
i=1 i=1
Proof: We prove the statement for two random variables X and Y; the general case
follows by induction. The summations that follow are understood to be over the ranges
of the corresponding random variables:
E[X + Y ] = (i + j) Pr((X = i) ∩ (Y = j))
i j
= i Pr((X = i) ∩ (Y = j)) + j Pr((X = i) ∩ (Y = j))
i j i j
= i Pr((X = i) ∩ (Y = j)) + j Pr((X = i) ∩ (Y = j))
i j j i
= i Pr(X = i) + j Pr(Y = j)
i j
= E[X] + E[Y ].
The first equality follows from Definition 1.2. In the penultimate equation we have used
Theorem 1.6, the Law of Total Probability.
We now use this property to compute the expected sum of two standard dice. Let X =
X1 + X2 , where Xi represents the outcome of die i for i = 1, 2. Then
1
6
7
E[Xi ] = j= .
6 j=1 2
26
2.2 the bernoulli and binomial random variables
To obtain the penultimate line, we used the linearity of expectations. To obtain the last
line we used Lemma 2.2 to simplify E[XE[X]] = E[X] · E[X].
The fact that E[X 2 ] ≥ (E[X])2 is an example of a more general theorem known as
Jensen’s inequality. Jensen’s inequality shows that, for any convex function f, we have
E[ f (X )] ≥ f (E[X]).
Visually, a convex function f has the property that, if you connect two points on the
graph of the function by a straight line, this line lies on or above the graph of the
function. The following fact, which we state without proof, is often a useful alternative
to Definition 2.4.
E[ f (X )] ≥ f (E[X]).
Proof: We prove the theorem assuming that f has a Taylor expansion. Let μ = E[X].
By Taylor’s theorem there is a value c such that
f (c)(x − μ)2
f (x) = f (μ) + f (μ)(x − μ) +
2
≥ f (μ) + f (μ)(x − μ),
since f (c) > 0 by convexity. Taking expectations of both sides and applying linearity
of expectations and Lemma 2.2 yields the result:
An alternative proof of Jensen’s inequality, which holds for any random variable X that
takes on only finitely many values, is presented in Exercise 2.10.
Suppose that we run an experiment that succeeds with probability p and fails with
probability 1 − p.
27
discrete random variables and expectation
The variable Y is called a Bernoulli or an indicator random variable. Note that, for a
Bernoulli random variable,
For example, if we flip a fair coin and consider the outcome “heads” a success, then
the expected value of the corresponding indicator random variable is 1/2.
Consider now a sequence of n independent coin flips. What is the distribution of the
number of heads in the entire sequence? More generally, consider a sequence of n inde-
pendent experiments, each of which succeeds with probability p. If we let X represent
the number of successes in the n experiments, then X has a binomial distribution.
That is, the binomial random variable X equals j when there are exactly j successes and
n − j failures in n independent experiments, each of which is successful with proba-
bility p.
As an exercise, you should show that Definition 2.5 ensures that nj=0 Pr(X = j) =
1. This is necessary for the binomial random variable to have a valid probability func-
tion, according to Definition 1.2.
The binomial random variable arises in many contexts, especially in sampling. As a
practical example, suppose that we want to gather data about the packets going through
a router by postprocessing them. We might want to know the approximate fraction of
packets from a certain source or of a certain data type. We do not have the memory
available to store all of the packets, so we choose to store a random subset – or sample
– of the packets for later analysis. If each packet is stored with probability p and if n
packets go through the router each day, then the number of sampled packets each day
is a binomial random variable X with parameters n and p. If we want to know how
much memory is necessary for such a sample, a natural starting point is to determine
the expectation of the random variable X.
Sampling in this manner arises in other contexts as well. For example, by sampling
the program counter while a program runs, one can determine what parts of a program
are taking the most time. This knowledge can be used to aid dynamic program opti-
mization techniques such as binary rewriting, where the executable binary form of a
program is modified while the program executes. Since rewriting the executable as the
program runs is expensive, sampling helps the optimizer to determine when it will be
worthwhile.
28
2.3 conditional expectation
n−1
(n − 1)!
= np pk (1 − p)(n−1)−k
k=0
k! ((n − 1) − k)!
n − 1
n−1
= np pk (1 − p)(n−1)−k
k=0
k
= np,
Definition 2.6: E[Y | Z = z] = y Pr(Y = y | Z = z),
y
For example, suppose that we independently roll two standard six-sided dice. Let X1
be the number that shows on the first die, X2 the number on the second die, and X the
sum of the numbers on the two dice. Then
8
1 11
E[X | X1 = 2] = x Pr(X = x | X1 = 2) = x· = .
x x=3
6 2
where the sum is over all values in the range of Y and all of the expectations exist.
Proof: Pr(Y = y)E[X | Y = y] = Pr(Y = y) x Pr(X = x | Y = y)
y y x
= x Pr(X = x | Y = y) Pr(Y = y)
x y
= x Pr(X = x ∩ Y = y)
x y
= x Pr(X = x) = E[X].
x
Lemma 2.6: For any finite collection of discrete random variables X1 , X2 , . . . , Xn with
finite expectations and for any random variable Y,
n n
E Xi | Y = y = E[Xi | Y = y].
i=1 i=1
Perhaps somewhat confusingly, the conditional expectation is also used to refer to the
following random variable.
Definition 2.7: The expression E[Y | Z] is a random variable f (Z) that takes on the
value E[Y | Z = z] when Z = z.
We emphasize that E[Y | Z] is not a real value; it is actually a function of the random
variable Z. Hence E[Y | Z] is itself a function from the sample space to the real numbers
and can therefore be thought of as a random variable.
In the previous example of rolling two dice,
1 +6
X
1 7
E[X | X1 ] = x Pr(X = x | X1 ) = x· = X1 + .
x x=X1 +1
6 2
yi−1
= j Pr Zk = j
j≥0 k=1
yi−1
=E Zk
k=1
yi−1
= E[Zk ]
k=1
= yi−1 np.
In the third line we have used that the Zk are all independent binomial random variables;
in particular, the value of each Zk is independent of Yi−1 , allowing us to remove the
conditioning. In the fifth line, we have applied the linearity of expectations.
Applying Theorem 2.7, we can compute the expected size of the ith generation
inductively. We have
E[Yi ] = E[E[Yi | Yi−1 ]] = E[Yi−1 np] = npE[Yi−1 ].
By induction on i, and using the fact that Y0 = 1, we then obtain
E[Yi ] = (np)i .
The expected total number of copies of process S generated by the program is
given by
E Yi = E[Yi ] = (np)i .
i≥0 i≥0 i≥0
Suppose that we flip a coin until it lands on heads. What is the distribution of the number
of flips? This is an example of a geometric distribution, which arises in the following
situation: we perform a sequence of independent trials until the first success, where
each trial succeeds with probability p.
Definition 2.8: A geometric random variable X with parameter p is given by the fol-
lowing probability distribution on n = 1, 2, . . . ,:
Pr(X = n) = (1 − p)n−1 p.
That is, for the geometric random variable X to equal n, there must be n − 1 failures,
followed by a success.
As an exercise, you should show that the geometric random variable satisfies
Pr(X = n) = 1.
n≥1
Again, this is necessary for the geometric random variable to have a valid probability
function, according to Definition 1.2.
In the context of our example from Section 2.2 of sampling packets on a router, if
packets are sampled with probability p, then the number of packets transmitted after the
last sampled packet until and including the next sampled packet is given by a geometric
random variable with parameter p.
Geometric random variables are said to be memoryless because the probability that
you will reach your first success n trials from now is independent of the number of
failures you have experienced. Informally, one can ignore past failures because they do
not change the distribution of the number of future trials until first success. Formally,
we have the following statement.
Lemma 2.8: For a geometric random variable X with parameter p and for n > 0,
(1 − p)n+k−1 p
=
(1 − p)k
= (1 − p)n−1 p
= Pr(X = n).
The fourth equality uses the fact that, for 0 < x < 1, ∞i=k x = x /(1 − x).
i k
33
discrete random variables and expectation
Lemma 2.9: Let X be a discrete random variable that takes on only nonnegative inte-
ger values. Then
∞
E[X] = Pr(X ≥ i).
i=1
∞
∞
∞
Proof: Pr(X ≥ i) = Pr(X = j)
i=1 i=1 j=i
∞
j
= Pr(X = j)
j=1 i=1
∞
= j Pr(X = j)
j=1
= E[X].
The interchange of (possibly) infinite summations is justified, since the terms being
summed are all nonnegative.
Hence
∞
E[X] = Pr(X ≥ i)
i=1
∞
= (1 − p)i−1
i=1
1
=
1 − (1 − p)
1
= .
p
Thus, for a fair coin where p = 1/2, on average it takes two flips to see the first
heads.
There is another approach to finding the expectation of a geometric random variable
X with parameter p – one that uses conditional expectations and the memoryless prop-
erty of geometric random variables. Recall that X corresponds to the number of flips
until the first heads given that each flip is heads with probability p. Let Y = 0 if the first
34
2.4 the geometric distribution
flip is tails and Y = 1 if the first flip is heads. By the identity from Lemma 2.5,
i−1
pi = 1 − .
n
1 n
E[Xi ] = = .
pi n−i+1
35
discrete random variables and expectation
and
n n
1 1
≤ dx = ln n.
k=2
k x=1 x
This is clarified in Figure 2.1, where the area below the curve f (x) = 1/x corre-
sponds
n to the integral
n and the areas of the shaded regions correspond to the summations
k=1 1/k and k=2 1/k.
Hence ln n ≤ H(n) ≤ ln n + 1, proving the claim.
As a simple application of the coupon collector’s problem, suppose that packets are
sent in a stream from a source host to a destination host along a fixed path of routers.
The host at the destination would like to know which routers the stream of packets has
passed through, in case it finds later that some router damaged packets that it processed.
If there is enough room in the packet header, each router can append its identification
number to the header, giving the path. Unfortunately, there may not be that much room
available in the packet header.
Suppose instead that each packet header has space for exactly one router identi-
fication number, and this space is used to store the identification of a router chosen
uniformly at random from all of the routers on the path. This can actually be accom-
plished easily; we consider how in Exercise 2.18. Then, from the point of view of the
destination host, determining all the routers on the path is like a coupon collector’s
problem. If there are n routers along the path, then the expected number of packets in
36
2.5 application: the expected run-time of quicksort
– –
+ +
– + – +
Figure 2.1: Approximating the area above and below f (x) = 1/x.
the stream that must arrive before the destination host knows all of the routers on the
path is nH(n) = n ln n + (n).
Quicksort is a simple – and, in practice, very efficient – sorting algorithm. The input is
a list of n numbers x1 , x2 , . . . , xn . For convenience, we will assume that the numbers
are distinct. A call to the Quicksort function begins by choosing a pivot element from
the set. Let us assume the pivot is x. The algorithm proceeds by comparing every other
element to x, dividing the list of elements into two sublists: those that are less than x
and those that are greater than x. Notice that if the comparisons are performed in the
natural order, from left to right, then the order of the elements in each sublist is the
same as in the initial list. Quicksort then recursively sorts these sublists.
In the worst case, Quicksort requires (n2 ) comparison operations. For example,
suppose our input has the form x1 = n, x2 = n − 1, . . . , xn−1 = 2, xn = 1. Suppose
also that we adopt the rule that the pivot should be the first element of the list. The
first pivot chosen is then n, so Quicksort performs n − 1 comparisons. The division
has yielded one sublist of size 0 (which requires no additional work) and another of
size n − 1, with the order n − 1, n − 2, . . . , 2, 1. The next pivot chosen is n − 1, so
Quicksort performs n − 2 comparisons and is left with one group of size n − 2 in the
order n − 2, n − 3, . . . , 2, 1. Continuing in this fashion, Quicksort performs
n(n − 1)
(n − 1) + (n − 2) + · · · + 2 + 1 = comparisons.
2
This is not the only bad case that leads to (n2 ) comparisons; similarly poor perfor-
mance occurs if the pivot element is chosen from among the smallest few or the largest
few elements each time.
37
discrete random variables and expectation
Quicksort Algorithm:
We clearly made a bad choice of pivots for the given input. A reasonable choice of
pivots would require many fewer comparisons. For example, if our pivot always splits
the list into two sublists of size at most n/2, then the number of comparisons C(n)
would obey the following recurrence relation:
C(n) ≤ 2C(n/2) + (n).
The solution to this equation yields C(n) = O(n log n), which is the best possible result
for comparison-based sorting. In fact, any sequence of pivot elements that always split
the input list into two sublists each of size at least cn for some constant c would yield
an O(n log n) running time.
This discussion provides some intuition for how we would like pivots to be chosen.
In each iteration of the algorithm there is a good set of pivot elements that split the
input list into two almost equal sublists; it suffices if the sizes of the two sublists are
within a constant factor of each other. There is also a bad set of pivot elements that do
not split up the list significantly. If good pivots are chosen sufficiently often, Quicksort
will terminate quickly. How can we guarantee that the algorithm chooses good pivot
elements sufficiently often? We can resolve this problem in one of two ways.
First, we can change the algorithm to choose the pivots randomly. This makes Quick-
sort a randomized algorithm; the randomization makes it extremely unlikely that we
repeatedly choose the wrong pivots. We demonstrate shortly that the expected number
of comparisons made by a simple randomized Quicksort is 2n ln n + O(n), matching
(up to constant factors) the (n log n) bound for comparison-based sorting. Here, the
expectation is over the random choice of pivots.
A second possibility is that we can keep our deterministic algorithm, using the first
list element as a pivot, but consider a probabilistic model of the inputs. A permutation
of a set of n distinct items is just one of the n! orderings of these items. Instead of
looking for the worst possible input, we assume that the input items are given to us in
a random order. This may be a reasonable assumption for some applications; alterna-
tively, this could be accomplished by ordering the input list according to a randomly
38
2.5 application: the expected run-time of quicksort
chosen permutation before running the deterministic Quicksort algorithm. In this case,
we have a deterministic algorithm but a probabilistic analysis based on a model of the
inputs. We again show in this setting that the expected number of comparisons made
is 2n ln n + O(n). Here, the expectation is over the random choice of inputs.
The same techniques are generally used both in analyses of randomized algorithms
and in probabilistic analyses of deterministic algorithms. Indeed, in this application the
analysis of the randomized Quicksort and the probabilistic analysis of the deterministic
Quicksort under random inputs are essentially the same.
Let us first analyze Random Quicksort, the randomized algorithm version of
Quicksort.
Theorem 2.11: Suppose that, whenever a pivot is chosen for Random Quicksort, it
is chosen independently and uniformly at random from all possibilities. Then, for any
input, the expected number of comparisons made by Random Quicksort is 2n ln n +
O(n).
Proof: Let y1 , y2 , . . . , yn be the same values as the input values x1 , x2 , . . . , xn but sorted
in increasing order. For i < j, let Xi j be a random variable that takes on the value 1 if
yi and y j are compared at any time over the course of the algorithm, and 0 otherwise.
Then the total number of comparisons X satisfies
n−1
n
X= Xi j ,
i=1 j=i+1
and
n−1
n
E[X] = E Xi j
i=1 j=i+1
n−1
n
= E[Xi j ]
i=1 j=i+1
k = j − i + 1 then yields
n−1
n
2
E[X] =
i=1 j=i+1
j−i+1
n−1 n−i+1
2
=
i=1 k=2
k
2
n n+1−k
=
k=2 i=1
k
n
2
= (n + 1 − k)
k=2
k
2
n
= (n + 1) − 2(n − 1)
k=2
k
n
1
= (2n + 2) − 4n.
k=1
k
Notice that we used a rearrangement of the double summation to obtain a clean form
for the expectation.
Recalling that the summation H(n) = nk=1 1/k satisfies H(n) = ln n + (1), we
have E[X] = 2n ln n + (n).
Next we consider the deterministic version of Quicksort, on random input. We assume
that the order of the elements in each recursively constructed sublist is the same as in
the initial list.
Theorem 2.12: Suppose that, whenever a pivot is chosen for Quicksort, the first ele-
ment of the sublist is chosen. If the input is chosen uniformly at random from all pos-
sible permutations of the values, then the expected number of comparisons made by
Deterministic Quicksort is 2n ln n + O(n).
Proof: The proof is essentially the same as for Random Quicksort. Again, yi and y j
are compared if and only if either yi or y j is the first pivot selected by Quicksort from
the set Y i j . Since the order of elements in each sublist is the same as in the original list,
the first pivot selected from the set Y i j is just the first element from Y i j in the input list,
and since all possible permutations of the input values are equally likely, every element
in Y i j is equally likely to be first. From this, we can again use linearity of expectations
in the same way as in the analysis of Random Quicksort to obtain the same expression
for E[X].
2.6. Exercises
Exercise 2.1: Suppose we roll a fair k-sided die with the numbers 1 through k on the
die’s faces. If X is the number that appears, what is E[X]?
40
2.6 exercises
Exercise 2.2: A monkey types on a 26-letter keyboard that has lowercase letters only.
Each letter is chosen independently and uniformly at random from the alphabet. If the
monkey types 1,000,000 letters, what is the expected number of times the sequence
“proof” appears?
Exercise 2.3: Give examples of functions f and random variables X where E[ f (X )] <
f (E[X]), E[ f (X )] = f (E[X]), and E[ f (X )] > f (E[X]).
Exercise 2.4: Prove that E[X k ] ≥ E[X]k for any even integer k ≥ 1.
Exercise 2.5: If X is a B(n, 1/2) random variable with n ≥ 1, show that the probability
that X is even is 1/2.
Exercise 2.6: Suppose that we independently roll two standard six-sided dice. Let X1
be the number that shows on the first die, X2 the number on the second die, and X the
sum of the numbers on the two dice.
Exercise 2.7: Let X and Y be independent geometric random variables, where X has
parameter p and Y has parameter q.
You may find it helpful to keep in mind the memoryless property of geometric random
variables.
Exercise 2.8: (a) Alice and Bob decide to have children until either they have their first
girl or they have k ≥ 1 children. Assume that each child is a boy or girl independently
with probability 1/2 and that there are no multiple births. What is the expected number
of female children that they have? What is the expected number of male children that
they have?
(b) Suppose Alice and Bob simply decide to keep having children until they have
their first girl. Assuming that this is possible, what is the expected number of boys that
they have?
Exercise 2.9: (a) Suppose that we roll twice a fair k-sided die with the numbers 1
through k on the die’s faces, obtaining values X1 and X2 . What is E[max(X1 , X2 )]?
What is E[min(X1 , X2 )]?
41
discrete random variables and expectation
Exercise 2.10: (a) Show by induction that if f : R → R is convex then, for any
x1 , x2 , . . . , xn and λ1 , λ2 , . . . , λn with ni=1 λi = 1,
n
n
f λi xi ≤ λi f (xi ). (2.2)
i=1 i=1
Exercise 2.12: We draw cards uniformly at random with replacement from a deck of
n cards. What is the expected number of cards we must draw until we have seen all n
cards in the deck? If we draw 2n cards, what is the expected number of cards in the
deck that are not chosen at all? Chosen exactly once?
Exercise 2.13: (a) Consider the following variation of the coupon collector’s problem.
Each box of cereal contains one of 2n different coupons. The coupons are organized
into n pairs, so that coupons 1 and 2 are a pair, coupons 3 and 4 are a pair, and so on.
Once you obtain one coupon from every pair, you can obtain a prize. Assuming that
the coupon in each box is chosen independently and uniformly at random from the 2n
possibilities, what is the expected number of boxes you must buy before you can claim
the prize?
(b) Generalize the result of the problem in part (a) for the case where there are kn
different coupons, organized into n disjoint sets of k coupons, so that you need one
coupon from every set.
Exercise 2.14: The geometric distribution arises as the distribution of the number of
times we flip a coin until it comes up heads. Consider now the distribution of the number
of flips X until the kth head appears, where each coin flip comes up heads independently
with probability p. Prove that this distribution is given by
n−1
Pr(X = n) = pk (1 − p)n−k
k−1
for n ≥ k. (This is known as the negative binomial distribution.)
Exercise 2.15: For a coin that comes up heads independently with probability p on
each flip, what is the expected number of flips until the kth heads?
42
2.6 exercises
(a) Let n be a power of 2. Show that the expected number of streaks of length log2 n + 1
is 1 − o(1).
(b) Show that, for sufficiently large n, the probability that there is no streak of length
at least
log2 n − 2 log2 log2 n is less than 1/n. (Hint: Break the sequence of flips
up into disjoint blocks of
log2 n − 2 log2 log2 n consecutive flips, and use that the
event that one block is a streak is independent of the event that any other block is
a streak.)
Exercise 2.17: Recall the recursive spawning process described in Section 2.3. Sup-
pose that each call to process S recursively spawns new copies of the process S, where
the number of new copies is 2 with probability p and 0 with probability 1 − p. If Yi
denotes the number of copies of S in the ith generation, determine E[Yi ]. For what
values of p is the expected total number of copies bounded?
Exercise 2.18: The following approach is often called reservoir sampling. Suppose
we have a sequence of items passing by one at a time. We want to maintain a sample
of one item with the property that it is uniformly distributed over all the items that we
have seen at each step. Moreover, we want to accomplish this without knowing the total
number of items in advance or storing all of the items that we see.
Consider the following algorithm, which stores just one item in memory at all times.
When the first item appears, it is stored in the memory. When the kth item appears, it
replaces the item in memory with probability 1/k. Explain why this algorithm solves
the problem.
Exercise 2.19: Suppose that we modify the reservoir sampling algorithm of Exer-
cise 2.18 so that, when the kth item appears, it replaces the item in memory with prob-
ability 1/2. Describe the distribution of the item in memory.
Exercise 2.23: Linear insertion sort can sort an array of numbers in place. The first
and second numbers are compared; if they are out of order, they are swapped so that
they are in sorted order. The third number is then placed in the appropriate place in the
sorted order. It is first compared with the second; if it is not in the proper order, it is
swapped and compared with the first. Iteratively, the kth number is handled by swap-
ping it downward until the first k numbers are in sorted order. Determine the expected
number of swaps that need to be made with a linear insertion sort when the input is a
random permutation of n distinct numbers.
Exercise 2.24: We roll a standard fair die over and over. What is the expected number
of rolls until the first pair of consecutive sixes appears? (Hint: The answer is not 36.)
Exercise 2.25: A blood test is being performed on n individuals. Each person can
be tested separately, but this is expensive. Pooling can decrease the cost. The blood
samples of k people can be pooled and analyzed together. If the test is negative, this
one test suffices for the group of k individuals. If the test is positive, then each of the k
persons must be tested separately and thus k + 1 total tests are required for the k people.
Suppose that we create n/k disjoint groups of k people (where k divides n) and use the
pooling method. Assume that each person has a positive result on the test independently
with probability p.
(a) What is the probability that the test for a pooled sample of k people will be positive?
(b) What is the expected number of tests necessary?
(c) Describe how to find the best value of k.
(d) Give an inequality that shows for what values of p pooling is better than just testing
every individual.
the cycles could be self-loops. What is the expected number of cycles in a random
permutation of n numbers?
Exercise 2.28: Consider a simplified version of roulette in which you wager x dollars
on either red or black. The wheel is spun, and you receive your original wager plus
another x dollars if the ball lands on your color; if the ball doesn’t land on your color,
you lose your wager. Each color occurs independently with probability 1/2. (This is a
simplification because real roulette wheels have one or two spaces that are neither red
nor black, so the probability of guessing the correct color is actually less than 1/2.)
The following gambling strategy is a popular one. On the first spin, bet 1 dollar. If
you lose, bet 2 dollars on the next spin. In general, if you have lost on the first k − 1
spins, bet 2k−1 dollars on the kth spin. Argue that by following this strategy you will
eventually win a dollar. Now let X be the random variable that measures your maximum
loss before winning (i.e., the amount of money you have lost before the play on which
you win). Show that E[X] is unbounded. What does it imply about the practicality of
this strategy?
Exercise 2.30: In the roulette problem of Exercise 2.28, we found that with probability
1 you eventually win a dollar. Let X j be the amount you win on the jth bet. (This
might be 0 if you have already won a previous bet.) Determine E[X j ] and show that,
by applying the linearity of expectations, you find your expected winnings are 0. Does
the linearity of expectations hold in this case? (Compare with Exercise 2.29.)
Exercise 2.31: A variation on the roulette problem of Exercise 2.28 is the following.
We repeatedly flip a fair coin. You pay j dollars to play the game. If the first head comes
up on the kth flip, you win 2k /k dollars. What are your expected winnings? How much
would you be willing to pay to play the game?
Exercise 2.32: You need a new staff assistant, and you have n people to interview. You
want to hire the best candidate for the position. When you interview a candidate, you
can give them a score, with the highest score being the best and no ties being possible.
45
discrete random variables and expectation
You interview the candidates one by one. Because of your company’s hiring practices,
after you interview the kth candidate, you either offer the candidate the job before the
next interview or you forever lose the chance to hire that candidate. We suppose the
candidates are interviewed in a random order, chosen uniformly at random from all n!
possible orderings.
We consider the following strategy. First, interview m candidates but reject them all;
these candidates give you an idea of how strong the field is. After the mth candidate,
hire the first candidate you interview who is better than all of the previous candidates
you have interviewed.
(a) Let E be the event that we hire the best assistant, and let Ei be the event that ith
candidate is the best and we hire him. Determine Pr(Ei ), and show that
m
n
1
Pr(E ) = .
n j=m+1 j − 1
n 1
(b) Bound j=m+1 j−1 to obtain
m m
(ln n − ln m) ≤ Pr(E ) ≤ (ln(n − 1) − ln(m − 1)).
n n
(c) Show that m(ln n − ln m)/n is maximized when m = n/e, and explain why this
means Pr(E ) ≥ 1/e for this choice of m.
46
chapter three
Moments and Deviations
In this and the next chapter we examine techniques for bounding the tail distribution,
the probability that a random variable assumes values that are far from its expectation.
In the context of analysis of algorithms, these bounds are the major tool for estimating
the failure probability of algorithms and for establishing high probability bounds on
their run-time. In this chapter we study Markov’s and Chebyshev’s inequalities and
demonstrate their application in an analysis of a randomized median algorithm. The
next chapter is devoted to the Chernoff bound and its applications.
Markov’s inequality, formulated in the next theorem, is often too weak to yield useful
results, but it is a fundamental tool in developing more sophisticated bounds.
Theorem 3.1 [Markov’s Inequality]: Let X be a random variable that assumes only
nonnegative values. Then, for all a > 0,
E[X]
Pr(X ≥ a) ≤ .
a
Proof: For a > 0, let
1 if X ≥ a,
I=
0 otherwise,
and note that, since X ≥ 0,
X
I≤ . (3.1)
a
Because I is a 0–1 random variable, E[I] = Pr(I = 1) = Pr(X ≥ a).
Taking expectations in (3.1) thus yields
X E[X]
Pr(X ≥ a) = E[I] ≤ E = .
a a
47
moments and deviations
For example, suppose we use Markov’s inequality to bound the probability of obtaining
more than 3n/4 heads in a sequence of n fair coin flips. Let
1 if the ith coin flip is heads,
Xi =
0 otherwise,
n
and let X = i=1 Xi denote the number of heads in the n coin flips. Since E[Xi ] =
Pr(Xi = 1) = 1/2, it follows that E[X] = ni=1 E[Xi ] = n/2. Applying Markov’s
inequality, we obtain
E[X] n/2 2
Pr(X ≥ 3n/4) ≤ = = .
3n/4 3n/4 3
Markov’s inequality gives the best tail bound possible when all we know is the expec-
tation of the random variable and that the variable is nonnegative (see Exercise 3.16). It
can be improved upon if more information about the distribution of the random variable
is available.
Additional information about a random variable is often expressed in terms of its
moments. The expectation is also called the first moment of a random variable. More
generally, we define the moments of a random variable as follows.
Definition 3.1: The kth moment of a random variable X is E[X k ].
A significantly stronger tail bound is obtained when the second moment (E[X 2 ]) is also
available. Given the first and second moments, one can compute the variance and stan-
dard deviation of the random variable. Intuitively, the variance and standard deviation
offer a measure of how far the random variable is likely to be from its expectation.
Definition 3.2: The variance of a random variable X is defined as
Var[X] = E[(X − E[X])2 ] = E[X 2 ] − (E[X])2 .
The standard deviation of a random variable X is
σ [X] = Var[X].
The two forms of the variance in the definition are equivalent, as is easily seen by using
the linearity of expectations. Keeping in mind that E[X] is a constant, we have
E[(X − E[X])2 ] = E[X 2 − 2XE[X] + E[X]2 ]
= E[X 2 ] − 2E[XE[X]] + E[X]2
= E[X 2 ] − 2E[X]E[X] + E[X]2
= E[X 2 ] − (E[X])2 .
If a random variable X is constant – so that it always assumes the same value – then
its variance and standard deviation are both zero. More generally, if a random vari-
able X takes on the value kE[X] with probability 1/k and the value 0 with probability
48
3.2 variance and moments of a random variable
√
1 − 1/k, then its variance is (k − 1)(E[X])2 and its standard deviation is k − 1E[X].
These cases help demonstrate the intuition that the variance (and standard deviation)
of a random variable are small when the random variable assumes values close to its
expectation and are large when it assumes values far from its expectation.
We have previously seen that the expectation of the sum of two random variables is
equal to the sum of their individual expectations. It is natural to ask whether the same
is true for the variance. We find that the variance of the sum of two random variable
has an extra term, called the covariance.
Definition 3.3: The covariance of two random variables X and Y is
Cov(X, Y ) = E[(X − E[X])(Y − E[Y ])].
Theorem 3.2: For any two random variables X and Y,
Var[X + Y ] = Var[X] + Var[Y ] + 2 Cov(X, Y ).
Proof:
Var[X + Y ] = E[(X + Y − E[X + Y ])2 ]
= E[(X + Y − E[X] − E[Y ])2 ]
= E[(X − E[X])2 + (Y − E[Y ])2 + 2(X − E[X])(Y − E[Y ])]
= E[(X − E[X])2 ] + E[(Y − E[Y ])2 ] + 2E[(X − E[X])(Y − E[Y ])]
= Var[X] + Var[Y ] + 2 Cov(X, Y ).
The extension of this theorem to a sum of any finite number of random variables is
proven in Exercise 3.14.
The variance of the sum of two (or any finite number of) random variables does equal
the sum of the variances when the random variables are independent. Equivalently, if X
and Y are independent random variables, then their covariance is equal to zero. To prove
this result, we first need a result about the expectation of the product of independent
random variables.
Theorem 3.3: If X and Y are two independent random variables, then
E[X · Y ] = E[X] · E[Y ].
Proof: In the summations that follow, let i take on all values in the range of X, and let
j take on all values in the range of Y:
E[X · Y ] = (i · j) · Pr((X = i) ∩ (Y = j))
i j
= (i · j) · Pr(X = i) · Pr(Y = j)
i j
= i · Pr(X = i) j · Pr(Y = j)
i j
= E[X] · E[Y ],
where the independence of X and Y is used in the second line.
49
moments and deviations
Unlike the linearity of expectations, which holds for the sum of random variables
whether they are independent or not, the result that the expectation of the product of
two (or more) random variables is equal to the product of their expectations does not
necessarily hold if the random variables are dependent. To see this, let Y and Z each
correspond to fair coin flips, with Y and Z taking on the value 0 if the flip is heads
and 1 if the flip is tails. Then E[Y ] = E[Z] = 1/2. If the two flips are independent,
then Y · Z is 1 with probability 1/4 and 0 otherwise, so indeed E[Y · Z] = E[Y ] · E[Z].
Suppose instead that the coin flips are dependent in the following way: the coins are
tied together, so Y and Z either both come up heads or both come up tails together. Each
coin considered individually is still a fair coin flip, but now Y · Z is 1 with probability
1/2 and so E[Y · Z] = E[Y ] · E[Z].
Cov(X, Y ) = 0
and
Proof:
In the second equation we have used the fact that, since X and Y are independent, so
are X − E[X] and Y − E[Y ] and hence Theorem 3.3 applies. For the last equation we
use the fact that, for any random variable Z,
By induction we can extend the result of Corollary 3.4 to show that the variance of
the sum of any finite number of independent random variables equals the sum of their
variances.
50
3.3 chebyshev’s inequality
Using the expectation and the variance of the random variable, one can derive a signif-
icantly stronger tail bound known as Chebyshev’s inequality.
Theorem 3.6 [Chebyshev’s Inequality]: For any a > 0,
Var[X]
Pr(|X − E[X]| ≥ a) ≤ .
a2
51
moments and deviations
52
3.3 chebyshev’s inequality
In fact, we can do slightly better. Chebyshev’s inequality yields that 4/n is actu-
ally a bound on the probability that X is either smaller than n/4 or larger than 3n/4,
so by symmetry the probability that X is greater than 3n/4 is actually 2/n. Cheby-
shev’s inequality gives a significantly better bound than Markov’s inequality for large
n.
1
Pr(X ≥ 2nHn ) ≤ .
2
To use Chebyshev’s inequality,
we need to find the variance of X. Recall again from
Section 2.4.1 that X = ni=1 Xi , where the Xi are geometric random variables with
parameter (n − i + 1)/n. In this case, the Xi are independent because the time to col-
lect the ith coupon does not depend on how long it took to collect the previous i − 1
coupons. Hence
n n
Var[X] = Var Xi = Var[Xi ],
i=1 i=1
∞
1
= xi .
1−x i=0
∞
1
= ixi−1
(1 − x)2 i=0
∞
= (i + 1)xi ;
i=0
∞
2
= i(i − 1)xi−2
(1 − x)3 i=0
∞
= (i + 1)(i + 2)xi .
i=0
53
moments and deviations
Finally, we reach
For a geometric random variable Y, E[Y 2 ] can also be derived using conditional expec-
tations. We use that Y corresponds to the number of flips until the first heads, where
each flip is heads with probability p. Let X = 0 if the first flip is tails and X = 1 if the
first flip is heads. By Lemma 2.5,
54
3.4 median and mean
Let X be a random variable. The median of X is defined to be any value m such that
Pr(X ≤ m) ≥ 1/2 and Pr(X ≥ m) ≥ 1/2.
55
moments and deviations
For example, for a discrete random variable that is uniformly distributed over an odd
number of distinct, sorted values x1 , x2 , . . . , x2k+1 , the median is the middle value xk+1 .
For a discrete random variable that is uniformly distributed over an even number of
values x1 , x2 , . . . , x2k , any value in the range (xk , xk+1 ) would be a median.
The expectation E[X] and the median are usually different numbers. For distribu-
tions with a unique median that are symmetric around either the mean or median, the
median is equal to the mean. For some distributions, the median can be easier to work
with than the mean, and in some settings it is a more natural quantity to work with.
The following theorem gives an alternate characterization of the mean and median:
Theorem 3.9: For any random variable X with finite expectation E[X] and finite
median m,
E[(X − c)2 ],
and
2. the median m is a value of c that minimizes the expression
E[|X − c|].
and taking the derivative with respect to c shows that c = E[X] yields the minimum.
For the second result, we want to show that that for any value c that is not a
median and for any median m, we have E[|X − c|] > E[|X − m|], or equivalently that
E[|X − c| − |X − m|] > 0. In that case the value of c that minimizes E[|X − c|] will
be a median. (In fact, as a by-product, we show that for any two medians m and m ,
E[|X − m|] = E[|X − m |].)
Let us take the case where c > m for a median m, and c is not a median, so Pr(X ≥
c) < 1/2. A similar argument holds for any value of c such that Pr(X ≤ c) < 1/2.
For x ≥ c, |x − c| − |x − m| = m − c. For m < x < c, |x − c| − |x − m| = c + m −
2x > m − c. Finally, for x ≤ m, |x − c| − |x − m| = c − m. Combining the three cases,
we have
E[|X − c| − |X − m|]
= Pr(X ≥ c)(m − c) + Pr(X = x)(c + m − 2x) + Pr(X ≤ m)(c − m).
x:m<x<c
where the inequality comes from Pr(X ≥ c) < 1/2 and m < c. (Note here that if c were
another median, so Pr(X ≥ c) = 1/2, we would obtain E[|X − c| − |X − m|] = 0, as
stated earlier.)
If Pr(m < X < c) = 0, then
E[|X − c| − |X − m|]
= Pr(X ≥ c)(m − c) + Pr(X = x)(c + m − 2x) + Pr(X ≤ m)(c − m)
x:m<x<c
> Pr(X > m)(m − c) + Pr(X ≤ m)(c − m)
1 1
> (m − c) + (c − m)
2 2
= 0,
where here the first inequality comes from c + m − 2x > m − c for any value of x
with non-zero probability in the range m < x < c. (This case cannot hold if c and m
are both medians, as in this case we cannot have Pr(X ≥ m) = 1/2 and Pr(X ≥ c) =
1/2.)
Interestingly, for well-behaved random variables, the median and the mean cannot
deviate from each other too much.
Theorem 3.10: If X is a random variable with finite standard deviation σ , expectation
μ, and median m, then
|μ − m| ≤ σ.
Proof: The proof follows from the following sequence:
|μ − m| = |E[X] − m|
= |E[X − m]|
≤ E[|X − m|]
≤ E[|X − μ|]
≤ E[(X − μ)2 ]
= σ.
Here the first inequality follows from Jensen’s inequality, the second inequality follows
from the result that the median minimizes E[|X − c|], and the third inequality is again
Jensen’s inequality.
In Exercise 3.19, we suggest another way of proving this result.
Given a set S of n elements drawn from a totally ordered universe, the median of S is
an element m of S such that at least
n/2 elements in S are less than or equal to m and
at least
n/2 + 1 elements in S are greater than or equal to m. If the elements in S are
57
moments and deviations
distinct, then m is the (n/2)th element in the sorted order of S. Note that the median
of a set is similar to but slightly different from the the median of a random variable
defined in Section 3.4.
The median can be easily found deterministically in O(n log n) steps by sorting,
and there is a relatively complex deterministic algorithm that computes the median in
O(n) time. Here we analyze a randomized linear time algorithm that is significantly
simpler than the deterministic one and yields a smaller constant factor in the linear
running time. To simplify the presentation, we assume that n is odd and that the ele-
ments in the input set S are distinct. The algorithm and analysis can be easily modified
to include the case of a multi-set S (see Exercise 3.24) and a set with an even number of
elements.
√
this choice, the set C includes all the elements of S that are between the 2 n sample
points surrounding the median of R. The analysis will clarify that the choice of the size
of R and the choices for d and u are tailored to guarantee both that (a) the set C is large
enough to include m with high probability and (b) the set C is sufficiently small so that
it can be sorted in sublinear time with high probability.
A formal description of the procedure is presented as Algorithm 3.1. In what follows,
√
for convenience we treat n and n3/4 as integers.
The interesting part of the analysis that remains after Theorem 3.11 is bounding the
probability that the algorithm outputs FAIL. We bound this probability by identifying
59
moments and deviations
three “bad” events such that, if none of these bad events occurs, the algorithm does not
fail. In a series of lemmas, we then bound the probability of each of these events and
show that the sum of these probabilities is only O(n−1/4 ).
Consider the following three events:
√
E 1 : Y1 = |{r ∈ R | r ≤ m}| < 12 n3/4 − n;
√
E2 : Y2 = |{r ∈ R | r ≥ m}| < 12 n3/4 − n;
E3 : |C| > 4n3/4 .
Lemma 3.12: The randomized median algorithm fails if and only if at least one of E1 ,
E2 , or E3 occurs.
Proof: Failure in step 7 of the algorithm is equivalent to the event E3 . Failure in step
6 of the algorithm occurs if and only if d > n/2 or u > n/2. But for d > n/2, the
√
1 3/4
2
n − n th smallest element of R must be larger than m; this is equivalent to the
event E1 . Similarly, u > n/2 is equivalent to the event E2 .
Lemma 3.13:
1 −1/4
Pr(E1 ) ≤ n .
4
Proof: Define a random variable Xi by
1 if the ith sample is less than or equal to the median,
Xi =
0 otherwise.
The Xi are independent, since the sampling is done with replacement. Because there are
(n − 1)/2 + 1 elements in S that are less than or equal to the median, the probability
that a randomly chosen element of S is less than or equal to the median can be written as
(n − 1)/2 + 1 1 1
Pr(Xi = 1) = = + .
n 2 2n
The event E1 is equivalent to
3/4
n
1 3/4 √
Y1 = Xi < n − n.
i=1
2
Since Y1 is the sum of Bernoulli trials, it is a binomial random variable with para-
meters n3/4 and 1/2 + 1/2n. Hence, using the result of Section 3.2.1 yields
3/4 1 1 1 1
Var[Y1 ] = n + −
2 2n 2 2n
1 1
= n3/4 − 5/4
4 4n
1 3/4
< n .
4
60
3.5 application: a randomized algorithm for computing the median
and
1 −1/4
Pr(E3 ) ≤ Pr(E3,1 ) + Pr(E3,2 ) ≤ n .
2
Combining the bounds just derived, we conclude that the probability that the algorithm
outputs FAIL is bounded by
Pr(E1 ) + Pr(E2 ) + Pr(E3 ) ≤ n−1/4 .
This yields the following theorem.
Theorem 3.15: The probability that the randomized median algorithm fails is
bounded by n−1/4 .
By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an
iterative algorithm that never fails but has a random running time. The samples taken
in successive runs of the algorithm are independent, so the success of each run is inde-
pendent of other runs, and hence the number of runs until success is achieved is a
geometric random variable. As an exercise, you may wish to show that this variation
of the algorithm (that runs until it finds a solution) still has linear expected running
time.
Randomized algorithms that may fail or return an incorrect answer are called Monte
Carlo algorithms. The running time of a Monte Carlo algorithm often does not depend
on the random choices made. For example, we showed in Theorem 3.11 that the ran-
domized median algorithm always terminates in linear time, regardless of its random
choices.
A randomized algorithm that always returns the right answer is called a Las Vegas
algorithm. We have seen that the Monte Carlo randomized algorithm for the median can
be turned into a Las Vegas algorithm by running it repeatedly until it succeeds. Again,
turning it into a Las Vegas algorithm means the running time is variable, although the
expected running time is still linear.
3.6. Exercises
Exercise 3.1: Let X be a number chosen uniformly at random from [1, n]. Find Var[X].
Exercise 3.2: Let X be a number chosen uniformly at random from [−k, k]. Find
Var[X].
Exercise 3.3: Suppose that we roll a standard fair die 100 times. Let X be the sum
of the numbers that appear over the 100 rolls. Use Chebyshev’s inequality to bound
Pr(|X − 350| ≥ 50).
Exercise 3.4: Prove that, for any real number c and any discrete random variable X,
Var[cX] = c2 Var[X].
62
3.6 exercises
Exercise 3.5: Given any two random variables X and Y, by the linearity of expecta-
tions we have E[X − Y ] = E[X] − E[Y ]. Prove that, when X and Y are independent,
Var[X − Y ] = Var[X] + Var[Y ].
Exercise 3.6: For a coin that comes up heads independently with probability p on each
flip, what is the variance in the number of flips until the kth head appears?
Exercise 3.7: A simple model of the stock market suggests that, each day, a stock with
price q will increase by a factor r > 1 to qr with probability p and will fall to q/r with
probability 1 − p. Assuming we start with a stock with price 1, find a formula for the
expected value and the variance of the price of the stock after d days.
Exercise 3.8: Suppose that we have an algorithm that takes as input a string of n
bits. We are told that the expected running time is O(n2 ) if the input bits are chosen
independently and uniformly at random. What can Markov’s inequality tell us about
the worst-case running time of this algorithm on inputs of size n?
n
Exercise 3.9: (a) Let X be the sum of Bernoulli random variables, X = i=1 Xi . The
Xi do not need to be independent. Show that
n
E[X 2 ] = Pr(Xi = 1)E[X | Xi = 1]. (3.5)
i=1
Exercise 3.10: For a geometric random variable X, find E[X 3 ] and E[X 4 ]. (Hint: Use
Lemma 2.5.)
Exercise 3.11: Recall the Bubblesort algorithm of Exercise 2.22. Determine the vari-
ance of the number of inversions that need to be corrected by Bubblesort.
Exercise 3.12: Find an example of a random variable with finite expectation and
unbounded variance. Give a clear argument showing that your choice has these
properties.
Exercise 3.13: Find an example of a random variable with finite jth moments for
1 ≤ j ≤ k but an unbounded (k + 1)th moment. Give a clear argument showing that
your choice has these properties.
63
moments and deviations
Exercise 3.14: Prove that, for any finite collection of random variables X1 , X2 , . . . , Xn ,
n n n
Var Xi = Var[Xi ] + 2 Cov(Xi , X j ).
i=1 i=1 i=1 j>i
Exercise 3.16: This problem shows that Markov’s inequality is as tight as it could
possibly be. Given a positive integer k, describe a random variable X that assumes only
nonnegative values such that
1
Pr(X ≥ kE[X]) = .
k
Exercise 3.17: Can you give an example (similar to that for Markov’s inequality in
Exercise 3.16) that shows that Chebyshev’s inequality is tight? If not, explain why not.
Exercise 3.18: Show that, for a random variable X with standard deviation σ [X] and
any positive real number t:
1
(a) Pr(X − E[X] ≥ tσ [X]) ≤ ;
1 + t2
2
(b) Pr(|X − E[X]| ≥ tσ [X]) ≤ .
1 + t2
Exercise 3.19: Using Exercise 3.18, show that |μ − m| ≤ σ for a random variable
with finite standard deviation σ , expectation μ, and median m.
Exercise 3.21: (a) Chebyshev’s inequality uses the variance of a random variable to
bound its deviation from its expectation. We can also use higher moments. Suppose
that we have a random variable X and an even integer k for which E[(X − E[X])k ] is
finite. Show that
1
Pr |X − E[X]| > t k E[(X − E[X])k ] ≤ k .
t
(b) Why is it difficult to derive a similar inequality when k is odd?
Exercise 3.22: A fixed point of a permutation π [1, n] → [1, n] is a value for which
π (x) = x. Find the variance in the number of fixed points of a permutation chosen
uni-
formly at random from all permutations. (Hint: Let Xi be 1 if π (i) = i, so that ni=1 Xi
64
3.6 exercises
n
is the number of fixed points. You cannot use linearity to find Var i=1 Xi , but you
can calculate it directly.)
Exercise 3.23: Suppose that we flip a fair coin n times to obtain n random bits. Con-
sider all m = n2 pairs ofthese bits in some order. Let Yi be the exclusive-or of the ith
pair of bits, and let Y = mi=1 Yi be the number of Yi that equal 1.
(a) Show that each Yi is 0 with probability 1/2 and 1 with probability 1/2.
(b) Show that the Yi are not mutually independent.
(c) Show that the Yi satisfy the property that E[YiY j ] = E[Yi ]E[Y j ].
(d) Using Exercise 3.15, find Var[Y ].
(e) Using Chebyshev’s inequality, prove a bound on Pr(|Y − E[Y ]| ≥ n).
Exercise 3.24: Generalize the median-finding algorithm for the case where the input
S is a multi-set. Bound the error probability and the running time of the resulting
algorithm.
Exercise 3.25: Generalize the median-finding algorithm to find the kth largest item in
a set of n items for any given value of k. Prove that your resulting algorithm is correct,
and bound its running time.
Exercise 3.26: The weak law of large numbers states that, if X1 , X2 , X3 , . . . are inde-
pendent and identically distributed random variables with mean μ and standard devia-
tion σ , then for any constant ε > 0 we have
X1 + X2 + · · · + Xn
lim Pr
− μ > ε = 0.
n→∞ n
Use Chebyshev’s inequality to prove the weak law of large numbers.
65
chapter four
Chernoff and Hoeffding Bounds
This chapter introduces large deviation bounds commonly called Chernoff and
Hoeffding bounds. These bounds are extremely powerful, giving exponentially
decreasing bounds on the tail distribution. These bounds are derived by applying
Markov’s inequality to the moment generating function of a random variable. We start
this chapter by defining and discussing the properties of the moment generating func-
tion. We then derive Chernoff bounds for the binomial distribution and other related
distributions, using a set balancing problem as an example, and the Hoeffding bound
for sums of bounded random variables. To demonstrate the power of Chernoff bounds,
we apply them to the analysis of randomized packet routing schemes on the hypercube
and butterfly networks.
Before developing Chernoff bounds, we discuss the special role of the moment gener-
ating function E[etX ].
Definition 4.1: The moment generating function of a random variable X is
MX (t ) = E[etX ].
We are mainly interested in the existence and properties of this function in the neigh-
borhood of zero.
The function MX (t ) captures all of the moments of X.
Theorem 4.1: Let X be a random variable with moment generating function MX (t ).
Under the assumption that exchanging the expectation and differentiation operands is
legitimate, for all n > 1 we then have
E[X n ] = MX(n) (0),
66
4.1 moment generating functions
Proof: Assuming that we can exchange the expectation and differentiation operands,
then
MX(n) (t ) = E[X n etX ].
Computed at t = 0, this expression yields
MX(n) (0) = E[X n ].
The assumption that expectation and differentiation operands can be exchanged holds
whenever the moment generating function exists in a neighborhood of zero, which will
be the case for all distributions considered in this book.
As a specific example, consider a geometric random variable X with parameter p, as
in Definition 2.8. Then, for t < − ln(1 − p),
MX (t ) = E[etX ]
∞
= (1 − p)k−1 petk
k=1
∞
p
= (1 − p)k etk
1 − p k=1
p
= ((1 − (1 − p)et )−1 − 1).
1− p
It follows that
MX(1) (t ) = p(1 − (1 − p)et )−2 et and
MX(2) (t ) = 2p(1 − p)(1 − (1 − p)et )−3 e2t + p(1 − (1 − p)et )−2 et .
Evaluating these derivatives at t = 0 and using Theorem 4.1 gives E[X] = 1/p
and E[X 2 ] = (2 − p)/p2 , matching our previous calculations from Section 2.4 and
Section 3.3.1.
Another useful property is that the moment generating function of a random variable
(or, equivalently, all of the moments of the variable) uniquely defines its distribution.
However, the proof of the following theorem is beyond the scope of this book.
Theorem 4.2: Let X and Y be two random variables. If
MX (t ) = MY (t )
for all t ∈ (−δ, δ) for some δ > 0, then X and Y have the same distribution.
One application of Theorem 4.2 is in determining the distribution of a sum of indepen-
dent random variables.
Theorem 4.3: If X and Y are independent random variables, then
MX+Y (t ) = MX (t )MY (t ).
Proof:
MX+Y (t ) = E[et(X+Y ) ] = E[etX etY ] = E[etX ]E[etY ] = MX (t )MY (t ).
67
chernoff and hoeffding bounds
Here we have used that X and Y are independent – and hence etX and etY are indepen-
dent – to conclude that E[etX etY ] = E[etX ]E[etY ].
The Chernoff bound for a random variable X is obtained by applying Markov’s inequal-
ity to etX for some well-chosen value t. From Markov’s inequality, we can derive the
following useful inequality: for any t > 0,
E[etX ]
Pr(X ≥ a) = Pr(etX ≥ eta ) ≤ .
eta
In particular,
E[etX ]
Pr(X ≥ a) ≤ min .
t>0 eta
Similarly, for any t < 0,
E[etX ]
Pr(X ≤ a) = Pr(etX ≥ eta ) ≤ .
eta
Hence
E[etX ]
Pr(X ≤ a) ≤ min .
t<0 eta
Bounds for specific distributions are obtained by choosing appropriate values for t.
While the value of t that minimizes E[etX ]/eta gives the best possible bounds, often one
chooses a value of t that gives a convenient form. Bounds derived from this approach
are generally referred to collectively as Chernoff bounds. When we speak of a Chernoff
bound for a random variable, it could actually be one of many bounds derived in this
fashion.
trials. Our Chernoff bound will hold for the binomial distribution and also for the more
general setting of the sum of Poisson trials.
, . . . , Xn be a sequence of independent Poisson trials with Pr(Xi = 1) = pi .
Let X1
Let X = ni=1 Xi , and let
n
n n
μ = E[X] = E Xi = E[Xi ] = pi .
i=1 i=1 i=1
For a given δ > 0, we are interested in bounds on Pr(X ≥ (1 + δ)μ) and Pr(X ≤
(1 − δ)μ) – that is, the probability that X deviates from its expectation μ by δμ or more.
To develop a Chernoff bound we need to compute the moment generating function of
X. We start with the moment generating function of each Xi :
MXi (t ) = E[etXi ]
= pi et + (1 − pi )
= 1 + pi (et − 1)
≤ e pi (e −1) ,
t
where in the last inequality we have used the fact that, for any y, 1 + y ≤ ey . Applying
Theorem 4.3, we take the product of the n generating functions to obtain
n
MX (t ) = MXi (t )
i=1
n
e pi (e −1)
t
≤
i=1
!
n
= exp pi (e − 1)
t
i=1
(et −1)μ
=e .
Now that we have determined a bound on the moment generating function, we are
ready to develop concrete versions of the Chernoff bound for a sum of Poisson trials.
We start with bounds on the deviation above the mean.
Theorem4.4: Let X1 , . . . , Xn be independent Poisson trials such that Pr(Xi = 1) = pi .
Let X = ni=1 Xi and μ = E[X]. Then the following Chernoff bounds hold:
1. for any δ > 0,
μ
eδ
Pr(X ≥ (1 + δ)μ) ≤ ; (4.1)
(1 + δ)(1+δ)
2. for 0 < δ ≤ 1,
Pr(X ≥ (1 + δ)μ) ≤ e−μδ /3
2
; (4.2)
3. for R ≥ 6μ,
Pr(X ≥ R) ≤ 2−R . (4.3)
69
chernoff and hoeffding bounds
The first bound of the theorem is the strongest, and it is from this bound that we derive
the other two bounds, which have the advantage of being easier to state and compute
with in many situations.
Proof: Applying Markov’s inequality, for any t > 0 we have
Pr(X ≥ (1 + δ)μ) = Pr(etX ≥ et(1+δ)μ )
E[etX ]
≤ t(1+δ)μ
e
e(e −1)μ
t
≤ t(1+δ)μ .
e
For any δ > 0, we can set t = ln(1 + δ) > 0 to get Eqn. (4.1):
μ
eδ
Pr(X ≥ (1 + δ)μ) ≤ .
(1 + δ)(1+δ)
To obtain Eqn. (4.2) we need to show that, for 0 < δ ≤ 1,
eδ
≤ e−δ /3 .
2
(1 + δ)(1+δ)
Taking the logarithm of both sides, we obtain the equivalent condition
δ2
f (δ) = δ − (1 + δ) ln(1 + δ) + ≤ 0.
3
Computing the derivatives of f (δ), we have:
1+δ 2
f (δ) = 1 − − ln(1 + δ) + δ
1+δ 3
2
= − ln(1 + δ) + δ;
3
1 2
f (δ) = − + .
1+δ 3
We see that f (δ) < 0 for 0 ≤ δ < 1/2 and that f (δ) > 0 for δ > 1/2. Hence f (δ)
first decreases and then increases over the interval [0, 1]. Since f (0) = 0 and f (1) <
0, we can conclude that f (δ) ≤ 0 in the interval [0, 1]. Since f (0) = 0, it follows that
f (δ) ≤ 0 in that interval, proving Eqn. (4.2).
To prove Eqn. (4.3), let R = (1 + δ)μ. Then, for R ≥ 6μ, δ = R/μ − 1 ≥ 5. Hence,
using Eqn. (4.1),
μ
eδ
Pr(X ≥ (1 + δ)μ) ≤
(1 + δ)(1+δ)
(1+δ)μ
e
≤
1+δ
e R
≤
6
−R
≤2 .
70
4.2 deriving and applying chernoff bounds
≤ t(1−δ)μ .
e
For 0 < δ < 1, we set t = ln(1 − δ) < 0 to get Eqn. (4.4):
μ
e−δ
Pr(X ≤ (1 − δ)μ) ≤ .
(1 − δ)(1−δ)
To prove Eqn. (4.5) we must show that, for 0 < δ < 1,
e−δ
≤ e−δ /2 .
2
(1 − δ)(1−δ)
Taking the logarithm of both sides, we obtain the equivalent condition
δ2
f (δ) = −δ − (1 − δ) ln(1 − δ) + ≤0
2
for 0 < δ < 1.
Differentiating f (δ) yields
f (δ) = ln(1 − δ) + δ,
1
f (δ) = − + 1.
1−δ
Since f (δ) < 0 in the range (0, 1) and since f (0) = 0, we have f (δ) ≤ 0 in the range
[0, 1). Therefore, f (δ) is nonincreasing in that interval. Since f (0) = 0, it follows that
f (δ) ≤ 0 when 0 < δ < 1, as required.
Often the following form of the Chernoff bound, which is derived immediately from
Eqn. (4.2) and Eqn. (4.4), is used.
In practice we often do not have the exact value of E[X]. Instead we can use μ ≥ E[X]
in Theorem 4.4 and μ ≤ E[X] in Theorem 4.5 (see Exercise 4.7).
Notice that, instead of predicting a single value for the parameter, we give an interval
that is likely to contain the parameter. If p can take on any real value, it may not make
sense to try to pin down its exact value from a finite sample, but it does make sense to
estimate it within some small range.
Naturally we want both the interval size 2δ and the error probability γ to be as
small as possible. We derive a trade-off between these two parameters and the number
of samples n. In particular, given that among n samples (chosen uniformly at random
from the entire population) we find the mutation in exactly X = p̃n samples, we need
to find values of δ and γ for which
We can apply the Chernoff bounds in Eqns. (4.2) and (4.5) to compute
δ δ
Pr(p ∈
/ [ p̃ − δ, p̃ + δ]) = Pr X < np 1 − + Pr X > np 1 + (4.7)
p p
< e−np(δ/p) /2 + e−np(δ/p) /3
2 2
(4.8)
−nδ 2 /2p −nδ 2 /3p
=e +e . (4.9)
The bound given in Eqn. (4.9) is not useful because the value of p is unknown. A
simple solution is to use the fact that p ≤ 1, yielding
Setting γ = e−nδ /2 + e−nδ /3 , we obtain a trade-off between δ, n, and the error proba-
2 2
bility γ .
We can apply other Chernoff bounds, such as those in Exercises 4.13 and 4.16, to
obtain better bounds. We return to the subject of parameter estimation when we discuss
the Monte Carlo method in Chapter 11.
We can obtain stronger bounds using a simpler proof technique for some special cases
of symmetric random variables.
We consider first the sum of independent random variables when each variable
assumes the value 1 or −1 with equal probability.
n
Let X = i=1 Xi . For any a > 0,
i=1
and
E[etX ] 2
Pr(X ≥ a) = Pr(etX ≥ eta ) ≤ ta
≤ et n/2−ta .
e
Setting t = a/n, we obtain
Pr(X ≥ a) ≤ e−a /2n .
2
n
Let X = i=1 Xi . Then, for any a > 0,
Pr(Y ≥ μ + a) ≤ e−2a /n .
2
proving the first part of the corollary. The second part follows from setting a = δμ =
δn/2. Again applying Theorem 4.7, we have
Note that the constant in the exponent of the bound of Eqn. (4.10) is 1 instead of the
1/3 in the bound of Eqn. (4.2).
Similarly, we have the following result.
Pr(Y ≤ μ − a) ≤ e−2a /n .
2
75
chernoff and hoeffding bounds
Suppose that we are looking for a vector b̄ with entries in {−1, 1} that minimizes
This problem arises in designing statistical experiments. Each column of the matrix A
represents a subject in the experiment and each row represents a feature. The vector
b̄ partitions the subjects into two disjoint groups, so that each feature is roughly as
balanced as possible between the two groups. One of the groups serves as a control
group for an experiment that is run on the other group.
Our randomized algorithm for computing a vector b̄ is extremely simple. We ran-
domly choose the entries of b̄, with Pr(bi = 1) = Pr(bi = −1) = 1/2. The choices
for different entries are independent. Surprisingly, although this algorithm ignores the
entries
√ of the matrix A, the following theorem shows that Ab̄∞ is likely to be only
O m ln n . This bound is fairly tight. In Exercise 4.15 you √are asked to show that,
when m = n, there exists a matrix A for which Ab̄∞ is n for any choice of b̄.
Theorem 4.11: For a random vector b̄ with entries chosen independently and with
equal probability from the set {−1, 1},
√ 2
Pr Ab̄∞ ≥ 4m ln n ≤ .
n
Proof: Consider
√ the ith row āi = ai,1 , . . . , ai,m , and
√ let k be the number of 1s in that
row.
√ If k ≤ 4m ln n, then clearly |āi · b̄| = |ci | ≤ 4m ln n. On the other hand, if k >
4m ln n then we note that the k nonzero terms in the sum
m
Zi = ai, j b j
j=1
are independent random variables, each with probability 1/2 of being either +1 or −1.
Now using the Chernoff bound of Corollary 4.8 and the fact that m ≥ k,
√ 2
Pr |Zi | > 4m ln n ≤ 2e−4m ln n/2k ≤ 2 .
n
By the union bound, the probability that the bound fails for any row is at most
2/n.
76
4.5 the hoeffding bound
Hoeffding’s bound extends the Chernoff bound technique to general random variables
with a bounded range.
Theorem 4.12 [Hoeffding Bound]: Let X1 , . . . , Xn be independent random variables
such that for all 1 ≤ i ≤ n, E[Xi ] = μ and Pr(a ≤ Xi ≤ b) = 1. Then
n
1
Xi − μ ≥ ≤ 2e−2n /(b−a) .
2 2
Pr
n
i=1
Proof: The proof relies on the following bound for the moment generating function,
which we prove first.
Lemma 4.13 [Hoeffding’s Lemma]: Let X be a random variable such that
Pr(X ∈ [a, b]) = 1 and E[X] = 0. Then for every λ > 0,
E[eλX ] ≤ eλ (b−a)2 /8
2
.
Proof: Before beginning, note that since E[X] = 0, if a = 0 then b = 0 and the state-
ment is trivial. Hence we may assume a < 0 and b > 0.
Since f (x) = eλx is a convex function, for any α ∈ (0, 1),
f (αa + (1 − α)b) ≤ αeλa + (1 − α)eλb .
For x ∈ [a, b], let α = b−x
b−a
; then x = αa + (1 − α)b and we have
b − x λa x − a λb
eλx ≤ e + e .
b−a b−a
We consider eλX and take expectations. Using the fact that E[X] = 0, we have
b − X λa X − a λb
E[eλX ] ≤ E e +E e
b−a b−a
b λa E[X] λa a λb E[X] λb
= e − e − e + e
b−a b−a b−a b−a
b λa a λb
= e − e .
b−a b−a
We now require some manipulation of this final expression. Let φ(t ) = −θt +
−a
ln(1 − θ + θet ), for θ = b−a > 0. Then
λ2 (b − a)2
φ(λ(b − a)) ≤ .
8
It follows that
where for the key second to last inequality we have used Hoeffding’s Lemma with the
fact that Zi /n is bounded between (a − μ)/n and (b − μ)/n. Setting λ = (b−a)
4n
2 gives
1
n
= Pr(Z ≥ ) ≤ e−2n /(b−a)2
2
Pr Xi − μ ≥ .
n i=1
1
n
= Pr(Z ≤ −) ≤ e−2n /(b−a)2
2
Pr Xi − μ ≤ − .
n i=1
The proof of the following more general version of the bound is left as an exercise
(Exercise 4.20).
Note that Theorem 4.12 bounds the deviation of the average of the n random vari-
ables while Theorem 4.14 bounds the deviation of the sum of the variables.
78
∗
4.6 application: packet routing in sparse networks
Examples:
1. Consider n independent random variables X1 , . . . , Xn such that Xi is uniformly dis-
tributed in {0, . . . , }. For all i, μ = E[Xi ] = /2, and
n
1
Xi − ≥ ≤ 2e−2n / .
2 2
Pr
n 2
i=1
In particular,
n
1
Xi − μ ≥ δμ ≤ 2e−nδ /2 .
2
Pr
n
i=1
≥
4
= 2e−12 /(n(n+1)(2n+1))
2
.
We can conclude
Pr(|Y − μ| ≥ δμ) ≤ 2e−12δ n (n+1)2 /(16n(n+1)(2n+1))
≤ 2e−3nδ /8
2 2 2
.
Each node can be connected directly to only a few neighbors, and most packets must
traverse intermediate nodes en route to their final destination. Since an edge may be
on the path of more than one packet and since each edge can process only one packet
per step, parallel packet routing on sparse networks may lead to congestion and bottle-
necks. The practical problem of designing an efficient communication scheme for par-
allel computers leads to an interesting combinatorial and algorithmic problem: design-
ing a family of sparse networks connecting any number of processors, together with
a routing algorithm that routes an arbitrary permutation request in a small number of
parallel steps.
We discuss here a simple and elegant randomized routing technique and then use
Chernoff bounds to analyze its performance on the hypercube network and the butterfly
network. We first analyze the case of routing a permutation on a hypercube, a network
with N processors and O(N log N) edges. We then present a tighter argument for the
butterfly network, which has N nodes and only O(N) edges.
See Figure 4.1. Note that the total number of directed edges in the n-cube is nN, since
each node is adjacent to n outgoing and n ingoing edges. Also, the diameter of the
network is n; that is, there is a directed path of length up to n connecting any two
nodes in the network, and there are pairs of nodes that are not connected by any shorter
path.
The topology of the hypercube allows for a simple bit-fixing routing mechanism, as
shown in Algorithm 4.1. When determining which edge to cross next, the algorithm
simply considers each bit in order and crosses the edge if necessary.
Although it seems quite natural, using only the bit-fixing routes can lead to high
levels of congestion and poor performance, as shown in Exercise 4.22. There are certain
permutations on which the bit-fixing routes behave poorly. It turns out, as we will show,
that these routes perform well if each packet is being sent from a source to a destination
chosen uniformly at random. This motivates the following approach: first route each
packet to a randomly chosen intermediate point, and then route it from this intermediate
point to its final destination.
It may seem unusual to first route packets to a random intermediate point. In some
sense, this is similar in spirit to our analysis of Quicksort in Section 2.5. We found there
that for a list already sorted in reverse order, Quicksort would take (n2 ) comparisons,
whereas the expected number of comparisons for a randomly chosen permutation is
only O(n log n). Randomizing the data can lead to a better running time for Quicksort.
80
∗
4.6 application: packet routing in sparse networks
000 010
0 00 10 100 110
001 011
1 01 11 101 111
(d) n = 4.
Here, too, randomizing the routes that packets take – by routing them through a ran-
dom intermediate point – avoids bad initial permutations and leads to good expected
performance.
The two-phase routing algorithm (Algorithm 4.2) is executed in parallel by all the
packets. The random choices are made independently for each packet. Our analysis
holds for any queueing policy that obeys the following natural requirement: if a queue
is not empty at the beginning of a time step, some packet is sent along the edge associ-
ated with that queue during that time step. We prove that this routing strategy achieves
asymptotically optimal parallel time.
81
chernoff and hoeffding bounds
Proof: We first analyze the run-time of Phase I. To simplify the analysis we assume that
no packet starts the execution of Phase II before all packets have finished the execution
of Phase I. We show later that this assumption can be removed.
We emphasize a fact that we use implicitly throughout. If a packet is routed to a
randomly chosen node x̄ in the network, we can think of x̄ = (x1 , . . . , xn ) as being
generated by setting each xi independently to be 0 with probability 1/2 and 1 with
probability 1/2.
For a given packet M, let T1 (M) be the number of steps for M to finish Phase I. For
a given edge e, let X1 (e) denote the total number of packets that traverse edge e during
Phase I.
In each step of executing Phase I, packet M is either traversing an edge or waiting in a
queue while some other packet traverses an edge on M’s route. This simple observation
relates the routing time of M to the total number of packet transitions through edges on
the path of M, as follows.
Let us call any path P = (e1 , e2 , . . . , em ) of m ≤ n edges that follows the bit-fixing
algorithm a possible packet path. We denote the corresponding nodes by v0 , v1 , . . . , vm
with ei = (vi−1 , vi ). Following the definition of T1 (M), for any possible packet path P
we let
m
T1 (P) = X1 (ei ).
i=1
By Lemma 4.16, the probability that Phase I takes more than T steps is bounded by
the probability that, for some possible packet path P, T1 (P) ≥ T . Note that there are
at most 2n · 2n = 22n possible packet paths, since there are 2n possible origins and 2n
possible destinations.
82
∗
4.6 application: packet routing in sparse networks
1 This approach overestimates the time to finish a phase. In fact, there is a deterministic argument showing that,
in this setting, the delay of a packet on a path is bounded by the number of different packets that traverse edges
of the path, and hence there is no need to bound the total number of traversals of these packets on the path.
However, in the spirit of this book we prefer to present the probabilistic argument.
83
chernoff and hoeffding bounds
Pr(T1 (P) ≥ 30n) ≤ Pr(H ≥ 6n) + Pr(T1 (P) ≥ 30n | H < 6n)
≤ 2−6n + Pr(T1 (P) ≥ 30n | H < 6n).
Hence if we show
we then have
P more than 30n times, as can be shown easily by induction (on the number of biased
coins).
Letting Z be the number of heads in 36n fair coin flips, we now apply the Chernoff
bound of Eqn. (4.5) to prove:
Pr(T1 (P) ≥ 30n | H ≤ 6n) ≤ Pr(Z ≤ 6n) ≤ e−18n(2/3) /2 = e−4n ≤ 2−3n−1 .
2
It follows that
Pr(T1 (P) ≥ 30n) ≤ Pr(H ≥ 6n) + Pr(T1 (P) ≥ 30n | H ≤ 6n) ≤ 2−3n ,
as we wanted to show. Because there are at most 22n possible packet paths in the hyper-
cube, the probability that there is any possible packet path for which T1 (P) ≥ 30n is
bounded by
22n 2−3n = 2−n = O(N −1 ).
This completes the analysis of Phase I. Consider now the execution of Phase II,
assuming that all packets completed their Phase I route. In this case, Phase II can be
viewed as running Phase I backwards: instead of packets starting at a given origin
and going to a random destination, they start at a random origin and end at a given
destination. Hence no packet spends more than 30n steps in Phase II with probability
1 − O(N −1 ).
In fact, we can remove the assumption that packets begin Phase II only after Phase
I has completed. The foregoing argument allows us to conclude that the total number
of packet traversals across the edges of any packet path during Phase I and Phase II
together is bounded by 60n with probability 1 − O(N −1 ). Since a packet can be delayed
only by another packet traversing that edge, we find that every packet completes both
Phase I and Phase II after 60n steps with probability 1 − O(N −1 ) regardless of how the
phases interact, concluding the proof of Theorem 4.15
Note that the run-time of the routing algorithm is optimal up to a constant factor, since
the diameter of the hypercube is n. However, the network is not fully utilized because
2nN directed edges are used to route just N packets. At any give time, at most 1/2n of
the edges are actually being used. This issue is addressed in the next section.
l0
l1
l2
l3
ve
ve
ve
ve
le
le
le
le
row 000
row 001
row 010
row 011
row 100
row 101
row 110
row 111
Figure 4.2: The butterfly network. In the wrapped butterfly, levels 0 and 3 are collapsed into one
level.
is the row number and 0 ≤ r ≤ n − 1 is the column number of the node. Node (x, r) is
connected to node (y, s) if and only if s = r + 1 mod n and either:
See Figure 4.2. To see the relation between the wrapped butterfly and the hypercube,
observe that by collapsing the n nodes in each row of the wrapped butterfly into one
“super node” we obtain an n-cube network. Using this correspondence, one can easily
verify that there is a unique directed path of length n connecting node (x, r) to any
other node (w, r) in the same column. This path is obtained by bit fixing: first fixing
bits r + 1 to n, then bits 1 to r. See Algorithm 4.3. Our randomized permutation routing
algorithm on the butterfly consists of three phases, as shown in Algorithm 4.4.
Unlike our analysis of the hypercube, our analysis here cannot simply bound the
number of active packets that possibly traverse edges of a path. Given the path of a
packet, the expected number of other packets that share edges with this path when
86
∗
4.6 application: packet routing in sparse networks
routing a random permutation on the butterfly network is (n2 ) and not O(n) as in the
n-cube. To obtain an O(n) routing time, we need a more refined analysis technique that
takes into account the order in which packets traverse edges.
Because of this, we need to consider the priority policy that the queues use when
there are several packets waiting to use the edge. A variety of priority policies would
work here; we assume the following rules.
Theorem 4.17: Given an arbitrary permutation routing problem on the wrapped but-
terfly with N = n2n nodes, with probability 1 − O(N −1 ) the three-phase routing scheme
of Algorithm 4.4 routes all packets to their destinations in O(n) = O(log N) parallel
steps.
Proof: The priority rule in the edge queues guarantees that packets in a phase cannot
delay packets in earlier phases. Because of this, in our forthcoming analysis we can
consider the time for each phase to complete separately and then add these times to
bound the total time for the three-phase routing scheme to complete.
We begin by considering the second phase. We first argue that with high probability
each row transmits at most 4n packets in the second phase. To see this, let Xw be the
87
chernoff and hoeffding bounds
number of packets whose intermediate row choice is w in the three-phase routing algo-
rithm. Then Xw is the sum of 0–1 independent random variables, one for each packet,
and E[Xw ] = n. Hence, we can directly apply the Chernoff bound of Eqn. (4.1) to find
3
n
e
Pr(Xw ≥ 4n) ≤ ≤ 3−2n .
44
There are 2n possible rows w. By the union bound, the probability that any row has
more than 4n packets is only 2n · 3−2n = O(N −1 ).
We now argue that, if each row has at most 4n packets for the second phase, then the
second phase takes at most 5n steps to complete. Combined with our previous observa-
tions, this means the second phase takes at most 5n steps with probability 1 − O(N −1 ).
To see this, note that in the second phase the routing has a special structure: each packet
moves from edge to edge along its row. Because of the priority rule, each packet can
be delayed only by packets already in a queue when it arrives. Therefore, to place an
upper bound on the number of packets that delay a packet p, we can bound the total
number of packets found in each queue when p arrives at the queue. But in Phase II, the
number of other packets that an arriving packet finds in a queue cannot increase in size
over time, since at each step a queue sends a packet and receives at most one packet.
(It is worth considering the special case when a queue becomes empty at some point
in Phase II; this queue can receive another packet at some later step, but the number of
packets an arriving packet will find in the queue after that point is always zero.) Since
there are at most 4n packets total in the row to begin with, p finds at most 4n packets
that delay it as it moves from queue to queue. Since each packet moves at most n times
in the second phase, the total time for the phase is 5n steps.
We now consider the other phases. The first and third phases are again the same by
symmetry, so we consider just the first phase. Our analysis will use a delay sequence
argument.
that time it has already finished transmitting all packets with priority numbers up to i.
Thus,
Ti+1 ≤ Ti + ti+1 .
Since T1 = t1 , we have
Tn ≤ Tn−1 + tn
≤ Tn−2 + tn−1 + tn
n
≤ ti ,
i=1
We conclude that
Pr(T ≥ 40n) ≤ Pr(T ≥ 40n | H ≤ 5n) + Pr(H ≥ 5n) ≤ 2−5n+1 .
There are no more than 2N3n−1 ≤ n2n 3n possible delay sequences, since a sequence
can start in any one of the 2N edges of the network, and by Definition 4.5, if ei is the
ith edge in the sequence, there are only three possible assignments for ei+1 . Thus, the
probability that, in the execution of Phase I, there is a delay sequence with T ≥ 40n is
bounded above (using the union bound) by
n2n 3n 2−5n+1 ≤ O(N −1 ).
Since Phase III is entirely similar to Phase I and since Phase II also finishes in O(n)
steps with probability 1 − O(N −1 ), we have that the three-phase routing algorithm fin-
ishes in O(n) steps with probability 1 − O(N −1 ).
4.7. Exercises
Exercise 4.1: Alice and Bob play checkers often. Alice is a better player, so the proba-
bility that she wins any given game is 0.6, independent of all other games. They decide
to play a tournament of n games. Bound the probability that Alice loses the tournament
using a Chernoff bound.
Exercise 4.2: We have a standard six-sided die. Let X be the number of times that a 6
occurs over n throws of the die. Let p be the probability of the event X ≥ n/4. Compare
the best upper bounds on p that you can obtain using Markov’s inequality, Chebyshev’s
inequality, and Chernoff bounds.
Exercise 4.3: (a) Determine the moment generating function for the binomial random
variable B(n, p).
90
4.7 exercises
(b) Let X be a B(n, p) random variable and Y a B(m, p) random variable, where X
and Y are independent. Use part (a) to determine the moment generating function of
X + Y.
(c) What can we conclude from the form of the moment generating function of
X + Y?
Exercise 4.4: Determine the probability of obtaining 55 or more heads when flipping
a fair coin 100 times by an explicit calculation, and compare this with the Chernoff
bound. Do the same for 550 or more heads in 1000 flips.
Exercise 4.5: We plan to conduct an opinion poll to find out the percentage of people
in a community who want its president impeached. Assume that every person answers
either yes or no. If the actual fraction of people who want the president impeached is
p, we want to find an estimate X of p such that
Pr(|X − p| ≤ ε p) > 1 − δ
for a given ε and δ, with 0 < ε, δ < 1.
We query N people chosen independently and uniformly at random from the com-
munity and output the fraction of them who want the president impeached. How large
should N be for our result to be a suitable estimator of p? Use Chernoff bounds, and
express N in terms of p, ε, and δ. Calculate the value of N from your bound if ε = 0.1
and δ = 0.05 and if you know that p is between 0.2 and 0.8.
Exercise 4.6: (a) In an election with two candidates using paper ballots, each vote is
independently misrecorded with probability p = 0.02. Use a Chernoff bound to give
an upper bound on the probability that more than 4% of the votes are misrecorded in
an election of 1,000,000 ballots.
(b) Assume that a misrecorded ballot always counts as a vote for the other candidate.
Suppose that candidate A received 510,000 votes and that candidate B received 490,000
votes. Use Chernoff bounds to upper bound the probability that candidate B wins the
election owing to misrecorded ballots. Specifically, let X be the number of votes for
candidate A that are misrecorded and let Y be the number of votes for candidate B that
are misrecorded. Bound Pr((X > k) ∪ (Y < )) for suitable choices of k and .
Exercise 4.7: Throughout the chapter we implicitly assumed the following extension
of the Chernoff
n bound. Prove that it is true.
Let X = i=1 Xi , where the Xi are independent 0–1 random variables. Let μ =
E[X]. Choose any μL and μH such that μL ≤ μ ≤ μH . Then, for any δ > 0,
μH
eδ
Pr(X ≥ (1 + δ)μH ) ≤ .
(1 + δ)(1+δ)
Similarly, for any 0 < δ < 1,
μL
e−δ
Pr(X ≤ (1 − δ)μL ) ≤ .
(1 − δ)(1−δ)
91
chernoff and hoeffding bounds
Exercise 4.8: We show how to construct a random permutation π on [1, n], given a
black box that outputs numbers independently and uniformly at random from [1, k]
where k ≥ n. If we compute a function f [1, n] → [1, k] with f (i) = f ( j) for i = j,
this yields a permutation; simply output the numbers [1, n] according to the order of
the f (i) values. To construct such a function f, do the following for j = 1, . . . , n: choose
f ( j) by repeatedly obtaining numbers from the black box and setting f ( j) to the first
number found such that f ( j) = f (i) for i < j.
Prove that this approach gives a permutation chosen uniformly at random from all
permutations. Find the expected number of calls to the black box that are needed when
k = n and k = 2n. For the case k = 2n, argue that the probability that each call to the
black box assigns a value of f ( j) to some j is at least 1/2. Based on this, use a Chernoff
bound to bound the probability that the number of calls to the black box is at least 4n.
(a) Show using Chebyshev’s inequality that O(r2 /ε2 δ) samples are sufficient to solve
the problem.
(b) Suppose that we need only a weak estimate that is within εE[X] of E[X] with
probability at least 3/4. Argue that O(r2 /ε2 ) samples are enough for this weak
estimate.
(c) Show that, by taking the median of O(log(1/δ)) weak estimates, we can obtain an
estimate within εE[X] of E[X] with probability at least 1 − δ. Conclude that we
need only O((r2 log(1/δ))/ε2 ) samples.
Exercise 4.10: A casino is testing a new class of simple slot machines. Each game, the
player puts in $1, and the slot machine is supposed to return either $3 to the player with
probability 4/25, $100 with probability 1/200, or nothing with all remaining probabil-
ity. Each game is supposed to be independent of other games.
The casino has been surprised to find in testing that the machines have lost $10,000
over the first million games. Derive a Chernoff bound for the probability of this event.
You may want to use a calculator or program to help you choose appropriate values as
you derive your bound.
Exercise 4.14: Modify the proof of Theorem 4.4 to show the following bound for
a weighted sum of Poisson trials. Let X1 , . . . , Xn be independent Poisson trials such
that Pr(Xi ) = pi and let a1 , . . . , an be real numbers in [0, 1]. Let X = ni=1 ai Xi and
μ = E[X]. Then the following Chernoff bound holds: for any δ > 0,
μ
eδ
Pr(X ≥ (1 + δ)μ) ≤ .
(1 + δ)(1+δ)
Prove a similar bound for the probability that X ≤ (1 − δ)μ for any 0 < δ < 1.
Pr(|X| ≥ a) ≤ 2e−2a /n .
2
93
chernoff and hoeffding bounds
Exercise 4.17: Suppose that we have n jobs to distribute among m processors. For
simplicity, we assume that m divides n. A job takes 1 step with probability p and k > 1
steps with probability 1 − p. Use Chernoff bounds to determine upper and lower
bounds (that hold with high probability) on when all jobs will be completed if we
randomly assign exactly n/m jobs to each processor.
Exercise 4.19: Recall that a function f is said to be convex if, for any x1 , x2 and for
0 ≤ λ ≤ 1,
f (λx1 + (1 − λ)x2 ) ≤ λ f (x1 ) + (1 − λ) f (x2 ).
(a) Let Z be a random variable that takes on a (finite) set of values in the interval [0, 1],
and let p = E[Z]. Define the Bernoulli random variable X by Pr(X = 1) = p and
Pr(X = 0) = 1 − p. Show that E[ f (Z)] ≤ E[ f (X )] for any convex function f.
(b) Use the fact that f (x) = etx is convex for any t ≥ 0 to obtain a Chernoff bound for
the sum of n independent random variables with distribution Z as in part (a), based
on a Chernoff bound for independent Poisson trials.
Exercise 4.21: We prove that the Randomized Quicksort algorithm sorts a set of
n numbers in time O(n log n) with high probability. Consider the following view of
Randomized Quicksort. Every point in the algorithm where it decides on a pivot ele-
ment is called a node. Suppose the size of the set to be sorted at a particular node is s.
The node is called good if the pivot element divides the set into two parts, each of size
not exceeding 2s/3. Otherwise the node is called bad. The nodes can be thought of as
94
4.7 exercises
forming a tree in which the root node has the whole set to be sorted and its children
have the two sets formed after the first pivot step and so on.
(a) Show that the number of good nodes in any path from the root to a leaf in this tree
is not greater than c log2 n, where c is some positive constant.
(b) Show that, with high probability (greater than 1 − 1/n2 ), the number of nodes in
a given root to leaf path of the tree is not greater than c log2 n, where c is another
constant.
(c) Show that, with high probability (greater than 1 − 1/n), the number of nodes in
the longest root to leaf path is not greater than c log2 n. (Hint: How many nodes
are there in the tree?)
(d) Use your answers to show that the running time of Quicksort is O(n log n) with
probability at least 1 − 1/n.
Exercise 4.22: Consider the bit-fixing routing algorithm for routing a permutation on
the n-cube. Suppose that n is even. Write each source node s as the concatenation of
two binary strings as and bs each of length n/2. Let the destination of s’s packet be
bs and
the concatenation of√ as . Show that this permutation causes the bit-fixing routing
algorithm to take N steps.
Exercise 4.23: Consider the following modification to the bit-fixing routing algorithm
for routing a permutation on the n-cube. Suppose that, instead of fixing the bits in order
from 1 to n, each packet chooses a random order (independent of other packets’ choices)
and fixes the bits in that order. Show that there is a permutation for which this algorithm
requires 2(n) steps with high probability.
Exercise 4.24: Assume that we use the randomized routing algorithm for the n-cube
network (Algorithm 4.2) to route a total of up to p2n packets, where each node is the
source of no more than p packets and each node is the destination of no more than p
packets.
Exercise 4.25: Show that the expected number of packets that traverse any edge on
the path of a given packet when routing a random permutation on the wrapped butterfly
network of N = n2n nodes is (n2 ).
Exercise 4.26: In this exercise, we design a randomized algorithm for the following
packet routing problem. We are given a network that is an undirected connected graph
G, where nodes represent processors and the edges between the nodes represent wires.
We are also given a set of N packets to route. For each packet we are given a source
node, a destination node, and the exact route (path in the graph) that the packet should
take from the source to its destination. (We may assume that there are no loops in the
95
chernoff and hoeffding bounds
path.) In each time step, at most one packet can traverse an edge. A packet can wait at
any node during any time step, and we assume unbounded queue sizes at each node.
A schedule for a set of packets specifies the timing for the movement of packets
along their respective routes. That is, it specifies which packet should move and which
should wait at each time step. Our goal is to produce a schedule for the packets that
tries to minimize the total time and the maximum queue size needed to route all the
packets to their destinations.
(a) The dilation d is the maximum distance traveled by any packet. The congestion c is
the maximum number of packets that must traverse a single edge during the entire
course of the routing. Argue that the time required for any schedule should be at
least (c + d).
(b) Consider the following unconstrained schedule, where many packets may traverse
an edge during a single time step. Assign each packet an integral delay chosen ran-
domly, independently, and uniformly from the interval [1, αc/ log(Nd)], where α
is a constant. A packet that is assigned a delay of x waits in its source node for x time
steps; then it moves on to its final destination through its specified route without
ever stopping. Give an upper bound on the probability that more than O(log(Nd))
packets use a particular edge e at a particular time step t.
(c) Again using the unconstrained schedule of part (b), show that the probability that
more than O(log(Nd)) packets pass through any edge at any time step is at most
1/(Nd) for a sufficiently large α.
(d) Use the unconstrained schedule to devise a simple randomized algorithm that, with
high probability, produces a schedule of length O(c + d log(Nd)) using queues of
size O(log(Nd)) and following the constraint that at most one packet crosses an
edge per time step.
96
chapter five
Balls, Bins, and Random Graphs
In this chapter, we focus on one of the most basic of random processes: m balls are
thrown randomly into n bins, each ball landing in a bin chosen independently and uni-
formly at random. We use the techniques we have developed previously to analyze this
process and develop a new approach based on what is known as the Poisson approx-
imation. We demonstrate several applications of this model, including a more sophis-
ticated analysis of the coupon collector’s problem and an analysis of the Bloom filter
data structure. After introducing a closely related model of random graphs, we show an
efficient algorithm for finding a Hamiltonian cycle on a random graph with sufficiently
many edges. Even though finding a Hamiltonian cycle is NP-hard in general, our result
shows that, for a randomly chosen graph, the problem is solvable in polynomial time
with high probability.
Sitting in lecture, you notice that there are 30 people in the room. Is it more likely that
some two people in the room share the same birthday or that no two people in the room
share the same birthday?
We can model this problem by assuming that the birthday of each person is a ran-
dom day from a 365-day year, chosen independently and uniformly at random for each
person. This is obviously a simplification; for example, we assume that a person’s birth-
day is equally likely to be any day of the year, we avoid the issue of leap years, and we
ignore the possibility of twins! As a model, however, it has the virtue of being easy to
understand and analyze.
One way to calculate this probability is to directly count the configurations where
two people do not share a birthday. It is easier to think about the configurations where
people do not share a birthday than about configurations where some two people do.
Thirty days must be chosen from the 365; there are 365 30
ways to do this. These 30
days
can be assigned to the people in any of the 30! possible orders. Hence there are
365
30
30! configurations where no two people share the same birthday, out of the 36530
97
balls, bins, and random graphs
m−1
j
m−1
1− ≈ e− j/n
j=1
n j=1
⎧ ⎫
⎨ m−1 ⎬
j
= exp −
⎩ n⎭ j=1
= e−m(m−1)/2n
≈ e−m /2n .
2
Hence the value for m at which the probability that m people all have different birthdays
is 1/2 is approximately given by the equation
m2
= ln 2,
2n
√
or m = 2n ln 2. For the case n = 365, this approximation gives m = 22.49 to two
decimal places, matching the exact calculation quite well.
98
5.2 balls into bins
Quite tight and formal bounds can be established using bounds in place of the
approximations just derived, an option that is considered in Exercise 5.3. The follow-
ing simple arguments, however, give loose bounds and good intuition. Let us consider
each person one at a time, and let Ek be the event that the kth person’s birthday does
not match any of the birthdays of the first k − 1 people. Then the probability that the
first k people fail to have distinct birthdays is
k
Pr(Ē1 ∪ Ē2 ∪ · · · ∪ Ēk ) ≤ Pr(Ēi )
i=1
k
i−1
≤
i=1
n
k(k − 1)
= .
2n
√ √
If k ≤ n this probability is less than 1/2, so with n people the probability is at
least 1/2 that all birthdays will
√bedistinct.
Now assume that the first n people all have distinct birthdays. Each person after
√ √
that has probability
√ at least n/n = 1/ n of having the √same
birthday as one of these
first n people. Hence the
√ probability that the next n people all have different
birthdays than the first n people is at most
√n
1 1 1
1− √ < < .
n e 2
√
Hence, once there are 2 n people, the probability is at most 1/e that all birthdays
will be distinct.
the number of balls equals the number of bins and the average load is 1. Of course the
maximum possible load is n, but it is very unlikely that all n balls land in the same bin.
We seek an upper bound that holds with probability tending to 1 as n grows large. We
can show that the maximum load is more than 3 ln n/ ln ln n with probability at most
1/n for sufficiently large n via a direct calculation and a union bound. This is a very
loose bound; although the maximum load is in fact (ln n/ ln ln n) with probability
close to 1 (as we show later), the constant factor 3 we use here is chosen to simplify
the argument and could be reduced with more care.
Lemma 5.1: When n balls are thrown independently and uniformly at random into n
bins, the probability that the maximum load is more than 3 ln n/ ln ln n is at most 1/n
for n sufficiently large.
we have
k
k
k! > .
e
Applying a union bound again allows us to find that, for M ≥ 3 ln n/ ln ln n, the prob-
ability that any bin receives at least M balls is bounded above by
M
e e ln ln n 3 ln n/ln ln n
n ≤n
M 3 ln n
ln ln n 3 ln n/ln ln n
≤n
ln n
= eln n (eln ln ln n−ln ln n )3 ln n/ln ln n
= e−2 ln n+3(ln n)(ln ln ln n)/ln ln n
1
≤
n
for n sufficiently large.
100
5.3 the poisson distribution
where the first equality follows from the linearity of expectations and the second fol-
lows from symmetry, as E[X j2 ] is the same for all buckets.
Since X1 is a binomial random variable B(n, 1/n), using the results of Section 3.2.1
yields
n(n − 1) 1
E[X12 ] = 2
+ 1 = 2 − < 2.
n n
Hence the total expected time spent in the second stage is at most 2cn, so Bucket sort
runs in expected linear time.
We now consider the probability that a given bin is empty in the balls and bins model
with m balls and n bins as well as the expected number of empty bins. For the first bin
101
balls, bins, and random graphs
to be empty, it must be missed by all m balls. Since each ball hits the first bin with
probability 1/n, the probability the first bin remains empty is
1 m
1− ≈ e−m/n ;
n
of course, by symmetry this probability is the same for all bins. If Xi is a random variable
that is 1 when the ith bin is empty and 0 otherwise, then E[Xi ] = (1 − 1/n)m . Let X be
a random variable that represents the number of empty bins. Then, by the linearity of
expectations,
n
n
1 m
E[X] = E Xi = E[Xi ] = n 1 − ≈ ne−m/n .
i=1 i=1
n
Thus, the expected fraction of empty bins is approximately e−m/n . This approximation
is very good even for moderately size values of m and n, and we use it frequently
throughout this chapter.
We can generalize the preceding argument to find the expected fraction of bins with
r balls for any constant r. The probability that a given bin has r balls is
r
m 1 1 m−r 1 m(m − 1) · · · (m − r + 1) 1 m−r
1− = 1 − .
r n n r! nr n
When m and n are large compared to r, the second factor on the right-hand side is
approximately (m/n)r , and the third factor is approximately e−m/n . Hence the proba-
bility pr that a given bin has r balls is approximately
e−m/n (m/n)r
pr ≈ , (5.2)
r!
and the expected number of bins with exactly r balls is approximately npr . We formalize
this relationship in Section 5.3.1.
The previous calculation naturally leads us to consider the following distribution.
Definition 5.1: A discrete Poisson random variable X with parameter μ is given by
the following probability distribution on j = 0, 1, 2, . . . :
e−μ μ j
Pr(X = j) = .
j!
(Note that Poisson random variables differ from Poisson trials, discussed in Sec-
tion 4.2.1.)
Let us verify that the definition gives a proper distribution in that the probabilities
sum to 1:
∞ ∞
e−μ μ j
Pr(X = j) =
j=0 j=0
j!
∞
−μ μj
=e
j=0
j!
= 1,
where we have used the Taylor expansion ex = ∞ j=0 (x / j!).
j
102
5.3 the poisson distribution
j
e−μ1 μk1 e−μ2 μ2
( j−k)
=
k=0
k! ( j − k)!
e−(μ1 +μ2 )
j
j!
= μk1 μ2( j−k)
j! k=0
k! ( j − k)!
−(μ1 +μ2 ) j
e j
= μk1 μ2( j−k)
j! k=0
k
e−(μ1 +μ2 ) (μ1 + μ2 ) j
= .
j!
In the last equality we used the binomial theorem to simplify the summation.
103
balls, bins, and random graphs
k=0
k! k=0
k!
Given two independent Poisson random variables X and Y with means μ1 and μ2 , we
apply Theorem 4.3 to prove
MX+Y (t) = MX (t) · MY (t) = e(μ1 +μ2 )(e −1) ,
t
which is the moment generating function of a Poisson random variable with mean μ1 +
μ2 . By Theorem 4.2, the moment generating function uniquely defines the distribution,
and hence the sum X + Y is a Poisson random variable with mean μ1 + μ2 .
We can also use the moment generating function of the Poisson distribution to prove
that E[X 2 ] = λ(λ + 1) and Var[X] = λ (see Exercise 5.5).
Next we develop a Chernoff bound for Poisson random variables that we will use
later in this chapter.
Theorem 5.4: Let X be a Poisson random variable with parameter μ.
1. If x > μ, then
e−μ (eμ)x
Pr(X ≥ x) ≤ ;
xx
2. If x < μ, then
e−μ (eμ)x
Pr(X ≤ x) ≤ .
xx
3. For δ > 0,
μ
eδ
Pr(X ≥ (1 + δ)μ) ≤ ;
(1 + δ)(1+δ)
4. For 0 < δ < 1,
μ
e−δ
Pr(X ≤ (1 − δ)μ) ≤ .
(1 − δ)(1−δ)
Proof: For any t > 0 and x > μ,
E[etX ]
Pr(X ≥ x) = Pr(etX ≥ etx ) ≤ .
etx
Plugging in the expression for the moment generating function of the Poisson distribu-
tion, we have
Pr(X ≥ x) ≤ eμ(e −1)−x t .
t
ex (1 − x2 ) ≤ 1 + x ≤ ex , (5.3)
which follows from the Taylor series expansion of ex . (This is left as Exercise 5.7.)
Then
nk k (1 − p)n
Pr(Xn = k) ≤ p
k! (1 − p)k
(np)k e−p n
≤
k! 1 − pk
−p n
e (np)k 1
= .
k! 1 − pk
The second line follows from the first by Eqn. (5.3) and the fact that (1 − p)k ≥ 1 − pk
for k ≥ 0. Also,
(n − k + 1)k k
Pr(Xn = k) ≥ p (1 − p)n
k!
((n − k + 1)p)k −p n
≥ e (1 − p2 )n
k!
e−p n ((n − k + 1)p)k
≥ (1 − p2 n),
k!
where in the second inequality we applied Eqn. (5.3) with x = −p.
Combining, we have
e−p n (np)k 1 e−p n ((n − k + 1)p)k
≥ Pr(Xn = k) ≥ (1 − p2 n).
k! 1 − pk k!
In the limit, as n approaches infinity, p approaches zero because the limiting value of
pn is the constant λ. Hence 1/(1 − pk) approaches 1, 1 − p2 n approaches 1, and the
difference between (n − k + 1)p and np approaches 0. It follows that
e−p n (np)k 1 e−λ λk
lim =
n→∞ k! 1 − pk k!
and
e−p n ((n − k + 1)p)k e−λ λk
lim (1 − p2 n) = .
n→∞ k! k!
Since limn→∞ Pr(Xn = k) lies between these two values, the theorem follows.
106
5.4 the poisson approximation
conditioned on (Y1(m) , . . . , Yn(m) ) satisfying i Yi(m) = k:
(m) n
Pr Y1 , . . . , Yn (m)
= (k1 , . . . , kn ) (m)
Yi = k
i=1
Pr Y1(m) = k1 ∩ Y1(m) = k2 ∩ · · · ∩ Yn(m) = kn
= n (m) .
Pr i=1 Yi =k
The probability that Yi(m) = ki is e−m/n (m/n)ki /ki !, since the Yi(m) are independent Pois-
son random variables with mean m/n. Also, by Lemma 5.2, the sum of the Yi(m) is itself
a Poisson random variable with mean m. Hence
n −m/n
Pr Y1(m) = k1 ∩ Y1(m) = k2 ∩ · · · ∩ Yn(m) = kn i=1 e (m/n)ki /ki !
n =
Pr i=1 Yi
(m)
=k e−m mk /k!
k!
= ,
(k1 !)(k2 !) · · · (kn !)nk
proving the theorem.
With this relationship between the two distributions, we can prove strong results about
any function on the loads of the bins.
Theorem 5.7: Let f (x1 , . . . , xn ) be a nonnegative function. Then
√
E f X1(m) , . . . , Xn(m) ≤ e mE f Y1(m) , . . . , Yn(m) . (5.4)
Proof: We have that
∞
n
(m)
n (m)
E f Y1 , . . . , Yn(m) = E f Y1 , . . . , Yn(m)
(m) (m)
Yi = k Pr Yi = k
k=0 i=1 i=1
n
(m)
n
≥ E f Y1 , . . . , Yn(m) Yi(m) = m Pr Yi(m) = m
i=1 i=1
= E[ f X1(m) , . . . , Xn(m) ] Pr Yi(m) =m ,
(m)
where
n the last equality follows from the fact that the joint distribution of the Y i given
(m) (m) n (m)
Y
i=1 i = m is exactly that of the Xi , as shown in Theorem 5.6. Since i=1 Yi
is Poisson distributed with mean m, we now have
mm e−m
E f Y1(m) , . . . , Yn(m) ≥ E f X1(m) , . . . , Xn(m) .
m!
We use the following loose bound on m!, which we prove as Lemma 5.8:
m
√ m
m! < e m .
e
This yields
1
E f Y1(m) , . . . , Yn(m) ≥ E f X1(m) , . . . , Xn(m) √ ,
e m
and the theorem is proven.
108
5.4 the poisson approximation
We prove the upper bound we used for factorials, which closely matches the loose lower
bound we used in Lemma 5.1.
Lemma 5.8:
√ n n
n! ≤ e n . (5.5)
e
Proof: We use the fact that
n
ln(n!) = ln i.
i=1
This follows from the fact that ln x is concave, since its second derivative is −1/x2 ,
which is always negative. Therefore,
n
n
ln n
ln x dx ≥ ln i −
1 i=1
2
or, equivalently,
ln n
n ln n − n + 1 ≥ ln(n!) − .
2
The result now follows simply by exponentiating.
Theorem 5.7 holds for any nonnegative function on the number of balls in the bins. In
particular, if the function is the indicator function that is 1 if some event occurs and 0
otherwise, then the theorem gives bounds on the probability of events. Let us call the
scenario in which the number of balls in the bins are taken to be independent Poisson
random variables with mean m/n the Poisson case, and the scenario where m balls are
thrown into n bins independently and uniformly at random the exact case.
Corollary 5.9: Any event that takes place with probability p in the Poisson case takes
√
place with probability at most pe m in the exact case.
Proof: Let f be the indicator function of the event. In this case, E[ f ] is just the
probability that the event occurs, and the result follows immediately from Theorem
5.7.
This is a quite powerful result. It says that any event that happens with small proba-
bility in the Poisson case also happens with small probability in the exact case, where
balls are thrown into bins. Since in the analysis of algorithms we often want to show
that certain events happen with small probability, this result says that we can utilize an
109
balls, bins, and random graphs
analysis of the Poisson approximation to obtain a bound for the exact case. The Pois-
son approximation is easier to analyze because the numbers of balls in each bin are
independent random variables.1
We can actually do even a little bit better in many natural cases. Part of the proof of
the following theorem is outlined in Exercises 5.14 and 5.15.
Theorem 5.10: Let f (x1 , . . . , xn ) be a nonnegative function such that
E[ f (X1(m) , . . . , Xn(m) )] is either monotonically increasing or monotonically decreasing
in m. Then
E f X1(m) , . . . , Xn(m) ≤ 2E f Y1(m) , . . . , Yn(m) . (5.6)
The following corollary is immediate.
Corollary 5.11: Let E be an event whose probability is either monotonically increas-
ing or monotonically decreasing in the number of balls. If E has probability p in the
Poisson case, then E has probability at most 2p in the exact case.
To demonstrate the utility of this corollary, we again consider the maximum load prob-
lem for the case m = n. We have shown via a union bound argument that the maximum
load is at most 3 ln n/ ln ln n with high probability. Using the Poisson approximation,
we prove the following almost-matching lower bound on the maximum load.
Lemma 5.12: When n balls are thrown independently and uniformly at random into
n bins, the maximum load is at least ln n/ ln ln n with probability at least 1 − 1/n for n
sufficiently large.
Proof: In the Poisson case, the probability that bin 1 has load at least M = ln n/ ln ln n
is at least 1/eM!, which is the probability it has load exactly M. In the Poisson case,
all bins are independent, so the probability that no bin has load at least M is at
most
1 n
1− ≤ e−n/(eM!) .
eM!
We now need to choose M so that e−n/(eM!) ≤ n−2 , for then (by Theorem 5.7) we will
have that the probability that the maximum load is not at least M in the exact case is at
√
most e n/n2 < 1/n. This will give the lemma. Because the maximum load is clearly
monotonically increasing in the number of balls, we could also apply the slightly better
Theorem 5.10, but this would not affect the argument substantially.
It therefore suffices to show that M! ≤ n/2e ln n, or equivalently that ln M! ≤ ln n −
ln ln n − ln(2e). From our bound of Eqn. (5.5), it follows that
M
M
√ M M
M! ≤ e M ≤M
e e
1 There are other ways to handle the dependencies in the balls-and-bins model. In Chapter 13 we describe a more
general way to deal with dependencies (using martingales) that applies here. Also, there is a theory of negative
dependence that applies to balls-and-bins problems that also allows these dependencies to be dealt with nicely.
110
5.4 the poisson approximation
when n (and hence M = ln n/ ln ln n) are suitably large. Hence, for n suitably large,
ln M! ≤ M ln M − M + ln M
ln n ln n
= (ln ln n − ln ln ln n) − + (ln ln n − ln ln ln n)
ln ln n ln ln n
ln n
≤ ln n −
ln ln n
≤ ln n − ln ln n − ln(2e),
where in the last two inequalities we have used the fact that ln ln n = o(ln n/ ln ln n).
Since all bins are independent under the Poisson approximation, the probability that no
bin is empty is
e−c n −c
1− ≈ e−e .
n
The last approximation is appropriate in the limit as n grows large, so we apply it here.
To show the Poisson approximation is accurate, we undertake the following steps.
Consider the experiment where each bin has a Poisson number of balls, each with mean
ln n + c. Let E be the event that no bin is empty, and let X be the number of balls thrown.
We have seen that
−c
lim Pr(E ) = e−e .
n→∞
That is, the difference between our experiment coming up with exactly m balls or just
almost m balls makes an asymptotically negligible difference in the probability that
every bin has a ball. With these two facts, Eqn. (5.7) becomes
√ √
Pr(E ) = Pr E | |X − m| ≤ 2m ln m · Pr |X − m| ≤ 2m ln m
√ √
+ Pr E | |X − m| > 2m ln m · Pr |X − m| > 2m ln m
√
= Pr E | |X − m| ≤ 2m ln m · (1 − o(1)) + o(1)
= Pr(E | X = m)(1 − o(1)) + o(1),
and hence
lim Pr(E ) = lim Pr(E | X = m).
n→∞ n→∞
But from Theorem 5.6, the quantity on the right is equal to the probability that every
bin has at least one ball when m balls are thrown randomly, since conditioning on m
total balls with the Poisson approximation is equivalent to throwing m balls randomly
into the n bins. As aresult, the theorem
√ follows
once we have shown these two facts.
To show that Pr |X − m| > 2m ln m is o(1), consider that X is a Poisson ran-
dom variable with mean m, since it is a sum of independent Poisson random variables.
We use the Chernoff bound for the Poisson distribution (Theorem 5.4) to bound this
112
5.5 application: hashing
Another possibility is to place the words into bins and then search the appropriate bin
for the word. The words in a bin would be represented by a linked list. The placement
of words into bins is accomplished by using a hash function. A hash function f from a
universe U into a range [0, n − 1] can be thought of as a way of placing items from the
universe into n bins. Here the universe U would consist of possible password strings.
The collection of bins is called a hash table. This approach to hashing is called chain
hashing, since items that fall in the same bin are chained together in a linked list.
Using a hash table turns the dictionary problem into a balls-and-bins problem. If our
dictionary of unacceptable passwords consists of m words and the range of the hash
function is [0, n − 1], then we can model the distribution of words in bins with the
same distribution as m balls placed randomly in n bins. We are making a rather strong
assumption by presuming that our hash function maps words into bins in a fashion
that appears random, so that the location of each word is independent and identically
distributed. There is a great deal of theory behind designing hash functions that appear
random, and we will not delve into that theory here. We simply model the problem by
assuming that hash functions are random. In other words, we assume that (a) for each
x ∈ U, the probability that f (x) = j is 1/n (for 0 ≤ j ≤ n − 1) and that (b) the values
of f (x) for each x are independent of each other. Notice that this does not mean that
every evaluation of f (x) yields a different random answer! The value of f (x) is fixed
for all time; it is just equally likely to take on any value in the range.
Let us consider the search time when there are n bins and m words. To search for an
item, we first hash it to find the bin that it lies in and then search sequentially through
the linked list for it. If we search for a word that is not in our dictionary, the expected
number of words in the bin the word hashes to is m/n. If we search for a word that is in
our dictionary, the expected number of other words in that word’s bin is (m − 1)/n, so
the expected number of words in the bin is 1 + (m − 1)/n. If we choose n = m bins for
our hash table, then the expected number of words we must search through in a bin is
constant. If the hashing takes constant time, then the total expected time for the search
is constant.
The maximum time to search for a word, however, is proportional to the maximum
number of words in a bin. We have shown that when n = m this maximum load is
(ln n/ ln ln n) with probability close to 1, and hence with high probability this is the
maximum search time in such a hash table. While this is still faster than the required
time for standard binary search, it is much slower than the average, which can be a
drawback for many applications.
Another drawback of chain hashing can be wasted space. If we use n bins for n items,
several of the bins will be empty, potentially leading to wasted space. The space wasted
can be traded off against the search time by making the average number of words per
bin larger than 1.
represent. Suppose we use a hash function to map each word into a 32-bit string. This
string will serve as a short fingerprint for the word; just as a fingerprint is a succinct way
of identifying people, the fingerprint string is a succinct way of identifying a word. We
keep the fingerprints in a sorted list. To check if a proposed password is unacceptable,
we calculate its fingerprint and look for it on the list, say by a binary search.2 If the
fingerprint is on the list, we declare the password unacceptable.
In this case, our password checker may not give the correct answer! It is possible for
a user to input an acceptable password, only to have it rejected because its fingerprint
matches the fingerprint of an unacceptable password. Hence there is some chance that
hashing will yield a false positive: it may falsely declare a match when there is not an
actual match. The problem is that – unlike fingerprints for human beings – our finger-
prints do not uniquely identify the associated word. This is the only type of mistake this
algorithm can make; it does not allow a password that is in the dictionary of unsuitable
passwords. In the password application, allowing false positives means our algorithm
is overly conservative, which is probably acceptable. Letting easily cracked passwords
through, however, would probably not be acceptable.
To place the problem in a more general context, we describe it as an approximate
set membership problem. Suppose we have a set S = {s1 , s2 , . . . , sm } of m elements
from a large universe U. We would like to represent the elements in such a way that
we can quickly answer queries of the form “is x an element of S?” We would also like
the representation to take as little space as possible. In order to save space, we would
be willing to allow occasional mistakes in the form of false positives. Here the unal-
lowable passwords correspond to our set S.
How large should the range of the hash function used to create the fingerprints be?
Specifically, if we are working with bits, how many bits should we use to create a
fingerprint? Obviously, we want to choose the number of bits that gives an acceptable
probability for a false positive match. The probability that an acceptable password has a
fingerprint that is different from any specific unallowable password in S is (1 − 1/2b ).
It follows that if the set S has size m and if we use b bits for the fingerprint, then
the probability of a false positive for an acceptable password is 1 − (1 − 1/2b )m ≥
1 − e−m/2 . If we want this probability of a false positive to be less than a constant c,
b
we need
e−m/2 ≥ 1 − c,
b
115
balls, bins, and random graphs
In our example, if our dictionary has 216 = 65,536 words, then using 32 bits when
hashing yields a false positive probability of just less than 1/65,536.
We let f = (1 − e−km/n )k = (1 − p)k . From now on, for convenience we use the
asymptotic approximations p and f to represent (respectively) the probability that a
bit in the Bloom filter is 0 and the probability of a false positive.
Suppose that we are given m and n and wish to optimize the number of hash func-
tions k in order to minimize the false positive probability f. There are two competing
forces: using more hash functions gives us more chances to find a 0-bit for an element
that is not a member of S, but using fewer hash functions increases the fraction of 0-bits
116
5.5 application: hashing
in the array. The optimal number of hash functions that minimizes f as a function of k
is easily found taking the derivative. Let g = k ln(1 − e−km/n ), so that f = eg and mini-
mizing the false positive probability f is equivalent to minimizing g with respect to k. We
find
dg km e−km/n
= ln(1 − e−km/n ) + .
dk n 1 − e−km/n
It is easy to check that the derivative is zero when k = (ln 2) · (n/m) and that this
point is a global minimum. In this case the false positive probability f is (1/2)k ≈
(0.6185)n/m . The false positive probability falls exponentially in n/m, the number of
bits used per item. In practice, of course, k must be an integer, so the best possible
choice of k may lead to a slightly higher false positive rate.
A Bloom filter is like a hash table, but instead of storing set items we simply use one
bit to keep track of whether or not an item hashed to that location. If k = 1, we have
just one hash function and the Bloom filter is equivalent to a hashing-based fingerprint
system, where the list of the fingerprints is stored in a 0–1 bit array. Thus Bloom filters
can be seen as a generalization of the idea of hashing-based fingerprints. As we saw
when using fingerprints, to get even a small constant probability of a false positive
required (log m) fingerprint bits per item. In many practical applications, (log m)
bits per item can be too many. Bloom filters allow a constant probability of a false
positive while keeping n/m, the number of bits of storage required per item, constant.
For many applications, the small space requirements make a constant probability of
117
balls, bins, and random graphs
error acceptable. For example, in the password application, we may be willing to accept
false positive rates of 1% or 2%.
Bloom filters are highly effective even if n = cm for a small constant c, such as
c = 8. In this case, when k = 5 or k = 6 the false positive probability is just over 0.02.
This contrasts with the approach of hashing each element into (log m) bits. Bloom
filters require significantly fewer bits while still achieving a very good false positive
probability.
It is also interesting to frame the optimization another way. Consider f, the proba-
bility of a false positive, as a function of p. We find
f = (1 − p)k
= (1 − p)(− ln p)(n/m)
= (e− ln(p) ln(1−p) )n/m . (5.8)
From the symmetry of this expression, it is easy to check that p = 1/2 minimizes the
false positive probability f. Hence the optimal results are achieved when each bit of the
Bloom filter is 0 with probability 1/2. An optimized Bloom filter looks like a random
bit string.
To conclude, we reconsider our assumption that the fraction of entries that are still 0
after all of the elements of S are hashed into the Bloom filter is p. Each bit in the array
can be thought of as a bin, and hashing an item is like throwing a ball. The fraction of
entries that are still 0 after all of the elements of S are hashed is therefore equivalent to
the fraction of empty bins after mk balls are thrown into n bins. Let X be the number of
such bins when mk balls are thrown. The expected fraction of such bins is
1 km
p = 1− .
n
The events of different bins being empty are not independent, but we can apply
Corollary 5.9, along with the Chernoff bound of Eqn. (4.6), to obtain
√
Pr(|X − np | ≥ εn) ≤ 2e ne−nε /3p .
2
Actually, Corollary 5.11 applies as well, since the number of 0-entries – which corre-
sponds to the number of empty bins – is monotonically decreasing in the number of
balls thrown. The bound tells us that the fraction of empty bins is close to p (when
n is reasonably large) and that p is very close to p. Our assumption that the fraction
of 0-entries in the Bloom filter is p is therefore quite accurate for predicting actual
performance.
If each user has an identifying name or number, hashing provides one possible solu-
tion. Hash each user’s identifier into 2b bits, and then take the permutation given by
the sorted order of the resulting numbers. That is, the user whose identifier gives the
smallest number when hashed comes first, and so on. For this approach to work, we do
not want two users to hash to the same value, since then we must decide again how to
order these users.
If b is sufficiently large, then with high probability the users will all obtain distinct
hash values. One can analyze the probability that two hash values collide by using the
analysis from Section 5.1 for the birthday paradox; hash values correspond to birthdays.
We here use a simpler analysis based just on using a union bound. There are n2 pairs
of users. The probability that any specific pair has the same hash value is 1/2b . Hence
the probability that any pair has the same hash value is at most
n 1 n(n − 1)
b
= .
2 2 2b+1
pm (1 − p)(2 )−m .
n
One way to generate a random graph in Gn,p is to consider each of the n2 possible edges
in some order and then independently add each edge to the graph with probability p.
119
balls, bins, and random graphs
The expected number of edges in the graph is therefore n2 p, and each vertex has
expected degree (n − 1)p.
In the Gn,N model,
n we consider all undirected graphs on n vertices with exactly N
edges. There are (N2 ) possible graphs, each selected with equal probability. One way
from the graphs in Gn,N is to start with a graph with no
to generate a graph uniformly
edges. Choose one of the n2 possible edges uniformly n at random and add it to the edges
in the graph. Now choose one of the remaining 2 − 1 possible edges independently
and uniformly at random and add it to the graph. Similarly, continue choosing one of
the remaining unchosen edges independently and uniformly at random until there are
N edges.
The Gn,p and Gn,N models are related; when p = N/ n2 , the number of edges in a
random graph in Gn,p is concentrated around N, and conditioned on a graph from Gn,p
having N edges, that graph is uniform over all the graphs from Gn,N . The relationship
is similar to the relationship between throwing m balls into n bins and having each bin
have a Poisson distributed number of balls with mean m/n.
Here, for example is one way of formalizing the relationship between the Gn,p and
Gn,N models. A graph property is a property that holds for a graph regardless of how
the vertices are labeled, so it holds for all possible isomorphisms of the graph. We say
that a graph property is monotone increasing if whenever the property holds for G =
(V, E ) it holds also for any graph G = (V, E ) with E ⊆ E ; monotone decreasing graph
properties are defined similarly. For example, the property that a graph is connected
is a monotone increasing graph property, as is the property that a graph contains a
connected component of at least k vertices for any particular value of k. The property
that a graph is a tree, however, is not a monotone graph property, although the property
that the graph contains no cycles is a monotone decreasing graph property. We have
the following lemma:
Lemma 5.14: For a given monotone increasing graph property let P(n, N) be the
probability that the property holds for a graph in Gn,N and P(n, p) the probability
that
it holds for a graph in Gn,p . Let p+ = (1 + )N/ n2 and p− = (1 − )N/ n2 for a
constant 1 > > 0. Then
P(n, p− ) − e−O(N ) ≤ P(n, N) ≤ P(n, p+ ) + e−O(N ) .
Proof: Let X be a random variable giving the number of edges that occur when a graph
is chosen from Gn,p− . Conditioned on X = k, a random graph from Gn,p− is equivalent
to a graph from Gn,k , since the k edges chosen are equally likely to be any subset of k
edges. Hence
( n2 )
−
P(n, p ) = P(n, k) Pr(X = k).
k=0
In particular,
P(n, p− ) = P(n, k) Pr(X = k) + P(n, k) Pr(X = k).
k≤N k>N
120
5.6 random graphs
Also, for a monotone increasing graph property, P(n, k) ≤ P(n, N) for k ≤ N. Hence
P(n, p− ) ≤ Pr(X ≤ N)P(n, N) + Pr(X > N) ≤ P(n, N) + Pr(X > N).
However, Pr(X > N) can be bounded by a standard Chernoff bound; X is the sum of
n
2
independent Bernoulli random variables, and hence by Theorem 4.4
1
E[X] ≤ Pr(X > (1 + )E[X]) ≤ e−(1−) N/3 .
2
Pr(X > N) = Pr X >
1−
Here we have used that 1
1−
> 1 + for 0 < < 1.
Similarly,
P(n, p+ ) = P(n, k) Pr(X = k) + P(n, k) Pr(X = k),
k<N k≥N
so
P(n, p+ ) ≥ Pr(X ≥ N)P(n, N) ≥ P(n, N) − Pr(X < N).
By Theorem 4.5
1
E[X] ≤ e−(1+) N/8 ,
2
Pr(X > N) = Pr X < E[X] ≤ Pr X < 1 +
1+ 2
where here we have used that 1
1+
< 1 − /2 for 0 < < 1.
Figure 5.2: The rotation of the path v1 , v2 , v3 , v4 , v5 , v6 with the edge (v6 , v3 ) yields a new path
v1 , v2 , v3 , v6 , v5 , v4 .
is an NP-hard problem. However, our analysis of this algorithm shows that finding a
Hamiltonian cycle is not hard for suitably randomly selected graphs, even though it
may be hard to solve in general.
Our algorithm will make use of a simple operation called a rotation. Let G be an
undirected graph. Suppose that
P = v1 , v2 , . . . , vk
is a simple path in G and that (vk , vi ) is an edge of G. Then
P = v1 , v2 , . . . , vi , vk , vk−1 , . . . , vi+2 , vi+1
is also a simple path, which we refer to as the rotation of P with the rotation edge
(vk , vi ); see Figure 5.2.
We first consider a simple, natural algorithm that proves challenging to analyze. We
assume that our input is presented as a list of adjacent edges for each vertex in the graph,
with the edges of each list being given in a random order according to independent and
uniform random permutations. Initially, the algorithm chooses an arbitrary vertex to
start the path; this is the initial head of the path. The head is always one of the endpoints
of the path. From this point on, the algorithm either “grows” the path deterministically
from the head, or rotates the path – as long as there is an adjacent edge remaining on
the head’s list. See Algorithm 5.1.
The difficulty in analyzing this algorithm is that, once the algorithm views some
edges in the edge lists, the distribution of the remaining edges is conditioned on the
edges the algorithm has already seen. We circumvent this difficulty by considering a
modified algorithm that, though less efficient, avoids this conditioning issue and so is
easier to analyze for the random graphs we consider. See Algorithm 5.2. Each ver-
tex v keeps two lists. The list used-edges(v) contains edges adjacent to v that have
been used in the course of the algorithm while v was the head; initially this list is
empty. The list unused-edges(v) contains other edges adjacent to v that have not been
used.
We initially analyze the algorithm assuming a specific model for the initial unused-
edges lists. We subsequently relate this model to the Gn,p model for random graphs.
Assume that each of the n − 1 possible edges connected to a vertex v is initially on the
unused-edges list for vertex v independently with some probability q. We also assume
these edges are in a random order. One way to think of this is that, before beginning
the algorithm, we create the unused-edges list for each vertex v by inserting each pos-
sible edge (v, u) with probability q; we think of the corresponding graph G as being
the graph including all edges that were inserted on some unused-edges list. Notice that
122
5.6 random graphs
123
balls, bins, and random graphs
this means an edge (v, u) could initially be on the unused-edges list for v but not for
u. Also, when an edge (v, u) is first used in the algorithm, if v is the head then it is
removed just from the unused-edges list of v; if the edge is on the unused-edges list for
u, it remains on this list.
By choosing the rotation edge from either the used-edges list or the unused-edges
list with appropriate probabilities and then reversing the path with some small proba-
bility in each step, we modify the rotation process so that the next head of the list is
chosen uniformly at random from among all vertices of the graph. Once we establish
this property, the progress of the algorithm can be analyzed through a straightforward
application of our analysis of the coupon collector’s problem.
The modified algorithm appears wasteful; reversing the path or rotating with one of
the used edges cannot increase the path length. Also, we may not be taking advantage
of all the possible edges of G at each step. The advantage of the modified algorithm is
that it proves easier to analyze, owing to the following lemma.
Lemma 5.16: Suppose the modified Hamiltonian cycle algorithm is run on a graph
chosen using the described model. Let Vt be the head vertex after the tth step. Then, for
any vertex u, as long as at the tth step there is at least one unused edge available at the
head vertex,
That is, the head vertex can be thought of as being chosen uniformly at random from
all vertices at each step, regardless of the history of the process.
If u = vi+1 is a vertex on the path but (vk , vi ) is not in used-edges(vk ), then the
probability that Vt+1 = u is the probability that the edge (vk , vi ) is chosen from unused-
edges(vk ) as the next rotation edge, which is
1 |used-edges(vk )| 1 1
1− − = . (5.9)
n n n − |used-edges(vk )| − 1 n
Finally, if u is not on the path, then the probability that Vt+1 = u is the probability that
the edge (vk+1 , u) is chosen from unused-edges(vk ). But this has the same probability
as in Eqn. (5.9).
For Algorithm 5.2, the problem of finding a Hamiltonian path looks exactly like the
coupon collector’s problem; the probability of finding a new vertex to add to the path
when there are k vertices left to be added is k/n. Once all the vertices are on the
path, the probability that a cycle is closed in each rotation is 1/n. Hence, if no list
of unused-edges is exhausted then we can expect a Hamiltonian path to be formed in
about O(n ln n) rotations, with about another O(n ln n) rotations to close the path to
form a Hamiltonian cycle. More concretely, we can prove the following theorem.
Theorem 5.17: Suppose the input to the modified Hamiltonian cycle algorithm ini-
tially has unused-edge lists where each edge (v, u) with u = v is placed on v’s list
independently with probability q ≥ 20 ln n/n. Then the algorithm successfully finds a
Hamiltonian cycle in O(n ln n) iterations of the repeat loop (step 2) with probability
1 − O(n−1 ).
Note that we did not assume that the input random graph has a Hamiltonian cycle. A
corollary of the theorem is that, with high probability, a random graph chosen in this
way has a Hamiltonian cycle.
Proof of Theorem 5.17: Consider the following two events.
E1 : The algorithm ran for 3n ln n steps with no unused-edges list becoming empty, but
it failed to construct a Hamiltonian cycle.
E2 : At least one unused-edges list became empty during the first 3n ln n iterations of
the loop.
For the algorithm to fail, either event E1 or E2 must occur. We first bound the proba-
bility of E1 . Lemma 5.16 implies that, as long as there is no empty unused-edges list in
the first 3n ln n iterations of step 2 of Algorithm 5.2, in each iteration the next head of
the path is uniform among the n vertices of the graph. To bound E1 , we therefore con-
sider the probability that more than 3n ln n iterations are required to find a Hamiltonian
cycle when the head is chosen uniformly at random each iteration.
The probability that the algorithm takes more than 2n ln n iterations to find a Hamil-
tonian path is exactly the probability that a coupon collector’s problem on n types
requires more than 2n ln n coupons. The probability that any specific coupon type has
not been found among 2n ln n random coupons is
1 2n ln n 1
1− ≤ e−2 ln n = 2 .
n n
125
balls, bins, and random graphs
By the union bound, the probability that any coupon type is not found is at most
1/n.
In order to complete a Hamiltonian path to a cycle the path must close, which it does
at each step with probability 1/n. Hence the probability that the path does not become
a cycle within the next n ln n iterations is
n ln n
1 1
1− ≤ e− ln n = .
n n
and hence
2
Pr(E2 ) ≤ .
n
In total, the probability that the algorithm fails to find a Hamiltonian cycle in 3n ln n
iterations is bounded by
4
Pr(E1 ) + Pr(E2 ) ≤ .
n
We did not make an effort to optimize the constants in the proof. There is, how-
ever, a clear trade-off; with more edges, one could achieve a lower probability of
failure.
We are left with showing how our algorithm can be applied to graphs in Gn,p . We
show that, as long as p is known, we can partition the edges of the graph into edge lists
that satisfy the requirements of Theorem 5.17.
Proof: We partition the edges of our input graph from Gn,p as follows. Let q ∈ [0, 1] be
such that p = 2q − q2 . Consider any edge (u, v) in the input graph. We execute exactly
one of the following three possibilities: with probability q(1 − q)/(2q − q2 ) we place
the edge on u’s unused-edges list but not on v’s; with probability q(1 − q)/(2q − q2 ) we
initially place the edge on v’s unused-edges list but not on u’s; and with the remaining
probability q2 /(2q − q2 ) the edge is placed on both unused-edges lists.
Now, for any possible edge (u, v), the probability that it is initially placed in the
unused-edges list for v is
q(1 − q) q2
p + = q.
2q − q2 2q − q2
Moreover, the probability that an edge (u, v) is initially placed on the unused-edges
list for both u and v is pq2 /(2q − q2 ) = q2 , so these two placements are indepen-
dent events. Since each edge (u, v) is treated independently, this partitioning fulfills
the requirements of Theorem 5.17 provided the resulting q is at least 20 ln n/n. When
p ≥ (40 ln n)/n we have q ≥ p/2 ≥ (20 ln n)/n, and the result follows.
In Exercise 5.27, we consider how to use Algorithm 5.2 even in the case where p is not
known in advance, so that the edge lists must be initialized without knowledge of p.
5.7. Exercises
127
balls, bins, and random graphs
Exercise 5.2: Suppose that Social Security numbers were issued uniformly at random,
with replacement. That is, your Social Security number would consist of just nine ran-
domly generated digits, and no check would be made to ensure that the same number
was not issued twice. Sometimes, the last four digits of a Social Security number are
used as a password. How many people would you need to have in a room before it was
more likely than not that two had the same last four digits? How many numbers could
be issued before it would be more likely than not that there is a duplicate number? How
would you answer these two questions if Social Security numbers had 13 digits? Try
to give exact numerical answers.
Exercise 5.3: Suppose that balls are thrown randomly into n bins. Show, for some
√
constant c1 , that if there are c1 n balls then the probability that no two land in the
same bin is at most 1/e. Similarly, show for some constant c2 (and sufficiently large n)
√
that, if there are c2 n balls, then the probability that no two land in the same bin is at
least 1/2. Make these constants as close to optimal as possible. Hint: You may want to
use the facts that
e−x ≥ 1 − x
and
1
e−x−x ≤ 1 − x
2
for x≤ .
2
Exercise 5.4: In a lecture hall containing 100 people, you consider whether or not
there are three people in the room who share the same birthday. Explain how to calculate
this probability exactly, using the same assumptions as in our previous analysis.
Exercise 5.5: Use the moment generating function of the Poisson distribution to com-
pute the second moment and the variance of the distribution.
Exercise 5.6: Let X be a Poisson random variable with mean μ, representing the num-
ber of errors on a page of this book. Each error is independently a grammatical error
with probability p and a spelling error with probability 1 − p. If Y and Z are random
variables representing the number of grammatical and spelling errors (respectively) on
a page of this book, prove that Y and Z are Poisson random variables with means μp
and μ(1 − p), respectively. Also, prove that Y and Z are independent.
Exercise 5.8: Suppose that n balls are thrown independently and uniformly at random
into n bins.
128
5.7 exercises
(a) Find the conditional probability that bin 1 has one ball given that exactly one ball
fell into the first three bins.
(b) Find the conditional expectation of the number of balls in bin 1 under the condition
that bin 2 received no balls.
(c) Write an expression for the probability that bin 1 receives more balls than bin 2.
Exercise 5.9: Our analysis of Bucket sort in Section 5.2.2 assumed that n elements
were chosen independently and uniformly at random from the range [0, 2k ). Suppose
instead that n elements are chosen independently from the range [0, 2k ) according to
a distribution with the property that any number x ∈ [0, 2k ) is chosen with probability
at most a/2k for some fixed constant a > 0. Show that, under these conditions, Bucket
sort still requires linear expected time.
Exercise 5.10: Consider the probability that every bin receives exactly one ball when
n balls are thrown randomly into n bins.
(a) Give an upper bound on this probability using the Poisson approximation.
(b) Determine the exact probability of this event.
(c) Show that these two probabilities differ by a multiplicative factor that equals the
probability that a Poisson random variable with parameter n takes on the value n.
Explain why this is implied by Theorem 5.6.
Exercise 5.11: Consider throwing m balls into n bins, and for convenience let the
bins be numbered from 0 to n − 1. We say there is a k-gap starting at bin i if bins
i, i + 1, . . . , i + k − 1 are all empty.
Exercise 5.12: The following problem models a simple distributed system wherein
agents contend for resources but “back off” in the face of contention. Balls represent
agents, and bins represent resources.
The system evolves over rounds. Every round, balls are thrown independently and
uniformly at random into n bins. Any ball that lands in a bin by itself is served and
removed from consideration. The remaining balls are thrown again in the next round.
We begin with n balls in the first round, and we finish when every ball is served.
(a) If there are b balls at the start of a round, what is the expected number of balls at
the start of the next round?
(b) Suppose that every round the number of balls served was exactly the expected
number of balls to be served. Show that all the balls would be served in O(log log n)
rounds. (Hint: If x j is the expected number of balls left after j rounds, show and
use that x j+1 ≤ x2j /n.)
129
balls, bins, and random graphs
Exercise 5.13: Suppose that we vary the balls-and-bins process as follows. For conve-
nience let the bins be numbered from 0 to n − 1. There are log2 n players. Each player
randomly chooses a starting location uniformly from [0, n − 1] and then places one
ball in each of the bins numbered mod n, + 1 mod n, . . . , + n/ log2 n − 1 mod n.
Argue that the maximum load in this case is only O(log log n/ log log log n) with prob-
ability that approaches 1 as n → ∞.
Exercise 5.15: (a) In Theorem 5.7 we showed that, for any nonnegative functions f,
(m)
E f Y1(m) , . . . , Yn(m) ≥ E f X1(m) , . . . , Xn(m) Pr Yi = m .
Exercise 5.16: We consider another way to obtain Chernoff-like bounds in the setting
of balls and bins without using Theorem 5.7. Consider n balls thrownrandomly into
n bins. Let Xi = 1 if the ith bin is empty and 0 otherwise. Let X = ni=1 Xi . Let Yi ,
i = 1, . . . , n, be independent
Bernoulli random variables that are 1 with probability
p = (1 − 1/n)n . Let Y = ni=1 Yi .
(a) Show that E[X1 X2 · · · Xk ] ≤ E[Y1Y2 · · · Yk ] for any k ≥ 1.
(b) Show that E[etX ] ≤ E[etY ] for all t ≥ 0. (Hint: Use the expansion for ex and com-
pare E[X k ] to E[Y k ].)
(c) Derive a Chernoff bound for Pr(X ≥ (1 + δ)E[X]).
Exercise 5.17: Let G be a random graph generated using the Gn,p model.
(a) A clique of k vertices in a graph is a subset of k vertices such that all 2k edges
between these vertices lie in the graph. For what value of p, as a function of n, is
the expected number of cliques of five vertices in G equal to 1?
(b) A K3,3 graph is a complete bipartite graph with three vertices on each side. In other
words, it is a graph with six vertices and nine edges; the six distinct vertices are
arranged in two groups of three, and the nine edges connect each of the nine pairs
130
5.7 exercises
of vertices with one vertex in each group. For what value of p, as a function of n,
is the expected number of K3,3 subgraphs of G equal to 1?
(c) For what value of p, as a function of n, is the expected number of Hamiltonian
cycles in the graph equal to 1?
Exercise 5.18: Theorem 5.7 shows that any event that occurs with small probability
in the balls-and-bins setting where the number of balls in each bin is an independent
Poisson random variable also occurs with small probability in the standard balls-and-
bins model. Prove a similar statement for random graphs: Every event that happens
in the Gn,p model also happens with small probability in the
with small probability
Gn,N model for N = n2 p.
Exercise 5.21: (a) Let f (n) be the expected number of random edges that must be
added before an empty undirected graph with n vertices becomes connected. (Con-
nectedness is defined in Exercise 5.19.) That is, suppose that we start with a graph on
n vertices with zero edges and then repeatedly add an edge, chosen uniformly at ran-
dom from all edges not currently in the graph, until the graph becomes connected. If
Xn represents the number of edges added, then f (n) = E[Xn ].
Write a program to estimate f (n) for a given value of n. Your program should track
the connected components of the graph as you add edges until the graph becomes con-
nected. You will probably want to use a disjoint set data structure, a topic covered in
standard undergraduate algorithms texts. You should try n = 100, 200, 300, 400, 500,
600, 700, 800, 900, and 1000. Repeat each experiment 100 times, and for each value of
n compute the average number of edges needed. Based on your experiments, suggest a
function h(n) that you think is a good estimate for f (n).
(b) Modify your program for the problem in part (a) so that it also keeps track of
isolated vertices. Let g(n) be the expected number of edges added before there are no
more isolated vertices. What seems to be the relationship between f (n) and g(n)?
Exercise 5.22: In hashing with open addressing, the hash table is implemented as an
array and there are no linked lists or chaining. Each entry in the array either contains
one hashed item or is empty. The hash function defines, for each key k, a probe sequence
h(k, 0), h(k, 1), . . . of table locations. To insert the key k, we first examine the sequence
of table locations in the order defined by the key’s probe sequence until we find an
empty location; then we insert the item at that position. When searching for an item in
the hash table, we examine the sequence of table locations in the order defined by the
key’s probe sequence until either the item is found or we have found an empty location
131
balls, bins, and random graphs
in the sequence. If an empty location is found, this means the item is not present in the
table.
An open-address hash table with 2n entries is used to store n items. Assume that the
table location h(k, j) is uniform over the 2n possible table locations and that all h(k, j)
are independent.
(a) Show that, under these conditions, the probability of an insertion requiring more
than k probes is at most 2−k .
(b) Show that, for i = 1, 2, . . . , n, the probability that the ith insertion requires more
than 2 log n probes is at most 1/n2 .
Let the random variable Xi denote the number of probes required by the ith insertion.
You have shown in part (b) that Pr(Xi > 2 log n) ≤ 1/n2 . Let the random variable X =
max1≤i≤n Xi denote the maximum number of probes required by any of the n insertions.
(c) Show that Pr(X > 2 log n) ≤ 1/n.
(d) Show that the expected length of the longest probe sequence is E[X] = O(log n).
Exercise 5.23: Bloom filters can be used to estimate set differences. Suppose you have
a set X and I have a set Y, both with n elements. For example, the sets might represent
our 100 favorite songs. We both create Bloom filters of our sets, using the same number
of bits m and the same k hash functions. Determine the expected number of bits where
our Bloom filters differ as a function of m, n, k, and |X ∩ Y |. Explain how this could be
used as a tool to find people with the same taste in music more easily than comparing
lists of songs directly.
Exercise 5.24: Suppose that we wanted to extend Bloom filters to allow deletions as
well as insertions of items into the underlying set. We could modify the Bloom filter
to be an array of counters instead of an array of bits. Each time an item is inserted
into a Bloom filter, the counters given by the hashes of the item are increased by one.
To delete an item, one can simply decrement the counters. To keep space small, the
counters should be a fixed length, such as 4 bits.
Explain how errors can arise when using fixed-length counters. Assuming a setting
where one has at most n elements in the set at any time, m counters, k hash functions,
and counters with b bits, explain how to bound the probability that an error occurs over
the course of t insertions or deletions.
Exercise 5.25: Suppose that you built a Bloom filter for a dictionary of words with
m = 2b bits. A co-worker building an application wants to use your Bloom filter but
has only 2b−1 bits available. Explain how your colleague can use your Bloom filter to
avoid rebuilding a new Bloom filter using the original dictionary of words.
Exercise 5.26: For the leader election problem alluded to in Section 5.5.4, we have n
users, each with an identifier. The hash function takes as input the identifier and outputs
a b-bit hash value, and we assume that these values are independent and uniformly
distributed. Each user hashes its identifier, and the leader is the user with the smallest
132
5.8 an exploratory assignment
hash value. Give lower and upper bounds on the number of bits b necessary to ensure
that a unique leader is successfully chosen with probability p. Make your bounds as
tight as possible.
Exercise 5.27: Consider Algorithm 5.2, the modified algorithm for finding Hamilto-
nian cycles. We have shown that the algorithm can be applied to find a Hamiltonian
cycle with high probability in a graph chosen randomly from Gn,p , when p is known
and sufficiently large, by initially placing edges in the edge lists appropriately. Argue
that the algorithm can similarly be applied to find a Hamiltonian cycle with high prob-
ability on a graph chosen randomly from Gn,N when N = c1 n ln n for a suitably large
constant c1 . Argue also that the modified algorithm can be applied even when p is not
known in advance as long as p is at least c2 ln n/n for a suitably large constant c2 .
Part of the research process in random processes is first to understand what is going on
at a high level and then to use this understanding in order to develop formal mathemat-
ical proofs. In this assignment, you will be given several variations on a basic random
process. To gain insight, you should perform experiments based on writing code to
simulate the processes. (The code should be very short, a few pages at most.) After
the experiments, you should use the results of the simulations to guide you to make
conjectures and prove statements about the processes. You can apply what you have
learned up to this point, including probabilistic bounds and analysis of balls-and-bins
problems.
Consider a complete binary tree with N = 2n − 1 nodes. Here n is the depth of the
tree. Initially, all nodes are unmarked. Over time, via processes that we shall describe,
nodes becomes marked.
All of the processes share the same basic form. We can think of the nodes as having
unique identifying numbers in the range of [1, N]. Each unit of time, I send you the
identifier of a node. When you receive a sent node, you mark it. Also, you invoke the
following marking rule, which takes effect before I send out the next node.
r If a node and its sibling are marked, its parent is marked.
r If a node and its parent are marked, the other sibling is marked.
The marking rule is applied recursively as much as possible before the next node is
sent. For example, in Figure 5.3, the marked nodes are filled in. The arrival of the node
labeled by an X will allow you to mark the remainder of the nodes, as you apply the
marking rule first up and then down the tree. Keep in mind that you always apply the
marking rule as much as possible.
Now let us consider the different ways in which I might be sending you the nodes.
Process 1: Each unit of time, I send the identifier of a node chosen independently and
uniformly at random from all of the N nodes. Note that I might send you a node that
is already marked, and in fact I may send a useless node that I have already sent.
133
balls, bins, and random graphs
Process 2: Each unit of time I send the identifier of a node chosen uniformly at random
from those nodes that I have not yet sent. Again, a node that has already been marked
might arrive, but each node will be sent at most once.
Process 3: Each unit of time I send the identifier of a node chosen uniformly at random
from those nodes that you have not yet marked.
We want to determine how many time steps are needed before all the nodes are
marked for each of these processes. Begin by writing programs to simulate the sending
processes and the marking rule. Run each process ten times for each value of n in the
range [10, 20]. Present the data from your experiments in a clear, easy-to-read fashion
and explain your data suitably. A tip: You may find it useful to have your program print
out the last node that was sent before the tree became completely marked.
1. For the first process, prove that the expected number of nodes sent is (N log N).
How well does this match your simulations?
2. For the second process, you should find that almost all N nodes must be sent
√ before
the tree is marked. Show that, with constant probability, at least N − 2 N nodes
must be sent.
3. The behavior of the third process might seem a bit unusual. Explain it with a proof.
After answering these questions, you may wish to consider other facts you could prove
about these processes.
134
chapter six
The Probabilistic Method
The probabilistic method is a way of proving the existence of objects. The under-
lying principle is simple: to prove the existence of an object with certain properties,
we demonstrate a sample space of objects in which the probability is positive that a
randomly selected object has the required properties. If the probability of selecting an
object with the required properties is positive, then the sample space must contain such
an object, and therefore such an object exists. For example, if there is a positive proba-
bility of winning a million-dollar prize in a raffle, then there must be at least one raffle
ticket that wins that prize.
Although the basic principle of the probabilistic method is simple, its application to
specific problems often involves sophisticated combinatorial arguments. In this chapter
we study a number of techniques for constructing proofs based on the probabilistic
method, starting with simple counting and averaging arguments and then introducing
two more advanced tools, the Lovász local lemma and the second moment method.
In the context of algorithms we are generally interested in explicit constructions
of objects, not merely in proofs of existence. In many cases the proofs of existence
obtained by the probabilistic method can be converted into efficient randomized con-
struction algorithms. In some cases, these proofs can be converted into efficient deter-
ministic construction algorithms; this process is called derandomization, since it con-
verts a probabilistic argument into a deterministic one. We give examples of both
randomized and deterministic construction algorithms arising from the probabilistic
method.
where the last inequality follows from the assumptions of the theorem. Hence
⎛ n ⎞ ⎛ n ⎞
⎜
k
⎟ ⎜ ⎟
k
Pr ⎝ Ai ⎠ = 1 − Pr ⎝ Ai ⎠ > 0.
i=1 i=1
As an example, consider whether the edges of K1000 can be 2-colored in such a way
that there is no monochromatic K20 . Our calculations are simplified if we note that, for
n ≤ 2k/2 and k ≥ 3,
n − 2k +1 nk
2 ≤ 2−(k(k−1)/2)+1
k k!
2k/2+1
≤
k!
< 1.
Observing that for our example n = 1000 ≤ 210 = 2k/2 , we see that by Theorem 6.1
there exists a 2-coloring of the edges of K1000 with no monochromatic K20 .
136
6.2 the expectation argument
Can we use this proof to design an efficient algorithm to construct such a coloring?
Let us consider a general approach that gives a randomized construction algorithm.
First, we require that we can efficiently sample a coloring from the sample space. In
this case sampling is easy, because we can simply color each edge independently with
a randomly chosen color. In general, however, there might not be an efficient sampling
algorithm.
If we have an efficient sampling algorithm, the next question is: How many sam-
ples must we generate before obtaining a sample that satisfies our requirements? If
the probability of obtaining a sample with the desired properties is p and if we sam-
ple independently at each trial, then the number of samples needed before finding a
sample with the required properties is a geometric random variable with expectation
1/p. Hence we need that 1/p be polynomial in the problem size in order to have an
algorithm that finds a suitable sample in polynomial expected time.
If p = 1 − o(1), then sampling once gives a Monte Carlo construction algorithm
that is incorrect with probability o(1). In our specific example of finding a coloring on
a graph of 1000 vertices with no monochromatic K20 , we know that the probability that
a random coloring has a monochromatic K20 is at most
220/2+1
< 8.5 · 10−16 .
20!
Hence we have a Monte Carlo algorithm with a small probability of failure.
If we want a Las Vegas algorithm – that is, one that always gives a correct construc-
tion – then we need a third ingredient. We require a polynomial time procedure for
verifying that a sample object satisfies the requirements; then we can test samples until
we find one that does so. An upper bound on the expected time for this construction
can be found by multiplying together the expected number of samples 1/p by the sum
of an upper bound on the time to generate each sample and an upper bound on the time
to check each sample.1 For the coloring problem, there is a polynomial time verifica-
tion algorithm when k is a constant: simply check all nk cliques and make sure they
are not monochromatic. It does not seem that this approach can be extended to yield
polynomial time algorithms when k grows with n.
As we have seen, in order to prove that an object with certain properties exists, we
can design a probability space from which an element chosen at random yields an
object with the desired properties with positive probability. A similar and sometimes
easier approach for proving that such an object exists is to use an averaging argument.
The intuition behind this approach is that, in a discrete probability space, a random
variable must with positive probability assume at least one value that is no greater
than its expectation and at least one value that is not smaller than its expectation.
1 Sometimes the time to generate or check a sample may itself be a random variable. In this case, Wald’s equation
(discussed in Chapter 13) may apply.
137
the probabilistic method
For example, if the expected value of a raffle ticket is $3, then there must be at least
one ticket that ends up being worth no more than $3 and at least one that ends up being
worth no less than $3.
More formally, we have the following lemma.
Lemma 6.2: Suppose we have a probability space S and a random variable X defined
on S such that E[X] = μ. Then Pr(X ≥ μ) > 0 and Pr(X ≤ μ) > 0.
Proof: We have
μ = E[X] = x Pr(X = x),
x
where the summation ranges over all values in the range of X. If Pr(X ≥ μ) = 0, then
μ= x Pr(X = x) = x Pr(X = x) < μ Pr(X = x) = μ,
x x<μ x<μ
Thus, there must be at least one instance in the sample space of S for which the value
of X is at least μ and at least one instance for which the value of X is no greater than μ.
Let C(A, B) be a random variable denoting the value of the cut corresponding to the
sets A and B. Then
m
m
1 m
E[C(A, B)] = E Xi = E[Xi ] = m · = .
i=1 i=1
2 2
Since the expectation of the random variable C(A, B) is m/2, there exists a partition A
and B with at least m/2 edges connecting the set A to the set B.
We can transform this argument into an efficient algorithm for finding a cut with value
at least m/2. We first show how to obtain a Las Vegas algorithm. In Section 6.3, we
show how to construct a deterministic polynomial time algorithm.
It is easy to randomly choose a partition as described in the proof. The expectation
argument does not give a lower bound on the probability that a random partition has a
cut of value at least m/2. To derive such a bound, let
m
p = Pr C(A, B) ≥ ,
2
and observe that C(A, B) ≤ m. Then
m
= E[C(A, B)]
2
= i Pr(C(A, B) = i) + i Pr(C(A, B) = i)
i<m/2 i≥m/2
m
≤ (1 − p) − 1 + pm,
2
which implies that
1
p≥ .
m/2 + 1
The expected number of samples before finding a cut with value at least m/2 is therefore
just m/2 + 1. Testing to see if the value of the cut determined by the sample is at least
m/2 can be done in polynomial time simply by counting the edges crossing the cut. We
therefore have a Las Vegas algorithm for finding the cut.
clauses.
Proof: Assign values independently and uniformly at random to the variables. The
probability that the ith clause with ki literals is satisfied is at least (1 − 2−ki ). The
expected number of satisfied clauses is therefore at least
m
(1 − 2−ki ) ≥ m(1 − 2−k ),
i=1
and there must be an assignment that satisfies at least that many clauses.
The foregoing argument can also be easily transformed into an efficient randomized
algorithm; the case where all ki = k is left as Exercise 6.1.
The probabilistic method can yield insight into how to construct deterministic algo-
rithms. As an example, we apply the method of conditional expectations in order to
derandomize the algorithm of Section 6.2.1 for finding a large cut.
Recall that we find a partition of the n vertices V of a graph into sets A and B by
placing each vertex independently and uniformly at random in one of the two sets. This
gives a cut with expected value E[C(A, B)] ≥ m/2. Now imagine placing the vertices
deterministically, one at a time, in an arbitrary order v1 , v2 , . . . , vn . Let xi be the set
where vi is placed (so xi is either A or B). Suppose that we have placed the first k
vertices, and consider the expected value of the cut if the remaining vertices are then
placed independently and uniformly into one of the two sets. We write this quantity
as E[C(A, B) | x1 , x2 , . . . , xk ]; it is the conditional expectation of the value of the cut
given the locations x1 , x2 , . . . , xk of the first k vertices. We show inductively how to
place the next vertex so that
E[C(A, B) | x1 , x2 , . . . , xk ] ≤ E[C(A, B) | x1 , x2 , . . . , xk+1 ].
140
6.3 derandomization using conditional expectations
It follows that
E[C(A, B)] ≤ E[C(A, B) | x1 , x2 , . . . , xn ].
The right-hand side is the value of the cut determined by our placement algorithm,
since if x1 , x2 , . . . , xn are all determined then we have a cut of the graph. Hence our
algorithm returns a cut whose value is at least E[C(A, B)] ≥ m/2.
The base case in the induction is
E[C(A, B) | x1 ] = E[C(A, B)],
which holds by symmetry because it does not matter where we place the first vertex.
We now prove the inductive step, that
E[C(A, B) | x1 , x2 , . . . , xk ] ≤ E[C(A, B) | x1 , x2 , . . . , xk+1 ]. (6.1)
Consider placing vk+1 randomly, so that it is placed in A or B with probability 1/2 each,
and let Yk+1 be a random variable representing the set where it is placed. Then
1
E[C(A, B) | x1 , x2 , . . . , xk ] = E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = A]
2
1
+ E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = B].
2
It follows that
max E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = A], E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = B]
≥ E[C(A, B) | x1 , x2 , . . . , xk ].
Therefore, all we have to do is compute the two quantities E[C(A, B) | x1 , x2 , . . . ,
xk , Yk+1 = A] and E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = B] and then place the vk+1 in the
set that yields the larger expectation. Once we do this, we will have a placement satis-
fying
E[C(A, B) | x1 , x2 , . . . , xk ] ≤ E[C(A, B) | x1 , x2 , . . . , xk+1 ].
To compute E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = A], note that the conditioning gives
the placement of the first k + 1 vertices. We can therefore compute the number of edges
among these vertices that contribute to the value of the cut. For all other edges, the
probability that it will later contribute to the cut is 1/2, since this is the probability
its two endpoints end up on different sides of the cut. By linearity of expectations,
E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 = A] is the number of edges crossing the cut whose
endpoints are both among the first k + 1 vertices, plus half of the remaining edges. This
is easy to compute in linear time. The same is true for E[C(A, B) | x1 , x2 , . . . , xk , Yk+1 =
B].
In fact, from this argument, we see that the larger of the two quantities is determined
just by whether vk+1 has more neighbors in A or in B. All edges that do not have vk+1
as an endpoint contribute the same amount to the two expectations. Our derandomized
algorithm therefore has the following simple form: Take the vertices in some order.
Place the first vertex arbitrarily in A. Place each successive vertex to maximize the
number of edges crossing the cut. Equivalently, place each vertex on the side with
141
the probabilistic method
fewer neighbors, breaking ties arbitrarily. This is a simple greedy algorithm, and our
analysis shows that it always guarantees a cut with at least m/2 edges.
Thus far we have used the probabilistic method to construct random structures with the
desired properties directly. In some cases it is easier to work indirectly, breaking the
argument into two stages. In the first stage we construct a random structure that does not
have the required properties. In the second stage we then modify the random structure
so that it does have the required property. We give two examples of this sample-and-
modify technique.
Theorem 6.5: Let G = (V, E ) be a connected graph on n vertices with m ≥ n/2 edges.
Then G has an independent set with at least n2 /4m vertices.
Proof: Let d = 2m/n ≥ 1 be the average degree of the vertices in G. Consider the
following randomized algorithm.
1. Delete each vertex of G (together with its incident edges) independently with prob-
ability 1 − 1/d.
2. For each remaining edge, remove it and one of its adjacent vertices.
The remaining vertices form an independent set, since all edges have been removed.
This is an example of the sample-and-modify technique. We first sample the vertices,
and then we modify the remaining graph.
Let X be the number of vertices that survive the first step of the algorithm. Since
the graph has n vertices and since each vertex survives with probability 1/d, it follows
that
n
E[X] = .
d
Let Y be the number of edges that survive the first step. There are nd/2 edges in
the graph, and an edge survives if and only if its two adjacent vertices survive.
Thus
nd 1 2 n
E[Y ] = = .
2 d 2d
The second step of the algorithm removes all the remaining edges and at most Y
vertices. When the algorithm terminates, it outputs an independent set of size at least
142
6.5 the second moment method
X − Y , and
n n n
E[X − Y ] =− = .
d 2d 2d
The expected size of the independent set generated by the algorithm is at least n/2d,
so the graph has an independent set with at least n/2d = n2 /4m vertices.
We modify the original randomly chosen graph G by eliminating one edge from each
cycle of length up to k − 1. The modified graph therefore has girth at least k. When n
is sufficiently large, the expected number of edges in the resulting graph is
1 1 1/k+1 1
E[X − Y ] ≥ 1− n − kn(k−1)/k ≥ n1/k+1 .
2 n 4
Hence there exists a graph with at least 14 n1+1/k edges and girth at least k.
The second moment method is another useful way to apply the probabilistic method.
The standard approach typically makes use of the following inequality, which is easily
derived from Chebyshev’s inequality.
Theorem 6.7: If X is an integer-valued random variable, then
Var[X]
Pr(X = 0) ≤ . (6.2)
(E[X])2
143
the probabilistic method
Proof:
Var[X]
Pr(X = 0) ≤ Pr(|X − E[X]| ≥ E[X]) ≤ .
(E[X])2
so that
n
E[X] = p6 .
4
In this case E[X] = o(1), which means that E[X] < ε for sufficiently large n. Since X is
a nonnegative integer-valued random variable, it follows that Pr(X ≥ 1) ≤ E[X] < ε.
Hence, the probability that a random graph chosen from Gn,p has a clique of four or
more vertices is less than ε.
We now consider the case when p = f (n) and f (n) = ω(n−2/3 ). In this case,
E[X] → ∞ as n grows large. This in itself is not sufficient to conclude that, with high
probability, a graph chosen random from Gn,p has a clique of at least four vertices. We
can, however, use Theorem 6.7 to prove that Pr(X = 0) = o(1) in this case. To do so
we must show that Var[X] = o((E[X])2 ). Here we shall bound the variance directly;
an alternative approach is given as Exercise 6.12.
We begin with the following useful formula.
Lemma 6.9: Let Yi , i = 1, . . . , m, be 0–1 random variables, and let Y = mi=1 Yi . Then
Var[Y ] ≤ E[Y ] + Cov(Yi , Y j ).
1≤i, j≤m;i= j
144
6.6 the conditional expectation inequality
We wish to compute
⎡ n ⎤
(4 )
Var[X] = Var ⎣ Xi ⎦ .
i=1
Applying Lemma 6.9, we see that we need to consider the covariance of the Xi . If
|Ci ∩ C j | = 0 then the corresponding cliques are disjoint, and it follows that Xi and X j
are independent. Hence, in this case, E[Xi X j ] − E[Xi ]E[X j ] = 0. The same is true if
|Ci ∩ C j | = 1.
If |Ci ∩ C j | = 2, then the corresponding cliques share one edge. For both cliques to
be in the graph, the eleven corresponding edges must appear n in the graph. Hence, in
this case E[Xi X j ] − E[Xi ]E[X j ] ≤ E[Xi X j ] ≤ p . There are 6 ways to choose the six
11
6
vertices and 2;2;2 ways to split them into Ci and C j (because we choose two vertices
for Ci ∩ C j , two for Ci alone, and two for C j alone).
If |Ci ∩ C j | = 3, then the corresponding cliques share three edges. For both cliques
to be in the graph, the nine corresponding edges must appear in the graph. Hence, in
this case E[XiX j ] − E[Xi ]E[X j ] ≤ E[Xi X j ] ≤ p9 . There are n5 ways to choose the five
5
vertices, and 3;1;1 ways to split them
into Ci and C j .
Finally, recall again that E[X] = n4 p6 and p = f (n) = ω(n−2/3 ). Therefore,
n n 6 n 5
Var[X] ≤ p+
6
p +
11
p9 = o(n8 p12 ) = o((E[X])2 ),
4 6 2; 2; 2 5 3; 1; 1
since
2
n
(E[X]) =
2
p6 = (n8 p12 ).
4
Theorem 6.7 now applies, showing that Pr(X = 0) = o(1) and thus the second part of
the theorem.
For a sum of Bernoulli random variables, we can derive an alternative to the second
moment method that is often easier to apply.
145
the probabilistic method
n
Theorem 6.10: Let X = i=1 Xi , where each Xi is a 0–1 random variable. Then
n
Pr(Xi = 1)
Pr(X > 0) ≥ . (6.3)
i=1
E[X | Xi = 1]
Notice that the Xi need not be independent for Eqn. (6.3) to hold.
Proof: Let Y = 1/X if X > 0, with Y = 0 otherwise. Then
Pr(X > 0) = E[XY ].
However,
n
E[XY ] = E XiY
i=1
n
= E[XiY ]
i=1
n
= E[XiY | Xi = 1] Pr(Xi = 1) + E[XiY | Xi = 0] Pr(Xi = 0)
i=1
n
= E[Y | Xi = 1] Pr(Xi = 1)
i=1
n
= E[1/X | Xi = 1] Pr(Xi = 1)
i=1
n
Pr(Xi = 1)
≥ .
i=1
E[X | Xi = 1]
The key step is from the third to the fourth line, where we use conditional expectations
in a fruitful way by taking advantage of the fact that E[XiY | Xi = 0] = 0. The last line
makes use of Jensen’s inequality, with the convex function f (x) = 1/x.
We can use Theorem 6.10 to give an alternate proof of Theorem 6.8. Specifically, if
p = f (n) = ω(n−2/3 ), we use Theorem 6.10 to show that, for any constant ε > 0 and
for sufficiently large n, the probability that a random graph chosen from Gn,p does not
have a clique with four or more vertices is less than ε.
(n4 )
As in the proof of Theorem 6.8, let X = i=1 Xi , where Xi is 1 if the subset of four
vertices Ci is a 4-clique and 0 otherwise. For a specific X j , we have Pr(X j = 1) = p6 .
Using the linearity of expectations, we compute
⎡ n ⎤
(4 ) (n4 )
E[X | X j = 1] = E ⎣ Xi X j = 1⎦ = E[Xi | X j = 1].
i=1 i=1
(n4 )
E[X | X j = 1] = E[Xi | X j = 1]
i=1
n−4 n−4 n−4 n−4
=1+ p +46
p +6
6
p +4
5
p3 .
4 3 2 1
One of the most elegant and useful tools in applying the probabilistic method is the
Lovász Local Lemma. Let E1 , . . . , En be a set of bad events in some probability space.
We want to show that there is an element in the sample space that is not included in
any of the bad events.
This would be easy to do if the events were mutually independent. Recall
that events E1 , E2 , . . . , En are mutually independent if and only if, for any subset
I ⊆ [1, n],
Pr Ei = Pr(Ei ).
i∈I i∈I
Also, if E1 , . . . , En are mutually independent then so are Ē1 , . . . , Ēn . (This was left as
Exercise 1.20.) If Pr(Ei ) < 1 for all i, then
n
n
Pr Ēi = Pr(Ēi ) > 0,
i=1 i=1
and there is an element of the sample space that is not included in any bad event.
Mutual independence is too much to ask for in many arguments. The Lovász local
lemma generalizes the preceding argument to the case where the n events are not mutu-
ally independent but the dependency is limited. Specifically, following from the defi-
nition of mutual independence, we say that an event En+1 is mutually independent of
147
the probabilistic method
Pr ⎝En+1 E j ⎠ = Pr(En+1 ).
j∈I
Pr Ēi > 0.
i=1
Pr ⎝Ek Ē j ⎠ ≤ 2p.
j∈S
For this expression to be well-defined when S is not empty, we need Pr j∈S Ē j > 0.
The base case s = 0 follows from the assumption
that Pr(Ek ) ≤ p. To perform the
inductive step, we first show that Pr Ē
j∈S j > 0. This is true when s = 1, because
Pr(Ē j ) ≥ 1 − p > 0. For s > 1, without loss of generality let S = {1, 2, . . . , s}. Then
s ⎛ ⎞
s
i−1
Pr Ēi = Pr ⎝Ēi Ē j ⎠
i=1 i=1 j=1
⎛ ⎛ ⎞⎞
s
i−1
= ⎝1 − Pr ⎝Ei Ē j ⎠⎠
i=1 j=1
s
≥ (1 − 2p) > 0.
i=1
Pr ⎝Ek Ē j ⎠ = Pr(Ek ) ≤ p.
j∈S
We continue with the case |S2 | < s. It will be helpful to introduce the following nota-
tion. Let FS be defined by
FS = Ē j ,
j∈S
and similarly define FS1 and FS2 . Notice that FS = FS1 ∩ FS2 .
Applying the definition of conditional probability yields
Pr(Ek ∩ FS )
Pr(Ek | FS ) = . (6.4)
Pr(FS )
Canceling the common factor, which we have already shown to be nonzero, yields
149
the probabilistic method
Using also the fact that |S1 | ≤ d, we establish a lower bound on the denominator of
Eqn. (6.5) as follows:
⎛ ⎞
≥ 1− Pr ⎝Ei Ē j ⎠
i∈S1 j∈S2
≥ 1− 2p
i∈S1
≥ 1 − 2pd
1
≥ .
2
Using the upper bound for the numerator and the lower bound for the denominator,
we prove the induction:
Pr(Ek ∩ FS1 | FS2 )
Pr(Ek | FS ) =
Pr(FS1 | FS2 )
p
≤ = 2p.
1/2
The theorem follows from
n ⎛ ⎞
n
i−1
Pr Ēi = Pr ⎝Ēi Ē j ⎠
i=1 i=1 j=1
⎛ ⎛ ⎞⎞
n
i−1
= ⎝1 − Pr ⎝Ei Ē j ⎠⎠
i=1 j=1
n
≥ (1 − 2p) > 0.
i=1
event that the paths chosen by pairs i and j share at least one edge. Since a path in Fi
shares edges with no more than k paths in Fj ,
k
p = Pr(Ei, j ) ≤ .
m
Let d be the degree of the dependency graph. Since event Ei, j is independent of all
events Ei , j when i ∈
/ {i, j} and j ∈
/ {i, j}, we have d < 2n. Since
8nk
4dp < ≤ 1,
m
all of the conditions of the Lovász Local Lemma are satisfied, proving
⎛ ⎞
Pr ⎝ Ēi, j ⎠ > 0.
i= j
Hence, there is a choice of paths such that the n paths are edge disjoint.
Pr Ēi > 0;
i=1
151
the probabilistic method
The Lovász Local Lemma proves that a random element in an appropriately defined
sample space has a nonzero probability of satisfying our requirement. However, this
probability might be too small for an algorithm that is based on simple sampling. The
number of objects that we need to sample before we find an element that satisfies our
requirements might be exponential in the problem size.
In a number of interesting applications, the existential result of the Lovász Local
Lemma can be used to derive efficient construction algorithms. Although the details
differ in the specific applications, many known algorithms are based on a common two-
phase scheme. In the first phase, a subset of the variables of the problem are assigned
random values; the remaining variables are deferred to the second stage. The subset of
variables that are assigned values in the first stage is chosen so that:
1. using the Local Lemma, one can show that the random partial solution fixed in the
first phase can be extended to a full solution of the problem without modifying any
of the variables fixed in the first phase; and
2. the dependency graph H between events defined by the variables deferred to the
second phase has, with high probability, only small connected components.
When the dependency graph consists of connected components, a solution for the
variables of one component can be found independently of the other components. Thus,
the first phase of the two-phase algorithm breaks the original problem into smaller
subproblems. Each of the smaller subproblems can then be solved independently in the
second phase by an exhaustive search.
152
∗
6.8 explicit constructions using the local lemma
subformula will have no more than O(k log m) deferred variables. An exhaustive search
of all the possible assignments for all variables in each subformula can then be done in
polynomial time. Hence we focus on the following lemma.
Lemma 6.15: All connected components in H are of size O(log m) with probability
1 − o(1).
Proof: Consider a connected component R of r vertices in H. If R is a connected com-
ponent in H , then all its r nodes are surviving clauses. A surviving clause is either
a dangerous clause or it shares at least one deferred variable with a dangerous clause
(i.e., it has a neighbor in H that is a dangerous clause). The probability that a given
clause is dangerous is at most 2−k/2 , since exactly k/2 of its variables were given ran-
dom values in phase I yet none of these values satisfied the clause. The probability that
a given clause survives is the probability that either this clause or at least one of its
direct neighbors is dangerous, which is bounded by
(d + 1)2−k/2 ,
where again d = kT > 1.
If the survival of individual clauses were independent events then we would be in
excellent shape. However, from our description here it is evident that such events are
not independent. Instead, we identify a subset of the vertices in R such that the survival
of the clauses represented by the vertices of this subset are independent events. A 4-tree
S of a connected component R in H is defined as follows:
1. S is a rooted tree;
2. any two nodes in S are at distance at least 4 in H;
3. there can be an edge in S only between two nodes with distance exactly 4 between
them in H;
4. any node of R is either in S or is at distance 3 or less from a node in S.
Considering the nodes in a 4-tree proves useful because the event that a node u in
a 4-tree survives and the event that another node v in a 4-tree survives are actually
independent. Any clause that could cause u to survive has distance at least 2 from
any clause that could cause v to survive. Clauses at distance 2 share no variables, and
hence the events that they are dangerous are independent. We can take advantage of
this independence to conclude that, for any 4-tree S, the probability that the nodes in
the 4-tree survive is at most
((d + 1)2−k/2 )|S| .
A maximal 4-tree S of a connected component R is the 4-tree with the largest possible
number of vertices. Since the degree of the dependency graph is bounded by d, there
are no more than
d + d(d − 1) + d(d − 1)(d − 1) ≤ d 3 − 1
nodes at distance 3 or less from any given vertex. We therefore claim that a maximal
4-tree of R must have at least r/d 3 vertices. Otherwise, when we consider the vertices
of the maximal 4-tree S and all neighbors within distance 3 or less of these vertices,
we obtain fewer than r vertices. Hence there must be a vertex of distance at least 4
154
6.9 lovász local lemma: the general case
from all vertices in S. If this vertex has distance exactly 4 from some vertex in S, then
it can be added to S and thus S is not maximal, yielding a contradiction. If its dis-
tance is larger than 4 from all vertices in S, consider any path that brings it closer to S;
such a path must eventually pass through a vertex of distance at least 4 from all ver-
tices in S and of distance 4 from some vertex in S, again contradicting the maximality
of S.
To show that with probability 1 − o(1) there is no connected component R of size
r ≥ c log2 m for some constant c in H , we show that there is no 4-tree of H of size
r/d 3 that survives with probability 1 − o(1). Since a surviving connected component
R would have a maximal 4-tree of size r/d 3 , the absence of such a 4-tree implies the
absence of such a component.
We need to count the number of 4-trees of size s = r/d 3 in H. We can choose the
root of the 4-tree in m ways. A tree with root v is uniquely defined by an Eulerian tour
that starts and ends at v and traverses each edge of the tree twice, once in each direction.
Since an edge of S represents a path of length 4 in H, at each vertex in the 4-tree the
Eulerian path can continue in as many as d 4 different ways, and therefore the number
of 4-trees of size s = r/d 3 in H is bounded by
3
m(d 4 )2s = md 8r/d .
The probability that the nodes of each such 4-tree survive in H is at most
((d + 1)2−k/2 )s = ((d + 1)2−k/2 )r/d .
3
For completeness we include the statement and proof of the general case of the Lovász
Local Lemma.
155
the probabilistic method
Then
n
n
Pr Ēi ≥ (1 − xi ).
i=1 i=1
Pr ⎝Ek Ē j ⎠ ≤ xk .
j∈S
As in the case of the symmetric version of the Local Lemma, we must be careful that
the conditional probability is well-defined. This follows using the same approach as in
the symmetric case, so we focus on the rest of the induction.
The base case s = 0 follows from the assumption that
Pr(Ek ) ≤ xk (1 − x j ) ≤ xk .
(k, j)∈E
Pr ⎝Ek Ē j ⎠ = Pr(Ek ) ≤ xk .
j∈S
We continue with the case |S2 | < s. We again use the notation
FS = Ē j
j∈S
Pr(FS1 | FS2 ) = Pr ⎝ Ē j Ē j ⎠
j∈S1 j∈S2
⎛ ⎛ i−1 ⎛ ⎞⎞⎞
r
= ⎝1 − Pr ⎝E ji Ē jt ∩ ⎝ Ē j ⎠⎠⎠
i=1 t=1 j∈S2
r
≥ (1 − x ji )
i=1
≥ (1 − x j ).
(k, j)∈E
Using the upper bound for the numerator and the lower bound for the denominator,
we can prove the induction hypothesis:
⎛ ⎞
Pr ⎝Ek Ē j ⎠ = Pr(Ek | FS )
j∈S
157
the probabilistic method
Recently, there have been several advances in extending the Lovász Local Lemma. We
briefly summarize the key points here, and start by looking again to the k-SAT problem
to provide an example of these ideas in action.
We have shown previously that if no variable in a k-SAT formula appears in more
than 2k /(4k) clauses, then the formula has a satisfying assignment, and we have shown
that if each variable appears in no more that 2αk clauses for some constant α a solution
can be found in expected polynomial time. Here we provide an improved result which
again provides a solution in expected polynomial time.
Theorem 6.18: Suppose that every clause in a k-SAT formula shares one or more
variables with at most 2k−3 − 1 other clauses. Then a solution for the formula exists
and can be found in expected time that is polynomial in the number of clauses m.
Before starting the proof, we informally describe our algorithm. As before, let
x1 , x2 , . . . , x be the variables and C1 , C2 , . . . , Cm be the m clauses in the formula.
We begin by choosing a random truth assignment (uniformly at random). We then look
for a clause Ci that is unsatisfied; if no such clause exists we are done. If such a clause
exists, we look specifically at the variables in the clause, and randomly choose a new
truth assignment for those variables. Doing so will hopefully “fix” the clause Ci so that
it is satisfied, but it may not; even worse, it may end up causing a clause C j that shares
a variable with Ci to become unsatisfied. We recursively fix these neighboring clauses,
so that when the recursion is finished, we have that Ci is satisfied and we have not
damaged any clause by making it become unsatisfied. We therefore have improved the
situation by satisfying at least one previously unsatisfied clause. We then continue to
the next unsatisfied clause; we have to do this at most m times.
The underlying question that we need to answer to show that this algorithm works
is how we know that the recursion we have described stops successfully. Perhaps it
simply goes on forever, or for an exponential amount of time. The proof we provide
shows that this cannot be the case through a new type of argument. Specifically, we
show that if such bad recursions occur with non-trivial probability, then one could
compress a random string of n independent, unbiased flips into much fewer than n bits.
That should seem impossible, and it is. While compression is a theme we cover in much
more detail in Chapter 10, we explain the compression result we need here in the proof
of the theorem. All we need is that a string of r random bits, where each bit is chosen
independently and uniformly at random, cannot be compressed so that the average
length of the representation over all choices of the r random bits is less than r − 2.
To see that this must be true, assume the best possible setting for us, where we don’t
have to worry about the “end” of our compressed sequence, but can use each string of
bits of length less than r to represent one of the 2r possible strings we aim to compress.
That is, we won’t worry that one compressed string might be “0” and another one
might be “00”, in which case it might be hard to distinguish whether “00” was meant
to represent a single compressed string, or two copies of the string represented by “0”.
(Essentially, a compressed string can be terminated for free; this allowance can only
158
∗
6.10 the algorithmic lovász local lemma
hurt us in our argument.) Still, each string of s < r bits can only represent a single
possible string of length r. Hence we have available one string of length 0 (the empty
string), two strings of length 1, and so on. There are only 2r − 1 strings of length less
than r; even if we count only those in computing the average length of the compressed
string, which again can only hurt us, the average length would be at least
r−1
1
r−i
· i ≥ r − 2.
i=1
2
The same compression fact naturally holds true for any collection of 2r equally likely
strings; they do not have to be limited to strings of r random bits.
Given this fact, our proof proceeds as follows.
We note the algorithm produces a history, which we use in the analysis of the algo-
rithm.
It is important to realize that while a clause can become satisfied and unsatisfied
again multiple times through the recursive process, when we return to the main routine
and complete the call to localcorrect, we have satisfied the clause Ci that localcorrect
was called on from the main routine, and further any clause that was previously satisfied
has stayed satisfied because of the recursion. What we wish to show is that the recursive
process has to stop.
159
the probabilistic method
Our analysis makes use of the fact that our algorithm makes use of a random string.
We provide two different ways to describe how our algorithm runs.
We can think of our algorithm as being described by the random string of bits it uses.
It takes n bits to initially assign random truth values to each of the variables. After that,
it takes k bits to resample values for a clause each time localcorrect is called. Let us refer
to each time localcorrect is called as a round. Then one way to describe our algorithm’s
actions for j rounds is with the random string of n + jk bits used by the algorithm.
But here is another way of describing how our algorithm works. We keep track of the
“history” of the algorithm as shown in the algorithm. The history includes a list of the
clauses that localcorrect is called on by the main routine. The history also includes a list
of the recursive calls to localcorrect, in a slightly non-obvious way. First, we note that
the algorithm uses a flag bit 0 and a flag bit 1 to mark the start and end of recursive calls,
so the algorithm tracks the stack of recursive calls in a natural way. Second, instead of
the natural approach of using log2 m bits to represent the index of the clause in our
recursive calls, the algorithm uses only k − 3 bits. We now explain why only k − 3 bits
are needed. Since there are at most 2k−3 possible clauses that share a variable with the
current clause (including the current clause itself) that could be the next one called, the
clause can be represented by an index of k − 3 bits. (Imagine having an ordered list of
the up to 2k−3 clauses that share a variable with each clause; we just need the index into
that list.) Finally, our history will also include the current truth assignment of n bits.
Note that the current truth assignment can be thought of as in an separate updatable
storage area for the history; every time the truth assignment is updated, so is this part
of the history.
We now show that when the algorithm has run j rounds, we can recover the random
string of n + jk bits that the algorithm has used from the history we have described.
Start with the current truth assignment, and break the history up, using the flags that
mark invocations of localcorrect. We can use the history to determine the sequence of
recursive calls, and what clauses localcorrect was called on. Then, going backwards
through the history, we know at each step which clause was being resampled. For that
clause to have to be resampled, it must have been unsatisfied previously. But there is
only one setting of the variables that makes a clause unsatisfied, and hence we know
what the truth values for those variables were before the clause was resampled. We
can therefore update the current truth assignment so that it represents the truth assign-
ment before the resampling, and continue backwards through the process. Repeating
this action, we can determine the original truth assignment, and since at each step we
can determine what variable values were changed and what their values were on each
resampling, we recover the whole string of n + jk random bits.
Our history takes at most n + mlog2 m + j(k − 1) bits; here we use the fact that
each resampling uses at most k − 1 bits, including the two bits that may be necessary as
flags for the start and end of the recursion given by that resampling. For large enough j,
our history yields a compressed form of the the random string used to run the algorithm,
since only k − 1 bits are used to represent each resampling in the history instead of the
k bits used by the algorithm.
Now suppose there were no truth assignment, in which case the algorithm would
run forever. Then after a large enough number of rounds J, the history will be at most
160
∗
6.10 the algorithmic lovász local lemma
n + mlog2 m + J(k − 1) bits, while the random string running the algorithm would
be n + Jk bits. By our result on compressing random strings, we must have
n + mlog2 m + J(k − 1) ≥ n + Jk − 2.
Hence
J ≤ mlog2 m + 2.
This contradicts that the algorithm can run forever, so there must be a truth assignment.
Similarly, the number of rounds J is more than mlog2 m + 2 + i with probability
at most 2−i . To see this, suppose the probability of lasting to this round is greater than
2−i . Again consider the algorithm after J = mlog2 m + 2 + i rounds, so the history
will be at most n + mlog2 m + J(k − 1) bits. The algorithm can also be described
by the n + Jk random bits that led to the current state. As there are at least 2n+Jk ran-
dom bit strings of this length, and the probability of lasting at least this many rounds
is greater than 2−i by assumption, there are at least 2n+Jk−i random bit strings associ-
ated with reaching this round. By our result on compressing random strings, it requires
more than n + Jk − i − 2 bits on average to represent the at least 2n+Jk−i random bit
strings associated with reaching this round. But the history, as we have already argued,
provides a representation of these random bit strings, in that we can reconstruct the
algorithm’s random bit string from the history. The number of bits the history uses is
only
n + mlog2 m + J(k − 1) = n + Jk − i − 2,
a contradiction.
Since the probability of lasting more than mlog2 m + 2 + i is at most 2−i , we can
bound the expected number of rounds by
∞
mlog2 m + 2 + i2−i .
i=1
The expected number rounds used by the algorithm is thus at most mlog2 m + 4.
The work done in each resampling round can easily be made to be polynomial in
m, so the total expected time to find an assigment can be made polynomial in m as
well.
While already surprising, the proof above can be improved slightly. A more careful
encoding shows that the expected number of rounds required can be reduced to O(m)
instead of O(m log m). This is covered in the Exercise 6.21.
The algorithmic approach we have used for the satisfiability problem in the proof of
Theorem 6.18 can be extended further to obtain an algorithmic version of the Lovász
local lemma, which we now describe. Let us suppose that we have a collection of n
events E1 , E2 , . . . , En that depend on a collection of mutually independent variables
y1 , y2 , . . . , y . The dependency graph on events has an edge between two events if they
both depend on at least one shared variable yi . The idea is that at each step if there
is an event that is unsatisfied, we resample only the random variables on which that
event depends. As with the k-Satisfiability Algorithm using the algorithmic Lovász
161
the probabilistic method
Local Lemma, this resampling process has to be ordered carefully to ensure progress.
If the dependencies are not too great, then the right resampling algorithm terminates
with a solution.
The symmetric version is easier to state.
Theorem 6.19: Let E1 , E2 , . . . , En be a set of events in an arbitrary probability space
that are determined by mutually independent random variables y1 , y2 , . . . , y , and let
G = (V, E ) be the dependency graph for these events. Suppose the following conditions
hold for values d and p:
1. each event Ei is adjacent to at most d other events in the dependency graph, or
equivalently, there are only d other events that also depend on one or more of the
y j that Ei depends on;
2. Pr(Ei ) ≤ p;
3. ep(d + 1) ≤ 1.
Then there exists an assignment of the yi so that the event ∩ni=1 Ēi holds, and a resam-
pling algorithm with the property that the expected number of times the algorithm
resamples the event Ei in finding such an assignment is at most 1/d. Hence the expected
total number of resampling steps taken by the algorithm is at most n/d.
However, we also have a corresponding theorem for the asymmetric version.
Theorem 6.20: Let E1 , E2 , . . . , En be a set of events in an arbitrary probability
space that are determined by mutually independent random variables y1 , y2 , . . . , y ,
and let G = (V, E ) be the dependency graph for these events. Assume there exist
x1 , x2 , . . . , xn ∈ [0, 1] such that, for all 1 ≤ i ≤ n
Pr(Ei ) ≤ xi (1 − x j ).
(i, j)∈E
Then there exists an assignment of the yi so that the event ∩ni=1 Ēi holds, and a resam-
pling algorithm with the property that the expected number of times the algorithm
resamples the event Ei in finding such an assignment is at most xi /(1 − xi ). Hence
the
n expected total number of resampling steps taken by the algorithm is at most
i=1 xi /(1 − xi ).
The proofs of these theorems are beyond the scope of the book. Similar to the algo-
rithm for satisfiability based on resampling given above, the proof relies on bounding
the expected number of resamplings that occur over the course of the algorithm.
6.11. Exercises
Exercise 6.1: Consider an instance of SAT with m clauses, where every clause has
exactly k literals.
(a) Give a Las Vegas algorithm that finds an assignment satisfying at least m(1 − 2−k )
clauses, and analyze its expected running time.
162
6.11 exercises
(b) Give a derandomization of the randomized algorithm using the method of condi-
tional expectations.
Exercise 6.2:
(a) Prove that, for every integer n, there exists a coloring of the edges of the complete
graph Kn by
two colors so that the total number of monochromatic copies of K4 is
at most n4 2−5 .
(b) Give a randomized algorithm for finding a coloring with at most n4 2−5 mono-
chromatic copies of K4 that runs in expected time polynomial in n.
(c) Show how to construct such a coloring deterministically in polynomial time using
the method of conditional expectations.
Exercise 6.3: Given an n-vertex undirected graph G = (V, E ), consider the following
method of generating an independent set. Given a permutation σ of the vertices, define
a subset S(σ ) of the vertices as follows: for each vertex i, i ∈ S(σ ) if and only if no
neighbor j of i precedes i in the permutation σ .
(a) Show that each S(σ ) is an independent set in G.
(b) Suggest a natural randomized algorithm to produce σ for which you can show that
the expected cardinality of S(σ ) is
n
1
,
i=1
di + 1
where di denotes the degree of vertex i.
(c) Prove that G has an independent set of size at least ni=1 1/(di + 1).
Exercise 6.4: Consider the following two-player game. The game begins with k tokens
placed at the number 0 on the integer number line spanning [0, n]. Each round, one
player, called the chooser, selects two disjoint and nonempty sets of tokens A and B.
(The sets A and B need not cover all the remaining tokens; they only need to be disjoint.)
The second player, called the remover, takes all the tokens from one of the sets off the
board. The tokens from the other set all move up one space on the number line from
their current position. The chooser wins if any token ever reaches n. The remover wins
if the chooser finishes with one token that has not reached n.
(a) Give a winning strategy for the chooser when k ≥ 2n .
(b) Use the probabilistic method to show that there must exist a winning strategy for
the remover when k < 2n .
(c) Explain how to use the method of conditional expectations to derandomize the
winning strategy for the remover when k < 2n .
Exercise 6.5: We have shown using the probabilistic method that, if a graph G has n
nodes and m edges, then there exists a partition of the n nodes into sets A and B such
that at least m/2 edges cross the partition. Improve this result slightly: show that there
exists a partition such that at least mn/(2n − 1) edges cross the partition.
163
the probabilistic method
Exercise 6.6: We can generalize the problem of finding a large cut to finding a large
k-cut. A k-cut is a partition of the vertices into k disjoint sets, and the value of a cut is
the weight of all edges crossing from one of the k sets to another. In Section 6.2.1 we
considered 2-cuts when all edges had the same weight 1, showing via the probabilistic
method that any graph G with m edges has a cut with value at least m/2. Generalize
this argument to show that any graph G with m edges has a k-cut with value at least
(k − 1)m/k. Show how to use derandomization (following the argument of Section 6.3)
to give a deterministic algorithm for finding such a cut.
Exercise 6.7: A hypergraph H is a pair of sets (V, E ), where V is the set of vertices
and E is the set of hyperedges. Every hyperedge in E is a subset of V. In particular, an
r-uniform hypergraph is one where the size of each edge is r. For example, a 2-uniform
hypergraph is just a standard graph. A dominating set in a hypergraph H is a set of
vertices S ⊂ V such that e ∩ S = ∅ for every edge e ∈ E. That is, S hits every edge of
the hypergraph.
Let H = (V, E ) be an r-uniform hypergraph with n vertices and m edges. Show
that there is a dominating set of size at most np + (1 − p)r m for every real number
0 ≤ p ≤ 1. Also, show that there is a dominating set of size at most (m + n ln r)/r.
Exercise 6.8: Prove that, for every integer n, there exists a way to 2-color the edges
of Kx so that there is no monochromatic clique of size k when
n 1− 2k
x=n− 2 .
k
(Hint: Start by 2-coloring the edges of Kn , then fix things up.)
Exercise 6.9: A tournament is a graph on n vertices with exactly one directed edge
between each pair of vertices. If vertices represent players, then each edge can be
thought of as the result of a match between the two players: the edge points to the win-
ner. A ranking is an ordering of the n players from best to worst (ties are not allowed).
Given the outcome of a tournament, one might wish to determine a ranking of the play-
ers. A ranking is said to disagree with a directed edge from y to x if y is ahead of x in
the ranking (since x beat y in the tournament).
(a) Prove that, for every tournament, there exists a ranking that disagrees with at most
50% of the edges.
(b) Prove that, for sufficiently large n, there exists a tournament such that every ranking
disagrees with at least 49% of the edges in the tournament.
164
6.11 exercises
Exercise 6.11: Consider a graph in Gn,p with n vertices and each pair of vertices
independently connected by an edge with probability p. We prove a threshold for the
existence of triangles in the graph.
Let t1 , . . . , t(n ) be an enumeration of all triplets of three vertices in the graph. Let
3
Xi = 1 if the the three edges of the triplet ti appear in the graph, so that ti forms a triangle
(n3 )
in the graph. Otherwise Xi = 0. Let X = i=1 Xi .
(a) Compute E[X].
(b) Use (a) to show that if pn → 0 then Pr(X > 0) → 0.
(c) Show that Var[Xi ] ≤ p3 .
(d) Show that Cov(Xi , X j ) = p5 − p6 for O(n4 ) pairs i = j, otherwise Cov(Xi , X j ) =
0.
(e) Show that Var[X] = O(n3 p3 + n4 (p5 − p6 )).
(f) Conclude that if p is such that pn → ∞ then Pr(X = 0) → 0.
Exercise 6.12: In Section 6.5.1, we bounded the variance of the number of 4-cliques
in a random graph in order to demonstrate the second moment method. Showhow to
calculate the variance directly by using the equality from Exercise 3.9: for X = n1=1 Xi
the sum of Bernoulli random variables,
n
E[X 2 ] = Pr(Xi = 1)E[X | Xi = 1].
i=1
Exercise 6.13: Consider the problem of whether graphs in Gn,p have cliques of con-
stant size k. Suggest an appropriate threshold function for this property. Generalize the
argument used for cliques of size 4, using either the second moment method or the
conditional expectation i