How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver?
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)