【学习笔记】随机游走优化 dp

· · 算法·理论

引入

一个数轴，初始有一个点在 0 位置。现在这个点会移动 n 次，每一次有 \frac12 的概率点从 x 移动到 x+1，另外 \frac12 的概率点从 x 移动到 x-1。问移动完 n 次之后 |x| 的期望值是多少。

上述问题的答案不超过 O(\sqrt n) 级别。下面给出一个简单的证明：

直接计算 E[|x|] 比较复杂。考虑先放缩一下，计算出 E[x^2] 的值，然后就可以直接得到 E[|x|]\le \sqrt{E[x^2]}。

记第 i 步 x 移动的决策是 p_i（也就是 x 在第 i 次操作中移动到了 x+p_i 位置）。则显然有 x^2=(p_1+p_2+\ldots+p_n)^2，也就可以得到 E[x^2]=\sum\limits_{i=1}^nE[p_i^2]+2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nE[p_ip_j]=n+2\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nE[p_ip_j]。又因为决策之间是两两独立的，所以直接分类 p_i,p_j 的取值分别算期望，可以得到 E[p_ip_j]=0，也就得到了 E[x^2]=n\Rightarrow E[x]\le O(\sqrt n)。

现在在上面的问题上扩展，考虑另外一个与其相似的问题：

一个数轴，初始有一个点在 0 位置。现在这个点会移动 n 次，每一次有 \frac12 的概率点从 x 移动到 x+1，另外 \frac12 的概率点从 x 移动到 x-1。问移动完 n 次后，x 移动到的全部 n+1 个位置中绝对值最大的点的期望值是多少。

解决完上一个问题之后容易猜测答案还是 O(\sqrt n) 级别的。下面给出一个证明：

设随机游走位置为 S_0=0,S_k=\xi_1+\xi_2+\cdots+\xi_k，其中每个 \xi_i 有 \frac12 的概率为 1，另外 \frac12 的概率为 -1。为了方便，记 M_i=\max\limits_{j=0}^i|S_j| 即前 i 次移动中距离原点最远的距离是多少。

因为 M_n 是非负整数，所以 \mathbb E[M_n]=\sum_{t\ge1}\Pr(M_n\ge t)。

所以只要我们能证明 \Pr(M_n\ge t)\le C e^{-c t^2/n}，把这个式子对 t 求和，就会得到 \mathbb E[M_n]=O(\sqrt n)。

事件 M_n\ge t 的意思是：在前 n 步里，曾经到过 t 或者 -t。所以 \Pr(M_n\ge t) \le \Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr) + \Pr\Bigl(\min_{0\le k\le n}S_k\le -t\Bigr)。

由于对称性，这两项相等，因此有：\Pr(M_n\ge t)\le 2\Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr)。

现在用一维随机游走最经典的“反射法”结论：\Pr\Bigl(\max_{0\le k\le n}S_k\ge t\Bigr)\le 2\Pr(S_n\ge t)，结合一下就可以得到 \Pr(M_n\ge t)\le 4\Pr(S_n\ge t)。

此时又因为 S_n=\xi_1+\cdots+\xi_n 是 n 个独立 \pm1 的和，所以它的方差是 n，标准差是 \sqrt n。更进一步，S_n 有高斯型尾估计：\Pr(S_n\ge t)\le e^{-t^2/(2n)}，因此 \Pr(M_n\ge t)\le 4e^{-t^2/(2n)}。

结合一开始得到的式子，有：

\mathbb E[M_n]= \sum_{t\ge1}\Pr(M_n\ge t)\le\sum_{t\ge1}4e^{-t^2/(2n)}

而这个和的量级就是 \sqrt n。最简单的看法是把它和积分比较：

\sum_{t\ge1}e^{-t^2/(2n)} \le \int_0^\infty e^{-x^2/(2n)}{dx}= \sqrt n\int_0^\infty e^{-u^2/2}du= C\sqrt n

所以有 \mathbb E[M_n]\le 4C\sqrt n。于是得到最终结论：

\boxed{\mathbb E[M_n]=O(\sqrt n)}

事实上，可以继续收紧上下界得到 \mathbb E[M_n]\sim\sqrt{\frac{\pi n}2}，但是我不会证，而且在实际题目中并不需要这么紧的上界，因此这里直接给出一个由 ChatGPT 5.4 Thinking 给出的证明过程：

:::info[证明过程] 设随机游走的过程为：

S_0=0,\qquad S_k=\sum_{i=1}^k \xi_i,\qquad \Pr(\xi_i=1)=\Pr(\xi_i=-1)=\frac12,

题目要求的是 M_n:=\max_{0\le k\le n}|S_k| 的期望 \mathbb E[M_n]。

1. 先写成尾和公式

因为 M_n 是非负整数值随机变量，所以：

\mathbb E[M_n]=\sum_{m\ge1}\Pr(M_n\ge m).

而 n 步最多走到距离 n，所以实际上：

\boxed{\mathbb E[M_n]=\sum_{m=1}^n \Pr(M_n\ge m)}

也就是：

\boxed{\mathbb E[M_n]=\sum_{m=1}^n \Bigl(1-\Pr(M_n<m)\Bigr)}

2. 精确公式

事件 M_n<m 就是“前 n 步始终没有碰到 \pm m”，也就是随机游走在区间 {-m+1,-m+2,\dots,m-1} 内存活到第 n 步。

这是经典吸收随机游走，谱分解可得：

\Pr(M_n<m) = \frac1m\sum_{j=0}^{m-1} (-1)^j \cot\frac{(2j+1)\pi}{4m}, \Bigl(\cos\frac{(2j+1)\pi}{2m}\Bigr)^n.

因此：

\boxed{ \mathbb E[M_n] = \sum_{m=1}^n \left[ 1- \frac1m\sum_{j=0}^{m-1} (-1)^j \cot\frac{(2j+1)\pi}{4m}, \Bigl(\cos\frac{(2j+1)\pi}{2m}\Bigr)^n \right]. }

这就是这个期望的一个标准精确表达式。

3. 渐近结果

当 n\to\infty 时，有经典极限定理：

\frac{M_n}{\sqrt n}\ \Longrightarrow\ \sup_{0\le t\le 1}|B_t|

其中 B_t 是标准布朗运动。并且该极限随机变量的期望是：

\mathbb E\Bigl[\sup_{0\le t\le 1}|B_t|\Bigr] = \sqrt{\frac{\pi}{2}}

所以：

\boxed{\mathbb E[M_n]\sim \sqrt{\frac{\pi n}{2}}}

也就是主项约为：

\mathbb E[M_n]\approx 1.253314\sqrt n.

4. 对比一下末位置

注意这不是最后位置 |S_n| 的期望。后者是 \mathbb E|S_n|\sim \sqrt{\frac{2n}{\pi}},，而这里取的是全过程的最大绝对值，所以更大，主常数变成了 \sqrt{\frac{\pi}{2}}。

5. 最终结论

精确值：

\boxed{ \mathbb E!\left[\max_{0\le k\le n}|S_k|\right] = \sum_{m=1}^n \left[ 1- \frac1m\sum_{j=0}^{m-1} (-1)^j \cot!\frac{(2j+1)\pi}{4m}, \Bigl(\cos!\frac{(2j+1)\pi}{2m}\Bigr)^n \right]. }

渐近值：

\boxed{ \mathbb E!\left[\max_{0\le k\le n}|S_k|\right] \sim \sqrt{\frac{\pi n}{2}}}

:::

解决问题

考虑用上面给出的 trick 解决一道经典题目！

题目给出的六边形网格不太好处理，因此容易想到把这个东西压扁，将六个方向修改为上，下，左，右，右上，左下。此时容易想到直接 dp。设 f_{i,x,y,j,k} 表示当前处理了前 i 个 idea，L=j,G=k，当前网格的横坐标是 x，纵坐标是 y，是否是可行的状态。

考虑优化这个 dp。可行性 dp 通常有下面两种优化方法：

这个问题看着很不能把状态写到答案里，因此考虑用 bitset 优化。发现 y 这个 dp 维度其实就是在做一次循环移位操作，用 bitset 优化可以让时间复杂度除一个 w，但是仍然难以通过。

考虑利用上面的 trick。注意到最后需要让所在的位置 (x,y) 回到 (0,0)，而上面的 trick 在更高维度上也同样满足距离 (0,0) 的曼哈顿距离期望为 O(\sqrt n) 级别。因此考虑直接随机打乱输入的 idea 顺序，此时对于距离原点超过 O(\sqrt n) 的位置，其很大概率是可以被不超过 O(\sqrt n) 的位置所替代的，因此只需要处理 \boldsymbol{x,y\in[-O(\sqrt n),O(\sqrt n)]} 的部分，范围以外的 dp 值直接截断处理即可。此时算法的时间复杂度被优化到 O(\frac{n^2p^2}w)，卡常后可以通过该题。

:::success[代码] 因为作者不太会卡常所以目前只有用 C++98 提交才能通过/kel

#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
const int mod = 998244353;
bitset<26> f[2][110][110][26];
int p[N], a[N][12];
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n, M; cin >> n >> M;
    const int m = M, st = sqrt(n) + 2;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 12; ++j) cin >> a[i][j];
    int x, y; cin >> x >> y;
    for (int i = 1; i <= n; ++i) p[i] = i;
    random_shuffle(p + 1, p + n + 1);
    f[0][0][0][st] = 1 << st;
    for (int I = 1, i = p[1]; I <= n; i = p[++I])
        for (int j = 0; j < m; ++j)
            for (int k = 0; k < m; ++k)
                for (int h = 0; h <= st * 2; ++h) {
                    f[I & 1][j][k][h] = f[~I & 1][(j - a[i][4] + m) % m][(k - a[i][5] + m) % m][h + 1] >> 1 | f[~I & 1][(j - a[i][0] + m) % m][(k - a[i][1] + m) % m][h] << 1 | f[~I & 1][(j - a[i][2] + m) % m][(k - a[i][3] + m) % m][h + 1] | f[~I & 1][(j - a[i][6] + m) % m][(k - a[i][7] + m) % m][h] >> 1;
                    if (h) f[I & 1][j][k][h] |= f[~I & 1][(j - a[i][8] + m) % m][(k - a[i][9] + m) % m][h - 1] | f[~I & 1][(j - a[i][10] + m) % m][(k - a[i][11] + m) % m][h - 1] << 1;
                }
    cout << ((f[n & 1][x][y][st][st]) ? "Chaotic Evil" : "Not a true problem setter") << '\n';
    return 0;
}
:::

### 练习

> 给定一个 $n$ 个结点的树，每条边都有边权（边权可能为负）。你需要选择若干条有 $4$ 条边组成的简单路径（可以不选），使得没有一条边被超过一条路径覆盖。问所有被路径覆盖的边的边权的和最大是多少。
>
> 数据范围：$2\le n\le 2\times 10^5$。

考虑一个暴力的 dp 做法。设 $f_{i,0/1/2/3}$ 表示当前只处理 $i$ 结点为根的子树，$i$ 结点没有挂长度不为 $4$ 的链 / 在子树里挂了一条长度为 $1/2/3$ 的链，边权之和最大是多少。转移过程需要合并儿子结点的 dp 信息，考虑再记一个 dp 数组辅助转移：设 $g_{i,0/1}$ 表示当前合并了若干个儿子结点的信息，其中儿子结点里长度为 $0$ 的链比长度为 $2$ 的链多 $i$ 条，长度为 $1$ 的链数量 $\bmod\ 2=0,1$，边权和最大是多少（只记录这些信息是因为子树内合并链只能是长度为 $0,2$ 的链对应匹配，长度为 $1$ 的链单独匹配）。此时合并信息是简单的。

直接做转移时间复杂度为 $O(n^2)$。注意到辅助转移的 $g$ 数组中 $i$ 维度维护的是两类儿子结点的链的差值，而一个儿子结点只能有最多一条连向父亲结点的链，最后可以转移到 $f$ 数组里的 $g$ 也只有 $g_{-1,*},g_{0,*},g_{1,*}$ 三类。因此考虑把长度为 $0$ 的链看作 $1$，长度为 $2$ 的链看作 $-1$，则可以看作是在数轴上做随机游走，打乱儿子结点顺序后 $g_i$ 这个维度只需要维护 $O(\sqrt n)$ 个 $i$ 的信息即可。此时算法的时间复杂度优化到 $O(n\sqrt n)$，可以通过该题。

:::success[代码]
```cpp line-numbers
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
const int N = 200010;
const int mod = 998244353;
const int inf = 1e18;
constexpr inline void add(int &x, int v) { x += v; if (x >= mod) x -= mod; }
constexpr inline void sub(int &x, int v) { x = (x + mod - v) % mod; }
vector<pair<int, int>> adj[N];
int f[N][4], g[2][1010][2];
inline void dfs(int u, int fa) {
    for (auto &[v, w] : adj[u]) if (v != fa) dfs(v, u);
    memset(g, -0x3f, sizeof g);
    int l = 500, r = 500, o = 0; g[0][500][0] = g[1][500][0] = 0;
    for (auto &[v, w] : adj[u]) if (v != fa) {
        --l, ++r, o ^= 1;
        if (l < 1) l = 1;
        if (r > 1000) r = 1000;
        for (int i = l; i <= r; ++i)
            for (int j = 0; j < 2; ++j)
                g[o][i][j] = max({
                    f[v][0] + g[o ^ 1][i][j], 
                    f[v][0] + g[o ^ 1][i - 1][j] + w, 
                    f[v][1] + g[o ^ 1][i][j ^ 1] + w, 
                    f[v][2] + g[o ^ 1][i + 1][j] + w, 
                    f[v][3] + g[o ^ 1][i][j] + w
                });
    } f[u][0] = g[o][500][0], f[u][1] = g[o][501][0], f[u][2] = g[o][500][1], f[u][3] = g[o][499][0];
}
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].emplace_back(b, c), adj[b].emplace_back(a, c);
    } for (int i = 1; i <= n; ++i) random_shuffle(adj[i].begin(), adj[i].end());
    dfs(1, 0), cout << f[1][0] << '\n';
    return 0;
}

:::