Random walks on graphs

This page introduces random walks on graphs from the perspectives of grid graphs, sparse graphs, and general graphs, presenting several solution methods and comparing their advantages and disadvantages.

Definition

Given a simple directed graph $G=(V, E)(V=\{v_1, v_2, \cdots, v_{|V|}\})$ and start vertex $s \in V$, terminal vertex $t \in V$, let every edge $e=\left(x, y\right)$ have a positive weight $w_e$ satisfying $\forall x \in V \backslash\left\{t\right\}$, $\sum_{\left(x, y\right) \in E} w_{\left(x, y\right)}=1$. Also, assume that for every vertex $x$ there is a path from $x$ to $t$. A token starts from the start vertex and, each second, from its current vertex $x$, with probability $w_{(x, y)}$, chooses an outgoing edge $\left(x, y\right)$ and moves to $y$. It stops on reaching the terminal vertex. Find the expected time taken.

In fact, this problem can also be written in matrix form. Define the matrix $P$ by:

$$P_{x, y}= \begin{cases} w_{(x, y)} & \text{if } (x, y) \in E \text{ and } x \neq t \\ 0 & \text{if } (x, y) \notin E \text{ or } x=t \\ \end{cases}$$

The required answer is:

$$\sum_{k \geq 0} k \times\left(P^k\right)_{s, t}$$

Here, $\left(P^k\right)_{s, t}$ is the probability of first reaching the terminal vertex after $k$ steps. When the graph is finite and every vertex can reach the terminal vertex, the definition of $P$ shows that all its eigenvalues are less than one, so the answer is guaranteed to converge.

For convenience, unless otherwise specified, this page uses $n$ to denote $|V|$ and $m$ to denote $|E|$.

In addition, a sparse graph on this page means a graph whose numbers of edges and vertices are of the same order.

Grid graphs

Example 1: Circles of Waiting

A token starts at the point $(0,0)$ in the Cartesian plane and moves randomly every second. If it is currently at $(x, y)$, then in the next second it moves with probability $p_1$ to $(x-1, y)$, with probability $p_2$ to $(x, y-1)$, with probability $p_3$ to $(x+1, y)$, and with probability $p_4$ to $(x, y+1)$. It is guaranteed that $p_1+p_2+p_3+p_4=1$. Find the expected time until it moves to a position whose Euclidean distance from the origin is greater than $R$. $0 \leq R \leq 50$, $p_1, p_2, p_3, p_4>0$, and the answer is taken modulo $10^9+7$.

Naive approach

Let $f(i, j)$ denote the expected time, starting from $(i, j)$, to reach a position whose Euclidean distance from the origin is greater than $R$. The recurrence is:

$$f(i, j)= \begin{cases} p_1 f(i-1, j) + p_2 f(i, j-1) + p_3 f(i+1, j) + p_4 f(i, j+1) + 1 & i^2 + j^2 \leq R^2 \\ 0 & i^2 + j^2 > R^2 \end{cases}$$

Because the transitions do not have a topological order, Gaussian elimination is required. The time complexity is $O\left(R^6\right)$, which is too high for this problem.

Direct elimination

Notice that most coefficients in the equations to be eliminated are zero. The complexity can be reduced by computing only positions with nonzero values during elimination.

Consider the elimination process. Eliminate the equations from top to bottom in the coordinate system, and from left to right within each row. Color eliminated equations yellow, points adjacent to yellow points green, and all other points black, as shown below:

Next, eliminate the equation corresponding to the next green cell. In this equation, only the coefficients of the variables corresponding to the green cell and the first black cell below it may be nonzero; likewise, only the equations corresponding to those two cells may have a nonzero coefficient for the variable corresponding to the current cell.

There are only $O(R)$ green cells, so eliminating one equation takes $O\left(R^2\right)$ time. Since there are only $O\left(R^2\right)$ equations, the total time complexity is reduced to $O\left(R^4\right)$, which is sufficient for this problem.

Pivot method

There are $O\left(R^2\right)$ equations and variables. If the size can be reduced to $O(R)$, naive Gaussian elimination will be sufficient.

Take the variable corresponding to the leftmost cell in each row as a pivot; there are $2 R+1$ pivots in total. Express the variables corresponding to all other cells as linear functions of these pivots. Consider the columns from left to right. For each cell $(i, j)$ in the current column, $f(i, j)， f(i-1, j)， f(i, j-1)， f(i, j+1)$ are known linear functions of the pivots. Rearranging the recurrence gives:

$$f(i+1, j)=\frac{f(i, j)-p_1 f(i-1, j)-p_2 f(i, j-1)-p_4 f(i, j+1)-1}{p_3}$$

This gives a linear-function representation of $f(i+1, j)$ in terms of the pivots. If $(i+1, j)$ is already at Euclidean distance greater than $R$ from the origin, we obtain the equation $f(i+1, j)=0$. In the end, there are $2 R+1$ equations, on which we can perform Gaussian elimination.

During the stage of recursively deriving the linear functions of the pivots, there are $O\left(R^2\right)$ variables and deriving each variable takes $O(R)$ time; afterward, the problem size has been reduced to $O(R)$. Both parts take $O\left(R^3\right)$ time, so the total time complexity is also $O\left(R^3\right)$, which is sufficient for this problem.

Comparison of the two approaches

The two approaches are compared below from several perspectives:

In terms of time complexity, the worst-case complexity of the pivot method on a grid graph is $O(n \sqrt{n})$ (it is highest when both the length and width of the grid graph are of order $O(\sqrt{n})$), while the worst-case complexity of direct elimination is $O\left(n^2\right)$. The pivot method is better.

In terms of precision, direct elimination is more accurate than the pivot method for problems requiring real-number calculations rather than calculations modulo a number.

In terms of applicability, the two approaches are suited to different situations.

When the grid graph contains obstacles or some edges have probability $0$, the pivot method needs one additional pivot for every obstacle or edge with probability $0$. When the number of obstacles or edges with probability $0$ exceeds $O(R)$, the time complexity of the pivot method increases, while the time complexity of direct elimination remains unchanged.

However, the pivot method can also eliminate recurrences similar to those on grid graphs, such as $f(i, j)=p_1 f(i+1, j)+p_2 f(i, j+1)+p_3 f(\operatorname{pre}(i, j))+1$, where $\operatorname{pre}(i, j)=(x, y)(x \leq i, y \leq j)$ is given by the problem. The complexity analysis for direct elimination does not apply to this model.

In addition, the determinant of a grid graph's adjacency matrix cannot be computed with the pivot method; only direct elimination can optimize its time complexity.

In summary, each approach has its strengths, and the appropriate one should be chosen after analyzing the specific problem.

Sparse graphs

Example 2: Expected Value

Given a simple, undirected, connected sparse graph $G=(V, E)$, a token starts at $v_1$. Each second it chooses uniformly among the edges incident to its current vertex and moves to the vertex at the other end. Find the expected time to reach $v_n$. $n \leq 2000$, and the answer is taken modulo $p$, where $p$ is a randomly generated prime in the interval $\left[10^9, 1.01 \times 10^9\right]$.

Prerequisites

Definition 4.1. Every polynomial satisfying $p(A) = 0$, namely $p(λ)$, is called an annihilating polynomial of matrix $A$.

Definition 4.2. Let $I_n$ denote the $n$-th order identity matrix. The characteristic polynomial of an $n × n$ matrix $A$ is defined as $p(λ) = \det(λI_n - A)$, where $\det$ denotes the determinant of a matrix. It is easy to see that the characteristic polynomial of an $n$-th order matrix $A$ has degree at most $n$.

Theorem 4.2. (Cayley–Hamilton theorem) The characteristic polynomial of any matrix is an annihilating polynomial for that matrix.

Therefore, the degree of the annihilating polynomial of least degree for an $n$-th order matrix is also at most $n$.

Solving the original problem

Notice that the expected time $E(t)=\sum_{i\geq0}\Pr[t>i]$ is the sum of the probabilities that the walk has not ended after $i$ steps. If we can find these probabilities, summing over all $i ≥ 0$ gives the answer.

Let $f(i, j)$ denote the probability that after $i$ steps the token is currently at $j$ and has never reached $n$. Then:

$$f(i,j)=\sum_{(k,j)\in E}\frac{f(i-1,k)}{\deg_k}(j\neq n)$$

Here $\deg_k$ denotes the degree of $k$.

The transition of $f$ is independent of $i$, so one transition can be viewed as multiplication by a matrix, namely $f{i+1}=f_iM$. Since the least-degree annihilating polynomial of $M$ has degree at most $n$, the shortest recurrence for $f$ also has length at most $n$. Therefore, the shortest recurrence for $\Pr[t>i]=\sum_{j=1}^{n-1}f(i,j)$ also has length at most $n$. We can, in $O(nm)$ time, compute $\Pr[t>0],\Pr[t>1],\cdots,\Pr[t>3n]$; then, in $O(n^2)$ time, use the Berlekamp–Massey algorithm to find the shortest recurrence for $\Pr[t > i]$.

Consider a $k$-th order linear recurrence sequence $a$. Suppose that for $i ≥ i_0$, $a_i=\sum_{j=1}^kc_ja_{i-j}$. Let the generating functions of $a$ and $c$ be $A(x)$ and $C(x)$, respectively. Then $A(x)=A(x)C(x)+A_0(x)$, where $A_0(x)$ is determined by the terms with $i < i_0$.

Returning to the original problem, once we know the shortest recurrence for $\Pr[t > i]$, we can find $C(x)$ and $A_0(x)$ (with the same definitions as in the preceding paragraph). Rearranging gives $A(x)=\frac{A_0(x)}{1-C(x)}$. We seek $\sum_{i\geq0}[x^i]A(x)$, which is clearly $A(1)$. Substituting $x = 1$ solves the original problem. Since the modulus is a random prime, we may assume the denominator is not $0$.

Thus, the problem is solved in $O(nm+n^2)$ time. If the numbers of vertices and edges of $G$ are of the same order, the time complexity here can be regarded as $O(n^2)$.

General graphs

Example 3: Frank

Given a simple strongly connected directed graph $G = (V, E)$, for all $1 ≤ s ≤ n$, $1 ≤ t ≤ n$, and $s ≠ t$, answer the following question: A token starts at $v_s$. Each second it chooses uniformly among the outgoing edges of its current vertex and moves to the vertex at the other end. Find the expected time to reach $v_t$. $3 ≤ n ≤ 400$.

Analysis and transformation

Let $p_{i, j}$ be the probability, when the token is at $i$, of choosing the outgoing edge $(i, j)$ and moving to $j$; in particular, it is $0$ when the edge does not exist. Let $f_{i,j}$ be the expected time for a random walk from $i$ to $j$; in particular, $f_{i,i} = 0$. When $i ≠ j$, the recurrence is:

$$f_{i,j}=1+\sum_{1\leq k\leq n}p_{i,k}f_{k,j}$$

When $i = j$, let $g_i$ denote the expected time for a random walk starting at $i$ to return to $i$ for the first time. Then:

$$f_{i,i}=1-g_i+\sum_{1\le k\le n}p_{i,k}f_{k,i}$$

For clarity, write the recurrence in matrix form. Let $P$ be the transition matrix of the graph, $F$ the answer matrix, $I$ the $n$-th order identity matrix, $J$ the all-ones $n$-th order matrix with entries $1$, and $G$ an $n$-th order matrix satisfying $G_{i,i} = g_i$ and having $0$ elsewhere. Then:

$$F=J-G+PF$$

If we can find $G$, we only need to solve:

$$(I − P)F = J − G$$

Finding G

Definition 5.1. The stationary distribution of an $n$-th order transition matrix $P$ is an $n$-dimensional vector $π$ satisfying $\sum_{i=1}^{n}\pi_{i}=1$ and $πP = π$. Every component of $π$ lies in the interval $[0,1]$.

The meaning of a stationary distribution is easy to see. If at some moment the token has probability $π_i$ of being at $v_i$, then it has the same distribution at every later moment. We can, in $O(n^3)$ time, find $π$ by solving a system with Gaussian elimination. What is the relationship between $π$ and $G$?

Theorem 5.1. For every $1 ≤ i ≤ n$, $π_ig_i = 1$.

Proof

From $F = J - G + PF$, rearranging gives:

$$G = PF + J − F$$

Multiplying both sides on the left by $π$ gives:

$$πG = πPF + πJ − πF$$

By the definition of $π$, we have $πP = π$, so:

$$πG = πJ$$

Therefore:

$$\pi_ig_i=\sum_{j=1}^n\pi_j=1$$

This proves the original proposition.

Thus, by introducing the stationary distribution, in $O(n^3)$ time we can find $G$.

Solving the original problem

While solving the system, we encounter a problem: $(I - P)$ is rank-deficient, so the system cannot be solved by multiplying by an inverse matrix.

Definition 5.2. A directed spanning tree of $G = (V,E)$ rooted at $r\in V$ is a subgraph of $G$, namely $T = (V,A)$, satisfying:

1. For every $i ≠ r$, the out-degree of $i$ is $1$.
2. The out-degree of $r$ is $0$.
3. $T$ contains no cycles.

Lemma 5.1. (The directed matrix-tree theorem) For a directed graph $G$, let $D$ be its out-degree matrix, namely $D_{i,i} = d_i$ and $D_{i,j} = 0(i ≠ j)$, where $d_i$ is the out-degree of $i$, and let $A$ be its adjacency matrix. The number of directed spanning trees rooted at $r$ is the determinant of $D - A$ with row $r$ and column $r$ deleted.

Theorem 5.2. For a strongly connected graph $G = (V,E)$ and its transition matrix $P$, the rank of $(I - P)$ is $n - 1$.

Proof

Multiplying a row of a matrix by a nonzero constant does not change its rank, so, for $(I - P)$, multiply row $i$ by the out-degree of $v_i$ to obtain a new matrix $L$. It suffices to prove that the rank of $L$ is $n - 1$. Since every row of $L$ sums to $0$, summing all column vectors of $L$ gives the zero vector, so these vectors are linearly dependent. so the rank of $L$ is not $n$.
It is easy to see that $L$ equals the out-degree matrix of graph $G$ minus its adjacency matrix. By Lemma 5.1, $L$ with row $i$ and column $i$ deleted yields a determinant equal to the number of directed spanning trees rooted at $v_i$.
Since G is strongly connected, the number of directed spanning trees rooted at any vertex is nonzero, namely not $0$. Thus, after deleting $L$'s row $i$ and column $i$, the matrix remains full rank. Since adding a column cannot decrease rank, $L$ with row $i$ deleted has linearly independent row vectors. Hence the rank of $L$ is $n - 1$. Return to the original problem and consider solving its system. For convenience, write it as $AX = B$, where $A$ and $B$ are known and $X$ is unknown. Since $A$ is rank-deficient, there are infinitely many solutions; first find one particular solution. Perform Gaussian elimination on $A$ and $B$ together. Reduce $A$ by eliminating its first $n - 1$ rows so that only the main diagonal and the $n$-th column can have nonzero entries, and reduce the last row to all $0$, obtaining the following form:

$$\begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & a_1 \\0&1&0&\cdots&0&a_2\\0&0&1&\cdots&0&a_3\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\0&0&0&\cdots&1&a_{n-1}\\0&0&0&\cdots&0&0 \end{bmatrix} X= \begin{bmatrix} b_{1,1}&b_{1,2}&b_{1,3}&\cdots&b_{1,n-1}&b_{1,n} \\b_{2,1}&b_{2,2}&b_{2,3}&\cdots&b_{2,n-1}&b_{2,n} \\b_{3,1}&b_{3,2}&b_{3,3}&\cdots&b_{3,n-1}&b_{3,n} \\\vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\b_{n-1,1}&b_{n-1,2}&b_{n-1,3}&\cdots&b_{n-1,n-1}&b_{n-1,n} \\0&0&0&\cdots&0&0 \end{bmatrix}$$

Set $X_{n,i} = 0$ to obtain a particular solution, denoted by $Y$. Next adjust this particular solution to obtain an actual solution.
Since $X_{n,i} = 0$, the combinatorial interpretation gives $Y_{i,j} = 1 + Y_{j,j} + P_{i,k}X_{k,j}$. It is easy to solve for $X_{i,j} = Y_{i,j} - Y_{j,j}$. This solves the problem in $O(n^3)$ time.

References

1. A brief discussion of random walks on graph models. IOI2019 Chinese National Team Candidate Collection of Papers (pp. 17–26)