随机游走：反正下一步也不知道往哪走

· · 算法·理论

随机游走这东西，说白了就是乱走。

站在一个点上，每次随机挑条能走的边继续走。可能一路往前，也可能绕一大圈又回到原地。听起来挺随便，但题做起来一点都不随便。

因为图上有环，状态很容易互相依赖。你算我，我又算你，绕一圈回来发现谁都算不出来，最后只能老老实实列方程。

所以随机游走题做多了以后，会发现经常绕不开几件事：状态怎么设，方程怎么列，列完以后怎么解。

这篇就把我目前遇到过的几种套路记一下，省得以后题目在图上乱走，我也跟着一起乱走。

符号约定

为了后面写起来方便，本文统一作如下约定：

另外，如果没有特别说明，树都默认先选定一个根，再按照父子关系进行讨论。

一、基础

1. 期望的线性性

先记一个最基本的东西：期望具有线性性。

对于随机变量 X,Y，有 E(X+Y)=E(X)+E(Y)。

更一般地，有 E\left(\sum_{i=1}^{n}X_i\right)=\sum_{i=1}^{n}E(X_i)。

而且这个性质不要求这些随机变量相互独立。

所以碰到一个比较大的期望时，经常可以先把它拆成很多小部分，每部分单独算，最后直接加起来。

2. 一步分析

随机游走列方程时，最常用的思路就是先看下一步。

设当前在节点 u，下一步有 p_{u,v} 的概率走到节点 v。如果走到 v 以后还需要 f_v 的期望代价，那么直接按照下一步去了哪里分类即可。

比如每走一步代价为 1：

f_u=1+\sum_{v:u\to v}p_{u,v}f_v

说白了就是：先走一步，再算剩下的。

后面大部分期望转移式，其实都是这个套路。

3. 常见状态设计

随机游走题里，常见的状态大概有下面几种：

状态怎么设，主要还是看题目问什么。问还要走多久，就考虑到终点的期望；问某个点会经过多少次，就考虑点的期望经过次数；一个位置不够描述，那就把状态升维。

随机游走还有一个很重要的特点：下一步怎么走，只和当前所在的状态有关，和之前是怎么走到这里的无关。

所以一旦走到节点 u，后面的过程就可以直接用状态 f_u 来描述，不需要管前面绕了多少圈。

不过要注意，随机过程本身虽然只看当前状态，列出来的方程却可能互相依赖。图上有环时，f_u 依赖 f_v，f_v 又可能绕回来依赖 f_u，所以才会需要高斯消元。

二、一般图与网格图上的随机游走

一般图上的随机游走，最直接的思路就是设状态，然后按每一步的转移概率列方程。

麻烦的地方是图上有环。一个状态可能依赖另一个状态，绕一圈以后那个状态又依赖回来，所以普通 dp 往往没法直接做。

这种时候一般就要列线性方程组，再高斯消元；如果图或者矩阵本身有特殊结构，还可以继续优化。

1. 到达终点的期望步数

这类题一般设 f_u 表示从节点 u 出发，到达终点的期望步数。

设终点为 t，那么 f_t=0。

如果每走一步的代价都是 1，那么从 u 出发，先花一步走到某个相邻节点 v，接下来还要走 f_v 的期望步数，所以：

f_u=1+\sum_{v:u\to v}p_{u,v}f_v

更一般地，如果边 (u,v) 的代价为 w_{u,v}，那么：

f_u=\sum_{v:u\to v}p_{u,v}(f_v+w_{u,v})

其中 p_{u,v} 表示从 u 走到 v 的概率。

例题 2.1 CF24D Broken robot

题意

给一张 n\times m 的网格图，机器人初始在 (x,y)。

每秒它会等概率向左、向右、向下走，或者原地不动，但不能走出矩阵。求它走到最后一行的期望时间。

做法

设 f_{i,j} 表示从 (i,j) 到最后一行的期望时间，则有：

f_{i,j}= \begin{cases} \displaystyle 1+\frac{f_{i,j}+f_{i+1,j}}{2},&m=1\\[8pt] \displaystyle 1+\frac{f_{i,j}+f_{i,2}+f_{i+1,j}}{3},&j=1\\[8pt] \displaystyle 1+\frac{f_{i,j}+f_{i,m-1}+f_{i+1,j}}{3},&j=m\\[8pt] \displaystyle 1+\frac{f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j}}{4},&1<j<m \end{cases}

边界为 f_{n,j}=0。

式子不难写，问题是同一行里的状态会互相依赖，没法直接 dp。

整个网格一共有 nm 个状态，最后一行已经知道，所以真正的未知数有 (n-1)m 个。全部丢进去高斯消元当然能做，但复杂度是 O(n^3m^3)，肯定过不了。

于是把某一行的方程写成矩阵看看：

\left[ \begin{array}{cccccc|c} 2 & -1 & 0 & 0 & \cdots & 0 & 3+f_{i+1,1} \\ -1 & 3 & -1 & 0 & \cdots & 0 & 4+f_{i+1,2} \\ 0 & -1 & 3 & -1 & \cdots & 0 & 4+f_{i+1,3} \\ 0 & 0 & -1 & 3 & \ddots & 0 & 4+f_{i+1,4} \\ \vdots & \vdots & \vdots & \ddots & \ddots & -1 & \vdots \\ 0 & 0 & 0 & 0 & -1 & 2 & 3+f_{i+1,m} \end{array} \right]

可以发现这是一个三对角矩阵。

从左往右消元时，每一行只需要消掉左边一个 -1，所以一整行只要 O(m)。再从右往左回代，就能求出这一行所有的 f_{i,j}。

总复杂度为 O(nm)。

2. 点与边的期望经过次数

还有一类题问的是：某个点或者某条边，整个过程中期望会经过多少次。

设 f_u 表示节点 u 被经过的期望次数。

每经过一次节点 v，都有 p_{v,u} 的概率下一步走到 u，所以：

f_u=[u=s]+\sum_{v:v\to u}f_vp_{v,u}

这里起点 s 一开始就已经被经过一次，所以要额外加上 [u=s]。

如果题目问的是边，可以先把边的期望转成点的期望。

如果每次在节点 u 等概率选择一条出边，那么有向边 u\to v 的期望经过次数就是 \frac{f_u}{d_u}。

对于无向边 (u,v)，两个方向都可能走，所以要加起来，也就是 \frac{f_u}{d_u}+\frac{f_v}{d_v}。

注意，如果某个点是终点，到达以后立刻停止，那就不能再算从这个点往外走的贡献。

例题 2.2 P3232 [HNOI2013 / JSOI2013] 游走

题意

给一张无向图，小 Z 从 1 号点开始随机游走，到 n 号点停止。

每走过一条边，就获得这条边边权大小的分数。现在要给 m 条边分配 1 到 m 互不相同的权值，使最后得到的期望分数最小。

做法

设 f_u 表示节点 u 被经过的期望次数。

对每个非终点列出期望方程，高斯消元求出所有 f_u。知道点的期望以后，就能算出每条边的期望经过次数。

经过次数越多的边，给越小的权值即可。

这里要注意，终点 n 到达以后就停止，所以不能再从 n 往外转移。

总结一下，两种状态的区别就是：求从 u 到终点，看 u\to v；求 u 的经过次数，看 v\to u。

一个看接下来往哪走，一个看谁能走到这里。

3. 无法直接线性递推的贡献

有些题问的既不是步数，也不是点或者边经过多少次，而是路径上的某种特殊信息。

如果这个贡献不能直接相加，那期望线性性也就没法直接套。这时候一般要先想办法拆贡献，再把它转成概率或者普通期望。

例题 2.3 P3211 [HNOI2011] XOR 和路径

题意

给一张带权无向连通图，从 1 号点开始随机游走，每次等概率选择一条相邻边，走到 n 号点以后停止。

求经过的所有边权异或和的期望。

做法

异或不能直接按普通加法来算期望，所以考虑按二进制位拆开。

枚举第 k 位，设 f_u 表示从节点 u 出发，最终走到 n 时，这一位异或结果为 1 的概率。

如果从 u 走到相邻节点 v：

所以对于 u\neq n：

f_u=\frac{1}{d_u}\left(\sum_{\substack{v\sim u\\w_{u,v}^{(k)}=0}}f_v+\sum_{\substack{v\sim u\\w_{u,v}^{(k)}=1}}(1-f_v)\right)

边界为 f_n=0，因为走到 n 以后就停止，不会再经过新的边。

图上有环，所以这些状态还是会互相依赖。对于每一个二进制位，列出 n-1 个线性方程，高斯消元求出 f_1。

第 k 位的贡献就是 f_1^{(k)}2^k，最后答案为 Ans=\sum_k f_1^{(k)}2^k。

三、树上的随机游走

到了树上以后，会稍微好做一点。

虽然还是会来回乱走，但树上有两个很好用的性质：任意两点之间路径唯一，删掉一条边以后整棵树会直接分成两个连通块。

靠着这些结构，很多一般图上要高斯消元的问题，到了树上可以直接变成树形 dp 或者一些简单递推。

1. 树上点的期望经过次数

一般图上求点的期望经过次数，要列 f_u=[u=s]+\sum_{v:v\to u}f_vp_{v,u}，然后解线性方程组。

但树上路径唯一，有时候可以直接分析两件事：从起点出发走到 u 的概率是多少，以及已经到了 u 以后还会再经过它多少次。

例题 3.1 CF1823F Random Walk

题意

给一棵树，从节点 s 开始随机游走，每次等概率走向一个相邻节点，到达 t 后立即停止。

求每个节点被经过次数的期望。

做法

把树以终点 t 为根，设 dis_u 表示节点 u 到终点 t 的距离。

先考虑一个问题：假设已经走到了节点 u，那么从现在开始直到到达 t，节点 u 还会被经过多少次？

设这个期望为 E_u，当前位置这一次也算进去。

从 u 出发：

所以离开 u 以后再次回到 u 的概率为：

\frac{d_u-1}{d_u}+\frac{1}{d_u}\left(1-\frac{1}{dis_u}\right)

于是：

E_u=1+\left[\frac{d_u-1}{d_u}+\frac{1}{d_u}\left(1-\frac{1}{dis_u}\right)\right]E_u

化简得到 E_u=d_u\cdot dis_u。

不过，这只是已经到达 u 以后，后面还会经过多少次。还要算从起点 s 出发，到底有多大概率能走到 u。

设 x 是路径 u\to t 和路径 s\to t 的第一个交点。

如果 u 本身就在 s\to t 的路径上，那一定会经过 u。否则，从 x 出发，在先到达 u 和先到达 t 之间，先到达 u 的概率是 \frac{dis_x}{dis_u}。

所以：

ans_u=E_u\cdot\frac{dis_x}{dis_u}=d_u\cdot dis_u\cdot\frac{dis_x}{dis_u}=d_u\cdot dis_x

最终得到 ans_u=d_u\cdot dis_x。

对于终点 t，第一次到达后立即停止，所以 ans_t=1。

2. 有向边期望拆分

树上任意两点之间的路径唯一，所以如果能求出每条父子边两个方向上的期望到达步数，那么任意两点之间的期望到达时间，就可以直接拆成路径上若干条有向边的贡献。

设 f_u 表示从 u 第一次随机游走到 fa_u 所需的期望步数，g_u 表示从 fa_u 第一次随机游走到 u 所需的期望步数。

先看 f_u 怎么算。

从 u 出发，有 \frac{1}{d_u} 的概率直接一步走到父亲。剩下的情况会先走到某个儿子 v，然后从 v 回到 u，最后再从 u 走到 fa_u。

所以：

f_u=\frac{1}{d_u}+\sum_{v\in son(u)}\frac{1+f_v+f_u}{d_u}

两边乘以 d_u：

d_uf_u=1+\sum_{v\in son(u)}(1+f_v+f_u)

拆开：

d_uf_u=1+d_u-1+(d_u-1)f_u+\sum_{v\in son(u)}f_v

合并得到：

f_u=d_u+\sum_{v\in son(u)}f_v

这里已经可以直接树形 dp 了。我们继续往下推：

因为 subtree(u) 内部有 sz_u-1 条边，每条边对度数和贡献 2，再加上 u 连向父亲的那条边额外贡献 1，所以：

\sum_{x\in subtree(u)}d_x=2(sz_u-1)+1=2sz_u-1 注意，$f_u=2sz_u-1$ 只对 $u\neq root$ 成立。 **接下来算 $g_u$。** ![](https://cdn.luogu.com.cn/upload/image_hosting/xxmu3pua.png) 先假设 $fa_u$ 不是根节点，$bro$ 表示 $u$ 的兄弟，$gfa$ 表示 $fa_{fa_u}$。 从 $fa_u$ 出发去 $u$，有三种情况： 1. 一步直接走到 $u$。 2. 先走到某个兄弟 $bro$，绕回来以后再继续。 3. 先走到爷爷，再回来继续走。 所以： $$ g_u=\frac{1}{d_{fa_u}}+\sum_{\substack{bro\in son(fa_u)\\bro\neq u}}\frac{1+f_{bro}+g_u}{d_{fa_u}}+\frac{1+g_{fa_u}+g_u}{d_{fa_u}} $$ 两边乘以 $d_{fa_u}$： $$ d_{fa_u}g_u=1+\sum_{\substack{bro\in son(fa_u)\\bro\neq u}}(1+f_{bro}+g_u)+1+g_{fa_u}+g_u $$ 拆开： $$ d_{fa_u}g_u=1+(d_{fa_u}-2)+(d_{fa_u}-2)g_u+\sum_{\substack{bro\in son(fa_u)\\bro\neq u}}f_{bro}+1+g_{fa_u}+g_u $$ 合并得到： $$ g_u=d_{fa_u}+\sum_{\substack{bro\in son(fa_u)\\bro\neq u}}f_{bro}+g_{fa_u} $$ 而： $$ f_{fa_u}=d_{fa_u}+f_u+\sum_{\substack{bro\in son(fa_u)\\bro\neq u}}f_{bro} $$ 所以： $$ g_u=g_{fa_u}+f_{fa_u}-f_u $$ 为了统一递推，形式上定义 $f_{root}=2(n-1)$，$g_{root}=0$。 于是对于所有非根节点 $u$，都有 $g_u=g_{fa_u}+f_{fa_u}-f_u$。 这样就能预处理出每条父子边两个方向的期望到达步数。 对于任意两点 $a,b$，因为树上路径唯一，所以从 $a$ 随机游走到 $b$ 的期望步数，就是 $a\to b$ 路径上每条有向边对应期望的总和。 #### 例题 3.2 [P3412 仓鼠找 sugar II](https://www.luogu.com.cn/problem/P3412) ##### 题意 给定一棵 $n$ 个节点的树，随机选择起点 $a$ 和终点 $b$。从 $a$ 出发，每次等概率走向一个相邻节点，到达 $b$ 后停止，求所需步数的期望。 ##### 做法 上面已经求出了每个非根节点 $u$ 的 $f_u=E(u\to fa_u)$ 和 $g_u=E(fa_u\to u)$。 如果直接枚举所有点对 $(a,b)$ 再沿路径统计，肯定不行，所以改成考虑每条边对答案的贡献。 设 $u$ 是非根节点，考虑边 $(fa_u,u)$。删掉这条边以后，整棵树被分成两部分，大小分别是 $sz_u$ 和 $n-sz_u$。 如果 $a\in subtree(u)$，$b\notin subtree(u)$，那么从 $a$ 到 $b$ 一定会按 $u\to fa_u$ 的方向经过这条边，所以每对点贡献 $f_u$。 这样的有序点对有 $sz_u(n-sz_u)$ 个，因此这一方向的总贡献是 $sz_u(n-sz_u)f_u$。 反过来，如果 $a\notin subtree(u)$，$b\in subtree(u)$，那么会按 $fa_u\to u$ 的方向经过这条边，贡献 $g_u$。 所以这条边的总贡献为 $sz_u(n-sz_u)(f_u+g_u)$。 最后所有有序点对的期望步数总和为 $\sum_{u\neq root}sz_u(n-sz_u)(f_u+g_u)$，再除以 $n^2$ 即可。 ### 3. 线性函数消元 树上随机游走里还有一种很常见的情况：直接列出期望转移后，会发现父亲依赖儿子，儿子又依赖父亲，普通树形 dp 根本推不动。 但这些转移式一般都是线性的，所以可以把节点 $u$ 的答案写成父亲答案的一次函数：$f_u=k_uf_{fa_u}+b_u$。 对于 $u$ 的每个儿子 $v$，同样有 $f_v=k_vf_u+b_v$。 只要儿子的 $k_v,b_v$ 已经求出来，就能把这些式子代回 $u$ 的转移方程，再整理出新的 $k_u,b_u$。 于是就可以从叶子开始，一路往上消到根。根没有父亲，所以能直接求出答案；如果还需要所有节点的值，再从根往下代回去即可。 这个过程可以看成树上的高斯消元。普通高斯消元是在整个方程组里消未知数，这里借着树的父子结构，每个点只需要维护两个系数 $k_u,b_u$。 #### 例题 3.3 [CF802L Send the Fool Further! (hard)](https://www.luogu.com.cn/problem/CF802L) 警示后人：这题在 CF 上的题号是 802J3，但洛谷上对应的是 CF802L。 ##### 题意 给一棵带权树，从 $1$ 号点开始随机游走，每次等概率走向一个相邻节点，到达叶子后停止，求经过边权总和的期望。 ##### 做法 设 $f_u$ 表示当前在节点 $u$，直到随机游走结束还要经过的期望边权总和。 对于叶子节点，有 $f_u=0$。 对于非叶子节点 $u$： $$ f_u=\frac{f_{fa_u}+w_{u,fa_u}+\sum_{v\in son(u)}(f_v+w_{u,v})}{d_u} $$ 这个转移既依赖儿子又依赖父亲，显然不能直接树形 dp。 考虑写成 $f_u=k_uf_{fa_u}+b_u$。 假设对于 $u$ 的每个儿子 $v$，已经有 $f_v=k_vf_u+b_v$，代入原式： $$ d_uf_u=f_{fa_u}+w_{u,fa_u}+\sum_{v\in son(u)}(k_vf_u+b_v+w_{u,v}) $$ 移项： $$ \left(d_u-\sum_{v\in son(u)}k_v\right)f_u=f_{fa_u}+w_{u,fa_u}+\sum_{v\in son(u)}(b_v+w_{u,v}) $$ 所以： $$ k_u=\frac{1}{d_u-\sum_{v\in son(u)}k_v} $$ $$ b_u=\frac{w_{u,fa_u}+\sum_{v\in son(u)}(b_v+w_{u,v})}{d_u-\sum_{v\in son(u)}k_v} $$ 这样从叶子开始，自底向上就能求出所有 $k_u,b_u$。 对于根节点 $1$，因为没有父亲，直接得到： $$ f_1=\frac{\sum_{v\in son(1)}(b_v+w_{1,v})}{d_1-\sum_{v\in son(1)}k_v} $$ 这就是答案，总复杂度为 $O(n)$。 --- ## 四、多维状态随机游走 如果随机游走者不止一个，只记录一个点就不够了。 比如两个人分别在 $u,v$，那就把它们合成一个状态 $(u,v)$。原来只有 $n$ 个状态，现在直接变成 $n^2$ 个。 ### 1. 双人随机游走 #### 例题 4.1 [CF113D Museum](https://www.luogu.com.cn/problem/CF113D) ##### 题意 给一张无向连通图，两个人分别从 $a,b$ 出发。 每一秒，对于位于节点 $i$ 的人，有 $p_i$ 的概率原地不动，否则等概率走向一个相邻节点。两个人同时行动。 当两个人出现在同一个节点时停止，求最终在每个节点相遇的概率。 注意，就算两个人同时沿同一条边反向移动，也不会在边上相遇。 ##### 做法 设 $f_{u,v,k}$ 表示两个人当前分别在节点 $u,v$，最后在节点 $k$ 相遇的概率。 如果已经相遇，也就是 $u=v$，那么 $f_{u,u,k}=[u=k]$。 接下来考虑 $u\neq v$。 一秒以后，两个人的行动有四种情况： 1. 两个人都不动，概率是 $p_up_v$。 2. 第一个人走到相邻节点 $x$，第二个人不动，概率是 $\frac{1-p_u}{d_u}p_v$。 3. 第一个人不动，第二个人走到相邻节点 $y$，概率是 $p_u\frac{1-p_v}{d_v}$。 4. 两个人都移动，分别走到 $x,y$，概率是 $\frac{(1-p_u)(1-p_v)}{d_ud_v}$。 所以： $$ f_{u,v,k}=p_up_vf_{u,v,k}+\sum_{x\sim u}\frac{1-p_u}{d_u}p_vf_{x,v,k}+\sum_{y\sim v}p_u\frac{1-p_v}{d_v}f_{u,y,k}+\sum_{x\sim u}\sum_{y\sim v}\frac{(1-p_u)(1-p_v)}{d_ud_v}f_{x,y,k} $$ 移项以后： $$ (1-p_up_v)f_{u,v,k}-\sum_{x\sim u}\frac{1-p_u}{d_u}p_vf_{x,v,k}-\sum_{y\sim v}p_u\frac{1-p_v}{d_v}f_{u,y,k}-\sum_{x\sim u}\sum_{y\sim v}\frac{(1-p_u)(1-p_v)}{d_ud_v}f_{x,y,k}=0 $$ 这样就得到了一个关于 $n^2$ 个状态的线性方程组。 对于每一个最终相遇点 $k$，左边的系数矩阵完全一样，只有边界条件不同，所以可以在增广矩阵右边同时放 $n$ 列，一次高斯消元把所有答案一起求出来。 初始状态是 $(x,y)$，所以最后输出 $f_{x,y,1},f_{x,y,2},\dots,f_{x,y,n}$。 --- ## 五、结语 写到这里，我突然觉得随机游走这个名字还挺贴切。 很多时候我们确实不知道下一步会走到哪。可能往前，可能绕路，也可能折腾半天又回到原点。站在当下看，很容易觉得前面都白走了。 但过一段时间再回头，有些绕过的路至少让你知道哪里走不通，也让你碰见了一些原本不会遇到的东西。最后到了哪里，往往也不是一开始就计划好的。 所以现在再看，走弯路这件事其实没那么可怕。 一直不走，才是真的哪都到不了。