# Randomized Algorithms (Spring 2010)/Problem Set 3

## Problem 1 (20 points)

The Collatz conjecture says that if you start with any positive integer ${\displaystyle x_{0}}$, the following deterministic procedure

${\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}}}$

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

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

Note that in this game, ${\displaystyle x_{t}}$ does not have to be an integer.

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

## 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 ${\displaystyle G(V,E)}$ be a ${\displaystyle d}$-regular graph (every vertex has exact ${\displaystyle d}$ neighbors) on ${\displaystyle n}$ vertices. Run the following algorithm on ${\displaystyle G}$:
1. For each vertex ${\displaystyle v\in V}$, ${\displaystyle v}$ is chosen to a set ${\displaystyle S}$ independently with probability ${\displaystyle {\frac {1}{d}}}$.
2. Assuming that ${\displaystyle G[S]}$ is the subgraph of ${\displaystyle G}$ induced by ${\displaystyle S}$, for each edge ${\displaystyle (u,v)\in G[S]}$, remove one of the vertices ${\displaystyle \{u,v\}}$ from ${\displaystyle S}$.
Let ${\displaystyle S^{*}}$ be the resulting independent set.
Derive an upper bound on the probability that this algorithm finds an independent set smaller than ${\displaystyle {\frac {n(1-\epsilon )}{2d}}}$.
(b)
Borrow the idea from the theorem of large independent set to prove a similar result for dominating set (a set ${\displaystyle D}$ of vertices such that every vertex is either in ${\displaystyle D}$ or adjacent to a vertex in ${\displaystyle D}$). Prove the following theorem:
Let ${\displaystyle G(V,E)}$ be a ${\displaystyle d}$-regular graph on ${\displaystyle n}$ vertices. Then ${\displaystyle G}$ has a dominating set of at most ${\displaystyle {\frac {n(1+\ln(d+1))}{d+1}}}$ 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 ${\displaystyle G(V,E)}$ be a cycle of length ${\displaystyle cn}$, where ${\displaystyle c}$ is an integer, let ${\displaystyle V=V_{1}\cup V_{2}\cup \cdots \cup V_{n}}$ be a partition of the ${\displaystyle cn}$ vertices into ${\displaystyle n}$ pairwise disjoint subsets, each of cardinality ${\displaystyle c}$. Find a proper bound on ${\displaystyle c}$ that no matter how to partition the ${\displaystyle V}$ into ${\displaystyle V_{1},V_{2},\cdots ,V_{n}}$, there must be an independent set of ${\displaystyle G}$ containing precisely one vertex from each ${\displaystyle V_{i}}$.

(Hint: use the Lovasz local lemma.)