I am given the following randomized algorithm for SAT,
- Input: A satisfiable CNF-formula $\varphi$.
- Output: An assignment $\rho$, such that $\rho \models \varphi$.
The algorithm works as follow:
- Choose an arbitrary assignment $\rho$.
- As long as $\rho \not \models \varphi$
- Choose a clause in $\varphi$ not satisfied by $\rho$ uniformly at random.
- Choose a variable $x\in_{u.a.r}\operatorname{VAR}(C)$.
- Flip the value of $\rho(x)$ (set $\rho(x) = \overline{\rho(x)}$).
We have to prove that for a 2-CNF Formula, the algorithm has polynomial expected running time.
I have proven that for a fixed assignment $\alpha$, such taht $\alpha \models \varphi$, with probability $p \geq 1/2$, after each iteration the number of variables that are assigned different values in $\alpha$ and $\rho$ decrease by one. With probability $1-p$, the assignments $\rho$ and $\alpha$ differ at one extra variable.
Now I have to prove, that the algorithm finished in expected polynomial number of steps. I was able to add one more step of abstraction. Let $X_i$ be the random variable that indicates the number of steps needed to make $\rho = \alpha$, when $\rho$ and $\alpha$ differ by exactly $i$ variables. Then it holds that $$E[X_i] = 1 + p E[X_{i-1}] + (1-p) E[X_{i+1}],$$ and $X_i \leq X_{i+1}$ for all $i$ and $E[X_0]$ is equal to 0. We need to find a polynomial bound for $E[X_i]$.
Since $p\geq 1/2$ and $X_i \leq X_{i+1}$, the following must hold $$E[X_i] \leq 1 + \frac{E[X_{i-1}] + E[X_{i-1}]}{2}$$
Now this can bee seen as walking on the integer line, in each step we move either one step to the left or one step to the right and the probability of moving to the left is at least one half. We have to prove that in expected polynomial many steps (polynomial in the starting position), we reach the number $0$ on the line.
Any help on this problem is very appreciated :)