Tail Inequalities

Prev: Moments and Deviations Next: The Probabilistic Method

Problems

4.1

Suppose you are given a biased coin that has $\mathrm{Pr}[\text{HEADS}]=p\ge a$, for some fixed $a$, without being given any other information about $p$. Devise a procedure for estimating $p$ by a value $\tilde{p}$ such that you can guarantee that

$$\mathrm{Pr}[|p-\tilde{p}|>ϵp]<\delta ,$$

for any choice of the constants $0<a,ϵ,\delta <1$. Let $N$ be the number of times you need to flip the biased coin to obtain the estimate. What is the smallest value of $N$ for which you can still give this guarantee?

---

4.2

Let $X$ be a random variable. Define the $k$th factorial moment of $X$, $\mathbb{E}[X^{[k]}]$, as the expected value of

$$X^{[k]}=X(X-1)\cdots (X-k+1).$$

Let $G_1$ denote a random graph on $n$ vertices where each edge independently is present with probability $p$, and $G_2$ denote a graph on $n$ vertices that has $m$ edges chosen uniformly at random. Let $X_n$ denote the number of isolated vertices in $G_1$, and let $Y_n$ be the number of isolated vertices in $G_2$. Consider the case

$$p=\frac{\log n+c}{n}$$

and

$$m=\frac{n(\log n+c)}{2},$$

for a real value $c$. Prove that $\mathbb{E}[X_n^{[k]}]$ and $\mathbb{E}[Y_n^{[k]}]$ are asymptotically equal to ${\lambda }^k$, where $\lambda =e^{-c}$.

---

4.3

For $\mu$ in the range $[1,\ln n]$, use (4.1) to obtain a closed-form upper bound for ${\Delta }^{+}(\mu ,1/n^2)$, as a function of $\mu$ and $n$, that is within a constant factor of the best possible.

---

4.4

Let $X_1,X_2,\dots ,X_n$ be independent geometrically distributed random variables each having expectation $2$, each of the $X_i$ is an independent experiment counting the number of tosses of an unbiased coin up to and including the first HEADS. Let

$$X=\sum _{i=1}^n{X}_i$$

and $\delta$ be a positive real constant. Use moment generating functions and the Chernoff technique to derive the best upper bound you can on

$$\mathrm{Pr}[X>(1+\delta )(2n)].$$

---

4.5

The result of Theorem 4.2 bounds the probability of the sum of Poisson trials deviating far below its expectation. Use this to give a bound on the probability of the sum of independent geometric random variables deviating above its expectation, thus providing an alternative approach to that in Problem 4.4.

---

4.6

Hoeffding’s Bound [202].

Suppose $Y_1,\dots ,Y_n$ are independent Poisson trials such that $\mathrm{Pr}[Y_i=1]=p_i$. Let

$$Y=\sum _{i=1}^n{Y}_i,\mu =\mathbb{E}[Y]=\sum _{i=1}^n{p}_i,p=\mu /n.$$

Our goal is to show that from the standpoint of deviations from the mean, the worst case is when the $p_i$‘s are all equal. Let $X$ be the sum of $n$ independent Bernoulli trials each having probability $p$ of assuming the value $1$. Then, for any $a\ge \mu +1$ and any $b\le \mu -1$, show that

$$\mathrm{Pr}[Y\ge a]\le \mathrm{Pr}[X\ge a],$$

and

$$\mathrm{Pr}[Y\le b]\le \mathrm{Pr}[X\le b].$$

---

4.7

Due to W. Hoeffding [202].

This problem deals with a useful generalization of the Hoeffding bound in Problem 4.6.

1. A function $f:\mathbb{R}\to \mathbb{R}$ is said to be convex if for any $x_1$, $x_2$ and $0\le \lambda \le 1$, the following inequality is satisfied:

$$f(\lambda x_1+(1-\lambda )x_2)\le \lambda f(x_1)+(1-\lambda )f(x_2).$$

Show that the function $f(x)=e^{tx}$ is convex for any $t>0$. What can you say when $t\le 0$? 2. Let $Z$ be a random variable that assumes values in the interval $[0,1]$, and let $p=\mathbb{E}[Z]$. Define the Bernoulli random variable $X$ such that $\mathrm{Pr}[X=1]=p$ and $\mathrm{Pr}[X=0]=1-p$. Show that for any convex function $f$, $\mathbb{E}[f(Z)]\le \mathbb{E}[f(X)]$. 3. Let $Y_1,\dots ,Y_n$ be independent and identically distributed random variables over $[0,1]$, and define

$$Y=\sum _{i=1}^n{Y}_i.$$

Using parts (1) and (2), derive upper and lower tail bounds for the random variable $Y$ using the Chernoff bound technique. In particular, show that

$$\mathrm{Pr}[Y-\mathbb{E}[Y]>\delta ]\le \exp (-2{\delta }^2/n).$$

Remark: While the results in this problem hold for continuous random variables, they may be a bit easier to prove in the case where $Z,Y_1,\dots ,Y_n$ take on a discrete set of values in the interval $[0,1]$. Also, it should be easy to generalize this to distributions defined over arbitrary intervals $[l,h]$. See also Problem 4.21.

---

4.8

Consider a BPP algorithm that has an error probability of $1/2-1/p(n)$, for some polynomially bounded function $p(n)$ of the input size $n$. Using the Chernoff bound on the tail of the binomial distribution, show that a polynomial number of independent repetitions of this algorithm suffice to reduce the error probability to $1/2^n$.

---

4.9

Consider now the following variant of the bit-fixing algorithm. Each packet randomly orders the bit positions in the label of its source, and then corrects the mismatched bits in that order. Show that there is a permutation for which with high probability this algorithm requires $2^{\Omega (n)}$ steps to complete the routing.

---

4.10

Suppose we run Valiant’s scheme on an $N$-node network in which every node is of degree $d$; each packet first goes to a random destination chosen uniformly from all the nodes and then on to its final destination. Show that the expected number of steps for the completion of the first phase is

$$\Omega \left(\frac{\log N}{d\log \log N}+\frac{\log N}{\log d}\right).$$

---

4.11

The lattice approximation problem is an extension of the set-balancing problem, Example 4.5. As before, we are given an $n\times n$ matrix $A$ all of whose entries are $0$ or $1$. In addition, we are given a column vector $p$ with $n$ entries, all of which are in the interval $[0,1]$. We wish to find a column vector $q$ with $n$ entries, all of which are from the set $\{0,1\}$, so as to minimize

$$\Vert A(p-q){\Vert }_{\infty }.$$

We think of the vector $q$ as an integer approximation to the given real vector $p$, in the sense that $Aq$ is close to $Ap$ in every component. This has applications to approximating certain integer programs given solutions to their linear programming relaxations, along the lines of Section 4.3. Derive a bound on $\Vert A(p-q){\Vert }_{\infty }$ assuming that $q$ were derived from $p$ using randomized rounding.

---

4.12

Consider the global wiring problem of Section 4.3. We wish to approximate the best possible solution without the restriction that only one-bend routes are used. Adapt the approach in Section 4.3 to devise an algorithm running in time polynomial in the number of gates and nets, achieving an approximation similar to that in Theorem 4.8.

---

4.13

The set-cover problem is the following: given sets $S_1,\dots ,S_n$ over a universe $U$, find the smallest set $T\subseteq U$ such that for $1\le i\le n$, $T\cap S_i\ne \varnothing$. An alternative formulation of this problem is the following: given a $0$-$1$ matrix $M$, find a $0$-$1$ column vector $c$ such that the dot product of each row of $M$ with $c$ is positive while minimizing $\Vert c{\Vert }_1$. The matrix $M$ has $n$ rows, and the $i$th row is the incidence vector of the set $S_i$.

Given a matrix $M$, let $C(M)$ denote the size of the smallest set-cover for $M$. Let $n$ be the number of rows in $M$. Show that we can adapt the technique of linear programming followed by randomized rounding to find a set-cover of size $O(\log n)$ times $C(M)$.

---

4.14

Show that the RandQS algorithm of Chapter 1 runs in time $O(n\log n)$ with high probability.

---

4.15

Redesign the parameters of the LazySelect algorithm of Chapter 3 and invoke the Chernoff bound to show that with high probability it finds the $k$th smallest of $n$ elements in

$$n+k+\sqrt{n}{\log }^{O(1)}n$$

steps, with probability $1-o(1)$.

---

4.16

Prove Lemmas 4.9 and 4.10. Also, formulate and prove their generalizations to the case where the conditioning is done on more than one random variable. Finally, using these, prove Lemma 4.11.

---

4.17

Prove Theorem 4.12.

---

4.18

Prove Lemma 4.14.

---

4.19

Using Lemma 4.14, prove Theorem 4.13.

---

4.20

Derive the tail bounds described in Problem 4.7(3) by applying Azuma’s inequality, Corollary 4.17, to the Doob martingale sequence obtained from $Y$ by setting

$$X_0=\mathbb{E}[Y]$$

and, for $1\le i\le n$,

$$X_i=\mathbb{E}[Y\mid Y_1,\dots ,Y_i].$$

How does this bound compare with the one obtained in Problem 4.7?

---

4.21

Prove Azuma’s inequality, Theorem 4.16, for the case where $c_k=1$ for all $k$. Note that this is the same as Corollary 4.17 with $c=1$. Do you see how to generalize this to the case of arbitrary $c_k$‘s? Hint: Concentrate on the upper tail bound, since the lower tail bound can be obtained by negating the random variables. Consider the martingale difference sequence $Y_1,Y_2,\dots$ obtained by setting $Y_i=X_i-X_{i-1}$, and note that

$$X_t=\sum _{i=1}^t{Y}_i.$$

You can essentially mimic the proof of Theorem 4.1, but be careful to use conditional expectations and the martingale property in going from the analog of equation (4.2) to that of equation (4.3). Since the random variables $Y_i$ could have arbitrary distributions over the interval $[-1,1]$, you will also have to make use of an argument similar to that in Problem 4.7.

---

4.22

Due to A. Kamath, R. Motwani, K. Palem, and P. Spirakis [228].

Consider again the issue of tail bounds on the number of empty bins studied in Theorem 4.18. In this setting, let $I_i$ be the indicator variable whose value is $1$ if and only if bin $i$ is empty, and define

$$Z=\sum _{i=1}^n{I}_i$$

as the number of empty bins.

Define

$$p=\mathbb{E}[I_i]=(1-1/n{)}^m,$$

and let $I_i^{\prime }$ be mutually independent Bernoulli random variables that take value $1$ with probability $p$ and value $0$ with probability $1-p$; note that the sum

$$Y=\sum _{i=1}^n{I}_i^{\prime }$$

has the binomial distribution with parameters $n$ and $p$.

1. Show that for all $t\ge 0$,

$$\mathbb{E}[e^{tZ}]\le \mathbb{E}[e^{tY}].$$

Conclude that any Chernoff bound on the upper tail of $Y$‘s distribution also applies to the upper tail of $Z$‘s distribution, even though the Bernoulli variables $I_i$ are not mutually independent. The point is that their correlation is negative and only helps to reduce the tail probability. How does the resulting bound on the upper tail of $Z$‘s distribution compare with the bound given in Theorem 4.18? 2. Can you show that for all $t<0$,

$$\mathbb{E}[e^{tZ}]\le \mathbb{E}[e^{tY}]?$$

Repeat the exercise in part (1) for the lower tail.