===== 随机游走 =====

有一类随机游走问题定义如下：在数轴中 $[0,n]$ 之间的整点上随机走动，走到 $0$ 或点 $n$ 时停止。否则，在点 $i$ 处，分别有 $f(i),g(i),h(i)$ 的概率向左走一步，不动，或者向右走一步，其中 $f(i)+g(i)+h(i)=1$。

首先可以计算出 $P(i)$，表示从点 $i$ 走到点 $n$ 的概率。那么有 ) $$
P(i)=
\begin{cases}
&0&(i=0)\\
&f(i)P(i-1)+g(i)P(i)+h(i)P(i+1)&(0<i<n)\\
&1&(i=n)\\
\end{cases}
$$

注意到

$$
\begin{aligned}
(f(i)+h(i))P(i)=&f(i)P(i-1)+h(i)P(i+1)\\
f(i)(P(i)-P(i-1))=&h(i)(P(i+1)-P(i))\\
P(i+1)-P(i)=&\frac{f(i)}{h(i)}(P(i)-P(i-1))\\
\end{aligned}
$$

因此

$$
P(i)=P(1)\cdot\sum_{j=0}^{i-1}\frac{\prod_{k=1}^{j}f(k)}{\prod_{k=1}^{j}h(k)}
$$

那么可以得到 $P(n)$ 与 $P(1)$ 之间的关系，即可解出 $P(1)$，从而求出所有 $P$。

此外，我们还可以为本题定义一种伪数学期望，它是指能到达点 $n$ 的前提下，游戏进行的期望次数，即 $E(t)=\sum_{i=0}^{+\infty}iP(i|x_{0}=t)$，这里 $P(i|x_{0}=t)$ 是指从 $t$ 出发，恰好在 $i$ 步后走到 $n$ 的概率。

$$
\begin{aligned}
E(t)&=\sum_{i=0}^{+\infty}iP(i|x_{0}=t)\\
&=\sum_{i=0}^{+\infty}i(f(i)P(i-1|x_{0}=t-1)+g(i)P(i-1|x_{0}=t)+h(i)P(i-1|x_{0}=t))\\
&=f(t)E(t-1)+g(t)E(t)+h(t)E(t+1)+P(t)\\
\end{aligned}
$$

因此

$$
\begin{aligned}
f(t)(E(t)-E(t-1))&=h(t)(E(t+1)-E(t))+P(t)\\
\end{aligned}
$$

定义 $dE(t)=E(t)-E(t-1)$，那么

$$
\begin{aligned}
f(t)dE(t)&=h(t)dE(t+1)+P(t)\\
dE(t+1)&=\frac{f(t)}{h(t)}dE(t)-\frac{1}{h(t)}P(t)\\
\end{aligned}
$$

那么这样可以 $\mathcal{O}(n)$ 计算。

如果希望能够在亚线性时间进行计算，可以看到概率尚有比较优美的闭式解，从中可能可以挖掘出一些性质。而对于伪期望，这一方法就行不通了。为了进一步解决类似这样的问题，我们需要引入一些随机过程中的理论。

==== 鞅 ====

设有一随机过程 $\{X_{n},n\ge0\}$，若对于一切 $n$，$E[|X_{n}|]<\infty$，且 $E[X_{n+1}|X_{0},X_{1},\ldots,X_{n}]=X_{n}$，那么称 $\{X_{n},n\ge0\}$ 为鞅。

==== 随机时间 ====

正整数值（可能取无穷）的随机变量 $N$ 称为随机过程 $\{X_{n},n\ge0\}$ 的随机时间，如果事件 $N=n$ 由随机变量 $X_{0},\ldots,X_{n}$ 决定。若 $P(N<\infty)=1$，随机时间 $N$ 称为停时。

==== 停止过程 ====

设 $N$ 是过程 $\{X_{n},n\ge0\}$ 的随机时间，令

$$
\overline{X}_{n}=
\begin{cases}
&X_{n}&(n\le N)\\
&X_{N}&(n>N)
\end{cases}
$$

形象地说，当随机时间 $N$ 达到之后，随机过程即停止，不再发生变化。

==== 引理 1 ====

若 $N$ 是鞅 $\{X_{n}\}$ 的随机时间，则停止过程 $\{\overline{X}_{n}\}$ 也是鞅。

因此 $E[\overline{X}_{n}]=E[\overline{X}_{0}]=E[X_{0}]$。

==== 定理 1（停时定理） ====

若 $N$ 是鞅 $\{X_{n}\}$ 的停时，那么（在一定的正则性条件下）$E[X_{N}]=E[X_{0}]$。

这是一个重要的定理，为后面的方法奠定了基础。

==== 基本思想 ====

假设有一个随机过程 $\{X_{n},n\ge0\}$ 及其停时 $T$，现在需要求出 $E[T]$。但是通常来说 $E(T)$ 并不好求。但是对于随机游走这样的随机过程，不妨构造 $X$ 的一个势函数 $\phi(X)$，使得

$$
\begin{aligned}
&E[\phi(X_{n+1})-\phi(X_{n})|X_{0},\ldots,X_{n}]=-1&(n<T)\\
&E[\phi(X_{n+1})-\phi(X_{n})|X_{0},\ldots,X_{n}]=0&(n\ge T)\\
\end{aligned}
$$

即每走一步势函数期望减小 $1$，停时后则不变。

这里需要证明可以构造停时的双射。通常在这类题目中，状态转移是一个马尔可夫过程，且 $X$ 恰有一种状态 $X_{T}$ 是停止状态，那么我们希望证明 $\phi(X_{T})$ 是唯一的。事实上，可以证明 $\phi(X_{T})$ 是唯一的最小值。假设它不是唯一的最小值，那么一定存在一个状态 $X'$，它不是停止状态，且 $\phi(X')$ 是最小值，那么 $E[\phi(X'_{1})-\phi(X')|X']=-1$，那么显然存在一种状态使得它的值比 $\phi(X')$ 小，矛盾。因此在 $\phi$ 满足要求的前提下，$\phi(X_{T})$ 是唯一的最小值，从而可以在两个随机过程中建立一个停时的双射。

考虑随机过程 $Y_{n}=\phi(X_{n})+\min(n,N)$，首先证明 $Y_{n}$ 是鞅：

若 $n<T$，那么

$$
\begin{aligned}
&E[Y_{n+1}|Y_{0},\ldots,Y_{n}]\\
=&E[Y_{n+1}-Y_{n}|Y_{0},\ldots,Y_{n}]+Y_{n}\\
=&Y_{n}\Box
\end{aligned}
$$

同理 $n\ge T$ 也可证。

根据停时定理，$E[Y_{T}]=E[Y_{0}]$，即 $E[\phi(X_{T})+T]=E[\phi(X_{0})+0]$，因此 $E[T]=\phi(X_{0})-\phi(X_{T})$。

下面具体到各个题目讲解 $\phi$ 的构造。

==== CF 1349D ====

**题解**：设球的总数为 $m=\sum_{i=1}^{n}x_{i}$，定义 $X_{t}=(x_{t1},x_{t2},\ldots,x_{tn})$，考虑势函数 $\phi(X_{t})=\sum_{i=1}^{n}f(x_{ti})$。

$$
\begin{aligned}
E[\phi(X_{t+1})|X_{t}]&=\sum_{i=1}^{n}\sum_{j\neq i}\frac{x_{ti}}{m(n-1)}\left[f(x_{ti}-1)+f(x_{tj}+1)+\sum_{k\notin\{i,j\}}f(x_{tk})\right]\\
&=\sum_{i=1}^{n}\frac{x_{ti}}{m}f(x_{ti}-1)+\frac{m-x_{ti}}{m(n-1)}f(x_{ti}+1)+\frac{(m-x_{ti})(n-2)}{m(n-1)}f(x_{ti})
\end{aligned}
$$

由于 $E[\phi(X_{t+1})-\phi(X_{t})|X_{t}]=-1$，因此

$$
\begin{aligned}
\sum_{i=1}^{n}f(x_{ti})&=\sum_{i=1}^{n}\frac{x_{ti}}{m}f(x_{ti}-1)+\frac{m-x_{ti}}{m(n-1)}f(x_{ti}+1)+\frac{(m-x_{ti})(n-2)}{m(n-1)}f(x_{ti})+\frac{x_{ti}}{m}
\end{aligned}
$$

那么只要对于任意 $x$ 令 $f(x)=\frac{x}{m}f(x-1)+\frac{m-x}{m(n-1)}f(x+1)+\frac{(m-x)(n-2)}{m(n-1)}f(x)+\frac{x}{m}$ 即可。

令 $x=0$，可得 $f(0)=f(1)$，不妨令 $f(0)=f(1)=1$，即可递推求解。

注意到

$$
\begin{aligned}
\left(\frac{x}{m}+\frac{m-x}{m(n-1)}\right)f(x)&=\frac{x}{m}f(x-1)+\frac{m-x}{m(n-1)}f(x+1)+\frac{x}{m}\\
\frac{x}{m}[f(x)-f(x-1)]&=\frac{m-x}{m(n-1)}[f(x+1)-f(x)]+\frac{x}{m}\\
f(x+1)-f(x)&=\frac{(n-1)x}{(m-x)}[f(x)-f(x-1)-1]
\end{aligned}
$$

答案为 $\sum_{i=1}^{n}f(x_{0i})-(f(m)+(n-1)f(0))$。

==== CF 850F ====

**题解**：与上题的思路基本相同：

$$
\begin{aligned}
E[\phi(X_{t+1})|X_{t}]&=\sum_{i=1}^{n}\sum_{j\neq i}\frac{x_{ti}x_{tj}}{m(m-1)}\left[f(x_{ti}+1)+f(x_{tj}-1)+\sum_{k\notin\{i,j\}}f(x_{tk})\right]+\sum_{i=1}^{n}\frac{x_{ti}(x_{ti}-1)}{m(m-1)}\phi(X_{t})\\
&=\sum_{i=1}^{n}\frac{x_{ti}(m-x_{ti})}{m(m-1)}f(x_{ti}-1)+\frac{x_{ti}(m-x_{ti})}{m(m-1)}f(x_{ti}+1)+\left[1-\frac{2x_{ti}(m-x_{ti})}{m(m-1)}\right]f(x_{ti})
\end{aligned}
$$

由于 $E[\phi(X_{t+1})-\phi(X_{t})|X_{t}]=-1$，因此

$$
\begin{aligned}
\sum_{i=1}^{n}f(x_{ti})&=\sum_{i=1}^{n}\frac{x_{ti}(m-x_{ti})}{m(m-1)}f(x_{ti}-1)+\frac{x_{ti}(m-x_{ti})}{m(m-1)}f(x_{ti}+1)+\left[1-\frac{2x_{ti}(m-x_{ti})}{m(m-1)}\right]f(x_{ti})+\frac{x_{ti}}{m}
\end{aligned}
$$

那么只要对于任意 $x$ 令 $f(x)=\frac{x(m-x)}{m(m-1)}f(x-1)+\frac{x(m-x)}{m(m-1)}f(x+1)+\left[1-\frac{2x(m-x)}{m(m-1)}\right]f(x)+\frac{x}{m}$ 即可。

注意到

$$
\begin{aligned}
\frac{2x(m-x)}{m(m-1)}f(x)&=\frac{x(m-x)}{m(m-1)}f(x-1)+\frac{x(m-x)}{m(m-1)}f(x+1)+\frac{x}{m}\\
f(x+1)-f(x)&=f(x)-f(x-1)-\frac{m-1}{m-x}
\end{aligned}
$$

注意到令 $x=0$ 得到 $f(0)=f(0)$，因此 $f(0),f(1)$ 均可任取。本题中 $m$ 较大，但是计算可得 $f(m)=f(0)+m(f(1)-f(0))-(m-1)^{2}$。

==== CF 1025G ====

**题解**：与上题的思路基本相同：

$$
\begin{aligned}
E[\phi(X_{t+1})|X_{t}]&=\sum_{i=1}^{n}\sum_{j\neq i}\frac{1}{n(n-1)}\left[f(x_{ti}+1)+(x_{tj}-1)f(1)+\sum_{k\notin\{i,j\}}f(x_{tk})\right]\\
&=\sum_{i=1}^{n}\frac{1}{n}f(x_{ti}+1)+\frac{x_{ti}-1}{n}f(1)+\frac{n-2}{n}f(x_{ti})
\end{aligned}
$$

由于 $E[\phi(X_{t+1})-\phi(X_{t})|X_{t}]=-1$，因此

$$
\begin{aligned}
\sum_{i=1}^{n}f(x_{ti})&=\sum_{i=1}^{n}\frac{1}{n}f(x_{ti}+1)+\frac{x_{ti}-1}{n}f(1)+\frac{n-2}{n}f(x_{ti})+\frac{1}{n}
\end{aligned}
$$

那么只要对于任意 $x$ 令 $2f(x)=f(x+1)+(x-1)f(1)+1$ 即可。

令 $x=1$，可得 $f(2)=2f(1)-1$。递推即可。

==== CF 1479E ====

**题解**：与上题的思路基本相同：

$$
\begin{aligned}
E[\phi(X_{t+1})|X_{t}]=&\frac{1}{2}\sum_{i=1}^{n}\frac{x_{ti}}{m}\left[f(x_{ti}-1)+f(1)+\sum_{k\neq i}f(x_{tk})\right]\\
&\frac{1}{2}\sum_{i=1}^{n}\sum_{j\neq i}\frac{x_{ti}x_{tj}}{m^{2}}\left[f(x_{ti}-1)+f(x_{tj}+1)+\sum_{k\notin\{i,j\}}f(x_{tk})\right]\\
&+\frac{1}{2}\sum_{i=1}^{n}\frac{x^{2}_{ti}}{m^{2}}\phi(X_{t})\\
&=\sum_{i=1}^{n}\frac{2m^{2}-3mx_{ti}+2x_{ti}^{2}}{2m^{2}}f(x_{ti})+\frac{(m-x_{ti})x_{ti}}{2m^{2}}f(x_{ti}+1)+\frac{2mx_{ti}-x_{ti}^{2}}{2m^{2}}f(x_{ti}-1)+\frac{1}{2}f(1)
\end{aligned}
$$

由于 $E[\phi(X_{t+1})-\phi(X_{t})|X_{t}]=-1$，因此

$$
\begin{aligned}
\sum_{i=1}^{n}f(x_{ti})&=\sum_{i=1}^{n}\frac{2m^{2}-3mx_{ti}+2x_{ti}^{2}}{2m^{2}}f(x_{ti})+\frac{(m-x_{ti})x_{ti}}{2m^{2}}f(x_{ti}+1)+\frac{2mx_{ti}-x_{ti}^{2}}{2m^{2}}f(x_{ti}-1)+\frac{1}{2}f(1)+1\\
\sum_{i=1}^{n}\frac{3mx_{ti}-2x_{ti}^{2}}{2m^{2}}f(x_{ti})&=\sum_{i=1}^{n}\frac{(m-x_{ti})x_{ti}}{2m^{2}}f(x_{ti}+1)+\frac{2mx_{ti}-x_{ti}^{2}}{2m^{2}}f(x_{ti}-1)+\frac{x_{ti}}{2m}f(1)+\frac{x_{ti}}{m}
\end{aligned}
$$

那么只要对于任意 $x$ 令

$$
\begin{aligned}
\frac{3mx-2x^{2}}{2m^{2}}f(x)&=\frac{(m-x)x}{2m^{2}}f(x+1)+\frac{2mx-x^{2}}{2m^{2}}f(x-1)+\frac{x}{2m}f(1)+\frac{x}{m}\\
\frac{m-x}{2m}[f(x+1)-f(x)]&=\frac{2m-x}{2m}[f(x)-f(x-1)]-\frac{1}{2}f(1)-1\\
f(x+1)-f(x)&=\frac{2m-x}{m-x}[f(x)-f(x-1)]-\frac{m}{m-x}f(1)-\frac{2m}{m-x}
\end{aligned}
$$

即可。

$f(0)$ 需要定义为 $0$，为了方便，令 $f(1)=-2$。令 $g(x)=f(x)-f(x-1)$，那么 $g(1)=f(1)-f(0)=-2$。有 $g(x+1)=\frac{2m-x}{m-x}g(x)$。

本题 $x_{i}$ 很大，因此需要用到根号求阶乘的技巧，因为与本主题无关，在此不做说明。