2
$\begingroup$

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:

enter image description here

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?

$\endgroup$
5
  • $\begingroup$ Please edit your question to define all notation and explain your derivation. I don't see how we can identify where you went wrong if you don't provide your reasoning. I don't understand what connection you are drawing between the gambler ruin problem and your algorithm for k-sat, or why you think there is a connection, or why you think those are the correct parameters. Can you provide a self-contained description of the gambler's ruin problem and of your proposed algorithm as well? $\endgroup$
    – D.W.
    Mar 30, 2022 at 18:22
  • 1
    $\begingroup$ @D.W. Thanks for your read and remind, I have edited it. Could please read it again, thank you. $\endgroup$
    – Jxb
    Mar 31, 2022 at 3:53
  • $\begingroup$ You don't have the correct statement of the Gambler's ruin problem. Your expression for the "solution" to the Gambler's ruin problem does not match the statement of the problem as you have described it. The Gambler's ruin problem does not assume you have n coins. It assumes at each step you flip a coin, and is interest in your total winnings. Please look again, then revise your post to correct the error. $\endgroup$
    – D.W.
    Mar 31, 2022 at 5:49
  • $\begingroup$ @D.W. Gambler ruin theorem includes two questions, first is total winnings, and the second is the expected gamblings before the gambler lose all his money or win n money. Here we used the second part. $\endgroup$
    – Jxb
    Mar 31, 2022 at 6:06
  • $\begingroup$ @D.W. I edit it again, could you please take another look, thank you so much! $\endgroup$
    – Jxb
    Mar 31, 2022 at 6:18

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
11
  • $\begingroup$ Thanks a lot, I got it, The mistake I made was that i did not consider the probability of $Y$ will become so small. But there maybe a mistake in your 2CNF instace: the number of unsatisfied clause should be $\tbinom{d}{2}$ $\endgroup$
    – Jxb
    Mar 31, 2022 at 6:49
  • $\begingroup$ Maybe your instace should be changed to$(x_i\vee \overline{x}_j)$ and $(x_i\vee x_j)$ $\endgroup$
    – Jxb
    Mar 31, 2022 at 7:58
  • $\begingroup$ Thanks for the correction! $\endgroup$ Mar 31, 2022 at 10:23
  • $\begingroup$ What's more, the number of unsatisfied clauses maybe not $\tbinom{n}{2}-\tbinom{n-d}{2}$. And your another expression should be changed too? $\endgroup$
    – Jxb
    Apr 1, 2022 at 2:11
  • $\begingroup$ I think it should add up now. $\endgroup$ Apr 1, 2022 at 5:10

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.