图上随机游走

本页介绍图上随机游走问题。主要从网格图、稀疏图、一般图三个角度进行探究，介绍了解决这类问题的各种方法，并对比了它们在解决各种问题时的优缺点。

定义

给定一张有向简单图 $G=(V, E)(V=\{v_1, v_2, \cdots, v_{|V|}\})$ 和起点 $s \in V$ ，终点 $t \in V$ ，每条边 $e=\left(x, y\right)$ 有正权值，满足 $\forall x \in V \backslash\left\{t\right\}$ ， $\sum_{\left(x, y\right) \in E} w_{\left(x, y\right)}=1$ ，且对于任意点都存在一条从出发到达的路径。有一枚棋子从起点出发，每秒从当前所在点以 $w_{(x, y)}$ 的概率选择出边 $\left(x, y\right)$ 并走向，到达终点则停止，求期望花费时间。

事实上，这个问题也可以写成矩阵的形式。定义矩阵：

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}

要求的答案即为：

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

其中 $\left(P^k\right)_{s, t}$ 表示走了步第一次到达终点的概率。当图有限且所有点都能到达终点时，由的定义可以证明其特征值都小于 1，所以答案一定是收敛的。

为了方便描述，在本页中如无特殊说明，均用代指，代指。

另外，在本页中，稀疏图指边数和点数同阶的图。

网格图

例题 1 Circles of Waiting

有一枚棋子起始被放在平面直角坐标系的点。每秒棋子会随机移动。假设它当前在，它下一秒有的概率移动到，的概率移动到，的概率移动到，的概率移动到。保证。求期望经过多少时间它会移动到一个离原点的欧几里得距离大于的位置。 $0 \leq R \leq 50$ ，，答案对取模。

朴素做法

记表示在棋子在时移动到一个离原点的欧几里得距离大于的位置的期望时间，转移方程为：

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 \\ 0 & i^2 + j^2 > R \end{cases}

由于转移并不存在拓扑序，需要使用高斯消元求解。时间复杂度 $O\left(R^6\right)$ ，无法通过本题。

直接消元法

注意到需要消元的方程的系数大多数都是 0，消元时只对值非 0 的位置进行计算就可以降低复杂度。

考虑消元的过程，将方程按照在坐标系中从上到下，同一层中从左到右的顺序进行消元，将已经消元过的方程染成黄色，与黄色点相邻的点染成绿色，其余点染成黑色，如下图：

graph-random-walk-1

接下来要对下一个绿色格子对应的方程进行消元。在这个方程中，只有绿色格子和它下方的第一个黑色格子对应的变量系数可能不为 0 ; 而只有绿色格子和它下方的第一个黑色格子对应的方程中，当前格子对应的变量系数可能不为 0。

注意到绿色格子只有个，所以单个方程消元的时间复杂度为 $O\left(R^2\right)$ 。一共只有 $O\left(R^2\right)$ 个方程，所以时间复杂度降低为 $O\left(R^4\right)$ ，可以通过本题。

主元法

方程和变量都有 $O\left(R^2\right)$ 个，如果能将规模缩小至，那么朴素的高斯消元就能通过了。

将每行从左到右第一个格子对应的变量设为主元，共个，设法将其他格子对应的变量用关于这些主元的线性函数表示。从左到右逐列考虑，对于当前列的每个格子，注意到 $，，，$ 都是已知的关于主元的线性函数，将转移方程移项，有：

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}

这样我们就能得到关于主元的线性函数表示。如果已经离原点欧几里得距离超过了，则可以得到一个方程：。最终，会得到个方程，对这些方程进行高斯消元即可。

在递推关于主元的线性函数的阶段，共有 $O\left(R^2\right)$ 个变量，递推单个变量需要花费的时间；之后，将问题的规模缩减到了。两部分的时间复杂度均为 $O\left(R^3\right)$ ，总的时间复杂度也为 $O\left(R^3\right)$ ，可以通过本题。

两种做法的对比

下面从多种方面对比两种做法：

从时间复杂度方面，主元法在网格图上的最坏时间复杂度为 $O(n \sqrt{n})$ （当网格图长和宽都为 $O(\sqrt{n})$ 级别时时间复杂度最高），直接消元法在网格图上最坏时间复杂度为 $O\left(n^2\right)$ ，主元法较优。

从精度方面，对于一些需要进行实数计算而不是取模的题目，直接消元法的精度优于主元法。

从适用性方面，两种做法适用于不同的方面。

当网格图中存在障碍或者走某些边的概率为时，对于每个障碍或者概率为的边主元法需要增加一个主元，当障碍或者概率为的边的数量多于时，主元法的时间复杂度会增加，而直接消元法的时间复杂度仍然不变。

但主元法还可以做类似于网格图的转移方程的消元，例如 $f(i, j)=p_1 f(i+1, j)+p_2 f(i, j+1)+p_3 f(\operatorname{pre}(i, j))+1$ ，其中 $\operatorname{pre}(i, j)=(x, y)(x \leq i, y \leq j)$ 是问题给定的值，而直接消元法的复杂度分析在这种模型中并不适用。

除此以外，网格图邻接矩阵行列式的计算，也不能使用主元法，只能用直接消元法来优化时间复杂度。

综上，两种做法各有所长，需要根据具体题目分析采用不同的做法。

稀疏图

例题 2 Expected Value

给定一张简单无向连通稀疏图，有一枚棋子起始被放在，每秒棋子会从与当前点相连的边中等概率选择一条走到出边指向的点，求到达的期望时间。 $n \leq 2000$ ，答案对取模，是在区间 $\left[10^9, 1.01 \times 10^9\right]$ 内随机生成的一个质数。

基础知识

定义 4.1. 所有满足的多项式称为矩阵的零化多项式。

定义 4.2. 记表示阶单位矩阵，定义一个矩阵的特征多项式为 $p(λ) = \det(λI_n - A)$ ，其中 $\det$ 表示一个矩阵的行列式。不难发现，一个阶矩阵的特征多项式的次数不超过。

定理 4.2.（Cayley–Hamilton 定理）任意矩阵的特征多项式是它的零化多项式。

所以，一个阶矩阵的次数最小的零化多项式的次数也不超过。

求解原问题

注意到，期望走的时间 $E(t)=\sum_{i\geq0}\Pr[t>i]$ ，如果我们能求出走了步还没有结束的概率，对所有求和即为答案。

记表示走了步，当前停留在，且没有走到过的概率，那么有：

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

其中 $\deg_k$ 表示的度数。

注意到的转移与无关，可以认为一次转移是乘上了一个矩阵，即 $f{i+1}=f_iM$ 。由于的最小零化多项式次数不超过，所以的最短递推式长度也不超过，故 $\Pr[t>i]=\sum_{j=1}^{n-1}f(i,j)$ 的最短递推式长度也不超过。我们可以在的时间求出 $\Pr[t>0],\Pr[t>1],\cdots,\Pr[t>3n]$ ，然后使用Berlekamp–Massey算法，在的时间内求解出 $\Pr[t > i]$ 的最短递推式。

考虑求一个阶线性递推序列的生成函数。不妨设时 $a_i=\sum_{j=1}^kc_ja_{i-j}$ ，记和的生成函数为和，那么，其中是由的项决定的。

回到原问题，由于我们能求出 $\Pr[t > i]$ 的最短递推式，则我们可以求出和（定义与上一段相同），移项得 $A(x)=\frac{A_0(x)}{1-C(x)}$ 。我们要求的是 $\sum_{i\geq0}[x^i]A(x)$ ，不难发现这个值就等于，将带入原问题求解即可。由于模数是随机质数，可以认为分母不会为。

这样，我们就在的时间复杂度内解决了本题。如果图的点数与边数同阶，本题中时间复杂度可以认为是。

一般图

例题 3 Frank

给定一张简单强连通有向图，对于所有，，。回答下面的问题：有一枚棋子起始被放在，每秒棋子会从当前点的出边中等概率选择一条走到出边指向的点，求到达的期望时间。。

分析和转化

记 $p_{i, j}$ 表示棋子在时，选择出边走到的概率，特别地，当出边不存在时概率为。记 $f_{i,j}$ 表示随机游走到的期望时间，特别地， $f_{i,i} = 0$ 。当时，转移方程为：

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

当时，记表示从开始随机游走，第一次回到的期望时间，那么：

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

为了方便观察，我们将转移方程写成矩阵的形式。记表示这个图的转移矩阵，表示答案矩阵，表示阶单位矩阵，表示阶全矩阵，是一个阶矩阵，满足 $G_{i,i} = g_i$ ，其他位置为，则：

如果我们能求出，那么我们只需要解方程：

G 的求法

定义 5.1. 定义一个阶转移矩阵的稳态分布为一个维向量，满足 $\sum_{i=1}^{n}\pi_{i}=1$ ，。其中，每一维的值都在区间内。

我们很容易找出稳态分布的实际意义。如果某个时刻棋子有的概率停留在，则在之后的任意时刻，棋子仍然满足这个概率分布。我们可以在的时间通过高斯消元解方程来求出，那么与有什么关系呢？

定理 5.1. 对于任意，有。

证明

由，移项得：

两边同时在左边乘上有：

由的定义有，故：

所以：

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

原命题得证。

所以，通过引入稳态分布，我们可以在的时间内求解。

求解原问题

在解方程的过程中，我们发现一个问题：并不满秩，不能通过乘逆矩阵的方法求解。

定义 5.2. 定义一个有向图的以 $r\in V$ 为根的有向生成树是的一个子图，满足：

对于任意，的出度为。
的出度为。
中不存在环。

引理 5.1.（有向图上的矩阵树定理）对于一个有向图，记表示其出度矩阵，即 $D_{i,i} = d_i$ ， $D_{i,j} = 0(i ≠ j)$ ，其中表示的出度，记表示其邻接矩阵，则其以为根的有向生成树个数为去掉第行第列后的行列式。

定理 5.2. 对于一个强连通图的转移矩阵，的秩为。

证明

因为对矩阵某一行乘上一个非零常数其秩不改变，所以我们将的第行乘上的出度，得到一个新的矩阵，只需证明的秩为即可。
由于每行的和均为，对的所有列向量求和，会得到零向量，即这些向量线性相关，所以的秩不为。
不难发现等于图的出度矩阵减去其邻接矩阵，由引理 5.1 得去掉第行第列后行列式表示以为根的有向生成树个数。
由于 G 是强连通的，所以以任意点为根的有向生成树个数均不为，即去掉第行第列之后仍然满秩。
因为加上一列秩不会变小，所以去掉第行后所有行向量线性无关。故的秩为。
回到原问题，考虑求解原问题中的方程。为了方便，我们将方程写成的形式，其中，已知，需要求解。由于不满秩，解有无数个，我们首先求出一组特解。将和一起做高斯消元。把的前行消成只有主对角线和第列有值的形式，最后一行消成全，即下列形式：

\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}

令 $X_{n,i} = 0$ ，可以解出一组特解，记为。接下来将特解调整为真正的解。
注意到 $X_{n,i} = 0$ ，考虑组合意义有 $Y_{i,j} = 1 + Y_{j,j} + P_{i,k}X_{k,j}$ ，不难解出 $X_{i,j} = Y_{i,j} - Y_{j,j}$ 。最终在的时间复杂度内解决了这个问题。

参考

浅谈图模型上的随机游走问题。IOI2019 中国国家候选队论文集（pp. 17-26)

本页面最近更新：2023/9/28 08:28:45，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用