Randomized Algorithms (Spring 2010)/Problem Set 3

Problem 1 (20 points)

The Collatz conjecture says that if you start with any positive integer [math]\displaystyle{ x_0 }[/math], the following deterministic procedure

[math]\displaystyle{ x_{t+1}= \begin{cases} (3x_t+1)/2 & \mbox{if }x_t\mbox{ is odd},\\ x_t/2 & \mbox{if }x_t\mbox{ is even}, \end{cases} }[/math]

will eventually get to 1. Since the Collatz conjecture seems to be hard to prove, consider the following randomized version:

[math]\displaystyle{ x_{t+1}= \begin{cases} 3x_t/2 & \mbox{with probability }1/2,\\ x_t/2 & \mbox{with probability }1/2. \end{cases} }[/math]

Note that in this game, [math]\displaystyle{ x_t }[/math] does not have to be an integer.

1. What is the expected value of [math]\displaystyle{ x_t }[/math] as a function of [math]\displaystyle{ t }[/math] and [math]\displaystyle{ x_0 }[/math]?
2. Show that there is a constant [math]\displaystyle{ c }[/math] such that ln [math]\displaystyle{ x_t - ct }[/math] is a martingale.
3. Assuming that [math]\displaystyle{ x_0 = 1 }[/math], use the Azuma's inequality to get a bound on the probability that [math]\displaystyle{ x_t ≥ N }[/math] for any fixed [math]\displaystyle{ N \gt 0 }[/math].

Problem 2 (20 points)

(a)

Consider the theorem of large independent set in Lecture 8. The proof of the theorem describes a probabilistic experiment which generates independent set with large expected cardinality. Now we wish to turn this experiment to a randomized algorithm. Consider the special case that the graph is regular.

Let [math]\displaystyle{ G(V,E) }[/math] be a [math]\displaystyle{ d }[/math]-regular graph (every vertex has exact [math]\displaystyle{ d }[/math] neighbors) on [math]\displaystyle{ n }[/math] vertices. Run the following algorithm on [math]\displaystyle{ G }[/math]:

1. For each vertex [math]\displaystyle{ v\in V }[/math], [math]\displaystyle{ v }[/math] is chosen to a set [math]\displaystyle{ S }[/math] independently with probability [math]\displaystyle{ \frac{1}{d} }[/math].
2. Assuming that [math]\displaystyle{ G[S] }[/math] is the subgraph of [math]\displaystyle{ G }[/math] induced by [math]\displaystyle{ S }[/math], for each edge [math]\displaystyle{ (u,v)\in G[S] }[/math], remove one of [math]\displaystyle{ \{u,v\} }[/math] from [math]\displaystyle{ S }[/math].

Let [math]\displaystyle{ S^* }[/math] be the resulting independent set.

Derive an upper bound on the probability that this algorithm finds an independent set smaller than [math]\displaystyle{ \frac{n(1-\epsilon)}{2d} }[/math].

(b)

Borrow the idea from the theorem of large independent set to prove a similar result for dominating set (a set [math]\displaystyle{ D }[/math] of vertices such that every vertex is either in [math]\displaystyle{ D }[/math] or adjacent to a vertex in [math]\displaystyle{ D }[/math]). Prove the following theorem:

Let [math]\displaystyle{ G(V,E) }[/math] be a [math]\displaystyle{ d }[/math]-regular graph on [math]\displaystyle{ n }[/math] vertices. Then [math]\displaystyle{ G }[/math] has a dominating set of at most [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math] vertices.

(Hint: As the probabilistic experiment for generating an independent set, consider sampling a set of vertices and then altering it to a dominating set.)

Problem 3 (10 points)

Let [math]\displaystyle{ G(V,E) }[/math] be a cycle of length [math]\displaystyle{ cn }[/math], where [math]\displaystyle{ c }[/math] is an integer, let [math]\displaystyle{ V=V_1\cup V_2\cup\cdots\cup V_n }[/math] be a partition of the [math]\displaystyle{ cn }[/math] vertices into [math]\displaystyle{ n }[/math] pairwise disjoint subsets, each of cardinality [math]\displaystyle{ c }[/math]. Find a proper bound on [math]\displaystyle{ c }[/math] that no matter how to partition the [math]\displaystyle{ V }[/math] into [math]\displaystyle{ V_1, V_2,\cdots, V_n }[/math], there must be an independent set of [math]\displaystyle{ G }[/math] containing precisely one vertex from each [math]\displaystyle{ V_i }[/math].

(Hint: use the Lovasz local lemma.)