expected running time of Randomwalk for k-SAT

Question

model: gambler ruin theorem.

A gambler has $i$ coins initially, in every step, he wins a coin with probability $p$, and loses a coin with probability $1-p$. The expected time that he loses all his coins or wins $n-i$ coins (thus he has $n$ coins totally) is as following: $$E(i)=-\frac{n}{1-2p}\frac{(\frac{1-p}{p})^i-1}{\frac{1-p}{p})^n-1}+\frac{i}{1-2p}$$ this result is from p272 of https://www.emis.de/journals/AMEN/2018/AMEN-171010.pdf

K-SAT problem

https://cstheory.stackexchange.com/questions/1196/what-is-the-k-sat-problem

Assume that there are $n$ variables in K-SAT.

I use $X=(x_i, x_2, \dots x_n)$ to denote the candidate solution of K-SAT.

$X$ is a vector of $n$ dimensions.

$x_i=1$ means the i-th variable is true, $x_i=0$ means the i-th variable is false.

The algorithm:

Apply gambler ruin theorem to analysis

Assuming there is a unique solution $X^*$, and the initial solution $X$ generated by the algorithm has the same $i$ bits with the unique solution $X^*$.

Apparently, when $i$ becomes $0$ or $n$, the algorithm will stopped, and I want to calculate the expected iterations of the algorithm before it stop.

In each iteration, the same bits can be decrease or increase by 1.

and the probability of increase by 1 is at least $p=1/k$. (Because it's k-sat, in each unsatisfied clause, there are at least one variables that doesn't match $X^*$)

The number of same bits between $X^*$ and$X$ incrases by 1, corresponding to the gambler wins a coin. And decreasing by 1 corresponding to the gambler lose a coin.

Thus I think I can use $$E(i)=-\frac{n}{1-2p}\frac{(\frac{1-p}{p})^i-1}{\frac{1-p}{p})^n-1}+\frac{i}{1-2p}$$ to calculate the expected runtime.

but the expected run time is O(n), which is impossible for k-sat problem.

My question is , where am i wrong?

Answer 1

The probability that step 4 brings $X$ closer to the unique satisfying assignment is not $1/k$. Rather, it is at least $1/k$. When $X$ is far away from a satisfying assignment, the probability is likely to be significantly larger. This makes it quite unlikely that you will ever get to a situation in which $Y$ is close to the unique satisfying assignment.

As a concrete illustration, consider the 2CNF containing all $\binom{n}{2}$ clauses of the form $x_i \lor x_j$ and all $2\binom{n}{2}$ clauses of the form $x_i \lor \bar{x}_j$. The only satisfying assignment has all variables positive. Suppose that the current assignment $X$ contains $d$ negative variables. There are $\binom{n}{2} - \binom{n-d}{2}$ unsatisfied clauses, one for each pair of variables, not both of which are positive. In $\binom{d}{2}$ of them, both literals are false, and in $d(n-d)$, one literal is false. Therefore, the probability that we flip a negative variable is $$ \frac{\binom{d}{2} \cdot 1 + d(n-d) \cdot \frac{1}{2}}{\binom{d}{2} + d(n-d)} = \frac{n-1}{2n-d-1} = \frac{1}{2} + \frac{d-1}{2(2n-d-1)}. $$ When $d$ is linear in $n$, this probability is larger than $1/2$ by a constant.

If we repeat the same calculation for $k$CNFs (we have all clause of width $k$ in which at least one variable is positive), the value of $p$ that we get is $$ \frac{\frac{1}{k} \sum_{\ell=1}^k \binom{d}{\ell} \binom{n-d}{k-\ell} \ell}{\sum_{\ell=1}^k \binom{d}{\ell} \binom{n-d}{k-\ell}} = \frac{\frac{d}{k} \sum_{\ell=1}^k \binom{d-1}{\ell-1} \binom{n-d}{k-\ell}}{\sum_{\ell=1}^k \frac{d}{\ell} \binom{d-1}{\ell-1} \binom{n-d}{k-\ell}} = \frac{\frac{1}{k} \binom{n-1}{k-1}}{\binom{n-1}{k-1} + \sum_{\ell=2}^k \frac{1}{\ell} \binom{d-1}{\ell-1} \binom{n-d}{k-\ell}}. $$ This expression shows that when $d$ is small, the probability is indeed close to $1/k$. On the other hand, another expression is $$ \frac{\frac{d}{k} \binom{n-1}{k-1}}{\binom{n}{k} - \binom{n-d}{k}} = \frac{\frac{d}{n} \binom{n}{k}}{\binom{n}{k} - \binom{n-d}{k}} \approx \frac{d}{n} \frac{n^k}{n^k - (n-d)^k} = \frac{d}{n} \frac{1}{1 - (1-d/n)^k}. $$ When $d \approx \alpha n$ for $\alpha$ satisfying $\alpha/(1-\alpha^k) = 1/2$ (for example, when $k = 3$, we get $\alpha \approx 0.45$), $p$ crosses $1/2$, and so the algorithm will start improving the solution in expectation. Consequently, $X$ is unlikely to have more than $0.46n$ many negative variables.

---

When analyzing Schöning's algorithm, we keep track of the distance of $X$ from a fixed satisfying assignment. In the analysis, we say that the behavior of $X$ stochastically dominates a biased random walk with constant $p = 1/k$. This means that $X$ behaves better than such a random walk, and so if we show that a $1/k$-biased random walk hits its target with some probability $q$, then it follows that the actual algorithm also finds a satisfying assignment with probability $q$.