1 Probability and Computing 1.3 Moments and Deviations 1.5 Balls, Bins, and Random Graphs

1.4 Chernoff and Hoeffding Bounds

Exercise 1.4.1 (Exercise 4.9 [MU17]).

Suppose that we can obtain independent samples $\{X_{i}\}_{i\in[1,n]}$ of a random variable $X$ and that we want to use these samples to estimate $\operatorname*{\mathbb{E}}\left[X\right]$ . Using $t$ samples, we use $(\sum_{i\in[1,t]}X_{i})/t$ for our estimate of $\operatorname*{\mathbb{E}}\left[X\right]$ . We want the estimate to be within $\varepsilon\operatorname*{\mathbb{E}}\left[X\right]$ from the true value of $\operatorname*{\mathbb{E}}\left[X\right]$ with probability at least $1-\delta$ . We may not be able to use Chernoff’s bound directly to bound how good our estimate is if $X$ is not a 0-1 random variable, and we do not know its moment generating function. We develop an alternative approach that requires only having a bound on the variance of $X$ . Let $r=\sqrt{\mathrm{Var}\left[X\right]}/\operatorname*{\mathbb{E}}\left[X\right]$ .

•

Show using Chebyshev’s inequality that $O(r^{2}/\varepsilon^{2}\delta)$ samples are sufficient to solve the problem.
•

Suppose that we need only a weak estimate that is within $\varepsilon\operatorname*{\mathbb{E}}\left[X\right]$ of $\operatorname*{\mathbb{E}}\left[X\right]$ with probability at least $3/4$ . Argue that $O(r^{2}/\varepsilon^{2})$ samples are enough for this weak estimate.
•

Show that, by taking the median of $O(\log(1/\delta))$ independent weak estimates, we can obtain an estimate within $\varepsilon\operatorname*{\mathbb{E}}\left[X\right]$ of $\operatorname*{\mathbb{E}}\left[X\right]$ with probability at least $1-\delta$ . Conclude that we need only $O((r^{2}\log(1/\delta))/\varepsilon^{2})$ samples.

Proof.

Let $Y=\sum_{i\in[1,t]}X_{i}$ , then $\operatorname*{\mathbb{E}}\left[Y\right]=t\cdot\operatorname*{\mathbb{E}}\left% [X\right]$ and $\mathrm{Var}\left[Y\right]=\mathrm{Var}[\sum_{i\in[1,t]}X_{i}]=t\cdot\mathrm{% Var}\left[X\right]$ .

By Chebyshev’s inequality,

	$\displaystyle\Pr\left[\left\|\frac{1}{t}\cdot Y-\operatorname{\mathbb{E}}\left% [X\right]\right\|\geq\varepsilon\operatorname{\mathbb{E}}\left[X\right]\right]$	$\displaystyle=\Pr\left[\left\|Y-\operatorname{\mathbb{E}}\left[Y\right]\right\|% \geq\varepsilon\operatorname{\mathbb{E}}\left[Y\right]\right]$
		$\displaystyle\leq\frac{\mathrm{Var}\left[Y\right]}{\varepsilon^{2}% \operatorname{\mathbb{E}}\left[Y\right]^{2}}=\frac{\mathrm{Var}\left[X\right]% }{t\varepsilon^{2}\operatorname{\mathbb{E}}\left[X\right]^{2}}=\frac{r^{2}}{t% \varepsilon^{2}}\leq\delta.$

Now that $t\geq r^{2}/\delta\varepsilon^{2}$ , thus $t=O(r^{2}/\delta\varepsilon^{2})$ .

Suppose $\delta\leq 1/4$ , then $t\geq 4r^{2}/\varepsilon^{2}$ , and thus $t=O(r^{2}/\varepsilon^{2})$ .

When it comes to using a median of $s$ weak estimates to boost the confidence in estimation, we have a trick called Median of Mean (MoM) [JVV86]. The key idea is to take advantage of the “structure” of median value, that half of the weak estimates are smaller, while the other half are greater.

Since we hope with probability at least $1-\delta$ , the median of weak estimates is within $\varepsilon\operatorname*{\mathbb{E}}\left[X\right]$ range, then we say the bad event is the median of weak estimates is out of $\varepsilon\operatorname*{\mathbb{E}}\left[X\right]$ range. Equivalently, a bad event occurs when more than half of the weak estimates are above $(1+\varepsilon)\operatorname*{\mathbb{E}}\left[X\right]$ , or more than half of them are below $(1-\varepsilon)\operatorname*{\mathbb{E}}\left[X\right]$ .

Form each weak estimate from an independent batch of $O(r^{2}/\varepsilon^{2})$ samples, so the weak estimates are independent. In this sense, we introduce independent 0-1 random variables (indicators) $\{1_{L,i}\}_{i\in[1,s]}$ and $\{1_{R,i}\}_{i\in[1,s]}$ where

•

$1_{L,i}=1$ only when $i^{\mathrm{th}}$ weak estimate is smaller than $(1-\varepsilon)\operatorname*{\mathbb{E}}\left[X\right]$ ,
•

$1_{R,i}=1$ only when $i^{\mathrm{th}}$ weak estimate is greater than $(1+\varepsilon)\operatorname*{\mathbb{E}}\left[X\right]$ ,

and $1_{L}=\sum_{i\in[1,s]}1_{L,i}$ , $1_{R}=\sum_{i\in[1,s]}1_{R,i}$ . Since a weak estimate is within $\varepsilon\operatorname*{\mathbb{E}}\left[X\right]$ range with probability at least $3/4$ , we have both $\Pr\left[1_{L,i}=1\right]$ and $\Pr\left[1_{R,i}=1\right]$ upper bounded by $1/4$ , and thus both $\operatorname*{\mathbb{E}}\left[1_{L}\right]$ and $\operatorname*{\mathbb{E}}\left[1_{R}\right]$ are at most $s/4$ .

We first bound $1_{L}$ , and derive $1_{R}$ by symmetry. By Chernoff’s bound,

\Pr\left[1_{L}\geq\frac{s}{2}\right]\leq\operatorname*{\mathbb{E}}\left[\exp(t% \cdot 1_{L})\right]/\exp\left(\frac{s}{2}\cdot t\right)\leq\exp\left(\frac{s}{% 4}\cdot(e^{t}-1)-\frac{s}{2}\cdot t\right)=\exp(\varphi(t)).

Then we have $\varphi^{\prime}(t)=\frac{s}{4}\cdot e^{t}-\frac{s}{2}$ , and derive that $\varphi(t)$ min by $t=\ln 2$ for a positive $t$ . Now that

\exp\left(\left(\frac{1}{4}-\frac{\ln 2}{2}\right)\cdot s\right)\leq\frac{% \delta}{2},

we have $s\geq\left((\ln 2)/2-1/4\right)^{-1}\cdot\ln(2/\delta)$ , thus $s=O(\log(1/\delta))$ .

We thus conclude that we need $O(r^{2}\log(1/\delta)/\varepsilon^{2})$ samples in total. ∎

Exercise 1.4.2 (Exercise 4.12 [MU17]).

Consider a collection $\{X_{i}\}_{i\in[1,n]}$ of $n$ independent geometrically distributed random variables with mean 2. Let $X=\sum_{i\in[1,n]}X_{i}$ and $\delta>0$ .

•

Derive a bound on $\Pr\left[X\geq(1+\delta)\cdot 2n\right]$ by applying Chernoff’s bound to a sequence of $(1+\delta)\cdot 2n$ fair coin tosses.
•

Directly derive a Chernoff’s bound on $\Pr\left[X\geq(1+\delta)\cdot 2n\right]$ using the MGF for geometric random variables.
•

Compare these 2 bounds derived above.

Proof.

A way to model the “Coupon Collection” alike problem for bounding the sum of geometrically distributed random variables is transforming to an upper bound to the sum of a sequence of Bernoulli trials.

Since a geometrically distributed random variable can be seen as the number of Bernoulli trials until one success, then for event $X\geq(1+\delta)\cdot 2n$ , there are at most $n$ successes among $(1+\delta)\cdot 2n$ independent Bernoulli trials (in the worst case, the last trial must be success among $n$ successes in total $(1+\delta)\cdot 2n$ trials).

We write $Y_{i}$ as $i^{\mathrm{th}}$ independent Bernoulli trial with success probability being $1/2$ among $(1+\delta)\cdot 2n$ trials, we write $Y=\sum_{i\in[1,(1+\delta)\cdot 2n]}Y_{i}$ , and $\operatorname*{\mathbb{E}}[Y]=(1+\delta)\cdot n$ . We thus can upper bound $\Pr[X\geq(1+\delta)\cdot 2n]$ by $\Pr\left[Y\leq n\right]$ , as we can loosen the boundary condition on the worst case, where last trial must be successful among $n$ successes.

By Chernoff’s bound for bounding the deviation below the mean, we have

	$\displaystyle\Pr[X\geq(1+\delta)\cdot 2n]$	$\displaystyle\leq\Pr\left[Y\leq n\right]$
		$\displaystyle\leq\frac{\operatorname*{\mathbb{E}}[\exp(tY)]}{\exp(n\cdot t)}$
		$\displaystyle\leq\frac{\exp((1+\delta)\cdot n\cdot(e^{t}-1))}{\exp(n\cdot t)}$
		$\displaystyle=\exp((1+\delta)\cdot n\cdot(e^{t}-1)-n\cdot t)=\exp(\varphi(t))$

with $t<0$ , and min by $t=-\ln(1+\delta)$ deriving a upper bound $((1+\delta)\cdot e^{-\delta})^{n}$ .

If we brute force for a bound on $X=\sum_{i\in[1,n]}X_{i}$ , the MGF of $X_{i}$ is $M_{X_{i}}(t)=\sum_{k\geq 1}\exp(kt)\cdot 2^{-k}=\sum_{k\geq 1}(e^{t}/2)^{k}$ . When $0<t<\ln 2$ , $M_{X_{i}}(t)=e^{t}/(2-e^{t})$ . Again by Chernoff’s bound for bounding the deviation above the mean,

	$\displaystyle\Pr\left[X\geq(1+\delta)\cdot 2n\right]$	$\displaystyle\leq\left(\frac{M_{X_{i}}(t)}{\exp((1+\delta)\cdot 2t)}\right)^{n}$
		$\displaystyle=\left((2-e^{t})\exp((2\delta+1)\cdot t)\right)^{-n}$
		$\displaystyle=\left(2\exp((2\delta+1)\cdot t)-\exp((2\delta+2)\cdot t)\right)^% {-n}=\varphi(t)^{-n},$

and $\varphi^{\prime}(t)=(4\delta+2)\exp((2\delta+1)\cdot t)-(2\delta+2)\exp((2% \delta+2)\cdot t)$ , and thus $\varphi(t)$ max by $t=\ln(2\delta+1)-\ln(\delta+1)$ ,

\Pr\left[X\geq(1+\delta)\cdot 2n\right]\leq\left(\frac{1}{\delta+1}\cdot\left(% \frac{2\delta+1}{\delta+1}\right)^{2\delta+1}\right)^{-n}=\left((1+\delta)% \cdot\left(\frac{\delta+1}{2\delta+1}\right)^{2\delta+1}\right)^{n}.

By section 1.5.1, we know the first one is looser. ∎

Exercise 1.4.3 (Exercise 4.8 [MU17]).

We show how to construct a random permutation $\pi$ on $[1,n]$ , given a black box that outputs numbers independently and uniformly at random from $[1,k]$ where $k\geq n$ . If we compute a function $f:[1,n]\to[1,k]$ with $f(i)\neq f(j)$ for $i\neq j$ , this yields a permutation, by outputting $[1,n]$ according to the order of $\{f(i)\}_{i\in[1,n]}$ . To construct such a function $f$ , do the following for $i\in[1,n]$ : choose $f(i)$ by repeatedly drawing number from the black box and set $f(i)$ to the first number that is $f(i)\neq f(j)$ for $j<i$ .

Prove that this approach gives a permutation chosen uniformly at random for all permutations. Find the expected number of calls to the black box that are needed when $k=n$ and $k=2n$ . For the case $k=2n$ , argue that the probability that each call to the black box assigns a value of $f(j)$ to some $j$ is at least $1/2$ . Based on this, use a Chernoff bound to bound the probability that the number of calls to the black box is at least $4n$ .

Proof.

At the first sight, this is a “Coupon Collection” problem, where we can introduce $n$ independent geometrically distributed random variables $\{X_{i}\}_{i\in[1,n]}$ each with success probability $p_{i}=(k+1-i)/k$ , and we write $X=\sum_{i\in[1,n]}X_{i}$ . When $k=2n$ , each $p_{i}\geq 1/2$ as $p_{n}=(n+1)/2n$ .

For expectation of $X$ , $\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i\in[1,n]}\operatorname*{% \mathbb{E}}[X_{i}]$ by linearity of expectation. For $\operatorname*{\mathbb{E}}\left[X_{i}\right]$ , by conditional expectation and memoryless of geometric distribution,

	$\displaystyle\operatorname*{\mathbb{E}}\left[X_{i}\right]$	$\displaystyle=\operatorname{\mathbb{E}}\left[X_{i}\mid X_{i,0}=1\right]\cdot% \Pr\left[X_{i,0}=1\right]+\operatorname{\mathbb{E}}\left[X_{i}\mid X_{i,0}=0% \right]\cdot\Pr\left[X_{i,0}=0\right]$
		$\displaystyle=1\cdot p_{i}+\left(1+\operatorname*{\mathbb{E}}\left[X_{i}\right% ]\right)\cdot\left(1-p_{i}\right),$

$\operatorname*{\mathbb{E}}\left[X_{i}\right]=p_{i}^{-1}=k/(k-i+1)$ . Thus $\operatorname*{\mathbb{E}}\left[X\right]=n\ln n+\Theta(n)$ when $k=n$ , $\operatorname*{\mathbb{E}}\left[X\right]=2n(\ln 2n-\ln n)+\Theta(n)$ when $k=2n$ .

For upper bounding $\Pr\left[X\geq 4n\right]$ , we first upper bound by $\Pr\left[Y\geq 4n\right]$ , where $\{Y_{i}\}_{i\in[1,n]}$ are $n$ independent geometrically distributed random variables, each with success probability $1/2$ , and we write $Y=\sum_{i\in[1,n]}Y_{i}$ . Then we upper bound $\Pr\left[Y\geq 4n\right]$ by $\Pr\left[Z\leq n\right]$ through the previous trick of turning sum of geometrically distributed random variables into sum of a sequence of Bernoulli trials. We introduce $4n$ independent Bernoulli distributed random variables $\{Z_{i}\}_{i\in[1,4n]}$ with $\Pr\left[Z_{i}=1\right]=1/2$ , and we write $Z=\sum_{i\in[1,4n]}Z_{i}$ .

By Chernoff’s bound, we have

	$\displaystyle\Pr\left[X\geq 4n\right]$	$\displaystyle\leq\Pr\left[Y\geq 4n\right]$
		$\displaystyle\leq\Pr\left[Z\leq n\right]$
		$\displaystyle\leq\exp(2n(e^{t}-1)-nt)=\exp(\varphi(t)),$

with $\varphi(t)$ min at $t=-\ln 2$ , thus derives an upper bound by $(2/e)^{n}$ . ∎

Exercise 1.4.4 (Exercise 4.13 [MU17]).

Let $\{X_{i}\}_{i\in[1,n]}$ be independent Poisson trials such that $\Pr\left[X_{i}=1\right]=p$ . Let $X=\sum_{i\in[1,n]}X_{i}$ so that $\operatorname*{\mathbb{E}}\left[X\right]=pn$ . Let

F(x,p)=x\ln\frac{x}{p}+(1-x)\ln\frac{1-x}{1-p}.

•

Show that, for $1\geq x>p$ ,

$\Pr\left[X\geq xn\right]\leq e^{-nF(x,p)}.$
•

Show that, when $0<x,p<1$ , we have $F(x,p)-2(x-p)^{2}\geq 0$ .
•

Argue that

$\displaystyle\Pr\left[X\geq(p+\varepsilon)n\right]$ $\displaystyle\leq e^{-2n\varepsilon^{2}},$

$\displaystyle\Pr\left[X\leq(p-\varepsilon)n\right]$ $\displaystyle\leq e^{-2n\varepsilon^{2}},$

$\displaystyle\Pr\left[\left|X-pn\right|\geq\varepsilon n\right]$ $\displaystyle\leq 2e^{-2n\varepsilon^{2}}.$

Proof.

For Chernoff’s bound on $\Pr[X_{i}\geq x]$ , we typically turn to $1+kx\leq e^{kx}$ for $k>0$ , then

	$\displaystyle\frac{\operatorname*{\mathbb{E}}\left[\exp(tX_{i})\right]}{\exp(% xt)}$	$\displaystyle=\frac{p\cdot e^{t}+1-p}{\exp(xt)}=\frac{1+p\cdot(e^{t}-1)}{\exp(% xt)}$
		$\displaystyle\leq\exp(p\cdot(e^{t}-1)-xt)=\exp(\varphi(t)),$

to derive an upper bound by choosing $t$ . A different bound can be derived by avoiding the trick we often apply,

\frac{\operatorname*{\mathbb{E}}\left[\exp(tX_{i})\right]}{\exp(xt)}=p\cdot% \exp((1-x)\cdot t)+(1-p)\cdot\exp(-xt)=\varphi(t),

then we have

\varphi^{\prime}(t)=p(1-x)\cdot\exp((1-x)\cdot t)-x(1-p)\cdot\exp(-xt).

When $t=\ln(1-p)+\ln x-\ln(1-x)-\ln p>0$ , $\varphi(t)$ min by

	$\displaystyle\min_{t}\varphi(t)$	$\displaystyle=p\cdot\left(\frac{(1-p)x}{(1-x)p}\right)^{1-x}+(1-p)\cdot\left(% \frac{(1-p)x}{(1-x)p}\right)^{-x}$
		$\displaystyle=\left(p\cdot\frac{(1-p)x}{(1-x)p}+1-p\right)\cdot\left(\frac{(1-% p)x}{(1-x)p}\right)^{-x}$
		$\displaystyle=\frac{1-p}{1-x}\cdot\left(\frac{(1-p)x}{(1-x)p}\right)^{-x}.$

By taking $\ln$ both sides, we have

	$\displaystyle\ln\min_{t}\varphi(t)$	$\displaystyle=\ln\frac{1-p}{1-x}-x\ln\frac{(1-p)x}{(1-x)p}$
		$\displaystyle=(1-x)\ln\frac{1-p}{1-x}+x\ln\frac{p}{x}=-F(x,p),$

thus deriving a bound for $\Pr[X_{i}\geq x]\leq\exp(-F(x,p))$ . Finally, when bounding $\Pr[X\geq xn]$ ,

	$\displaystyle\Pr\left[X\geq xn\right]$	$\displaystyle\leq\frac{\operatorname*{\mathbb{E}}\left[\exp(tX)\right]}{\exp(% xnt)}$
		$\displaystyle=\frac{\prod_{i\in[1,n]}\operatorname{\mathbb{E}}\left[\exp(tX_{% i})\right]}{\exp(xnt)}=\left(\frac{\operatorname{\mathbb{E}}\left[\exp(tX_{i}% )\right]}{\exp(xt)}\right)^{n}$
		$\displaystyle\leq\exp(-nF(x,p)).$

Taking partial derivative against $x$ in $F(x,p)$ , we have

\frac{\partial}{\partial x}F(x,p)=\ln\frac{x}{p}+x\cdot\frac{p}{x}\cdot\frac{1% }{p}-\ln\frac{1-x}{1-p}+(1-x)\cdot\frac{1-p}{1-x}\cdot\frac{-1}{1-p}=\ln\frac{% x}{p}-\ln\frac{1-x}{1-p},

and it is $0$ when $x=p$ , taking second order partial derivative against $x$ , we have

\frac{\partial^{2}}{\partial x^{2}}F(x,p)=\frac{1}{x}-\frac{1-p}{1-x}\cdot% \frac{-1}{1-p}=\frac{1}{x}+\frac{1}{1-x}\geq 4,

and therefore $F(x,p)\geq F(p,p)+2(x-p)^{2}=2(x-p)^{2}$ by Taylor expansion.

We can plug in the result $F(x,p)\geq 2(x-p)^{2}$ , and derive

\Pr\left[X\geq(p+\varepsilon)n\right]\leq\exp(-nF(p+\varepsilon,p))\leq\exp(-2% n\varepsilon^{2}).

When $x<p$ and we upper bound $\Pr[X_{i}\leq x]$ , $t=\ln(1-p)+\ln x-\ln(1-x)-\ln p<0$ gives $\ln\min_{t}\varphi(t)=-F(x,p)$ , then $\Pr[X_{i}\leq x]\leq\exp(-F(x,p))$ . Thus,

\Pr\left[X\leq(p-\varepsilon)n\right]\leq\exp(-nF(p-\varepsilon,p))\leq\exp(-2% n\varepsilon^{2}).

Eventually, we derive bounds on both sides by

\Pr\left[\left|X-pn\right|\geq\varepsilon n\right]\leq 2\exp(-2n\varepsilon^{2% }).

Remark 1.4.5.

$F(x,p)$ is exactly the KL divergence [KL51] between Bernoulli distributions with parameters $x$ and $p$ .

∎

Exercise 1.4.6 (Exercise 4.14 [MU17]).

Let $\{X_{i}\}_{i\in[1,n]}$ be independent Poisson trials such that $\Pr[X_{i}]=p_{i}$ , and let $\{a_{i}\}_{i\in[1,n]}$ be real numbers in $[0,1]$ . Let $X=\sum_{i\in[1,n]}a_{i}X_{i}$ and $\mu=\operatorname*{\mathbb{E}}\left[X\right]$ . Then the following Chernoff bound holds: for any $\delta>0$ ,

\Pr\left[X\geq(1+\delta)\mu\right]\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+% \delta}}\right)^{\mu}.

Prove a similar bound for the probability that $X\leq(1-\delta)\mu$ for $0<\delta<1$ .

Proof.

By Jensen’s inequality over concave functions,

\operatorname*{\mathbb{E}}\left[\exp(ta_{i}X_{i})\right]\leq\operatorname*{% \mathbb{E}}\left[\exp(tX_{i})\right]^{a_{i}}

for all $t$ , as $f(x)=x^{a_{i}}$ is concave if $0\leq a_{i}\leq 1$ .

By Chernoff’s upper tail and lower tail bound,

	$\displaystyle\Pr\left[X_{i}\geq(1+\delta)p_{i}\right]$	$\displaystyle\leq\frac{\operatorname*{\mathbb{E}}\left[\exp(tX_{i})\right]}{% \exp((1+\delta)p_{i}\cdot t)}\leq\frac{\exp(p_{i}\cdot(e^{t}-1))}{\exp((1+% \delta)p_{i}\cdot t)},\text{ min by $t=\ln(1+\delta)>0$ by}\left(\frac{e^{% \delta}}{(1+\delta)^{1+\delta}}\right)^{p_{i}},$
	$\displaystyle\Pr\left[X_{i}\leq(1-\delta)p_{i}\right]$	$\displaystyle\leq\frac{\operatorname*{\mathbb{E}}\left[\exp(tX_{i})\right]}{% \exp((1-\delta)p_{i}\cdot t)}\leq\frac{\exp(p_{i}\cdot(e^{t}-1))}{\exp((1-% \delta)p_{i}\cdot t)},\text{ min by $t=\ln(1-\delta)<0$ by}\left(\frac{e^{-% \delta}}{(1-\delta)^{1-\delta}}\right)^{p_{i}}.$

By Chernoff’s bound and Jensen’s inequality, for upper tail bound, given $t>0$ and $\delta>0$ ,

	$\displaystyle\Pr\left[X\geq(1+\delta)\mu\right]$	$\displaystyle\leq\frac{\operatorname{\mathbb{E}}\left[\exp(tX)\right]}{\exp((% 1+\delta)\mu\cdot t)}=\prod_{i\in[1,n]}\left(\frac{\operatorname{\mathbb{E}}% \left[\exp(ta_{i}X_{i})\right]}{\exp((1+\delta)a_{i}p_{i}\cdot t)}\right)$
		$\displaystyle\leq\prod_{i\in[1,n]}\left(\frac{\operatorname*{\mathbb{E}}\left[% \exp(tX_{i})\right]}{\exp((1+\delta)p_{i}\cdot t)}\right)^{a_{i}}$
		$\displaystyle\leq\prod_{i\in[1,n]}\left(\frac{\exp(p_{i}\cdot(e^{t}-1))}{\exp(% (1+\delta)p_{i}\cdot t)}\right)^{a_{i}}=\left(\frac{\exp(e^{t}-1)}{\exp((1+% \delta)\cdot t)}\right)^{\mu},$

and right hand side is minimized by

\min_{t>0}\left(\frac{\exp(e^{t}-1)}{\exp((1+\delta)\cdot t)}\right)^{\mu}=% \left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}.

Symmetrically, for lower tail bound, given $t<0$ and $0<\delta<1$ ,

	$\displaystyle\Pr\left[X\leq(1-\delta)\mu\right]$	$\displaystyle\leq\frac{\operatorname{\mathbb{E}}\left[\exp(tX)\right]}{\exp((% 1-\delta)\mu\cdot t)}=\prod_{i\in[1,n]}\left(\frac{\operatorname{\mathbb{E}}% \left[\exp(ta_{i}X_{i})\right]}{\exp((1-\delta)a_{i}p_{i}\cdot t)}\right)$
		$\displaystyle\leq\prod_{i\in[1,n]}\left(\frac{\operatorname*{\mathbb{E}}\left[% \exp(tX_{i})\right]}{\exp((1-\delta)p_{i}\cdot t)}\right)^{a_{i}}$
		$\displaystyle\leq\prod_{i\in[1,n]}\left(\frac{\exp(p_{i}\cdot(e^{t}-1))}{\exp(% (1-\delta)p_{i}\cdot t)}\right)^{a_{i}}=\left(\frac{\exp(e^{t}-1)}{\exp((1-% \delta)\cdot t)}\right)^{\mu},$

with right hand side minimized by

\min_{t<0}\left(\frac{\exp(e^{t}-1)}{\exp((1-\delta)\cdot t)}\right)^{\mu}=% \left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\mu}.

∎

Exercise 1.4.7 (Exercise 4.7 [MU17]).

Let $X=\sum_{i\in[1,n]}X_{i}$ , where $\{X_{i}\}_{i\in[1,n]}$ are independent 0-1 random variables. Let $\mu=\operatorname*{\mathbb{E}}\left[X\right]$ . Choose any $\mu_{L}$ and $\mu_{H}$ such that $\mu_{L}\leq\mu\leq\mu_{H}$ . Then, for any $\delta>0$ ,

\Pr\left[X\geq(1+\delta)\mu_{H}\right]\leq\left(\frac{e^{\delta}}{(1+\delta)^{% 1+\delta}}\right)^{\mu_{H}}.

Similarly, for any $0<\delta<1$ ,

\Pr\left[X\leq(1-\delta)\mu_{L}\right]\leq\left(\frac{e^{-\delta}}{(1-\delta)^% {1-\delta}}\right)^{\mu_{L}}.

Proof.

The MGF of $X$ can be relaxed in following manner

\operatorname*{\mathbb{E}}\left[\exp(tX)\right]=\prod_{i\in[1,n]}\operatorname% *{\mathbb{E}}\left[\exp(tX_{i})\right]\leq\prod_{i\in[1,n]}\exp\left(p_{i}% \cdot(e^{t}-1)\right)=\exp\left(\mu\cdot(e^{t}-1)\right).

Given $\mu_{L}\leq\mu\leq\mu_{H}$ ,

•

When $t>0$ , $\exp\left(\mu\cdot(e^{t}-1)\right)\leq\exp\left(\mu_{H}\cdot(e^{t}-1)\right)$ .
•

When $t<0$ , $\exp\left(\mu\cdot(e^{t}-1)\right)\leq\exp\left(\mu_{L}\cdot(e^{t}-1)\right)$ .

Then for upper tail with $t>0$ and $\delta>0$ ,

\Pr\left[X\geq(1+\delta)\mu_{H}\right]\leq\frac{\exp(\mu\cdot(e^{t}-1))}{\exp(% (1+\delta)\mu_{H}\cdot t)}\leq\frac{\exp(\mu_{H}\cdot(e^{t}-1))}{\exp((1+% \delta)\mu_{H}\cdot t)}=\left(\frac{\exp\left(e^{t}-1\right)}{\exp\left((1+% \delta)\cdot t\right)}\right)^{\mu_{H}},

the right hand side is minimized by

\min_{t>0}\left(\frac{\exp(e^{t}-1)}{\exp((1+\delta)\cdot t)}\right)^{\mu_{H}}% =\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu_{H}}.

For lower tail with $t<0$ and $0<\delta<1$ ,

\Pr\left[X\leq(1-\delta)\mu_{L}\right]\leq\frac{\exp(\mu\cdot(e^{t}-1))}{\exp(% (1-\delta)\mu_{L}\cdot t)}\leq\frac{\exp(\mu_{L}\cdot(e^{t}-1))}{\exp((1-% \delta)\mu_{L}\cdot t)}=\left(\frac{\exp\left(e^{t}-1\right)}{\exp\left((1-% \delta)\cdot t\right)}\right)^{\mu_{L}},

the right hand side is minimized by

\min_{t<0}\left(\frac{\exp(e^{t}-1)}{\exp((1-\delta)\cdot t)}\right)^{\mu_{L}}% =\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\mu_{L}}.

Moreover, for lower tail bound,

\Pr\left[X\leq(1-\delta)\mu_{L}\right]\leq\Pr\left[X\leq(1-\delta)\mu\right]% \leq\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\mu}\leq\left(% \frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\mu_{L}}.

The first inequality holds from $\mu_{L}\leq\mu$ , the second one holds from Chernoff’s bound, and the third one holds from the fact that for $0<\delta<1$ ,

\frac{e^{-\delta}}{\left(1-\delta\right)^{1-\delta}}\leq\exp\left(-\frac{% \delta^{2}}{2}\right)\leq 1.

This chain of inequality comes in handy when we cannot compute the exact expectation, yet we can still derive a lower bound for the expectation, and give a looser version of tail bound. The sandwiched inequality chain can even be applied with previous weighted version of Chernoff bound with weights $\{a_{i}\}_{i\in[1,n]}$ in $(0,1)$ . ∎

1.4.1 Hoeffding’s Bound

Hoeffding’s bound says that a sum of independent bounded random variables concentrates around the sum of their expectations. The probability of being far deacays exponentially fast in the squared deviation, namely $\exp\left(-O(\varepsilon^{2})\right)$ .

Lemma 1.4.8 (Hoeffding’s Lemma [Hoe63]).

Let $X$ be a random variable with $X\in[a,b]$ and $\operatorname*{\mathbb{E}}\left[X\right]=0$ , then for any $\lambda$ ,

\operatorname*{\mathbb{E}}\left[\exp\left(\lambda X\right)\right]\leq\exp\left% (\frac{\lambda^{2}(b-a)^{2}}{8}\right).

Proof.

Since $f(x)=\exp\left(\lambda x\right)$ is convex, then

f\left(\alpha a+(1-\alpha)b\right)\leq\alpha f(a)+(1-\alpha)f(b).

For $x\in[a,b]$ , let $x=\alpha a+(1-\alpha)b$ , then $\alpha=(b-x)/(b-a)$ .

Since $\operatorname*{\mathbb{E}}\left[X\right]=0$ , then by linearity of expectation,

\operatorname*{\mathbb{E}}\left[\exp\left(\lambda X\right)\right]\leq% \operatorname*{\mathbb{E}}\left[\frac{b-X}{b-a}\exp\left(\lambda a\right)+% \frac{X-a}{b-a}\exp\left(\lambda b\right)\right]=\frac{b}{b-a}\exp\left(% \lambda a\right)-\frac{a}{b-a}\exp\left(\lambda b\right).

Let $\theta=-a/(b-a)\in[0,1]$ , and

\varphi(t)=-\theta t+\ln\left(1-\theta+\theta\exp(t)\right),

then when $t=\lambda(b-a)$ ,

	$\displaystyle\exp\left(\varphi\left(\lambda\left(b-a\right)\right)\right)$	$\displaystyle=\exp\left(-\theta\lambda\left(b-a\right)\right)\cdot\left(1-% \theta+\theta\exp\left(\lambda(b-a)\right)\right)$
		$\displaystyle=\left(1-\theta\right)\cdot\exp\left(-\theta\lambda(b-a)\right)+% \theta\cdot\exp\left((1-\theta)\lambda(b-a)\right)$
		$\displaystyle=(1-\theta)\cdot\exp\left(\lambda a\right)+\theta\cdot\exp\left(% \lambda b\right)$
		$\displaystyle=\frac{b}{b-a}\exp\left(\lambda a\right)-\frac{a}{b-a}\exp\left(% \lambda b\right).$

Since $\varphi(0)=0$ ,

\varphi^{\prime}(t)=-\theta+\frac{\theta\exp(t)}{1-\theta+\theta\exp(t)}

means $\varphi^{\prime}(0)=0$ , and

\varphi^{\prime\prime}(t)=\frac{\theta\exp(t)}{1-\theta+\theta\exp(t)}-\left(% \frac{\theta\exp(t)}{1-\theta+\theta\exp(t)}\right)^{2}\leq\frac{1}{4}.

By the Taylor expansion and the Taylor remainder theorem in Lagrange form, there is $t^{\prime}$ between $0$ and $t$ such that

\varphi(t)=\varphi(0)+\varphi^{\prime}(0)\cdot t+\frac{\varphi^{\prime\prime}(% t^{\prime})}{2}\cdot t^{2}\leq\frac{t^{2}}{8}.

Therefore,

\operatorname*{\mathbb{E}}\left[\exp\left(\lambda X\right)\right]\leq\exp\left% (\varphi\left(\lambda(b-a)\right)\right)\leq\exp\left(\frac{\lambda^{2}(b-a)^{% 2}}{8}\right).

∎

Theorem 1.4.9 (Hoeffding’s Bound [Hoe63]).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that for all $1\leq i\leq n$ , $\operatorname*{\mathbb{E}}\left[X_{i}\right]=\mu$ and $X_{i}\in[a,b]$ . Then

\Pr\left[\left|\frac{1}{n}\sum_{i\in[1,n]}X_{i}-\mu\right|\geq\varepsilon% \right]\leq 2\exp\left(-\frac{2n\varepsilon^{2}}{(b-a)^{2}}\right).

Proof.

Let $Z_{i}=(X_{i}-\mu)/n$ , then $\operatorname*{\mathbb{E}}\left[Z_{i}\right]=0$ and $Z_{i}\in[(a-\mu)/n,(b-\mu)/n]$ for $i\in[1,n]$ . Let $Z=\sum_{i\in[1,n]}Z_{i}$ . For $\lambda\geq 0$ ,

	$\displaystyle\Pr\left[Z\geq\varepsilon\right]$	$\displaystyle=\Pr\left[\exp\left(\lambda Z\right)\geq\exp\left(\lambda% \varepsilon\right)\right]$
		$\displaystyle\leq\frac{1}{\exp\left(\lambda\varepsilon\right)}\cdot% \operatorname{\mathbb{E}}\left[\exp\left(\lambda Z\right)\right]=\frac{1}{% \exp\left(\lambda\varepsilon\right)}\cdot\prod_{i\in[1,n]}\operatorname{% \mathbb{E}}\left[\exp\left(\lambda Z_{i}\right)\right]$
		$\displaystyle\leq\frac{1}{\exp\left(\lambda\varepsilon\right)}\cdot\left(\exp% \left(\frac{\lambda^{2}(b-a)^{2}}{8n^{2}}\right)\right)^{n}=\exp\left(\frac{(b% -a)^{2}}{8n}\cdot\lambda^{2}-\varepsilon\cdot\lambda\right)$
		$\displaystyle\leq\exp\left(-\frac{2n\varepsilon^{2}}{(b-a)^{2}}\right),$

where the second inequality is from Markov inequality over MGF, the third equality is from $X_{1},\ldots$ being independent, the fourth inequality is from lemma 1.4.8, and the last inequality is by minimizing at $\lambda=4n\varepsilon/(b-a)^{2}$ .

The lower bound argument is similar, for $\lambda<0$ ,

	$\displaystyle\Pr\left[Z\leq-\varepsilon\right]$	$\displaystyle=\Pr\left[\exp\left(\lambda Z\right)\geq\exp\left(-\lambda% \varepsilon\right)\right]$
		$\displaystyle\leq\frac{1}{\exp\left(-\lambda\varepsilon\right)}\cdot% \operatorname{\mathbb{E}}\left[\exp\left(\lambda Z\right)\right]=\exp\left(% \lambda\varepsilon\right)\cdot\prod_{i\in[1,n]}\operatorname{\mathbb{E}}\left% [\exp\left(\lambda Z_{i}\right)\right]$
		$\displaystyle\leq\exp\left(\frac{(b-a)^{2}}{8n}\cdot\lambda^{2}+\varepsilon% \cdot\lambda\right)\leq\exp\left(-\frac{2n\varepsilon^{2}}{(b-a)^{2}}\right),$

where the last inequality is by minimizing at $\lambda=-4n\varepsilon/(b-a)^{2}$ . ∎

Theorem 1.4.10 (Generalized Hoeffding’s Bound [Hoe63]).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that for all $1\leq i\leq n$ , $\operatorname*{\mathbb{E}}\left[X_{i}\right]=\mu_{i}$ and $X_{i}\in[a_{i},b_{i}]$ , then

\Pr\left[\left|\sum_{i\in[1,n]}X_{i}-\sum_{i\in[1,n]}\mu_{i}\right|\geq% \varepsilon\right]\leq 2\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i\in[1,n]}(b_% {i}-a_{i})^{2}}\right).

Proof.

Let $Z_{i}=X_{i}-\mu_{i}$ , then $\operatorname*{\mathbb{E}}\left[Z_{i}\right]=0$ and $Z_{i}\in[a_{i}-\mu_{i},b_{i}-\mu_{i}]$ for $i\in[1,n]$ . Let $Z=\sum_{i\in[1,n]}Z_{i}$ . For $\lambda\geq 0$ ,

	$\displaystyle\Pr\left[Z\geq\varepsilon\right]$	$\displaystyle=\Pr\left[\exp\left(\lambda Z\right)\geq\exp\left(\lambda% \varepsilon\right)\right]$
		$\displaystyle\leq\frac{1}{\exp\left(\lambda\varepsilon\right)}\cdot% \operatorname{\mathbb{E}}\left[\exp\left(\lambda Z\right)\right]=\frac{1}{% \exp\left(\lambda\varepsilon\right)}\cdot\prod_{i\in[1,n]}\operatorname{% \mathbb{E}}\left[\exp\left(\lambda Z_{i}\right)\right]$
		$\displaystyle\leq\frac{1}{\exp\left(\lambda\varepsilon\right)}\cdot\prod_{i\in% [1,n]}\exp\left(\frac{\lambda^{2}(b_{i}-a_{i})^{2}}{8}\right)=\exp\left(\sum_{% i\in[1,n]}\frac{(b_{i}-a_{i})^{2}}{8}\cdot\lambda^{2}-\varepsilon\cdot\lambda\right)$
		$\displaystyle\leq\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i\in[1,n]}(b_{i}-a_{% i})^{2}}\right),$

where the last inequality is by minimizing at $4\varepsilon/\sum_{i\in[1,n]}(b_{i}-a_{i})^{2}$ .

The lower bound argument is similar, for $\lambda<0$ ,

	$\displaystyle\Pr\left[Z\leq-\varepsilon\right]$	$\displaystyle=\Pr\left[\exp\left(\lambda Z\right)\geq\exp\left(-\lambda% \varepsilon\right)\right]$
		$\displaystyle\leq\frac{1}{\exp\left(-\lambda\varepsilon\right)}\cdot% \operatorname{\mathbb{E}}\left[\exp\left(\lambda Z\right)\right]=\exp\left(% \lambda\varepsilon\right)\cdot\prod_{i\in[1,n]}\operatorname{\mathbb{E}}\left% [\exp\left(\lambda Z_{i}\right)\right]$
		$\displaystyle\leq\exp\left(\lambda\varepsilon\right)\cdot\prod_{i\in[1,n]}\exp% \left(\frac{\lambda^{2}(b_{i}-a_{i})^{2}}{8}\right)\leq\exp\left(-\frac{2% \varepsilon^{2}}{\sum_{i\in[1,n]}(b_{i}-a_{i})^{2}}\right),$

where the last inequality is by minimizing at $-4\varepsilon/\sum_{i\in[1,n]}(b_{i}-a_{i})^{2}$ . ∎

1.4.2 Quicksort Runtime Analysis

Exercise 1.4.11 (Exercise 4.21 [MU17]).

We prove that the Randomized Quicksort algorithm sorts a set of $n$ numbers in time $O(n\log n)$ with high probability. Consider the following view of Randomized Quicksort. Every point in the algorithm where it decideds on a pivot element is called a node. Suppose the size of the set to be sorted at a particular node is $s$ . The node is called good if the pivot element divides the set into two parts, each of size not exceeds $2s/3$ . Otherwise the node is called bad. The nodes can be thought of as forming a tree in which the root node has the whole set to be sorted and its children have the two sets formed after the first pivot step and so on.

•

Show that the number of good nodes in any path from the root to a leaf in this tree is not greater than $c\log_{2}n$ , where $c$ is some positive constant.
•

Show that, w.h.p. (greater than $1-1/n^{2}$ ), the number of nodes in a given root to leaf path of the tree is not greater than $c^{\prime}\log_{2}n$ , where $c^{\prime}$ is another constant.
•

Show that, w.h.p. (greater than $1-1/n$ ), the number of nodes in the longest root to leaf path is not greater than $c^{\prime}\log_{2}n$ .
•

Show that the running time of Quicksort is $O(n\log n)$ with probability at least $1-1/n$ .

Proof.

Suppose a given node with all the internal nodes being good nodes, then the longest such path gives the upper bound on the number of good nodes in any path of the tree. This can be proven by contradiction.

Suppose the path with the largest number of good nodes is not with all good nodes, looking like $\mathbf{u}=\mathbf{v}_{0}\parallel c\parallel\mathbf{v}_{1}$ , where $c$ is a not good node. Then the suffix path $c\parallel\mathbf{v}_{1}$ has to be the path with the largest number of good nodes among the subtree with root $c$ ; otherwise there exists a path $\mathbf{s}$ in subtree with root $c$ with more good nodes, then $\mathbf{u}$ has less good nodes than $\mathbf{v}_{0}\parallel\mathbf{s}$ , contradicting with $\mathbf{u}$ being the path with the most good nodes among the tree.

We assume $c\parallel\mathbf{v}_{1}$ being the path with the largest number of good nodes among the subtree rooted by $c$ , then the largest number of good nodes under subtree rooted by $c$ is $\left|\mathbf{v}_{1}\right|$ , so is the subtree rooted by $v_{1,0}$ . Since the subtree rooted by $c$ as strictly more nodes than the subtree rooted by $v_{1,0}$ , then the largest number of good nodes of subtree rooted by $c$ is lower bounded by $\left|\mathbf{v}_{1}\right|$ . Thus we complete the proof that the largest number of good nodes from a tree is from the longest path with all nodes being good nodes.

The longest path full of good nodes has length $\log_{\frac{3}{2}}n=\log_{2}n\cdot(\log_{2}3-1)^{-1}=c\log_{2}n$ , by partition on boundary of good node condition, and choose the big piece side.

One observation: a path has at most $c\log_{2}n$ good nodes.

Let $Y$ be the length of a path, and we want to upper bound $\Pr[Y\geq c^{\prime}\log_{2}n]$ . By prior observation, the path can have at most $c\log_{2}n$ good nodes, and we can turn the bound on path length into the bound on the number of good nodes. If the path survives $\ell$ levels, then among those first $\ell$ levels we have seen at most $c\log_{2}n$ good nodes (since too many of good nodes stops a path from growing). Therefore $\Pr[Y\geq c^{\prime}\log_{2}n]\leq\Pr[X\leq c\log_{2}n]$ , where $\{X_{i}\}_{i\in[1,c^{\prime}\log_{2}n]}$ are independent Bernoulli trials with parameter $1/3$ , and $X=\sum_{i\in[1,c^{\prime}\log_{2}n]}X_{i}$ .

We want $c<c^{\prime}/3$ for lower tail bounding, and $c^{\prime}$ sufficiently large. By Chernoff’s bound,

	$\displaystyle\Pr\left[Y\geq c^{\prime}\log_{2}n\right]$	$\displaystyle\leq\Pr\left[X\leq c\log_{2}n\right]$
		$\displaystyle\leq\exp\left(-\frac{1}{2}\cdot\mu\cdot\delta^{2}\right)=n^{-% \Theta(1)},$

where $\mu=\frac{1}{3}c^{\prime}\log_{2}n$ and $\delta=1-\frac{3c}{c^{\prime}}$ .

For bounding the longest path is no longer than $c^{\prime}\log_{2}n$ , we union bound against all leaves (at most $n$ ), that the probability of existing a path longer than $c^{\prime}\log_{2}n$ is at most $n\cdot 1/n^{2}$ , hence the path is at most $c^{\prime}\log_{2}n$ long with probability $1-1/n^{2}\cdot n=1-1/n$ .

Each row of partition is dominated by runtime in $O(n)$ , and the tree height is at most $c^{\prime}\log_{2}n$ with probability at least $1-1/n$ , hence that the runtime of the algorithm is $O(n\log n)$ with probability greater than $1-1/n$ . ∎

1.4.3 Network Routing Problems

Exercise 1.4.12 (Exercise 4.22 [MU17]).

Consider the bit-fixing routing algorithm for routing a permutation on the $n$ -cube. Suppose that $n$ is even. Write each source node as $a_{s}\parallel b_{s}$ , with $a_{s}$ and $b_{s}$ of length $n/2$ . Let the destination of $s$ ’s packet be $b_{s}\parallel a_{s}$ . Show that this permutation causes the bit-fixing routing algorithm to take $\Omega(\sqrt{N})$ steps.

Proof.

Since the permutation is $a_{s}\parallel b_{s}\mapsto b_{s}\parallel a_{s}$ , we can view the algorithm as 2 phases by fixing $a_{s}$ and $b_{s}$ . WLOG we analyze the property from phase 1, as the 2 phases are symmetric.

We write address format $a_{s}\parallel b_{s}$ in $a_{s,0}\parallel a_{s,1}\parallel b_{s,0}\parallel b_{s,1}$ , where $a_{s}=a_{s,0}\parallel a_{s,1}$ and $b_{s}=b_{s,0}\parallel b_{s,1}$ . During the bit fixing, the packet from $a_{s}\parallel b_{s}$ traverses to $b_{s,0}\parallel a_{s,1}\parallel b_{s,0}\parallel b_{s,1}$ . Eventually, when all $a_{s}$ bits are fixed to $b_{s}$ , the packet arrives $b_{s}\parallel b_{s}$ .

We notice that there are up to $\sqrt{N}$ such intermediate addresses $b_{s}\parallel b_{s}$ , yet in the $n$ -cube there are $N=2^{n}$ packets. Thus, nodes with addresses $b_{s}\parallel b_{s}$ will be traversed by $\sqrt{N}$ packets in total.

Another interesting observation is: the packet routing in such permutation is not “load-balancing”.

View each bit being fixed as a packet traversing from one half-hypercube to another half-hypercube. By prior discussion, we noticed that the first phase bit fixing is “localized”, namely all $\sqrt{N}$ packets from $\ast\parallel b_{s}$ go to $b_{s}\parallel b_{s}$ , and it takes no other packets. To be more generalized, all packets from $\ast\parallel a_{s,1}\parallel b_{s,0}\parallel b_{s,1}$ go to $b_{s,0}\parallel a_{s,1}\parallel b_{s,0}\parallel b_{s,1}$ . The earlier the bit being fixed, the less packets traversing through half-hypercubes. With more bits fixed in the front ( $b_{s,0}$ ) and less bits flexible in the back ( $a_{s,1}$ ), more packets aggregated from sub-hypercubes are forced to take 1 path to merge sub-hypercubes (Think of 8 packets over 3 bit hypercube, the $110-111$ edge will take 4 packages). Therefore, right before $n^{\mathrm{th}}$ bit being fixed, where $n=\left|a_{s}\right|$ , there are $\sqrt{N}/2$ packets aggregated for 1 bit fix to $b_{s}\parallel b_{s}$ , that the edge will be used by $\sqrt{N}/2$ packets, and thus the edge has an $\Omega(\sqrt{N})$ delay.

We conclude that the deterministic bit-fixing algorithm takes $\Omega(\sqrt{N})$ steps to route in this permutation. ∎

Exercise 1.4.13 (Exercise 4.23 [MU17]).

Consider the following modification to the bit-fixing routing algorithm for routing a permutation on the $n$ -cube. Instead of fixing the bits in order from $1$ to $n$ , each packet chooses a random order (independent of other packet’s choices) and fixes the bits in that order. Show that there is a permutation for which this algorithm requires $2^{\Omega(n)}$ steps with high probability.

Proof.

We use the previous permutation $a_{s}\parallel b_{s}\mapsto b_{s}\parallel a_{s}$ , and $2\sqrt{N}$ special cases, $a_{s}\parallel 0$ and $0\parallel b_{s}$ , are interesting. For these permutations, we would like to lower bound the number of packets that traverse $0\parallel 0$ .

To reach $0\parallel 0$ , the non-zero side should be fixed to zero first, before any bit on zero side being fliped to non-zero. WLOG we discuss the case that non-zero on the left side, the non-zero on right side follows from symmetry. We introduce 0-1 independent random variables $\{X_{i,j}\}$ where $i\in[1,\frac{n}{2}]$ and $j\in[1,\binom{n/2}{i}]$ , indicating if $j^{\mathrm{th}}$ packet with $i$ ones traverses $0\parallel 0$ . The routing should fix $i$ one bits first, thus $\Pr\left[X_{i,j}=1\right]=\binom{2i}{i}^{-1}$ .

Before moving to the lower bound the packet numbers, we need to derive the expectation of $X=\sum X_{i,j}$ ,

\operatorname*{\mathbb{E}}\left[X\right]=\sum_{i\in[1,\frac{n}{2}]}\sum_{j\in[% 1,\binom{n/2}{i}]}\operatorname*{\mathbb{E}}\left[X_{i,j}\right]=\sum_{i\in[1,% \frac{n}{2}]}\frac{\binom{n/2}{i}}{\binom{2i}{i}}\\ \geq\sum_{i\in[1,\frac{n}{2}]}\frac{1}{4^{i}}\cdot\binom{n/2}{i}=\left(\frac{5% }{4}\right)^{n/2}-1=\mu_{L},

the relaxation on $\binom{2i}{i}$ follows

\binom{2i}{i}\leq\sum_{k\in[0,2i]}\binom{2i}{k}=2^{2i}=4^{i}.

The previous lower tail bound inequality chain comes in handy, that

\Pr\left[X\leq(1-\delta)\cdot\mu\right]\leq\left(\frac{e^{-\delta}}{(1-\delta)% ^{1-\delta}}\right)^{\mu}\leq\left(\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}% \right)^{\mu_{L}}.

Since $\mu_{L}=2^{\Omega(n)}$ , we conclude that the algorithm on this permutation has runtime $2^{\Omega(n)}$ time steps. ∎

Exercise 1.4.14 (Exercise 4.24 [MU17]).

Assume we use the randomized routing algorithm for $n$ -cube network to route a total of up to $p2^{n}$ packets, where each node is the source of no more than $p$ packets, and each node is the destination of no more than $p$ packets.

•

Give a high probability bound on the runtime of the algorithm.
•

Give a high probability bound on the maximum number of packets at any nodes at any step of the execution of the routing algorithm.

Proof.

The analysis follows from the runtime analysis for randomized bit-fixing routing [VB81], but the number of packets increase from $2^{n}$ to $p\cdot 2^{n}$ . There are 2 phases, by first routing $p\cdot 2^{n}$ packets to random intermediate nodes, then route these nodes to their destinations. WLOG we analyze the first phase’s runtime, as they are symmetric.

Follow from the proof structure, we first bound the number of “active packets” over certain path, then upper bound the probability of the path with not many “active packets” yet runs slow, finally we derive a probability upper bound by union bounding all paths over the $n$ -cube.

We recall the notion of “active packets”, that a packet is “active” at a node $v_{i-1}$ on the path. If $v_{i-1}$ and $v_{i}$ are adjacent on path, and diff by $j^{\mathrm{th}}$ bit, in order for a packet to be “active”, its bits should be fixed before $j^{\mathrm{th}}$ bit when it reaches $v_{i-1}$ . With that said, there are $p2^{j-1}$ packets sharing same suffix as $v_{i-1}$ from $j^{\mathrm{th}}$ bit, while the probability of sampling a random intermediate address with prefixed $j-1$ bits matching $v_{i-1}$ is $2^{-(j-1)}$ . Thus, the expected number of “active packets” at a node on an edge is $p$ .

Given a path of length $m$ , the path is at most $n$ as there are $n$ bits to fix. Let $X$ be the number of “active packets” on this path, then the expected number of “active packets” is upper bounded by $\operatorname*{\mathbb{E}}\left[X\right]=mp\leq np$ . By Chernoff’s bound, the probability of having too many “active packets” is upper bounded as follows

\Pr\left[X\geq 6np\geq 6mp\right]\leq 2^{-6np}.

By conditional probability, we derive the following upper bound by sums of (conditional) probabilities

	$\displaystyle\Pr\left[A\right]$	$\displaystyle=\Pr\left[A\mid B\right]\cdot\Pr\left[B\right]+\Pr\left[A\mid\neg B% \right]\cdot\Pr\left[\neg B\right]$
		$\displaystyle\leq\Pr\left[B\right]+\Pr\left[A\mid\neg B\right].$

We upper bound the probability of the runtime of the path being at least $30np$ time steps by either “too many active packets” or “not many active packets but running slow” as follows

	$\displaystyle\Pr\left[T\geq 30np\right]$	$\displaystyle=\Pr\left[T\geq 30np\mid X\geq 6np\right]\cdot\Pr\left[X\geq 6np% \right]+\Pr\left[T\geq 30np\mid X<6np\right]\cdot\Pr\left[X<6np\right]$
		$\displaystyle\leq\Pr\left[X\geq 6np\right]+\Pr\left[T\geq 30np\mid X<6np\right].$

For “not many active packets but running slow” case, the runtime of the path is measuring how many packets stay on the path, turns into the time steps used to route all the packets. Only “active packets” can stay on the path, with probability $1/2$ to branch into the next node on path. An “active packet”’s stay on the path can be modeled by the number of failures in a geometrically distributed random variable, and it leaves the path on a successful trial with probability $1/2$ . Upper bound on the sum of geometrically distributed random variables can be relaxed by upper bounding the sum of a serial of Bernoulli trials with parameter $1/2$ here

\Pr\left[T\geq 30np\mid X<6np\right]\leq\Pr\left[\sum_{i\in[1,36np]}Y_{i}<6np% \right]\leq\exp\left(-\frac{1}{2}\cdot 18np\cdot\left(\frac{2}{3}\right)^{2}% \right)=\exp\left(-4np\right)\leq 2^{-3np-1}.

Therefore, the probability for the path’s runtime being at least $30np$ is upper bounded by $2^{-3np}$

\Pr\left[T\geq 30np\right]\leq 2^{-6np}+2^{-3np-1}\leq 2^{-3np}.

Union bounding over $2^{2n}$ paths, the probability of the first phase runtime exceeding $30np$ is at most $2^{2n-3np}$ .

On the number of packets at any nodes at any time step, we can upper bound by the number of packets that will traverse the node. Let $X_{i}$ be the number of packets arriving the node on $i^{\mathrm{th}}$ bit, $X=\sum_{i\in[1,n]}X_{i}$ be the number of packets using the node. Since $\operatorname*{\mathbb{E}}\left[X_{i}\right]=p$ by $p2^{i}$ source packets and $2^{-i}$ probability in random address prefix matching the node’s address’s prefix, by linearity of expectation, $\operatorname*{\mathbb{E}}\left[X\right]=np$ .

Once we have an expectation, by Chernoff’s bound we have $\Pr\left[X\geq 6np\right]\leq 2^{-6np}$ for this node at a certain step. By union bound over all nodes and time steps, the queue exceeding $6np$ has probability at most $2^{-6np}\cdot 2^{n}\cdot O(np)$ . ∎

Exercise 1.4.15 (Exercise 4.26 [MU17]).

Given a network that is an undirected graph $G$ , where nodes represent processors and the edges between the nodes represent wires. We are also given a set of $N$ packets to route. For each packet we are given a source node, a destination node, and the exact route that the packet should take from source to destination. In each time step, at most one packet can traverse an edge. A packet can wait at any node during any time step, and we assume unbounded queue sizes at each node.

A schedule for a set of packets specifies the timing for the movement of packets along their respective routes. That is, it specifies which packet should move and which should wait at each time step. Our goal is to produce a schedule for the packets that tries to minimize the total time and the maximum queue size needed to route all the packets to their destination.

•

The dilation $d$ is the maximum distance traveled by any packet. The congestion $c$ is the maximum number of packets that must traverses a single edge during the entire course of the routing. Argue that the time required for any schedule should be at least $\Omega(c+d)$ .
•

Consider the following unconstrained schedule, where many packets may traverse an edge during a single time step. Assign each packet an integral delay $x$ , chosen randomly, independently, and uniformly from the interval $\left[1,\left\lceil\alpha c/\log(Nd)\right\rceil\right]$ , where $\alpha$ is a constant. A packet waits in its source node for $x$ time steps, then it moves on to its final destination through its specified route without ever stopping. Give an upper bound on the probability that more than $O(\log(Nd))$ packets use a particular edge $e$ at a particular time step $t$ .
•

Again using the unconstrained schedule, show that the probability that more than $O(\log(Nd))$ packets pass through any edge at any time step is at most $1/(Nd)$ for a positive constant $\alpha$ .
•

Use the unconstrained schedule to devise a simple randomized algorithm that, with high probability, produces a schedule of length $O(c+d\log(Nd))$ using queues of size $O(\log(Nd))$ and following the constraint that at most one packet crosses an edge per time step.

Proof.

The length of the schedule is the runtime of the routing algorithm, and it is lower bounded by: the maximum distance a packet can traverse in the network, and the maximum congestion that delays the package traversal. Therefore, let $T$ denotes the time steps of the routing algorithm, and $T\geq\max(c,d)$ , and we conclude that $T=\Omega(c+d)$ .

Considering how many packets traverse edge $e$ at the $t^{\mathrm{th}}$ time step, we introduce $\{X_{i}\}_{i\in[1,N]}$ independent 0-1 random variables, where $X_{i}=1$ stands for $i^{\mathrm{th}}$ packet traverses $e$ at $t^{\mathrm{th}}$ time step. Since there are at most $c\leq N$ packets traverse $e$ , and if they traverse $e$ at the $t^{\mathrm{th}}$ time step, they had to be starting by one of the $\left\lceil\alpha c/\log{Nd}\right\rceil$ delays, we here upper bound the expectation of $X=\sum_{i\in[1,N]}X_{i}$ by

\operatorname*{\mathbb{E}}\left[X\right]\leq c\cdot\frac{\log(Nd)}{\alpha c}=% \frac{\log(Nd)}{\alpha}.

By 1.4.7, given $\mu_{H}\geq\mu$ ,

\Pr\left[X\geq(1+\delta)\mu_{H}\right]\leq\left(\frac{e^{\delta}}{(1+\delta)^{% 1+\delta}}\right)^{\mu_{H}}\leq\exp(-\mu_{H}\delta^{2}/3),

we have $X\geq(1+\delta)\log(Nd)/\alpha$ probability upper bounded by $(Nd)^{-\delta^{2}/3\alpha}$ .

Bounding the number of packets traverses any edge at any time step is equivalent to bounding the congestion of the schedule, which can be achieved by union bounding through all the time steps and all the edges. Each packet can go as far as $d$ edges, and the packet arrives destination with at most $d+\left\lceil\alpha c/\log(Nd)\right\rceil$ time steps (by assumption that it does not stop once). If $\delta=1$ and $\alpha<1/9$ , the upper bounded probability is

	$\displaystyle Nd\cdot\left(d+\left\lceil\frac{\alpha c}{\log{Nd}}\right\rceil% \right)\cdot(Nd)^{-\frac{\delta^{2}}{3\alpha}}$	$\displaystyle\leq Nd\cdot Nd\cdot(Nd)^{-\frac{\delta^{2}}{3\alpha}}$
		$\displaystyle\leq(Nd)^{2}\cdot(Nd)^{-3}=(Nd)^{-1}.$

If the tuned algorithm has schedule of length $O(d\log(Nd)+c)$ with queue size $O(\log(Nd))$ , try scale the schedule by $2\log(Nd)/\alpha$ . By previous result, with the assumption that multiple packets crossing an edge at a time with no stop, the probability of more than $2\log(Nd)/\alpha$ packets passing through any edge at any time step is at most $(Nd)^{-1}$ . In the prior model, each time step the edge let packets crossing in a batch, and the batch is at most $2\log(Nd)/\alpha$ .

Now removing the assumption of multiple packets crossing an edge at a time, by scaling $2\log(Nd)/\alpha$ to the schedule and queue of size $O(\log(Nd))$ , given an edge allowing only 1 packet at a time, the batched moving can be simulated with the devised algorithm. ∎

Remark 1.4.16.

The intuition is: we first let everyone run non-stop with random starts, count how bad the pileups get, then spread those pileups thin by stretching time proportionally, and leading to an average case non stop routing. This is the Leighton-Maggs-Rao trick [LMR94].

	$\displaystyle\Pr\left[X\geq(p+\varepsilon)n\right]$	$\displaystyle\leq e^{-2n\varepsilon^{2}},$
	$\displaystyle\Pr\left[X\leq(p-\varepsilon)n\right]$	$\displaystyle\leq e^{-2n\varepsilon^{2}},$
	$\displaystyle\Pr\left[\left\|X-pn\right\|\geq\varepsilon n\right]$	$\displaystyle\leq 2e^{-2n\varepsilon^{2}}.$