4 Going Nowhere: Drift Without Drift
We encounter a surprisingly easy application of drift theory in the absence of drift. An example of a random process which does not exhibit any expected change (drift) is the Gambler's Ruin process. By considering a transformation of the process (essentially: squaring it) the process now exhibits drift in the order of its variance, which is then amenable to analysis with drift theory.
4.1 Unbiased Random Walks
We start by deriving two general corollaries, before we draw conclusions for specific random walks. The first, Theorem 4.1 [Unbiased Random Walk on the Line], concerns completely unbiased random walks. The second, Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier], gives the situation for random walks with one barrier.
Theorem 4.1 [Unbiased Random Walk on the Line].
Let $n \in \natnum$, let $(X_t)_{t \in \natnum}$ be an integrable random process over $[0,n]$, and let $T = \inf\set{t \in \natnum }{ X_t \in \{0, n\}}$. Suppose that there is a $\delta \in \realnum_{+}$ such that, for all $t \lt T$, we have the following conditions (variance, drift).
- (Var)
- $\Var{X_{t+1} - X_t \mid X_0,…,X_t} = \delta$;
- (D)
- $\Ew{X_{t+1} - X_t \mid X_0,…,X_t} = 0$.
Proof.
We consider the process $Y_t = X_t(n-X_t)$.
Note that $T$ is the first time $t \in \natnum$ such that $Y_t = 0$. In the following, we condition on $X_0,…,X_t$, a filtration that $Y_0,…,Y_t$ is adapted to; this allows us to apply our drift theorems by Theorem 8.6 [Conditioning on Filtration vs. History vs. Events] while giving information not only about the value of $Y_t$, but also about $X_t$. Furthermore, for all $s \in [1..n-1]$, we have
\begin{align*}
\Ew{Y_t - Y_{t+1} \mid X_0,…,X_t} &= \Ew{X_{t+1}^2-X_{t}^2 \mid X_0,…,X_t} - n\Ew{X_{t+1}-X_{t} \mid X_0,…,X_t}\\
&= \Ew{X_{t+1}^2 \mid X_0,…,X_t} - X_t^2 = \Var{X_{t+1} \mid X_0,…,X_t}\\
&= \Var{X_{t+1} - X_t \mid X_0,…,X_t} = \delta.
\end{align*}
Thus, we have a drift of $\delta$ towards $0$. Since $Y_0 = X_0(n - X_0)$, the theorem follows from an application of Theorem 2.1 [Additive Drift, Upper Bound].
Since the proof is based on the additive drift theorem, a lower bound of $\delta$ on the variance is enough for an upper bound on the expected first-hitting time and vice versa.
Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier].
Let $n \in \natnum$, let $(X_t)_{t \in \natnum}$ be an integrable random process over $[0,n]$, and let $T = \inf\set{t \in \natnum }{ X_t = n}$.
Suppose that there is a $\delta \in \realnum_{+}$ such that, for all $t \lt T$, we have the following conditions (variance, drift).
- (Var)
- $\Var{X_{t+1} - X_t \mid X_0,…,X_t} \geq \delta$;
- (D)
- $\Ew{X_{t+1} - X_t \mid X_0,…,X_t} \geq 0$.
Proof.
We consider the process $Y_t = n^2 - X_t^2$. Note that $T$ is the first time such that $Y_t = 0$. Further note that, from (D) we get, for all $t \lt T$,
\begin{equation}
\Ew{X_{t + 1} \mid X_0,…, X_t}^2 \geq X_t^2.\tag{$\ast$}
\end{equation}
As in the previous proof, we condition on $X_0,…,X_t$ and implicitly use Theorem 8.6 [Conditioning on Filtration vs. History vs. Events]. We now have
\begin{align*}
\Ew{Y_t - Y_{t+1} \mid X_0,…, X_t} & = \Ew{X_{t+1}^2 - X_{t}^2 \mid X_0,…, X_t}\\
& = \Ew{X_{t+1}^2 \mid X_0,…, X_t} - X_t^2\\
&\eqnComment{$(\ast)$}{\geq} \Ew{X_{t+1}^2 \mid X_0,…, X_t} - \Ew{X_{t + 1} \mid X_0,…, X_t}^2\\
&= \Var{X_{t+1} \mid X_0,…, X_t}\\
&= \Var{X_{t+1} - X_t \mid X_0,…, X_t}\\
&\geq \delta.
\end{align*}
Thus, we have a drift of at least $\delta$ towards $0$. Since $Y_0 = n^2 - X_0^2$, the theorem follows from an application of Theorem 2.1 [Additive Drift, Upper Bound].
Note that in neither of the two preceding theorems is the process allowed to overshoot the target. Using an additive drift theorem that allows for overshooting, like Theorem 5.3 [Additive Drift, Upper Bound with Overshooting], one can derive corresponding extensions of the above two theorems with essentially the same proof. We note that Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier] is tight with the following example.
Example 4.3 [Fair Random Walk].
Let $(X_t)_{t \in \natnum}$ be the time-homogeneous Markov-chain on $[0..n]$, where, for all $t \in \natnum$,
- for all $i \in [1..n-1]$, $\Pr{X_{t + 1} = i+1 \mid X_t = i} = 1/2 = \Pr{X_{t + 1} = i-1 \mid X_t = i}$;
- the state $0$ is reflective, that is, $\Pr{X_{t + 1} = 1 \mid X_t = 0} = 1$; and
- the state $n$ is absorbing.
4.2 Analysis of Concrete Unbiased Random Walks
In this section we see several domains in which we apply our theorems about unbiased random walks. The Gambler's Ruin in Theorem 4.4 [Gambler's Ruin] is the most straightforward application of Theorem 4.1 [Unbiased Random Walk on the Line]. A more intricate application is given in Theorem 4.5 [The Recolour Algorithm], where it is used to bound the expected run time for an algorithm to find a certain coloring of a graph.
Regarding Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier], in Theorem 4.6 [Random 2-SAT] we use it to derive an upper bound on the time for an algorithm to find a satisfying assignment for a 2-SAT formula.
Regarding Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier], in Theorem 4.6 [Random 2-SAT] we use it to derive an upper bound on the time for an algorithm to find a satisfying assignment for a 2-SAT formula.
We start with the gambler's ruin, a random walk on the line. It starts at $n$, going either one step to the left or one step to the right, each with probability $1/2$, modeling winning or losing a fair coin toss to either win or lose a coin. The question of how long it takes to either be broke ($0$ coins left) or double the starting number of coins is the simplest setting of an unbiased random walk. This process also goes by many other names, such as drunkard's walk, random walk on a line, or one-dimensional random walk.
Theorem 4.4 [Gambler's Ruin].
Suppose we start with $n \in \natnum$ coins and, in each iteration, uniformly at random either gain a coin or lose a coin. Then, after an expected number of exactly $n^2$ iterations, we are either broke or have reached a total of $2n$ coins.
Proof.
For all $t \in \natnum$, let $X_t$ be the random sequence of the number of coins after $t$ iterations. We have
$$
\Ew{X_{t+1} - X_t \mid X_0,…,X_t} = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot (-1) = 0.
$$
Furthermore, we have
$$
\Var{X_{t+1} - X_t \mid X_0,…,X_t} = \frac{1}{2} \cdot 1^2 + \frac{1}{2} \cdot (-1)^2 = 1.
$$
Thus, we can now apply Theorem 4.1 [Unbiased Random Walk on the Line] to get the desired result.
Our next example considers the analysis of the run time of an algorithm. McDiarmid [McD93A Random Recolouring Method for Graphs and Hypergraphs. Colin McDiarmid. Combinatorics, Probability and Computing 1993.] studies the following simple randomized algorithm called Recolour, for coloring a given undirected graph $G$ with two colors such that it contains no monochromatic triangle (a subgraph on three pairwise connected vertices which are all colored with the same color). Recolour starts with an arbitrary $2$-coloring of $G$. At every step, it checks whether the current coloring has a monochromatic triangle. If so, Recolour changes the color of one of the vertices of this triangle uniformly at random. Otherwise, the $2$-coloring has no monochromatic triangles and it is the output of Recolour.
McDiarmid shows that, when Recolour is applied to a 3-colorable graph $G$ (a graph that can be colored with three colors so that no two neighbors share a color), it returns a 2-coloring of $G$ with no monochromatic triangle in expected time $\bigO{n^4}$. His analysis shows that the expected run time of the algorithm is bounded above by the expected hitting time of a random walk on the line with two absorbing states — which is exactly the setting of Theorem 4.1 [Unbiased Random Walk on the Line]. This analysis in turn relies on previous results on one-dimensional random walks, which usually require lengthy calculations.
We present a simple and self-contained proof of the $\bigO{n^4}$ expected run time of the Recolour algorithm for finding a 2-coloring with no monochromatic triangles on 3-colorable graphs. Our proof follows the proof of McDiarmid [McD93A Random Recolouring Method for Graphs and Hypergraphs. Colin McDiarmid. Combinatorics, Probability and Computing 1993.] to reduce the problem to an unbiased random walk on the line and then uses Theorem 4.1 [Unbiased Random Walk on the Line]. A similar analysis can be used to derive an upper bound on the run time of Recolour on hypergraph colorings.
McDiarmid shows that, when Recolour is applied to a 3-colorable graph $G$ (a graph that can be colored with three colors so that no two neighbors share a color), it returns a 2-coloring of $G$ with no monochromatic triangle in expected time $\bigO{n^4}$. His analysis shows that the expected run time of the algorithm is bounded above by the expected hitting time of a random walk on the line with two absorbing states — which is exactly the setting of Theorem 4.1 [Unbiased Random Walk on the Line]. This analysis in turn relies on previous results on one-dimensional random walks, which usually require lengthy calculations.
We present a simple and self-contained proof of the $\bigO{n^4}$ expected run time of the Recolour algorithm for finding a 2-coloring with no monochromatic triangles on 3-colorable graphs. Our proof follows the proof of McDiarmid [McD93A Random Recolouring Method for Graphs and Hypergraphs. Colin McDiarmid. Combinatorics, Probability and Computing 1993.] to reduce the problem to an unbiased random walk on the line and then uses Theorem 4.1 [Unbiased Random Walk on the Line]. A similar analysis can be used to derive an upper bound on the run time of Recolour on hypergraph colorings.
Theorem 4.5 [The Recolour Algorithm].
The expected run time of Recolour on a 3-colorable graph with $n \in \natnum_+$ vertices is $\bigO{n^4}$.
Proof.
Let $G=(V,E)$ be a 3-colorable graph, and let $\chi\colon V\rightarrow \{1, 2, 3\}$ be a 3-coloring of $G$. Let $U = \set{v\in V }{ \chi(v) \in \{1, 2\} }$ be the set of all vertices which are colored with colors $1$ and $2$. Note that any 2-coloring of $G$ that agrees with $\chi$ on the vertices from $U$ is a 2-coloring of $G$ with no monochromatic triangles. Thus, the run time of Recolour is bounded from above by the expected time that Recolour takes to find such a coloring.
Let $\chi_t$ be the 2-coloring found by Recolour at time $t \in \natnum$. Let $Y_t$ be the number of vertices $u\in U$ such that $\chi_t(u)=\chi(u)$. The algorithm terminates when $Y_t \in \{0,|U|\}$, since agreeing on all vertices of $U$ is a coloring without monochromatic triangles, but disagreeing on all vertices from $U$ is also such a valid coloring, since the use of the colors is symmetric. Let $s \in [1.. |U| - 1]$ denote an outcome of $Y_t$ before the algorithm terminates. We then have that $\Pr{Y_{t+1}=Y_t+1 \mid Y_t = s} = 1/3$, as, for every monochromatic triangle, there is exactly one vertex in $u \in U$ with $\chi_t(u) \neq \chi(u)$ which can be recolored to obtain another vertex where the colors match. Similarly, $\Pr{Y_{t+1}=Y_t-1 \mid Y_t = s} = 1/3$. Thus, $Y_t$ is an unbiased random walk on the line with first-hitting time $T = \inf \set{t \in \natnum }{ Y_t \in \{0,|U|\} }$. We have $$ \Var{Y_{t+1} - Y_t \mid Y_0,…,Y_t} = \frac{1}{3} \cdot 1^2 + \frac{1}{3} \cdot 0^2 + \frac{1}{3} \cdot (-1)^2 = \frac{2}{3}. $$ Applying Theorem 4.1 [Unbiased Random Walk on the Line] we get $$ \Ew{T}=\frac{3\Ew{Y_0(|U| - Y_0)}}{2}\leq \frac{3n^2}{8}. $$ At each step, the algorithm requires $\bigO{n^2}$ time to find a monochromatic triangle and modify this to obtain a new coloring, which concludes the proof.
Let $\chi_t$ be the 2-coloring found by Recolour at time $t \in \natnum$. Let $Y_t$ be the number of vertices $u\in U$ such that $\chi_t(u)=\chi(u)$. The algorithm terminates when $Y_t \in \{0,|U|\}$, since agreeing on all vertices of $U$ is a coloring without monochromatic triangles, but disagreeing on all vertices from $U$ is also such a valid coloring, since the use of the colors is symmetric. Let $s \in [1.. |U| - 1]$ denote an outcome of $Y_t$ before the algorithm terminates. We then have that $\Pr{Y_{t+1}=Y_t+1 \mid Y_t = s} = 1/3$, as, for every monochromatic triangle, there is exactly one vertex in $u \in U$ with $\chi_t(u) \neq \chi(u)$ which can be recolored to obtain another vertex where the colors match. Similarly, $\Pr{Y_{t+1}=Y_t-1 \mid Y_t = s} = 1/3$. Thus, $Y_t$ is an unbiased random walk on the line with first-hitting time $T = \inf \set{t \in \natnum }{ Y_t \in \{0,|U|\} }$. We have $$ \Var{Y_{t+1} - Y_t \mid Y_0,…,Y_t} = \frac{1}{3} \cdot 1^2 + \frac{1}{3} \cdot 0^2 + \frac{1}{3} \cdot (-1)^2 = \frac{2}{3}. $$ Applying Theorem 4.1 [Unbiased Random Walk on the Line] we get $$ \Ew{T}=\frac{3\Ew{Y_0(|U| - Y_0)}}{2}\leq \frac{3n^2}{8}. $$ At each step, the algorithm requires $\bigO{n^2}$ time to find a monochromatic triangle and modify this to obtain a new coloring, which concludes the proof.
The analysis of the Recolour algorithm for finding 2-colorings with no monochromatic triangles appears as an exercise in [Upf05Probability and computing: randomized algorithms and probabilistic analysis. Michael Mitzenmacher and Eli Upfal. Cambridge University Press 2005.].
In the final example of this section, we consider finding satisfying assignments of 2-SAT formulas. Papadimitriou [Pap91On Selecting a Satisfying Truth Assignment (Extended Abstract) Christos H. Papadimitriou. FOCS 1991.] studies the following simple randomized algorithm that returns a satisfying assignment of a satisfiable 2-SAT formula $\phi$ with $n$ variables and $m$ clauses within $\bigO{n^2m}$ time in expectation. The algorithm starts with a random assignment of the variables of $\phi$. At every step, the algorithm checks whether there is an unsatisfied clause for this assignment. If so, the algorithm changes the assignment of one of the variables of this assignment uniformly at random. Otherwise, the assignment is satisfying and it is the output of the algorithm.
The analysis given is similar to the Recolour algorithm, and it also relies on the previous results on one-dimensional random walks. An extensive analysis of this algorithm appears in [Upf05Probability and computing: randomized algorithms and probabilistic analysis. Michael Mitzenmacher and Eli Upfal. Cambridge University Press 2005.]. Here, we present a simpler proof that uses Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier].
Theorem 4.6 [Random 2-SAT].
The randomized 2-SAT algorithm, when run on a satisfiable 2-SAT formula over $n \in \natnum_+$ variables and $m \in \natnum_+$ clauses, terminates in $\bigO{n^2m}$ time in expectation.
Proof.
Let $\phi$ be a satisfiable 2-SAT formula and $a$ a satisfying assignment. At each time step $t \in \natnum_+$, the randomized 2-SAT algorithm finds a (not necessarily satisfying) assignment $a_t$. Let $X_t$ be the random variable denoting the number of variables that have the same truth assignment in both $a$ and $a_t$. Let $T$ be the first time the algorithm reaches a satisfying assignment for $\phi$. Assume that a clause $x \vee y$ is not satisfied by $a_t$. Since $a$ is a satisfying assignment, $a$ and $a_t$ differ in the assignment of at least one of the variables in this clause. Thus,
\begin{align*}
\Pr{X_{t+1} = X_t+1 \mid X_0, …, X_t} &\geq 1/2;\mbox{ and}\\
\Pr{X_{t+1} = X_t-1 \mid X_0, …, X_t} &\leq 1/2.
\end{align*}
When $a_t=a$, the algorithm terminates.
By Theorem 4.2 [Unbiased Random Walk on the Line, One Barrier] with variance bounded by $1$, we have $\Ew{T} \leq n^2$. In order to transition from $a_t$ to $a_{t+1}$, the algorithm requires $\bigO{m}$ time (since the 2-SAT formula has $m$ distinct clauses), concluding the proof.
This work is licensed as Creative Commons Attribution - ShareAlike 4.0 International.
All mathematical statement in this script are freely usable, of course. As a collection and with comments they are licensed as stated above.