What is the stationary distribution of this process?

  2. 2.

What is the mean recurrence time $\mu_{n}$ for some state $n$?

  3. 3.

Use $\mu_{n}$ to get a tight asymptotic (i.e., big-$\Theta$) bound on
$\mu_{0,n}$, the expected time to reach $n$ starting from $0$.

##### Solution

  1. 1.

For $n>0$, we have $\pi_{n}=\frac{1}{2}\pi_{n-1}+\frac{3}{8}\pi_{n+1}$, with a
base case $\pi_{0}=\frac{1}{8}+\frac{3}{8}\pi_{0}+\frac{3}{8}\pi_{1}$.

The $\pi_{n}$ expression is a linear homogeneous recurrence, so its solution
consists of linear combinations of terms $b^{n}$, where $b$ satisfies
$1=\frac{1}{2}b^{-1}+\frac{3}{8}b$. The solutions to this equation are $b=2/3$
and $b=2$; we can exclude the $b=2$ case because it would make our
probabilities blow up for large $n$. So we can reasonably guess
$\pi_{n}=a(2/3)^{n}$ when $n>0$.

For $n=0$, substitute
$\pi_{0}=\frac{1}{8}+\frac{3}{8}\pi_{0}+\frac{3}{8}a(2/3)$ to get
$\pi_{0}=\frac{1}{5}+\frac{2}{5}a$. Now substitute

$\displaystyle\pi_{1}$ $\displaystyle=(2/3)a$
$\displaystyle=\frac{1}{2}\pi_{0}+\frac{3}{8}a(2/3)^{2}$
$\displaystyle=\frac{1}{2}\left(\frac{1}{5}+\frac{2}{5}a\right)+\frac{3}{8}a(2/3)^{2}$
$\displaystyle=\frac{1}{10}+\frac{11}{30}a,$

which we can solve to get $a=1/3$.

So our candidate $\pi$ is $\pi_{0}=1/3$, $\pi_{n}=(1/3)(2/3)^{n}$, and in fact
we can drop the special case for $\pi_{0}$.

As a check,
$\sum_{i=0}^{n}\pi_{n}=(1/3)\sum_{i=0}^{n}(2/3)^{n}=\frac{1/3}{1-2/3}=1$.

  2. 2.

Since $\mu_{n}=1/\pi_{n}$, we have $\mu_{n}=3(3/2)^{n}$.

  3. 3.

In general, let $\mu_{k,n}$ be the expected time to reach $n$ starting at $k$.
Then
$\mu_{n}=\mu_{n,n}=1+\frac{1}{8}\mu_{0,n}+\frac{1}{2}\mu_{n+1,n}+\frac{3}{8}\mu_{n-1,n}\geq
1+\mu_{0,n}/8$. It follows that $\mu_{0,n}\leq
8\mu_{n}+1=24(3/2)^{n}+1=O((3/2)^{n})$.

For the lower bound, observe that $\mu_{n}\leq\mu_{n,0}+\mu_{0,n}$. Since
there is a $1/8$ chance of reaching $0$ from any state, we have $\mu_{n,0}\leq
8$. It follows that $\mu_{n}\leq 8+\mu_{0,n}$ or
$\mu_{0,n}\geq\mu_{n}-8=\Omega((3/2)^{n})$.

####  E.4.3 Yet another shuffling algorithm

Suppose we attempt to shuffle a deck of $n$ cards by picking a card uniformly
at random, and swapping it with the top card. Give the best bound you can on
the mixing time for this process to reach a total variation distance of
$\epsilon$ from the uniform distribution.

##### Solution

It’s tempting to use the same coupling as for move-to-top (see §9.4.3). This
would be that at each step we choose the same card to swap to the top
position, which increases by at least one the number of cards that are in the
same position in both decks. The problem is that at the next step, these two
cards are most likely separated again, by being swapped with other cards in
two different positions.

Instead, we will do something slightly more clever. Let $Z_{t}$ be the number
of cards in the same position at time $t$. If the top cards of both decks are
equal, we swap both to the same position chosen uniformly at random. This has
no effect on $Z_{t}$. If the top cards of both decks are not equal, we pick a
card uniformly at random and swap it to the top in both decks. This increases
$Z_{t}$ by at least $1$, unless we happen to pick cards that are already in
the same position; so $Z_{t}$ increases by at least $1$ with probability
$1-Z_{t}/n$.

Let’s summarize a state by an ordered pair $(k,b)$ where $k=Z_{t}$ and $b$ is
$0$ if the top cards are equal and $1$ if they are not equal. Then we have a
Markov chain where $(k,0)$ goes to $(k,1)$ with probability $\frac{n-k}{n}$
(and otherwise stays put); and $(k,1)$ goes to $(k+1,0)$ (or higher) with
probability $\frac{n-k}{n}$ and to $(k,0)$ with probability $\frac{k}{n}$.

Starting from $(k,0)$, we expect to wait $\frac{n}{n-k}$ steps on average to
reach $(k,1)$, at which point we move to $(k+1,0)$ or back to $(k,0)$ in one
more step; we iterate through this process $\frac{n}{n-k}$ times on average
before we are successful. This gives an expected number of steps to get from
$(k,0)$ to $(k+1,0)$ (or possibly a higher value) of
$\frac{n}{n-k}\left(\frac{n}{n-k}+1)\right)$. Summing over $k$ up to $n-2$
(since once $k>n-2$, we will in fact have $k=n$, since $k$ can’t be $n-1$), we
get

$\displaystyle\operatorname{E}\left[{\tau}\right]$
$\displaystyle\leq\sum_{k=0}^{n-2}\frac{n}{n-k}\left(\frac{n}{n-k}+1\right)$
$\displaystyle=\sum_{m=2}^{n}\left(\frac{n^{2}}{m^{2}}+\frac{n}{m}\right)$
$\displaystyle\leq n^{2}\left(\frac{\pi^{2}}{6}-1\right)+n\ln n.$
$\displaystyle=O(n^{2}).$

So we expect the deck to mix in $O(n^{2}\log(1/\epsilon))$ steps. (I don’t
know if this is the real bound; my guess is that it should be closer to
$O(n\log n)$ as in all the other shuffling procedures.)

###  E.5 Assignment 5: due Thursday, 2011-04-07, at 23:59

####  E.5.1 A reversible chain

Consider a random walk on $\mathbb{Z}_{m}$, where $p_{i,i+1}=2/3$ for all $i$
and $p_{i,i-1}=1/3$ for all $i$ except $i=0$. Is it possible to assign values
to $p_{0,m-1}$ and $p_{0,0}$ to make this chain reversible, and if so, what
stationary distribution do you get?

##### Solution

Suppose we can make this chain reversible, and let $\pi$ be the resulting
stationary distribution. From the detailed balance equations, we have
$(2/3)\pi_{i}=(1/3)\pi_{i+1}$ or $\pi_{i+1}=2\pi_{i}$ for $i=0\dots m-2$. The
solution to this recurrence is $\pi_{i}=2^{i}\pi_{0}$, which gives
$\pi_{i}=\frac{2^{i}}{2^{m}-1}$ when we set $\pi_{0}$ to get
$\sum_{i}\pi_{i}=1$.

Now solve $\pi_{0}p_{0,m-1}=\pi_{m-1}p_{m-1,0}$ to get

$\displaystyle p_{0,m-1}$ $\displaystyle=\frac{\pi_{m-1}p_{m-1,0}}{\pi_{0}}$
$\displaystyle=2^{m-1}(2/3)$ $\displaystyle=2^{m}/3.$

This is greater than $1$ for $m>1$, so except for the degenerate cases of
$m=1$ and $m=2$, it’s not possible to make the chain reversible.

####  E.5.2 Toggling bits

Consider the following Markov chain on an array of $n$ bits $a[1],a[2],\dots
a[n]$. At each step, we choose a position $i$ uniformly at random. We then
change $A[i]$ to $\neg A[i]$ with probability $1/2$, provided $i=1$ or
$A[i-1]=1$ (if neither condition holds hold, do nothing).333Motivation:
Imagine each bit represents whether a node in some distributed system is
inactive (0) or active (1), and you can only change your state if you have an
active left neighbor to notify. Also imagine that there is an always-active
_base station_ at $-1$ (alternatively, imagine that this assumption makes the
problem easier than the other natural arrangement where we put all the nodes
in a ring).

  1. 1.

What is the stationary distribution?

  2. 2.

How quickly does it converge?

##### Solution

  1. 1.

First let’s show irreducibility. Starting from an arbitrary configuration,
repeatedly switch the leftmost $0$ to a $1$ (this is always permitted by the
transition rules); after at most $n$ steps, we reach the all-$1$
configuration. Since we can repeat this process in reverse to get to any other
configuration, we get that every configuration is reachable from every other
configuration in at most $2n$ steps ($2n-1$ if we are careful about handling
the all-$0$ configuration separately).

We also have that for any two adjacent configurations $x$ and $y$,
$p_{xy}=p_{yx}=\frac{1}{2n}$. So we have a reversible, irreducible, aperiodic
(because there exists at least one self-loop) chain with a uniform stationary
distribution $\pi_{x}=2^{-n}$.

  2. 2.

Here is a bound using the obvious coupling, where we choose the same position
in $X$ and $Y$ and attempt to set it to the same value. To show this
coalesces, given $X_{t}$ and $Y_{t}$ define $Z_{t}$ to be the position of the
rightmost $1$ in the common prefix of $X_{t}$ and $Y_{t}$, or $0$ if there is
no $1$ in the common prefix of $X_{t}$ and $Y_{t}$. Then $Z_{t}$ increases by
at least $1$ if we attempt to set position $Z_{t}+1$ to $1$, which occurs with
probability $\frac{1}{2n}$, and decreases by at most $1$ if we attempt to set
$Z_{t}$ to $0$, again with probability $\frac{1}{2n}$.

It follows that $Z_{t}$ reaches $n$ no later than a $\pm 1$ random walk on
$0\dots n$ with reflecting barriers that takes a step every $1/n$ time units
on average. The expected number of steps to reach $n$ from the worst-case
starting position of $0$ is exactly $n^{2}$. (Proof: model the random walk
with a reflecting barrier at $0$ by folding a random walk with absorbing
barriers at $\pm n$ in half, then use the bound from §8.5.1.) We must then
multiply this by $n$ to get an expected $n^{3}$ steps in the original process.
So the two copies coalesce in at most $n^{3}$ expected steps. My suspicion is
one could improve this bound with a better analysis by using the bias toward
increasing $Z_{t}$ to get the expected time to coalesce down to $O(n^{2})$,
but I don’t know any clean way to do this.

The path coupling version of this is that we look at two adjacent
configurations $X_{t}$ and $Y_{t}$, use the obvious coupling again, and see
what happens to
$\operatorname{E}\left[{d(X_{t+1},Y_{t+1})}\;\middle|\;{X_{t},Y_{t}}\right]$,
where the distance is the number of transitions needed to convert $X_{t}$ to
$Y_{t}$ or vice versa. If we pick the position $i$ where $X_{t}$ and $Y_{t}$
differ, then we coalesce; this occurs with probability $1/n$. If we change the
$1$ to the left of $i$ to a $0$, then $d(X_{t+1},Y_{t+1})$ rises to $3$
(because to get from $X_{t+1}$ to $Y_{t+1}$, we have to change position $i-1$
to $1$, change position $i$, and then change position $i-1$ back to $0$); this
occurs with probability $1/2n$ if $i>1$. But we can also get into trouble if
we try to change position $i+1$; we can only make the change in one of $X_{t}$
and $Y_{t}$, so we get $d(X_{t+1},Y_{t+1})=2$ in this case, which occurs with
probability $1/2n$ when $i<n$. Adding up all three cases gives a worst-case
expected change of $-1/n+2/2n+1/2n=1/2n>0$. So unless we can do something more
clever, path coupling won’t help us here.

However, it is possible to get a bound using canonical paths, but the best
bound I could get was not as good as the coupling bound. The basic idea is
that we will change $x$ into $y$ one bit at a time (from left to right, say),
so that we will go through a sequence of intermediate states of the form
$y[1]y[2]\dots y[i]x[i+1]x[i+2]\dots x[n]$. But to change $x[i+1]$ to
$y[i+1]$, we may also need to reach out with a tentacle of $1$ bits from from
the last $1$ in the current prefix of $y$ (and then retract it afterwards).
Given a particular transition where we change a $0$ to a $1$, we can
reconstruct the original $x$ and $y$ by specifying (a) which bit $i$ at or
after our current position we are trying to change; (b) which $1$ bit before
our current position is the last “real” $1$ bit in $y$ as opposed to something
we are creating to reach out to position $i$; and (c) the values of $x[1]\dots
x[i-1]$ and $y[i+1]\dots y[i]$. A similar argument applies to $1\rightarrow 0$
transitions. So we are routing at most $n^{2}2^{n-1}$ paths across each
transition, giving a bound on the congestion

$\displaystyle\rho$
$\displaystyle\leq\left(\frac{1}{2^{-n}/2n}\right)n^{2}2^{n-1}2^{-2n}$
$\displaystyle=n^{3}.$

The bound on $\tau_{2}$ that follows from this is $8n^{6}$, which is pretty
bad (although the constant could be improved by counting the (a) and (b) bits
more carefully). As with the coupling argument, it may be that there is a less
congested set of canonical paths that gives a better bound.

####  E.5.3 Spanning trees

Suppose you have a connected graph $G=(V,E)$ with $n$ nodes and $m$ edges.
Consider the following Markov process. Each state $H_{t}$ is a subgraph of $G$
that is either a spanning tree or a spanning tree plus an additional edge. At
each step, flip a fair coin. If it comes up heads, choose an edge $e$
uniformly at random from $E$ and let $H_{t+1}=H_{t}\cup\left\\{{e}\right\\}$
if $H_{t}$ is a spanning tree and let
$H_{t+1}=H_{t}\setminus\left\\{{e}\right\\}$ if $H_{t}$ is not a spanning tree
and $H_{t}\setminus\left\\{{e}\right\\}$ is connected. If it comes up tails
and $H_{t}$ is a spanning tree, let $H_{t+1}$ be some other spanning tree,
sampled uniformly at random. In all other cases, let $H_{t+1}=H_{t}$.

Let $N$ be the number of states in this Markov chain.

  1. 1.

What is the stationary distribution?

  2. 2.

How quickly does it converge?

##### Solution

  1. 1.

Since every transition has a matching reverse transition with the same
transition probability, the chain is reversible with a uniform stationary
distribution $\pi_{H}=1/N$.

  2. 2.

Here’s a coupling that coalesces in at most $4m/3+2$ expected steps:

    1. (a)

If $X_{t}$ and $Y_{t}$ are both trees, then send them to the same tree with
probability $1/2$; else let them both add edges independently (or we could
have them add the same edge—it doesn’t make any difference to the final
result).

    2. (b)

If only one of $X_{t}$ and $Y_{t}$ is a tree, with probability $1/2$ scramble
the tree while attempting to remove an edge from the non-tree, and the rest of
the time scramble the non-tree (which has no effect) while attempting to add
an edge to the tree. Since the non-tree has at least three edges that can be
removed, this puts $(X_{t+1},Y_{t+1}$ in the two-tree case with probability at
least $3/2m$.

    3. (c)

If neither $X_{t}$ nor $Y_{t}$ is a tree, attempt to remove an edge from both.
Let $S$ and $T$ be the sets of edges that we can remove from $X_{t}$ and
$Y_{t}$, respectively, and let $k=\min(\left\lvert S\right\rvert,\left\lvert
T\right\rvert)\geq 3$. Choose $k$ edges from each of $S$ and $T$ and match
them, so that if we remove one edge from each pair, we also remove the other
edge. As in the previous case, this puts $(X_{t+1},Y_{t+1}$ in the two-tree
case with probability at least $3/2m$.

To show this coalesces, starting from an arbitrary state, we reach a two-tree
state in at most $2m/3$ expected steps. After one more step, we either
coalesce (with probability $1/2$) or restart from a new arbitrary state. This
gives an expected coupling time of at most $2(2m/3+1)=4m/3+2$ as claimed.

###  E.6 Assignment 6: due Monday, 2011-04-25, at 17:00

####  E.6.1 Sparse satisfying assignments to DNFs

Given a formula in disjunctive normal form, we’d like to estimate the number
of satisfying assignments in which exactly $w$ of the variables are true. Give
a fully polynomial-time randomized approximation scheme for this problem.

##### Solution

Essentially, we’re going to do the Karp-Luby covering trick [KL85] described
in §10.3, but will tweak the probability distribution when we generate our
samples so that we only get samples with weight $w$.

Let $U$ be the set of assignment with weight $w$ (there are exactly
$\binom{n}{w}$ such assignments, where $n$ is the number of variables). For
each clause $C_{i}$, let $U_{i}=\left\\{{x\in
U}\;\middle|\;{C_{i}(x)=1}\right\\}$. Now observe that:

  1. 1.

We can compute $\left\lvert U_{i}\right\rvert$. Let $k_{i}=\left\lvert
C_{i}\right\rvert$ be the number of variables in $C_{i}$ and
$k^{+}_{i}=\left\lvert C^{+}_{i}\right\rvert$ the number of variables that
appear in positive form in $C_{i}$. Then $\left\lvert
U_{i}\right\rvert=\binom{n-k_{i}}{w-k^{+}_{i}}$ is the number of ways to make
a total of $w$ variables true using the remaining $n-k_{i}$ variables.

  2. 2.

We can sample uniformly from $U_{i}$, by sampling a set of $w-k^{+}_{i}$ true
variables not in $C_{i}$ uniformly from all variables not in $C_{i}$.

  3. 3.

We can use the values computed for $\left\lvert U_{i}\right\rvert$ to sample
$i$ proportionally to the size of $\left\lvert U_{i}\right\rvert$.

So now we sample pairs $(i,x)$ with $x\in U_{i}$ uniformly at random by
sampling $i$ first, then sampling $x\in U_{i}$. As in the original algorithm,
we then count $(i,x)$ if and only if $C_{i}$ is the leftmost clause for which
$C_{i}(x)=1$. The same argument that at least $1/m$ of the $(i,x)$ pairs count
applies, and so we get the same bounds as in the original algorithm.

####  E.6.2 Detecting duplicates

Algorithm E.1 attempts to detect duplicate values in an input array $S$ of
length $n$.

1 Initialize $A[1\dots n]$ to $\bot$

2 Choose a hash function $h$

3 for  _$i\leftarrow 1\dots n$_ do

4 $x\leftarrow S[i]$

5 if  _$A[h(x)]=x$_ then

6 return true

7 else

8 $A[h(x)]\leftarrow x$

9

return false

Algorithm E.1 Dubious duplicate detector

It’s easy to see that Algorithm E.1 never returns true unless some value
appears twice in $S$. But maybe it misses some duplicates it should find.

  1. 1.

Suppose $h$ is a random function. What is the worst-case probability that
Algorithm E.1 returns false if $S$ contains two copies of some value?

  2. 2.

Is this worst-case probability affected if $h$ is drawn instead from a
$2$-universal family of hash functions?

##### Solution

  1. 1.

Suppose that $S[i]=S[j]=x$ for $i<j$. Then the algorithm will see $x$ in
$A[h(x)]$ on iteration $j$ and return true, unless it is overwritten by some
value $S[k]$ with $i<k<j$. This occurs if $h(S[k])=h(x)$, which occurs with
probability exactly $1-(1-1/n)^{j-i-1}$ if we consider all possible $k$. This
quantity is maximized at $1-(1-1/n)^{n-2}\approx 1-(1-1/n)^{2}/e\approx
1-(1-1/2n)/e$ when $i=1$ and $j=n$.

  2. 2.

As it happens, the algorithm can fail pretty badly if all we know is that $h$
is $2$-universal. What we can show is that the probability that some $S[k]$
with $i<j<k$ gets hashed to the same place as $x=S[i]=S[j]$ in the analysis
above is at most $(j-i-1)/n\leq(n-2)/n=(1-2/n)$, since each $S[k]$ has at most
a $1/n$ chance of colliding with $x$ and the union bound applies. But it is
possible to construct a $2$-universal family for which we get exactly this
probability in the worst case.

Let $U=\left\\{{0\dots n}\right\\}$, and define for each $a$ in
$\left\\{{0\dots n-1}\right\\}$ $h_{a}:U\rightarrow n$ by $h_{a}(n)=0$ and
$h_{a}(x)=(x+a)\bmod n$ for $x\neq n$. Then $H=\left\\{{h_{a}}\right\\}$ is
$2$-universal, since if $x\neq y$ and neither $x$ nor $y$ is $n$,
$\Pr\left[{h_{a}(x)=h_{a}(y)}\right]=0$, and if one of $x$ or $y$ is $n$,
$\Pr\left[{h_{a}(x)=h_{a}(y)}\right]=1/n$. But if we use this family in
Algorithm E.1 with $S[1]=S[n]=n$ and $S[k]=k$ for $1<k<n$, then there are
$n-2$ choices of $a$ that put one of the middle values in $A[0]$.

####  E.6.3 Balanced Bloom filters

A clever algorithmist decides to solve the problem of Bloom filters filling up
with ones by capping the number of ones at $m/2$. As in a standard Bloom
filter, an element is inserted by writing ones to
$A[h_{1}(x)],A[h_{2}(x)],\dots,A[h_{k}(x)]$; but after writing each one, if
the number of one bits in the bit-vector is more than $m/2$, one of the ones
in the vector (chosen uniformly at random) is changed back to a zero.

Because some of the ones associated with a particular element might be
deleted, the membership test answers yes if at least $3/4$ of the bits
$A[h_{1}(x)]\dots A[h_{k}(x)]$ are ones.

To simplify the analysis, you may assume that the $h_{i}$ are independent
random functions. You may also assume that $(3/4)k$ is an integer.

  1. 1.

Give an upper bound on the probability of a false positive when testing for a
value $x$ that has never been inserted.

  2. 2.

Suppose that we insert $x$ at some point, and then follow this insertion with
a sequence of insertions of new, distinct values $y_{1},y_{2},\dots$. Assuming
a worst-case state before inserting $x$, give asymptotic upper and lower
bounds on the expected number of insertions until a test for $x$ fails.

##### Solution

  1. 1.

The probability of a false positive is maximized when exactly half the bits in
$A$ are one. If $x$ has never been inserted, each $A[h_{i}(x)]$ is equally
likely to be zero or one. So $\Pr\left[{\text{false positive for
$x$}}\right]=\Pr\left[{S_{k}\geq(3/4)k}\right]$ when $S_{k}$ is a binomial
random variable with parameters $1/2$ and $k$. Chernoff bounds give

$\displaystyle\Pr\left[{S_{k}\geq(3/4)k}\right]$
$\displaystyle=\Pr\left[{S_{k}\geq(3/2)\operatorname{E}\left[{S_{k}}\right]}\right]$
$\displaystyle\leq\left(\frac{e^{1/2}}{(3/2)^{3/2}}\right)^{k/2}$
$\displaystyle\leq(0.94734)^{k}.$

We can make this less than any fixed $\epsilon$ by setting $k\geq
20\ln(1/\epsilon)$ or thereabouts.

  2. 2.

For false negatives, we need to look at how quickly the bits for $x$ are
eroded away. A minor complication is that the erosion may start even as we are
setting $A[h_{1}(x)]\dots A[h_{k}(x)]$.

Let’s consider a single bit $A[i]$ and look at how it changes after (a)
setting $A[i]=1$, and (b) setting some random $A[r]=1$.

In the first case, $A[i]$ will be $1$ after the assignment unless it is set
back to zero, which occurs with probability $\frac{1}{m/2+1}$. This
distribution does not depend on the prior value of $A[i]$.

In the second case, if $A[i]$ was previously $0$, it becomes $1$ with
probability

$\displaystyle\frac{1}{m}\left(1-\frac{1}{m/2+1}\right)$
$\displaystyle=\frac{1}{m}\cdot\frac{m/2}{m/2+1}$
$\displaystyle=\frac{1}{m+2}.$

If it was previously $1$, it becomes $0$ with probability

$\displaystyle\frac{1}{2}\cdot\frac{1}{m/2+1}$ $\displaystyle=\frac{1}{m+2}.$

So after the initial assignment, $A[i]$ just flips its value with probability
$\frac{1}{m+2}$.

It is convenient to represent $A[i]$ as $\pm 1$; let $X^{t}_{i}=-1$ if
$A[i]=0$ at time $t$, and $1$ otherwise. Then $X^{t}_{i}$ satisfies the
recurrence

$\displaystyle\operatorname{E}\left[{X^{t+1}_{i}}\;\middle|\;{X^{t}_{i}}\right]$
$\displaystyle=\frac{m+1}{m+2}X^{t}_{i}-\frac{1}{m+2}X^{t}_{i}$
$\displaystyle=\frac{m}{m+2}X^{t}_{i}.$
$\displaystyle=\left(1-\frac{2}{m+2}\right)X^{t}_{i}.$

We can extend this to
$\operatorname{E}\left[{X^{t}_{i}}\;\middle|\;{X^{0}_{i}}\right]=\left(1-\frac{2}{m+2}\right)^{t}X^{0}_{i}\approx
e^{-2t/(m+2)}X^{0}_{i}$.

Similarly, after setting $A[i]=1$, we get
$\operatorname{E}\left[{X_{i}}\right]=1-2\frac{1}{m/2+1}=1-\frac{4}{2m+1}=1-o(1)$.

Let $S^{t}=\sum_{i=1}^{k}X^{t}_{h_{i}(x)}$. Let $0$ be the time at which we
finish inserting $x$. Then each for each $i$ we have

$1-o(1)e^{-2k/(m+2)}\leq\operatorname{E}\left[{X^{0}_{h_{i}(x)}}\right]\leq
1-o(1),$

from which it follows that

$k(1-o(1))e^{-2k/(m+2)}\leq\operatorname{E}\left[{S^{0}}\right]\leq 1-o(1)$

and in general that

$k(1-o(1))e^{-2(k+t)/(m+2)}\leq\operatorname{E}\left[{S^{t}}\right]\leq
1-o(1)e^{-2t/(m+2)}.$

So for any fixed $0<\epsilon<1$ and sufficiently large $m$, we will have
$\operatorname{E}\left[{S^{t}}\right]=\epsilon k$ for some $t^{\prime}$ where
$t\leq t^{\prime}\leq k+t$ and $t=\Theta(m\ln(1/\epsilon))$.

We are now looking for the time at which $S^{t}$ drops below $k/2$ (the $k/2$
is because we are working with $\pm 1$ variables). We will bound when this
time occurs using Markov’s inequality.

Let’s look for the largest time $t$ with
$\operatorname{E}\left[{S^{t}}\right]\geq(3/4)k$. Then
$\operatorname{E}\left[{k-S^{t}}\right]\leq k/4$ and $\Pr\left[{k-S^{t}\geq
k/2}\right]\leq 1/2$. It follows that after $\Theta(m)-k$ operations, $x$ is
still visible with probability $1/2$, which implies that the expected time at
which it stops being visible is at least $(\Omega(m)-k)/2$. To get the
expected number of insert operations, we divide by $k$, to get $\Omega(m/k)$.

For the upper bound, apply the same reasoning to the first time at which
$\operatorname{E}\left[{S^{t}}\right]\leq k/4$. This occurs at time $O(m)$ at
the latest (with a different constant), so after $O(m)$ steps there is at most
a $1/2$ probability that $S^{t}\geq k/2$. If $S^{t}$ is still greater than
$k/2$ at this point, try again using the same analysis; this gives us the
usual geometric series argument that $\operatorname{E}\left[{t}\right]=O(m)$.
Again, we have to divide by $k$ to get the number of insert operations, so we
get $O(m/k)$ in this case.

Combining these bounds, we have that $x$ disappears after $\Theta(m/k)$
insertions on average. This seems like about what we would expect.

###  E.7 Final exam

Write your answers in the blue book(s). Justify your answers. Work alone. Do
not use any notes or books.

There are four problems on this exam, each worth 20 points, for a total of 80
points. You have approximately three hours to complete this exam.

####  E.7.1 Leader election

Suppose we have $n$ processes and we want to elect a leader. At each round,
each process flips a coin, and drops out if the coin comes up tails. We win if
in some round there is exactly one process left.

Let $T(n)$ be the probability that this event eventually occurs starting with
$n$ processes. For small $n$, we have $T(0)=0$ and $T(1)=1$. Show that there
is a constant $c>0$ such that $T(n)\geq c$ for all $n>1$.

##### Solution

Let’s suppose that there is some such $c$. We will necessarily have $c\leq
1=T(1)$, so the induction hypothesis will hold in the base case $n=1$.

For $n\geq 2$, compute

$\displaystyle T(n)$ $\displaystyle=\sum_{k=0}^{n}2^{-n}\binom{n}{k}T(k)$
$\displaystyle=2^{-n}T(n)+2^{-n}nT(1)+\sum_{k=2}^{n-1}2^{-n}\binom{n}{k}T(k)$
$\displaystyle\geq 2^{-n}T(n)+2^{-n}n+2^{-n}(2^{n}-n-2)c.$

Solve for $T(n)$ to get

$\displaystyle T(n)$ $\displaystyle\geq\frac{n+(2^{n}-n-2)c}{2^{n}-1}$
$\displaystyle=c\left(\frac{2^{n}-n-2+n/c}{2^{n}-1}\right).$

This will be greater than or equal to $c$ if $2^{n}-n-2+n/c\geq 2^{n}-1$ or
$n/c\geq n+1$, which holds if $c\leq\frac{n}{n+1}$. The worst case is $n=2$
giving $c=2/3$.

Valiant and Vazirani [VV86] used this approach to reduce solving general
instances of SAT to solving instances of SAT with unique solutions; they prove
essentially the result given above (which shows that fixing variables in a SAT
formula is likely to produce a SAT formula with a unique solution at some
point) with a slightly worse constant.

####  E.7.2 Two-coloring an even cycle

Here is a not-very-efficient algorithm for $2$-coloring an even cycle. Every
node starts out red or blue. At each step, we pick one of the $n$ nodes
uniformly at random, and change its color if it has the same color as at least
one of its neighbors. We continue until no node has the same color as either
of its neighbors.

Suppose that in the initial state there are exactly two monochromatic edges.
What is the worst-case expected number of steps until there are no
monochromatic edges?

##### Solution

Suppose we have a monochromatic edge surrounded by non-monochrome edges, e.g.
$RBRRBR$. If we pick one of the endpoints of the edge (say the left endpoint
in this case), then the monochromatic edge shifts in the direction of that
endpoint: $RBBRBRB$. Picking any node not incident to a monochromatic edge has
no effect, so in this case there is no way to increase the number of
monochromatic edges.

It may also be that we have two adjacent monochromatic edges: $BRRRB$. Now if
we happen to pick the node in the middle, we end up with no monochromatic
edges ($BRBRB$) and the process terminates. If on the other hand we pick one
of the nodes on the outside, then the monochromatic edges move away from each
other.

We can thus model the process with $2$ monochromatic edges as a random walk,
where the difference between the leftmost nodes of the edges (mod $n$)
increases or decreases with equal probability $2/n$ except if the distance is
$1$ or $-1$; in this last case, the distance increases (going to $2$ or $-2$)
with probability $2/n$, but decreases only with probability $1/n$. We want to
know when this process hits $0$ (or $n$).

Imagine a random walk starting from position $k$ with absorbing barriers at
$1$ and $n-1$. This reaches $1$ or $n-1$ after $(k-1)(n-1-k)$ steps on
average, which translates into $(n/4)(k-1)(n-1-k)$ steps of our original
process if we take into account that we only move with probability $4/n$ per
time unit. This time is maximized by setting $k=n/2$, which gives
$(n/4)(n/2-1)^{2}=n^{3}/16-n^{2}/4+n/4$ expected time units to reach $1$ or
$n-1$ for the first time.

At $1$ or $n-1$, we wait an addition $n/3$ steps on average; then with
probability $1/3$ the process finishes and with probability $2/3$ we start
over from position $2$ or $n-2$; in the latter case, we run $(n/4)(n-3)+n/3$
time units on average before we may finish again. On average, it takes $3$
attempts to finish. Each attempt incurs the expected $n/3$ cost before taking
a step, and all but the last attempt incur the expected $(n/4)(n-3)$
additional steps for the random walk. So the last phase of the process the
process adds $(1/2)n(n-3)+n=(1/2)n^{2}-(5/4)n$ steps.

Adding up all of the costs gives
$n^{3}/16-n^{2}/4+n/4+n/3+(1/2)n^{2}-(5/4)n=\frac{1}{16}n^{3}+\frac{1}{4}n^{2}-\frac{2}{3}n$
steps.

####  E.7.3 Finding the maximum

1 Randomly permute $A$

2 $m\leftarrow-\infty$

3 for  _$i\leftarrow 1\dots n$_ do

4 if  _$A[i] >m$_ then

5 $m\leftarrow A[i]$

6

return $m$

Algorithm E.2 Randomized max-finding algorithm

Suppose that we run Algorithm E.2 on an array with $n$ elements, all of which
are distinct. What is the expected number of times Line E.2 is executed as a
function of $n$?

##### Solution

Let $X_{i}$ be the indicator variable for the event that Line E.2 is executed
on the $i$-th pass through the loop. This will occur if $A[i]$ is greater than
$A[j]$ for all $j<i$, which occurs with probability exactly $1/i$ (given that
$A$ has been permuted randomly). So the expected number of calls to Line E.2
is
$\sum{i=1}^{n}\operatorname{E}\left[{X_{i}}\right]=\sum_{i=1}^{n}\frac{1}{i}=H_{n}$.

####  E.7.4 Random graph coloring

Let $G$ be a random $d$-regular graph on $n$ vertices, that is, a graph drawn
uniformly from the family of all $n$-vertex graph in which each vertex has
exactly $d$ neighbors. Color the vertices of $G$ red or blue independently at
random.

  1. 1.

What is the expected number of monochromatic edges in $G$?

  2. 2.

Show that the actual number of monochromatic edges is tightly concentrated
around its expectation.

##### Solution

The fact that $G$ is itself a random graph is a red herring; all we really
need to know is that it’s $d$-regular.

  1. 1.

Because $G$ has exactly $dn/2$ edges, and each edge has probability $1/2$ of
being monochromatic, the expected number of monochromatic edges is $dn/4$.

  2. 2.

This is a job for Azuma’s inequality. Consider the vertex exposure martingale.
Changing the color of any one vertex changes the number of monochromatic edges
by at most $d$. So we have $\Pr\left[{\left\lvert
X-\operatorname{E}\left[{X}\right]\right\rvert\geq t}\right]\leq
2\exp\left(-t^{2}/2\sum_{i=1}^{n}d^{2}\right)=2e^{-t^{2}/2nd^{2}}$, which
tells us that the deviation is likely to be not much more than $O(d\sqrt{n})$.

##  Appendix F Sample assignments from Spring 2009

###  F.1 Final exam, Spring 2009

Write your answers in the blue book(s). Justify your answers. Work alone. Do
not use any notes or books.

There are four problems on this exam, each worth 20 points, for a total of 80
points. You have approximately three hours to complete this exam.

####  F.1.1 Randomized mergesort (20 points)

Consider the following randomized version of the mergesort algorithm. We take
an unsorted list of $n$ elements and split it into two lists by flipping an
independent fair coin for each element to decide which list to put it in. We
then recursively sort the two lists, and merge the resulting sorted lists. The
merge procedure involves repeatedly comparing the smallest element in each of
the two lists and removing the smaller element found, until one of the lists
is empty.

Compute the expected number of comparisons needed to perform this final merge.
(You do not need to consider the cost of performing the recursive sorts.)

##### Solution

Color the elements in the final merged list red or blue based on which sublist
they came from. The only elements that do not require a comparison to insert
into the main list are those that are followed only by elements of the same
color; the expected number of such elements is equal to the expected length of
the longest monochromatic suffix. By symmetry, this is the same as the
expected longest monochromatic prefix, which is equal to the expected length
of the longest sequence of identical coin-flips.

The probability of getting $k$ identical coin-flips in a row followed by a
different coin-flip is exactly $2^{-k}$; the first coin-flip sets the color,
the next $k-1$ must follow it (giving a factor of $2^{-k+1}$, and the last
must be the opposite color (giving an additional factor of $2^{-1}$). For $n$
identical coin-flips, there is a probability of $2^{-n+1}$, since we don’t
need an extra coin-flip of the opposite color. So the expected length is
$\sum_{k=1}^{n-1}k2^{-k}+n2^{-n+1}=\sum_{k=0}^{n}k2^{-k}+n2^{-n}$.

We can simplify the sum using generating functions. The sum
$\sum_{k=0}^{n}2^{-k}z^{k}$ is given by $\frac{1-(z/2)^{n+1}}{1-z/2}$. Taking
the derivative with respect to $z$ gives
$\sum_{k=0}^{n}2^{-k}kz^{k-1}=(1/2)\frac{1-(z/2)^{n+1}}{1-z/2}^{2}+(1/2)\frac{(n+1)(z/2)^{n}}{1-z/2}$.
At $z=1$ this is $2(1-2^{-n-1})-2(n+1)2^{-n}=2-(n+2)2^{-n}$. Adding the second
term gives $\operatorname{E}\left[{X}\right]=2-2\cdot 2^{-n}=2-2^{-n+1}$.

Note that this counts the expected number of elements for which we do not have
to do a comparison; with $n$ elements total, this leaves $n-2+2^{-n+1}$
comparisons on average.

####  F.1.2 A search problem (20 points)

Suppose you are searching a space by generating new instances of some problem
from old ones. Each instance is either good or bad; if you generate a new
instance from a good instance, the new instance is also good, and if you
generate a new instance from a bad instance, the new instance is also bad.

Suppose that your start with $X_{0}$ good instances and $Y_{0}$ bad instances,
and that at each step you choose one of the instances you already have
uniformly at random to generate a new instance. What is the expected number of
good instances you have after $n$ steps?

Hint: Consider the sequence of values
$\left\\{{X_{t}/(X_{t}+Y_{t})}\right\\}$.

##### Solution

We can show that the suggested sequence is a martingale, by computing

$\displaystyle\operatorname{E}\left[{\frac{X_{t+1}}{X_{t+1}+Y_{t+1}}}\;\middle|\;{X_{t},Y_{t}}\right]$
$\displaystyle=\frac{X_{t}}{X_{t}+Y_{t}}\cdot\frac{X_{t}+1}{X_{t}+Y_{t}+1}+\frac{Y_{t}}{X_{t}+Y_{t}}\cdot\frac{X_{t}}{X_{t}+Y_{t}+1}$
$\displaystyle=\frac{X_{t}(X_{t}+1)+Y_{t}X_{t}}{(X_{t}+Y_{t})(X_{t}+Y_{t}+1)}$
$\displaystyle=\frac{X_{t}(X_{t}+Y_{t}+1)}{(X_{t}+Y_{t})(X_{t}+Y_{t}+1)}$
$\displaystyle=\frac{X_{t}}{X_{t}+Y_{t}}.$

From the martingale property we have
$\operatorname{E}\left[{\frac{X_{n}}{X_{n}+Y_{n}}}\right]=\frac{X_{0}}{X_{0}+Y_{0}}$.
But $X_{n}+Y_{n}=X_{0}+Y_{0}+n$, a constant, so we can multiply both sides by
this value to get
$\operatorname{E}\left[{X_{n}}\right]=X_{0}\left(\frac{X_{0}+Y_{0}+n}{X_{0}+Y_{0}}\right)$.

####  F.1.3 Support your local police (20 points)

At one point I lived in a city whose local police department supported
themselves in part by collecting fines for speeding tickets. A speeding ticket
would cost 1 unit (approximately $100), and it was unpredictable how often one
would get a speeding ticket. For a price of 2 units, it was possible to
purchase a metal placard to go on your vehicle identifying yourself as a
supporter of the police union, which (at least according to local legend)
would eliminate any fines for subsequent speeding tickets, but which would not
eliminate the cost of any previous speeding tickets.

Let us consider the question of when to purchase a placard as a problem in on-
line algorithms. It is possible to achieve a strict111I.e., with no additive
constant. competitive ratio of 2 by purchasing a placard after the second
ticket. If one receives fewer than 2 tickets, both the on-line and off-line
algorithms pay the same amount, and at 2 or more tickets the on-line algorithm
pays 4 while the off-line pays 2 (the off-line algorithm purchased the placard
before receiving any tickets at all).

  1. 1.

Show that no deterministic algorithm can achieve a lower (strict) competitive
ratio.

  2. 2.

Show that a randomized algorithm can do so, against an oblivious adversary.

##### Solution

  1. 1.

Any deterministic algorithm essentially just chooses some fixed number $m$ of
tickets to collect before buying the placard. Let $n$ be the actual number of
tickets issued. For $m=0$, the competitive ratio is infinite when $n=0$. For
$m=1$, the competitive ratio is 3 when $n=1$. For $m>2$, the competitive ratio
is $(m+2)/2>2$ when $n=m$. So $m=2$ is the optimal choice.

  2. 2.

Consider the following algorithm: with probability $p$, we purchase a placard
after 1 ticket, and with probability $q=1-p$, we purchase a placard after 2
tickets. This gives a competitive ratio of $1$ for $n=0$, $1+2p$ for $n=1$,
and $(3p+4q)/2=(4-p)/2=2-p/2$ for $n\geq 2$. There is a clearly a trade-off
between the two ratios $1+2p$ and $2-p/2$. The break-even point is when they
are equal, at $p=2/5$. This gives a competitive ratio of $1+2p=9/5$, which is
less than $2$.

####  F.1.4 Overloaded machines (20 points)

Suppose $n^{2}$ jobs are assigned to $n$ machines with each job choosing a
machine independently and uniformly at random. Let the load on a machine be
the number of jobs assigned to it. Show that for any fixed $\delta>0$ and
sufficiently large $n$, there is a constant $c<1$ such that the maximum load
exceeds $(1+\delta)n$ with probability at most $nc^{n}$.

##### Solution

This is a job for Chernoff bounds. For any particular machine, the load $S$ is
a sum of independent indicator variables and the mean load is $\mu=n$. So we
have

$\displaystyle\Pr\left[{S\geq(1+\delta)\mu}\right]$
$\displaystyle\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{n}.$

Observe that $e^{\delta}/(1+\delta)^{1+\delta}<1$ for $\delta>0$. One proof of
this fact is to take the log to get $\delta-(1+\delta)\log(1+\delta)$, which
equals $0$ at $\delta=0$, and then show that the logarithm is decreasing by
showing that
$\frac{d}{d\delta}\dots=1-\frac{1+\delta}{1+\delta}-\log(1+\delta)=-\log(1+\delta)<0$
for all $\delta>0$.

So we can let $c=e^{\delta}/(1+\delta)^{1+\delta}$ to get a bound of $c^{n}$
on the probability that any particular machine is overloaded and a bound of
$nc^{n}$ (from the union bound) on the probability that any of the machines is
overloaded.

##  Appendix G Probabilistic recurrences

Randomized algorithms often produce recurrences with ugly sums embedded inside
them (see, for example, (1.3.1)). We’d like to have tools for pulling at least
asymptotic bounds out of these recurrences without having to deal with the
sums. This isn’t always possible, but for certain simple recurrences we can
make it work.

###  G.1 Recurrences with constant cost functions

Let us consider probabilistic recurrences of the form $T(n)=1+T(n-X_{n})$,
where $X_{n}$ is a random variable with $0<X_{n}\leq n$ and $T(0)=0$. We
assume we can compute a lower bound on $\operatorname{E}\left[{X_{n}}\right]$
for each $n$, and we want to translate this lower bound into an upper bound on
$\operatorname{E}\left[{T(n)}\right]$.

###  G.2 Examples

  * •

How long does it take to get our first heads if we repeatedly flip a coin that
comes up heads with probability $p$? Even though we probably already know the
answer to this, We can solve it by solving the recurrence
$T(1)=1+T(1-X_{1}),T(0)=0$, where $\operatorname{E}\left[{X_{1}}\right]=p$.

  * •

Hoare’s FIND [Hoa61b], often called QuickSelect, is an algorithm for finding
the $k$-th smallest element of an unsorted array. It works like QuickSort,
only after partitioning the array around a random pivot we throw away the part
that doesn’t contain our target and recurse only on the surviving piece. How
many rounds of this must we do? Here $\operatorname{E}\left[{X_{n}}\right]$ is
more complicated, since after splitting our array of size $n$ into piles of
size $n^{\prime}$ and $n-n^{\prime}-1$, we have to pick one or the other (or
possibly just the pivot alone) based on the value of $k$.

  * •

Suppose we start with $n$ biased coins that each come up heads with
probability $p$. In each round, we flip all the coins and throw away the ones
that come up tails. How many rounds does it take to get rid of all of the
coins? (This essentially tells us how tall a skip list [Pug90] can get.) Here
we have $\operatorname{E}\left[{X_{n}}\right]=(1-p)n$.

  * •

In the coupon collector problem, we sample from $1\dots n$ with replacement
until we see ever value at least once. We can model this by a recurrence in
which $T(k)$ is the time to get all the coupons given there are $k$ left that
we haven’t seen. Here $X_{n}$ is $1$ with probability $k/n$ and $0$ with
probability $(n-k)/n$, giving $\operatorname{E}\left[{X_{n}}\right]=k/n$.

  * •

Let’s play Chutes and Ladders without the chutes and ladders. We start at
location $n$, and whenever it’s our turn, we roll a fair six-sided die $X$ and
move to $n-X$ unless this value is negative, in which case we stay put until
the next turn. How many turns does it take to get to $0$?

###  G.3 The Karp-Upfal-Wigderson bound

This is a bound on the expected number of rounds to finish a process where we
start with a problem instance of size $n$, and after one round of work we get
a new problem instance of size $n-X_{n}$, where $X_{n}$ is a random variable
whose distribution depends on $n$. It was original described in a paper by
Karp, Upfal, and Wigderson on analyzing parallel search algorithms [KUW88].
The bound applies when $\operatorname{E}\left[{X_{n}}\right]$ is bounded below
by a non-decreasing function $\mu(n)$.

######  Lemma G.3.1.

Let $a$ be a constant, let $T(n)=1+T(n-X_{n})$, where for each $n$, $X_{n}$ is
an integer-valued random variable satisfying $0\leq X_{n}\leq n-a$ and let
$T(a)=0$. Let $\operatorname{E}\left[{X_{n}}\right]\geq\mu(n)$ for all $n>a$,
where $\mu$ is a positive non-decreasing function of $n$. Then

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle\leq\int_{a}^{n}\frac{1}{\mu(t)}\,dt.$ (G.3.1)

To get an intuition for why this works, imagine that $X_{n}$ is the speed at
which we drop from $n$, expressed in units per round. Traveling at this speed,
it takes $1/X_{n}$ rounds to cross from $k+1$ to $k$ for any such interval we
pass. From the point of view of the interval $[k,k+1]$, we don’t know which
$n$ we are going to start from before we cross it, but we do know that for any
$n\geq k+1$ we start from, our speed will be at least $\mu(n)\geq\mu(k+1)$ on
average. So the time it takes will be at most
$\int_{k}^{k+1}\frac{1}{\mu(t)}\,dt$ on average, and the total time is
obtained by summing all of these intervals.

Of course, this intuition is not even close to a real proof (among other
things, there may be a very dangerous confusion in there between
$1/\operatorname{E}\left[{X_{n}}\right]$ and
$\operatorname{E}\left[{1/X_{n}}\right]$), so we will give a real proof as
well.

###### Proof of Lemma G.3.1.

This is essentially the same proof as in Motwani and Raghavan [MR95], but we
add some extra detail to allow for the possibility that $X_{n}=0$.

Let $p=\Pr\left[{X_{n}=0}\right]$, $q=1-p=\Pr\left[{X_{n}\neq 0}\right]$. Note
we have $q>0$ because otherwise
$\operatorname{E}\left[{X_{n}}\right]=0<\mu(n)$. Then we have

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle=1+\operatorname{E}\left[{T(n-X_{n})}\right]$
$\displaystyle=1+p\operatorname{E}\left[{T(n-X_{n})}\;\middle|\;{X_{n}=0}\right]+q\operatorname{E}\left[{T(n-X_{n})}\;\middle|\;{X_{n}\neq
0}\right]$
$\displaystyle=1+p\operatorname{E}\left[{T(n)}\right]+q\operatorname{E}\left[{T(n-X_{n})}\;\middle|\;{X_{n}\neq
0}\right].$

Now we have $\operatorname{E}\left[{T(n)}\right]$ on both sides, which we
don’t like very much. So we collect it on the left-hand side:

$\displaystyle(1-p)\operatorname{E}\left[{T(n)}\right]$
$\displaystyle=1+q\operatorname{E}\left[{T(n-X_{n})}\;\middle|\;{X_{n}\neq
0}\right],$

divide both sides by $q=1-p$, and apply the induction hypothesis:

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle=1/q+\operatorname{E}\left[{T(n-X_{n})}\;\middle|\;{X_{n}\neq
0}\right]$
$\displaystyle=1/q+\operatorname{E}\left[{\operatorname{E}\left[{T(n-X_{n})}\;\middle|\;{X_{n}}\right]}\;\middle|\;{X_{n}\neq
0}\right]$ $\displaystyle\leq
1/q+\operatorname{E}\left[{\int_{a}^{n-X_{n}}\frac{1}{\mu(t)}\,dt}\;\middle|\;{X_{n}\neq
0}\right]$
$\displaystyle=1/q+\operatorname{E}\left[{\int_{a}^{n}\frac{1}{\mu(t)}\,dt-\int_{n-X_{n}}^{n}\frac{1}{\mu(t)}\,dt}\;\middle|\;{X_{n}\neq
0}\right]$ $\displaystyle\leq
1/q+\int_{a}^{n}\frac{1}{\mu(t)}\,dt-\operatorname{E}\left[{\frac{X_{n}}{\mu(n)}}\;\middle|\;{X_{n}\neq
0}\right]$ $\displaystyle\leq
1/q+\int_{a}^{n}\frac{1}{\mu(t)}\,dt-\frac{\operatorname{E}\left[{X_{n}}\;\middle|\;{X_{n}\neq
0}\right]}{\mu(n)}.$

The second-to-last step uses the fact that $\mu(t)\leq\mu(n)fort\leq n$.

It may seem like we don’t know what
$\operatorname{E}\left[{X_{n}}\;\middle|\;{X_{n}\neq 0}\right]$ is. But we
know that $X_{n}\geq 0$, so we have
$\operatorname{E}\left[{X_{n}}\right]=p\operatorname{E}\left[{X_{n}}\;\middle|\;{X_{n}=0}\right]+q\operatorname{E}\left[{X_{n}}\;\middle|\;{X_{n}\neq
0}\right]=q\operatorname{E}\left[{X_{n}}\;\middle|\;{X_{n}\neq 0}\right]$. So
we can solve for $\operatorname{E}\left[{X_{n}}\;\middle|\;{X_{n}\neq
0}\right]=E[X_{n}]/q$. So let’s plug this in:

$\displaystyle\operatorname{E}\left[{T(n)}\right]$ $\displaystyle\leq
1/q+\int_{a}^{n}\frac{1}{\mu(t)}\,dt-\frac{\operatorname{E}\left[{X_{n}}\right]/q}{\mu(n)}$
$\displaystyle\leq 1/q+\int_{a}^{n}\frac{1}{\mu(t)}\,dt-1/q$
$\displaystyle=\int_{a}^{n}\frac{1}{\mu(t)}\,dt.$

This concludes the proof. ∎

Now we just need to find some applications.

####  G.3.1 Waiting for heads

For the recurrence $T(1)=1+T(1-X_{1})$ with
$\operatorname{E}\left[{X_{1}}\right]=p$, we set $\mu(n)=p$ and get
$\operatorname{E}\left[{T(1)}\right]\leq\int_{0}^{1}\frac{1}{p}\,dt=\frac{1}{p}$,
which happens to be exactly the right answer.

####  G.3.2 Quickselect

In Quickselect, we pick a random pivot and split the original array of size
$n$ into three piles of size $m$ (less than the pivot), 1 (the pivot itself),
and $n-m-1$ (greater than the pivot). We then figure out which of the three
piles contains the $k$-th smallest element (depend on how $k$ compares to
$m-1$) and recurse, stopping when we hit a pile with $1$ element. It’s easiest
to analyze this by assuming that we recurse in the largest of the three piles,
i.e., that our recurrence is $T(n)=1+\max(T(m),T(n-m-1))$, where $m$ is
uniform in $0\dots n-1$. The exact value of
$\operatorname{E}\left[{\max(m,n-m-1)}\right]$ is a little messy to compute
(among other things, it depends on whether $n$ is odd or even), but it’s not
hard to see that it’s always less than $(3/4)n$. So letting $\mu(n)=n/4$, we
get

$\displaystyle\operatorname{E}\left[{T(n)}\right]\leq\int_{1}^{n}\frac{1}{t/4}\,dt=4\ln
n.$

####  G.3.3 Tossing coins

Here we have $\operatorname{E}\left[{X_{n}}\right]=(1-p)n$. If we let
$\mu(n)=(1-p)n$ and plug into the formula without thinking about it too much,
we get

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle\leq\int_{0}^{n}\frac{1}{(1-p)t}\,dt=\frac{1}{1-p}(\ln n-\ln
0).$

That $\ln 0$ is trouble. We can fix it by making $\mu(n)=(1-p)\lceil n\rceil$,
to get

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle\leq\int_{0+}^{n}\frac{1}{(1-p)\lceil t\rceil}\,dt$
$\displaystyle=\frac{1}{1-p}\sum_{k=1}^{n}\frac{1}{k}$
$\displaystyle=\frac{H_{n}}{1-p}.$

####  G.3.4 Coupon collector

Now that we know how to avoid dividing by zero, this is easy and fun. Let
$\mu(x)=\lceil x\rceil/n$, then we have

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle\leq\int_{0+}^{n}\frac{n}{\lceil t\rceil}\,dt$
$\displaystyle=\sum_{k=1}^{n}\frac{n}{k}$ $\displaystyle=nH_{n}.$

As it happens, this is the exact answer for this case. This will happen
whenever $X$ is always a 0–1 variable111A 0–1 random variable is also called a
Bernoulli random variable, but 0–1 is shorter to type and more informative.
Even more confusing, the underlying experiment that gives rise to a Bernoulli
random variable goes by the entirely different name of a Poisson trial. Jacob
Bernoulli and Siméon-Denis Poisson were great mathematicians, but there are
probably better ways to remember them. and we define
$\mu(x)=\operatorname{E}\left[{X}\;\middle|\;{n=\lceil x\rceil}\right]$, which
can be seen by spending far too much time thinking about the precise sources
of error in the inequalities in the proof.

####  G.3.5 Chutes and ladders

Let $\mu(n)$ be the expected drop from position $n$. We have to be a little
bit careful about small $n$, but we can compute that in general
$\mu(n)=\frac{1}{6}\sum_{i=0}^{\min(n,6)}i$. For fractional values $x$ we will
set $\mu(x)=\mu(\lceil x\rceil)$ as before. Then we have

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle\leq\int_{0+}^{n}\frac{1}{\mu(t)}\,dt$
$\displaystyle=\sum_{k=1}^{n}\frac{1}{\mu(k)}$

We can summarize the values in the following table:

$\displaystyle\begin{array}[]{llll}n&\mu(n)&1/\mu(n)&\sum 1/\mu(k)\\\
1&1/6&6&6\\\ 2&1/2&2&8\\\ 3&1&1&9\\\ 4&5/3&3/5&48/5\\\ 5&5/2&2/5&10\\\ \geq
6&7/2&2/7&10+(2/7)(n-5)=(2/7)n+65/7\\\ \end{array}$

This is a slight overestimate; for example, we can calculate by hand that the
expected waiting time for $n=2$ is $6$ and for $n=3$ that it is $20/3=6+2/3$.

We can also consider the generalized version of the game where we start at $n$
and drop by $1\dots n$ each turn as long as the drop wouldn’t take us below 0.
Now the expected drop from position $k$ is $k(k+1)/2n$, and so we can apply
the formula to get

$\displaystyle\operatorname{E}\left[{T(n)}\right]$
$\displaystyle\leq\sum_{k=1}^{n}\frac{2n}{k(k+1)}.$

The sum of $\frac{1}{k(k+1)}$ when $k$ goes from $1$ to $n$ happens to have a
very nice value; it’s exactly $\frac{n}{n+1}=1+\frac{1}{n+1}$.222Proof:
Trivially true for $n=0$; for larger $n$, compute
$\sum_{k=1}^{n}\frac{1}{k(k+1)}\sum_{k=1}^{n-1}\frac{1}{k(k+1)}+\frac{1}{n(n+1)}=\frac{n-1}{n}+\frac{1}{n(n+1)}=\frac{(n-1)(n+1)-1}{n(n+1)}=\frac{n^{2}}{n(n+1)}=n/(n+1)$.
So in this case we can rewrite the bound as
$2n\cdot\frac{n}{n+1}=\frac{2n^{2}}{n+1}$.

###  G.4 High-probability bounds

So far we have only considered bounds on the expected value of $T(n)$. Suppose
we want to show that $T(n)$ is in fact small with high probability, i.e., a
statement of the form $\Pr\left[{T(n)\geq t}\right]\leq\epsilon$. There are
two natural ways to do this: we can repeatedly apply Markov’s inequality to
the expectation bound, or we can attempt to analyze the recurrence in more
detail. The first method tends to give weaker bounds but it’s easier.

####  G.4.1 High-probability bounds from expectation bounds

Given $\operatorname{E}\left[{T(n)}\right]\leq m$, we have
$\Pr\left[{T(n)\geq\alpha m}\right]\leq\alpha^{-1}$. This does not give a very
good bound on probability; if we want to show $\Pr\left[{T(n)\geq
t}\right]\leq n^{-c}$ for some constant $c$ (a typical high-probability
bound), we need $t\geq n^{c}m$. But we can get a better bound if $m$ bounds
the expected time starting from any reachable state, as is the case for the
class of problems we have been considering.

The idea is that if $T(n)$ exceeds $\alpha m$, we restart the analysis and
argue that $\Pr\left[{T(n)\geq 2\alpha m}\;\middle|\;{T(n)\geq\alpha
m}\right]\leq\alpha^{-1}$, from which it follows that $\Pr\left[{T(n)\geq
2\alpha m}\right]\leq\alpha^{-2}$. In general, for any non-negative integer
$k$, we have $\Pr\left[{T(n)\geq k\alpha m}\right]\leq\alpha^{-k}$. Now we
just need to figure out how to pick $\alpha$ to minimize this quantity for
fixed $t$.

Let $t=k\alpha m$. Then $k=t/\alpha m$ and we seek to minimize
$\alpha^{-t/\alpha m}$. Taking the logarithm gives $-(t/m)(\ln\alpha)/\alpha$.
The $t/m$ factor is irrelevant to the minimization problem, so we are left
with minimizing $-(\ln\alpha)/\alpha$. Taking the derivative gives
$-\alpha^{-2}+\alpha^{-2}\ln\alpha$; this is zero when $\ln\alpha=1$ or
$\alpha=e$. (This popular constant shows up often in problems like this.) So
we get $\Pr\left[{T(n)\geq kem}\right]\leq e^{-k}$, or, letting
$k=\ln(1/\epsilon)$, $\Pr\left[{T(n)\geq
em\ln(1/\epsilon)}\right]\leq\epsilon$.

So, for example, we can get an $n^{-c}$ bound on the probability of running
too long by setting our time bound to $em\ln(n^{c})=cem\ln n=O(m\log n)$. We
can’t hope to do better than $O(m)$, so this bound is tight up to a log
factor.

####  G.4.2 Detailed analysis of the recurrence

As Lance Fortnow has explained,333http://weblog.fortnow.com/2009/01/soda-and-
me.html getting rid of log factors is what theoretical computer science is all
about. So we’d like to do better than an $O(m\log n)$ bound if we can. In some
cases this is not too hard.

Suppose for each $n$, $T(n)=1+T(X)$, where
$\operatorname{E}\left[{X}\right]\leq\alpha n$ for a fixed constant $\alpha$.
Let $X_{0}=n$, and let $X_{1},X_{2}$, etc., be the sequence of sizes of the
remaining problem at time 1, 2, etc. Then we have
$\operatorname{E}\left[{X_{1}}\right]\leq\alpha n$ from our assumption. But we
also have
$\operatorname{E}\left[{X_{2}}\right]=\operatorname{E}\left[{\operatorname{E}\left[{X_{2}}\;\middle|\;{X_{1}}\right]}\right]\leq\operatorname{E}\left[{\alpha
X_{1}}\right]=\alpha\operatorname{E}\left[{X_{1}}\right]\leq\alpha^{2}n$, and
by induction we can show that
$\operatorname{E}\left[{X_{k}}\right]\leq\alpha^{k}n$ for all $k$. Since
$X_{k}$ is integer-valued, $\operatorname{E}\left[{X_{k}}\right]$ is an upper
bound on $\Pr\left[{X_{k}>0}\right]$; we thus get $\Pr\left[{T(n)\geq
k}\right]=\Pr\left[{X_{k}>0}\right]\leq\alpha^{k}n$. We can solve for the
value of $k$ that makes this less than $\epsilon$:
$k=-\log(n/\epsilon)/\log\alpha=\log_{1/\alpha}n+\log_{1/\alpha}(1/\epsilon)$.

For comparison, the bound on the expectation of $T(n)$ from Lemma G.3.1 is
$H(n)/(1-\alpha)$. This is actually pretty close to $\log_{1/\alpha}n$ when
$\alpha$ is close to 1, and is not too bad even for smaller $\alpha$. But the
difference is that the dependence on $\log(1/\epsilon)$ is additive with the
tighter analysis, so for fixed $c$ we get $\Pr\left[{T(n)\geq t}\right]\leq
n^{-c}$ at $t=O(\log n+\log n^{c})=O(\log n)$ instead of $O(\log n\log
n^{c})=O(\log^{2}n)$.

###  G.5 More general recurrences

We didn’t do these, but if we had to, it might be worth looking at Roura’s
Improved Master Theorems [Rou01].

## Bibliography

  * [AA11] Dan Alistarh and James Aspnes.  Sub-logarithmic test-and-set against a weak adversary.  In Distributed Computing: 25th International Symposium, DISC 2011, volume 6950 of Lecture Notes in Computer Science, pages 97–109. Springer-Verlag, September 2011.
  * [AACH12] James Aspnes, Hagit Attiya, and Keren Censor-Hillel.  Polylogarithmic concurrent data structures from monotone circuits.  Journal of the ACM, 59(1):2:1–2:24, February 2012.
  * [AAG+10] Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui.  Fast randomized test-and-set and renaming.  In Nancy A. Lynch and Alexander A. Shvartsman, editors, Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, volume 6343 of Lecture Notes in Computer Science, pages 94–108. Springer, 2010.
  * [ABMRT96] Arne Andersson, Peter Bro Miltersen, Søren Riis, and Mikkel Thorup.  Static dictionaries on AC${}^{\mbox{0}}$ RAMs: Query time $\theta(\sqrt{\log n/\log\log n})$ is necessary and sufficient.  In FOCS, pages 441–450, 1996.
  * [Abr88] Karl Abrahamson.  On achieving consensus using a shared memory.  In Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms, pages 291–302, 1988.
  * [AC08] Hagit Attiya and Keren Censor.  Tight bounds for asynchronous randomized consensus.  Journal of the ACM, 55(5):20, October 2008.
  * [ACBF02] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  Machine Learning, 47:235–256, 2002.
  * [Ach03] Dimitris Achlioptas.  Database-friendly random projections: Johnson-Lindenstrauss with binary coins.  J. Comput. Syst. Sci., 66(4):671–687, June 2003.
  * [Adl78] Leonard Adleman.  Two theorems on random polynomial time.  In Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pages 75–83, Washington, DC, USA, 1978. IEEE Computer Society.
  * [AE19] James Aspnes and He Yang Er.  Consensus with max registers.  In Jukka Suomela, editor, 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:9, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [AF01] David Aldous and James Allen Fill.  Reversible Markov chains and random walks on graphs.  Unpublished manuscript, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html, 2001.
  * [AH90] James Aspnes and Maurice Herlihy.  Fast randomized consensus using shared memory.  Journal of Algorithms, 11(3):441–461, September 1990.
  * [AKS83] M. Ajtai, J. Komlós, and E. Szemerédi.  An O(n log n) sorting network.  In STOC ’83: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pages 1–9, New York, NY, USA, 1983. ACM.
  * [AKS04] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  PRIMES is in P.  Annals of Mathematics, 160:781–793, 2004.
  * [Alo91] Noga Alon.  A parallel algorithmic version of the local lemma.  Random Structures & Algorithms, 2(4):367–378, 1991.
  * [AS92] Noga Alon and Joel H. Spencer.  The Probabilistic Method.  John Wiley & Sons, 1992.
  * [AS07] James Aspnes and Gauri Shah.  Skip graphs.  ACM Transactions on Algorithms, 3(4):37, November 2007.
  * [Asp15] James Aspnes.  Faster randomized consensus with an oblivious adversary.  Distributed Computing, 28(1):21–29, February 2015.
  * [AVL62] G. M. Adelson-Velskii and E. M. Landis.  An information organization algorithm.  Doklady Akademia Nauk SSSR, 146:263–266, 1962.
  * [AW96] James Aspnes and Orli Waarts.  Randomized consensus in $O(n\log^{2}n)$ operations per processor.  SIAM Journal on Computing, 25(5):1024–1044, October 1996.
  * [Azu67] Kazuoki Azuma.  Weighted sums of certain dependent random variables.  Tôhoku Mathematical Journal, 19(3):357–367, 1967.
  * [Bab79] László Babai.  Monte-carlo algorithms in graph isomorphism testing.  Technical Report D.M.S. 79-10, Université de Montréal, 1979.
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM J. Comput., 26(5):1510–1523, October 1997.
  * [BCB12] Sébastian Bubeck and Nicolò Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends in Machine Learning, 5(1):1–122, 2012.
  * [BD92] Dave Bayer and Persi Diaconis.  Trailing the dovetail shuffle to its lair.  Annals of Applied Probability, 2(2):294–313, 1992.
  * [Bec91] József Beck.  An algorithmic approach to the lovász local lemma. i.  Random Structures & Algorithms, 2(4):343–365, 1991.
  * [Bel57] Richard Earnest Bellman.  Dynamic Programming.  Princeton University Press, 1957.
  * [Blo70] Burton H. Bloom.  Space/time trade-offs in hash coding with allowable errors.  Commun. ACM, 13(7):422–426, 1970.
  * [Bol01] Béla Bollobás.  Random Graphs.  Cambridge University Press, second edition, 2001.
  * [BR91] Gabriel Bracha and Ophir Rachman.  Randomized consensus in expected $O(n^{2}\log n)$ operations.  In Sam Toueg, Paul G. Spirakis, and Lefteris M. Kirousis, editors, Distributed Algorithms, 5th International Workshop, volume 579 of Lecture Notes in Computer Science, pages 143–150, Delphi, Greece, 7–9 October 1991. Springer, 1992.
  * [Bro86] Andrei Z. Broder.  How hard is to marry at random? (on the approximation of the permanent).  In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 28-30 May 1986, Berkeley, California, USA, pages 50–58, 1986.
  * [Bro88] Andrei Z. Broder.  Errata to “how hard is to marry at random? (on the approximation of the permanent)”.  In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 2-4 May 1988, Chicago, Illinois, USA, page 551, 1988.
  * [BRSW06] Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson.  2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, STOC ’06, pages 671–680, New York, NY, USA, 2006. ACM.
  * [CCFC04] Moses Charikar, Kevin Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  Theor. Comput. Sci., 312(1):3–15, 2004.
  * [CM03] Saar Cohen and Yossi Matias.  Spectral bloom filters.  In Alon Y. Halevy, Zachary G. Ives, and AnHai Doan, editors, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pages 241–252, 2003.
  * [CM05] Graham Cormode and S. Muthukrishnan.  An improved data stream summary: the count-min sketch and its applications.  J. Algorithms, 55(1):58–75, 2005.
  * [CMV13] Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan.  Why simple hash functions work: Exploiting the entropy in a data stream.  Theory of Computing, 9(1):897–945, 2013.
  * [CS00] Artur Czumaj and Christian Scheideler.  Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma.  In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, SODA ’00, pages 30–39, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics.
  * [CW77] J. Lawrence Carter and Mark N. Wegman.  Universal classes of hash functions (extended abstract).  In Proceedings of the ninth annual ACM symposium on Theory of computing, STOC ’77, pages 106–112, New York, NY, USA, 1977. ACM.
  * [Deu89] David Deutsch.  Quantum computational networks.  Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 425(1868):73–90, 1989.
  * [Dev88] Luc Devroye.  Applications of the theory of records in the study of random trees.  Acta Informatica, 26(1-2):123–130, October 1988.
  * [DGM02] Martin Dyer, Catherine Greenhill, and Mike Molloy.  Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs.  Random Struct. Algorithms, 20:98–114, January 2002.
  * [DHKP97] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen.  A reliable randomized algorithm for the closest-pair problem.  J. Algorithms, 25(1):19–51, 1997.
  * [Dir39] P. A. M. Dirac.  A new notation for quantum mechanics.  Mathematical Proceedings of the Cambridge Philosophical Society, 35:416–418, 6 1939.
  * [DJ92] David Deutsch and Richard Jozsa.  Rapid solution of problems by quantum computation.  Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558, 1992.
  * [Dum56] A. I. Dumey.  Indexing for rapid random-access memory.  Computers and Automation, 5(12):6–9, 1956.
  * [Dye03] Martin Dyer.  Approximate counting by dynamic programming.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, STOC ’03, pages 693–699, New York, NY, USA, 2003. ACM.
  * [EL75] Paul Erdős and Laszlo Lovász.  Problems and results on 3-chromatic hypergraphs and some related questions.  In A. Hajnal, R. Rado, and V. T. Sós, editors, Infinite and Finite Sets (to Paul Erdős on his 60th birthday), pages 609–627. North-Holland, 1975.
  * [Epp16] David Eppstein.  Cuckoo filter: Simplification and analysis.  In Rasmus Pagh, editor, 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016, June 22-24, 2016, Reykjavik, Iceland, volume 53 of LIPIcs, pages 8:1–8:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
  * [Erd45] P. Erdős.  On a lemma of Littlewood and Offord.  Bulletin of the American Mathematical Society, 51(12):898–902, 1945\.
  * [Erd47] P. Erdős.  Some remarks on the theory of graphs.  Bulletin of the American Mathematical Society, 53:292–294, 1947\.
  * [ES35] P. Erdős and G. Szekeres.  A combinatorial problem in geometry.  Compositio Mathematica, 2:463–470, 1935.
  * [Eul68] M. L. Euler.  Remarques sur un beau rapport entre les séries des pussances tant directes que réciproques.  Mémoires de l’Académie des Sciences de Berlin, 17:83–106, 1768\.
  * [FAKM14] Bin Fan, David G. Andersen, Michael Kaminsky, and Michael Mitzenmacher.  Cuckoo filter: Practically better than bloom.  In Aruna Seneviratne, Christophe Diot, Jim Kurose, Augustin Chaintreau, and Luigi Rizzo, editors, Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, CoNEXT 2014, Sydney, Australia, December 2-5, 2014, pages 75–88. ACM, 2014.
  * [FCAB00] Li Fan, Pei Cao, Jussara M. Almeida, and Andrei Z. Broder.  Summary cache: a scalable wide-area web cache sharing protocol.  IEEE/ACM Trans. Netw., 8(3):281–293, 2000.
  * [Fel68] William Feller.  An Introduction to Probability Theory and Its Applications, volume 1.  Wiley, third edition, 1968.
  * [Fel71] William Feller.  An Introduction to Probability Theory and Its Applications, volume 2.  Wiley, second edition, 1971.
  * [FGQ12] Xiequan Fan, Ion Grama, and Liu Quansheng.  Hoeffding’s inequality for supermartingales.  Available as http://arxiv.org/abs/1109.4359, July 2012.
  * [FKS84] M.L. Fredman, J. Komlós, and E. Szemerédi.  Storing a Sparse Table with O(1) Worst Case Access Time.  Journal of the ACM (JACM), 31(3):538–544, 1984.
  * [FLP85] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.  Impossibility of distributed consensus with one faulty process.  Journal of the ACM, 32(2):374–382, April 1985.
  * [FNM85] Philippe Flajolet and G Nigel Martin.  Probabilistic counting algorithms for data base applications.  Journal of computer and system sciences, 31(2):182–209, 1985.
  * [FPSS03] Dimitris Fotakis, Rasmus Pagh, Peter Sanders, and Paul Spirakis.  Space efficient hash tables with worst case constant access time.  In Helmut Alt and Michel Habib, editors, STACS 2003, volume 2607 of Lecture Notes in Computer Science, pages 271–282. Springer Berlin Heidelberg, 2003.
  * [FR75] Robert W. Floyd and Ronald L. Rivest.  Expected time bounds for selection.  Commun. ACM, 18(3):165–172, 1975.
  * [GKP88] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete Mathematics: A Foundation for Computer Science.  Addison-Wesley, 1988.
  * [Goo83] Nelson Goodman.  Fact, Fiction, and Forecast.  Harvard University Press, 1983.
  * [GR93] Igal Galperin and Ronald L. Rivest.  Scapegoat trees.  In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 165–174. Society for Industrial and Applied Mathematics, 1993.
  * [Gro96] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219. ACM, 1996.  Available as http://arxiv.org/abs/quant-ph/9605043.
  * [GS78] Leo J. Guibas and Robert Sedgewick.  A dichromatic framework for balanced trees.  In Foundations of Computer Science, 1978., 19th Annual Symposium on, pages 8–21. IEEE, 1978.
  * [GS92] G. R. Grimmet and D. R. Stirzaker.  Probability and Random Processes.  Oxford Science Publications, second edition, 1992.
  * [GS01] Geoffrey R. Grimmett and David R. Stirzaker.  Probability and Random Processes.  Oxford University Press, third edition, 2001.
  * [Gur00] Venkatesen Guruswami.  Rapidly mixing Markov chains: A comparison of techniques.  Available at ftp://theory.lcs.mit.edu/pub/people/venkat/markov-survey.ps, 2000.
  * [GW94] Michel X. Goemans and David P. Williamson.  New $3/4$-approximation algorithms for the maximum satisfiability problem.  SIAM J. Discret. Math., 7:656–666, November 1994.
  * [GW95] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  Journal of the ACM, 42(6):1115–1145, 1995.
  * [GW12] George Giakkoupis and Philipp Woelfel.  On the time and space complexity of randomized test-and-set.  In Darek Kowalski and Alessandro Panconesi, editors, ACM Symposium on Principles of Distributed Computing, PODC ’12, Funchal, Madeira, Portugal, July 16-18, 2012, pages 19–28. ACM, 2012.
  * [Has70] W. K. Hastings.  Monte carlo sampling methods using Markov chains and their applications.  Biometrika, 57(1):97–109, 1970.
  * [HH80] P. Hall and C.C. Heyde.  Martingale Limit Theory and Its Application.  Academic Press, 1980.
  * [HK73] John E. Hopcroft and Richard M. Karp.  An n${}^{\mbox{5/2}}$ algorithm for maximum matchings in bipartite graphs.  SIAM J. Comput., 2(4):225–231, 1973.
  * [Hoa61a] C. A. R. Hoare.  Algorithm 64: Quicksort.  Commun. ACM, 4:321, July 1961.
  * [Hoa61b] C. A. R. Hoare.  Algorithm 65: find.  Commun. ACM, 4:321–322, July 1961.
  * [Hoe63] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  Journal of the American Statistical Association, 58(301):13–30, March 1963.
  * [Hol16] Jonathan Holmes.  AI is already making inroads into journalism but could it win a Pulitzer?  https://www.theguardian.com/media/2016/apr/03/artificla-intelligence-robot-reporter-pulitzer-prize, April 2016.  Accessed September 18th, 2016.
  * [HST08] Maurice Herlihy, Nir Shavit, and Moran Tzafrir.  Hopscotch hashing.  In Proceedings of the 22nd international symposium on Distributed Computing, DISC ’08, pages 350–364, Berlin, Heidelberg, 2008. Springer-Verlag.
  * [IM98] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: Towards removing the curse of dimensionality.  In STOC, pages 604–613, 1998.
  * [JL84] William B. Johnson and Joram Lindenstrauss.  Extensions of Lipschitz mappings into a Hilbert space.  In Conference in Modern Analysis and Probability (New Haven, Connecticut, 1982), number 26 in Contemporary Mathematics, pages 189–206. American Mathematical Society, 1984.
  * [JLR00] Svante Janson, Tomasz Łuczak, and Andrezej Ruciński.  Random Graphs.  John Wiley & Sons, 2000.
  * [JS89] Mark Jerrum and Alistair Sinclair.  Approximating the permanent.  SIAM J. Comput., 18(6):1149–1178, 1989.
  * [JSV04] Mark Jerrum, Alistair Sinclair, and Eric Vigoda.  A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.  J. ACM, 51(4):671–697, 2004.
  * [Kar93] David R. Karger.  Global min-cuts in rnc, and other ramifications of a simple min-out algorithm.  In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, SODA ’93, pages 21–30, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics.
  * [KL85] Richard M. Karp and Michael Luby.  Monte-carlo algorithms for the planar multiterminal network reliability problem.  J. Complexity, 1(1):45–64, 1985.
  * [KM08] Adam Kirsch and Michael Mitzenmacher.  Less hashing, same performance: Building a better bloom filter.  Random Struct. Algorithms, 33(2):187–218, 2008.
  * [KNW10] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  An optimal algorithm for the distinct elements problem.  In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’10, pages 41–52, New York, NY, USA, 2010. ACM.
  * [Kol33] A.N. Kolmogorov.  Grundbegriffe der Wahrscheinlichkeitsrechnung.  Springer, 1933.
  * [KR99] V. S. Anil Kumar and H. Ramesh.  Markovian coupling vs. conductance for the Jerrum-Sinclair chain.  In FOCS, pages 241–252, 1999.
  * [KS76] J.G. Kemeny and J.L. Snell.  Finite Markov Chains: With a New Appendix “Generalization of a Fundamental Matrix”.  Undergraduate Texts in Mathematics. Springer, 1976.
  * [KSK76] John G. Kemeny, J. Laurie. Snell, and Anthony W. Knapp.  Denumerable Markov Chains, volume 40 of Graduate Texts in Mathematics.  Springer, 1976.
  * [KT75] Samuel Karlin and Howard M. Taylor.  A First Course in Stochastic Processes.  Academic Press, second edition, 1975.
  * [KUW88] Richard M. Karp, Eli Upfal, and Avi Wigderson.  The complexity of parallel search.  Journal of Computer and System Sciences, 36(2):225–253, 1988.
  * [LAA87] Michael C. Loui and Hosame H. Abu-Amara.  Memory requirements for agreement among unreliable asynchronous processes.  Advances in Computing Research, pages 163–183, 1987.
  * [Li80] Shuo-Yen Robert Li.  A martingale approach to the study of occurrence of sequence patterns in repeated experiments.  Annals of Probability, 8(6):1171–1176, 1980.
  * [Lin92] Torgny Lindvall.  Lectures on the Coupling Method.  Wiley, 1992.
  * [LPW09] David A. Levin, Yuval Peres, and Elizabeth L. Wimmer.  Markov Chains and Mixing Times.  American Mathematical Society, 2009.
  * [LR85] T. L. Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  Advances in Applied Mathematics, 6(1):4–22, March 1985.
  * [Lub85] Michael Luby.  A simple parallel algorithm for the maximal independent set problem.  In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 1–10, New York, NY, USA, 1985. ACM.
  * [LW05] Michael Luby and Avi Wigderson.  Pairwise independence and derandomization.  Foundations and Trends in Theoretical Computer Science, 1(4):237–301, 2005.
  * [McC85] Edward M. McCreight.  Priority search trees.  SIAM J. Comput., 14(2):257–276, 1985.
  * [McD89] Colin McDiarmid.  On the method of bounded differences.  In Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference, pages 148–188, 1989.
  * [MH92] Colin McDiarmid and Ryan Hayward.  Strong concentration for Quicksort.  In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete algorithms, SODA ’92, pages 414–421, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics.
  * [Mil76] Gary L. Miller.  Riemann’s hypothesis and tests for primality.  Journal of Computer and System Sciences, 13(3):300–317, 1976.
  * [ML86] Lothar F. Mackert and Guy M. Lohman.  R* optimizer validation and performance evaluation for distributed queries.  In Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, and Yahiko Kambayashi, editors, VLDB’86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings, pages 149–159. Morgan Kaufmann, 1986.
  * [MN98] Makoto Matsumoto and Takuji Nishimura.  Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator.  ACM Trans. Model. Comput. Simul., 8:3–30, January 1998.
  * [Mos09] Robin A. Moser.  A constructive proof of the Lovász local lemma.  In Proceedings of the 41st annual ACM Symposium on Theory of Computing, STOC ’09, pages 343–350, New York, NY, USA, 2009. ACM.
  * [MR95] Rajeev Motwani and Prabhakar Raghavan.  Randomized Algorithms.  Cambridge University Press, 1995.
  * [MR98] Michael Molloy and Bruce Reed.  Further algorithmic aspects of the local lemma.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC ’98, pages 524–529, New York, NY, USA, 1998. ACM.
  * [MRR+53] Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller.  Equation of state calculations by fast computing machines.  J. Chem. Phys., 21(6):1087–1092, 1953.
  * [MT05] Ravi Montenegro and Prasad Tetali.  Mathematical aspects of mixing times in markov chains.  Foundations and Trends in Theoretical Computer Science, 1(3), 2005\.
  * [MT10] Robin A. Moser and Gábor Tardos.  A constructive proof of the general Lovász local lemma.  J. ACM, 57:11:1–11:15, February 2010.
  * [MU05] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis.  Cambridge University Press, 2005.
  * [Mun11] Randall Munroe.  Sports.  http://xkcd.com/904/, 2011.  Accessed September 18th, 2016.
  * [Pag01] Rasmus Pagh.  On the cell probe complexity of membership and perfect hashing.  In STOC, pages 425–432, 2001.
  * [Pag06] Rasmus Pagh.  Cuckoo hashing for undergraduates.  Available at http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf, 2006.
  * [Pap91] Christos H. Papadimitriou.  On selecting a satisfying truth assignment (extended abstract).  In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 163–169. IEEE Computer Society, 1991.
  * [PPR05] Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao.  An optimal bloom filter replacement.  In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 823–829. SIAM, 2005.
  * [PR04] Rasmus Pagh and Flemming Friche Rodler.  Cuckoo hashing.  J. Algorithms, 51(2):122–144, 2004.
  * [PSL80] M. Pease, R. Shostak, and L. Lamport.  Reaching agreement in the presence of faults.  Journal of the ACM, 27(2):228–234, April 1980.
  * [PT12] Mihai Patrascu and Mikkel Thorup.  The power of simple tabulation hashing.  J. ACM, 59(3):14, 2012.
  * [Pug90] William Pugh.  Skip Lists: A Probabilistic Alternative to Balanced Trees.  Communications of the ACM, 33(6):668–676, June 1990.
  * [Rab80] Michael O Rabin.  Probabilistic algorithm for testing primality.  Journal of Number Theory, 12(1):128–138, 1980.
  * [Rag88] Prabhakar Raghavan.  Probabilistic construction of deterministic algorithms: approximating packing integer programs.  J. Comput. Syst. Sci., 37:130–143, October 1988.
  * [Rou01] Salvador Roura.  Improved master theorems for divide-and-conquer recurrences.  J. ACM, 48:170–205, March 2001.
  * [RT87] Prabhakar Raghavan and Clark D. Tompson.  Randomized rounding: a technique for provably good algorithms and algorithmic proofs.  Combinatorica, 7:365–374, December 1987.
  * [SA96] Raimund Seidel and Cecilia R. Aragon.  Randomized search trees.  Algorithmica, 16(4/5):464–497, 1996.  Available at http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf.
  * [She11] Irina Shevtsova.  On the asymptotically exact constants in the Berry-Esseen-Katz inequality.  Theory of Probability & Its Applications, 55(2):225–252, 2011\.  A preprint is available at http://arxiv.org/pdf/1111.6554.pdf.
  * [Sho97] Peter W Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM journal on computing, 26(5):1484–1509, 1997.
  * [Spu12] Francis Spufford.  Red Plenty.  Graywolf Press, 2012.
  * [Sri08] Aravind Srinivasan.  Improved algorithmic versions of the Lovász local lemma.  In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’08, pages 611–620, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics.
  * [SS71] A. Schönhage and V. Strassen.  Schnelle multiplikation großer zahlen.  Computing, 7(3–4):281–292, 1971.
  * [SS87] E. Shamir and J. Spencer.  Sharp concentration of the chromatic number on random graphs $G_{n,p}$.  Combinatorica, 7:121–129, January 1987.
  * [Str03] Gilbert Strang.  Introduction to linear algebra.  Wellesley-Cambridge Press, 2003.
  * [SW13] Dennis Stanton and Dennis White.  Constructive Combinatorics.  Undergraduate Texts in Mathematics. Springer, 2013.
  * [Tod91] Seinosuke Toda.  Pp is as hard as the polynomial-time hierarchy.  SIAM J. Comput., 20(5):865–877, 1991.
  * [Tof80] Tommaso Toffoli.  Reversible computing.  Technical Report MIT/LCS/TM-151, MIT Laboratory for Computer Science, 1980\.
  * [Val79] Leslie G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.
  * [Val82] Leslie G. Valiant.  A scheme for fast parallel communication.  SIAM J. Comput., 11(2):350–361, 1982.
  * [VB81] Leslie G. Valiant and Gordon J. Brebner.  Universal schemes for parallel communication.  In STOC, pages 263–277. ACM, 1981.
  * [Vui80] Jean Vuillemin.  A unifying look at data structures.  Communications of the ACM, 23(4):229–239, 1980.
  * [VV86] Leslie G. Valiant and Vijay V. Vazirani.  Np is as easy as detecting unique solutions.  Theor. Comput. Sci., 47(3):85–93, 1986.
  * [Wil04] David Bruce Wilson.  Mixing times of lozenge tiling and card shuffling Markov chains.  Annals of Applied Probability, 14(1):274–325, 2004.
  * [Wil06] Herbert S. Wilf.  generatingfunctionology.  A. K. Peters, third edition, 2006.  Second edition is available on-line at http://www.math.penn.edu/~wilf/DownldGF.html.
  * [WNC87] Ian H. Witten, Radford M. Neal, and John G. Cleary.  Arithmetic coding for data compression.  Communications of the ACM, 30(6):520–540, 1987.
  * [Yao77] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In 18th Annual Symposium on Foundations of Computer Science, pages 222–227. IEEE, 1977.
  * [Zur03] Wojciech Hubert Zurek.  Decoherence, einselection, and the quantum origins of the classical.  Rev. Mod. Phys., 75:715–775, May 2003.

## Index

  * $(r_{1},r_{2},p_{1},p_{2})$-sensitive Definition 7.7.1
  * #DNF §10.1, §10.3
  * #P §10.1
  * #SAT §10.1
  * 0–1 random variable footnote 1
  * $2$-coloring §11.3.3.3
  * 2-universal §7.2
  * $3$-way cut §E.3.3
  * absolute value footnote 2
  * adapted §5.3.2, footnote 6
  * adapted sequence of random variables item 1
  * adaptive adversary Chapter 14, §6.3.1
  * Adleman’s theorem §12.2
  * adversary Chapter 14
    * adaptive Chapter 14, §6.3.1
    * oblivious Chapter 14, §6.3.1
  * advice §12.2
  * agreement §14.1
  * Aldous-Fill manuscript §9.4
  * algorithm
    * Deutsch’s §13.4
    * distributed Chapter 14
    * UCB1 §5.3.4.5
  * algorithmic information theory footnote 1
  * amplitude
    * probability Chapter 13
  * ancestor item 1
    * common item 2
  * annealing schedule §9.4.5.2
  * anti-concentration bound §5.5
  * aperiodic §9.2.5
  * approximation algorithm §11.2.2
  * approximation ratio §11.2.2
  * approximation scheme
    * fully polynomial-time §10.4
    * fully polynomial-time randomized Chapter 10
  * arithmetic coding 2nd item, §10.2.1
  * arm §5.3.4.5
  * Atari 2600 §B.3.1
  * augmenting path §9.5.8.4
  * average-case analysis Chapter 1
  * AVL tree §6.1.1
  * avoiding worst-case inputs 1st item
  * axioms of probability §2.1.1
  * Azuma-Hoeffding inequality §5.3
  * Azuma’s inequality §5.3, §5.3.2
  * balanced §6.1
  * bandit
    * multi-armed §5.3.4.5
  * Bernoulli random variable footnote 1, §3.4.1
  * Berry-Esseen theorem §5.5.1
  * biased random walk §8.5.1
  * binary search tree §6.1
    * balanced §6.1
  * binary tree §6.1
  * binomial random variable §3.4.1
  * bipartite graph §9.5.8.4
  * bit-fixing routing §5.2.7.4, §9.5.8.2
  * Bloom filter §E.6.3, §7.6.1
    * counting §7.6.5
    * spectral §7.6.5
  * Bloomjoin §7.6.4
  * bounded difference property §5.3.3
  * bowling §D.3.1
  * bra §13.2
  * bra-ket notation §13.2
  * branching process §11.3.5
  * bubble sort §B.1.1
  * Byzantine processes Chapter 14
  * canonical paths §9.5.6
  * Catalan number footnote 1
  * causal coupling footnote 11
  * CCNOT §13.3.2
  * central limit theorem §5.4
  * chaining §7.1
  * Chapman-Kolmogorov equation §9.1
  * Chebyshev’s inequality §5.1
  * Cheeger constant §9.5.4
  * Cheeger inequality §9.5.4
  * chromatic number §5.3.4.2
  * Chutes and Ladders 5th item
  * circuit
    * quantum Chapter 13, §13.3
    * random §13.1
  * clause §10.3, §11.2.2, §11.3.3.2
  * clique footnote 1
  * closed loop §7.4.2
  * CLT §5.4
  * CNOT §13.3.2
  * coin
    * weak shared item 1
  * collision 3rd item, Chapter 7, §7.1
  * coloring
    * hypergrah §11.3.3.3
  * common ancestor item 2
  * common subsequence §E.3.1
  * complement §2.1
  * complex conjugate §13.2
  * computation
    * randomized §13.1
  * computation path §12.1
  * computation tree §12.1
  * concave §4.3
  * concentration bound Chapter 5
    * coupon collector problem §9.4.2
  * conditional expectation §1.3.1, §3.5
  * conditional probability §2.3
  * conductance §9.5.4
  * congestion §9.5.7
  * conjugate
    * complex §13.2
  * conjugate transpose §13.2
  * conjunctive normal form §11.2.2
  * consensus §14.1
  * continuous random variable §3.2
  * contraction §2.3.3.2
  * controlled controlled NOT §13.3.2
  * controlled NOT §13.3.2
  * convex §4.3
  * convex function §4.3
  * Cook reduction §10.1
  * count-min sketch §7.6.6, §7.6.6
  * countable additivity §2.1.1
  * countable Markov chain §9.1
  * counting Bloom filter §7.6.5
  * coupling §9.2.4
    * causal footnote 11
    * path §9.4.4
  * Coupling Lemma §9.2.4
  * coupling time §9.4.3, Lemma 9.4.1
  * coupon collector problem 4th item, §3.6.3
    * concentration bounds §9.4.2
  * covariance §3.4.3, §5.1.1.3
  * crash Chapter 14
  * cryptographic hash function 3rd item
  * cryptographically secure pseudorandom generator item 1
  * cryptographically secure pseudorandom number generator item 2
  * Cryptographically-secure pseudorandomness. item 2
  * cuckoo §7.4
  * cuckoo filter §7.6.3
  * cuckoo hash table §7.4
  * cuckoo hashing §7.4
    * $d$-ary §7.4.2
  * cumulative distribution function §3.2
  * curse of dimensionality §7.7.1
  * cut
    * minimum §2.3.3.2
  * cylinder set §2.1.1
  * $d$-ary cuckoo hashing §7.4.2
  * data stream computation §7.6.6
  * dead cat bounce §B.2.1
  * decoherence footnote 3
  * decomposition
    * Doob footnote 12
  * dense §9.5.8.4
  * dependency graph §11.3.4
  * depth
    * tree §C.3.1
  * derandomization Chapter 12
  * detailed balance equations §9.3
  * dictionary §7.1
  * discrete probability space §2.1
  * discrete random variable Chapter 3, §3.3
  * discretization §7.7.1.4
  * disjunctive normal form §10.3
  * distance
    * total variation Definition 9.2.1
  * distributed algorithm Chapter 14
  * distributed algorithms 5th item
  * distributed computing Chapter 14
  * distribution §3.2
    * geometric §3.6.2
    * stationary §9.2.1
  * DNF formula §10.3
  * dominating set §D.7.1, §E.2.1
  * Doob decomposition footnote 12
  * Doob decomposition theorem §8.2
  * Doob martingale §12.4, footnote 13
  * Doob’s martingale inequality §8.5.3
  * double record §C.7.1
  * dovetail shuffle §9.4.3.4
  * drift process §8.2
  * Dungeons and Dragons §B.2.1
  * eigenvalue §9.5.1
  * eigenvector §9.5.1
  * einselection footnote 3
  * entropy §10.2.1
  * equation
    * Wald’s §3.4.3.1
  * Erdős-Szekeres theorem §D.3.2, §E.3.1
  * error budget §4.1
  * Euler-Mascheroni constant §1.3.2
  * event Chapter 2, §2.1
  * events
    * independent §2.2
  * execution log §11.3.5
  * expectation §3.4
    * conditional §3.5
    * conditioned on a random variable §3.5.2
    * conditioned on a $σ$-algebra §3.5.3
    * conditioned on an event §3.5.1
    * iterated
      * law of §3.5.2.2
    * linearity of §3.4.1
  * expected time Chapter 1
  * expected value Chapter 1, §3.4
  * expected worst-case Chapter 1
  * exponential generating function §5.2
  * $ℱ$-measurable §3.5.3
  * false positive §7.6.2
  * filter
    * cuckoo §7.6.3
  * filtration §3.5.3, 2nd item
  * financial analysis §B.2.1
  * Find the Lady §1.1
  * fingerprint 3rd item, §7.6.3
  * fingerprinting 3rd item
  * finite Markov chain §9.1
  * first passage time §9.2.6
  * Flajolet-Martin sketch §D.4.1
  * FPRAS Chapter 10
  * fractional solution footnote 7, §11.2.2
  * Frobenius problem §9.2.5
  * fully polynomial-time approximation scheme §10.4
  * fully polynomial-time randomized approximation scheme Chapter 10
  * function
    * measurable footnote 1
  * futile word search puzzle §D.6.2
  * $G(n,p)$ §5.3.4.2
  * gate
    * Toffoli §13.3.2
  * generated by §3.5.3
  * generating function
    * exponential §5.2
    * probability footnote 5, footnote 3
  * geometric distribution §3.6.2
  * geometric random variable §3.6.2
  * graph
    * bipartite §9.5.8.4
    * random Chapter 3, §5.3.4.2
  * Grover diffusion operator item 2
  * Hadamard operator §13.3.1
  * handwaving §1.3.2, §11.3.5
  * harmonic number §1.3.2
  * hash function 3rd item, §7.1
    * perfect §7.3
    * tabulation §7.2.2
    * universal §7.2
  * hash table 3rd item, §7.1
    * cuckoo §7.4
  * hashing 3rd item
    * cuckoo §7.4
    * hopscotch §7.5
    * locality-sensitive §7.7
  * heap §6.3
  * heavy hitter §7.6.6
  * high probability footnote 1
  * high-probability bound Chapter 1
  * Hoare’s FIND 2nd item, §3.6.4
  * Hoeffding’s inequality §5.3
  * Hoeffding’s lemma §5.3.1
  * homogeneous §9.1
  * hopscotch hashing §7.5
  * hypercube network §5.2.7.4, §5.3.4.1
  * hyperedge §11.3.3.3
  * hypergraph §11.3.3.3
    * $k$-uniform §11.3.3.3
  * inclusion-exclusion formula §2.2
  * independence §2.2
    * of events §2.2
    * of sets of events §2.3.1
    * pairwise §2.3.1
  * independent §2.2, §2.3.1
  * independent events §2.2
  * independent random variables §3.2
  * independent set footnote 1
  * index §7.1
  * indicator random variable §3.2
  * indicator variable §1.3.2
  * inequality
    * Azuma-Hoeffding §5.3
    * Azuma’s §5.3, §5.3.2
    * Chebyshev’s §5.1
    * Cheeger §9.5.4
    * Doob’s martingale §8.5.3
    * Hoeffding’s §5.3
    * Markov’s §4.2
    * McDiarmid’s §5.3.3, Theorem 5.3.4
  * inner product §13.2
  * integer program footnote 7, §11.2.2
  * irreducible §9.2.5
  * iterated expectation
    * law of §3.5.2.2
  * Iverson bracket footnote 2
  * Iverson notation footnote 2
  * Johnson-Lindenstrauss lemma §7.7.1.1
  * joint distribution §3.2
  * joint probability mass function §3.2
  * $k$-CNF formula §11.3.3.2
  * $k$-uniform hypergraph §11.3.3.3
  * $k$-universal §7.2
  * $k$-wise independence §2.3.1
  * Karger’s min-cut algorithm §2.3.3.2
  * Karp-Upfal-Wigderson bound §G.3
  * ket §13.2
  * key §6.1, §7.1
  * KNAPSACK §10.4
  * Kolmogorov extension theorem §2.1.1
  * Las Vegas algorithm 1st item
  * law of iterated expectation §3.5.2.2
  * law of total probability §1.3.1, §2.3.2, §2.3.2
  * lazy Markov chain §9.2.5
  * leader election 5th item, §14.2
  * left spine §6.3.2.2
  * lemma
    * coupling §9.2.4
    * Johnson-Lindenstrauss §7.7.1.1
    * Lovász local §11.3
    * Yao’s §3.6.1
  * length §A.7.2
  * linear program footnote 7, §11.2.2
  * linearity of expectation §1.3.2, §3.4.1
  * Lipschitz function §9.4.5.2
  * literal §11.3.3.2
  * Littlewood-Offord problem §5.5.2
  * load balancing 3rd item
  * load factor §7.1
  * locality-sensitive hashing §7.7
  * loop
    * closed §7.4.2
  * Lovász Local Lemma §11.3
  * magnitude footnote 2
  * Markov chain Chapter 9, §9.1
    * lazy §9.2.5
  * Markov chain Monte Carlo Chapter 9
  * Markov process §9.1
  * Markov’s inequality §4.2
  * martingale §5.3.2, §8.1
    * Doob §12.4
    * vertex exposure §5.3.4.2
  * martingale difference sequence §5.3.2
  * martingale property item 2
  * matching §9.5.8.3
  * matrix
    * stochastic §13.1
    * transition §9.1
    * unitary §13.3.1
  * max register §14.6
  * maximum cut §11.2.1
  * McDiarmid’s inequality §5.3.3, Theorem 5.3.4
  * measurable §3.3, §3.3, §3.5.3
  * measurable function footnote 1
  * measurable sets §2.1.1
  * measure
    * probability Chapter 2
  * measurement §13.1
  * memoryless §9.1
  * message-passing Chapter 14
  * method of bounded differences §5.3.3
  * method of conditional probabilities §12.4
  * Metropolis §9.3.4
  * Metropolis-Hastings
    * convergence §9.4.5.2
  * Metropolis-Hastings algorithm §9.3.4
  * Miller-Rabin primality test §1.2
  * min-cut §2.3.3.2
  * minimum cut §2.3.3.2
  * mixing
    * rapid §9.4.2
  * mixing rate §9.5.2
  * mixing time Chapter 9, §9.2.3
  * moment §5.2
  * moment generating function §5.2
  * Monte Carlo algorithm §1.2, 2nd item
  * Monte Carlo simulation footnote 8
  * multi-armed bandit §5.3.4.5
  * multigraph §2.3.3.2
  * nearest neighbor search §7.7.1
  * network
    * sorting §11.1
  * NNS §7.7.1
  * no-cloning theorem footnote 5
  * non-uniform §12.2
  * norm footnote 2
  * normal form
    * conjunctive §11.2.2
    * disjunctive §10.3
  * notation
    * bra-ket §13.2
  * number
    * Catalan footnote 1
  * number P §10.1
  * objective function footnote 7
  * oblivious adversary Chapter 14, §6.3.1
  * open addressing §7.1
  * operator
    * Grover diffusion item 2
    * Hadamard §13.3.1
  * optimal solution footnote 7
  * optional stopping theorem §8.3
  * outcomes §2.1
  * pairwise independence §5.1.1.3
  * pairwise independent §2.3.1
  * paradox
    * St. Petersburg §3.4.1.1
  * parallel computing Chapter 14
  * partition §2.1
  * path
    * simple footnote 2
  * pending operation Chapter 14
  * perfect hash function §7.3
  * perfect matching §9.5.8.4
  * perfect matchings §10.1
  * period §9.2.5
  * periodic item 5
  * permanent §10.1
  * permutation routing §5.2.7.4
  * Perron-Frobenius theorem §9.5.1
  * pessimistic estimator §12.4
  * phase §13.3.1
  * Physical randomness. item 1
  * physical randomness item 1
  * pivot 1st item
  * PLEB §7.7.1
  * point location in equal balls §7.7.1
  * point query §7.6.6.2
  * points §2.1
  * Poisson trial footnote 1
  * polynomial-time hierarchy §10.1
  * preference §14.1.1
  * primality test
    * Miller-Rabin §1.2
  * probabilistic method 4th item, Chapter 11
  * probabilistic recurrence §5.3.4.4
  * probability §2.1
    * conditional §2.3
    * high footnote 1
    * stationary §9.2.1
  * probability amplification Chapter 12, §12.2
  * probability amplitude Chapter 13
  * probability generating function footnote 5, footnote 3
  * probability mass function §3.2
  * probability measure Chapter 2
  * probability of $A$ conditioned on $B$ §2.3
  * probability of $A$ given $B$ §2.3
  * probability space Chapter 2
    * discrete §2.1
  * probability theory Chapter 2
  * probing §7.1
  * product
    * inner §13.2
    * tensor §13.1
  * pseudorandom generator item 1
    * cryptographically secure item 1
  * pseudorandom number generator item 3
  * puzzle
    * word search §D.6.2
      * futile §D.6.2
  * quantum bit Chapter 13
  * quantum circuit Chapter 13, §13.3
  * quantum computing Chapter 13
  * qubit Chapter 13
  * query
    * point §7.6.6.2
  * QuickSelect 2nd item, §3.6.4
  * QuickSort §1.3, §5.3.4.4
  * radix tree §D.3.3
  * RAM Chapter 1
  * random circuit §13.1
  * random graph Chapter 3, §5.3.4.2
  * random structure 4th item
  * random variable Chapter 1, Chapter 2, Chapter 3
    * Bernoulli §3.4.1
    * binomial §3.4.1
    * discrete Chapter 3, §3.3
    * geometric §3.6.2
    * indicator §3.2
  * random walk §8.5.1
    * biased §8.5.1
    * unbiased §8.5.1
    * with one absorbing barrier footnote 4
    * with two absorbing barriers footnote 2
  * random-access machine Chapter 1
  * randomized computation §13.1
  * randomized rounding §10.4, §11.2.2
  * randomness
    * physical item 1
  * range coding 2nd item
  * rapid mixing §9.4.2
  * record §C.7.1
    * double §C.7.1
  * red-black tree §6.1.1
  * reducible item 5
  * reduction §10.1
  * register Chapter 14
    * max §14.6
  * regret §5.3.4.5
  * rejection sampling 1st item, §10.2.1, §9.3.4
  * relax footnote 7
  * relaxation §11.2.2
  * relaxation time §9.5.2
  * reversibility §9.2.1
  * reversible §13.3.1, §9.3
  * right spine §6.3.2.2
  * ring-cover tree §7.7.1
  * root §1.2, §6.1
  * rotation §6.1.1
    * tree §6.1.1
  * routing
    * bit-fixing §5.2.7.4, §9.5.8.2
    * permutation §5.2.7.4
  * run §A.7.2, §E.2.3
  * sampling §1.5.1, 2nd item
    * rejection 1st item, §10.2.1, §9.3.4
  * SAT §E.7.1
  * satisfiability §11.3.3.2
  * satisfiability problem §11.2.2
  * satisfy §11.2.2
  * scapegoat tree §6.1.1
  * search tree
    * balanced §6.1
    * binary §6.1
  * second-moment method §5.1.1.3
  * seed item 2, item 1
  * separate chaining §7.1
  * SHA footnote 3
  * shared coin
    * weak item 1
  * shared memory Chapter 14
  * sharp P §10.1
  * sifter item 2, §14.5, §4.3.2.3
  * simple path footnote 2
  * simplex method footnote 7
  * simulated annealing §9.4.5.2
  * simulation
    * Monte Carlo footnote 8
  * sketch §7.6.6
    * count-min §7.6.6, §7.6.6
    * Flajolet-Martin §D.4.1
  * sort
    * bubble §B.1.1
  * sorting network §11.1
  * Space Invaders §B.3.1
  * spanning tree §E.5.3
  * spare §D.3.1
  * spectral Bloom filter §7.6.5
  * spectral theorem §9.5.2
  * spine
    * left §6.3.2.2
    * right §6.3.2.2
  * sports reporting §B.2.1
  * sprite §B.3.1
  * standard deviation footnote 18
  * state space §9.1
  * state vector §13.1
  * stationary distribution Chapter 9, item 2, §9.2.1
  * stationary probability §9.2.1
  * Statistical pseudorandomness. item 3
  * stochastic matrix §13.1, §9.1
  * stochastic process footnote 1
  * stopping time Chapter 8, §8.1
  * strike §D.3.1
  * strong law of large numbers §5.4
  * strongly 2-universal §7.2
  * strongly $k$-universal §7.2
  * submartingale footnote 10, footnote 11, §8.2
  * subtree §6.1
  * supermartingale §8.2, footnote 10, 2nd item, §5.3.4.4
  * symmetry breaking 5th item
  * tabulation hashing §7.2.2
  * tensor product §13.1
  * termination §14.1
  * theorem
    * Adleman’s §12.2
    * Berry-Esseen §5.5.1
    * Doob decomposition §8.2
    * Erdős-Szekeres §D.3.2
    * Kolmogorov extension §2.1.1
    * no-cloning footnote 5
    * optional stopping §8.3
    * Perron-Frobenius §9.5.1
    * spectral §9.5.2
    * Toda’s §10.1
    * Valiant’s §10.1
  * third moment §5.5.1
  * Three-card Monte footnote 3
  * time
    * coupling §9.4.3, Lemma 9.4.1
    * expected Chapter 1
    * mixing §9.2.3
    * relaxation §9.5.2
    * stopping Chapter 8, §8.1
  * time-reversed chain §9.3.3
  * $t_{\mathrm{mix}}$ §9.2.3
  * Toda’s theorem §10.1
  * Toffoli gate §13.3.2
  * total path length §6.2
  * total variation distance Definition 9.2.1
  * transformation
    * unitary §13.3.1
  * transition matrix §9.1
  * transition probabilities §9.1
  * transpose
    * conjugate §13.2
  * treap §D.3.2, §6.3
  * tree
    * AVL §6.1.1
    * binary §6.1
    * binary search §6.1
    * cartesian footnote 3
    * radix §D.3.3
    * red-black §6.1.1
    * ring-cover §7.7.1
    * rotation §6.1.1
    * scapegoat §6.1.1
    * witness §11.3.5
  * tree rotation §6.1.1
  * truncation §8.3
  * UCB1 algorithm §5.3.4.5
  * unary §7.7.1.4
  * unbiased random walk §8.5.1
  * uniform §12.2
  * unitary matrix §13.3.1
  * unitary transformation §13.3.1
  * universal hash family §7.2
  * unranking §10.2.1
  * upper confidence bound §5.3.4.5
  * Valiant’s theorem §10.1
  * validity §14.1
  * variance §5.1
  * vector
    * state §13.1
  * vector space §3.5.2.3
  * vertex exposure martingale §5.3.4.2
  * wait-free Chapter 14
  * wait-free shared memory Chapter 14
  * Wald’s equation §3.4.3.1, §8.5.2
  * weak shared coin item 1
  * with high probability footnote 1
  * witness §1.2, §12.2
  * witness tree §11.3.5
  * word search puzzle §D.6.2
    * futile §D.6.2
  * worst-case analysis Chapter 1
  * xxHash footnote 3
  * Yao’s lemma §3.6.1
  * $ε$-nearest neighbor search §7.7.1
  * $ε$-NNS §7.7.1
  * $ε$-PLEB §7.7.1
  * $ε$-point location in equal balls §7.7.1
  * $σ$-algebra §2.1.1, §3.5.3
    * generated by a random variable §3.5.3
  * $τ_{2}$ §9.5.2
  * $Φ$ §9.5.4