As a homework we had to prove a set of upper bounds on a given probabilistic algorithm to find a satisfying assignment for a satisfiable 2-CNF formula. The problem is reproduced below. I'm sorry for all the incorrect language; English is not my native language and scientific language is especially difficult for me.
Observe the following algorithm:
input: A 2-CNF formula $F(x_1,\dots,x_n)$ with $n\ge1$ where each clause contains two literals.
- Choose an arbitrary assignment $a$ for $x_1,\dots,x_n$
- while $F(a)=0$ do
- select a clause $C$ from $F$ with $C(a)=0$
- select a literal $l$ from $C$
- flip the value of $l$ in $a$
Let $F$ be a 2-CNF formula in $n$ variables (let each clause have two literals without loss of generality) and let $h$ be an assignment that satisfies $F$. Show that the expected runtime of the aforementioned algorithm is bounded above by a polynomial.
Hint: Show that the following bounds for the expected number of loop iterations $t(i)$, where $i$ is the number of variables in which the initial assignment $a$ differs from $h$, hold:
- $t(0)=0$ and $t(n)\le t(n-1)+1$,
- $t(i)\le1+\frac12t(i-1)+\frac12t(i+1)$ for $i=1,\dots,n-1$,
- $t(i)\le i(2n-i)$ for $i=0,\dots,n$.
It was easy for me to prove upper bounds (1) and (3), where (3) was proved using (1) and (2), but I wasn't able to prove (2). In fact, I believe that (2) might be incorrect.
The idea behind (2) is that when a clause $C$ is chosen in step 3, either one or both literals in $C$ are assigned incorrectly (i.e. not like in $h$) because if both were assigned like in $h$, $C(a)=1$ and $C$ would not have been chosen. Thus, the probability $P$ for increasing the number of correctly assigned literals is greater or equal to $0.5$.
Boundary (2) would work for a probability of exactly $0.5$, but I don't see how this follows. If $t(i)$ would be monotonous, this would be easy to see, but $t(i)$ might not be monotonous. For instance, construct a 2-CNF formula where $h$ and $\bar h$ (where $\bar h$ is $h$ with the value of all literals flipped) are the only satisfying assignments. Obviously, $t(0)=t(n)=0$ and $t(i)>0$ for all $i=1,\dots,n-1$.
Can anybody help me with this proof? I handed in the assignment last Thursday without a conclusive proof for (2), but it bothers me that I was unable to find a solution for (2).