Randomized Algorithms (Spring 2010)/Problem Set 3

Problem 1 (10 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. }[/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].