Moments and Deviations

Prev: Game-Theoretic Techniques Next: Tail Inequalities

Problems

3.1

Consider an occupancy problem in which $n$ balls are independently and uniformly distributed in $n$ bins. Show that, for large $n$, the expected number of empty bins approaches $n/e$, where $e$ is the base of the natural logarithm. What is the expected number of empty bins when $m$ balls are thrown into $n$ bins? See Theorem 4.18.

---

3.2

Suppose $m$ balls are thrown into $n$ bins. Give the best bound you can on $m$ to ensure that the probability of there being a bin containing at least two balls is at least $\frac{1}{2}$.

---

3.3

A parallel computer consists of $n$ processors and $n$ memory modules. During a step, each processor sends a memory request to one of the memory modules. A memory module that receives either one or two requests can satisfy its request(s); modules that receive more than two requests will satisfy two requests and discard the rest.

1. Assuming that each processor chooses a memory module independently and uniformly at random, what is the expected number of processors whose requests are satisfied? Use the approximation $(1-1/n{)}^n\approx 1/e$ if necessary.
2. Repeat the computation for the case where each memory module can satisfy only one request during a step.

---

3.4

Consider the following experiment, which proceeds in a sequence of rounds. For the first round, we have $n$ balls, which are thrown independently and uniformly at random into $n$ bins. After round $i$, for $i\ge 1$, we discard every ball that fell into a bin by itself in round $i$. The remaining balls are retained for round $i+1$, in which they are thrown independently and uniformly at random into the $n$ bins. Show that there is a constant $c$ such that with probability $1-o(1)$, the number of rounds is at most $c\log \log n$.

---

3.5

Let $X$ be a random variable with expectation ${\mu }_X$ and standard deviation ${\sigma }_X$.

1. Show that for any $t\in {\mathbb{R}}^{+}$,

$$\mathrm{Pr}[X-{\mu }_X\ge t{\sigma }_X]\le \frac{1}{1+t^2}.$$

This version of the Chebyshev inequality is sometimes referred to as the Chebyshev-Cantelli bound. 2. Prove that

$$\mathrm{Pr}[|X-{\mu }_X|\ge t{\sigma }_X]\le \frac{2}{1+t^2}.$$

Under what circumstances does this give a better bound than the Chebyshev inequality?

---

3.6

Let $Y$ be a non-negative integer-valued random variable with positive expectation. Prove the following inequalities.

$$\mathrm{Pr}[Y=0]\le \frac{\mathbb{E}[Y^2]-\mathbb{E}[Y{]}^2}{\mathbb{E}[Y{]}^2}.$$

$$\frac{\mathbb{E}[Y{]}^2}{\mathbb{E}[Y^2]}\le \mathrm{Pr}[Y\ne 0]\le \mathbb{E}[Y].$$

3. Explain why the second inequality always gives a stronger bound than the first inequality.

---

3.7

Let $a$ and $b$ be chosen independently and uniformly at random from $Z_n=\{0,1,2,\dots ,n-1\}$, where $n$ is a prime. Suppose we generate $t$ pseudo-random numbers from $Z_n$ by choosing $r_i=ai+b\mathrm{mod}n$, for $1\le i\le t$. For any $ϵ\in [0,1]$, show that there is a choice of the witness set $W\subset Z_n$ such that $|W|\ge ϵn$ and the probability that none of the $r_i$‘s lie in the set $W$ is at least $(1-ϵ{)}^2/4t$.

---

3.8

Suggest a scheme for four-point sampling from the range $Z_n$ where $n$ is a prime. For $t<n$ samples $r_1,\dots ,r_t$ using this scheme, give an upper bound on the probability that all $t$ attempts fail to discover a witness given $x\in L$ and compare this with the bound of $1/16$ that the naive use of four samples would yield. En route, derive an upper bound on the fourth central moment of the sum of four-way independent random variables.

---

3.9

Due to D. R. Karger and R. Motwani [233].

1. Let $S,T$ be two disjoint subsets of a universe $U$ such that $|S|=|T|=n$. Suppose we select a random set $R\subseteq U$ by independently sampling each element of $U$ with probability $p$. We say that the random sample $R$ is good if the following two conditions hold: $R\cap S=\varnothing$ and $R\cap T\ne \varnothing$. Show that for $p=1/n$, the probability that $R$ is good is larger than some positive constant.
2. Suppose now that the random set $R$ is chosen by sampling the elements of $U$ with only pairwise independence. Show that for a suitable choice of the value of $p$, the probability that $R$ is good is larger than some positive constant.

---

3.10

The sharp threshold result in the coupon collector’s problem does not imply that the probability of needing more than $cn\log n$ trials goes to zero at a doubly exponential rate if $c$ were not a constant, but were allowed to grow with $n$. Let the probability of requiring more than $cn\log n$ trials be $p(c)$. For constant $c$, show that $1/p(c)$ can be bounded from above and below by polynomials in $n$.

---

3.11

Consider the extension of the coupon collector’s problem to that of collecting at least $k$ copies of each coupon type. Show that the sharp threshold for the number of selections required, denoted $X^{(k)}$, is centered at $n(\ln n+(k-1)\ln \ln n)$. In other words, for any positive integer $k$ and constant $c\in \mathbb{R}$, prove that

$$\underset{n\to \infty }{\lim }\mathrm{Pr}[X^{(k)}>n(\ln n+(k-1)\ln \ln n+c)]=e^{-e^{-c}}.$$

---

3.12

Consider the following process related to the coupon collector problem. There are $n$ bins and $n$ players, and each player has an infinite supply of balls. The bins are all initially empty. We have a sequence of rounds: in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable $Z$ be the number of rounds before every bin is non-empty. Determine the expected value of $Z$. What can you say about the tail of $Z$‘s distribution?

---

3.13

Let $B$ be a random bipartite graph on two independent sets of vertices $U$ and $V$, each with $n$ vertices. For each pair of vertices $u\in U$ and $v\in V$, the probability that the edge between them is present is $p(n)$, and the presence of any edge is independent of all other edges. Let $p(n)=(\ln n+c)/n$ for some $c\in \mathbb{R}$.

1. Show that the probability that $B$ contains an isolated vertex is asymptotically equal to $e^{-2e^{-c}}$.
2. Suggest and prove a generalization of this to random non-bipartite graphs.

---

3.14

Due to R. M. Karp.

Consider a bin containing $d$ balls chosen at random, without replacement, from a collection of $n$ distinct balls. Without being able to see or count the balls in the bin, we would like to simulate random sampling with replacement from the original set of $n$ balls. Our only access to the balls is that we can sample without replacement from the bin.

Consider the following strategy. Suppose that $k<d$ balls have been drawn from the bin so far. Flip a coin with the probability of HEADS being $k/n$. If HEADS appears, then pick one of the $k$ previously drawn balls uniformly at random; otherwise, draw a random ball from the bin. Show that each choice is independently and uniformly distributed over the space of the $n$ original balls. How many times can we repeat the sampling?

---

3.15

Due to D. Angluin and L. G. Valiant [28].

Let $B$ denote a random bipartite graph with $n$ vertices in each of the vertex sets $U$ and $V$. Each possible edge, independently, is present with probability $p(n)$. Consider the following algorithm for constructing a perfect matching, see Section 7.3, in such a random graph. Modify the Proposal Algorithm of Section 3.5 as follows. Each $u\in U$ can propose only to adjacent $v\in V$. A vertex $v\in V$ always accepts a proposal, and if a proposal causes a divorce, then the newly divorced $u\in U$ is the next to propose. The sampling procedure outlined in Problem 3.14 helps implement the Principle of Deferred Decisions. How small can you make the value of $p(n)$ and still have the algorithm succeed with high probability? The following fact concerning the degree $d(v)$ of a vertex $v$ in $B$ proves useful:

$$\mathrm{Pr}[d(v)\le (1-\beta )np]=O(e^{-{\beta }^{2}np/2}).$$