Randomized Algorithms (Spring 2010)/Problem Set 3
Problem 1 (20 points)
The Collatz conjecture says that if you start with any positive integer , the following deterministic procedure
will eventually get to 1. Since the Collatz conjecture seems to be hard to prove, consider the following randomized version:
Note that in this game, does not have to be an integer.
- What is the expected value of as a function of and ?
- Show that there is a constant such that is a martingale.
- Assuming that , use the Azuma's inequality to get a bound on the probability that for any fixed .
Problem 2 (20 points)
- 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 be a -regular graph (every vertex has exact neighbors) on vertices. Run the following algorithm on :
- For each vertex , is chosen to a set independently with probability .
- Assuming that is the subgraph of induced by , for each edge , remove one of the vertices from .
- Let be the resulting independent set.
- Derive an upper bound on the probability that this algorithm finds an independent set smaller than .
- Borrow the idea from the theorem of large independent set to prove a similar result for dominating set (a set of vertices such that every vertex is either in or adjacent to a vertex in ). Prove the following theorem:
- Let be a -regular graph on vertices. Then has a dominating set of at most 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 be a cycle of length , where is an integer, let be a partition of the vertices into pairwise disjoint subsets, each of cardinality . Find a proper bound on that no matter how to partition the into , there must be an independent set of containing precisely one vertex from each .
(Hint: use the Lovasz local lemma.)