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.

  1. Choose an arbitrary assignment $a$ for $x_1,\dots,x_n$
  2. while $F(a)=0$ do
  3.  select a clause $C$ from $F$ with $C(a)=0$
  4.  select a literal $l$ from $C$
  5.  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:

  1. $t(0)=0$ and $t(n)\le t(n-1)+1$,
  2. $t(i)\le1+\frac12t(i-1)+\frac12t(i+1)$ for $i=1,\dots,n-1$,
  3. $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).


1 Answer 1


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) > P(i \to i+1)$, and $P(i \to i-1) > 0.5, P(i \to i+1) < 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) < 0.5, \quad P(X_{i+1} = j-1 \mid X_i = j) > 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 $> 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)

  • $\begingroup$ How is $t(i-1)\le t(i)\le t(i+1)$? The question lists a counterexample where $t(0)\le t(i)\ge t(n)$ for $i=1,\dots,n-1$ $\endgroup$
    – fuz
    Commented Jan 14, 2015 at 7:34
  • $\begingroup$ @FUZxxl Sorry. It is a mistake. See the edited answer. $\endgroup$
    – hengxin
    Commented Jan 14, 2015 at 8:17
  • $\begingroup$ How does it follow that the randomized algorithm is heading to $X_0$? It could end in any other solution as well. How is $Y$ a pessimistic version of $X$? The solution from which we are $i$ steps away could be much farther away than a different solution. $\endgroup$
    – fuz
    Commented Jan 14, 2015 at 14:04
  • $\begingroup$ @FUZxxl I have tried to explain them. See the edited answer. Is it more reasonable now? $\endgroup$
    – hengxin
    Commented Jan 14, 2015 at 14:32
  • $\begingroup$ @FUZxxl I realized some errors in my answer, mainly about the concepts related to stochastic processes. I have revised them. In addition, I have posted a follow-up problem for the rigorous proof of "pessimistic" at math.se. $\endgroup$
    – hengxin
    Commented Jan 15, 2015 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.