A random walk on a graph G = (V, E) is a process that starts at a vertex v0 and at each step picks a random outgoing edge (v, w) from the current vertex and moves to w. The simplest random walk is on a graph with vertices numbered 0, 1, 2, ... k, with vertex i connected to vertex i-1 and i+1. A variant of this has no outgoing edge from 0 and k, or just 0 -> 0 and k -> k, so 0 and k are absorbing states. This can model a gambler playing a fair game who bets $1 at each step. The vertex number represents the gambler's current holdings, 0 represents going broke and k represents reaching the house limit and having to stop.

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