This can be appl;ied to solving the 2-SAT problem in the following way:

We are trying to find a satisfying assignment for a Boolean formula on n variables, where the formula is the conjunction (AND) of clauses, each of which is the disjunction (OR) of two literals (variable or negation). Start with a random assignment to the n variables, and at each step pick an unsatisified clause and change one of the variable assignments so that this clause is satisfied.

Pick one satisfying assignment as the goal, and let i be the number of variables in the current assignment that have the same setting as the goal. At each step, i changes to i-1 or i+1 and when i reaches n the process can stop, so this is like the random walk above with n an absorbing state and 0 a non-absorbing state.

**Reference:** Randomized Algorithms

Rajeev Motwani and Prabhakar Raghavan

Cambridge University Press, 1995