The Probabilistic Method

Prev: Tail Inequalities Next: Markov Chains and Random Walks

Problems

5.1

Due to J. Naor.

Let $X$ be a random variable with expectation $0$ such that the moment generating function $\mathbb{E}[\exp (t|X|)]$ is finite for some $t>0$. We can use the following two kinds of tail inequalities for $X$.

Chernoff Bound:

$$\mathrm{Pr}[|X|\ge \delta ]\le \underset{t\ge 0}{\min }\frac{\mathbb{E}[e^{t|X|}]}{e^{t\delta }}.$$

$k$th-Moment Bound:

$$\mathrm{Pr}[|X|\ge \delta ]\le \frac{\mathbb{E}[|X{|}^k]}{{\delta }^k}.$$

1. Show that for each $\delta$, there exists a choice of $k$ such that the $k$th-moment bound is stronger than the Chernoff bound. Hint: Consider the Taylor expansion of the moment generating function and apply the probabilistic method.
2. Why would we still prefer the Chernoff bound to the seemingly stronger $k$th-moment bound?

---

5.2

In Example 5.2, we applied the probabilistic method to certificates for the value of a game tree in the setting of Section 2.1. We showed that for any instance of $T_{2,k}$ there is a set of $n^{0.793}$ leaves whose values certify the value of the root for that instance. Show that, in fact, for any instance of $T_{2,k}$, there is a set of

$$2^k=\sqrt{n}$$

leaves whose values certify the value of the root for that instance.

---

5.3

Let $G$ be a graph on $n$ vertices, with $nd/2$ edges. Consider the following probabilistic experiment for finding an independent set in $G$. Delete each vertex of $G$, together with its incident edges, independently with probability $1-1/d$.

1. Compute the expected number of vertices and edges that remain after the deletion process.
2. From these, infer that there is an independent set with at least $n/2d$ vertices in any graph on $n$ vertices with $nd/2$ edges.
3. Let $G$ be a $3$-regular graph. Suppose that we wish to turn this probabilistic experiment into a randomized algorithm as follows. We delete each vertex independently with probability $2/3$. For every edge that remains, delete one of its end-points. Derive an upper bound on the probability that this algorithm finds an independent set smaller than $n(1-ϵ)/6$.

---

5.4

A function $f:\mathbb{R}\to \mathbb{R}$ is said to be concave 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)\ge \lambda f(x_1)+(1-\lambda )f(x_2).$$

The reader may wish to compare this with the notion of convex functions defined in Problem 4.7.

1. Suppose that $f$ is a concave function and $g$ is a linear function such that $g(0)\le f(0)$ and $g(1)\le f(1)$. Show that for any $x$ in the interval $[0,1]$, $g(x)\le f(x)$.
2. Show that the function

$$f(x)=1-(1-x/k{)}^k$$

is concave for any $k>0$. What can you say when $k\le 0$? 3. Let

$$f(x)=1-(1-x/k{)}^k$$

and

$$g(x)=\left(1-(1-1/k{)}^k\right)x.$$

Show that $f(x)\ge g(x)$ for positive $k$ and $0\le x\le 1$.

---

5.5

Use the probabilistic method to show that an expanding graph with the following properties exists for $n$ sufficiently large:

• $|L|=|R|=n$.
• Every vertex in $L$ has degree $n^{3/4}$, and every vertex in $R$ has degree at most $3n^{3/4}$.
• Every subset of $n^{3/4}$ vertices in $L$ has at least $n-n^{3/4}$ neighbors in $R$.

---

5.6

Suppose that you had access to the expanding graph described in Problem 5.5 for a certain value of $n$. Show that it can be used to run the LazySelect algorithm of Section 3.3 on any instance of size $n$, using $\log n$ random bits to choose the entire sample $R$. Show that the expected running time of this implementation is $O(n)$.

---

5.7

Let $G$ be a $d$-regular graph on $n$ vertices.

1. Show that the number of connected subgraphs of $G$ of size $r$ is at most $n{d}^{2r}$.
2. Suppose that each vertex of $G$ is deleted independently with probability $1-1/2d^2$. Show that with probability $1-n^{-\alpha }$, there is no surviving connected component of size exceeding $\log n$, for a suitable constant $\alpha$.

---

5.8

Lemma 5.11 guarantees that with positive probability, none of the events ${\mathcal{E}}_i$ occurs. In this problem, we see how small this positive probability can be. Consider again the probabilistic experiment suggested in Problem 5.3. Let $G$ be a $\sqrt{n}$-regular graph. Suppose that we delete vertices of $G$ independently with probability $1-1/(3n^{1/4})$.

1. Use Lemma 5.11 to make the obvious argument that with positive probability, an independent set remains after the deletion.
2. Use the Chernoff bound to show that the probability that fewer than $n^{3/4}/6$ vertices survive is less than $\exp (-n^{3/4}/12)$.
3. Now consider what happens when the above experiment is run on a $\sqrt{n}$-regular graph containing no independent set of size exceeding $\sqrt{n}$. What does this say about the positive probability in part (1)?

---

5.9

In Section 5.5, we assumed that a variable appears in at most $2^k/50$ clauses. Replace the constant $50$ by the smallest constant you can for the following results:

1. The existence proof using Corollary 5.12.
2. The algorithm of Section 5.5.

---

5.10

Due to J. Naor.

For a graph $G(V,E)$, and any $T\subseteq V$, define the cut function $c(T)$ as the number of edges in $E$ which have exactly one end-point in $T$. For a suitably small function $f(n)$ and large enough even integer $n$, show that there exists a graph $G(V,E)$ with $|V|=n$ such that for every subset $T\subseteq V$ of size $n/2$,

$$\left|c(T)-\frac{n^2}{8}\right|\le f(n).$$

How small can you make the function $f(n)$?

---

5.11

In this problem, we will complete establishing the properties of $\hat{P}(a)$ leading to Theorem 5.15.

1. Show that for a node $a$ at the $i$th level of the computation tree, $\hat{P}(a)$ is of the form

$$N(a)/2^{n-i},$$

where $N(a)$ is a sum of binomial coefficients. Prove that for any node $a$ with children $c$ and $d$,

$$\min \{\hat{P}(c),\hat{P}(d)\}\le \hat{P}(a),$$

and that for any node $a$, we can compute $\hat{P}(a)$ in time polynomial in $n$. 2. Give an upper bound on the running time of the deterministic algorithm.

---

5.12

Show how the method of conditional probabilities can be applied to derandomize the RandAuto algorithm.

---

5.13

Consider the randomized algorithm implicitly described in the proof of Theorem 5.1, which finds a cut of expected size $m/2$ in a graph with $m$ edges. Use the method of conditional probabilities to derandomize this algorithm and obtain a deterministic polynomial time algorithm that computes a cut of size at least $m/2$.

---

5.14

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

An $(n,m)$-safe set instance consists of a universe $U$ of size $n$, a safe set $S\subseteq U$, and $m$ target sets $T_1,\dots ,T_m\subseteq U$ such that

• $|S|=|T_1|=\cdots =|T_m|$,
• and, for $1\le i\le m$, $S\cap T_i=\varnothing$.

An isolator for a safe set instance is a set $I\subseteq U$ that intersects all the target sets but not the safe set. An $(n,m)$-universal isolating family $\mathcal{F}$ is a collection of subsets of $U$ such that $\mathcal{F}$ contains an isolator for any $(n,m)$-safe set instance. Show that there exists a $(n,m)$-universal isolating family $\mathcal{F}$ such that $|\mathcal{F}|$ is polynomially bounded in $n$ and $m$.