derivative $2np^{2n-1}q^{n}-np^{2n}q^{n-1}$ and setting to $0$. Removing
common factors gives $2q-p=0$, or $2-3p=0$, giving $p=2/3$, which is about
what one would expect.

We then get $\Pr\left[{X=2n}\right]=3\cdot(2/3)^{2n}(1/3)^{n}$. This is pretty
small for reasonably large $n$, which suggests that a randomized algorithm may
not be the best in this case.

###  A.2 Assignment 2: due Thursday, 2019-09-26, at 23:00

####  A.2.1 A logging problem

An operating system generates a new log entry at time $t$ with independent
probability $p_{t}$, and the size of each log entry for any $t$ is an integer
$X$ chosen uniformly in the range $a\leq X\leq b$, where the choice of $X$ at
a particular time $t$ is independent of all the other log entry sizes and all
choices of whether to write a log entry.

Suppose that over some fixed period of time, the operating system generates
$n$ log entries on average. Compute the expectation of the total size $S$ of
all the log entries, and show that the probability that $S$ is more than a
small constant fraction larger than $\operatorname{E}\left[{S}\right]$ is
exponentially small as a function of $n$.

##### Solution

For each $t$, let $X_{t}$ be the size of the log entry at time $t$. Then
$\operatorname{E}\left[{S}\right]=\sum_{t}\operatorname{E}\left[{X_{t}}\right]=\sum_{t}p_{t}\frac{a+b}{2}=\frac{a+b}{2}\operatorname{E}\left[{\sum_{t}p_{t}}\right]=\frac{a+b}{2}\cdot
n$.

We can’t use Chernoff bounds directly on the $X_{t}$ because they aren’t
Bernoulli random variables, and we can’t use Hoeffding’s inequality because we
don’t actually know how many of them there are. So we will use Chernoff first
to bound the number of nonzero $X_{t}$ and then use Hoeffding to bound their
sum.

The easiest way to think about this is to imagine we generate the nonzero
$X_{t}$ by generating a sequence of independent values $Y_{1},Y_{2},\dots$,
with each $Y_{i}$ uniform in $[a,b]$, then select the $i$-th nonzero $X_{t}$
to have value $Y_{i}$.

Let $Z_{t}$ be the indicator variable for the event that a log entry is
written at time $t$. Then $N=\sum_{t}Z_{t}$ gives the total number of log
entries, and
$\operatorname{E}\left[{N}\right]=\operatorname{E}\left[{\sum_{t}Z_{t}}\right]=\sum_{t}p_{t}=n$.

Pick some $\delta<1$; then Chernoff’s inequality (5.2.2) gives

$\displaystyle\Pr\left[{N\geq(1+\delta)n}\right]$ $\displaystyle\leq
e^{-n\delta^{2}/3}.$

Suppose $N<(1+\delta)n$. Then
$\sum_{t}X_{t}=\sum_{i=1}^{N}Y_{i}\leq\sum_{i=1}^{(1+\delta)n}Y_{i}$. This
last quantity is a sum of independent bounded random variables, so we can
apply the asymmetric version of Hoeffding’s inequality (5.3.16) to get

$\displaystyle\Pr\left[{\sum_{i=1}^{(1+\delta)n}Y_{i}-(1+\delta)n\cdot\frac{a+b}{2}\geq
s}\right]$
$\displaystyle\leq\exp\left(-\frac{s^{2}}{2(1+\delta)n\left(\frac{b-a}{2}\right)^{2}}\right)$

For $s=\delta n\cdot\frac{a+b}{2}$ this gives a bound of

$\displaystyle\exp\left(-\frac{-\delta^{2}n^{2}\left(\frac{a+b}{2}\right)^{2}}{2(1+\delta)n\left(\frac{b-a}{2}\right)^{2}}\right)$
$\displaystyle\leq\exp\left(-\frac{-\delta^{2}n\left(\frac{a+b}{2}\right)^{2}}{2(1+\delta)\left(\frac{b+a}{2}\right)^{2}}\right)$
$\displaystyle=\exp\left(-\frac{-\delta^{2}n}{2(1+\delta)}\right).$

If we put this all together, we get

$\displaystyle\Pr\left[{S\geq(1+2\delta)n\frac{a+b}{2}}\right]$
$\displaystyle\leq
e^{-n\delta^{2}/3}+e^{-n\delta^{2}/2(1+\delta)}=e^{-\Theta(n)}.$

####  A.2.2 Return of the exploding computers

Suppose we are working in the model described in §A.1.2, where $3n$ machines
in a ring are each turned on independently at random with probability $p$, and
a machine remains active only if it is turned on and at least one of its
neighbors is not turned on. We have seen that an optimal choice of $p$ gives
$cn$ active machines on average for a constant $c$ independent of $n$.

Unfortunately, averages are not good enough for our customers. Show that there
is a choice of $p$ and constants $c^{\prime}>0$ and $\delta>0$ such that at
least $c^{\prime}n$ machines are active with probability at least
$1-e^{-\delta n}$ for any $n$.

##### Solution

We can use the method of bounded differences. Let $X_{i}$ be the indicator for
the event that machine $i$ is turned on, and let $S=f(X_{1},\dots,X_{3n})$
compute the number of active machines. Then changing one input to $f$ from $0$
to $1$ increases $f$ by at most $1$, and decreases it by at most $2$ (since it
may be that the new machine explodes, producing no increase, and it also
explodes both neighbors, producing a net $-2$ change). So McDiarmid’s
inequality (5.3.12) applies with $c_{i}=2$ for all $i$, giving

$\displaystyle\Pr\left[{f(X_{1},\dots,X_{3n}-\operatorname{E}\left[{f(X_{1},\dots,X_{3n}}\right]\leq
t}\right]$ $\displaystyle\leq\exp\left(-\frac{2t^{2}}{3n\cdot 2^{2}}\right)$
$\displaystyle=e^{-t^{2}/6n}.$

Choose $p$ to maximize the expected number of active machines, and let
$\operatorname{E}\left[{S}\right]=c^{\prime}n$. Choose $c$ so that
$0<c<c^{\prime}$. Then $\Pr\left[{S\leq
cn}\right]=\Pr\left[{S-\operatorname{E}\left[{S}\right]\leq
c^{\prime}n-cn}\right]\leq
e^{-(c^{\prime}-c)^{2}n^{2}/6n}=e^{-(c^{\prime}-c)^{2}n/6}=e^{-\delta n}$,
where $\delta=(c^{\prime}-c)^{2}/6>0$.

The above is my original sample solution, below are some quick sketches of
alternative approaches that showed up in submissions:

  * •

Analyze the dependence and use Lemma 5.2.2. This gives similar results to
McDiarmid’s inequality with a bit more work. The basic idea is that
$\operatorname{E}\left[{X_{i}|X_{1}\dots X_{i-1}}\right]\geq p(1-p)$ for
$i<3n$ whether or not $X_{i-1}$ is $1$ (we don’t care about the other
variables). So we can let $p_{i}=p(1-p)$ for these values of $i$. To avoid
wrapping around at the end, either omit $X_{3n}$ entirely or let $p_{3n}=0$.

  * •

Even simpler: Let $Y_{i}$ be the indicator for the event that machine $i$ is
active. Then $Y_{3},Y_{6},\dots,Y_{3n}$ are all independent, and we can bound
$\sum_{i=1}^{n}Y_{3i}\leq\sum_{i=1}^{3n}Y_{i}$ using either Chernoff or
Hoeffding.

###  A.3 Assignment 3: due Thursday, 2019-10-10, at 23:00

####  A.3.1 Two data plans

A cellphone company offers a choice of two data plans, both based on
penalizing the user whenever they use more data than in the past. For both
plans the assumption is that your data usage in each month
$i\in\left\\{{0\dots\infty}\right\\}$ is an independent continuous random
variable that is uniform in the range $[0,c]$ for some fixed constant $c$.

With Plan A, you pay a penalty of $1 for every month $i$ in which your usage
$X_{i}$ exceeds $\max_{j<i}X_{j}$. This excludes month $0$, for which the max
of the previous empty set is taken to be $+\infty$.

With Plan B, you pay a penalty of $100 for every pair of months $2i$ and
$2i+1$ in which $X_{2i}$ and $X_{2i+1}$ both exceed $\max_{j<2i}X_{j}$. As in
Plan A, you never pay a penalty for the pair of months $0$ and $1$.

  1. 1.

Suppose that you expect to live forever (and keep whatever plan you pick
forever as well). If your goal is to minimize your expected total cost over
eternity, which plan should you pick?

  2. 2.

Which plan is cheaper on average if you don’t plan to live for more than, say,
the next 1000 years?

(Assume no discounting of future payments in either case.)

##### Solution

Let $A_{i}$ be the event that we pay a penalty in month $i$ with plan $A$, and
let $B_{i}$ for even $i$ be the event that we pay a penalty for months $i$ and
$i+1$ in plan $B$. Then for $i>0$,

$\displaystyle\Pr\left[{A_{i}}\right]$
$\displaystyle=\Pr\left[{X_{i}>\max_{j<i}X_{j}}\right]$
$\displaystyle=\Pr\left[{X_{i}=\max_{j\leq i}X_{i}}\right]$
$\displaystyle=\frac{i!}{(i+1)!}$ $\displaystyle=\frac{1}{i+1}.$ Similarly,
$\displaystyle\Pr\left[{B_{i}}\right]$
$\displaystyle=\Pr\left[{\text{$X_{i}>\max_{j<i}X_{j}$ and
$X_{i+1}>\max_{j<i}$}}\right]$ $\displaystyle=\frac{i!\cdot 2}{(i+2)!}$
$\displaystyle=\frac{2}{(i+2)(i+1)}.$

(In the first case, we count all orderings of the $i+1$ elements $0\dots i$
that make $X_{i}$ largest, and divide by the total number of orderings. In the
second case, we count all the orderings that make $X_{i}$ and $X_{i+1}$ both
larger than all the other values.)

Now let us do some sums.

  1. 1.

For the infinite-lifetime version, Plan A costs

$\displaystyle\sum_{i=1}^{\infty}\frac{1}{i+1},$

which diverges. Plan B costs

$\displaystyle 100\cdot\sum_{i=1}^{\infty}\frac{2}{(2i)(2i-1)}$
$\displaystyle\leq 100\cdot\sum_{i=1}^{\infty}\frac{2}{(2i)^{2}}$
$\displaystyle=100\cdot\sum_{i=1}^{\infty}\frac{1}{2i^{2}}$
$\displaystyle=\frac{100}{2}\cdot\frac{\pi^{2}}{6}.$

which is finite. So Plan B is better for immortals.

  2. 2.

For the finite-lifetime version, over $n$ months, Plan A costs

$\displaystyle\sum_{i=1}^{n}\frac{1}{i}$ $\displaystyle\approx\ln n+\gamma$

Plan B has a $\frac{2}{3\cdot 4}=\frac{1}{6}$ chance of costing $100 after the
first four months, giving an expected cost of at least $16. As long as you
keep both for at least four months, for $n\ll e^{16}\approx 8886110$ months
$\approx 740509$ years, plan A is better.

####  A.3.2 A randomly-indexed list

Consider the following data structure: We store elements in a sorted linked
list, and as each element is inserted, with probability $p$ we also insert it
in a balanced binary search tree data structure with guaranteed $O(\log
n)$-time search and insert operations (say, a red-black tree). We can now
search for an element $x$ by searching for the largest element $y$ in the tree
less than or equal to $x$, then walking along the list starting from $y$ until
we find $x$ (or some value bigger than $x$).

Recall that for a skip list with (small) parameter $p$, the expected number of
pointers stored per element is $1+O(p)$ and the expected cost of a search
operation is $O\left(\frac{1}{p}\log n\right)$.

  1. 1.

What are the corresponding asymptotic values for the expected pointers per
element and the expected cost of a search for this new data structure, as a
function of $p$ and $n$?

  2. 2.

Suppose you are given $n$ in advance. Is it possible to choose $p$ based on
$n$ for the tree-based data structure to get lower expected space overhead
(expressed in terms of pointers per element) than with a skip list, while
still getting $O(\log n)$ expected search time?

##### Solution

  1. 1.

This is actually easier than the analysis for a skip list, because there is no
recursion to deal with.

A balanced binary search tree stores exactly $2$ pointers per element, so with
an expected $pn$ elements in the tree, we get $n+2pn$ pointers total, or
$1+2p)$ pointers per element.

For the search cost, work backwards from the target $x$ to argue that we
traverse an expected $O(1/p)$ edges in the linked list before hitting a tree
node. Searching the tree takes $O(\log n)$ time independent of $p$. This gives
a cost of $O\left(\frac{1}{p}+\log n\right)$.

  2. 2.

Yes. Let $p=\Theta(1/\log n)$. Then we use an expected $1+O(1/\log n)$
pointers per element, while the search cost is $O\left(\frac{1}{1/\log n}+\log
n\right)=O(\log n)$. In contrast, getting $1+O(1/\log n)$ expected space with
a skip list would also require setting $p=\Theta(1/\log n)$, but this would
give an expected search cost $\Theta(\log^{2}n)$.

###  A.4 Assignment 4: due Thursday, 2019-10-31, at 23:00

####  A.4.1 A hash tree

Suppose we attempt to balance a binary search tree by inserting $n$ elements
one at a time, using hashes of the values instead of the values themselves.

Specifically, let $M=\left\\{{1\dots n^{2}}\right\\}$ be the set of possible
hash values; let $U=\left\\{{1\dots u}\right\\}$ be the universe of possible
values, where $u\gg n^{2}$; and let $H$ be a $2$-universal family of hash
functions $h:U\rightarrow M$. After the adversary chooses $n$ distinct values
$x_{1},\dots,x_{n}$, the algorithm chooses a hash function $h\in H$ uniformly
at random, and inserts $x_{1}$ through $x_{n}$ in order into a binary search
tree with no rebalancing, where the key for each value $x_{i}$ is $h(x_{i})$.

In the case of duplicate keys (which shouldn’t happen very often), assume that
if we try to insert $x$ into a subtree with root $r$, and $h(x)=h(r)$, we just
adopt some fixed rule like always inserting $x$ into the right subtree of $r$.

For any $n$ and $u\gg n^{2}$, prove or disprove: for any $2$-universal family
$H$ of hash functions, and any sequence of values $x_{1},\dots,x_{n}$, the
expected depth of a tree constructed by the above process is $O(\log n)$.

##### Solution

Disproof: We will construct a $2$-universal family $H$ such that $h(x)=x$ for
all $h\in H$ whenever $1\leq x\leq m$. We can then insert the values $x_{i}=i$
with corresponding hash values $h(x_{i})=i$ and get a tree of depth exactly
$n$.

Start with a _strongly_ $2$-universal family $H^{\prime}$. For each
$h^{\prime}$ in $H$, construct a corresponding $h$ according to the rule
$h(x)=x$ when $1\leq x\leq m$ and $h(x)=h^{\prime}(x)$ otherwise. We claim
that this gives a $2$-universal family of hash functions.

Recall that $H$ is $2$-universal if, for any $x\neq y$,
$\Pr\left[{h(x)=h(y)}\right]\leq 1/m$, when $h$ is chosen uniformly from $H$.
We consider three cases:

  1. 1.

If $1\leq x\leq m$ and $1\leq y\leq m$, then $h(x)=x\neq y=h(y)$ always.

  2. 2.

If $1\leq x\leq m$ and $m<y$, then
$\Pr\left[{h(y)=h(x)}\right]=\Pr\left[{h^{\prime}(y)=x}\right]=1/m$, since
$h(y)$ is equally likely to be any value by strong $2$-universality. A
symmetric argument works if $m<x$ and $1\leq y\leq m$.

  3. 3.

If $m<x$ and $m<y$, then
$\Pr\left[{h(x)=h(y)}\right]=\Pr\left[{h^{\prime}(x)=h^{\prime}(y)}\right]=1/m$.

In each case we have $\Pr\left[{h(x)=h(y)}\right]\leq 1/m$. So $H$ gives a
$2$-universal hash family that produces trees of depth $n$, much greater than
$O(\log n)$.

####  A.4.2 Randomized robot rendezvous on a ring

Suppose we have a ring of size $nm$, consisting of positions $0,\dots,nm-1$,
with $n$ robots starting at positions $X_{i0}=im$.

At each time step $t$, an adversary chooses one of the $n$ robots $i$, and
this robot moves from position $X_{it}$ to $X_{i,t+1}=(X_{it}\pm 1)\bmod mn$,
moving clockwise or counterclockwise with equal probability. If any other
robot or robots $i^{\prime}$ are at the same position
$X_{i^{\prime}t}=X_{it}$, they also move to the same new position with robot
$i$. Eventually, the robots slowly coalesces until all robots are in the same
position.

The process finishes at the first time $\tau$ where $X_{i\tau}=X_{j\tau}$ for
all $i$ and $j$. What is $\operatorname{E}\left[{\tau}\right]$?

(Assume that the adversary’s choice of robot to move at each time $t$ doesn’t
involve predicting the future. Formally, this choice must be measurable
$\mathcal{F}_{t}$, where $\mathcal{F}_{t}$ is the $\sigma$-algebra generated
by all the positions of the robots at times up to and including $t$.)

##### Solution

We’ll use a variant of the $X_{t}^{2}-t$ martingale for random walks.

For each $i$ and $t$, let $Y_{it}=X_{i+1,t}-X_{it}$ be the size of the gap
between $X_{i+1}$ and $X_{i}$ (wrapping around in the obvious way).

Suppose at some step $t$ the adversary chooses robot $j$ to move. Let $i$ and
$k$ be the smallest and largest robot ids such that $X_{it}=X_{jt}=X_{kt}$
(again wrapping around in the obvious way).

Then $Y_{i-1,t}$ and $Y_{kt}$ are the only gaps that change, and each rises or
drops by 1 with equal probability. So
$\operatorname{E}\left[{Y_{i-1,t+1}^{2}}\;\middle|\;{\mathcal{F}_{t}}\right]=Y_{i-1,t}^{2}+1$
and
$\operatorname{E}\left[{Y_{j,t+1}^{2}}\;\middle|\;{\mathcal{F}_{t}}\right]=Y_{j,t}^{2}+1$.
If we define $Z_{t}=\sum_{i=1}^{n}Y_{it}^{2}-2t$, then
$\left\\{{Z_{t}}\right\\}$ is a martingale with respect to
$\left\\{{\mathcal{F}_{t}}\right\\}$.

For any adversary strategy, starting from any configurations, there is a
sequence of at most $n^{2}m$ coin-flips that causes all robots to coalesce. So
$\operatorname{E}\left[{\tau}\right]\leq n^{2}m2^{n^{2}m}<\infty$. We also
have that $\left\lvert Z_{t+1}-Z_{t}\right\rvert\leq 2$, so we can apply the
finite-expectation/bounded-increments case of Theorem 8.3.1 to show that
$\operatorname{E}\left[{Z_{\tau}}\right]=\operatorname{E}\left[{Z_{0}}\right]=nm^{2}$.
But at time $\tau$, all but one interval $Y_{it}$ is zero, and the remaining
interval has length $mn$. This gives
$\operatorname{E}\left[{Z_{\tau}}\right]=\operatorname{E}\left[{(mn)^{2}-2\tau}\right]$,
giving
$\operatorname{E}\left[{\tau}\right]=\frac{1}{2}\left(n^{2}m^{2}-nm^{2}\right)=\binom{n}{2}m^{2}$.

The nice thing about this argument is that it instantly shows that the
adversary’s strategy doesn’t affect the expected time until all robots
coalesce, but the price is that the argument is somewhat indirect. For
specific adversary strategies, it may be possible to show the coalescence time
more directly. For example, consider an adversary that always picks robot $0$.
Then we can break down the resulting process into a sequence of phases
delimited by collisions between $0$ and robots that have not yet been added to
its entourage. The first such collision happens after robot $0$ hits one of
the two absorbing barriers at $-m$ and $+m$, which occurs in $m^{2}$ steps on
average. At this point, we now have a new random walk with absorbing barriers
at $-m$ and $+2m$ relative to the position of robot $0$ (possibly after
flipping the directions to get the signs right). This second random walk takes
$2m^{2}$ steps on average to hit one of the barriers. Continuing in this way
gives us a sequence of random walks with absorbing barriers at $-m$ and $+km$
for each $k\in\left\\{{1\dots n-1}\right\\}$. The total time is thus
$\sum_{k=1}^{n-1}km^{2}=\frac{(n-1)n}{2}m^{2}=\binom{n}{2}m^{2}$, as shown
above for the general case.

###  A.5 Assignment 5: due Thursday, 2019-11-14, at 23:00

####  A.5.1 Non-exploding computers

Engineers from the Exploding Computer Company have devised a new scheme for
managing the ring of overheating computers from Problem A.1.2. In the new
scheme, we start with an $n$-bit vector $S^{0}=0^{n}$. Each $1$ represents a
computer that is turned on, and each $0$ represents a computer that is turned
off.111The marketing department convinced the company to change the number of
computers in the ring from $3n$ to $n$ in response to consumer complaints. If
the engineers’ scheme works, the next meeting of the marketing department will
consider choosing a new name for the company.

Call a state $S$ permissible if there is no $j$ such that
$S^{t+1}_{j}=S^{t+1}_{j+1}=S^{t+1}_{j+2}=1$, where the indices wrap around mod
$n$.

At each step, some position $i$ is selected uniformly at random. If
$S^{t}_{i}=1$, $S^{t+1}_{i}$ is set to $0$ with probability $p$. If
$S^{t}_{i}=0$, $S^{t+1}_{i}$ is set to $1$ if this creates a permissible
configuration, and stays $0$ otherwise. For any positions $j\neq i$,
$S^{t+1}_{j}=S^{t}_{j}$.

  1. 1.

Show that when $0<p<1$, the sequence of values $S^{t}$ forms a Markov chain
with states consisting of all permissible sets, and that this chain has a
unique stationary distribution $\pi$ in which $\pi(S)=\pi(T)$ whenever $\lvert
S\rvert=\lvert T\rvert$, where $\lvert S\rvert$ is the number of $1$ bits in
$S$.

  2. 2.

Let $\tau$ be the first time at which $\lvert S^{\tau}\rvert\geq n/2$. Show
that for any $n$, there is a choice of $p\geq 0$ such that
$\operatorname{E}\left[{\tau}\right]=O(n\log n)$.

##### Solution

  1. 1.

First observe that the update rule for generating $S^{t+1}$ depends only on
the state $S^{t}$; this gives that $\left\\{{S^{t}}\right\\}$ is a Markov
chain. It is irreducible, because there is always a nonzero-probability path
from any permissible configuration $S$ to any permissible configuration $T$
that goes through the empty configuration $0^{n}$. It is aperiodic, because
for any nonempty configuration $S^{t}$, there is a nonzero probability that
$S^{t+1}=S^{t}$, since we can pick a position $i$ with $S^{t}_{i}=1$ and then
choose not set $S^{t+1}_{i}$ to $0$. So a unique stationary distribution $\pi$
exists.

We can show that $\pi(S)$ depends only on $\lvert S\rvert$ by using the fact
that the Markov chain is reversible. Let $S$ and $T$ be reachable states that
differ only in position $i$. Suppose that $S^{t}_{i}=0$ and $T^{t}_{i}=1$.
Then $p_{ST}=1/n$ and $p_{TS}=p/n$. Let $c=\sum_{S}p^{-\lvert S\rvert}$, where
$S$ ranges over all admissible states, and let $\pi_{S}=p^{-\lvert
S\rvert}/c$. Pick some $S$ and $T$ as above and let $k=\lvert S\rvert$.

$\displaystyle\pi_{S}p_{ST}$ $\displaystyle=\frac{p^{-k}}{c}\frac{1}{n}$
$\displaystyle=\frac{p^{-k-1}}{c}\frac{p}{n}$ $\displaystyle=\pi_{T}p_{TS}.$

So this particular choice of $\pi$ satisfies the detailed balance equations
and is the stationary distribution of the chain. Since $\pi(S)$ only depends
on $\lvert S\rvert$, it is immediate that $\pi(S)=\pi(T)$ when $\lvert
S\rvert=\lvert T\rvert$.

  2. 2.

For this part, we’ll set $p=0$, then walk directly up to a configuration with
$\lvert S^{t}\rvert\geq n/2$ in $O(n\log n)$ steps on average. Setting $p=0$
means that the chain is no longer irreducible, but we won’t care about this
since we are not worried about convergence.

Let $S$ be a permissible configuration with $\lvert S\rvert=k$. We want to get
a lower bound on the number of positions $i$ such that $S[i/1]$ is also
permissible. There $n-k$ zeroes in $S$; each such $0$ can be switched to $1$
unless it would create three ones in a row. We will show that at most $k$ of
the $n-k$ zeroes cannot be switched, by constructing an injection $f$ from the
set of unswitchable $0$ positions to the set of $1$ positions.

Let $i$ be a position such that $S_{i}=0$ but $S[i/1]$ is not permissible.
Then one of the following cases holds:

    1. (a)

$S_{i-2}=S_{i-1}=1$. Let $f(i)=i-1$.

    2. (b)

$S_{i-1}=S_{i+1}=1$. Let $f(i)=i-1$.

    3. (c)

$S_{i+1}=S_{i+2}=1$. Let $f(i)=i+1$.

To show that this is an injection, observe that the only way for $f(i)=f(j)$
to occur is if $f(i)=i+1$ and $f(j)=j-1$ (or vice versa). But if $f(i)=i+1$,
then $S_{j}=S_{i+2}=1$, and $S_{j}$ is not an unswitchable zero.

So out of $n-k$ zeroes we have at most $k$ unswitchable zeroes, giving at
least $n-2k$ switchable zeroes. The expected waiting time to hit one of these
at least $n-2k$ switchable zeroes is at most $\frac{n}{n-2k}$, giving a total
expected waiting time of at most
$\sum_{k=0}^{\lfloor(n-1)/2\rfloor}\frac{n}{n-2k}\leq nH_{n}=O(n\log n)$.

I suspect the correct expected waiting time is in fact $O(n)$, because (a) the
pattern $11011$ includes at least one $1$ that is not the image of any
unswitchable zero; (b) after, say, $n/8$ steps it is likely (via linearity of
expectation and McDiarmid’s inequality) that there are a linear number $\ell$
of such patterns in $S$; so that (c) even as $k$ gets close to $n/2$, the
number of unswitchable zeros is at least $n-2k+\ell=\Theta(n)$, giving
constant expected waiting times to find the next switchable zero. But actually
proving (b) given all the dependencies flying around looks at least mildly
painful, so we may want to just hope that an $O(n\log n)$ bound is good
enough.

####  A.5.2 A wordy walk

Consider the following random walk on strings over some alphabet $\Sigma$. At
each step:

  1. 1.

With probability $p$, if $\lvert X^{t}\rvert>1$, delete a character from a
position chosen uniformly at random from all positions in $X^{t}$. If $\lvert
X^{t}\rvert=1$, do nothing.

  2. 2.

With probability $q$, insert a new character chosen uniformly at random from
$\Sigma$ into $X^{t}$. The new character will be inserted after the first $i$
characters in $X^{t}$, where $i$ is chosen uniformly at random from
$\left\\{{0\dots\lvert X^{t}\rvert}\right\\}$.

  3. 3.

With probability $r$, choose one of the character positions in $X^{t}$
uniformly at random and replace the character in that position with a
character chosen uniformly at random from $\Sigma$.

For example, here is the result of running the above process for a few steps
with $\Sigma$ the lowercase Latin alphabet, $p=1/2$, $q=1/4$, and $r=1/4$,
starting from the string markov: markov markzv marzv carzv caurzv cauzv cauav
cauav cavav avav.

Assume $p+q+r=1$, $p>q>0$, and $r>0$.

Suppose that we start with $\lvert X^{0}\rvert=n$. Show that for any constants
$p,q,r$ satisfying the above constraints, and any constant $\epsilon>0$, there
is a time $t=O(n)$ such that $d_{TV}(X^{t},\pi)\leq\epsilon$, where $\pi$ is a
stationary distribution of this process.

##### Solution

We can simplify things a bit by tracking $X^{t}=\lvert S^{t}\rvert$. Since
changes in the length of $S$ don’t depend on the characters in $S$,
$\left\\{{X^{t}}\right\\}$ is also a Markov chain, with transition
probabilities

$\displaystyle p_{ij}$ $\displaystyle=\begin{cases}p&j=i-1\\\ q&j=i+1\\\
r&\text{otherwise}\end{cases}$

Applying the detailed balance equations gives a stationary distribution $\rho$
for $X^{t}$ of $\rho_{i}=(q/p)^{i-1}/(1-q/p)$. By symmetry, this gives a
stationary distribution $\pi_{S}=\frac{(q/p)^{\lvert
S\rvert-1}\lvert\Sigma\rvert^{-\lvert S\rvert}}{1-q/p}$. For $X$ with
distribution $\rho$, we have $\operatorname{E}\left[{X}\right]$ finite when
$p>q$ since
$\operatorname{E}\left[{X}\right]=\frac{1}{1-q/p}\sum_{n=1}^{\infty}n(q/p)^{n-1}$
converges.

We’ll show convergence for $S^{t}$ starting from a particular $S^{0}$ using a
coupling with a stationary copy of the chain $\left\\{{T^{t}}\right\\}$.

Our strategy will go as follows:

  1. 1.

Let $m=\lvert T^{0}\rvert$. We will argue that a coupling that applies the
same operation (delete, insert, change) to both copies of the chain reaches a
configuration where $\lvert S^{t}\rvert=\lvert T^{t}\rvert=1$ in $O\max(n,m)$
expected steps.

  2. 2.

From a state with $\lvert S^{t}\rvert=\lvert T^{t}\rvert=1$, with probability
$r>0$, both chains switch to a new character. Make this the same character and
get $S^{t}=Y^{t}$.

  3. 3.

If this doesn’t work, repeat the argument from the start. Note that we now
have $\lvert S^{t}\rvert=\lvert T^{t}\rvert\leq 2$, so after $O(1)$ expected
steps we are back at $\lvert S^{t}\rvert=\lvert T^{t}\rvert=1$ again. The
waiting time for convergence is now geometric and has expectation $O(1)$.

Let us now justify the claim that the waiting time to reach $\lvert
S^{t}\rvert=\lvert T^{t}\rvert=1$ is $O(\max(n,m))$. This is just the usual
argument for a biased random walk with one absorbing barrier. Let
$Z^{t}=\max\left(\lvert S^{t}\rvert,\lvert Y^{t}\rvert\right)$. Let $\tau$ be
the stopping time at which $Z^{t}$ is first equal to $1$. Observe that for
$t<\tau$, $\operatorname{E}\left[{Z^{t+1}}\right]{Z^{0}\dots
Z^{t}}=Z^{t}+q-p$, so $Q^{t}=Z^{t}+(p-q)t$ is a martingale with bounded
increments, and we can apply OST to get that
$\operatorname{E}\left[{Q_{\tau}}\right]=1-(p-q)\tau=\operatorname{E}\left[{Q_{0}}\right]=\max{n,m}$.
This gives $\operatorname{E}\left[{\tau}\right]=\frac{\max{n,m}-1}{p-q}$.

We now have a coupling that gives an expected d coalescence time of
$O(\max(n,m))$. If $\max(n,m)=n$, we are done. But it could be that
$\max(n,m)=m$. Conditioning on $\lvert T^{t}\rvert>n$, we are truncating the
distribution of $\lvert T^{t}\rvert$ to be a geometric distribution starting
at $n+1$; this has expected value $n+O(1)$, giving
$\operatorname{E}\left[{\max(n,m)}\right]=n+O(1)$ in either case. So the
coalescence time is $O(n+O(1))=O(n)$.

Since $\epsilon$ is a constant, after applying the Coupling Lemma and Markov’s
inequality, the $O$ eats it.

###  A.6 Assignment 6: due Monday, 2019-12-09, at 23:00

####  A.6.1 Randomized colorings

Suppose we want to use a constant number $k$ of colors to color the vertices
of a graph $G$ with $n$ vertices and $m$ edges so that we minimize the number
of monochromatic edges. A particularly simple approach is to color the
vertices independently and uniformly at random. This gives $m/k$ monochromatic
edges on average. But we’d like to derandomize the algorithm to get at most
$m/k$ monochromatic edges always.

There are two standard ways to do this:

  1. 1.

Replace the independent random colors with pairwise independent random colors
and then consider all possible random choices. Show that we can do this by
generating $n$ pairwise-independent colors from a small number of random
values, and determine the asymptotic time complexity, as a function of $n$,
$m$, and $k$, of generating and testing all the resulting colorings to find
the best one.

  2. 2.

Apply the method of conditional probabilities and assign colors one at a time
to minimize the expected number of monochromatic edges conditioned on the
assignment so far. Show that we can do so in this case, and compute the
asymptotic time complexity as a function of $n$, $m$, and $k$ of the resulting
deterministic algorithm.

##### Solution

  1. 1.

The obvious way to generate $n$ pairwise-independent random values in
$\left\\{{0,\dots,k-1}\right\\}$ is to apply the subset-sum construction
described in §5.1.2.1. Let $\ell=\lceil\lg(n+1)\rceil$, assign a distinct
nonempty subset $S_{v}$ of $\left\\{{1,\dots,\ell}\right\\}$ to each vertex
$v$, and let $X_{v}=\sum_{i\in C_{v}}r_{i}$ where $r_{1},\dots,r_{\ell}$ are
independent random values chosen uniformly from $\mathbb{Z}_{k}$. Then the
$X_{v}$ are pairwise independent, giving a probability of $1/k$ that any
particular edge is monochromatic. Since this gives $m/k$ monochromatic edges
on average, enumerating all choices of $r_{1},\dots,r_{\ell}$ will find a
particular coloring that gets at least $m/k$ monochromatic edges.

There are $k^{\ell}=k^{\lceil\lg(n+1)\rceil}$ possible choices. This is
bounded by $k^{2+\lg n}=O\left(k^{2}n^{\lg k}\right)=O\left(n^{\lg k}\right)$,
which is polynomial in $n$.

Generating each coloring takes $O(n\log n)$ time, and testing the edges takes
$O(m)$ time, for a total time of $O(n^{\lg k}(m+n\log n))$.

With some data structure tinkering we can reduce the complexity a bit. We can
enumerate all of $r_{1},\dots,r_{k}$ with an amortized $O(1)$ values changing
at each iteration. This still requires changing about half the colors, but we
can update each dynamically by subtracting off the old value of $r_{i}$ and
adding the new one, reducing the amortized cost per iteration from $O(n\log
n)$ to $O(n)$. We still end up checking most of the edges, so the cost will
now be $O\left(n^{\lg k}(m+n)\right)$. I don’t see an obvious way to do
better.

  2. 2.

For this part we let $X_{1},\dots,X_{n}$ be the colors assigned to the
vertices (ordering them arbitrarily) and let $f(X_{1},\dots,X_{n})$ be the
number of monochromatic edges given a particular coloring. Having fixed
$X_{1},\dots,X_{i}$, we want to choose $X_{i+1}$ to minimized
$\operatorname{E}\left[{f}\;\middle|\;{X_{1},\dots,X_{i+1}}\right]$.

Observe that $f(X_{1},\dots,X_{n})=\sum_{uv\in E}[X_{u}=X_{v}]$, so
$\operatorname{E}\left[{f|X_{1},\dots,X_{i}}\right]=\sum_{uv\in
E}\Pr\left[{X_{u}=X_{v}}\right]$. For each $uv$, if
$i+1\not\in\left\\{{u,v}\right\\}$, then $[X_{u}=X_{v}]$ is independent of
$X_{i+1}$, giving
$\Pr\left[{X_{u}=X_{v}}\;\middle|\;{X_{1},\dots,X_{i+1}}\right]=\Pr\left[{X_{u}=X_{v}}\;\middle|\;{X_{1},\dots,X_{i+1}}\right]$.
So we only care about the cases where $i+1\in\left\\{{u,v}\right\\}$. Assume
without loss of generality that $i+1=u$. If $v\leq i$, then $[X_{u}=X_{v}]$ is
either $1$ or $0$ depending on whether we set $X_{u}=X_{v}$ or not. If
$v>i+1$, then $X_{v}$ is independent of $X_{i+1}$, so
$\Pr\left[{X_{u}=X_{v}}\;\middle|\;{X_{1},\dots,X_{i+1}}\right]=\Pr\left[{X_{u}=X_{v}}\;\middle|\;{X_{1},\dots,X_{i}}\right]$.

This means that to minimize
$\operatorname{E}\left[{f}\;\middle|\;{X_{1},\dots,X_{i+1}}\right]$, the only
edges we need to consider are those edges $X_{uv}$ where one endpoint is $i+1$
and the other endpoint is in $\left\\{{1,\dots,i}\right\\}$. Minimizing the
conditional expectation of $f$ turns into the obvious greedy algorithm of
picking a color for $v_{i+1}$ that is least represented among its neighbors,
which we can do in $O\left(1+d(v_{i+1})\right)$ time. Adding up over all
vertices $v$ gives $O\left(\sum_{v\in V}(1+d(v))\right)=O(n+m)$ time.

####  A.6.2 No long paths

Given a directed graph $G$ with $n$ vertices and maximum out-degree $d$, we
would like to find an induced subgraph $G^{\prime}$ with at least
$(1-\delta)n/(d+1)$ vertices, such that $G^{\prime}$ has no simple paths222For
the purposes of this problem, a simple path of length $\ell$ is a directed
path with $\ell$ edges and no repeated vertices. of length $\lceil 2d\ln
n\rceil$ or greater.

Find an algorithm that does this in polynomial expected time for any constant
$d>0$ and $\delta>0$, and sufficiently large $n$.

##### Solution

We’ll put each vertex $v$ to $G^{\prime}$ with independent probability
$p=1/(d+1)$. We now have two possible bad outcomes:

  1. 1.

We may get a path of length $\lceil 2d\ln n\rceil$ in $G^{\prime}$.

  2. 2.

We may get fewer than $(1-\delta)n/(d+1)$ vertices in $G^{\prime}$.

We’ll start by showing that the sum of the probabilities of these bad outcomes
is not too big.

Let $\ell=\lceil 2d\ln n\rceil$. Observe that we can describe a path of length
$\ell$ in $G$ by specifying its starting vertex ($n$ choices) and a sequence
of $\ell$ edges each leaving the last vertex added so far ($d$ choices each).
This gives at most $nd^{\ell}$ paths of length $\ell$ in $G$. Each such path
appears in $G^{\prime}$ with probability exactly $p^{\ell+1}$. Using the usual
probabilistic-method argument, we get

$\displaystyle\Pr\left[{\text{$G^{\prime}$ includes at least one path of
length $\ell$}}\right]$ $\displaystyle\leq\operatorname{E}\left[{\text{number
of paths of length $\ell$ in $G^{\prime}$}}\right]$ $\displaystyle\leq
nd^{\ell}p^{\ell+1}$ $\displaystyle=np(pd)^{\ell}.$
$\displaystyle=\frac{1}{d+1}n\left(\frac{d}{d+1}\right)^{\ell}$
$\displaystyle=\frac{1}{d+1}n\left(1-\frac{1}{d+1}\right)^{\ell}$
$\displaystyle=\frac{1}{d+1}n\left(1-\frac{1}{d+1}\right)^{\lceil 2d\ln
n\rceil}$ $\displaystyle\leq\frac{1}{d+1}n\left(1-\frac{1}{d+1}\right)^{2d\ln
n}$ $\displaystyle\leq\frac{1}{d+1}ne^{-\ln n}$ $\displaystyle=\frac{1}{d+1}.$
$\displaystyle\leq\frac{1}{2}.$

For the second-to-last inequality, we use the inequality
$\left(1-\frac{1}{d+1}\right)^{2d}\leq e^{-1}$ for $d\geq 1$. This is easiest
to demonstrate numerically, but if we had to prove it we could argue that it
holds when $d=1$ (since $1/4<1/e$) and that $(1-\frac{1}{d+1})^{2d}$ is a
decreasing function of $d$.

For getting too few vertices, use Chernoff bounds. Let $X$ be the number of
vertices in $G^{\prime}$. Let
$\mu=\operatorname{E}\left[{X}\right]=\frac{n}{d+1}$.

$\displaystyle\Pr\left[{X<(1-\delta)n/(d+1)}\right]$
$\displaystyle=\Pr\left[{X<(1-\delta)\mu}\right]$ $\displaystyle\leq
e^{-\mu\delta^{2}/2}$ $\displaystyle=e^{-n\delta^{2}/(2(d+1))}$
$\displaystyle<1/4,$

for any fixed $d>0$, $\delta>0$, and sufficiently large $n$.

Adding these error probabilities together gives a total probability of failure
of at most $3/4$. We can select the vertices in $G^{\prime}$ in time linear in
$n$. So if we can detect failure in polynomial time and try again, we only
have to run at most $4$ poly-time attempts on average until we win, giving
polynomial expected cost.

So now let us detect failure. There are at most $nd^{\ell}$ paths of length
$\ell$ in $G$. We can enumerate all of them and check if each is in
$G^{\prime}$ in time

$\displaystyle O\left(nd^{\ell}\ell\right)$ $\displaystyle=O\left(n\ell
d^{2d\ln n+1}\right)$ $\displaystyle=O\left(n\ell de^{2d\ln n\ln d}\right)$
$\displaystyle=O\left(n^{2d\ln d+1}d^{2}\log n\right),$

which is polynomial in $n$ for fixed $d$.

###  A.7 Final exam

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

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

####  A.7.1 A uniform ring

Suppose we have a ring of $n$ nodes, each of which holds a bit. At each step,
we pick a node uniformly at random and have it copy the bit of its left
neighbor. For example, if we start in state $010$, then picking the rightmost
node will send us to state $011$, and if we then pick the leftmost node we
will reach state $111$. From this last state no further changes are possible.

Suppose $n$ is even and we start with a state where positions $1$ through
$n/2$ are all $0$ and positions $n/2+1$ through $n$ are all $1$. What is the
expected number of steps, as an asymptotic function of $n$, to reach a state
where all bits are the same?

##### Solution

First observe that any transition preserves the property that our state looks
like a string of the form $0^{k}1^{n-k}$, where both the zeroes and ones all
appear in consecutive positions around the ring.

Let $X_{t}$ be the number of zeroes after $t$ steps. We have $X_{0}=n/2$, and
our possible transitions when $0<X_{t}<n$ are:

  1. 1.

With probability $1/n$, we choose the leftmost zero and replace it with a one.
This makes $X_{t+1}=X_{t}-1$.

  2. 2.

With probability $1/n$, we choose the leftmost one and replace it with a zero.
This makes $X_{t+1}=X_{t}+1$.

  3. 3.

With the remaining probability $1-2/n$, we choose some node whose bit is equal
to that of its left neighbor. This makes $X_{t+1}=X_{t}$.

When $X_{t}=0$ or $X_{t}=n$, we have converged: no further changes are
possible.

Looking at the transitions for $X_{t}$, we see that it is doing a very lazy
random walk with absorbing barriers at $0$ and $n$. If we remember that a non-
lazy random walk converges in $O(n^{2})$ steps on average, we can argue that
the lazy version converges in $O(n^{3})$ steps on average, because the
expected waiting time between changes in $X_{t}$ is $n/2=O(n)$, and we can
multiply this by the number of changes because of Wald’s equation.

If we want to be very formal about this, we can also calculate the exact
expected convergence time using the Optional Stopping Theorem. Let’s guess
that $Y_{t}=X_{t}^{2}-ct$ is a martingale for some coefficient $c$. To find
$c$, observe that we need

$\displaystyle\operatorname{E}\left[{\left(X_{t+1}^{2}-c(t+1)\right)-\left(X_{t}^{2}-ct\right)}\;\middle|\;{X_{t}}\right]$
$\displaystyle=\operatorname{E}\left[{X_{t+1}^{2}-X_{t}^{2}-c}\;\middle|\;{X_{t}}\right]$
$\displaystyle=\frac{1}{n}(2X_{t}+1)+\frac{1}{n}(-2X_{t}+1)-c$
$\displaystyle=\frac{2}{n}-c$ $\displaystyle=0.$

So $\left\\{{Y_{t}}\right\\}$ is a martingale when $c=\frac{2}{n}$.

Let $\tau$ be the stopping time at which $X_{\tau}$ first equals $0$ or $n$.
The usual argument shows that $\operatorname{E}\left[{\tau}\right]$ is finite,
and $\left\\{{Y_{t}}\right\\}$ has bounded increments because $Y_{t}$ never
changes by more than $2X_{t}+1\leq 2n+1$. So OST applies and
$\operatorname{E}\left[{Y_{\tau}}\right]=\operatorname{E}\left[{Y_{0}}\right]=(n/2)^{2}$.
But we can expand

$\displaystyle\operatorname{E}\left[{Y_{\tau}}\right]$
$\displaystyle=\frac{1}{2}\cdot 0+\frac{1}{2}\cdot
n^{2}-\frac{2}{n}\cdot\operatorname{E}\left[{\tau}\right]$
$\displaystyle=\frac{n^{2}}{2}-\frac{2}{n}\cdot\operatorname{E}\left[{\tau}\right].$

This gives $\frac{n^{2}}{4}=\frac{n^{2}}{2}-\frac{2}{n}\cdot\tau$. Solving for
$\operatorname{E}\left[{\tau}\right]$ gives
$\operatorname{E}\left[{\tau}\right]=\frac{n^{3}}{8}=O(n^{3})$.

####  A.7.2 Forbidden runs

Given a sequence of coin-flips, a run is a maximal subsequence of either all
heads or all tails. The length of a run is the number of flips in the run. For
example, the sequence HHHTTHTHH has five runs: a run HHH of length $3$, a run
TT of length $2$, a run H of length $1$, a run T of length $1$, and a run HH
of length $2$.

Suppose we are attempting to transmit a sequence of $n$ fair, independent
coin-flips across a communication channel that uses a run of length $k$ to
signal an emergency condition. To avoid false alarms, we must encode our
sequence to include no runs of length $k$. We do this by encoding any run of
length $\ell\geq k$ as a run of length $\ell+1$ of the same value. For
example, when $k=2$, we would encode the previous example HHHTTHTHH as
HHHHTTTHTHHH.

As a function of $n$ and $k$, what is the expected length of the encoded
sequence?

##### Solution

Let $i$ range from $1$ to $n$, and let $X_{i}$ be the $i$-th coin-flip in the
sequence. Let $R_{i}$ be the indicator variable for the event that there is a
run of length $k$ or more starting at position $i$. Then the expected number
of runs of length $k$ or more is given by
$\sum_{i=1}^{n}\operatorname{E}\left[{R_{i}}\right]$ by linearity of
expectation, and because each such run adds one to the length of the encoded
sequence, the expected encoded length is
$n+\sum_{i=1}^{n}\operatorname{E}\left[{R_{i}}\right]$.

To compute $\operatorname{E}\left[{R_{i}}\right]$, we consider three cases:

  1. 1.

If $i=1$, then $R_{i}=1$ when $X_{1},\dots,X_{k}$ are all H or all T. This
gives $\operatorname{E}\left[{R_{i}}\right]=2\cdot 2^{-k}=2^{-k+1}$.

  2. 2.

If $1<i\leq n-k+1$, then $R_{i}=1$ when $X_{1},\dots,X_{k}$ are all H or all
T, and $X_{i-1}$ is not this common value (because otherwise the run starts
earlier). This gives $\operatorname{E}\left[{R_{i}}\right]=2\cdot
2^{-k-1}=2^{-k}$.

  3. 3.

If $i>n-k+1$, then $R_{i}=0$, because there aren’t enough coins left to get a
run of length $k$.

Summing over all the cases gives

$\displaystyle\sum_{i=1}^{n}\operatorname{E}\left[{R_{i}}\right]$
$\displaystyle=2^{-k+1}+\sum_{i=2}^{n-k+1}2^{-k}$ $\displaystyle=2\cdot
2^{-k}+(n-k)\cdot 2^{-k}$ $\displaystyle=(n-k+2)\cdot 2^{-k}.$

For the expected encoded sequence length, we must add back $n$ to get
$n+(n-k+2)\cdot 2^{-k}$.

####  A.7.3 A derandomized balancing scheme

Suppose we construct an $n\times n$ matrix $A$ where the elements $A_{ij}$ are
$n^{2}$ independent fair $\pm 1$ random variables. Then Hoeffding’s inequality
tells us that

$\Pr\left[{\left\lvert\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}\right\rvert\geq
t}\right]\leq 2\exp\left(-\frac{t^{2}}{2n^{2}}\right).$

Unfortunately this requires using $n^{2}$ random bits.

As an alternative, suppose we use $2n$ random bits to generate two sequences
$X$ and $Y$ of $n$ independent fair $\pm 1$ random variables, and define
$B_{ij}=X_{i}Y_{j}$.

Show that

$\displaystyle\Pr\left[{\left\lvert\sum_{i=1}^{n}\sum_{j=1}^{n}B_{ij}\right\rvert\geq
t}\right]\leq 4\exp\left(-\frac{t}{2n}\right).$

##### Solution

Start by factoring

$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}B_{ij}$
$\displaystyle=\sum_{i=1}^{n}\sum_{j=1}^{n}X_{i}Y_{j}$
$\displaystyle=\left(\sum_{i=1}^{n}X_{i}\right)\left(\sum_{j=1}^{n}Y_{j}\right).$

Each factor is a sum of $n$ independent $\pm 1$ random variables with
expectation $0$, so Hoeffding’s inequality applies, giving

$\displaystyle\Pr\left[{\left\lvert\sum_{i=1}^{n}X_{i}\right\rvert\geq
s}\right]$ $\displaystyle\leq 2\exp\left(-\frac{s^{2}}{2n}\right)$ and
$\displaystyle\Pr\left[{\left\lvert\sum_{j=1}^{n}Y_{j}\right\rvert\geq
s}\right]$ $\displaystyle\leq 2\exp\left(-\frac{s^{2}}{2n}\right).$

If neither of these events holds, then
$\left\lvert\sum_{i=1}^{n}\sum_{j=1}^{n}B_{ij}\right\rvert=\left\lvert\sum_{i=1}^{n}X_{i}\right\rvert\cdot\left\lvert\sum_{j=1}^{n}Y_{j}\right\rvert<s^{2}$.

So by the union bound,

$\displaystyle\Pr\left[{\left\lvert\sum_{i=1}^{n}\sum_{j=1}^{n}B_{ij}\right\rvert\geq
s^{2}}\right]$
$\displaystyle\leq\Pr\left[{\left\lvert\sum_{i=1}^{n}X_{i}\right\rvert\geq
s}\right]+\Pr\left[{\left\lvert\sum_{j=1}^{n}Y_{j}\right\rvert\geq s}\right]$
$\displaystyle\leq 4\exp\left(-\frac{s^{2}}{2n}\right).$

Now substitute $t$ for $s^{2}$.

##  Appendix B Sample assignments from Fall 2016

###  B.1 Assignment 1: due Sunday, 2016-09-18, at 17: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.)

####  B.1.1 Bubble sort

Algorithm B.1 implements one pass of the (generally pretty slow) bubble sort
algorithm. This involves comparing each array location with its successor, and
swapping the elements if they are out of order. The full bubble sort algorithm
repeats this loop until the array is sorted, but here we just do it once.

1procedure  _$\textnormal{{{}BubbleSortOnePass}}(A,n)$_

2 for  _$i\leftarrow 1$ to $n-1$_ do

3 if  _$A[i] >A[i+1]$_ then

4 Swap $A[i]$ and $A[i+1]$

5

6

7

Algorithm B.1 One pass of bubble sort

Suppose that $A$ starts out as a uniform random permutation of distinct
elements. As a function of $n$, what is the exact expected number of swaps
performed by Algorithm B.1?

##### Solution

The answer is $n-H_{n}$, where $H_{n}=\sum_{i=1}^{n}\frac{1}{i}$ is the $n$-th
harmonic number. There are a couple of ways to prove this. Below, we let
$A_{i}$ represent the original contents of $A[i]$, before doing any swaps. In
each case, we will use the fact that after $i$ iterations of the loop, $A[i]$
contains the largest of $A_{i},\dots,A_{i}$; this is easily proved by
induction on $i$.

  * •

Let $X_{ij}$ be the indicator variable for the event that $A_{i}$ is
eventually swapped with $A_{j}$. For this to occur, $A_{i}$ must be bigger
than $A_{j}$, and must be present in $A[j-1]$ after $j-1$ passes through the
loop. This happens if and only if $A_{i}$ is the largest value in
$A_{1},\dots,A_{j}$. Because these values are drawn from a uniform random
permutation, by symmetry $A_{i}$ is largest with probability exactly $1/j$. So
$\operatorname{E}\left[{X_{ij}}\right]=1/j$.

Now sum $X_{ij}$ over all pairs $i<j$. It is easiest to do this by summing
over $j$ first:

$\displaystyle\operatorname{E}\left[{\sum_{i<j}X_{ij}}\right]$
$\displaystyle=\sum_{i<j}\operatorname{E}\left[{X_{ij}}\right]$
$\displaystyle=\sum_{j=2}^{n}\sum_{i=1}^{j-1}\operatorname{E}\left[{X_{ij}}\right]$
$\displaystyle=\sum_{j=2}^{n}\sum_{i=1}^{j-1}\frac{1}{j}$
$\displaystyle=\sum_{j=2}^{n}\frac{j-1}{j}$
$\displaystyle=\sum_{j=1}^{n}\frac{j-1}{j}$
$\displaystyle=\sum_{j=1}^{n}(1-\frac{1}{j})$
$\displaystyle=n-\sum_{j=1}^{n}\frac{1}{j}$ $\displaystyle=n-H_{n}.$

  * •

Alternatively, let’s count how many values are _not_ swapped from $A[i]$ to
$A[i-1]$. We can then subtract from $n$ to get the number that are.

Let $Y_{i}$ be the indicator variable for the event that $A_{i}$ is not
swapped into $A[i-1]$. This occurs if, when testing $A[i-1]$ against $A[i]$,
$A[i]$ is larger. Since we know that at this point $A[i-1]$ is the largest
value among $A_{1},\dots,A_{i-1}$, $Y_{i}=1$ if and only if $A_{i}$ is greater
than all of $A_{1},\dots,A_{i-1}$, or equivalently if $A_{i}$ is the largest
value in $A_{1},\dots,A_{i}$. Again by symmetry we have
$\operatorname{E}\left[{Y_{i}}\right]=\frac{1}{i}$, and summing over all $i$
gives an expected $H_{n}$ values that are not swapped down. So there are
$n-H_{n}$ values on average that are swapped down, which also gives the
expected number of swaps.

####  B.1.2 Finding seats

A huge lecture class with $n$ students meets in a room with $m\geq n$ seats.
Because the room is dark, loud, and confusing, the students adopt the
following seat-finding algorithm:

  1. 1.

The students enter the room one at a time. No student enters until the
previous student has found a seat.

  2. 2.

To find a seat, a student chooses one of the $m$ seats uniformly at random. If
the seat is occupied, the student again picks a seat uniformly at random,
continuing until they either find a seat or have made $k$ attempts that led
them to an occupied seat.

  3. 3.

If a student fails to find a seat in $k$ attempts, they contact an
Undergraduate Seating Assistant, who leads them to an unoccupied seat.

Give an asymptotic (big-$\Theta$) expression for the number of students who
are helped by Undergraduate Seating Assistants, as a function of $n$, $m$, and
$k$, where $k$ is a constant independent of $n$ and $m$. As with any
asymptotic formula, this expression should work for large $n$ and $m$; and
should be as simple as possible.111An earlier version of this problem allowed
$k$ to grow with $n$, which causes some trouble with the asymptotics.

##### Solution

Define the $i$-th student to be the student who takes their seat after $i$
students have already sat (note that we are counting from zero here, which
makes things a little easier). Let $X_{i}$ be the indicator variable for the
even that the $i$-th student does not find a seat on their own and needs help
from a USA. Each attempt to find a seat fails with probability $i/m$. Since
each attempt is independent of the others, the probability that all $k$
attempts fail is $(i/m)^{k}$.

The number of students who need help is $\sum_{i=0}^{n-1}X_{i}$, so the
expected number is

$\displaystyle\operatorname{E}\left[{\sum_{i=0}^{n-1}X_{i}}\right]$
$\displaystyle=\sum_{i=0}^{n-1}\operatorname{E}\left[{X_{i}}\right]$
$\displaystyle=\sum_{i=0}^{n-1}(i/m)^{k}$
$\displaystyle=m^{-k}\sum_{i=0}^{n-1}i^{k}.$

Unfortunately there is no simple expression for $\sum i^{k}$ that works for
all $k$. However, we can approximate it from above and below using integrals.
From below, we have

$\displaystyle\sum_{i=0}^{n-1}i^{k}$ $\displaystyle=\sum_{i=1}^{n-1}i^{k}$
$\displaystyle\geq\int_{0}^{n-1}x^{k}dx$
$\displaystyle=\left[\frac{1}{k+1}x^{k+1}\right]_{0}^{n-1}$
$\displaystyle=\frac{1}{k+1}(n-1)^{k+1}$
$\displaystyle=\Omega\left(\frac{1}{k+1}n^{k+1}\right).$

From above, an almost-identical computation gives

$\displaystyle\sum_{i=0}^{n-1}i^{k}$ $\displaystyle\leq\int_{0}^{n}x^{k}dx$
$\displaystyle=\left[\frac{1}{k+1}x^{k+1}\right]_{0}^{n}$
$\displaystyle=frac{1}{k+1}n^{(}k+1)$ $\displaystyle=O(\frac{1}{k+1}n^{k+1}).$

Combining the two cases gives that the sum is
$\Theta\left(\frac{1}{k+1}n^{k+1}\right)$. We must also include $m^{-k}$,
giving the full answer

$\Theta\left(\frac{1}{k+1}n^{k+1}m^{-k}\right).$

I like writing this as $\Theta\left(n\frac{(n/m)^{k}}{k+1}\right)$ to
emphasize that the cost per student is
$\Theta\left(\frac{(n/m)^{k}}{k+1}\right)$, but there are a lot of different
ways to write the same thing. Note that since we are dealing with asymptotics,
we could also replace the $\frac{1}{k+1}$ with just $\frac{1}{k}$ and still be
correct, but that seems less informative somehow.

###  B.2 Assignment 2: due Thursday, 2016-09-29, at 23:00

####  B.2.1 Technical analysis

It is well known that many human endeavors—including sports reporting,
financial analysis, and Dungeons and Dragons—involve building narratives on
top of the output of a weighted random number generator [Mun11], a process
that is now often automated [Hol16]. For this problem, we are going to
consider a simplified model of automated financial analysis.

Let us model the changes in a stock price over $n$ days using a sequence of
independent $\pm 1$ random variables $X_{1},X_{2},\dots,X_{n}$, where each
$X_{i}$ is $\pm 1$ with probability $1/2$. Let $S_{i}=\sum_{j=1}^{i}X_{j}$,
where $i\in\left\\{{0,\dots,n}\right\\}$, be the price after $i$ days.

Our automated financial reporter will declare a dead cat bounce if a stock
falls in price for two days in a row, followed by rising in price, followed by
falling in price again. Formally, a dead cat bounce occurs on day $i$ if
$i\geq 4$ and $S_{i-4}>S_{i-3}>S_{i-2}<S_{i-1}>S_{i}$. Let $D$ be the number
of dead cat bounces over the $n$ days.

  1. 1.

What is $\operatorname{E}\left[{D}\right]$?

  2. 2.

What is $\operatorname{Var}\left[{D}\right]$?

  3. 3.

Our investors will shut down our system if it doesn’t declare at least one
dead cat bounce during the first $n$ days. What upper bound you can get on
$\Pr\left[{D=0}\right]$ using Chebyshev’s inequality?

  4. 4.

Show $\Pr\left[{D=0}\right]$ is in fact exponentially small in $n$.

Note added 2016-09-28: It’s OK if your solutions only work for sufficiently
large $n$. This should save some time dealing with weird corner cases when $n$
is small.

##### Solution

  1. 1.

Let $D_{i}$ be the indicator variable for the event that a dead cat bounce
occurs on day $i$. Let
$p=\operatorname{E}\left[{D_{i}}\right]=\Pr\left[{D_{i}=1}\right]$. Then

$p=\Pr\left[{X_{i-3}=-1\wedge X_{i-2}=-1\wedge X_{i-1=+1}\wedge
X_{i}=-1}\right]=\frac{1}{16},$

since the $X_{i}$ are independent.

Then

$\displaystyle\operatorname{E}\left[{D}\right]$
$\displaystyle=\operatorname{E}\left[{\sum_{i=4}^{n}D_{i}}\right]$
$\displaystyle=\sum_{i=4}^{n}\operatorname{E}\left[{D_{i}}\right]$
$\displaystyle=\sum_{i=4}^{n}\frac{1}{16}$ $\displaystyle=\frac{n-3}{16},$

assuming $n$ is at least $3$.

  2. 2.

For variance, we can’t just sum up
$\operatorname{Var}\left[{D_{i}}\right]=p(1-p)=\frac{15}{256}$, because the
$D_{i}$ are not independent. Instead, we have to look at covariance.

Each $D_{i}$ depends on getting a particular sequence of four values for
$X_{i-3}$, $X_{i-2}$, $X_{i-1}$, and $X_{i}$. If we consider how $D_{i}$
overlaps with $D_{j}$ for $j>i$, we get these cases:

Variable | Pattern | Correlation
---|---|---
$D_{i}$ | \--+- |
$D_{i+1}$ | \--+- | inconsistent
$D_{i+2}$ | \--+- | inconsistent
$D_{i+3}$ |  \--+- | overlap in one place

For larger $j$, there is no overlap, so $D_{i}$ and $D_{j}$ are independent
for $j\geq 4$, giving $\operatorname{Cov}\left[{D_{i}},{D_{j}}\right]=0$ for
these cases.

Because $D_{i}$ can’t occur with $D_{i+1}$ or $D_{i+2}$, when
$j\in\left\\{{i+1,i+2}\right\\}$ we have

$\operatorname{Cov}\left[{D_{i}},{D_{j}}\right]=\operatorname{E}\left[{D_{i}D_{j}}\right]-\operatorname{E}\left[{D_{i}}\right]\operatorname{E}\left[{D_{j}}\right]=0-(1/16)^{2}=-1/256.$

When $j=i+3$, the probability that both $D_{i}$ and $D_{j}$ occur is
$1/2^{7}$, since we only need to get $7$ coin-flips right. This gives

$\operatorname{Cov}\left[{D_{i}},{D_{i+3}}\right]=\operatorname{E}\left[{D_{i}D_{i+3}}\right]-\operatorname{E}\left[{D_{i}}\right]\operatorname{E}\left[{D_{i+3}}\right]=1/128-(1/16)^{2}=1/256.$

Now apply (5.1.5):

$\displaystyle\operatorname{Var}\left[{D}\right]$
$\displaystyle=\operatorname{Var}\left[{\sum_{i=4}^{n}D_{i}}\right]$
$\displaystyle=\sum_{i=4}^{n}\operatorname{Var}\left[{D_{i}}\right]+2\sum_{i=4}^{n-1}\operatorname{Cov}\left[{D_{i}},{D_{i+1}}\right]+2\sum_{i=4}^{n-2}\operatorname{Cov}\left[{D_{i}},{D_{i+2}}\right]+2\sum_{i=4}^{n-3}\operatorname{Cov}\left[{D_{i}},{D_{i+3}}\right]$
$\displaystyle=(n-3)\frac{15}{256}+2(n-4)\frac{-1}{256}+2(n-5)\frac{-1}{256}+2(n-6)\frac{1}{256}$
$\displaystyle=\frac{13n-39}{256},$

where to avoid special cases, we assume $n$ is at least $6$.

  3. 3.

At this point we are just doing algebra. For $n\geq 6$, we have:

$\displaystyle\Pr\left[{D=0}\right]$ $\displaystyle\leq\Pr\left[{\lvert
D-\operatorname{E}\left[{D}\right]\rvert\geq\operatorname{E}\left[{D}\right]}\right]$
$\displaystyle=\Pr\left[{\lvert
D-\operatorname{E}\left[{D}\right]\rvert\geq\frac{n-3}{16}}\right]$
$\displaystyle\leq\frac{(13n-39)/256}{((n-3)/16)^{2}}$
$\displaystyle=\frac{13n-39}{(n-3)^{2}}$ $\displaystyle=\frac{13}{n-3}.$

This is $\Theta\left(1/n\right)$, which is not an especially strong bound.

  4. 4.

Here is an upper bound that avoids the mess of computing the exact
probability, but is still exponentially small in $n$. Consider the events
$[D_{4i}=1]$ for $i\in\left\\{{1,2,\dots,\lfloor n/4\rfloor}\right\\}$. These
events are independent since they are functions of non-overlapping sequences
of increments. So we can compute
$\Pr\left[{D=0}\right]\leq\Pr\left[{D_{4i}=0,\forall
i\in\left\\{{1,\dots,\lfloor n/4\rfloor}\right\\}}\right]=(15/16)^{\lfloor
n/4\rfloor}$.

This expression is a little awkward, so if we want to get an asymptotic
estimate we can simplify it using $1+x\leq e^{x}$ to get $(15/16)^{\lfloor
n/4\rfloor}\leq\exp\left(-(1/16)\lfloor
n/4\rfloor\right)=O\left(\exp\left(-n/64\right)\right)$.

With a better analysis, we should be able to improve the constant in the
exponent; or, if we are real fanatics, calculate $\Pr\left[{D=0}\right]$
exactly. But this answer is good enough given what the problems asks for.

####  B.2.2 Faulty comparisons

Suppose we want to do a comparison-based sort of an array of $n$ distinct
elements, but an adversary has sabotaged our comparison subroutine.
Specifically, the adversary chooses a sequence of times
$t_{1},t_{2},\dots,t_{n}$, such that for each $i$, the $t_{i}$-th comparison
we do returns the wrong answer. Fortunately, this can only happen $n$ times.
In addition, the adversary is oblivious: thought it can examine the algorithm
before choosing the input and the times $t_{i}$, it cannot predict any random
choices made by the algorithm.

A simple deterministic work-around is to replace each comparison in our
favorite $\Theta(n\log n)$-comparison sorting algorithm with $2n+1$
comparisons, and take the majority value. But this gives us a
$\Theta(n^{2}\log n)$-comparison algorithm. We would like to do better using
randomization.

Show that in this model, for every fixed $c>0$ and sufficiently large $n$, it
is possible to sort correctly with probability at least $1-n^{-c}$ using
$O(n\log^{2}n)$ comparisons.

##### Solution

We’ll adapt QuickSort. If the bad comparisons occurred randomly, we could just
take the majority of $\Theta(\log n)$ faulty comparisons to simulate a non-
faulty comparison with high probability. But the adversary is watching, so if
we do these comparisons at predictable times, it could hit all $\Theta(\log
n)$ of them and stay well within its fault budget. So we are going to have to
be more sneaky.

Here’s this idea: Suppose we have a list of $n$ comparisons
$\left\langle{x_{1},y_{1}}\right\rangle,\left\langle{x_{2},y_{2}}\right\rangle,\dots,\left\langle{x_{n},y_{n}}\right\rangle$
that we want to perform. We will use a subroutine that carries out these
comparisons with high probability by doing $kn\ln n+n$ possibly-faulty
comparisons, with $k$ a constant to be chosen below, where each of the
possibly-faulty comparisons looks at $x_{r}$ and $y_{r}$ where each $r$ is
chosen independently and uniformly at random. The subroutine collects the
results of these comparisons for each pair
$\left\langle{x_{i},y_{i}}\right\rangle$ and takes the majority value.

At most $n$ of these comparisons are faulty, and we get an error only if some
pair $\left\langle{x_{i},y_{i}}\right\rangle$ gets more faulty comparisons
than non-faulty ones. Let $B_{i}$ be the number of bad comparisons of the pair
$\left\langle{x_{i},y_{i}}\right\rangle$ and $G_{i}$ the number of good
comparisons. We want to bound the probability of the event $B_{i}>G_{i}$.

The probability that any particular comparison lands on a particular pair is
exactly $1/n$; so $\operatorname{E}\left[{B_{i}}\right]=1$ and
$\operatorname{E}\left[{G_{i}}\right]=k\ln n$. Now apply Chernoff bounds. From
(5.2.4), $\Pr\left[{B_{i}\geq(k/2)\ln n}\right]\leq 2^{-(k/2)\ln n}=n^{-(k\ln
2)/2)}$ provided $(k/2)\ln n$ is at least $6$. In the other direction, (5.2.6)
says that $\Pr\left[{G_{i}\leq(k/2)\log n}\right]\leq e^{-(1/2)^{2}k\log
n/2}=n^{-k/8}$. So we have a probability of at most $n^{-k/2}+n^{-k/8}$ that
we get the wrong result for this particular pair, and from the union bound we
have a probability of at most $n^{1-k/2}+n^{1-k/8}$ that we get the wrong
result for any pair. We can simplify this a bit by observe that $n$ must be at
least $2$ (or we have nothing to sort), so we can put a bound of $n^{2-k/8}$
on the probability of any error among our $n$ simulated comparisons, provided
$k\geq 12/\ln 2$. We’ll choose $k=\max(12/\ln 2,8(c+3))$ to get a probability
of error of at most $n^{-c-1}$.

So now let’s implement QuickSort. The first round of QuickSort picks a pivot
and performs $n-1$ comparisons. We perform these comparisons using our
subroutine (note we can always throw in extra comparisons to bring the total
up to $n$). Now we have two piles on which to run the algorithm recursively.
Comparing all nodes in each pile to the pivot for that pile requires $n-3$
comparisons, which can again be done by our subroutine. At the next state, we
have four piles, and we can again perform the $n-7$ comparisons we need using
the subroutine. Continue until all piles have size $1$ or less; this takes
O($\log n)$ rounds with high probability. Since each round does $O(n\log n)$
comparisons and fails with probability at most $n^{-c-1}$, the entire process
takes $O(n\log^{2}n)$ comparisons and fails with probability at most
$n^{-c-1}O(\log n)\leq n^{-c}$ when $n$ is sufficiently large.

###  B.3 Assignment 3: due Thursday, 2016-10-13, at 23:00

####  B.3.1 Painting with sprites

In the early days of computing, memory was scarce, and primitive home game
consoles like the Atari 2600 did not possess enough RAM to store the image
they displayed on your television. Instead, these machines used a graphics
chip that would composite together fixed sprites, bitmaps stored in ROM that
could be displayed at locations specified by the CPU.222In the actual Atari
2600 graphics hardware, the CPU did this not by writing down the locations in
RAM somewhere (which would take memory), but by counting instruction cycles
since the graphics chip started refreshing the screen and screaming “display
this sprite NOW!” when the CRT beam got to the right position. For this
problem we will assume a more modern approach, where we can just give a list
of locations to the graphics hardware. One common programming trick of this
era was to repurpose existing data in memory as sprites, for example by
searching through a program’s machine code instructions to find sequences of
bytes that looked like explosions when displayed.

For this problem, we will imagine that we have a graphics device that can only
display one sprite. This is a bitmap consisting of $m$ ones, at distinct
relative positions
$\left\langle{y_{1},x_{1}}\right\rangle,\left\langle{y_{2},x_{2}}\right\rangle,\dots\left\langle{y_{m},x_{m}}\right\rangle$.
Displaying a sprite at position $y,x$ on our $n\times n$ screen sets the
pixels at positions $\left\langle{(y+y_{i})\bmod n,(x+x_{i})\bmod
n}\right\rangle$ for all $i\in\left\\{{1,\dots,m}\right\\}$. The screen is
initially blank (all pixels $0$) and setting a pixel at some position
$\left\langle{y,x}\right\rangle$ changes it to $1$. Setting the same pixel
more than once has no effect.

We would like to use these sprites to simulate white noise on the screen, by
placing them at independent uniform random locations with the goal of setting
roughly half of the pixels. Unfortunately, because the contents of the screen
are not actually stored anywhere, we can’t detect when this event occurs.
Instead, we want to fix the number of sprites $\ell$ so that we get $1/2\pm
o(1)$ of the total number of pixels set to $1$ with high probability, by which
we mean that $(1/2\pm o(1))n^{2}$ total pixels are set with probability
$1-n^{-c}$ for any fixed $c>0$ and sufficiently large $n$, assuming $m$ is
fixed.

An example of this process, using Taito Corporation’s classic Space Invader
bitmap, is shown in Figure B.1.

|
---|---
Figure B.1: Filling a screen with Space Invaders. The left-hand image places
four copies of a 46-pixel sprite in random positions on a $40\times 40$
screen. The right-hand image does the same thing with $24$ copies.

Compute the value of $\ell$ that we need as a function of $n$ and $m$, and
show that this choice of $\ell$ does in fact get $1/2\pm o(1)$ of the pixels
set with high probability.

##### Solution

We will apply the following strategy. First, we’ll choose $\ell$ so that each
individual pixel is set with probability close to $1/2$. Linearity of
expectation then gives roughly $n^{2}/2$ total pixels set on average. To show
that we get close to this number with high probability, we’ll use the method
of bounded differences.

The probability that pasting in a single copy of the sprite sets a particular
pixel is exactly $m/n^{2}$. So the probability that the pixel is not set after
$\ell$ sprites is $(1-m/n^{2})^{\ell}$. This will be exactly $1/2$ if
$\ell=\log_{1-m/n^{2}}1/2=\frac{\ln(1/2)}{\ln(1-m/n^{2})}$.

Since $\ell$ must be an integer, we can just round this quantity to the
nearest integer to pick our actual $\ell$. For example, when $n=40$ and
$m=46$, $\frac{\ln(1/2)}{\ln(1-46/40^{2})}=23.7612...$ which rounds to $24$.

For large $n$, we can use the approximation $\ln(1+x)\approx x$ (which holds
for small $x$) to approximate $\ell$ as $(n^{2}\ln 2/m)+o(1)$. We will use
this to get a concentration bound using (5.3.12).

We have $\ell$ independent random variables corresponding to the positions of
the $\ell$ sprites. Moving a single sprite changes the number of set pixels by
at most $m$. So the probability that the total number of set pixels deviates
from its expectation by more than $an\sqrt{\ln n}$ is bounded by

$\displaystyle 2\exp\left(-\frac{\left(an\sqrt{\ln n}\right)^{2}}{\ell
m^{2}}\right)$ $\displaystyle=2\exp\left(-\frac{a^{2}n^{2}\ln n}{(n^{2}\ln
2/m+o(1))m^{2}}\right)$ $\displaystyle=2\exp\left(-\frac{a^{2}\ln n}{m\ln
2+o(m^{2}/n^{2})}\right)$ $\displaystyle\leq\exp\left(-(a^{2}/m)\ln n\right)$
$\displaystyle=n^{-a^{2}/m},$

where the inequality holds when $n$ is sufficiently large. Now choose
$a=\sqrt{cm}$ to get a probability of deviating by more than $n\sqrt{cm\ln n}$
of at most $n^{-c}$. Since $n\sqrt{cm\ln n}=o(1)n^{2}$, this give us our
desired bound.

####  B.3.2 Dynamic load balancing

A low-cost competitor to better-managed data center companies offers a
scalable dynamic load balancing system that supplies a new machine whenever a
new job shows up, so that there are always $n$ machines available to run $n$
jobs. Unfortunately, one of the ways the company cuts cost is by not hiring
programmers to replace the code from their previous randomized load balancing
mechanism, so when the $i$-th job arrives, it is still assigned uniformly at
random to one of the $i$ available machines. This means that job $1$ is always
assigned to machine $1$; job $2$ is assigned with equal probability to machine
$1$ or $2$; job $3$ is assigned with equal probability to machine $1$, $2$, or
$3$; and so on. These choices are all independent. The company claims that the
maximum load is still not too bad, and that the reduced programming costs that
they pass on to their customers make up for their poor quality control and
terrible service.

Justify the first part of this claim by showing that, with high probability,
the most loaded machine after $n$ jobs has arrived has load $O(\log n)$.

##### Solution

Let $X_{ij}$ be the indicator variable for the event that machine $i$ gets job
$j$. Then $\operatorname{E}\left[{X_{ij}}\right]=1/j$ for all $i\leq j$, and
$\operatorname{E}\left[{X_{ij}}\right]=0$ when $i>j$.

Let $Y_{i}=\sum_{j=1}^{n}X_{ij}$ be the load on machine $i$.

Then
$\operatorname{E}\left[{Y_{i}}\right]=\operatorname{E}\left[{\sum_{j=1}^{n}X_{ij}}\right]=\sum_{j=i}^{n}1/j\leq\sum_{j=1}^{n}1/j=H_{n}\leq\ln
n+1$.

From (5.2.4), we have $\Pr\left[{Y_{i}\geq R}\right]\leq 2^{-R}$ as long as
$R>2e\operatorname{E}\left[{Y_{i}}\right]$. So if we let $R=(c+1)\lg n$, we
get a probability of at most $n^{-c-1}$ that we get more than $R$ jobs on
machine $i$. Taking the union bound over all $i$ gives a probability of at
most $n^{-c}$ that any machine gets a load greater than $(c+1)\lg n$. This
works as long as $(c+1)\lg n\geq 2e(\ln n+1)$, which holds for sufficiently
large $c$. For smaller $c$, we can just choose a larger value $c^{\prime}$
that does work, and get that $\Pr\left[{\max Y_{i}\geq(c^{\prime}+1)\lg
n}\right]\leq n^{-c^{\prime}}\leq n^{-c}$.

So for any fixed $c$, we get that with probability at least $1-n^{-c}$ the
maximum load is $O(\log n)$.

###  B.4 Assignment 4: due Thursday, 2016-11-03, at 23:00

####  B.4.1 Re-rolling a random treap

Suppose that we add to a random treap (see §6.3) an operation that re-rolls
the priority of the node with a given key $x$. This replaces the old priority
for $x$ with a new priority generated uniformly at random, independently of
the old priority any other priorities in the treap. We assume that the range
of priorities is large enough that the probability that this produces a
duplicate is negligible, and that the choice of which node to re-roll is done
obliviously, without regard to the current priorities of nodes or the
resulting shape of the tree.

Changing the priority of $x$ may break the heap property. To fix the heap
property, we either rotate $x$ up (if its priority now exceeds its parent’s
priority) or down (if its priority is now less than that of one or both of its
children). In the latter case, we rotate up the child with the higher
priority. We repeat this process until the heap property is restored.

Compute the best constant upper bound you can on the expected number of
rotations resulting from executing a re-roll operation.

##### Solution

The best possible bound is at most $2$ rotations on average in the worst case.

There is an easy but incorrect argument that $2$ is an upper bound, which says
that if we rotate up, we do at most the same number of rotations as when we
insert a new element, and if we rotate down, we do at most the same number of
rotations as when we delete an existing element. This gives the right answer,
but for the wrong reasons: the cost of deleting $x$, conditioned on the event
that re-rolling its priority gives a lower priority, is likely to be greater
than $2$, since the conditioning means that $x$ is likely to be higher up in
the tree than average; the same thing happens in the other direction when $x$
moves up. Fortunately, it turns out that the fact that we don’t necessarily
rotate $x$ all the way to or from the bottom compensates for this issue.

This can be formalized using the following argument, for which I am indebted
to Adit Singha and Stanislaw Swidinski. Fix some element $x$, and suppose its
old and new priorities are $p$ and $p^{\prime}$. If $p<p^{\prime}$, we rotate
up, and the sequence of rotations is exactly the same as we get if we remove
all elements of the original treap with priority $p$ or less and then insert a
new element $x$ with priority $p^{\prime}$. But now if we condition on the
number $k$ of elements with priority greater than $p$, their priorities
together with $p^{\prime}$ are all independent and identically distributed,
since they are all obtained by taking their original distribution and
conditioning on being greater than $p$. So all $(k+1)!$ orderings of these
priorities are equally likely, and this means that we have the same expected
cost as an insertion into a treap with $k$ elements, which is at most $2$.
Averaging over all $k$ shows that the expected cost of rotating up is at most
$2$, and, since rotating down is just the reverse of this process with a
reversed distribution on priorities (since we get it by choosing $p^{\prime}$
as our old priority and $p$ as the new one), the expected cost of rotating
down is also at most $2$. Finally, averaging the up and down cases gives that
the expected number of rotations without conditioning on anything is at most
$2$.

We now give an exact analysis of the expected number of rotations, which will
show that $2$ is in fact the best bound we can hope for.

The idea is to notice that whenever we do a rotation involving $x$, we change
the number of ancestors of $x$ by exactly one. This will always be a decrease
in the number of ancestors if the priority of $x$ went up, or an increase if
the priority of $x$ went down, so the total number of rotations will be equal
to the change in the number of ancestors.

Letting $A_{i}$ be the indicator for the event that $i$ is an ancestor of $x$
before the re-roll, and $A^{\prime}_{i}$ the indicator for the even that $i$
is an ancestor of $x$ after the re-roll, then the number of rotations is just
$\left\lvert\sum_{i}A_{i}-\sum_{i}A^{\prime}_{i}\right\rvert$, which is equal
to $\sum_{i}\left\lvert A_{i}-A^{\prime}_{i}\right\rvert$ since we know that
all changes $A_{i}-A^{\prime}_{i}$ have the same sign. So the expected number
of rotations is just $\operatorname{E}\left[{\sum_{i}\left\lvert
A_{i}-A^{\prime}_{i}\right\rvert}\right]=\sum_{i}\operatorname{E}\left[{\left\lvert
A_{i}-A^{\prime}_{i}\right\rvert}\right]$, by linearity of expectation.

So we have to compute $\operatorname{E}\left[{\left\lvert
A_{i}-A^{\prime}_{i}\right\rvert}\right]$. Using the same argument as in
§6.3.2, we have that $A_{i}=1$ if and only if $i$ has the highest initial
priority of all elements in the range $[\min(i,x),\max(i,x)]$, and the same
holds for $A^{\prime}_{i}$ if we consider updated priorities. So we want to
know the probability that changing only the priority of $x$ to a new random
value changes whether $i$ has the highest priority.

Let $k=\max(i,x)-\min(i,x)+1$ be the number of elements in the range under
consideration. To avoid writing a lot of mins and maxes, let’s renumber these
elements as $1$ through $k$, with $i=1$ and $x=k$ (this may involve flipping
the sequence if $i>x$). Let $X_{1},\dots,X_{k}$ be the priorities of these
elements, and let $X^{\prime}_{k}$ be the new priority of $x$. These $k+1$
random variables are independent and identically distributed, so conditioning
on the even that no two are equal, all $(k+1)!$ orderings of their values are
equally likely.

So now let us consider how many of these orderings result in $\left\lvert
A_{i}-A^{\prime}_{i}\right\rvert=1$. For $A_{i}$ to be $1$, $X_{1}$ must
exceed all of $X_{2},\dots,X_{k}$. For $A^{\prime}_{i}$ to be $0$, $X_{1}$
must not exceed all of $X_{2},\dots,X_{k_{1}},X^{\prime}_{k}$. The
intersection of these events is when
$X^{\prime}_{k}>X_{1}>\max(X_{2},\dots,X_{k})$. Since $X_{2},\dots,X_{k}$ can
be ordered in any of $(k-1)!$ ways, this gives

$\Pr\left[{A_{i}=1\wedge
A^{\prime}_{i}=0}\right]=\frac{(k-1)!}{(k+1)!}=\frac{1}{k(k+1)}.$

In the other direction, for $A_{i}$ to be $0$ and $A^{\prime}_{i}$ to be $1$,
we must have $X_{k}>X_{1}>\max(X_{1},\dots,X_{k-1},X_{k})$. This again gives

$\displaystyle\Pr\left[{A_{i}=0\wedge A^{\prime}_{i}=1}\right]$
$\displaystyle=\frac{1}{k(k+1)}$ and combining the two cases gives
$\displaystyle\operatorname{E}\left[{\left\lvert
A_{i}-A^{\prime}_{i}\right\rvert}\right]=\frac{2}{k(k+1)}.$

Now sum over all $i$:

$\displaystyle\operatorname{E}\left[{\text{number of rotations}}\right]$
$\displaystyle=\sum_{i=1}^{n}\operatorname{E}\left[{\left\lvert
A^{\prime}_{i}-A_{i}\right\rvert}\right]$
$\displaystyle=\sum_{i=1}^{x-1}\frac{2}{(x-i+1)(x-i+2)}+\sum_{i=x+1}^{n}\frac{2}{(i-x+1)(i-x+2}$
$\displaystyle=\sum_{k=2}^{x}\frac{2}{k(k+1)}+\sum_{k=2}^{n-x+1}\frac{2}{k(k+1)}$
$\displaystyle=\sum_{k=2}^{x}\left(\frac{2}{k}-\frac{2}{k+1}\right)+\sum_{k=2}^{n-x+1}\left(\frac{2}{k}-\frac{2}{k+1}\right)$
$\displaystyle=2-\frac{2}{x+1}-\frac{2}{n-x+2}.$

In the limit as $n$ goes to infinity, choosing $x=\lfloor n/2\rfloor$ makes
both fractional terms converge to $0$, making the expected number of rotations
arbitrarily close to $2$. So $2$ is the best possible bound that doesn’t
depend on $n$.

####  B.4.2 A defective hash table

A foolish programmer implements a hash table with $m$ buckets, numbered
$0,\dots,m-1$, with the property that any value hashed to an even-numbered
bucket is stored in a linked list as usual, but any value hashed to an odd-
numbered bucket is lost.

  1. 1.

Suppose we insert a set $S$ of $n=\lvert S\rvert$ items into this hash table,
using a hash function $h$ chosen at random from a strongly $2$-universal hash
family $H$. Show that there is a constant $c$ such that, for any $t>0$, the
probability that at least $n/2+t$ items are lost is at most $cn/t^{2}$.

  2. 2.

Suppose instead that we insert a set $S$ of $n=\lvert S\rvert$ items into this
hash table, using a hash function $h$ chosen at random from a hash family
$H^{\prime}$ that is $2$-universal, but that may not be strongly
$2$-universal. Show that if $n\leq m/2$, it is possible for an adversary that
knows $S$ to design a $2$-universal hash family $H^{\prime}$ that ensures that
all $n$ items are lost with probability $1$.

##### Solution

  1. 1.

Let $X_{i}$ be the indicator variable for the event that the $i$-th element of
$S$ is hashed to an odd-numbered bucket. Since $H$ is strongly $2$-universal,
$\operatorname{E}\left[{X_{i}}\right]\leq 1/2$ (with equality when $m$ is
even), from which it follows that
$\operatorname{Var}\left[{X_{i}}\right]=\operatorname{E}\left[{X_{i}}\right](1-\operatorname{E}\left[{X_{i}}\right])\leq
1/4$; and the $X_{i}$ are pairwise independent. Letting
$Y=\sum_{i=1}^{n}X_{i}$ be the total number of items lost, we get
$\operatorname{E}\left[{Y}\right]\leq n/2$ and
$\operatorname{Var}\left[{Y}\right]\leq n/4$. But then we can apply
Chebyshev’s inequality to show

$\displaystyle\Pr\left[{Y\geq n/2+t}\right]$
$\displaystyle\leq\Pr\left[{Y\geq\operatorname{E}\left[{Y}\right]+t}\right]$
$\displaystyle\leq\frac{\operatorname{Var}\left[{Y}\right]}{t^{2}}$
$\displaystyle\leq\frac{n/4}{t^{2}}$ $\displaystyle=\frac{1}{4}(n/t^{2}).$

So the desired bound holds with $c=1/4$.

  2. 2.

Write $[m]$ for the set $\left\\{{0,\dots,m-1}\right\\}$. Let
$S=\left\\{{x_{1},x_{2},\dots,x_{n}}\right\\}$.

Consider the set $H^{\prime}$ of all functions $h:U\rightarrow[m]$ with the
property that $h(x_{i})=2i+1$ for each $i$. Choosing a function $h$ uniformly
from this set corresponds to choosing a random function conditioned on this
constraint; and this conditioning guarantees that every element of $S$ is sent
to an odd-numbered bucket and lost. This gives us half of what we want.

The other half is that $H^{\prime}$ is $2$-universal. Observe that for any
$y\not\in S$, the conditioning does not constrain $h(y)$, and so $h(y)$ is
equally likely to be any element of $[m]$; in addition, $h(y)$ is independent
of $h(z)$ for any $z\neq y$. So for any $y\neq z$,
$\Pr\left[{h(y)=h(z)}\right]=1/m$ if one or both of $y$ and $z$ is not an
element of $S$, and $\Pr\left[{h(y)=h(z)}\right]=0$ if both are elements of
$S$. In either case, $\Pr\left[{h(y)=h(z)}\right]\leq 1/m$, and so
$H^{\prime}$ is $2$-universal.

###  B.5 Assignment 5: due Thursday, 2016-11-17, at 23:00

####  B.5.1 A spectre is haunting Halloween

An adult in possession of $n$ pieces of leftover Halloween candy is
distributing them to $n$ children. The candies have known integer values
$v_{1},v_{2},\dots,v_{n}$, and the adult starts by permuting the candies
according to a uniform random permutation $\pi$. They then give candy $\pi(1)$
to child $1$, candy $\pi(2)$ to child $2$, and so on. Or at least, that is
their plan.

Unbeknownst to the adult, child $n$ is a very young Karl Marx, and after
observing the first $k$ candies $\pi(1),\dots,\pi(k)$, he can launch a
communist revolution and seize the means of distribution. This causes the
remaining $n-k$ candies $\pi(k+1)$ through $\pi(n)$ to be distributed evenly
among the remaining $n-k$ children, so that each receives a value equal to
exactly $\frac{1}{n-k}\sum_{i=k+1}^{n}v_{\pi(i)}$. Karl may declare the
revolution at any time before the last candy is distributed (even at time $0$,
when no candies have been distributed). However, his youthful understanding of
the mechanisms of historical determinism are not detailed enough to predict
the future, so his decision to declare a revolution after seeing $k$ candies
can only depend on those $k$ candies and his knowledge of the values of all of
the candies but not their order.

Help young Karl optimize his expected take by devising an algorithm that takes
as input $v_{1},\dots,v_{n}$ and $v_{\pi(1)},\dots,v_{\pi(k)}$, where $0\leq
k<n$, and outputs whether or not to launch a revolution at this time. Compute
Karl’s exact expected return as a function of $v_{1},\dots,v_{n}$ when running
your algorithm, and show that no algorithm can do better.

##### Solution

To paraphrase an often-misquoted line of Trotsky’s, young Karl Marx may not
recognize the Optional Stopping Theorem Theorem, but the Optional Stopping
does not permit him to escape its net. No strategy, no matter how clever, can
produce an expected return better or worse than simply waiting for the last
candy.

Let $X_{t}$ be the expected return if Karl declares the revolution after
seeing $t$ cards. We will show that $\left\\{{X_{t},\mathcal{F}_{t}}\right\\}$
is a martingale where each $\mathcal{F}_{t}$ is the $\sigma$-algebra generated
by the random variables $v_{\pi(1)}$ through $v_{\pi(t)}$.

The value of $X_{t}$ is exactly

$X_{t}=\frac{1}{n-t}\sum_{i=t+1}^{n}v_{\pi(i)}=\frac{1}{n-t}\left(\sum_{i=t+1}^{n}v_{n}-\sum_{i=1}^{t}v_{\pi(i)}\right).$

This is also
$\operatorname{E}\left[{v_{\pi(t+1)}}\;\middle|\;{\mathcal{F}_{t}}\right]$,
since the next undistributed candy is equally likely to be any of the
remaining candies, and $\mathcal{F}_{t}$ determines the value of $v_{\pi(i)}$
for all $i\leq t$. So

$\displaystyle\operatorname{E}\left[{X_{t+1}}\;\middle|\;{\mathcal{F}_{t}}\right]$
$\displaystyle=\operatorname{E}\left[{\frac{1}{n-t-1}\left(\sum_{i=1}^{n}v_{i}-\sum_{i=1}^{t+1}v_{\pi(i)}\right)}\;\middle|\;{\mathcal{F}_{t}}\right]$
$\displaystyle=\frac{1}{n-t-1}\left(\sum_{i=1}^{n}v_{i}-\sum_{i=1}^{t}v_{\pi(i)}\right)-\frac{1}{n-t-1}\operatorname{E}\left[{v_{\pi(t+1)}}\;\middle|\;{\mathcal{F}_{T}}\right]$
$\displaystyle=\frac{n-t}{n-t-1}X_{t}-\frac{1}{n-t-1}X_{t}$
$\displaystyle=X_{t}.$

Now fix some strategy for Karl, and let $\tau$ be the time at which he
launches the revolution. Then $\tau<n$ is a stopping time with respect to the
$\mathcal{F}_{t}$, and the Optional Stopping Theorem (bounded time version)
says that
$\operatorname{E}\left[{X_{\tau}}\right]=\operatorname{E}\left[{X_{0}}\right]$.
So any strategy is equivalent (in expectation) to launching the revolution
immediately.

####  B.5.2 Colliding robots on a line

Suppose we have $k$ robots on a line of $n$ positions, numbered $1$ through
$n$. No two robots can pass each other or occupy the same position, so we can
specify the positions of all the robots at time $t$ as an increasing vector
$X^{t}=\left\langle{X^{t}_{1},X^{t}_{2},\dots,X^{t}_{k}}\right\rangle$. At
each time $t$, we pick one of the robots $i$ uniformly at random, and also
choose a direction $d=\pm 1$ uniformly and independently at random. Robot $i$
moves to position $X^{t+1}=X^{t}_{i}+d$ if (a) $0\leq X^{t}_{i}+d<n$, and (b)
no other robot already occupies position $X^{t}_{i}+d$. If these conditions do
not hold, robot $i$ stays put, and $X^{t+1}_{i}=X^{t}_{i}$.

  1. 1.

Given $k$ and $n$, determine the stationary distribution of this process.

  2. 2.

Show that the mixing time $t_{\mathrm{mix}}$ for this process is polynomial in
$n$.

##### Solution

  1. 1.

The stationary distribution is a uniform distribution on all $\binom{n}{k}$
placements of the robots. To prove this, observe that two vectors increasing
vectors $x$ and $y$ are adjacent if and only if there is some $i$ such that
$x_{j}=y_{j}$ for all $j\neq i$ and $x_{j}+d=y_{j}$ for some
$d\in\left\\{{-1,+1}\right\\}$. In this case, the transition probability
$p_{xy}$ is $\frac{1}{2n}$, since there is a $\frac{1}{n}$ chance that we
choose $i$ and a $\frac{1}{2}$ chance that we choose $d$. But this is the same
as the probability that starting from $y$ we choose $i$ and $-d$. So we have
$p_{xy}=p_{yx}$ for all adjacent $x$ and $y$, which means that a uniform
distribution $\pi$ satisfies $\pi_{x}p_{xy}=\pi_{y}p_{yx}$ for all $x$ and
$y$.

To show that this stationary distribution is unique, we must show that there
is at least one path between any two states $x$ and $y$. One way to do this is
to show that there is a path from any state $x$ to the state
$\left\langle{1,\dots,k}\right\rangle$, where at each step we move the lowest-
index robot $i$ that is not already at position $i$. Since we can reverse this
process to get to $y$, this gives a path between any $x$ and $y$ that occurs
with nonzero probability.

  2. 2.

This one could be done in a lot of ways. Below I’ll give sketches of three
possible approaches, ordered by increasing difficulty. The first reduces to
card shuffling by adjacent swaps, the second uses an explicit coupling, and
the third uses conductance.

Of these approaches, I am personally only confident of the coupling argument,
since it’s the one I did before handing out the problem, and indeed this is
the only one I have written up in enough detail below to be even remotely
convincing. But the reduction to card shuffling is also pretty straightforward
and was used in several student solutions, so I am convinced that it can be
made to work as well. The conductance idea I am not sure works at all, but it
seems like it could be made to work with enough effort.

    1. (a)

Let’s start with the easy method. Suppose that instead of colliding robots, we
have a deck of $n$ cards, of which $k$ are specially marked. Now run a
shuffling algorithm that swaps adjacent cards at each step. If we place a
robot at the position of each marked card, the trajectories of the robots
follow the pretty much the same distribution as in the colliding-robots
process. This is trivially the case when we swap a marked card with an
unmarked card (a robot moves), but it also works when we swap two marked cards
(no robot moves, since the positions of the set of marked cards stays the
same; this corresponds to a robot being stuck).

Unfortunately we can’t use exactly the same process we used in §9.4.3.3,
because this (a) allows swapping the cards in the first and last positions of
the deck, and (b) doesn’t include any moves corresponding to a robot at
position $1$ or $n$ trying to move off the end of the line.

The first objection is easily dealt with, and indeed the cited result of
Wilson [Wil04] doesn’t allow such swaps either. The second can be dealt with
by adding extra no-op moves to the card-shuffling process that occur with
probability $1/n$, scaling the probabilities of the other operations to keep
the sum to $1$. This doesn’t affect the card-shuffling convergence argument
much, but it is probably a good idea to check that everything still works.

Finally, even after fixing the card-shuffling argument, we still have to argue
that convergence in the card-shuffling process implies convergence in the
corresponding colliding-robot process. Here is where the definition of total
variation distance helps. Let $C^{t}$ be the permutation of the cards after
$t$ steps, and let $f:C^{t}\mapsto X^{t}$ map permutations of cards to
positions of robots. Let $\pi$ and $\pi^{\prime}$ be the stationary
distributions of the card and robot processes, respectively. Then
$d_{TV}(f(C^{t}),f(\pi))=\max_{A}\left\lvert\Pr\left[{X^{t}\in
A}\right]-\pi^{\prime}(A)\right\rvert=\max_{A}\left\lvert\Pr\left[{C^{t}\in
f^{-1}(A)}\right]-\pi(f^{-1}(A))\right\rvert\leq\max_{B}\left\lvert\Pr\left[{C^{t}\in
B}\right]-\pi(B)\right\rvert=d_{TV}(C^{t},\pi)$. So convergence of $C$ implies
convergence of $X=f(C)$.

    2. (b)

Alternatively, we can construct a coupling between two copies of the process
$X^{t}$ and $Y^{t}$, where as usual we start $X^{0}$ in our initial
distribution (whatever it is) and $Y^{0}$ in the uniform stationary
distribution. At each step we generate a pair $(i,d)$ uniformly at random from
$\left\\{{1,\dots,n}\right\\}\times\left\\{{-1,+1}\right\\}$. Having generated
this pair, we move robot $i$ in direction $d$ in both processes if possible.
It is clear that once $X^{t}=Y^{t}$, it will continue to hold that
$X^{t^{\prime}}=Y^{t^{\prime}}$ for all $t^{\prime}>t$.

To show convergence we must show that $X^{t}$ will in fact eventually hit
$Y^{t}$. To do so, let us track $Z^{t}=\lVert
X^{t}-Y^{t}\rVert_{1}=\sum_{i=1}^{k}\lvert X^{t}_{i}-Y^{t}_{i}\rvert$. We will
show that $Z_{t}$ is a supermartingale with respect to the history
$\mathcal{F}_{t}$ generated by the random variables
$\left\langle{X^{s},Y^{s}}\right\rangle$ for $s\leq t$. Specifically, we will
show that at each step, the expected change in $Z^{t}$ conditioning on $X^{t}$
and $Y^{t}$ is non-positive.

Fix $X^{t}$, and consider all $2n$ possible moves $(i,d)$. Since $(i,d)$
doesn’t change $X^{t}_{j}$ for any $j\neq i$, the only change in $Z^{t}$ will
occur if one of $X^{t}_{i}$ and $Y^{t}_{i}$ can move and the other can’t.
There are several cases:

      1. i.

If $i=k$, $d=+1$, and exactly one of $X^{t}_{k}$ and $Y^{t}_{k}$ is $n$, then
the copy of the robot not at $n$ moves toward the copy at $n$, giving
$Z_{t+1}-Z_{t}=-1$. The same thing occurs if $i=1$, $d=-1$, and exactly one of
$X^{t}_{1}$ and $Y^{t}_{1}$ is $1$.

It is interesting to note that these two cases will account for the entire
nonzero part of
$\operatorname{E}\left[{Z_{t+1}-Z_{t}}\;\middle|\;{\mathcal{F}_{t}}\right]$,
although we will not use this fact.

      2. ii.

If $i<k$, $d=+1$, $X^{t}_{i}+1=X^{t}_{i+1}$, but $Y^{t}_{i}+1<X^{t}_{i+1}$,
and $X^{t}_{i}\leq Y^{t}_{i}$, then robot $i$ can move right in $Y^{t}$ but
not in $X^{t}$. This gives $Z^{t+1}-Z^{t}=+1$.

However, in this case the move $(i+1,-1)$ moves robot $i+1$ left in $Y^{t}$
but not in $X^{t}$, and since $Y^{t}_{i+1}>Y^{t}_{i}+1>X^{t}_{i}=X^{t+1}_{i}$,
this move gives $Z^{t+1}-Z^{t}=-1$. Since the moves $(i,+1)$ and $(i+1,-1)$
occur with equal probability, these two changes in $Z^{t}$ cancel out on
average.

Essentially the same analysis applies if we swap $X^{t}$ with $Y^{t}$, and if
we consider moves $(i,-1)$ where $i>1$ in which one copy of the robot is
blocked but not the other. If we enumerate all such cases, we find that for
every move of these types that increase $Z^{t}$, there is a corresponding move
that decreases $Z^{t}$; it follows that these changes sum to zero in
expectation.

Because each $X^{t}_{i}$ and $Y^{t}_{i}$ lies in the range $[1,n]$, it holds
trivially that $Z^{t}\leq k(n-1)<n^{2}$. Consider an unbiased $\pm 1$ random
walk $W^{t}$ with a reflecting barrier at $n^{2}$ (meaning that at $n^{2}$ we
always move down) and an absorbing barrier at $0$. Then the expected time to
reach $0$ starting from $W^{t}=x$ is given by $x(2n^{2}-x)\leq n^{4}$. Since
this unbiased random walk dominates the biased random walk corresponding to
changes in $Z^{t}$, this implies that $Z^{t}$ can change at most $n^{4}$ times
on average before reaching $0$.

Now let us ask how often $Z^{t}$ changes. The analysis above implies that
there is a chance of at least $1/n$ that $Z^{t}$ changes in any state where
some robot $i$ with $X^{t}_{i}\neq Y^{t}_{i}$ is blocked from moving freely in
one or both directions in either the $X^{t}$ or $Y^{t}$ process. To show that
this occurs after polynomially many steps, choose some $i$ with $X^{t}_{i}\neq
Y^{t}_{i}$ that is not blocked in either process. Then $i$ is selected every
$\frac{1}{n}$ steps on average, and it moves according to a $\pm 1$ random
walk as long as it is not blocked. But a $\pm 1$ random walk will reach
position $1$ or $n$ in $O(n^{2})$ steps on average (corresponding to
$O(n^{3})$ steps of the original Markov chain), and $i$ will be blocked by the
left or right end of the line if it is not blocked before then. It follows
that we reach a state in which $Z^{t}$ changes with probability at least
$\frac{1}{n}$ after $O(n^{3})$ expected steps, which means that $Z^{t}$
changes every $O(n^{4})$ on average. Since we have previously established that
$Z^{t}$ reaches $0$ after $O(n^{4})$ expected changes, this gives a total of
$O(n^{8})$ expected steps of the Markov process before $Z^{t}=0$, giving
$X^{t}=Y^{t}$. Markov’s inequality and the Coupling Lemma then give
$t_{\mathrm{mix}}=O(n^{8})$.

    3. (c)

I believe it may also be possible to show convergence using a conductance
argument. The idea is to represent a state
$\left\langle{x_{1},\dots,x_{k}}\right\rangle$ as the differences
$\left\langle{\Delta_{1},\dots,\Delta_{n}}\right\rangle$, where
$\Delta_{1}=x_{1}$ and $\Delta_{i+1}=x_{i+1}-x_{i}$. This representation makes
the set of possible states $\left\\{{\Delta}\;\middle|\;{\Delta_{i}\geq
1,\sum_{i=1}^{k}\Delta_{i}\leq n}\right\\}$ look like a simplex, a pretty
well-behaved geometric object. In principle it should be possible to show an
isoperimetric inequality that the lowest-conductance sets in this simplex are
the $N$ points closest to any given corner, or possibly get a lower bound on
conductance using canonical paths. But the $\Delta$ version of the process is
messy (two coordinates change every time a robot moves), and there are some
complication with this not being a lazy random walk, so I didn’t pursue this
myself.

###  B.6 Assignment 6: due Thursday, 2016-12-08, at 23:00

####  B.6.1 Another colliding robot

A warehouse consists of an $n\times n$ grid of locations, which we can think
of as indexed by pairs $(i,j)$ where $1\leq i,j\leq n$. At night, the
warehouse is patrolled by a robot executing a lazy random walk. Unfortunately
for the robot, there are also $m$ crates scattered about the warehouse, and if
the robot attempts to walk onto one of the $m$ grid locations occupied by a
crate, it fails to do so, and instead emits a loud screeching noise. We would
like to use the noises coming from inside the warehouse to estimate $m$.

Formally, if the robot is at position $(i,j)$ at time $t$, then at time $t+1$
it either (a) stays at $(i,j)$ with probability $1/2$; or (b) chooses a
position $(i^{\prime},j^{\prime})$ uniformly at random from
$\left\\{{(i-1,j),(i+1,j),(i,j-1),(i,j+1)}\right\\}$ and attempts to move to
it. If the robot chooses not to move, it makes no noise. If it chooses to
move, but $(i^{\prime},j^{\prime})$ is off the grid or occupied by one of the
$m$ crates, then the robot stays at $(i,j)$ and emits the noise. Otherwise it
moves to $(i^{\prime},j^{\prime})$ and remains silent. The robot’s position at
time $0$ can be any unoccupied location on the grid.

To keep the robot from getting walled in somewhere, whatever adversary placed
the crates was kind enough to ensure that if a crate was placed at position
$(i,j)$, then all of the eight positions

$\begin{array}[]{ccc}(i-1,j+1)&(i,j+1)&(i+1,j+1)\\\ (i-1,j)&&(i+1,j)\\\
(i-1,j-1)&(i,j-1)&(i+1,j-1)\\\ \end{array}$

reachable by a king’s move from $(i,j)$ are unoccupied grid locations. This
means that they are not off the grid and not occupied by another crate, so
that the robot can move to any of these eight positions.

Your job is to devise an algorithm for estimating $m$ to within $\epsilon$
relative error with probability at least $1-\delta$, based on the noises
emitted by the robot. The input to your algorithm is the sequence of bits
$x_{1},x_{2},x_{3},\dots$, where $x_{i}$ is $1$ if the robot makes a noise on
its $i$-th step. Your algorithm should run in time polynomial in $n$,
$1/\epsilon$, and $\log(1/\delta)$.

##### Solution

It turns out that $\epsilon$ is a bit of a red herring: we can in fact compute
the _exact_ number of crates with probability $1-\delta$ in time polynomial in
$n$ and $\log(1/\delta)$.

The placement restrictions and laziness make this an irreducible aperiodic
chain, so it has a unique stationary distribution $\pi$. It is easy to argue
from reversibility that this is uniform, so each of the $N=n^{2}-m$ unoccupied
positions occurs with probability exactly $1/N$.

It will be useful to observe that we can assign three unique unoccupied
positions to each crate, to the east, south, and southeast, and this implies
$m\leq n^{2}/4$.

The idea now is to run the robot until the distribution on its position is
close to $\pi$, and then see if it hits an obstacle on the next step. We can
easily count the number of possible transitions that hit an obstacle, since
there are $4m$ incoming edges to the crates, plus $4n$ incoming edges to the
walls. Since each edge $uv$ has probability $\pi_{u}p_{uv}=\frac{1}{8N}$ of
being selected in the stationary distribution, the probability $q$ that we hit
an obstacle starting from $\pi$ is exactly
$\frac{n+m}{2N}=\frac{n+m}{n^{2}-m}$. This function is not trivial to invert,
but we don’t have to invert it: if we can compute its value (to some
reasonable precision), we can compare it to all $n^{2}/4+1$ possible values of
$m$, and see which it matches. But we still have to deal with both getting
enough samples and the difference between our actual distribution when we take
a sample and the stationary distribution. For the latter, we need a
convergence bound.

We will get this bound by constructing a family of canonical paths between
each distinct pair of locations $(i,j)$ and $(i^{\prime},j^{\prime})$. In the
absence of crates, we can use the L-shaped paths that first change $i$ to
$i^{\prime}$ and then $j$ to $j^{\prime}$, one step at a time in the obvious
way. If we encounter a crate at some position along this path, we replace that
position with a detour that uses up to three locations off the original path
to get around the obstacle. The general rule is that if we are traveling left-
to-right or right-to-left, we shift up one row to move past the obstacle, and
if we are moving up-to-down or down-to-up, we shift left one column. An
annoying special case is when the obstacle appears exactly at the corner
$(i^{\prime},j)$; here we replace the blocked position with the unique
diagonally adjacent position that still gives us a path.

Consider the number of paths $(i,j)\rightarrow(i^{\prime},j^{\prime})$
crossing a particular left-right edge $(x,y)\rightarrow(x+1,y)$. There are two
cases we have to consider:

  1. 1.

We cross the edge as part of the left-to-right portion of the path (this
includes left-to-right moves that are part of detours). In this case we have
$\lvert j-y\rvert\leq 1$. This gives at most $3$ choices for $j$, giving at
most $3n^{3}$ possible paths. (The constants can be improved here.)

  2. 2.

We cross the edge as part of a detour on the vertical portion of the path.
Then $\lvert i-x\rvert\leq 1$, and so we again have at most $3n^{3}$ possible
paths.

This gives at most $6n^{3}$ possible paths across each edge, giving a
congestion

$\displaystyle\rho$
$\displaystyle\leq\frac{1}{\pi_{ij}p_{ij,i^{\prime}j^{\prime}}}(6n^{3})\pi_{ij}\pi_{i^{\prime}j^{\prime}}$
$\displaystyle=\frac{1}{N^{-1}(1/8)}(6n^{3})N^{-2}$
$\displaystyle=24n^{3}N^{-}1$ $\displaystyle\leq
24n^{3}(\frac{3}{4}n^{2})^{-1}$ $\displaystyle=32n,$

since we can argue from the placement restrictions that $N\leq n^{2}/4$. This
immediately gives a bound $\tau_{2}\leq 8\rho^{2}\leq O(n^{2})$. using Lemma
9.5.3.

So let’s run for $\lceil 51\tau_{2}\ln n\rceil=O(n^{2}\ln n)$ steps for each
sample. Starting from any initial location, we will reach some distribution
$\sigma$ with $d_{TV}{\sigma,\pi}=O(n^{-50})$. Let $X$ be the number of
obstacles (walls or crates) adjacent to the current position, then we can
apply Lemma 9.2.2 to get
$\lvert\operatorname{E}_{\sigma}(X)-\operatorname{E}_{\pi}(X)\rvert\leq
4d_{TV}(\sigma,\pi)=O(n^{-50})$. The same bound (up to constants) also applies
to the probability $\rho=X/8$ of hitting an obstacle, giving
$\rho=4(n+m)/(n^{2}-m)\pm O(n^{-50})$. Note that $\rho$ is $\Theta(n^{-1}$ for
all values of $m$.

Now take $n^{10}\sqrt{\ln(1/\delta)}$ samples, with a gap of $\lceil
51\tau_{2}\ln n\rceil$ steps between each. The expected number of positive
samples is
$\mu=(\rho+O(n^{-50}))n^{10}\sqrt{\ln(1/\delta)}=\Theta(n^{9}\sqrt{\ln(1/\delta)})$,
and from Lemma 5.2.2, the probability that the number of positive samples
exceeds $\mu(1+n^{-4})$ is at most $\exp(-\mu
n^{-8}/3)=\exp(-\Theta(n\ln(1/\delta)))=\delta^{\Theta(n)}\leq\delta/2$ for
sufficiently large $n$. A similar bound holds on the other side. So with
probability at least $1-\delta$ we get an estimate $\hat{\rho}$ of
$\rho=4(n+m)/(n^{2}-m)$ that is accurate to within a relative error of
$n^{-4}$. Since $\frac{d\rho}{dm}=O(n^{-2})$ throughout the interval spanned
by $m$, and since $\rho$ itself is $\Theta(n^{-1})$, any relative error that
is $o(n^{-1})$ will give us an exact answer for $m$ when we round to the
nearest value of $\rho$. We are done.

We’ve chosen big exponents because all we care about is getting a polynomial
bound. With a cleaner analysis we could probably get better exponents. It is
also worth observing that the problem is ambiguous about whether we have
random access to the data stream, and whether the time taken by the robot to
move around counts toward our time bound. If we are processing the stream
after the fact, and are allow to skip to specific places in the stream at no
cost, we can get each sample in $O(1)$ time. This may further reduce the
exponents, and demonstrates why it is important to nail down all the details
of a model.

####  B.6.2 Return of the sprites

The Space Invaders from Problem B.3.1 are back, and now they are trying to
hide in random $n\times n$ bitmaps, where each pixel is set with probability
$1/2$. Figure B.2 shows an example of this, with two sprites embedded in an
otherwise random bitmap.

|
---|---
Figure B.2: Two hidden Space Invaders. On the left, the Space Invaders hide
behind random pixels. On the right, their positions are revealed by turning
the other pixels gray.

The sprites would like your assistance in making their hiding places
convincing. Obviously it’s impossible to disguise their presence completely,
but to make the camouflage as realistic as possible, they would like you to
provide them with an algorithm that will generate an $n\times n$ bitmap
uniformly at random, conditioned on containing _at least two_ copies of a
given $m$-pixel sprite at distinct offsets. (It is OK for the sprites to
overlap, but they cannot be directly on top of each other, and sprites that
extend beyond the edges of the bitmap wrap around as in Problem B.3.1.) Your
algorithm should make the probability of each bitmap that contains at least
two copies of the sprite be exactly equally likely, and should run in expected
time polynomial in $n$ and $m$.

##### Solution

Rejection sampling doesn’t work here because if the sprites are large, the
chances of getting two sprites out of a random bitmap are exponentially small.
Generating a random bitmap and slapping two sprites on top of it also doesn’t
work, because it gives a non-uniform distribution: if the sprites overlap in
$k$ places, there are $2^{n^{2}-2m+k}$ choices for the remaining bits, which
means that we would have to adjust the probabilities to account for the effect
of the overlap. But even if we do this, we still have issues with bitmaps that
contain more than two sprites: a bitmap with three sprites can be generated in
three different ways, and it gets worse quickly as we generate more. It may be
possible to work around these issues, but a simpler approach is to use the
sampling mechanism from Karp-Luby [KL85] (see also §10.3).

Order all $\binom{n^{2}}{2}$ positions $u<v$ for the two planted sprites in
lexicographic order. For each pair of positions $u<v$, let $A_{uv}$ be the set
of all bitmaps with sprites at $u$ and $v$. Then we can easily calculate
$\lvert A_{uv}\rvert=2^{n^{2}-2m+k}$ where $k$ is the number of positions
where sprites at $u$ and $v$ overlap, and so we can sample a particular
$A_{uv}$ with probability $\lvert A_{uv}\rvert/\sum_{st}\lvert A_{st}\rvert$
and then choose an element of $A_{uv}$ uniformly at random by filling in the
positions not covered by the sprites with independent random bits. To avoid
overcounting, we discard any bitmap that contains a sprite at a position less
than $\max(u,v)$; this corresponds to discarding any bitmap that appears in
$A_{st}$ for some $st<uv$. By the same argument as in Karp-Luby, we expect to
discard at most $\binom{n^{2}}{2}$ bitmaps before we get one that works. This
gives an expected $O(n^{4})$ attempts, each of which requires about $O(n^{2})$
work to generate a bitmap and $O(n^{2}m)$ work to test it, for a nicely
polynomial $O(n^{6}m)$ expected time in total.

If we don’t want to go through all this analysis, we could also reduce to
Karp-Luby directly by encoding the existence of two sprites as a large DNF
formula consisting of $\binom{n^{2}}{2}$ clauses, and then argue that the
sampling mechanism inside Karp-Luby gives us what we want.

###  B.7 Final exam

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

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

####  B.7.1 Virus eradication (20 points)

Viruses have infected a network structured as an undirected graph $G=(V,E)$.
At time $0$, all $n=\lvert V\rvert$ nodes are infected. At each step, as long
as there is at least one infected node, we can choose a node $v$ to disinfect;
this causes $v$ to become uninfected, but there is an independent
$\frac{1}{2d(v)}$ chance that each of $v$’s neighbors becomes infected if it
is not infected already, where $d(v)$ is the degree of $v$.

Let $X_{t}$ be the number of nodes that are infected after $t$ disinfection
steps. Let $\tau$ be the first time at which $X_{\tau}=0$. Show that, no
matter what strategy is used to select nodes to disinfect,
$\operatorname{E}\left[{\tau}\right]=O(n)$.

_Clarification added during exam:_ When choosing a node to disinfect, the
algorithm can only choose nodes that are currently infected.

##### Solution

Let $Y_{t}=X_{t}+\frac{1}{2}\min(t,\tau)$. We will show that
$\left\\{{Y_{t}}\right\\}$ is a supermartingale. Suppose we disinfect node $v$
at time $t$, and that $v$ has $d^{\prime}\leq d(v)$ uninfected neighbors. Then
$\operatorname{E}\left[{X_{t+1}}\;\middle|\;{X_{t}}\right]=X_{t}-1+\frac{d^{\prime}}{2d(v)}\leq
X_{t}-\frac{1}{2}$, because we always disinfect $v$ and each of its
$d^{\prime}$ uninfected neighbors contributes $\frac{1}{2d(v)}$ new infections
on average. We also have $\min(\tau,t)$ increasing by $1$ in this case. This
gives $\operatorname{E}\left[{Y_{t+1}}\;\middle|\;{Y_{t}}\right]\leq
Y_{t}-\frac{1}{2}+\frac{1}{2}=Y_{t}$ when $t<\tau$; it also holds trivially
that $Y_{t+1}=Y_{t}$ when $t\geq\tau$. So
$\operatorname{E}\left[{Y_{t+1}}\;\middle|\;{Y_{t}}\right]\leq Y_{t}$ always.

Now apply the optional stopping theorem. We have bounded increments, because
$\lvert Y_{t+1}-Y_{t}\rvert\leq n+\frac{1}{2}$. We also have bounded expected
time, because there is a nonzero probability $\epsilon$ that each sequence of
$n$ consecutive disinfections produces no new infections, giving
$\operatorname{E}\left[{\tau}\right]\leq 1/\epsilon$. So
$n=Y_{0}\geq\operatorname{E}\left[{Y_{\tau}}\right]=\frac{1}{2}\operatorname{E}\left[{\tau}\right]$,
giving $\operatorname{E}\left[{\tau}\right]\leq 2n=O(n)$.

####  B.7.2 Parallel bubblesort (20 points)

Suppose we are given a random bit-vector and choose to sort it using parallel
bubblesort. The initial state consists of $n$ independent fair random bits
$X^{0}_{1},X^{0}_{2},\dots,X^{0}_{n}$, and in each round, for each pair of
positions $X^{t}_{i}$ and $X^{t}_{i+1}$, we set new values $X^{t+1}_{i}=0$ and
$X^{t+1}_{i+1}=1$ if $X^{t}_{i}=1$ and $X^{t}_{i+1}=0$. When it holds that
$X^{t}_{i}=1$ and $X^{t}_{i+1}=0$, we say that there is a swap at position $i$
in round $t$. Denote the total number of swaps in round $t$ by $Y_{t}$.

  1. 1.

What is $\operatorname{E}\left[{Y_{0}}\right]$?

  2. 2.

What is $\operatorname{E}\left[{Y_{1}}\right]$?

  3. 3.

Show that both $Y_{0}$ and $Y_{1}$ are concentrated around their expectations,
by showing, for any fixed $c>0$ and each $t\in\left\\{{0,1}\right\\}$, that
there exists a function $f_{t}(n)=o(n)$ such that $\Pr\left[{\left\lvert
Y_{t}-\operatorname{E}\left[{Y_{t}}\right]\right\rvert\geq
f_{t}(n)}\right]\leq n^{-c}$.

##### Solution

  1. 1.

This is a straightforward application of linearity of expectation. Let
$Z^{t}_{i}$, for each $i\in\left\\{{1,\dots,n-1}\right\\}$, be the indicator
for the event that $X^{t}_{i}=1$ and $X^{t}_{i+1}=0$. For $t=0$, $X^{0}_{i}$
and $X^{0}_{i+1}$ are independent, so this event occurs with probability
$\frac{1}{4}$. So
$\operatorname{E}\left[{Y_{0}}\right]=\operatorname{E}\left[{\sum_{i=1}^{n-1}Z^{0}_{i}}\right]=\sum_{i=1}^{n-1}\operatorname{E}\left[{Z^{0}_{i}}\right]=(n-1)\frac{1}{4}=\frac{n-1}{4}$.

  2. 2.

Again we want to use linearity of expectation, but we have to do a little more
work to calculate $\operatorname{E}\left[{Z^{1}_{i}}\right]$. For $Z^{1}_{i}$
to be $1$, we need $X^{1}_{i}=1$ and $X^{1}_{i+1}=0$. If we ask where that $1$
in $X^{1}_{i}$ came from, either it started in $X^{0}_{i-1}$ and moved to
position $i$ because $X^{0}_{i}=0$, or it started in $X^{0}_{i}$ and didn’t
move because $X^{0}_{i+1}=1$. Similarly the $0$ in $X^{1}_{i+1}$ either
started in $X^{0}_{i+2}$ and moved down to replace $X^{0}_{i+1}=1$ or started
in $X^{1}_{i+1}$ and didn’t move because $X^{0}_{i}=0$. Enumerating all the
possible assignments of $X^{0}_{i-1}$, $X^{0}_{i}$, $X^{0}_{i+1}$, and
$X^{0}_{i+2}$ consistent with these conditions gives $0110$, $1000$, $1001$,
$1010$, and $1110$, making $\operatorname{E}\left[{Z^{1}_{i}}\right]=5\cdot
2^{-4}=\frac{5}{16}$ when $2\leq i\leq n-2$. This accounts for $n-3$ of the
positions.

There are two annoying special cases: when $i=1$ and when $i=n-1$. We can
handle these with the above analysis by pretending that $X^{t}_{0}=0$ and
$X^{t}_{n+1}=1$ for all $t$; this leaves the initial patterns $0110$ for $i=1$
and $1001$ for $i=n-1$, each of which occurs with probability $\frac{1}{8}$.

Summing over all cases then gives
$\operatorname{E}\left[{Y_{1}}\right]=\frac{1}{8}+\sum_{i=2}^{n-3}\frac{5}{16}+\frac{1}{8}=\frac{5n-11}{16}$.

  3. 3.

The last part is just McDiarmid’s inequality. Because the algorithm is
deterministic aside from the initial random choice of input, We can express
each $Y_{t}$ as a function $g_{t}(X^{0}_{1},\dots,X^{0}_{n})$ of the
independent random variables $X^{0}_{1},\dots,X^{0}_{n}$. Changing some
$X^{0}_{i}$ can change $Z^{0}_{i-1}$ and $Z^{0}_{i}$, for a total change to
$Y_{0}$ of at most $2$; similarly, changing $X^{0}_{i}$ can change at most
$Z^{1}_{i-2}$, $Z^{1}_{i-1}$, $Z^{1}_{i}$, and $Z^{i}_{i+1}$, for a total
change of at most $4$. So McDiarmid says that, for each
$t\in\left\\{{0,1}\right\\}$, $\Pr\left[{\lvert
Y_{t}-\operatorname{E}\left[{Y_{t}}\right]\rvert\leq s}\right]\leq
2\exp{-\Theta(s^{2}/n)}$. For any fixed $c>0$, there is some
$s=\Theta(\sqrt{n\log n})=o(n)$ such that the right-hand side is less than
$n^{-c}$.

####  B.7.3 Rolling a die (20 points)

Suppose we have a device that generates a sequence of independent fair random
coin-flips, but what we want is a six-sided die that generates the values
$1,2,3,4,5,6$ with equal probability.

  1. 1.

Give an algorithm that does so using $O(1)$ coin-flips on average.

  2. 2.

Show that any correct algorithm for this problem will use more than $n$ coin-
flips with probability at least $2^{-O(n)}$.

##### Solution

  1. 1.

Use rejection sampling: generate $3$ bits, and if the resulting binary number
is not in the range $1,\dots,6$, try again. Each attempt consumes $3$ bits and
succeeds with probability $3/4$, so we need to generate $\frac{4}{3}\cdot 3=4$
bits on average.

It is possible to improve on this by reusing the last bit of a discarded
triple of bits as the first bit in the next triple. This requires a more
complicated argument to show uniformity, but requires only two bits for each
attempt after the first, for a total of $3+\frac{1}{4}\cdot\frac{4}{3}\cdot
2=\frac{11}{3}$ bits on average. This is still $O(1)$, so unless that
$\frac{1}{3}$ bit improvement is really important, it’s probably easiest just
to do rejection sampling.

  2. 2.

Suppose that we have generated $n$ bits so far. Since $6$ does not evenly
divide $2^{n}$ for any $n$, we cannot assign an output from $1,\dots,6$ to all
possible $2^{n}$ sequences of bits without giving two outputs different
probabilities. So we must keep going in at least one case, giving a
probability of at least $2^{-n}=2^{-O(n)}$ that we continue.

##  Appendix C Sample assignments from Spring 2014

Assignments are typically due Wednesdays at 17:00. Assignments should be
submitted in PDF format via the classesv2 Drop Box.

###  C.1 Assignment 1: due Wednesday, 2014-09-10, at 17:00

####  C.1.1 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.

Anything else you’d like to say.

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

####  C.1.2 Two terrible data structures

Consider the following data structures for maintaining a sorted list:

  1. 1.

A sorted array $A$. Inserting a new element at position $A[i]$ into an array
that current contains $k$ elements requires moving the previous values in
$A[i]\dots A[k]$ to $A[i+1]\dots A[k+1]$. Each element moved costs one unit.

For example, if the array currently contains 1 3 5, and we insert 2, the
resulting array will contain 1 2 3 5 and the cost of the operation will be
$2$, because we had to move 3 and 5.

  2. 2.

A sorted doubly-linked list. Inserting a new element at a new position
requires moving the head pointer from its previous position to a neighbor of
the new node, and then to the new node; each pointer move costs one unit.

For example, if the linked list currently contains 1 3 5, with the head
pointer pointing to 5, and we insert 2, the resulting linked list will contain
1 2 3 5, with the head pointing to 2, and the cost will be $2$, because we had
to move the pointer from 5 to 3 and then from 3 to 2. Note that we do not
charge for updating the pointers between the new element and its neighbors. We
will also assume that inserting the first element is free.

Suppose that we insert the elements $1$ through $n$, in random order, into
both data structures. Give an exact closed-form expression for the expected
cost of each sequence of insertions.

##### Solution

  1. 1.

Suppose we have already inserted $k$ elements. Then the next element is
equally likely to land in any of the positions $A[1]$ through $A[k+1]$. The
number of displaced elements is then uniformly distributed in $0$ through $k$,
giving an expected cost for this insertion of $\frac{k}{2}$.

Summing over all insertions gives

$\displaystyle\sum_{k=0}^{n-1}\frac{k}{2}$
$\displaystyle=\frac{1}{2}\sum_{k=0}^{n-1}$ $\displaystyle=\frac{n(n-1)}{4}.$

An alternative proof, which also uses linearity of expectation, is to define
$X_{ij}$ as the indicator variable for the event that element $j$ moves when
element $i<j$ is inserted. This is $1$ if an only if $j$ is inserted before
$i$, which by symmetry occurs with probability exactly $1/2$. So the expected
total number of moves is

$\displaystyle\sum_{1\leq i<j\leq n}\operatorname{E}\left[{X_{ij}}\right]$
$\displaystyle=\sum_{1\leq i<j\leq n}\frac{1}{2}$
$\displaystyle=\frac{1}{2}\binom{n}{2}$ $\displaystyle=\frac{n(n-1)}{4}.$

It’s always nice when we get the same answer in situations like this.

  2. 2.

Now we need to count how far the pointer moves between any two consecutive
elements. Suppose that we have already inserted $k-1>0$ elements, and let
$X_{k}$ be the cost of inserting the $k$-th element. Let $i$ and $j$ be the
indices in the sorted list of the new and old pointer positions after the
$k$-th insertion. By symmetry, all pairs of distinct positions $i\neq j$ are
equally likely. So we have

$\displaystyle\operatorname{E}\left[{X_{k}}\right]$
$\displaystyle=\frac{1}{k(k-1)}\sum_{i\neq j}\left\lvert i-j\right\rvert$
$\displaystyle=\frac{1}{k(k-1)}\left(\sum_{1\leq i<j\leq k}(j-i)+\sum_{1\leq
j<i\leq k}(i-j)\right)$ $\displaystyle=\frac{2}{k(k-1)}\sum_{1\leq i<j\leq
k}(j-i)$ $\displaystyle=\frac{2}{k(k-1)}\sum_{j=1}^{k}\sum_{\ell=1}^{j-1}\ell$
$\displaystyle=\frac{2}{k(k-1)}\sum_{j=1}^{k}\frac{j(j-1)}{2}$
$\displaystyle=\frac{1}{k(k-1)}\sum_{j=1}^{k}j(j-1).$
$\displaystyle=\frac{1}{k(k-1)}\sum_{j=1}^{k}\left(j^{2}-j\right)$
$\displaystyle=\frac{1}{k(k-1)}\cdot\left(\frac{(2k+1)k(k+1)}{6}-\frac{k}{k+1}{2}\right)$
$\displaystyle=\frac{1}{k(k-1)}\cdot\frac{(2k-2)k(k+1)}{6}$
$\displaystyle=\frac{k+1}{3}.$

This is such a simple result that we might reasonably expect that there is a
faster way to get it, and we’d be right. A standard trick is to observe that
we can simulate choosing $k$ points uniformly at random from a line of $n$
points by instead choosing $k+1$ points uniformly at random from a cycle of
$n+1$ points, and deleting the first point chosen to turn the cycle back into
a line. In the cycle, symmetry implies that the expected distance between each
point and its successor is the same as for any other point; there are $k+1$
such distances, and they add up to $n+1$, so each expected distance is exactly
$\frac{n+1}{k+1}$.

In our particular case, $n$ (in the formula) is $k$ and $k$ (in the formula)
is $2$, so we get $\frac{k+1}{3}$. Note we are sweeping the whole absolute
value thing under the carpet here, so maybe the more explicit derivation is
safer.

However we arrive at $\operatorname{E}\left[{X_{k}}\right]=\frac{k+1}{3}$ (for
$k>1$), we can sum these expectations to get our total expected cost:

$\displaystyle\operatorname{E}\left[{\sum_{k=2}^{n}X_{k}}\right]$
$\displaystyle=\sum_{k=2}^{n}\operatorname{E}\left[{X_{k}}\right]$
$\displaystyle=\sum_{k=2}^{n}\frac{k+1}{3}$
$\displaystyle=\frac{1}{3}\sum_{\ell=3}^{n+1}\ell$
$\displaystyle=\frac{1}{3}\left(\frac{(n+1)(n+2)}{2}-3\right)$
$\displaystyle=\frac{(n+1)(n+2)}{6}-1.$

It’s probably worth checking a few small cases to see that this answer
actually makes sense.

For large $n$, this shows that the doubly-linked list wins, but not by much:
we get roughly $n^{2}/6$ instead of $n^{2}/4$. This is a small enough
difference that in practice it is probably dominated by other constant-factor
differences that we have neglected.

####  C.1.3 Parallel graph coloring

Consider the following algorithm for assigning one of $k$ colors to each node
in a graph with $m$ edges:

  1. 1.

Assign each vertex $u$ a color $c_{u}$, chosen uniformly at random from all
$k$ possible colors.

  2. 2.

For each vertex $u$, if $u$ has a neighbor $v$ with $c_{u}=c_{v}$, assign $u$
a new color $c^{\prime}_{u}$, again chosen uniformly at random from all $k$
possible colors. Otherwise, let $c^{\prime}_{u}=c_{u}$.

Note that any new colors $c^{\prime}$ do not affect the test $c_{u}=c_{v}$. A
node changes its color only if it has the same original color as the original
color of one or more of its neighbors.

Suppose that we run this algorithm on an $r$-regular111Every vertex has
exactly $r$ neighbors. triangle-free222There are no vertices $u$, $v$, and $w$
such that all are neighbors of each other. graph. As a function of $k$, $r$,
and $m$, give an exact closed-form expression for the expected number of
monochromatic333Both endpoints have the same color. edges after running both
steps of the algorithm.

##### Solution

We can use linearity of expectation to compute the probability that any
particular edge is monochromatic, and then multiply by $m$ to get the total.

Fix some edge $uv$. If either of $u$ or $v$ is recolored in step 2, then the
probability that $c^{\prime}_{u}=c^{\prime}_{v}$ is exactly $1/k$. If neither
is recolored, the probability that $c^{\prime}_{u}=c^{\prime}_{v}$ is zero
(otherwise $c_{u}=c_{v}$, forcing both to be recolored). So we can calculate
the probability that $c^{\prime}_{u}=c^{\prime}_{v}$ by conditioning on the
event $A$ that neither vertex is recolored.

This event occurs if both $u$ and $v$ have no neighbors with the same color.
The probability that $c_{u}=c_{v}$ is $1/k$. The probability that any
particular neighbor $w$ of $u$ has $c_{w}=c_{u}$ is also $1/k$; similarly for
any neighbor $w$ of $v$. These events are all independent on the assumption
that the graph is triangle-free (which implies that no neighbor of $u$ is also
a neighbor of $v$). So the probability that none of these $2r-1$ events occur
is $(1-1/k)^{2r-1}$.

We then have

$\displaystyle\Pr\left[{c_{u}=c_{v}}\right]$
$\displaystyle=\Pr\left[{c_{u}=c_{v}}\;\middle|\;{\overline{A}}\right]\Pr\left[{\overline{A}}\right]+\Pr\left[{c_{u}=c_{v}}\;\middle|\;{A}\right]\Pr\left[{A}\right]$
$\displaystyle=\frac{1}{k}\cdot\left(1-\left(1-\frac{1}{k}\right)^{2r-1}\right).$

Multiply by $m$ to get

$\frac{m}{k}\cdot\left(1-\left(1-\frac{1}{k}\right)^{2r-1}\right).$

For large $k$, this is approximately
$\frac{m}{k}\cdot\left(1-e^{-(2r-1)/k}\right)$, which is a little bit better
than than the $\frac{m}{k}$ expected monochrome edges from just running step
1.

Repeated application of step 2 may give better results, particular if $k$ is
large relative to $r$. We will see this technique applied to a more general
class of problems in §11.3.5.

###  C.2 Assignment 2: due Wednesday, 2014-09-24, at 17:00

####  C.2.1 Load balancing

Suppose we distribute $n$ processes independently and uniformly at random
among $m$ machines, and pay a communication cost of $1$ for each pair of
processes assigned to different machines. Let $C$ be the total communication
cost, that is, the number of pairs of processes assigned to different
machines. What is the expectation and variance of $C$?

##### Solution

Let $C_{ij}$ be the communication cost between machines $i$ and $j$. This is
just an indicator variable for the event that $i$ and $j$ are assigned to
different machines, which occurs with probability $1-\frac{1}{m}$. We have
$C=\sum_{1\leq i<j\leq n}C_{ij}$.

  1. 1.

Expectation is a straightforward application of linearity of expectation.
There are $\binom{n}{2}$ pairs of processes, and
$\operatorname{E}\left[{C_{ij}}\right]=1-\frac{1}{m}$ for each pair, so

$\operatorname{E}\left[{C}\right]=\binom{n}{2}\left(1-\frac{1}{m}\right).$

  2. 2.

Variance is a little trickier because the $C_{ij}$ are not independent. But
they are pairwise independent: even if we fix the location of $i$ and $j$, the
expectation of $C_{jk}$ is still $1-\frac{1}{m}$, so
$\operatorname{Cov}\left[{C_{ij}},{C_{jk}}\right]=\operatorname{E}\left[{C_{ij}C_{jk}}\right]-\operatorname{E}\left[{C_{ij}}\right]\cdot\operatorname{E}\left[{C_{jk}}\right]=0$.
So we can compute

$\operatorname{Var}\left[{C}\right]=\sum_{1\leq
i<j<n}\operatorname{Var}\left[{C_{ij}}\right]=\binom{n}{2}\frac{1}{m}\left(1-\frac{1}{m}\right).$

####  C.2.2 A missing hash function

A clever programmer inserts $X_{i}$ elements in each of $m$ buckets in a hash
table, where each bucket $i$ is implemented as a balanced binary search tree
with search cost at most $\lceil\lg(X_{i}+1)\rceil$. We are interested in
finding a particular target element $x$, which is equally likely to be in any
of the buckets, but we don’t know what the hash function is.

Suppose that we know that the $X_{i}$ are independent and identically
distributed with $\operatorname{E}\left[{X_{i}}\right]=k$, and that the
location of $x$ is independent of the values of the $X_{i}$. What is best
upper bound we can put on the expected cost of finding $x$?

##### Solution

The expected cost of searching bucket $i$ is
$\operatorname{E}\left[{\lceil\lg(X_{i}+1)\rceil}\right]$. This is the
expectation of a function of $X_{i}$, so we would like to bound it using
Jensen’s inequality (§4.3).

Unfortunately the function $f(n)=\lceil\lg(n+1)\rceil$ is not concave (because
of the ceiling), but $1+\lg(n+1)>\lceil\lg(n+1)\rceil$ is. So the expected
cost of searching bucket $i$ is bounded by
$1+\lg(\operatorname{E}\left[{X_{i}}\right]+1)=1+\lg(k+1)$.

Assuming we search the buckets in some fixed order until we find $x$, we will
search $Y$ buckets where $\operatorname{E}\left[{Y}\right]=\frac{n+1}{2}$.
Because $Y$ is determined by the position of $x$, which is independent of the
$X_{i}$, $Y$ is also independent of the $X_{i}$. So Wald’s equation (3.4.3)
applies, and the total cost is bounded by

$\frac{n+1}{2}\left(1+\lg(k+1)\right).$

###  C.3 Assignment 3: due Wednesday, 2014-10-08, at 17:00

####  C.3.1 Tree contraction

Suppose that you have a tree data structure with $n$ nodes, in which each node
$i$ has a pointer $\textnormal{{{}parent}}(u)$ to its parent (or itself, in
the case of the root node root).

Consider the following randomized algorithm for shrinking paths in the tree:
in the first phase, each node $u$ first determines its parent
$v=\textnormal{{{}parent}}(u)$ and its grandparent
$w=\textnormal{{{}parent}}(\textnormal{{{}parent}}(u))$. In the second phase,
it sets $\textnormal{{{}parent}}^{\prime}(u)$ to $v$ or $w$ according to a
fair coin-flip independent of the coin-flips of all the other nodes.

Let $T$ be the tree generated by the parent pointers and $T^{\prime}$ the tree
generated by the $\textnormal{{{}parent}}^{\prime}$ pointers. An example of
two such trees is given in Figure C.1.

0123456 |  0124365
---|---
Figure C.1: Example of tree contraction for Problem C.3.1. Tree $T$ is on the
left, $T^{\prime}$ on the right. Nodes $1$, $3$, $5$, and $6$ (in boldface)
switch to their grandparents. The other nodes retain their original parents.

Recall that the depth of a node is defined by
$\operatorname{depth}(\textnormal{{{}root}})=0$ and
$\operatorname{depth}(u)=1+\operatorname{depth}(\textnormal{{{}parent}}(u))$
when $u\neq\textnormal{{{}root}}$. The depth of a tree is equal to the maximum
depth of any node.

Let $D$ be depth of $T$, and $D^{\prime}$ be the depth of $T^{\prime}$. Show
that there is a constant $a$, such that for any fixed $c>0$, with probability
at least $1-n^{-c}$ it holds that

$a\cdot D-O\left(\sqrt{D\log n}\right)\leq D^{\prime}\leq a\cdot
D+O\left(\sqrt{D\log n}\right).$ (C.3.1)

##### Solution

For any node $u$, let $\operatorname{depth}(u)$ be the depth of $u$ in $T$ and
$\operatorname{depth}^{\prime}(u)$ be the depth of $u$ in $T^{\prime}$. Note
that $\operatorname{depth}^{\prime}(u)$ is a random variable. We will start by
computing $\operatorname{E}\left[{\operatorname{depth}^{\prime}(u)}\right]$ as
a function of $\operatorname{depth}(u)$, by solving an appropriate recurrence.

Let $S(k)=\operatorname{depth}^{\prime}(u)$ when $\operatorname{depth}(u)=k$.
The base cases are $S(0)=0$ (the depth of the root never changes) and $S(1)=1$
(same for the root’s children). For larger $k$, we have

$\displaystyle\operatorname{E}\left[{\operatorname{depth}^{\prime}(u)}\right]$
$\displaystyle=\frac{1}{2}\operatorname{E}\left[{1+\operatorname{depth}^{\prime}(\textnormal{{{}parent}}(u))}\right]+\frac{1}{2}\operatorname{E}\left[{1+\operatorname{depth}^{\prime}(\textnormal{{{}parent}}(\textnormal{{{}parent}}(u)))}\right]$
or $\displaystyle S(k)$ $\displaystyle=1+\frac{1}{2}S(k-1)+\frac{1}{2}S(k-2).$

There are various ways to solve this recurrence. The most direct may be to
define a generating function $F(z)=\sum_{k=0}^{\infty}S(k)z^{k}$. Then the
recurrence becomes

$F=\frac{z}{1-z}+\frac{1}{2}zF+\frac{1}{2}z^{2}F.$

Solving for $F$ gives

$\displaystyle F$
$\displaystyle=\frac{\frac{z}{1-z}}{1-\frac{1}{2}z-\frac{1}{2}z^{2}}$
$\displaystyle=\frac{2z}{(1-z)(2-z-z^{2})}.$
$\displaystyle=\frac{2z}{(1-z)^{2}(2+z)}$
$\displaystyle=2z\left(\frac{1/3}{(1-z)^{2}}+\frac{1/9}{(1-z)}+\frac{1/18}{1+\frac{1}{2}z}\right)$
$\displaystyle=\frac{2}{3}\cdot\frac{z}{(1-z)^{2}}+\frac{2}{9}\cdot\frac{z}{1-z}+\frac{1}{9}\cdot\frac{z}{1+\frac{1}{2}z},$
from which we can read off the exact solution $\displaystyle S(k)$
$\displaystyle=\frac{2}{3}\cdot
k+\frac{2}{9}+\frac{1}{9}\left(-\frac{1}{2}\right)^{k-1}$

when $k\geq 1$.444A less direct but still effective approach is to guess that
$S(k)$ grows linearly, and find $a$ and $b$ such that $S(k)\leq ak+b$. For
this we need $ak+b\leq 1+\frac{1}{2}(a(k-1)+b)+\frac{1}{2}(a(k-2)+b)$. The
$b$’s cancel, leaving $ak\leq 1+ak-\frac{3}{2}a$. Now the $ak$’s cancel,
leaving us with $0\leq 1-\frac{3}{2}a$ or $a\geq 2/3$. We then go back and
make $b=1/3$ to get the right bound on $S(1)$, giving the bound