probabilistic method doesn’t necessarily produce better results than we can
get by being smart. But the hope is that with the probabilistic method we
don’t have to be smart, and for some problems it seems that solving them
without using the probabilistic method requires being exceptionally smart.

####  11.1.2 Ramsey numbers

Consider a collection of $n$ schoolchildren, and imagine that each pair of
schoolchildren either like each other or dislike each other. We assume that
these preferences are symmetric: if $x$ likes $y$, then $y$ likes $x$, and
similarly if $x$ dislikes $y$, $y$ dislikes $x$. Let $R(k,h)$ be the smallest
value for $n$ that ensures that among any group of $n$ schoolchildren, there
is either a subset of $k$ children that all like each other or a subset of $h$
children that all dislike each other.111In terms of graphs, any graph $G$ with
at least $R(k,h)$ nodes contains either a clique of size $k$ or an independent
set of size $h$.

It is not hard to show that $R(k,h)$ is finite for all $k$ and $h$.222A simple
proof, due to Erdős and Szekeres [ES35], proceeds by showing that $R(k,h)\leq
R(k-1,h)+R(k,h-1)$. Given a graph $G$ of size at least $R(k-1,h)+R(k,h-1)$,
choose a vertex $v$ and partition the graph into two induced subgraphs $G_{1}$
and $G_{2}$, where $G_{1}$ contains all the vertices adjacent to $v$ and
$G_{2}$ contains all the vertices not adjacent to $v$. Either $\left\lvert
G_{1}\right\rvert\geq R(k-1,h)$ or $\left\lvert G_{2}\right\rvert\geq
R(k,h-1)$. If $\left\lvert G_{1}\right\rvert\geq R(k-1,h)$, then $G_{1}$
contains either a clique of size $k-1$ (which makes a clique of size $k$ in
$G$ when we add $v$ to it) or an independent set of size $h$ (which is also in
$G$). Alternatively, if $\left\lvert G_{2}\right\rvert\geq R(k,h-1)$, then
$G_{2}$ either gives us a clique of size $k$ by itself or an independent set
of size $h$ after adding $v$. Together with the fact that $R(1,h)=R(k,1)=1$,
this recurrence gives $R(k,h)\leq\binom{(k-1)+(h-1)}{k-1}$. The exact value of
$R(k,h)$ is known only for small values of $k$ and $h$.333There is a fairly
current table at http://en.wikipedia.org/wiki/Ramsey’s_Theorem. Some
noteworthy values are $R(3,3)=6$, $R(4,4)=18$, and $43\leq R(5,5)\leq 49$. One
problem with computing exact values is that as $R(k,h)$ grows, the number of
graphs one needs to consider gets very big. There are $2^{n\choose 2}$ graphs
with $n$ vertices, and even detecting the presence or absence of a moderately-
large clique or independent set in such a graph can be expensive. This pretty
much rules out any sort of brute-force approach based on simply enumerating
candidate graphs. But we can use the probabilistic method to show that for
$k=h$, it is reasonably large. The following theorem is due to Erdős, and was
the first known lower bound on $R(k,k)$.

######  Theorem 11.1.1 ([Erd47]).

If $k\geq 3$, then $R(k,k)>2^{k/2}$.

###### Proof.

Suppose each pair of schoolchildren flip a fair coin to decide whether they
like each other or not. Then the probability that any particular set of $k$
schoolchildren all like each other is $2^{-\binom{k}{2}}$ and the probability
that they all dislike each other is the same. Summing over both possibilities
and all subsets gives a bound of $\binom{n}{k}2^{1-\binom{k}{2}}$ on the
probability that there is at least one subset in which everybody likes
everybody or everybody dislikes everybody. For $n=2^{k/2}$, we have

$\displaystyle\binom{n}{k}2^{1-\binom{k}{2}}$
$\displaystyle\leq\frac{n^{k}}{k!}2^{1-\binom{k}{2}}$
$\displaystyle=\frac{2^{k^{2}/2+1-k(k-1)/2}}{k!}$
$\displaystyle=\frac{2^{k^{2}/2+1-k^{2}/2+k/2}}{k!}$
$\displaystyle=\frac{2^{1+k/2}}{k!}$ $\displaystyle<1.$

Because the probability that there is an all-liking or all-hating subset is
less than $1$, there must be some chance that we get a collection that doesn’t
have one. So such a collection exists. It follows that $R(k,k)>2^{k/2}$,
because we have shown that not all collections at $n=2^{k/2}$ have the Ramsey
property. ∎

The last step in the proof uses the fact that $2^{1+k/2}<k!$ for $k\geq 3$,
which can be tested explicitly for $k=3$ and proved by induction for larger
$k$. The resulting bound is a little bit weaker than just saying that $n$ must
be large enough that $\binom{n}{k}2^{1-\binom{k}{2}}\geq 1$, but it’s easier
to use.

The proof can be generalized to the case where $k\neq h$ by tweaking the
bounds and probabilities appropriately. Note that even though this process
generates a graph with no large cliques or independent sets with reasonably
high probability, we don’t have any good way of testing the result, since
testing for the existence of a clique is $\mathbf{NP}$-hard.

####  11.1.3 Directed cycles in tournaments

In the previous example we used the probabilistic method to show that there
existed a structure that didn’t contain some particular substructure. For this
example we will do the reverse: show that there exists a structure that
contains many instances of a particular substructure.

Imagine that $n$ wrestlers wrestle in a round-robin tournament, so that ever
wrestler wrestles every other wrestler exactly once, and so that for each pair
of wrestlers one wrestler beats the other. Consider a cycle of wrestlers
$x_{1},x_{2},\dots,x_{n}$ such that each wrestler $x_{i}$ beats $x_{i+1}$ and
$x_{n}$ beats $x_{1}$. (Note that we consider two cycles equivalent if one is
a cyclic shift of the other.)

######  Theorem 11.1.2.

For $n\geq 3$, there exists a tournament with at least $2^{-n}(n-1)!$ directed
cycles.

###### Proof.

Technical detail: We need $n\geq 3$ because the edges in a $2$-cycle always go
in opposite directions.

Flip a coin to decide the outcome of each pairing. For any particular sequence
$x_{1},\dots,x_{n}$, the probability that it is a directed cycle is then
$2^{-n}$ (since there are $n$ edges in the sequence and each has independent
probability $2^{-1}$ of going the right way). Now let $\sigma$ range over all
$(n-1)!$ cycles and define $X_{\sigma}$ as the indicator variable for the
event that each edge is directed the right way. We’ve just shown that
$\operatorname{E}\left[{X_{\sigma}}\right]=2^{-n}$; so the expected total
number of cycles is
$\operatorname{E}\left[{\sum_{\sigma}X_{\sigma}}\right]=\sum_{\sigma}\operatorname{E}\left[{X_{\sigma}}\right]=2^{-n}(n-1)!$.
But if the average value is at least $2^{-n}(n-1)!$, there must be some
specific outcome that gives a value at least this high. ∎

As in the Ramsey graph example, Theorem 11.1.2 says that generating a random
tournament is likely to give us many directed cycles, but whether a particular
tournament has this property may be hard to test. This is not unusual for
probabilistic-method arguments.

###  11.2 Approximation algorithms

One use of a randomized construction is to approximate the solution to an
otherwise difficult problem. In this section, we start with a trivial
approximation algorithm for the largest cut in a graph, and then show a more
powerful randomized approximation algorithm, due to Goemans and Williamson
[GW94], that gets a better approximation ratio for a much larger class of
problems.

####  11.2.1 MAX CUT

We’ve previously seen (§2.3.3.2) a randomized algorithm for finding small cuts
in a graph. What if we want to find a large cut?

Here is a particularly brainless algorithm that finds a large cut. For each
vertex, flip a coin: if the coin comes up heads, put the vertex in $S$,
otherwise, put in it $T$. For each edge, there is a probability of exactly
$1/2$ that it is included in the $S$–$T$ cut. It follows that the expected
size of the cut is exactly $m/2$.

One consequence of this is that every graph has a global cut that includes at
least half the edges. Another is that this algorithm finds such a cut, with
probability at least $\frac{1}{m+1}$. To prove this, let $X$ be the random
variable representing the number of edges in the cut, and let $p$ be the
probability that $X\geq m/2$. Then

$\displaystyle m/2$ $\displaystyle=\operatorname{E}\left[{X}\right]$
$\displaystyle=(1-p)\operatorname{E}\left[{X}\;\middle|\;{X<m/2}\right]+p\operatorname{E}\left[{X}\;\middle|\;{X\geq
m/2}\right]$ $\displaystyle\leq(1-p)\frac{m-1}{2}+pm.$

Solving this for $p$ gives the claimed bound.444This is tight for $m=1$, but I
suspect it’s an underestimate for larger $m$. The main source of slop in the
analysis seems to be the step $\operatorname{E}\left[{X}\;\middle|\;{X\geq
m/2}\right]\leq m$; using a concentration bound, we should be able to show a
much stronger inequality here and thus a much larger lower bound on $p$.

By running this enough times to get a good cut, we get a polynomial-time
randomized algorithm for approximating the maximum cut within a factor of $2$,
which is pretty good considering that MAX CUT is $\mathbf{NP}$-hard.

There exist better approximation algorithms. Goemans and Williamson [GW95]
give a 0.87856-approximation algorithm for MAX CUT based on randomized
rounding of a semidefinite program.555Semidefinite programs are like linear
programs except that the variables are vectors instead of scalars, and the
objective function and constraints apply to linear combinations of dot-
products of these variables. The Goemans-Williamson MAX CUT algorithm is based
on a relaxation of the integer optimization problem of maximizing $\sum
x_{i}x_{j}$ where each $x_{i}\in\left\\{{-1,+1}\right\\}$ encodes membership
in $S$ or $T$. They instead allow $x_{i}$ to be any unit vector in an
$n$-dimensional space, and then take the sign of the dot-product with a random
unit vector $r$ to map each optimized $x_{i}$ to one side of the cut or the
other. The analysis of this algorithm is a little involved, so we won’t
attempt to show this here, but we will describe (in §11.2.2) an earlier
result, also due to Goemans and Williamson [GW94], that gives a
$\frac{3}{4}$-approximation to MAX SAT using a similar technique.

####  11.2.2 MAX SAT

Like MAX CUT, MAX SAT is an $\mathbf{NP}$-hard optimization problem that
sounds like a very short story about Max. We are given a satisfiability
problem in conjunctive normal form: as a set of $m$ clauses, each of which is
the OR of a bunch of variables or their negations. We want to choose values
for the $n$ variables that satisfy as many of the clauses as possible, where a
clause is satisfied if it contains a true variable or the negation of a false
variable.666The presentation here follows [MR95, §5.2], which in turn is
mostly based on a classic paper of Goemans and Williamson [GW94].

We can instantly satisfy at least $m/2$ clauses on average by assigning values
to the variables independently and uniformly at random; the analysis is the
same as in §11.2.1 for large cuts, since a random assignment makes the first
variable in a clause true with probability $1/2$. Since this approach doesn’t
require thinking and doesn’t use the fact that many of our clauses may have
more than one variable, we can probably do better. Except we can’t do better
in the worst case, because it might be that our clauses consist entirely of
$x$ and $\neg x$ for some variable $x$; clearly, we can only satisfy half of
these. We could do better if we knew all of our clauses consisted of at least
$k$ distinct literals (satisfied with probability $1-2^{-k}$), but we can’t
count on this. We also can’t count on clauses not being duplicated, so it may
turn out that skipping a few hard-to-satisfy small clauses hurts us if they
occur many times.

Our goal will be to get a good approximation ratio, defined as the ratio
between the number of clauses we manage to satisfy and the actual maximum that
can be satisfied. The tricky part in designing a approximation algorithms is
showing that the denominator here won’t be too big. We can do this using a
standard trick, of expressing our original problem as an integer program and
then relaxing it to a linear program777A linear program is an optimization
problem where we want to maximize (or minimize) some linear objective function
of the variables subject to linear-inequality constraints. A simple example
would be to maximize $x+y$ subject to $2x+y\leq 1$ and $x+3y\leq 1$; here the
optimal solution is the assignment $x=\frac{2}{5},y=\frac{1}{5}$, which sets
the objective function to its maximum possible value $\frac{3}{5}$. An integer
program is a linear program where some of the variables are restricted to be
integers. Determining if an integer program even has a solution is
$\mathbf{NP}$-complete; in contrast, linear programs can be solved in
polynomial time. We can relax an integer program to a linear program by
dropping the requirements that variables be integers; this will let us find a
fractional solution that is at least as good as the best integer solution, but
might be undesirable because it tells us to do something that is ludicrous in
the context of our original problem, like only putting half a passenger on the
next plane. Linear programming has an interesting history. The basic ideas
were developed independently by Leonid Kantorovich in the Soviet Union and
George Dantzig in the United States around the start of the Second World War.
Kantorovich’s work had direct relevance to Soviet planning problems, but
wasn’t pursued seriously because it threatened the political status of the
planners, required computational resources that weren’t available at the time,
and looked suspiciously like trying to sneak a capitalist-style price system
into the planning process; for a fictionalized account of this tragedy, see
[Spu12]. Dantzig’s work, which included the development of the simplex method
for solving linear programs, had a higher impact, although its publication was
delayed until 1947 by wartime secrecy. whose solution doesn’t have to consist
of integers. We then convert the fractional solution back to an integer
solution by rounding some of the variables to integer values randomly in a way
that preserves their expectations, a technique known as randomized
rounding.888 Randomized rounding was invented by Raghavan and Thompson [RT87];
the particular application here is due to Goemans and Williamson [GW94].

Here is the integer program (taken from [MR95, §5.2]). We let
$z_{j}\in\left\\{{0,1}\right\\}$ represent whether clause $C_{j}$ is
satisfied, and let $y_{i}\in\left\\{{0,1}\right\\}$ be the value of variable
$x_{i}$. We also let $C_{j}^{+}$ and $C_{j}^{-}$ be the set of variables that
appear in $C_{j}$ with and without negation. The problem is to maximize

$\sum_{j=1}^{m}z_{j}$

subject to

$\sum_{i\in C_{j}^{+}}y_{i}+\sum_{i\in C_{j}^{-}}(1-y_{i})\geq z_{j},$

for all $j$.

The main trick here is to encode OR in the constraints; there is no
requirement that $z_{j}$ is the OR of the $y_{i}$ and $(1-y_{i})$ values, but
we maximize the objective function by setting it that way.

Sadly, solving integer programs like the above is $\mathbf{NP}$-hard (which is
not surprising, since if we could solve this particular one, we could solve
SAT). But if we drop the requirements that
$y_{i},z_{j}\in\left\\{{0,1}\right\\}$ and replace them with $0\leq y_{i}\leq
1$ and $0\leq z_{j}\leq 1$, we get a linear program—solvable in polynomial
time—with an optimal value at least as good as the value for the integer
program, for the simple reason that any solution to the integer program is
also a solution to the linear program.

The problem now is that the solution to the linear program is likely to be
fractional: instead of getting useful $0$–$1$ values, we might find out we are
supposed to make $x_{i}$ only $2/3$ true. So we need one more trick to turn
the fractional values back into integers. This is the randomized rounding
step: given a fractional assignment $\hat{y}_{i}$, we set $x_{i}$ to true with
probability $\hat{y}_{i}$.

So what does randomized rounding do to clauses? In our fractional solution, a
clause might have value $\hat{z}_{j}$, obtained by summing up bits and pieces
of partially-true variables. We’d like to argue that the rounded version gives
a similar probability that $C_{j}$ is satisfied.

Suppose $C_{j}$ has $k$ variables; to make things simpler, we’ll pretend that
$C_{j}$ is exactly $x_{1}\vee x_{2}\vee\dots x_{k}$. Then the probability that
$C_{j}$ is satisfied is exactly $1-\prod_{i=1}^{k}(1-\hat{y}_{i})$. This
quantity is minimized subject to $\sum_{i=1}^{k}\hat{y}_{i}\geq\hat{z}_{j}$ by
setting all $\hat{y}_{i}$ equal to $\hat{z}_{j}/k$ (easy application of
Lagrange multipliers, or can be shown using a convexity argument). Writing $z$
for $\hat{z}_{j}$, this gives

$\displaystyle\Pr\left[{\text{$C_{j}$ is satisfied}}\right]$
$\displaystyle=1-\prod_{i=1}^{k}(1-\hat{y}_{i})$ $\displaystyle\geq
1-\prod_{i=1}^{k}(1-z/k)$ $\displaystyle=1-(1-z/k)^{k}$ $\displaystyle\geq
z(1-(1-1/k)^{k}).$ $\displaystyle\geq z(1-1/e).$

The second-to-last step looks like a typo, but it actually works. The idea is
to observe that the function $f(z)=1-(1-z/k)^{k}$ is concave (Proof:
$\frac{d^{2}}{dz^{2}}f(z)=-\frac{k-1}{k}(1-z/k)^{k-2}<0$), while
$g(z)=z(1-(1-1/k)^{k})$ is linear, so since $f(0)=0=g(0)$ and
$f(1)=1-(1-1/k)^{k}=g(1)$, any point in between must have $f(z)\geq g(z)$. An
example of this argument for $k=3$ is depicted in Figure 11.1.

Figure 11.1: Tricky step in MAX SAT argument, showing $(1-(1-z/k)^{k})\geq
z(1-(1-1/k)^{k})$ when $0\leq z\leq 1$. The case $k=3$ is depicted.

Since each clause is satisfied with probability at least $\hat{z}_{j}(1-1/e)$,
the expected number of satisfied clauses is at least
$(1-1/e)\sum_{j}\hat{z}_{j}$, which is at least $(1-1/e)$ times the optimum.
This gives an approximation ratio of slightly more than 0.632, which is better
than $1/2$, but still kind of weak.

So now we apply the second trick from [GW94]: we’ll observe that, on a per-
clause basis, we have a randomized rounding algorithm that is good at
satisfying small clauses (the coefficient $(1-(1-1/k)^{k})$ goes all the way
up to $1$ when $k=1$), and our earlier dumb algorithm that is good at
satisfying big clauses. We can’t combine these directly (the two algorithms
demand different assignments), but we can run both in parallel and take
whichever gives a better result.

To show that this works, let $X_{j}$ be indicator for the event that clause
$j$ is satisfied by the randomized-rounding algorithm and $Y_{j}$ the
indicator for the even that it is satisfied by the simple algorithm. Then if
$C_{j}$ has $k$ literals,

$\displaystyle\operatorname{E}\left[{X_{j}}\right]+\operatorname{E}\left[{Y_{j}}\right]$
$\displaystyle\geq(1-2^{-k})+(1-(1-1/k)^{k})\hat{z}_{j}$
$\displaystyle\geq((1-2^{-k})+(1-(1-1/k)^{k}))\hat{z}_{j}$
$\displaystyle=(2-2^{-k}-(1-1/k)^{k})\hat{z}_{j}.$

The coefficient here is exactly $3/2$ when $k=1$ or $k=2$, and rises
thereafter, so for integer $k$ we have
$\operatorname{E}\left[{X_{j}}\right]+\operatorname{E}\left[{Y_{j}}\right]\geq(3/2)\hat{z}_{j}$.
Summing over all $j$ then gives
$\operatorname{E}\left[{\sum_{j}X_{j}}\right]+\operatorname{E}\left[{\sum_{j}Y_{j}}\right]\geq(3/2)\sum_{j}\hat{z}_{j}$.
But then one of the two expected sums must beat $(3/4)\sum_{j}\hat{z}_{j}$,
giving us a $(3/4)$-approximation algorithm.

###  11.3 The Lovász Local Lemma

Suppose we have a finite set of bad events $\mathcal{A}$, and we want to show
that with nonzero probability, none of these events occur. Formally, we want
to show $\Pr\left[{\bigcap_{A\in\mathcal{A}}\bar{A}}\right]>0$.

Our usual trick so far has been to use the union bound (4.1.1) to show that
$\sum_{A\in\mathcal{A}}\Pr\left[{A}\right]<1$. But this only works if the
events are actually improbable. If the union bound doesn’t work, we might be
lucky enough to have the events be independent; in this case,
$\Pr\left[{\bigcap_{A\in\mathcal{A}}\bar{A}}\right]=\prod_{A\in\mathcal{A}}\Pr\left[{\bar{A}}\right]>0$,
as long as each event $\bar{A}$ occurs with positive probability. But most of
the time, we’ll find that the events we care about aren’t independent, so this
won’t work either.

The Lovász Local Lemma [EL75] handles a situation intermediate between these
two extremes, where events are generally not independent of each other, but
each collection of events that are not independent of some particular event
$A$ has low total probability. In the original version, it’s non-constructive:
the lemma shows a nonzero probability that none of the events occur, but this
probability may be very small if we try to sample the events at random, and
there is no guidance for how to find a particular outcome that makes all the
events false.

Subsequent work [Bec91, Alo91, MR98, CS00, Sri08, Mos09, MT10] showed how,
when the events $A$ are determined by some underlying set of independent
variables and independence between two events is detected by having non-
overlapping sets of underlying variables, an actual solution could be found in
polynomial expected time. The final result in this series, due to Moser and
Tardos [MT10], gives the same bounds as in the original non-constructive
lemma, using the simplest algorithm imaginable: whenever some bad event $A$
occurs, try to get rid of it by resampling all of its variables, and continue
until no bad events are left.

####  11.3.1 General version

A formal statement of the general lemma is:999This version is adapted from
[MT10].

######  Lemma 11.3.1.

Let $\mathcal{A}=A_{1},\dots,A_{m}$ be a finite collection of events on some
probability space, and for each $A\in\mathcal{A}$, let $\Gamma(A)$ be a set of
events such that $A$ is independent of all events not in
$\Gamma^{+}{A}=\left\\{{A}\right\\}\cup\Gamma(A)$. If there exist real numbers
$0<x_{A}<1$ such that, for all events $A\in\mathcal{A}$

$\displaystyle\Pr\left[{A}\right]$ $\displaystyle\leq
x_{A}\prod_{B\in\Gamma(A)}(1-x_{B}),$ (11.3.1) then
$\displaystyle\Pr\left[{\bigcap_{A\in\mathcal{A}}\bar{A}}\right]$
$\displaystyle\geq\prod_{A\in\mathcal{A}}(1-x_{A}).$ (11.3.2)

In particular, this means that the probability that none of the $A_{i}$ occur
is not zero, since we have assumed $x_{A_{i}}<1$ holds for all $i$.

The role of $x_{A}$ in the original proof is to act as an upper bound on the
probability that $A$ occurs given that some collection of other events doesn’t
occur. For the constructive proof, the $x_{A}$ are used to show a bound on the
number of resampling steps needed until none of the $A$ occur.

####  11.3.2 Symmetric version

For many applications, having to come up with the $x_{A}$ values can be
awkward. The following symmetric version is often used instead:

######  Corollary 11.3.2.

Let $\mathcal{A}$ and $\Gamma$ be as in Lemma 11.3.1. Suppose that there are
constants $p$ and $d$, such that for all $A\in\mathcal{A}$, we have
$\Pr\left[{A}\right]\leq p$ and $\left\lvert\Gamma(A)\right\rvert\leq d$. Then
if $ep(d+1)<1$, $\Pr\left[{\bigcap_{A\in\mathcal{A}}\bar{A}}\right]\neq 0$.

###### Proof.

Basically, we are going to pick a single value $x$ such that $x_{A}=x$ for all
$A$ in $\mathcal{A}$, and (11.3.1) is satisfied. This works as long as $p\leq
x(1-x)^{d}$, as in this case we have, for all $A$, $\Pr\left[{A}\right]\leq
p\leq x(1-x)^{d}\leq
x(1-x)^{\left\lvert\Gamma(A)\right\rvert}=x_{A}\left(\prod_{B\in\Gamma(A)}(1-x_{B})\right)$.

For fixed $d$, $x(1-x)^{d}$ is maximized using the usual trick:
$\frac{d}{dx}x(1-x)^{d}=(1-x)^{d}-xd(1-x)^{d-1}=0$ gives $(1-x)-xd=0$ or
$x=\frac{1}{d+1}$. So now we need
$p\leq\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^{d}$. It is possible to show
that $1/e<\left(1-\frac{1}{d+1}\right)^{d}$ for all $d\geq 0$.101010Observe
that $\lim_{d\rightarrow\infty}\left(1-\frac{1}{d+1}\right)^{d}=e^{-1}$ and
that $f(d)=\left(1-\frac{1}{d+1}\right)^{d}=e^{-1}$ is a decreasing function.
The last part can be shown by taking the derivative of $\log f(d)$. See the
solution to Problem E.1.4 for the gory details.  So $ep(d+1)\leq 1$ implies
$p\leq\frac{1}{e(d+1)}\leq\left(1-\frac{1}{d+1}\right)^{d}\frac{1}{d+1}\leq
x(1-x)^{\left\lvert\Gamma(A)\right\rvert}$ as required by Lemma 11.3.1. ∎

####  11.3.3 Applications

Here we give some simple applications of the lemma.

#####  11.3.3.1 Graph coloring

Let’s start with a problem where we know what the right answer should be.
Suppose we want to color the vertices of a cycle with $c$ colors, so that no
edge has two endpoints with the same color. How many colors do we need?

Using brains, we can quickly figure out that $c=3$ is enough. Without brains,
we could try coloring the vertices randomly: but in a cycle with $n$ vertices
and $n$ edges, on average $n/c$ of the edges will be monochromatic, since each
edge is monochromatic with probability $1/c$. If these bad events were
independent, we could argue that there was a $(1-1/c)^{n}>0$ probability that
none of them occurred, but they aren’t, so we can’t. Instead, we’ll use the
local lemma.

The set of bad events $\mathcal{A}$ is just the set of events
$A_{i}=[\text{edge $i$ is monochromatic}]$. We’ve already computed $p=1/c$. To
get $d$, notice that each edge only shares a vertex with two other edges, so
$\left\lvert\Gamma(A_{i})\right\rvert\leq 2$. Corollary 11.3.2 then says that
there is a good coloring as long as $ep(d+1)=3e/c\leq 1$, which holds as long
as $c\geq 9$. We’ve just shown we can $9$-color a cycle. If use the asymmetric
version, we can set all $x_{A}$ to $1/3$ and show that
$p\leq\frac{1}{3}\left(1-\frac{1}{3}\right)^{2}=\frac{4}{27}$ would also work;
with this we can $7$-color a cycle. This is still not as good as what we can
do if we are paying attention, but not bad for a procedure that doesn’t use
the structure of the problem much.

#####  11.3.3.2 Satisfiability of $k$-CNF formulas

A more sophisticated application is demonstrating satisfiability for $k$-CNF
formulas where each variable appears in a bounded number of clauses. Recall
that a $k$-CNF formula consists of $m$ clauses, each of which consists of
exactly $k$ variables or their negations (collectively called literals. It is
satisfied if at least one literal in every clause is assigned the value true.

Suppose that each variable appears in at most $\ell$ clauses. Let
$\mathcal{A}$ consist of all the events $A_{i}=[\text{clause $i$ is not
satisfied}]$. Then, for all $i$, $\Pr\left[{A_{i}}\right]=2^{-k}$ exactly, and
$\left\lvert\Gamma(A_{i})\right\rvert\leq d=k(\ell-1)$ since each variable in
$A_{i}$ is shared with at most $\ell-1$ other clauses, and $A_{i}$ will be
independent of all events $A_{j}$ with which it doesn’t share a variable. So
if $ep(d+1)=e2^{-k}(k(\ell-1)+1)\leq 1$, which holds if
$\ell\leq\frac{2^{k}}{ek}+1$, Corollary 11.3.2 tells us that a satisfying
assignment exists.111111To avoid over-selling this claim, it’s worth noting
that the bound on $\ell$ only reaches $2$ at $k=4$, although it starts growing
pretty fast after that.

Corollary 11.3.2 doesn’t let us actually find a satisfying assignment, but it
turns out we can do that too. We’ll return to this when we talk about the
constructive version of the local lemma in §11.3.5.

#####  11.3.3.3 Hypergraph $2$-colorability

This was the original motivation for the lemma. A $k$-uniform hypergraph
$G=\left\langle{V,E}\right\rangle$ has a set of hyperedges $E$, each of which
contains exactly $k$ vertices from $V$. A $2$-coloring of the hypergraph
assigns one of two colors to each vertex in $v$, so that no edge is
monochromatic.

Suppose we color vertices at random. Pick some edge $S$, and let $A_{S}$ be
the probability that it is monochromatic. Then
$\Pr\left[{A_{S}}\right]=2^{1-k}$ exactly. We also have that $A_{S}$ depends
only on events $A_{T}$ where $S\cap T\neq\emptyset$. Suppose that there is a
bound $d$ on the number of hyperedges $T$ that overlap with any hyperedge $S$.
Then Corollary 11.3.2 says that there exists a good coloring as long as
$e2^{1-k}(d+1)<1$. This holds for any hypergraph with $d<2^{k-1}/e-1$.

Unlike graph coloring, it’s not so obvious how to solve hypergraph coloring
with a simple greedy algorithm. So here the local lemma seems to buy us
something we didn’t already have.

####  11.3.4 Non-constructive proof

This is essentially the same argument presented in [MR95, §5.5], but we adapt
the notation to match the statement in terms of neighborhoods $\Gamma(A)$
instead of edges in a dependency graph, where an event is independent of all
events that are not its successors in the graph. The two formulations are
identical, since we can always represent the neighborhoods $\Gamma(A)$ by
creating an edge from $A$ to $B$ when $B$ is in $\Gamma(A)$; and conversely we
can convert a dependency graph into a neighborhood structure by making
$\Gamma(A)$ the set of successors of $A$ in the dependency graph.

The proof is a bit easier than the non-constructive version, while also being
a bit more general because the neighborhood structure doesn’t depend on
identifying a collection of underlying independent variables.

The idea is to order the events in $\mathcal{A}$ as $A_{1},A_{2},\dots,A_{n}$
and expand $\Pr\left[{\bigcap_{i=1}^{n}\bar{A}_{i}}\right]$ as
$\prod_{i=1}^{n}\Pr\left[{\bar{A}_{i}}\;\middle|\;{\bigcap_{j=1}^{i-1}\bar{A}_{j}}\right]$.
If we can show that every term in the product is nonzero, we are done.

To do this, we will show by induction on $\left\lvert S\right\rvert$ the more
general statement that for any $A$ and _any_ $S\subseteq\mathcal{A}$ with
$A\not\in S$,

$\displaystyle\Pr\left[{A}\;\middle|\;{\bigcap_{B\in S}\bar{B}}\right]$
$\displaystyle\leq x_{A}.$ (11.3.3)

When $\left\lvert S\right\rvert=0$, this just says $\Pr\left[{A}\right]\leq
x_{A}$, which follows immediately from (11.3.1).

For larger $S$, split $S$ into $S_{1}=S\cap\Gamma(A)$, the events in $S$ that
might not be independent of $A$; and $S_{2}=S\setminus\Gamma(A)$, the events
in $S$ that we know to be independent of $A$. If $S_{2}=S$, then $A$ is
independent of all events in $S$, and (11.3.3) follows immediately from
$\Pr\left[{A}\;\middle|\;{\bigcap_{B\in
S}\bar{B}}\right]=\Pr\left[{A}\right]\leq
x_{A}\prod_{B\in\Gamma(A)}(1-x_{B})\leq x_{A}$. Otherwise $\left\lvert
S_{2}\right\rvert<\left\lvert S\right\rvert$, which means that we can assume
the induction hypothesis holds for $S_{2}$.

Write $C_{1}$ for the event $\bigcap_{B\in S_{1}}\bar{B}$ and $C_{2}$ for the
event $\bigcap_{B\in S_{2}}\bar{B}$. Then $\bigcap_{B\in S}\bar{B}=C_{1}\cap
C_{2}$ and we can expand

$\displaystyle\Pr\left[{A}\;\middle|\;{\bigcap_{B\in S}\bar{B}}\right]$
$\displaystyle=\frac{\Pr\left[{A\cap C_{1}\cap
C_{2}}\right]}{\Pr\left[{C_{1}\cap C_{2}}\right]}$
$\displaystyle=\frac{\Pr\left[{A\cap
C_{1}}\;\middle|\;{C_{2}}\right]\Pr\left[{C_{2}}\right]}{\Pr\left[{C_{1}}\;\middle|\;{C_{2}}\right]\Pr\left[{C_{2}}\right]}$
$\displaystyle=\frac{\Pr\left[{A\cap
C_{1}}\;\middle|\;{C_{2}}\right]}{\Pr\left[{C_{1}}\;\middle|\;{C_{2}}\right]}.$
(11.3.4)

We don’t need to do anything particularly clever with the numerator:

$\displaystyle\Pr\left[{A\cap C_{1}}\;\middle|\;{C_{2}}\right]$
$\displaystyle\leq\Pr\left[{A}\;\middle|\;{C_{2}}\right]$
$\displaystyle=\Pr\left[{A}\right]$ $\displaystyle\leq
x_{A}\left(\prod_{B\in\Gamma(A)}(1-x_{B})\right),$ (11.3.5)

from (11.3.1) and the fact that $A$ is independent of all $B$ in $S_{2}$ and
thus also independent of $C_{2}$.

For the denominator, we expand $C_{1}$ back out to $\bigcap_{B\in
S_{1}}\bar{B}$ and break out the induction hypothesis. To bound
$\Pr\left[{\bigcap_{B\in S_{1}}\bar{B}}\;\middle|\;{C_{2}}\right]$, we order
$S_{1}$ arbitrarily as $\left\\{{B_{1},\dots,B_{r}}\right\\}$, for some $r$,
and show by induction on $\ell$ as $\ell$ goes from $1$ to $r$ that

$\displaystyle\Pr\left[{\bigcap_{i=1}^{\ell}\bar{B}_{i}}\;\middle|\;{C_{2}}\right]$
$\displaystyle\geq\prod_{i=1}^{\ell}(1-x_{B_{i}}).$ (11.3.6)

The proof is that, for $\ell=1$,

$\displaystyle\Pr\left[{\bar{B}_{1}}\;\middle|\;{C_{2}}\right]$
$\displaystyle=1-\Pr\left[{B_{1}}\;\middle|\;{C_{2}}\right]$
$\displaystyle\geq 1-x_{B_{1}}$

using the outer induction hypothesis (11.3.3), and for larger $\ell$, we can
compute

$\displaystyle\Pr\left[{\bigcap_{i=1}^{\ell}\bar{B}_{i}}\;\middle|\;{C_{2}}\right]$
$\displaystyle=\Pr\left[{\bar{B}_{\ell}}\;\middle|\;{\left(\bigcap_{i=1}^{\ell-1}\bar{B}_{i}\right)\cap
C_{2}}\right]\cdot\Pr\left[{\bigcap_{i=1}^{\ell-1}\bar{B}_{i}}\;\middle|\;{C_{2}}\right]$
$\displaystyle\geq(1-x_{B_{\ell}})\prod_{i=1}^{\ell-1}(1-x_{B_{i}})$
$\displaystyle=\prod_{i=1}^{\ell}(1-x_{B_{i}}),$

where the second-to-last step uses the outer induction hypothesis (11.3.3) for
the first term and the inner induction hypothesis (11.3.6) for the rest. This
completes the proof of the inner induction.

When $\ell=r$, we get

$\displaystyle\Pr\left[{C_{1}}\;\middle|\;{C_{2}}\right]$
$\displaystyle=\Pr\left[{\bigcap_{i=1}^{r}\bar{B}_{i}}\;\middle|\;{C_{2}}\right]$
$\displaystyle\geq\prod_{B\in S_{1}}(1-x_{B}).$ (11.3.7)

Substituting (11.3.5) and (11.3.7) into (11.3.4) gives

$\displaystyle\Pr\left[{A}\;\middle|\;{\bigcap_{B\in S}\bar{B}}\right]$
$\displaystyle\leq\frac{x_{A}\left(\prod_{B\in\Gamma(A)}(1-x_{B})\right),}{\prod_{B\in
S_{1}}(1-x_{B})}$ $\displaystyle=x_{A}\left(\prod_{B\in\Gamma(A)\setminus
S_{1}}(1-x_{B})\right)$ $\displaystyle\leq x_{A}.$

This completes the proof of the outer induction.

To get the bound (11.3.2), we reach back inside the proof and repeat the
argument for (11.3.7) with $\bigcap_{A\in\mathcal{A}}\bar{A}$ in place of
$C_{1}$ and without the conditioning on $C_{2}$. We order $\mathcal{A}$
arbitrarily as $\left\\{{A_{1},A_{2},\dots,A_{m}}\right\\}$ and show by
induction on $k$ that

$\displaystyle\Pr\left[{\bigcap_{i=1}^{k}\bar{A}_{i}}\right]$
$\displaystyle\geq\prod_{i=1}^{k}(1-x_{A_{k}}).$ (11.3.8)

For the base case we have $k=0$ and $\Pr\left[{\Omega}\right]\geq 1$, using
the usual conventions on empty products. For larger $k$, we have

$\displaystyle\Pr\left[{\bigcap_{i=1}^{k}\bar{A}_{i}}\right]$
$\displaystyle=\Pr\left[{\bar{A}_{k}}\;\middle|\;{\bigcap_{i=1}^{k-1}\bar{A}_{i}}\right]\Pr\left[{\bigcap_{i=1}^{k-1}\bar{A}_{i}}\right]$
$\displaystyle\geq(1-x_{A_{k}})\prod_{i=1}^{k-1}(1-x_{A_{i}})$
$\displaystyle\geq\prod_{i=1}^{k}(1-x_{A_{k}}),$

where in the second-to-last step we use (11.3.3) for the first term and the
induction hypothesis (11.3.8) for the big product.

Setting $k=n$ finishes the proof.

####  11.3.5 Constructive proof

We now describe he constructive proof of the Lovász local lemma due to Moser
and Tardos [MT10], which is based on a slightly more specialized construction
of Moser alone [Mos09]. This version applies when our set of bad events
$\mathcal{A}$ is defined in terms of a set of _independent_ variables
$\mathcal{P}$, where each $A\in\mathcal{A}$ is determined by some set of
variables $\operatorname{vbl}(A)\subseteq\mathcal{P}$, and $\Gamma(A)$ is
defined to be the set of all events $B\neq A$ that share at least one variable
with $A$; i.e.,
$\Gamma(A)=\left\\{{B\in\mathcal{A}\setminus\left\\{{A}\right\\}}\;\middle|\;{\operatorname{vbl}(B)\cap\operatorname{vbl}(A)\neq\emptyset}\right\\}$.

In this case, we can attempt to find an assignment to the variables that makes
none of the $A$ occur using the obvious algorithm of sampling an initial state
randomly, then resampling all variables in $\operatorname{vbl}(A)$ whenever we
see some bad $A$ occur. Astonishingly, this actually works in a reasonable
amount of time, without even any cleverness in deciding which $A$ to resample
at each step, if the conditions for Lemma 11.3.1 hold for $x$ that are not too
large. In particular, we will show that a good assignment is found after each
$A$ is resampled at most $\frac{x_{A}}{1-x_{A}}$ times on average.

######  Lemma 11.3.3.

Under the conditions of Lemma 11.3.1, the Moser-Tardos procedure does at most

$\displaystyle\sum_{A}\frac{x_{A}}{1-x_{A}}$

resampling steps on average.

We defer the proof of Lemma 11.3.3 for the moment. For most applications, the
following symmetric version is easier to work with:

######  Corollary 11.3.4.

Under the conditions of Corollary 11.3.2, the Moser-Tardos procedure does at
most $m/d$ resampling steps on average.

###### Proof.

Follows from Lemma 11.3.3 and the choice of $x_{A}=\frac{1}{d+1}$ in the proof
of Corollary 11.3.2. ∎

How this expected $m/d$ bound translates into actual time depends on the cost
of each resampling step. The expensive part at each step is likely to be the
cost of finding an $A$ that occurs and thus needs to be resampled.

Intuitively, we might expect the resampling to work because if each
$A\in\mathcal{A}$ has a small enough neighborhood $\Gamma(A)$ and a low enough
probability, then whenever we resample $A$’s variables, it’s likely that we
fix $A$ and unlikely that we break too many $B$ events in $A$’s neighborhood.
It turns out to be tricky to quantify how this process propagates outward, so
the actual proof uses a different idea that essentially looks at this process
in reverse, looking for each resampled event $A$ at a set of previous events
whose resampling we can blame for making $A$ occur, and then showing that this
tree (which will include every resampling operation as one of its vertices)
can’t be too big.

The first step is to fix some strategy for choosing which event $A$ to
resample at each step. We don’t care what this strategy is; we just want it to
be the case that the sequence of events depends only on the random choices
made by the algorithm in its initial sampling and each resampling. We can then
define an execution log $C$ that lists the sequence of events
$C_{1},C_{2},C_{3},\dots$ that are resampled at each step of the execution.

From $C$ we construct a witness tree $T_{t}$ for each resampling step $t$
whose nodes are labeled with events, with the property that the children of a
node $v$ labeled with event $A_{v}$ are labeled with events in
$\Gamma^{+}(A_{v})=\left\\{{A_{v}}\right\\}\cup\Gamma(A_{v})$.

The root of $T_{t}$ is labeled with $C_{t}$. To construct the rest of the
tree, we work backwards through $C_{t-1},C_{t-2},\dots,C_{1}$, and for each
event $C_{i}$ we encounter, we attach $C_{i}$ as a child of the deepest $v$ we
can find with $C_{i}\in\Gamma^{+}(A_{v})$, choosing arbitrarily if there is
more than one such $v$, and discarding $C_{i}$ if there is no such $v$.

Now we can ask what the probability is that we see some particular witness
tree $T$ in the execution log. Each vertex of $T$ corresponds to some event
$A_{v}$ that we resample because it occurs; in order for it to occur, the
previous assignments of each variable in $\operatorname{vbl}(A_{v})$ must have
made $A_{v}$ true, which occurs with probability $\Pr\left[{A_{v}}\right]$.
But since we resample all the variables in $A_{v}$, any subsequent assignments
to these variables are independent of the ones that contributed to $v$; with
sufficient handwaving (or a rather detailed coupling argument as found in
[MT10]) this gives that each event $A_{v}$ occurs with independent probability
$\Pr\left[{A_{v}}\right]$, giving $\Pr\left[{T}\right]=\prod_{v\in
T}\Pr\left[{A_{v}}\right]$.

Why do we care about this? Because every event we resample is the root of some
witness tree, and we can argue that every event we resample is the root of a
_distinct_ witness tree. The proof is that since we only discard events $B$
that have $\operatorname{vbl}(B)$ disjoint from all nodes already in the tree,
once we put $A$ at the root, any other instance of $A$ gets included. So the
witness tree rooted at the $i$-th occurrence of $A$ in $C$ will include
exactly $i$ copies of $A$, unlike the witness tree rooted at the $j$-th copy
for $j\neq i$.

Now comes the sneaky trick: we’ll bound how many distinct witness trees $T$ we
expect to see rooted at $A$, given that each occurs with probability
$\prod_{v\in T}\Pr\left[{A_{v}}\right]$. This is done by constructing a
branching process using the $x_{B}$ values from Lemma 11.3.1 as probabilities
of a node with label $A$ having a child labeled $B$ for each $B$ in
$\Gamma^{+}(A)$, and doing algebraic manipulations on the resulting
probabilities until $\prod_{v\in T}\Pr\left[{A_{v}}\right]$ shows up. We can
then sum over the expected number of copies of trees to get a bound on the
expected number of events in the execution log (since each such even is the
root of some tree), which is equal to the expected number of resamplings.

Consider the process where we start with a root labeled $A$, and for each
vertex $v$ with label $A_{v}$, give it a child labeled $B$ for each
$B\in\Gamma^{+}(A_{v})$ with independent probability $x_{B}$. We’ll now
calculate the probability $p_{T}$ that this process generates a particular
tree $T$ in the set $\mathcal{T}_{A}$ of trees with root $A$.

Let $x^{\prime}_{B}=x_{B}\prod_{C\in\Gamma(B)}(1-x_{C})$. Note that (11.3.1)
says precisely that $\Pr\left[{B}\right]\leq x^{\prime}_{B}$.

For each vertex $v$ in $T$, let $W_{v}\subseteq\Gamma^{+}(A_{v})$ be the set
of events $B\in\Gamma^{+}(A_{v})$ that _don’t_ occur as labels of children of
$v$. The probability of getting $T$ is equal to the product of the
probabilities at each $v$ of getting all of its children and none of its non-
children. The non-children of $v$ collectively contribute $\prod_{B\in
W_{v}}(1-x_{B})$ to the product, and $v$ itself contributes $x_{A_{v}}$ (via
the product for its parent), unless $v$ is the root node. So we can express
the giant product as

$\displaystyle p_{T}$ $\displaystyle=\frac{1}{x_{A}}\prod_{v\in
T}\left(x_{A_{v}}\prod_{B\in W_{v}}(1-x_{B})\right).$

We don’t like the $W_{v}$ very much, so we get rid of them by taking the
product of _B_ in $\Gamma^{+}(A)$, then dividing out the ones that aren’t in
$W_{v}$. This gives

$\displaystyle p_{T}$ $\displaystyle=\frac{1}{x_{A}}\prod_{v\in
T}\left(x_{A_{v}}\prod_{B\in W_{v}}(1-x_{B})\right).$
$\displaystyle=\frac{1}{x_{A}}\prod_{v\in
T}\left(x_{A_{v}}\prod_{B\in\Gamma^{+}(A_{v})}(1-x_{B})\Pi_{B\in\Gamma^{+}(A_{v})\setminus
W_{v}}\frac{1}{1-x_{B}}\right).$

This seems like we exchanged one annoying index set for another, but each
element of $\Gamma^{+}(A_{V})\setminus W_{v}$ is $A_{v^{\prime}}$ for some
child of $v$ in $T$. So we can push these factors down to the children, and
since we are multiplying over all vertices in $T$, they will each show up
exactly once except at the root. To keep the products clean, we’ll throw in
$\frac{1}{1-x_{A}}$ for the root as well, but compensate for this by
multiplying by $1-x_{A}$ on the outside of the product. This gives

$\displaystyle p_{T}$ $\displaystyle=\frac{1-x_{A}}{x_{A}}\prod_{v\in
T}\left(\frac{x_{A_{v}}}{1-x_{A_{v}}}\prod_{B\in\Gamma^{+}(A_{v})}(1-x_{B})\right).$
$\displaystyle=\frac{1-x_{A}}{x_{A}}\prod_{v\in
T}\left(x_{A_{v}}\prod_{B\in\Gamma(A_{v})}(1-x_{B})\right).$
$\displaystyle=\frac{1-x_{A}}{x_{A}}\prod_{v\in T}x^{\prime}_{A_{v}}.$

Now we can bound the expected number of trees rooted at $A$ that appear in
$C$, assuming (11.3.1) holds. Letting $\mathcal{T}_{A}$ as before be the set
of all such trees and $N_{A}$ the number that appear in $C$, we have

$\displaystyle\operatorname{E}\left[{N_{A}}\right]$
$\displaystyle=\sum_{T\in\mathcal{T}_{A}}\Pr\left[{\text{$T$ appears in
$C$}}\right]$ $\displaystyle\leq\sum_{T\in\mathcal{T}_{A}}\prod_{v\in
T}\Pr\left[{A(v)}\right]$
$\displaystyle\leq\sum_{T\in\mathcal{T}_{A}}\prod_{v\in T}x^{\prime}_{A_{v}}$
$\displaystyle=\sum_{T\in\mathcal{T}_{A}}\frac{x_{A}}{1-x_{A}}p_{T}$
$\displaystyle=\frac{x_{A}}{1-x_{A}}\sum_{T\in\mathcal{T}_{A}}p_{T}$
$\displaystyle\leq\frac{x_{A}}{1-x_{A}}.$

The last sum is bounded by one because occurences of particular trees $T$ in
$\mathcal{T}_{A}$ are all disjoint events.

Now sum over all $A$, and we’re done.

##  Chapter 12 Derandomization

Derandomization is the process of taking a randomized algorithm and turning it
into a deterministic algorithm. This is useful both for practical reasons
(deterministic algorithms are more predictable, which makes them easier to
debug and gives hard guarantees on running time) and theoretical reasons (if
we can derandomize any randomized algorithm we could show results like
$\mathbf{P}=\mathbf{RP}$,111The class $\mathbf{RP}$ consists of all languages
$L$ for which there is a polynomial-time randomized algorithm that correctly
outputs “yes” given an input $x$ in $L$ with probability at least $1/2$, and
never answers “yes” given an input $x$ not in $L$. See §1.5.2 for a more
extended description of $\mathbf{RP}$ and other randomized complexity classes.
which would reduce the number of complexity classes that complexity theorists
otherwise have to deal with). It may also be the case that derandomizing a
randomized algorithm can be used for probability amplification, where we
replace a low probability of success with a higher probability, in this case
$1$.

There are basically two approaches to derandomization:

  1. 1.

Reduce the number of random bits used down to $O(\log n)$, and then search
through all choices of random bits exhaustively. For example, if we only need
pairwise independence, we could use the XOR technique from §5.1.2.1 to replace
a large collection of variables with a small collection of random bits.

Except for the exhaustive search part, this is how randomized algorithms are
implemented in practice: rather than burning random bits continuously, a
pseudorandom generator is initialized from a seed consisting of a small number
of random bits. For pretty much all of the randomized algorithms we know
about, we don’t even need to use a particularly strong pseudorandom generator.
This is largely because current popular generators are the products of a
process of evolution: pseudorandom generators that cause wonky behavior or
fail to pass tests that approximate the assumptions made about them by typical
randomized algorithms are abandoned in favor of better generators.222Having
cheaper computers helps here as well. Nobody would have been willing to spend
2496 bytes on the state vector for Mersenne Twister [MN98] back in 1975, but
by 1998 this amount of memory was trivial for pretty much any computing device
except the tiniest microcontrollers.

From a theoretical perspective, pseudorandom generators offer the possibility
of eliminating randomization from all randomized algorithms, except there is a
complication. While (under reasonable cryptographic assumptions) there exist
cryptographically secure pseudorandom generators whose output is
indistinguishable from a genuinely random source by polynomial-time algorithms
(including algorithms originally intended for other purposes), such generators
are inherently incapable of reducing the number of random bits down to the
$O(\log n)$ needed for exhaustive search. The reason is that any pseudorandom
generator with only polynomially-many seeds can’t be cryptographically secure,
because we can distinguish it from a random source by just checking its output
against the output for all possible seeds. Whether there is some other method
for transforming an arbitrary algorithm in $\mathbf{RP}$ or $\mathbf{BPP}$
into a deterministic algorithm remains an open problem in complexity theory
(and beyond the scope of this course).

  2. 2.

Start with a specific randomized protocol and analyze its behavior enough that
we can replace the random bits it uses with specific, deterministically-chosen
bits we can compute. This is the main approach we will describe below. A non-
constructive variant of this shows that we can always replace the random bits
used by all inputs of a given size with a few carefully-selected fixed
sequences (Adleman’s Theorem, described in §12.2). More practical is the
method of conditional probabilities, which chooses random bits sequentially
based on which value is more likely to give a good outcome (see §12.4).

###  12.1 Deterministic vs. randomized algorithms

In thinking about derandomization, it can be helpful to have more than one way
to look at a randomized algorithm. So far, we’ve describe randomized
algorithms as random choices of deterministic algorithms ($M_{r}(x)$) or,
equivalently, as deterministic algorithms that happen to have random inputs
($M(r,x)$). This gives a very static view of how randomness is used in the
algorithm. A more dynamic view is obtained by thinking of the computation of a
randomized algorithm as a computation tree, where each path through the tree
corresponds to a computation with a fixed set of random bits and a branch in
the tree corresponds to a random decision. In either case we want an execution
to give us the right answer with reasonably high probability, whether that
probability measures our chance of getting a good deterministic machine for
our particular input or landing on a good computation path.

###  12.2 Adleman’s theorem

The idea of picking a good deterministic machine is the basis for Adleman’s
theorem[Adl78], a classic result in complexity theory. Adleman’s theorem says
that we can always replace randomness by an oracle that presents us with a
fixed string of advice $p_{n}$ that depends only on the size of the input $n$
and has size polynomial in $n$. The formal statement of the theorem relates
the class $\mathbf{RP}$, which is the class of problems for which there exists
a polynomial-time Turing machine $M(x,r)$ that outputs $1$ at least half the
time when $x\in L$ and never when $x\not\in L$; and the class
$\mathbf{P/poly}$, which is the class of problems for which there is a
polynomial-sized string $p_{n}$ for each input size $n$ and a polynomial-time
Turing machine $M^{\prime}$ such that $M^{\prime}(x,p_{\left\lvert
x\right\rvert}$) outputs $1$ if and only if $x\in L$.

######  Theorem 12.2.1.

$\mathbf{RP}\subseteq\mathbf{P/poly}$.

###### Proof.

The intuition is that if any one random string has a constant probability of
making $M$ happy, then by choosing enough random strings we can make the
probability that $M$ fails using on every random string for any given input so
small that even after we sum over all inputs of a particular size, the
probability of failure is still small using the union bound (4.1.1). This is
an example of probability amplification, where we repeat a randomized
algorithm many times to reduce its failure probability.

Formally, consider any fixed input $x$ of size $n$, and imagine running $M$
repeatedly on this input with $n+1$ independent sequences of random bits
$r_{1},r_{2},\dots,r_{n+1}$. If $x\not\in L$, then $M(x,r_{i})$ never outputs
$1$. If $x\in L$, then for each $r_{i}$, there is an independent probability
of at least $1/2$ that $M(x,r_{i})=1$. So $\Pr\left[{M(x,r_{i})=0}\right]\leq
1/2$, and $\Pr\left[{\forall iM(x,r_{i})=0}\right]\leq 2^{-(n+1)}$. If we sum
this probability of failure for each individual $x\in L$ of length $n$ over
the at most $2^{n}$ such elements, we get a probability that any of them fail
of at most $2^{n}2^{-(n+1)}=1/2$. Turning this upside down, any sequence of
$n+1$ random inputs includes a witness that $x\in L$ for _all_ inputs $x$ with
probability at least $1/2$. It follows that a good sequence
$r_{1},\dots,r_{n+1}$, exists.

Our advice $p_{n}$ is now some good sequence $p_{n}=\left\langle{r_{1}\dots
r_{n+1}}\right\rangle$, and the deterministic advice-taking algorithm that
uses it runs $M(x,r_{i})$ for each $r_{i}$ and returns true if and only if at
least one of these executions returns true. ∎

The classic version of this theorem shows that anything you can do with a
polynomial-size randomized circuit (a circuit made up of AND, OR, and NOT
gates where some of the inputs are random bits, corresponding to the $r$ input
to $M$) can be done with a polynomial-size deterministic circuit (where now
the $p_{n}$ input is baked into the circuit, since we need a different circuit
for each size $n$ anyway).

A limitation of this result is that ordinary algorithms seem to be better
described by uniform families of circuits, where there exists a polynomial-
time algorithm that, given input $n$, outputs the circuit $C_{n}$ for
processing size-$n$ inputs. In contrast, the class of circuits generated by
Adleman’s theorem is most likely non-uniform: the process of finding the good
witnesses $r_{i}$ is not something we know how to do in polynomial time (with
the usual caveat that we can’t prove much about what we can’t do in polynomial
time).

###  12.3 Limited independence

For some algorithms, it may be that full independence is not needed for all of
the random bits. If the amount of independence needed is small enough, this
may allow us to reduce the actual number of random bits consumed down to
$O(\log n)$, at which point we can try all possible sequences of random bits
in polynomial time.

Variants of this technique have been used heavily in the cryptography and
complexity; see [LW05] for a survey of some early work in this area. We’ll do
a quick example of the method before before moving onto more direct
approaches.

####  12.3.1 MAX CUT

Let’s look at the randomized MAX CUT algorithm from §11.2.1. In the original
algorithm, we use $n$ independent random bits to assign the $n$ vertices to
$S$ or $T$. The idea is that by assigning each vertex independently at random
to one side of the cut or the other, each edge appears in the cut with
probability $1/2$, giving a total of $m/2$ edges in the cut in expectation.

Suppose that we replace these $n$ independent random bits with $n$ pairwise-
independent bits generated by taking XORs of subsets of $\lceil\lg(n+1)\rceil$
independent random bits as described in §5.1.2.1. Because the bits are
pairwise-independent, the probability that the two endpoints of an edge are
assigned to different sides of the cut is still exactly $1/2$. So on average
we get $m/2$ edges in the cut as before, and there is at least one sequence of
random bits that guarantees a cut at least this big.

But with only $\lceil\lg(n+1)\rceil$ random bits, there are only
$2^{\lceil\log(n+1)\rceil}<2(n+1)$ possible sequences of random bits. If we
try all of them, then we find a cut of size $m/2$ always. The total cost is
$O(n(n+m))$ if we include the $O(n+m)$ cost of testing each cut. Note that
this algorithm does not generate all $2^{n}$ possible cuts, but among those it
_does_ generate, there must be a large one.

In this particular case, we’ll see below how to get the same result at a much
lower cost, using more knowledge of the problem. So we have the typical trade-
off between algorithm performance and algorithm designer effort.

###  12.4 The method of conditional probabilities

The method of conditional probabilities [Rag88] follows an execution of the
randomized algorithm, but at each point where we would otherwise make a random
decision, it makes a decision that minimizes the conditional probability of
losing.

Structurally, this is similar to the method of bounded differences (see
§5.3.3). Suppose our randomized algorithm generates $m$ random values
$X_{1},X_{2},\dots,X_{m}$. Let $f(X_{1},\dots,X_{m})$ be the indicator
variable for our randomized algorithm failing (more generally, we can make it
an expected cost or some other performance measure). Extend $f$ to shorter
sequences of values by defining
$f(x_{1},\dots,x_{k})=\operatorname{E}\left[{f(x_{1},\dots,x_{k},X_{k+1},\dots,X_{m})}\right]$.
Then $Y_{k}=f(X_{1},\dots,X_{k})$ is a Doob martingale, just as in the method
of bounded differences. This implies that, for any partial sequence of values
$x_{1},\dots,x_{k}$, there exists some next value $x_{k+1}$ such that
$f(x_{1},\dots,x_{k})\geq f(x_{1},\dots,x_{k},x_{k+1})$. If we can find this
value, we can follow a path on which $f$ always decreases, and obtain an
outcome of the algorithm $f(x_{1},\dots,x_{m})$ less than or equal to the
initial value $f(\left\langle{}\right\rangle)$. If our outcomes are $0$–$1$
(as in failure probabilities), and our initial value for $f$ is less than $1$,
this means that we reach an outcome with $f=0$.

The tricky part here is that it may be hard to compute $f(x_{1},\dots,x_{k}$).
(It’s always possible to do so in principle by enumerating all assignments of
the remaining variables, but if we have time to do this, we can just search
for a winning assignment directly.) What makes the method of conditional
probabilities practical in many cases is that it’s not necessary for $f$ to
compute the actual probability of failure, as long as (a) $f$ gives an upper
bound on the real probability of failure, at least in terminal configurations,
and (b) $f$ has the property used in the argument that for any partial
sequence $x_{1},\dots,x_{k}$ there exists an extension
$x_{1},\dots,x_{k},x_{k+1}$ with $f(x_{1},\dots,x_{k})\geq
f(x_{1},\dots,x_{k},x_{k+1})$. Such an $f$ is called a pessimistic estimator.
If we can find a pessimistic estimator that is easy to compute and starts out
less than $1$, then we can just follow it down the tree to a leaf that doesn’t
fail.

####  12.4.1 A trivial example

Here is a very bad randomized algorithm for generating a string of $n$ zeros:
flip $n$ coins, and output the results. This has a $1-2^{-n}$ probability of
failure, which is not very good.

We can derandomize this algorithm and get rid of all probability of failure at
the same time. Let $f(x_{1},\dots,x_{k})$ be the probability of failure after
the first $k$ bits. Then we can easily compute $f$ (it’s $1$ if any of the
bits are $1$ and $1-2^{-(n-k)}$ otherwise). We can use this to find a bit
$x_{k+1}$ at each stage that reduces $f$. After noticing that all of these
bits are zero, we improve the deterministic algorithm even further by leaving
out the computation of $f$.

####  12.4.2 Deterministic construction of Ramsey graphs

Here is an example that is slightly less trivial. For this example we let $f$
be a count of bad events rather than a failure probability, but the same
method applies.

Recall from §11.1.2 that if $k\geq 3$, for $n\leq 2^{k/2}$ there exists a
graph with $n$ nodes and no cliques or independent sets of size $k$. The proof
of this fact is to observe that each subset of $k$ vertices is bad with
probability $2^{-k+1}$, and when $\binom{n}{k}2^{-k+1}<1$, the expected number
of bad subsets in $G_{n,1/2}$ is less than $1$, showing that some good graph
exists.

We can turn this into a deterministic $n^{O(\log n)}$ algorithm for finding a
Ramsey graph in the worst case when $n=2^{k/2}$. The trick is to set the edges
to be present or absent one at a time, and for each edge, take the value that
minimizes the expected number of bad subsets conditioned on the choices so
far. We can easily calculate the conditional probability that a subset is bad
in $O(k)$ time: if it already has both a present and missing edge, it’s not
bad. Otherwise, if we’ve already set $\ell$ of its edges to the same value,
it’s bad with probability exactly $2^{-k+\ell}$. Summing this over all
$O(n^{k})$ subsets takes $O(n^{k}k)$ time per edge, and we have $O(n^{2})$
edges, giving $O(n^{k+2}k)=O\left(n^{(2\lg n+2+\lg\lg n)}\right)=n^{O(\log
n)}$ time total.

It’s worth mentioning that there are better deterministic constructions in the
literature. The best construction that I am aware of is given by an algorithm
of Barak et al. [BRSW06], which constructs a graph with $k^{\log^{c}k}$
vertices with no clique or independent set of size $k$ for any fixed $c$.

####  12.4.3 MAX CUT using conditional probabilities

Again we consider the algorithm from §11.2.1 that assigns vertices to $S$ and
$T$ at random. To derandomize this algorithm, at each step we pick a vertex
and assign it to the side of the cut that maximizes the conditional
expectation of the number of edges that cross the cut. We can compute this
conditional expectation as follows:

  1. 1.

For any edge that already has both endpoints assigned to $S$ or $T$, it’s
either in the cut or it isn’t: add $0$ or $1$ as appropriate to the
conditional expectation.

  2. 2.

For any edge with only one endpoint assigned, there’s a $1/2$ probability that
the other endpoint gets assigned to the other side (in the original randomized
algorithm). Add $1/2$ to the conditional expectation for these edges.

  3. 3.

For any edge with neither endpoint assigned, we again have a $1/2$ probability
that it crosses the cut. Add $1/2$ for these as well.

So now let us ask how assigning a particular previously unassigned vertex $v$
to $S$ or $T$ affects the conditional probability. For any neighbor $w$ of $v$
that is not already assigned, adding $v$ to $S$ or $T$ doesn’t affect the
$1/2$ contribution of $vw$. So we can ignore these. The only effects we see
are that if some neighbor $w$ is in $S$, assigning $v$ to $S$ decreases the
conditional expectation by $1/2$ and assigning $v$ to $T$ increases the
expectation by $1/2$. So to maximize the conditional expectation, we should
assign $v$ to whichever side currently holds fewer of $v$’s neighbors—the
obvious greedy algorithm, which runs in $O(n+m)$ time if we are reasonably
clever about keeping track of how many neighbors each unassigned node has in
$S$ and $T$. The advantage of the method of conditional probabilities here is
that we immediately get that the greedy algorithm achieves a cut of size
$m/2$, which might require actual intelligence to prove otherwise.

####  12.4.4 Set balancing

Here we have a collection of vectors $v_{1},v_{2},\dots,v_{n}$ in
$\left\\{{0,1}\right\\}^{m}$. We’d like to find $\pm 1$ coefficients
$\epsilon_{1},\epsilon_{2},\dots\epsilon_{n}$ that minimize
$\max_{j}\left\lvert X_{j}\right\rvert$ where
$X_{j}=\sum_{i=1}^{n}\epsilon_{i}v_{ij}$.

If we choose the $\epsilon_{i}$ randomly, Hoeffding’s inequality (5.3.1) says
for each fixed $j$ that $\Pr\left[{\left\lvert
X_{j}\right\rvert>t}\right]<2\exp(-t^{2}/2n)$ (since there are at most $n$
non-zero values $v_{ij}$). Setting $2\exp(-t^{2}/2n)\leq 1/m$ gives
$t\geq\sqrt{2n\ln 2m}$. So by the union bound, we have
$\Pr\left[{\max_{j}\left\lvert X_{j}\right\rvert>\sqrt{2n\ln 2m}}\right]<1$: a
solution exists.

Because there may be very complicated dependence between the $X_{j}$, it is
difficult to calculate the probability of the event $\bigcup_{j}[\left\lvert
X_{j}\right\rvert\geq t]$, whether conditioned on some of the $\epsilon_{i}$
or not. However, we can calculate the probability of the individual events
$[\left\lvert X_{j}\right\rvert\geq t]$ exactly. Conditioning on
$\epsilon_{1},\dots,\epsilon_{k}$, the expected value of $X_{j}$ is just
$\ell=\sum_{i=1}^{k}\epsilon_{i}v_{ij}$, and the distribution of
$Y=X_{j}-\operatorname{E}\left[{X_{j}}\right]$ is the sum $r\leq n-k$
independent $\pm 1$ random variables. So

$\displaystyle\Pr\left[{\left\lvert
X_{j}\right\rvert>t}\;\middle|\;{\epsilon_{1},\dots,\epsilon_{k}}\right]$
$\displaystyle=1-\Pr\left[{-t-\ell\leq Y\leq t-\ell}\right]$
$\displaystyle=\sum_{i=-t-\ell}^{t-\ell}\binom{r}{i}2^{-r}.$

This last expression involves a linear number of terms, each of which we can
calculate using a linear number of operations on rational numbers that fit in
a linear number of bits, so we can calculate the probability exactly in
polynomial time by just adding them up.

For our pessimistic estimator, we take

$U(\epsilon_{1},\dots,\epsilon_{k})=\sum_{i=j}^{n}\Pr\left[{\left\lvert
X_{j}\right\rvert>\sqrt{2n\ln
2m}}\;\middle|\;{\epsilon_{1},\dots,\epsilon_{k}}\right].$

Note that we can calculate each term in the sum by adding up a big pile of
binomial coefficients. Furthermore, since each term in the sum is a Doob
martingale, the sum is a martingale as well, so
$\operatorname{E}\left[{U(\epsilon_{1},\dots,\epsilon_{k+1})}\;\middle|\;{\epsilon_{1},\dots,\epsilon_{k}}\right]=U(\epsilon_{1},\dots,\epsilon_{k})$.
It follows that for any choice of $\epsilon_{1},\dots,\epsilon_{k}$ there
exists some $\epsilon_{k+1}$ such that $U(\epsilon_{1},\dots,\epsilon_{k})\geq
U(\epsilon_{1},\dots,\epsilon_{k+1})$, and we can determine this winning
$\epsilon_{k+1}$ explicitly. Our previous argument shows that
$U(\left\langle{}\right\rangle)<1$, which implies that our final value
$U(\epsilon_{1},\dots,\epsilon_{n})$ will also be less than $1$. Since $U$ is
an integer, this means it must be $0$, and we find an assignment in which
$\left\lvert X_{j}\right\rvert<\sqrt{2n\ln 2m}$ for all $j$.

##  Chapter 13 Quantum computing

Quantum computing is a currently almost-entirely-theoretical branch of
randomized algorithms that attempts to exploit the fact that probabilities at
a microscopic scale arise in a mysterious way from more fundamental
probability amplitudes, which are complex-valued and can cancel each other out
where probabilities can only add. In a quantum computation, we replace random
bits with quantum bits—qubits for short—and replace random updates to the bits
with quantum operations.

To explain how this works, we’ll start by re-casting our usual model of a
randomized computation to make it look more like the standard quantum circuits
of Deutsch [Deu89]. We’ll then get quantum computation by replacing all the
real-valued probabilities with complex-valued amplitudes.

###  13.1 Random circuits

Let’s consider a very simple randomized computer whose memory consists of two
bits. We can describe our knowledge of the state of this machine using a
vector of length $4$, with the coordinates in the vector giving the
probability of states $00$, $01$, $10$, and $11$. For example, if we know that
the initial state is always $00$, we would have the (column) vector

$\displaystyle\begin{bmatrix}1\\\ 0\\\ 0\\\ 0\end{bmatrix}.$

Any such state vector $x$ for the system must consist of non-negative real
values that sum to $1$; this is just the usual requirement for a discrete
probability space. Operations on the state consist of taking the old values of
one or both bits and replacing them with new values, possibly involving both
randomness and dependence on the old values. The law of total probability
applies here, so we can calculate the new state vector $x^{\prime}$ from the
old state vector $x$ by the rule

$\displaystyle x^{\prime}_{b^{\prime}_{1}b^{\prime}_{2}}$
$\displaystyle=\sum_{b_{1}b_{2}}x_{b_{1}b_{2}}\Pr\left[{X_{t+1}=b^{\prime}_{1}b^{\prime}_{2}}\;\middle|\;{X_{t}=b_{1}b_{2}}\right].$

These are linear functions of the previous state vector, so we can summarize
the effect of our operation using a transition matrix $A$, where
$x^{\prime}=Ax$.111Note that this is the reverse of the convention we adopted
for Markov chains in Chapter 9. There it was convenient to have
$P_{ij}=p_{ij}=\Pr\left[{X_{t+1}=j}\;\middle|\;{X_{t}=i}\right]$. Here we
defer to the physicists and make the update operator come in front of its
argument, like any other function.

We imagine that these operations are carried out by feeding the initial state
into some circuit that generates the new state. This justifies the calling
this model of computation a random circuit. But the actual implementation
might be an ordinary computer than is just flipping coins. If we can interpret
each step of the computation as applying a transition matrix, the actual
implementation doesn’t matter.

For example, if we negate the second bit $2/3$ of the time while leaving the
first bit alone, we get the matrix

$\displaystyle A$ $\displaystyle=\begin{bmatrix}1/3&2/3&0&0\\\ 2/3&1/3&0&0\\\
0&0&1/3&2/3\\\ 0&0&2/3&1/3\end{bmatrix}.$

One way to derive this matrix other than computing each entry directly is that
it is the tensor product of the matrices that represent the operations on each
individual bit. The idea here is that the tensor product of $A$ and $B$,
written $A\otimes B$, is the matrix $C$ with $C_{ij,k\ell}=A_{ik}B_{j\ell}$.
We’re cheating a little bit by allowing the $C$ matrix to have indices
consisting of pairs of indices, one for each of $A$ and $B$; there are more
formal definitions that justify this at the cost of being harder to
understand.

In this particular case, we have

$\displaystyle\begin{bmatrix}1/3&2/3&0&0\\\ 2/3&1/3&0&0\\\ 0&0&1/3&2/3\\\
0&0&2/3&1/3\end{bmatrix}$ $\displaystyle=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}\otimes\begin{bmatrix}1/3&2/3\\\ 2/3&1/3\end{bmatrix}.$

The first matrix in the tensor product gives the update rule for the first bit
(the identity matrix—do nothing), while the second gives the update rule for
the second.

Some operations are not decomposable in this way. If we swap the values of the
two bits, we get the matrix

$\displaystyle S$ $\displaystyle=\begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\
0&1&0&0\\\ 0&0&0&1\end{bmatrix},$

which maps $00$ and $11$ to themselves but maps $01$ to $10$ and vice versa.

The requirement for all of these matrices is that they be stochastic. This
means that each column has to sum to $1$, or equivalently that $1A=1$, where
$1$ is the all-ones vector. This just says that our operations map probability
distributions to probability distributions; we don’t apply an operation and
find that the sum of our probabilities is now $3/2$ or something. (Proof: If
$1A=1$, then $\left\lvert Ax\right\rvert_{1}=1(Ax)=(1A)x=1x=\left\lvert
x\right\rvert_{1}$.)

A randomized computation in this model now consists of a sequence of these
stochastic updates to our random bits, and at the end performing a measurement
by looking at what the values of the bits actually are. If we want to be
mystical about it, we could claim that this measurement collapses a
probability distribution over states into a single unique state, but really we
are just opening the box to see what we got.

For example, we could generate two bias-$2/3$ coin-flips by starting with $00$
and using the algorithm flip second, swap bits, flip second, or in matrix
terms:

$\displaystyle x_{\text{out}}$ $\displaystyle=ASAx_{\text{in}}$
$\displaystyle=\begin{bmatrix}1/3&2/3&0&0\\\ 2/3&1/3&0&0\\\ 0&0&1/3&2/3\\\
0&0&2/3&1/3\end{bmatrix}\begin{bmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{bmatrix}\begin{bmatrix}1/3&2/3&0&0\\\ 2/3&1/3&0&0\\\
0&0&1/3&2/3\\\ 0&0&2/3&1/3\end{bmatrix}\begin{bmatrix}1\\\ 0\\\ 0\\\
0\end{bmatrix}$ $\displaystyle=\begin{bmatrix}1/9\\\ 2/9\\\ 2/9\\\
4/9\end{bmatrix}.$

When we look at the output, we find $11$ with probability $4/9$, as we’d
expect, and similarly for the other values.

###  13.2 Bra-ket notation

A notational oddity that scares many people away from quantum mechanics in
general and quantum computing in particular is the habit of practitioners in
these fields of writing basis vectors and their duals using bra-ket notation,
a kind of typographical pun invented by the physicist Paul Dirac [Dir39].

This is based on a traditional way of writing an inner product of two vectors
$x$ and $y$ in “bracket form” as $\left\langle{x}\middle|{y}\right\rangle$.
The interpretation of this is
$\left\langle{x}\middle|{y}\right\rangle=x^{*}y$, where $x^{*}$ is the
conjugate transpose of $x$.

For real-valued $x$ the conjugate transpose is the same as the transpose. For
complex-valued $x$, each coordinate $x_{i}=a+bi$ is replaced by its complex
conjugate $\bar{x}_{i}=a-bi$.) Using the conjugate transpose makes
$\left\langle{x}\middle|{x}\right\rangle$ equal $\left\lvert
x\right\rvert_{2}^{2}$ when $x$ is complex-valued.

For example, for our vector $x_{\text{in}}$ above that puts all of its
probability on $00$, we have

$\displaystyle\left\langle{x_{\text{in}}}\middle|{x_{\text{in}}}\right\rangle$
$\displaystyle=\begin{bmatrix}1&0&0&0\end{bmatrix}\begin{bmatrix}1\\\ 0\\\
0\\\ 0\end{bmatrix}=1.$ (13.2.1)

The typographic trick is to split in half both
$\left\langle{x}\middle|{y}\right\rangle$ and its expansion. For example, we
could split (13.2.1) as

$\displaystyle\left\langle{x_{\text{in}}}\right\rvert$
$\displaystyle=\begin{bmatrix}1&0&0&0\end{bmatrix}$
$\displaystyle\left\lvert{x_{\text{in}}}\right\rangle$
$\displaystyle=\begin{bmatrix}1\\\ 0\\\ 0\\\ 0\end{bmatrix}.$

In general, wherever we used to have a bracket
$\left\langle{x}\middle|{y}\right\rangle$, we now have a bra
$\left\langle{x}\right\rvert$ and a ket $\left\lvert{y}\right\rangle$. These
are just row vectors and column vectors, and $\left\langle{x}\right\rvert$ is
always the conjugate transpose of $\left\lvert{x}\right\rangle$.

The second trick in bra-ket notation is to make the contents of the bra or ket
an arbitrary name. For kets, this will usually describe some state. As an
example, we might write $x_{\text{in}}$ as $\left\lvert{00}\right\rangle$ to
indicate that it’s the basis vector that puts all of its weight on the state
$00$. For bras, this is the linear operator that returns $1$ when applied to
the given state and $0$ when applied to any orthogonal state. So
$\left\langle{00}\right\rvert\left\lvert{00}\right\rangle=\left\langle{00}\middle|{00}\right\rangle=1$
but
$\left\langle{00}\right\rvert\left\lvert{01}\right\rangle=\left\langle{00}\middle|{01}\right\rangle=0$.

####  13.2.1 States as kets

This notation is useful for the same reason that variable names are useful.
It’s a lot easier to remember that $\left\lvert{01}\right\rangle$ refers to
the distribution assigning probability $1$ to state $01$ than that
${\begin{bmatrix}0&1&0&0\end{bmatrix}}^{\scriptscriptstyle{\top}}$ is.

Other vectors can be expressed using a linear combination of kets. For
example, we can write

$\displaystyle x_{\text{out}}$
$\displaystyle=\frac{1}{9}\left\lvert{00}\right\rangle+\frac{2}{9}\left\lvert{01}\right\rangle+\frac{2}{9}\left\lvert{10}\right\rangle+\frac{4}{9}\left\lvert{11}\right\rangle.$

This is not as compact as just writing out the vector as a matrix, but it has
the advantage of clearly labeling what states the probabilities apply to.

####  13.2.2 Operators as sums of kets times bras

A similar trick can be used to express operators, like the swap operator $S$.
We can represent $S$ as a combination of maps from specific states to specific
other states. For example, the operator

$\displaystyle\left\lvert{01}\right\rangle\left\langle{10}\right\rvert$
$\displaystyle=\begin{bmatrix}0\\\ 1\\\ 0\\\
0\end{bmatrix}\begin{bmatrix}0&0&1&0\end{bmatrix}=\begin{bmatrix}0&0&0&0\\\
0&0&1&0\\\ 0&0&0&0\\\ 0&0&0&0\end{bmatrix}$

maps $\left\lvert{10}\right\rangle$ to $\left\lvert{01}\right\rangle$ (Proof:
$\left\lvert{01}\right\rangle\left\langle{10}\right\rvert\left\lvert{10}\right\rangle=\left\lvert{01}\right\rangle\left\langle{10}\middle|{10}\right\rangle=\left\lvert{01}\right\rangle$)
and sends all other states to $0$. Add up four of these mappings to get

$\displaystyle S$
$\displaystyle=\left\lvert{00}\right\rangle\left\langle{00}\right\rvert+\left\lvert{10}\right\rangle\left\langle{01}\right\rvert+\left\lvert{01}\right\rangle\left\langle{10}\right\rvert+\left\lvert{11}\right\rangle\left\langle{11}\right\rvert=\begin{bmatrix}1&0&0&0\\\
0&0&1&0\\\ 0&1&0&0\\\ 0&0&0&1\end{bmatrix}.$

Here the bra-ket notation both labels what we are doing and saves writing a
lot of zeros.

The intuition is that just like a ket represents a state, a bra represents a
test for being in that state. So something like
$\left\lvert{01}\right\rangle\left\langle{10}\right\rvert$ tests if we are in
the $10$ state, and if so, sends us to the $01$ state.

###  13.3 Quantum circuits

So how do we turn our random circuits into quantum circuits?

The first step is to replace our random bits with quantum bits (qubits).

For a single random bit, the state vector represents a probability
distribution

$\displaystyle
p_{0}\left\lvert{0}\right\rangle+p_{1}\left\lvert{1}\right\rangle,$

where $p_{0}$ and $p_{1}$ are non-negative real numbers with $p_{0}+p_{1}=1$.

For a single qubit, the state vector represents amplitudes

$\displaystyle
a_{0}\left\lvert{0}\right\rangle+a_{1}\left\lvert{1}\right\rangle,$

where $a_{0}$ and $a_{1}$ are complex numbers with $\left\lvert
a_{0}\right\rvert^{2}+\left\lvert a_{1}\right\rvert^{2}=1$.222The absolute
value, norm, or magnitude $\left\lvert a+bi\right\rvert$ of a complex number
is given by $\sqrt{a^{2}+b^{2}}$. When $b=0$, this is the same as the absolute
value for the corresponding real number. For any complex number $x$, the norm
can also be written as $\sqrt{\bar{x}x}$, where $\bar{x}$ is the complex
conjugate of $x$. This is because
$\sqrt{(a+bi)(a-bi)}=\sqrt{a^{2}-(bi)^{2}}=\sqrt{a^{2}+b^{2}}$. The appearance
of the complex conjugate here explains why we define
$\left\langle{x}\middle|{y}\right\rangle=x^{*}y$; the conjugate transpose
means that for $\left\langle{x}\middle|{x}\right\rangle$, when we multiply
$x^{*}_{i}$ by $x_{i}$ we are computing a squared norm. The reason for this
restriction on amplitudes is that if we measure a qubit, we will see state $0$
with probability $\left\lvert a_{0}\right\rvert^{2}$ and state $1$ with
probability $\left\lvert a_{1}\right\rvert^{2}$. Unlike with random bits,
these probabilities are not mere expressions of our ignorance but arise
through a still somewhat mysterious process from the more fundamental
amplitudes.333In the old days of “shut up and calculate,” this process was
thought to involve the unexplained power of a conscious observer to collapse a
superposition into a classical state. Nowadays the most favored explanation
involves decoherence, the difficulty of maintaining superpositions in systems
that are interacting with large, warm objects with lots of thermodynamic
degrees of freedom (measuring instruments, brains). The decoherence
explanation is particularly useful for explaining why real-world quantum
computers have a hard time keeping their qubits mixed even when nobody is
looking at them. Decoherence by itself does not explain _which_ basis states a
system collapses to. Since bases in linear algebra are pretty much arbitrary,
it would seem that we could end up running into a physics version of Goodman’s
grue-bleen paradox [Goo83], but there are appearently ways of dealing with
this too using a mechanism called einselection [Zur03], that favors classical
states over weird ones. Since all of this is (a) well beyond my own limited
comprehension of quantum mechanics and (b) irrelevant to the theoretical model
we are using, these issues will not be discussed further.

With multiple bits, we get amplitudes for all combinations of the bits, e.g.

$\displaystyle\frac{1}{2}\left(\left\lvert{00}\right\rangle+\left\lvert{01}\right\rangle+\left\lvert{10}\right\rangle+\left\lvert{11}\right\rangle\right)$

gives a state vector in which each possible measurement will be observed with
equal probability $\left(\frac{1}{2}\right)^{2}=\frac{1}{4}$. We could also
write this state vector as

$\displaystyle\begin{bmatrix}1/2\\\ 1/2\\\ 1/2\\\ 1/2\end{bmatrix}.$

####  13.3.1 Quantum operations

In the random circuit model, at each step we pick a small number of random
bits, apply a stochastic transformation to them, and replace their values with
the results. In the quantum circuit model, we do the same thing, but now our
transformations must have the property of being unitary. Just as a stochastic
matrix preserves the property that the probabilities in a state vector sum to
$1$, a unitary matrix preserves the property that the squared norms of the
amplitudes in a state vector sum to $1$.

Formally, a square, complex matrix $A$ is unitary if it preserves inner
products:
$\left\langle{Ax}\middle|{Ay}\right\rangle=\left\langle{x}\middle|{y}\right\rangle$
for all $x$ and $y$. Alternatively, $A$ is unitary if $A^{*}A=AA^{*}=I$, where
$A^{*}$ is the conjugate transpose of $A$, because if this holds,
$\left\langle{Ax}\middle|{Ay}\right\rangle=(Ax)^{*}(Ay)=x^{*}A^{*}Ay=x^{*}Iy=x^{*}y=\left\langle{x}\middle|{y}\right\rangle$.
Yet another way to state this is that the columns of $A$ form an orthonormal
basis: this means that $\left\langle{A_{i}}\middle|{A_{j}}\right\rangle=0$ if
$i\neq j$ and $1$ if $i=j$, which is just a more verbose way to say
$A^{*}A=I$. The same thing also works if we consider rows instead of columns.

The rule then is: at each step, we can operate on some constant number of
qubits by applying a unitary transformation to them. In principle, this could
be _any_ unitary transformation, but some particular transformations show up
often in actual quantum algorithms.444Deutsch’s original paper [Deu89] shows
that repeated applications of single-qubit rotations and the CNOT operation
(described in §13.3.2) are enough to approximate any unitary transformation.

The simplest unitary transformations are permutations on states (like the
operator that swaps two qubits), and rotations of a single state. One
particularly important rotation is the Hadamard operator

$\displaystyle H$ $\displaystyle=\sqrt{\frac{1}{2}}\begin{bmatrix}1&1\\\
1&-1\end{bmatrix}.$

This maps $\left\lvert{0}\right\rangle$ to the superposition
$\sqrt{\frac{1}{2}}\left\lvert{0}\right\rangle+\sqrt{\frac{1}{2}}\left\lvert{1}\right\rangle$;
since this superposition collapses to either $\left\lvert{0}\right\rangle$ or
$\left\lvert{1}\right\rangle$ with probability $1/2$, the state resulting from
$H\left\lvert{0}\right\rangle$ is the quantum-computing equivalent of a fair
coin-flip. Note that
$H\left\lvert{1}\right\rangle=\sqrt{\frac{1}{2}}\left\lvert{0}\right\rangle-\sqrt{\frac{1}{2}}\left\lvert{1}\right\rangle\neq
H\left\lvert{0}\right\rangle$. Even though both yield the same probabilities;
these two superpositions have different phases and may behave differently when
operated on further. That $H\left\lvert{0}\right\rangle$ and
$H\left\lvert{1}\right\rangle$ are different is necessary, and indeed a
similar outcome occurs for any quantum operation: all quantum operations are
reversible, because any unitary matrix $U$ has an inverse $U^{*}$.

If we apply $H$ in parallel to all the qubits in our system, we get the
$n$-fold tensor product $H^{\otimes n}$, which (if we take our bit-vector
indices as integers $0\dots N-1=2^{n}-1$ represented in binary) maps
$\left\lvert{0}\right\rangle$ to
$\sqrt{\frac{1}{N}}\sum_{i=0}^{N-1}\left\lvert{i}\right\rangle$. So $n$
applications of $H$ effectively scramble a deterministic initial state into a
uniform distribution across all states. We’ll see this scrambling operation
again when we look at Grover’s algorithm in §13.5.

####  13.3.2 Quantum implementations of classical operations

One issue that comes up with trying to implement classical algorithms in the
quantum-circuit model is that classical operation are generally not
reversible: if I execution $x\leftarrow x\wedge y$, it may not be possible to
reconstruct the old state of $x$. So I can’t implement AND directly as a
quantum operation.

The solution is to use more sophisticated reversible operations from which
standard classical operations can be extracted as a special case. A simple
example is the controlled NOT or CNOT operator, which computes the mapping
$(x,y)\mapsto(x,x\oplus y)$. This corresponds to the matrix (over the basis
$\left\lvert{00}\right\rangle,\left\lvert{01}\right\rangle,\left\lvert{10}\right\rangle,\left\lvert{11}\right\rangle$)

$\displaystyle\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{bmatrix},$

which is clearly unitary (the rows are just the standard basis vectors). We
could also write this more compactly as
$\left\lvert{00}\right\rangle\left\langle{00}\right\rvert+\left\lvert{01}\right\rangle\left\langle{01}\right\rvert+\left\lvert{11}\right\rangle\left\langle{10}\right\rvert+\left\lvert{10}\right\rangle\left\langle{11}\right\rvert$.

The CNOT operator gives us XOR, but for more destructive operations we need to
use more qubits, possibly including junk qubits that we won’t look at again
but that are necessary to preserve reversibility. The Toffoli gate or
controlled controlled NOT gate (CCNOT) is a 3-qubit gate that was originally
designed to show that classical computation could be performed reversibly
[Tof80]. It implements the mapping $(x,y,z)\mapsto(x,y,(x\wedge y)\oplus z)$,
which corresponds to the $8\times 8$ matrix

$\displaystyle\begin{bmatrix}1&0&0&0&0&0&0&0\\\ 0&1&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&0\\\
0&0&0&0&0&0&0&1\\\ 0&0&0&0&0&0&1&0\end{bmatrix}.$

By throwing in some extra qubits we don’t care about, Toffoli gates can
implement basic operations like NAND ($(x,y,1)\mapsto(x,y,\neg(x\wedge y))$),
NOT ($(x,1,1)\mapsto(x,1,\neg x)$), and fan-out
($(x,1,0)\mapsto(x,1,x)$).555In the case of fan-out, this only works with
perfect accuracy for classical bits and not superpositions, which run into
something called the no-cloning theorem. For example, applying CCNOT to
$\frac{1}{\sqrt{2}}\left\lvert{010}\right\rangle+\frac{1}{\sqrt{2}}\left\lvert{110}\right\rangle$
yields
$\frac{1}{\sqrt{2}}\left\lvert{010}\right\rangle+\frac{1}{\sqrt{2}}\left\lvert{111}\right\rangle$.
This works, sort of, but the problem is that the first and last bits are still
entangled, meaning we can’t operate on them independently. This is actually
not all that different from what happens in the probabilistic case (if I make
a copy of a random variable $X$, it’s correlated with the original $X$), but
it has good or bad consequences depending on whether you want to prevent
people from stealing your information undetected or run two copies of a
quantum circuit on independent replicas of a single superposition. This gives
a sufficient basis for implementing all classical circuits.

####  13.3.3 Representing Boolean functions

Suppose we have a quantum circuit that computes a Boolean function $f$. There
are two conventions for representing the output of $f$:

  1. 1.

We can represent $f(x)$ by XORing it with an extra qubit $y$:
$\left\lvert{x,y}\right\rangle\mapsto\left\lvert{x,y\oplus
f(x)}\right\rangle$. This is the approach taken by the CNOT ($f(x)=x)$ and
CCNOT ($f(x_{1}x_{2})=x_{1}\wedge x_{2}$) gates.

  2. 2.

We can represent $f(x)$ by changing the phase of
$\left\lvert{x}\right\rangle$:
$\left\lvert{x}\right\rangle\mapsto(-1)^{f(x)}\left\lvert{x}\right\rangle$.
The actual unitary operator corresponding to this is
$\sum_{x}(-1)^{f(x)}\left\lvert{x}\right\rangle\left\langle{x}\right\rvert$,
which in matrix form looks like a truth table for $f$ expressed as $\pm 1$
values along the diagonal, e.g.:

$\displaystyle\begin{bmatrix}1&0&0&0\\\ 0&-1&0&0\\\ 0&0&-1&0\\\ 0&0&0&1\\\
\end{bmatrix}$

for the XOR function.

This has the advantage of requiring one fewer qubit, but we can’t observe the
value of $f(x)$ directly, because the amplitude of
$\left\lvert{x}\right\rangle$ is unchanged. Where this comes in handy is when
we can use the change in phase in the context of a larger quantum algorithm to
get cancellations for some values of $x$.

The first representation makes more sense for modeling classical circuits. The
second turns out to be more useful when $f$ is a subroutine in a larger
quantum algorithm. Fortunately, the operator with matrix

$\displaystyle\begin{bmatrix}1&0\\\ 0&-1\\\ \end{bmatrix}$

converts the $\left\lvert{0}\right\rangle$–$\left\lvert{1}\right\rangle$
representation into the $\pm 1$ representation, so we can build any desired
classical $f$ using
$\left\lvert{0}\right\rangle$–$\left\lvert{1}\right\rangle$ logic and convert
it to $\pm 1$ as needed.

####  13.3.4 Practical issues (which we will ignore)

The big practical question is whether any of these operations—or even non-
trivial numbers of independently manipulable qubits—can be implemented in a
real, physical system. As theorists, we can ignore these issues, but in real
life they are what would make quantum computing science instead of science
fiction.666Current technology, sadly, still puts quantum computing mostly in
the science fiction category.

####  13.3.5 Quantum computations

Putting everything together, a quantum computation consists of three stages:

  1. 1.

We start with a collection of qubits in some known state $x_{0}$ (e.g.,
$\left\lvert{000\dots 0}\right\rangle$).

  2. 2.

We apply a sequence of unitary operators $A_{1},A_{2},\dots A_{m}$ to our
qubits.

  3. 3.

We take a measurement of the final superposition $A_{m}A_{m-1}\dots
A_{1}x_{0}$ that collapses it into a single state, with probability equal to
the square of the amplitude of that state.

Our goal is for this final state to tell us what we want to know, with
reasonably high probability.

###  13.4 Deutsch’s algorithm

We now have enough machinery to describe a real quantum algorithm. Known as
Deutsch’s algorithm, this computes $f(0)\oplus f(1)$ while evaluating $f$ once
[Deu89]. The trick, of course, is that $f$ is applied to a superposition.

Assumption: $f$ is implemented reversibly, as a quantum computation that maps
$\left\lvert{x}\right\rangle$ to $(-1)^{f(x)}\left\lvert{x}\right\rangle$. To
compute $f(0)\oplus f(1)$, evaluate

$\displaystyle HfH\left\lvert{0}\right\rangle$
$\displaystyle=\sqrt{\frac{1}{2}}Hf\left(\left\lvert{0}\right\rangle+\left\lvert{1}\right\rangle\right)$
$\displaystyle=\sqrt{\frac{1}{2}}H\left((-1)^{f(0)}\left\lvert{0}\right\rangle+(-1)^{f(1)}\left\lvert{1}\right\rangle\right)$
$\displaystyle=\frac{1}{2}\left(\left((-1)^{f(0)}+(-1)^{f(1)}\right)\left\lvert{0}\right\rangle+\left((-1)^{f(0)}-(-1)^{f(1)}\right)\left\lvert{1}\right\rangle\right).$

Suppose now that $f(0)=f(1)=b$. Then the $\left\lvert{1}\right\rangle$ terms
cancel out and we are left with

$\displaystyle\frac{1}{2}\left(2\cdot(-1)^{b}\left\lvert{0}\right\rangle\right)$
$\displaystyle=(-1)^{b}\left\lvert{0}\right\rangle.$

This puts all the weight on $\left\lvert{0}\right\rangle$, so when we take our
measurement at the end, we’ll see $0$.

Alternatively, if $f(0)=b\neq f(1)$, it’s the $\left\lvert{0}\right\rangle$
terms that cancel out, leaving $(-1)^{b}\left\lvert{1}\right\rangle$. Again
the phase depends on $b$, but we don’t care about the phase: the important
thing is that if we measure the qubit, we always see $1$.

The result in either case is that with probability $1$, we determine the value
of $f(0)\oplus f(1)$, after evaluating $f$ once (albeit on a superposition of
quantum states).

This is kind of a silly example, because the huge costs involved in building
our quantum computer probably swamp the factor-of-2 improvement we got in the
number of calls to $f$. But a generalization of this trick, known as the
Deutsch-Josza algorithm [DJ92], solves the much harder (although still a bit
contrived-looking) problem of distinguishing a constant Boolean function on
$n$ bits from a function that outputs one for exactly half of its inputs. No
deterministic algorithm can solve this problem without computing at least
$2^{n}/2+1$ values of $f$, giving an exponential speed-up.777The speed-up
compared to a randomized algorithm that works with probability $1-\epsilon$ is
less impressive. With randomization, we only need to look at $O(\log
1/\epsilon)$ values of $f$ to see both a $0$ and a $1$ in the non-constant
case. But even here, the Deutsch-Josza algorithm does have the advantage of
giving the correct answer always.

###  13.5 Grover’s algorithm

Grover’s algorithm [Gro96] is one of two main exemplars for the astonishing
power of quantum computers.888The other is Shor’s algorithm [Sho97], which
allows a quantum computer to factor $n$-bit integers in time polynomial in
$n$. Sadly, Shor’s algorithm is a bit too complicated to talk about here. The
idea of Grover’s algorithm is that if we have a function $f$ on $N=2^{n}$
possible inputs whose value is $1$ for exactly one possible input $w$, we can
find this $w$ with high probability using $O(\sqrt{N})$ quantum evaluations of
$f$. As with Deutsch’s algorithm, we assume that $f$ is encoded as an operator
(conventionally written $U_{w}$) that maps each $\left\lvert{x}\right\rangle$
to $(-1)^{f(x)}\left\lvert{x}\right\rangle$.

The basic outline of the algorithm:

  1. 1.

Start in the superposition
$\left\lvert{s}\right\rangle=\sqrt{\frac{1}{N}}\sum_{x}\left\lvert{x}\right\rangle=H^{\otimes
n}\left\lvert{0}\right\rangle$.

  2. 2.

Alternate between applying the Grover diffusion operator
$D=2\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-I$ and the $f$
operator $U_{w}=2\left\lvert{w}\right\rangle\left\langle{w}\right\rvert-I$. Do
this $O(\sqrt{n})$ times (the exact number of iterations is important and will
be calculated below).

  3. 3.

Take a measurement of the state. It will be $w$ with high probability.

Making this work requires showing that (a) we can generate the original
superposition $\left\lvert{s}\right\rangle$, (b) we can implement $D$
efficiently using unitary operations on a constant number of qubits each, and
(c) we actually get $w$ at the end of this process.

####  13.5.1 Initial superposition

To get the initial superposition, start with $\left\lvert{0^{n}}\right\rangle$
and apply the Hadamard transform to each bit individually; this gives
$\sqrt{\frac{1}{N}}\sum_{x}\left\lvert{x}\right\rangle$ as claimed.

####  13.5.2 The Grover diffusion operator

We have the definition
$D=2\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-I$.

Before we try to implement this, let’s start by checking that it is in fact
unitary. Compute

$\displaystyle DD^{*}$
$\displaystyle=(2\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-I)^{2}$
$\displaystyle=4\left\lvert{s}\right\rangle\left\langle{s}\right\rvert\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-4\left\lvert{s}\right\rangle\left\langle{s}\right\rvert+I^{2}$
$\displaystyle=4\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-4\left\lvert{s}\right\rangle\left\langle{s}\right\rvert+I$
$\displaystyle=I.$

Here we use the fact that
$\left\lvert{s}\right\rangle\left\langle{s}\right\rvert\left\lvert{s}\right\rangle\left\langle{s}\right\rvert=\left\lvert{s}\right\rangle\left\langle{s}\middle|{s}\right\rangle\left\langle{s}\right\rvert=\left\lvert{s}\right\rangle(1)\left\langle{s}\right\rvert=\left\lvert{s}\right\rangle\left\langle{s}\right\rvert$.

Recall that $\left\lvert{s}\right\rangle=H^{\otimes
n}\left\lvert{0^{n}}\right\rangle$, where $H^{\otimes n}$ is the result of
applying $H$ to each of the $n$ bits individually. We also have that $H^{*}=H$
and $HH^{*}=I$, from which $H^{\otimes n}H^{\otimes n}=I$ as well.

So we can expand

$\displaystyle D$
$\displaystyle=2\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-I$
$\displaystyle=2H^{\otimes n}\left\lvert{0^{n}}\right\rangle(H^{\otimes
n}\left\lvert{0^{n}}\right\rangle)^{*}-I$ $\displaystyle=2H^{\otimes
n}\left\lvert{0^{n}}\right\rangle\left\langle{0^{n}}\right\rvert H^{\otimes
n}-I$ $\displaystyle=H^{\otimes
n}\left(2\left\lvert{0^{n}}\right\rangle\left\langle{0^{n}}\right\rvert-I\right)H^{\otimes
n}.$

The two copies of $H^{\otimes n}$ involve applying $H$ to each of the $n$
bits, which we can do. The operator in the middle,
$2\left\lvert{0^{n}}\right\rangle\left\langle{0^{n}}\right\rvert-I$, maps
$\left\lvert{0^{n}}\right\rangle$ to $\left\lvert{0^{n}}\right\rangle$ and
maps all other basis vectors $\left\lvert{x}\right\rangle$ to
$-\left\lvert{x}\right\rangle$. This can be implemented as a NOR of all the
qubits, which we can do using our tools for classical computations. So the
entire operator $D$ can be implemented using $O(n)$ qubit operations, most of
which can be done in parallel.

####  13.5.3 Effect of the iteration

To see what happens when we apply $U_{w}D$, it helps to represent the state in
terms of a particular two-dimensional basis. The idea here is that the initial
state $\left\lvert{s}\right\rangle$ and the operation $U_{w}D$ are symmetric
with respect to any basis vectors $\left\lvert{x}\right\rangle$ that aren’t
$\left\lvert{w}\right\rangle$, so instead of tracking all of these
non-$\left\lvert{w}\right\rangle$ vectors separately, we will represent all of
them by a single composite vector

$\displaystyle\left\lvert{u}\right\rangle$
$\displaystyle=\sqrt{\frac{1}{N-1}}\sum_{x\neq w}\left\lvert{x}\right\rangle.$

The coefficient $\sqrt{\frac{1}{N-1}}$ is chosen to make
$\left\langle{u}\middle|{u}\right\rangle=1$. As always, we like our vectors to
have length $1$.

Using $\left\lvert{u}\right\rangle$, we can represent

$\displaystyle\left\lvert{s}\right\rangle=\sqrt{\frac{1}{N}}\left\lvert{w}\right\rangle+\sqrt{\frac{N-1}{N}}\left\lvert{u}\right\rangle.$
(13.5.1)

A straightforward calculation shows that this indeed puts $\sqrt{\frac{1}{N}}$
amplitude on each $\left\lvert{x}\right\rangle$.

Now we’re going to bring in some trigonometry. Let
$\theta=\sin^{-1}\sqrt{\frac{1}{N}}$, so that $\sin\theta=\sqrt{\frac{1}{N}}$
and $\cos\theta=\sqrt{1-\sin^{2}\theta}=\sqrt{\frac{N-1}{N}}$. We can then
rewrite (13.5.1) as

$\displaystyle\left\lvert{s}\right\rangle=(\sin\theta)\left\lvert{w}\right\rangle+(\cos\theta)\left\lvert{u}\right\rangle.$
(13.5.2)

Let’s look at what happens if we expand $D$ using (13.5.2):

$\displaystyle D$
$\displaystyle=2\left\lvert{s}\right\rangle\left\langle{s}\right\rvert-I$
$\displaystyle=2\left((\sin\theta)\left\lvert{w}\right\rangle+(\cos\theta)\left\lvert{u}\right\rangle\right)\left((\sin\theta)\left\langle{w}\right\rvert+(\cos\theta)\left\langle{u}\right\rvert\right)-I$
$\displaystyle=(2\sin^{2}\theta-1)\left\lvert{w}\right\rangle\left\langle{w}\right\rvert+(2\sin\theta\cos\theta)\left\lvert{w}\right\rangle\left\langle{u}\right\rvert+(2\sin\theta\cos\theta)\left\lvert{u}\right\rangle\left\langle{w}\right\rvert+(2\cos^{2}\theta-1)\left\lvert{u}\right\rangle\left\langle{u}\right\rvert$
$\displaystyle=(-\cos
2\theta)\left\lvert{w}\right\rangle\left\langle{w}\right\rvert+(\sin
2\theta)\left\lvert{w}\right\rangle\left\langle{u}\right\rvert+(\sin
2\theta)\left\lvert{u}\right\rangle\left\langle{w}\right\rvert+(\cos
2\theta)\left\lvert{u}\right\rangle\left\langle{u}\right\rvert$
$\displaystyle=\begin{bmatrix}-\cos 2\theta&\sin 2\theta\\\ \sin 2\theta&\cos
2\theta\end{bmatrix},$

where the matrix is over the basis
$(\left\lvert{w}\right\rangle,\left\lvert{u}\right\rangle)$.

Multiplying by $U_{w}$ negates all the $\left\lvert{w}\right\rangle$
coefficients. So we get

$\displaystyle U_{w}D$ $\displaystyle=\begin{bmatrix}-1&0\\\
0&1\end{bmatrix}\begin{bmatrix}-\cos 2\theta&\sin 2\theta\\\ \sin 2\theta&\cos
2\theta\end{bmatrix}$ $\displaystyle=\begin{bmatrix}\cos 2\theta&-\sin
2\theta\\\ \sin 2\theta&\cos 2\theta\end{bmatrix}.$ (13.5.3)

Aficionados of computer graphics, robotics, or just matrix algebra in general
may recognize (13.5.3) as the matrix that rotates two-dimensional vectors by
$2\theta$. Since we started with $\left\lvert{s}\right\rangle$ at an angle of
$\theta$, after $t$ applications of this matrix we will be at an angle of
$(2t+1)\theta$, or in state

$\displaystyle\left(\sin(2t+1)\theta\right)\left\lvert{w}\right\rangle+\left(\cos(2t+1)\theta\right)\left\lvert{u}\right\rangle.$

Ideally, we pick $t$ so that $(2t+1)\theta=\pi/2$, which would put all of the
amplitude on $\left\lvert{w}\right\rangle$. Because $t$ is an integer, we
can’t do this exactly, but setting $t=\lfloor\frac{\pi/2\theta-1}{2}\rfloor$
will get us somewhere between $\pi/2-2\theta$ and $\pi/2$. Since
$\theta\approx\sqrt{\frac{1}{N}}$, this gives us a probability of seeing
$\left\lvert{w}\right\rangle$ in our final measurement of $1-O(\sqrt{1/N})$
after $O(\sqrt{N})$ iterations of $U_{w}D$.

Sadly, this is as good as it gets. A lower bound of Bennet et al. [BBBV97]
shows that _any_ quantum algorithm using $U_{w}$ as the representation for $f$
must apply $U_{w}$ at least $\Omega(\sqrt{N})$ times to find $w$. So we get a
quadratic speedup but not the exponential speedup we’d need to solve
$\mathbf{NP}$-complete problems directly.

##  Chapter 14 Randomized distributed algorithms

A distributed algorithm is one that runs on multiple machines that communicate
with each other in some way, typically via message-passing (an abstraction of
packet-based computer networks) or shared memory (an abstraction of multi-core
CPUs and systems with a common memory bus). What generally distinguishes
distributed computing from the closely-related idea of parallel computing is
that we expect a lot of nondeterminism in a distributed algorithm: events take
place at unpredictable times, processes may crash, and in particular bad cases
we may have Byzantine processes that work deliberately against the algorithm.
We are not going to assume Byzantine processes; instead, we’ll look at a
particular model called wait-free shared memory.

This hostile nondeterminism is modeled by an adversary that controls
scheduling and failures. For a shared-memory model, we have a collection of
processes that each have a pending operation that is either a read or write to
some register. The adversary chooses which of these pending operations happens
next (so that concurrency between processes is modeled by interleaving their
operations). Unlike the adversary that supplies the worst-case input to a
traditional algorithm before it executes, an adversary scheduler might be able
to observe the execution of a distributed algorithm in progress and adjust its
choices in response. If it has full knowledge of the system (including
internal states of processes), we call it an adaptive adversary; at the other
extreme is an oblivious adversary that chooses the schedule of which processes
execute operations at which times in advance. This is similar to the
distinction between an adaptive and oblivious adversary required for the
analysis of randomized data structures (see §6.3.1.

For either adversary, what makes the system wait-free is that any process that
gets to take an unbounded number of steps has to finish whatever it is doing
no matter how the other processes are scheduled. In particular, this means
that no process can wait for any of the others, because they might never be
scheduled. The processes that do run all run the algorithm correctly, so the
model is equivalent to assuming up to $n-1$ of the processes may crash but
that none are Byzantine.

As with traditional algorithms, distributed algorithms can use randomization
to make themselves less predictable. The assumption is that even if the
adversary is adaptive, it can’t predict the outcome of future coin-flips. For
some problems, avoiding such predictability is provably necessary.

Distributed computing is a huge field, and we aren’t going to be able to cover
much of it in the limited space we have here. So we are going to concentrate
on a few simple problems that give some of the flavor or randomized
distributed algorithms (and that lead to problems that are still open).

###  14.1 Consensus

The consensus problem is to get a collection of $n$ processes to agree on a
value. The requirements are that all the processes that don’t crash finish the
protocol (with probability $1$ for randomized protocols) (termination), that
they all output the same value (agreement), and that this value was an input
to one of the processes (validity)—this last condition excludes protocols that
always output the same value no matter what happens during the execution, and
makes consensus useful for choosing among values generated by some other
process.

There are many versions of consensus. The original problem as proposed by
Pease, Shostak, and Lamport [PSL80] assumes Byzantine processes in a
synchronous message-passing system. Here scheduling is entirely predictable,
and the obstacle to agreement is dissension sown by the lying Byzantine
processes. We will instead consider wait-free shared-memory consensus, where
scheduling is unpredictable but the the processes and memory are trustworthy.
Even in this case, the unpredictable scheduling makes solving the problem
deterministically impossible.

####  14.1.1 Impossibility of deterministic algorithms

The FLP impossibility result [FLP85] and its extension to shared memory
[LAA87] show that consensus is impossible to solve in an asynchronus model
with even one crash failure. The general proof is a bit involved, but there is
a simple intuitive proof of this result for the wait-free where up to $n-1$ of
the processes may crash.

Crash all but two processes, one with input $0$ and one with input $1$. Define
the preference of a process as the value it will decided in a solo execution
(this is well-defined because the processes are deterministic). In the initial
state, the process with input $b$ has preference $b$ because of validity—it
doesn’t know the other process exists. But before it returns $b$, it has to
cause the other process to change its preference (once it leaves the other
process is running alone). It can do so only by sending a message or writing a
register. When it is about to do this, stop it and run the other process until
it does the same thing.

Either the other process somehow neutralizes the effect of the delayed
message/write during this time, or it doesn’t. In the first case, restart the
first process (which still has its original preference and now must do
something else to make the other process change). In the second case, deliver
both operations and let the processes exchange preferences. The resulting
execution looks very much like when two people are trying to pass each other
in a hallway and oscillate back-and-forth—but since our process’s have their
timing controlled by an adversary, the natural damping or randomness that
occurs in humans doesn’t ever resolve the situation.

We can avoid this impossibility result with randomness. If either of the
process decides to choose a new preference at random, then there is a 50%
chance it will end up agreeing with the other one, no matter what the other
one is doing. Assuming we can detect this agreement, this solves consensus in
constant expected time for two processes.

Unfortunately, this flip-if-confused approach does not generalize very well to
$n$ processes. The first known randomized shared-memory algorithm for
consensus, due to Abrahamson [Abr88], used essentially this idea. But because
it required waiting for a long run of identical coin-flips across all
processes, it took $O\left(2^{n^{2}}\right)$ steps on average to finish. In a
little while, we will see how to do better.

###  14.2 Leader election

In a shared-memory system, leader election is a very similar problem to
consensus. Here we want one of the processes to decide that it is the leader,
and the rest to decide that they are followers. The difference from consensus
is that we don’t require that the followers learn the identity of the leader.
This means that followers can drop out before the algorithm determines the
leader, which may allow a faster algorithm.

Note however that if there are only two processes, the losing process knows
who the winner is, because there is only one possibility. So the same argument
that shows that we can’t do consensus deterministically with two processes
also works for leader election.

###  14.3 How randomness helps

We’ve already hinted at the idea of using randomness to shake processes into
agreement. In the current literature on shared-memory consensus and leader
election, this idea shows up in two main forms:

  1. 1.

We can replace the $n$ separate coin-flips of stalled processes with a single
weak shared coin protocol. This is a protocol that has for each outcome
$b\in\left\\{{0,1}\right\\}$ a minimum probablity $\delta>0$ that every
processes receives $b$ as the value of the coin. Because $\delta$ will
typically be less than $1/2$, it is possible that we get disagreements, or
that the adversary can bias the coin toward a particular value that it likes.
But with a bit of extra machinery that we will not describe here, we can get
agreement after $O(1/\delta)$ calls to the shared coin on average [AH90]. An
example of a weak shared coin protocol that assumes an adaptive adversary is
given in §14.4.

  2. 2.

We can eliminate processes quickly using a sifter, which solves a weak version
of leader election that allows for multiple winners but guarantees that the
expected number of winners is small relative to $n$. Repeated application of a
sifter can quickly knock the number of repeated winners down to $1$, which
solves leader election (§14.5. With some tinkering, it is possible to use some
sifters to also solve consensus (§14.6. In both cases we assume an oblivious
adversary.

###  14.4 Building a weak shared coin

The goal of a weak shared coin is to minimize the influence of the adversary
scheduler. An adaptive adversary can bias the outcome of the coin by looking
at the random values generated by the individual processes, and withholding
values that it doesn’t like by delaying any write operations by those
processes. So we would like to find a way to combine the local coins at the
processes together into a single global coin that minimizes the influence of
any particular local coin. The easiest way to do this is by applying the
majority function: each process repeatedly generates $\pm 1$ values with equal
probability and adds them to a common pile. When the pile includes enough
local coins, we take the sign of the total to get the return value of the
global coin.

The nice thing about this approach is that the behavior of the processes is
symmetric. It doesn’t matter what order the adversary runs them in, the next
coin-flip is always another fair coin-flip. So we can analyze the sequence of
partial sums of _generated_ coin-flips using the tools we have developed for
sums of independent variables, random walks, and martingales. Unfortunately
things get a little more complicated when we look at the totals actually
observed by any particular processes.

The problem is that we need some mechanism for gathering up the local coin
values. Using read-write registers, we can have each process write the count
and sum of its own local coins to a register writable by it alone (this avoids
processes overwriting each other). Because the adversary can only delay one
coin from each process, both total count and the total sum are always within
$n$ of the correct value. If we could read all the registers instantaneously
and stop as soon as the count reached some threshold $T$, then for
$T=\Theta(n^{2})$ the distribution on the generated coins would be spread out
enough that the total would be at least $n+1$ away from $0$ with constant
probability. But the actual situation is more complicated.

The problem is that each process must do $n$ sequential reads to read all the
registers. This is not only expensive—it’s not something we want to do after
every local flip—but it also means that more coins may be generated while I’m
reading the registers, meaning any sum I compute at the end of the algorithm
might have only a tenuous connection with the actual sum of the generated
coins at any point in the execution.

The solution to the first part of this problem was proposed by Bracha and
Rachman [BR91]: only check the total after writing out $\Theta(n/\log n)$
local coin-flips, giving an amortized cost per coin-flip of $\Theta(\log n)$
register operations. Unfortunately this makes the second problem worse: a
process $p$ might continue generating many local coins after the total count
crosses the threshold, and each other process might see a different prefix of
these coins depending on when it reads $p$’s register.

Bracha and Rachman showed that this wasn’t too much of a problem using Azuma’s
inequality (this is where the $O(\log n)$ factor comes in). But later work by
Attiya and Censor [AC08] allowed for a simpler analysis of a slightly
different algorithm, which we will describe here.

Pseudocode for the Attiya-Censor coin is given in Algorithm 14.1. The
algorithm only checks the total count once for every $n$ coin-flips, giving an
amortized cost of $1$ read per coin-flip. But to keep the processes for
running too long, each process checks a multi-writer stop bit after ever coin-
flip.

1while  _$\sum_{j=1}^{n}r_{j}.\textnormal{{{}count}} <T$_ do

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

3
$\left\langle{r_{i}.\textnormal{{{}count}},r_{i}.\textnormal{{{}sum}}}\right\rangle\leftarrow\left\langle{r_{i}.\textnormal{{{}count}}+1,r_{i}.\textnormal{{{}sum}}\pm
1}\right\rangle$

4 if  _stop_ then

5 break;

6

7 $\textnormal{{{}stop}}\leftarrow\textnormal{{{}true}}$

8 return
$\operatorname{sgn}\left(\sum_{j=1}^{n}r_{j}.\textnormal{{{}sum}}\right)$

9

Algorithm 14.1 Attiya-Censor weak shared coin [AC08]

Each process may see a different total sum at the end, but our hope is that if
$T$ is large enough, there is at least a $\delta$ probability that all these
total sums are positive (or, by symmetry, negative). We can represent the
total sum seen by any particular process $i$ as a sum $S+D+X_{i}-H_{i}$,
where:

  1. 1.

$S$ is the sum of the first $T$ coin-flips. This has a binomial distribution,
equal to the sum of $T$ independent $\pm 1$ random variables. Letting
$T=cn^{2}$ for some reasonably large $c$ gives us a constant probability that
$\lvert S\rvert>4n$.

  2. 2.

$D$ is the sum of all coin-flips after the first $T$ that are generated before
some process sets the stop bit. There are at most $n^{2}+n$ such coin-flips,
and they form a martingale with bounded increments. So Azuma’s inequality
gives us that $\lvert D\rvert\leq 2n$ with at least constant probabability,
independent of $S$.

  3. 3.

$X_{i}=\sum_{j=1}^{n}Y_{ij}$, where $Y_{ij}$ is the sum of all coin-flips
generated by process $j$ between some process setting the stop bit and process
$i$ reading $r_{j}$. Since each process can generate at most one extra coin-
flip before checking stop, $\lvert X_{i}\rvert\leq n$ always.

  4. 4.

$H_{i}=\sum_{j=1}^{n}Z_{ij}$, where $Z_{ij}$ is the sum of all votes that are
generated by process $j$ before $i$ reads $r_{j}$, but that are not included
in $r_{j}.\textnormal{{{}sum}}$ because they haven’t been written yet. Again,
each process can contribute only one coin-flip to $H_{i}$. So $\lvert
H_{i}\rvert\leq n$ always.

Adding up the error terms $D+X_{i}-H_{i}$ gives a total that is bounded by
$4n$ with at least constant probability. This probability is independent of
the constant probability that $\lvert S\rvert>4n$. So if both of these events
occur, we win.

The total cost of the coin is $O(T+n^{2})=O(n^{2})$. This also gives a cost of
$O(n^{2})$ for consensus.

This turns out to be optimal, because of a lower bound on the expected total
steps for consensus appearing in the same paper [AC08]. This is a bit
disappointing, because an $\Omega(n^{2})$ lower bound translates to
$\Omega(n)$ steps for each process even if we can distribute the load evenly
across all processes (which Algorithm 14.1 might not). We’d like to get
something that scales better, but to get around the lower bound we will need
to switch to an oblivious adversary.

###  14.5 Leader election with sifters

The idea of a sifter [AA11] is to use randomization to quickly knock out
processes while leaving at least one process always. The current best known
sifter for standard read-write registers, due to Giakkoupis and Woelfel
[GW12], is shown in Algorithm 14.2.

1Choose $r\in\mathbb{Z}^{+}$ such that $\Pr\left[{r=i}\right]=2^{-i}$

2 $A[r]\leftarrow 1$

3 if  _$A[r+1]=0$_ then

4 stay

5

6else

7 leave

8

Algorithm 14.2 Giakkoupis-Woelfel sifter [GW12]

The cost of executing the sifter is two operations. Each process chooses an
index $r$ according to a geometric distribution, writes $A[r]$, and then
checks if any other process has written $A[r+1]$. The process stays if it sees
nothing.

Because any process with the maximum value of $r$ always stays, at least one
process stays. To show that not too many processes stay, let $X_{i}$ be the
number of survivors with $r=i$. This will be bounded by the number of
processes that write to $A[i]$ before any process writes to $A[i+1]$. We can
immediately see that $\operatorname{E}\left[{X_{i}}\right]\leq n\cdot 2^{-i}$,
since each process has probability $2^{-i}$ of writing to $A[i]$. But we can
also argue that $\operatorname{E}\left[{X_{i}}\right]\leq 2$ for any value of
$n$.

The reason is that because the adversary is oblivious, the choice of which
process writes next is independent of the location it writes to. If we
condition on some particular write being to either $A[i]$ or $A[i+1]$, there
is a $1/3$ chance that it writes to $A[i+1]$. So we can think of the
subsequence of writes that either land in $A[i+1]$ or $A[i]$ as a sequence of
biased coin-flips, and we are counting how many probability-$2/3$ tails we get
before the first probability-$1/3$ heads. This will be $2$ on average, or at
most $2$ if we take into account that we will stop after $n$ writes.

We thus have $\operatorname{E}\left[{X_{i}}\right]\leq\min(2,n\cdot 2^{-i})$.
So the expected total number of winners is bounded by
$\sum_{i=1}^{\infty}\operatorname{E}\left[{X_{i}}\right]\min(2,n\cdot
2^{-i})=2\lg n+O(1)$.

Now comes the fun part. Take all the survivors of our sifter, and run them
through more sifters. Let $S_{i}$ be the number of survivors of the first $i$
sifters. We’ve shown that
$\operatorname{E}\left[{S_{i+1}}\;\middle|\;{S_{i}}\right]=O(\log S_{i})$.
Since $\log$ is concave, Jensen’s inequality then gives
$\operatorname{E}\left[{S_{i+1}}\right]=O(\log\operatorname{E}\left[{S_{i}}\right])$.
Iterating this gives
$\operatorname{E}\left[{S_{i}}\right]=O(\log^{(i)}S_{0})=O(\log^{(i)}n)$. So
there is some $i=O(\log^{*}n$ at which $\operatorname{E}\left[{S_{i}}\right]$
is a constant.

This doesn’t quite give us leader election because the constant might not be
$1$. But there are known leader election algorithms that run in $O(1)$ time
with $O(1)$ expected participants [AAG+10], so we can use these to clean up
any excess processes that make it through all the sifters. The total cost is
$O(\log^{*}n)$ operations for each process.

###  14.6 Consensus with sifters

We’ve seen that we can speed up leader election by discarding potential
leaders quickly. For consensus, we want to discard potential output values
quickly. This is a little more complicated, because processes carrying losing
output values can’t just drop out if we haven’t determined the winning values
yet.

We are going to look at an algorithm by Aspnes and Er [AE19] that solves
consensus in $O(\log^{*}n)$ operations per process, using sifters built on top
of a stronger primitive than normal registers. (This algorithm uses some ideas
from an earlier paper of Aspnes [Asp15], which gives a more complicated
$O(\log\log n)$-time algorithm for standard registers.) As with the
Giakkoupis-Woelfel leader election algorithm, we assume an oblivious adversary
scheduler.

The stronger primitive we need is a max register[AACH12]. Unlike a standard
register, reading a max register returns the largest value ever written to it;
equivalently, trying to write a smaller value to a max register than it
already contains has no effect.

What this means for randomized algorithms is that we can knock out values
using a max register by a simple priority scheme. If each process writes a
tuple $\left\langle{r,v}\right\rangle$ to the max register, where $r$ is a
unique random priority and $v$ is the process’s preferred value, then the
$i$-th value written appears in the max register only if it is a left-to-right
maximum of the sequence of priorities, which occurs with probability roughly
$1/i$. (This follows from symmetry and the fact that the oblivious adversary
can’t selectively schedule smaller priorities first.) So on average only
$H_{n}=O(\log n)$ of these values will ever appear in the max register. By
having each process read and return a value from the max register, we’ve gone
from $n$ possible values to $O(\log n)$ possible values on average.

We now run into two technical obstacles. The first is that we can’t
necessarily guarantee that all the random priorities are unique, which we
would need to get an exact $1/i$ probability for survival. This can be dealt
with by choosing priorities over a sufficiently large range that the rare
collisions don’t add much to the expected survivors (say, $O(n^{3})$). The
second issue is that if we try to iterate the sifter, in the second round we
have many copies of each input value. So even if one copy drops out because of
a low priority, some other copy might get lucky and survive. To go from
$O(\log n)$ expected values to $O(\log\log n)$ expected values, we need to
make sure that no value gets more than one chance at surviving.

Here is where we use an idea that first appeared in [Asp15]. Instead of
generating a new priority for each value in each round, we generate a sequence
$r_{1},r_{2},\dots,r_{\ell}$ of priorities for all $\ell$ rounds all at once
at the beginning. We can then store
$\left\langle{r_{i},\dots,r_{\ell},v}\right\rangle$ in the max register for
round $i$, and the leading priority $r_{i}$ controls survival. Now we don’t
care about having multiple copies of a value, because they will all have the
same initial $r_{i}$, and if the first copy to be written doesn’t survive,
none of them will.

The result of applying this idea is Algorithm 14.3. Because each iteration of
the loop reduces $S_{i}$ survivors to $S_{i+1}=O(\log S_{i})$ survivors on
average, the same application of Jensen’s inequality that we used for
Algorithm 14.2 works here as well, so for an appropriate $\ell=O(\log^{*}n)$
we can get down to a single surviving value with reasonably high probability.

1procedure  _$\textnormal{{{}sifter}}(v)$_

2 Choose random ranks $r_{1}\dots r_{\ell}$

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

4
$\textnormal{{{}writeMax}}(M_{i},\left\langle{r_{i},\dots,r_{\ell},v}\right\rangle)$

5
$\left\langle{r_{i},\dots,r_{\ell},v}\right\rangle\leftarrow\textnormal{{{}readMax}}(M_{i})$

6

7 return $v$

8

Algorithm 14.3 Sifter using max registers [AE19]

This is not quite enough to get consensus, which requires agreement always,
but with some additional machinery it is possible to detect when the protocol
fails and re-run it if necessary. The final result is consensus in expected
$O(\log^{*}n)$ max register operations.

##  Appendix A Sample assignments from Fall 2019

###  A.1 Assignment 1: due Thursday, 2019-09-12, at 23:00

#### Bureaucratic part

Send me email! My address is<EMAIL_ADDRESS>
In your message, include:

  1. 1.

Your name.

  2. 2.

Your status: whether you are an undergraduate, grad student, auditor, etc.

  3. 3.

Whether you are taking the course as CPSC 469 or CPSC 569.

  4. 4.

Anything else you’d like to say.

(You will not be graded on the bureaucratic part, but you should do it
anyway.)

####  A.1.1 The golden ticket

An infamous candy company announces it is placing a golden ticket uniformly at
random in one of $n$ candy bars that are distributed to $n$ children, with
unimaginable wealth to be bestowed on the child who receives the ticket.
Unfortunately, the candy company owner is notorious for trickery and lies, so
the probability that the golden ticket actually exists is only $1/2$.

Consider the last child to open their candy bar, and what estimate they should
make of their probability of winning after seeing the first $k$ children open
their candy bars to find no ticket.

An optimist reasons: If the ticket does exist, then the last child’s chances
went from $1/n$ to $1/(n-k)$. So the fact that none of the first $k$ children
got the ticket is good news!

A pessimist reasons: The more candy bars are opened without seeing the ticket,
the more likely it is that the ticket doesn’t exist. So the fact that none of
the first $k$ children got the ticket is bad news!

Which of them is right? Compute the probability that the last child receives
the ticket given the first $k$ candy bars come up empty, and compare this to
the probability that the last child receives the ticket given no information
other than the initial setup of the problem.

##### Solution

Let $W$ be the event that the last child wins, $C$ the event that the candy
bar exists, and $L_{k}$ the event that the first $k$ children lose.

Without conditioning, we have

$\displaystyle\Pr\left[{W}\right]$
$\displaystyle=\Pr\left[{W}\;\middle|\;{C}\right]\Pr\left[{C}\right]+\Pr\left[{W}\;\middle|\;{\neg
C}\right]\Pr\left[{\neg C}\right]$
$\displaystyle=\frac{1}{n}\cdot\frac{1}{2}+0\cdot\frac{1}{2}$
$\displaystyle=\frac{1}{2n}.$ With conditioning, we have
$\displaystyle\Pr\left[{W}\;\middle|\;{L_{k}}\right]$
$\displaystyle=\frac{\Pr\left[{W\wedge
L_{k}}\right]}{\Pr\left[{L_{k}}\right]}$
$\displaystyle=\frac{1/2n}{\Pr\left[{L_{k}}\right]{C}\Pr\left[{C}\right]+\Pr\left[{L_{k}}\right]{\neg
C}\Pr\left[{\neg C}\right]}$
$\displaystyle=\frac{1/2n}{\frac{n-k}{n}\cdot\frac{1}{2}+1\cdot\frac{1}{2}}$
$\displaystyle=\frac{1/2n}{\frac{n-k}{2n}+\frac{1}{2}}$
$\displaystyle=\frac{1/2n}{\frac{2n-k}{2n}}$ $\displaystyle=\frac{1}{2n-k}.$

Since $\frac{1}{2n-k}>\frac{1}{2n}$ when $k>0$, the optimist is correct.

####  A.1.2 Exploding computers

Suppose we have a system of $3n$ machines $m_{0},m_{2},\dots m_{3n-1}$ in a
ring, and we turn each machine on at random with independent probability $p$.
Over time, the machines may overheat: if we turn on three consecutive machines
$m_{i},m_{i+1},$ and $m_{i+2}$ (wrapping indices around mod $3n$), the middle
machine $m_{i+1}$ overheats and explodes. Explosions happen simultaneously and
are purely a function of which machines are initially turned on; so if
$m_{1},m_{2},m_{3},m_{4},$ and $m_{5}$ are all turned on, $m_{2},m_{3},$ and
$m_{4}$ will all explode.

Call a machine a active if it is turned on and does not explode.

We want to choose $p$ to maximize the number of active machines $X$. But there
are two ways to interpret this goal.

  1. 1.

Suppose our goal is to maximize the _expected_ number of active machines
$\operatorname{E}\left[{X}\right]$. What value of $p$ should we choose, and
what does this give us for $\operatorname{E}\left[{X}\right]$?

  2. 2.

Suppose instead our goal is to maximize the probability of having the maximum
possible number of active machines. More formally, letting $M$ be the number
of survivors we could get if we chose which machines to turn on optimally, we
want to choose $p$ to maximize $\Pr\left[{X=M}\right]$. What value of $p$
should we choose, and what does this give us for $\Pr\left[{X=M}\right]$?

##### Solution

  1. 1.

Let $A_{i}$ be the event that machine $m_{i}$ is active, and let $X_{i}$ be
the indicator variable for $m_{i}$ being active and not exploding. We are
trying to maximize $\operatorname{E}\left[{\sum
X_{i}}\right]=\sum\operatorname{E}\left[{X_{i}}\right]=n\operatorname{E}\left[{X_{1}}\right]$,
where the last equation holds by symmetry.

Observe that $X_{1}=1$ if $A_{1}$ occurs and it is not the case that both
$A_{0}$ and $A_{2}$ occur. This gives
$\operatorname{E}\left[{X_{1}}\right]=\Pr\left[{X_{1}=1}\right]=p(1-p^{2})=p-p^{3}$.
By setting the derivative $1-3p^{2}$ to zero we find a unique extremum at
$p=\sqrt{1/3}$; this is a maximum since $p(1-p^{2})=0$ at the two corner
solutions $p=0$ and $p=1$. Setting $p=\sqrt{1/3}$ gives
$3n\operatorname{E}\left[{X_{i}}\right]=3n\cdot\sqrt{1/3}(2/3)=n\frac{2}{\sqrt{3}}\approx
n\cdot 1.154701\dots$.

  2. 2.

First we need to figure out $M$.

We can assume that we set up the optimal configuration so that none explode,
because any initial configuration that produces explosions can be replaced by
one where the dead machines are just turned off to start with, with no
reduction in the number of active machines.

Conveniently, we can divide the machines into consecutive groups of three, and
observe that (a) turning on the first two machines in each group causes no
explosions, (b) turning on three machines in any group causes the middle one
to explode. This shows $M=2n$ is the maximum achievable number of machines,
because (a) lets us get $M$ and (b) says we can’t do more, since this would
give us a group with three by the Pigeonhole Principle.

We still need to characterize how many possible patterns of $M=2n$ machines
produce no explosions. Since we can only have two consecutive active machines,
each pair of active machines must be followed by an inactive machine. Putting
two inactive machines in a row would allow a partitioning into groups of three
with some group getting only one active machine, leaving some other group with
three, which is trouble. So the pattern must consist of pairs of active
machines alternating with single inactive machines. There are exactly three
ways to do this.

Each of these three patterns occurs with probability $p^{2n}q^{n}$ where
$q=1-p$. Maximizing this probability can again be done by taking the