# 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)

- (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 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 .

- (b)
- 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.)