How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver? 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
    &emsp;select a clause $C$ from $F$ with $C(a)=0$
    &emsp;select a literal $l$ from $C$
    &emsp;flip the value of $l$ in $a$
    
    
    output: $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)&gt;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).
Denote the probability for increasing from $i$ to $i+1$ by $P(i \to i+1)$ and denote the probability for decreasing from $i$ to $i-1$ by $P(i \to i-1)$.

Consider an assignment $a$. Either one or both literals in the chosen clause $C$ are assigned incorrectly.

Case 1) Only one literal in $C$ is assigned incorrectly: In this case, the algorithm choose a literal $l$ from $C$ randomly. The chances for increasing or decreasing are equal.

Case 2) Both literals in $C$ are assigned incorrectly: Decreasing must happen. (Recall that $i$ denotes the number of the differences.)

Therefore, $P(i \to i-1) &gt; P(i \to i+1)$, and $P(i \to i-1) &gt; 0.5, P(i \to i+1) &lt; 0.5$.



Because $t(i-1) \le t(i) \le t(i+1)$, so we have the upper bound by a little relaxation:

Correction according to "Ref" below: Consider a stochastic process (denoted $X$) $X_0, X_1, X_2, \ldots$ (not necessarily a Markov Chain) over state space $\{0, 1, \cdots, n \}$. The state $i$ here corresponds to the difference $i$. 

The randomized algorithm aims to head to the state $0$ (possibly not monotonically). Although the algorithm could terminate before $X$ reaches $0$ if it finds another satisfying assignment than $h$, but we consider the worst case in which the algorithm only stops when $X_i = 0$. Also notice that $h$ here is arbitrary (meaning that the analysis is applicable to any satisfying assignment argument $h$; hence the worst case.)

Now we have

$$P(X_{i+1} = 1 \mid X_i = 0) = 1;$$
$$P(X_{i+1} = j+1 \mid X_i = j) &lt; 0.5, \quad P(X_{i+1} = j-1 \mid X_i = j) &gt; 0.5 \quad (1 \le j \le n-1).$$

Consider the following Markov Chain (denoted $Y$) $Y_0, Y_1, Y_2, \ldots$:
$$Y_0 = X_0;$$
$$P(Y_{i+1} = 1 \mid Y_i = 0) = 1;$$
$$P(Y_{i+1} = j+1 \mid Y_i = j) = 0.5, \quad P(Y_{i+1} = j-1 \mid Y_i = j) = 0.5 \quad (1 \le j \le n-1).$$

The process $Y$ can be regarded as a pessimistic version of $X$ because $X_i$ which decreases at the next step with probability $&gt; 0.5$ in $X$ now decreases with probability exactly 0.5 in $Y$.
We are only interested in the case of $X$ reaching $X_0$ by decreasing.      


  Therefore, the expected time to reach $X_0$ starting from any state is larger for $Y$ than for $X$.


NOTE: This is quite intuitive; however, the formal proof of this statement will involve some advanced techniques on Markov Chains. I have posted a follow-up problem at math.se).

Taking the place of $X$ by $Y$, we get the upper bound
$$t(i) \le 1 + \frac{1}{2} t(i−1) + \frac{1}{2} t(i+1)$$



Ref: Section 7.1.1 of the book "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Eli Upfal et al. (2005)