势函数和鞅的停时定理

前置芝士

鞅：

鞅是一类特殊的随机过程，假设我们从一开始就在观察一场赌博游戏，现在已经得到了前t秒的观测值，那么当第t+1 秒观测值的期望等于第t秒的观测值时，我们称这是一个公平赌博游戏。

具体来说，对于一个随机过程$A_1,A_2,...$,如果$E(A_{n+1}|A_0,A_2,..A_n)=A_n$,我们称该随机过程为鞅。

鞅的停时定理：

设时停时间（在不知道随机过程的中间状态下停止的时刻）为t，则$E(t)=E(0)$

这个E到底是什么，由具体的情境而定，但是只要一个随机过程是一个鞅，它就有该结论

势函数

接下来我们考虑一个很常见的问题：

对于一个随机过程$A_1,A_2,...$,如果其终止状态$A_t$是确定的，求$E[t]$,即时停时刻的期望（注意这里我们不要求该随机过程是一个鞅）

为此，我们引入一个势函数$\varphi (X)$

并且$\varphi (x)$满足如下性质：

• $\forall n<t,E(\varphi (A_{n+1})-\varphi (A_n)|A_0,A_1,...A_n)=-1$,即势能不断降低
• $E(\varphi (A_t))=C$,是一个常值

那么如果我们令$X_t=\varphi (A_t)+t$,则$E(X_{n+1}-X_n|x_0,x_1...x_n)=E(\varphi (A_{n+1})-\varphi (A_n)+1|x_0,x_1...x_n)=E(\varphi (A_{n+1})-\varphi (A_n)|x_0,x_1...x_n)+1=0$

我们发现随机过程$X_t$就是一个鞅了

那么由鞅的停时原理，$E(X_t)=E(X_0)$,即$E(\varphi (A_t)+t)=E(\varphi (A_0)+0)$,也即$E(\varphi (A_t))+E(t)=E(\varphi (A_0))$

所以我们得到$E(t)=E(\varphi (A_0))-E(\varphi (A_t))$,根据我们之前定义的性质，$E(\varphi )A_t$为一个常值，而$E(\varphi (A_0))$显然也是一个常值，所以只要能找到这个满足条件的势函数，就能很方便的求出$E(t)$

这里我们只是在随机过程$X_t$中应用了停时定理，对原本的随机过程$A_t$并没有做什么限制

接下来结合具体的题目来讨论一下如何构造这样的一个势函数

CF1349D

大意：

有n个人在玩传球游戏，一开始第$i$个人有$a_i$个球。每一次传球，等概率随机选中一个球，设其当前拥有者为$i$，$i$将这个球等概率随机传给另一个人$j(j\ne i)$。当某一个人拥有所有球时，停止游戏。问游戏停止时的期望传球次数。

记球的总数为m

不妨记状态$A_t=(a_{t,1},a_{t,2}...a_{t,n})$,一个n维向量，分别表示 在时刻t，第i个人手中球的数量，显然它唯一地表示了某一个时刻的全局状态

也就是说，我们现在就把这个游戏过程抽象成了一个随机过程$A_0,A_1....$,并且其停时为t。那么按照之前所说，我们需要去定义一个势函数$\varphi (A_t)$,为了计算方便，我们可以将$\varphi$具体到A的每一维向量，不妨记为$\varphi (A_t)={\sum }_{i=1}^{n}f(a_{t,i})$,这里f是什么我们并不知道，但是如果我们知道了f，其实也就是相当于构造出了这个势能函数

这里再把我们定义的$\varphi$的性质再放一下

---

$\varphi (x)$满足如下性质：

• $\forall n<t,E(\varphi (A_{n+1})-\varphi (A_n)|A_0,A_1,...A_n)=-1$,即势能不断降低
• $E(\varphi (A_t))=C$,是一个常值

---

那么我们首先来考虑第一个性质，为了方便，不妨先考虑$E(\varphi (A_{n+1})|A_0,A_1,...A_n)$

发现传球过程就是一个$Markov$过程，并且该时刻的状态只与上一个时刻的状态有关,所以$E(\varphi (A_{n+1})|A_0,A_1,...A_n)=E(\varphi (A_{n+1})|A_n)$

考虑一次转移的所有可能

i传球给j的概率是$\frac{a_{t,i}}{m}\frac{1}{n-1}$

$E(\varphi (A_{n+1})|A_n)={\sum }_{i=1}^n{\sum }_{j\ne i}\frac{a_{t,i}}{m}\frac{1}{n-1}[f(a_{t,i}-1)+f(a_{t,j}+1)+{\sum }_{k\notin (i,j)}f(a_{t,k})]$

$={\sum }_{i=1}^n\frac{a_{t,i}}{m}f(a_{t,i}-1)+\frac{m-a_{t,i}}{m(n-1)}f(a_{t,i}+1)+\frac{(m-a_{t,i})(n-2)}{m(n-1)}f(a_{t,i})$

根据我们定义的性质$E(\varphi (A_{n+1})-\varphi (A_n)|A_0,A_1,...A_n)=-1$

$E(\varphi (A_{n+1})-\varphi (A_n)|A_0,A_1,...A_n)=E(\varphi (A_{n+1})-\varphi (A_n)|A_n)$

$=({\sum }_{i=1}^n\frac{a_{t,i}}{m}f(a_{t,i}-1)+\frac{m-a_{t,i}}{m(n-1)}f(a_{t,i}+1)+\frac{(m-a_{t,i})(n-2)}{m(n-1)}f(a_{t,i}))-\sum f(a_{t,i})=-1$

所以$\sum f(a_{t,i})=({\sum }_{i=1}^n\frac{a_{t,i}}{m}f(a_{t,i}-1)+\frac{m-a_{t,i}}{m(n-1)}f(a_{t,i}+1)+\frac{(m-a_{t,i})(n-2)}{m(n-1)}f(a_{t,i}))+1$

那么我们可以把末尾的1分配到每一个和式里面去，这样左右的形式就统一了

所以$\sum f(a_{t,i})={\sum }_{i=1}^n[\frac{a_{t,i}}{m}f(a_{t,i}-1)+\frac{m-a_{t,i}}{m(n-1)}f(a_{t,i}+1)+\frac{(m-a_{t,i})(n-2)}{m(n-1)}f(a_{t,i})+\frac{a_{t,i}}{n}]$

那么不妨记$f(a)=\frac{a}{m}f(a-1)+\frac{m-a}{m(n-1)}f(a+1)+\frac{(m-a)(n-2)}{m(n-1)}f(a)+\frac{a}{n}$

这样和式还是成立的，我们也成功抽象出了f函数

再转化一下，$f(a+1)=\frac{m+an-2a}{m-a}f(a)-\frac{a(n-1)}{m-a}(f(a-1)+1)$

代入边界条件$a=0$时，有$f(1)=f(0)$,所以我们可以设$f(1)=f(0)=0$,毕竟势函数的初值并不重要

这样就得到了f，也就是相当于得到了势函数$\varphi (x_t)={\sum }_{i}f(x_{t,i})$

然后考虑势函数的第二个性质：$E(\varphi (A_t))=C$是一个常值

显然$E(\varphi (A_t))={\sum }_{i}f(a_{t,i})=f(m)+(n-1)f(0)$是一个常值

所以根据我们的结论，$E(t)=E(\varphi (A_0))-E(\varphi (A_t))={\sum }_{i}f(a_{0,i})-f(m)-(n-1)f(0)={\sum }_{i}f(a_{0,i})-f(m)$

这样我们就非常方便的得到了停时的期望

不妨来看一个近一点的例子

杭电多校09 Coins

大意：

n个人，每个人手中初始有$a_i$个硬币，每次随机选择两个人，第一个人给第二个人一个硬币，如果某个人手中没有硬币了，则立即退出游戏，不再回来。当某一个人拥有全部硬币时，游戏结束

问停时的期望

题意与上一题十分相像，但是该题存在人数不固定的情况，所以我们描述游戏局面的时候要稍微改变一下

还是令$m=\sum a_i$

令$A_t=(a_{t,1},a_{t,2}...a_{t,h_t})$来描述第t个时刻的局面，其中$h_t$表示当前的剩余人数，显然它不是一个固定的值。但是我们能保证$\forall i\le h_t,a_{t,i}>0$

仿照上一题的思路，我们令$\varphi (A_t)={\sum }_{i=1}^{n}f(a_{t,i})$作为势函数，尝试确定f

$E(\varphi (A_{n+1})|A_n)={\sum }_{i=1}^{h_t}{\sum }_{j\ne i}\frac{1}{h_t(h_t-1)}[f(a_{t,i}-1)+f(a_{t,j}+1)+{\sum }_{k\notin (i,j)}f(a_{t,k})]$

$={\sum }_{i=1}^{h_t}\frac{1}{h_t}f(a_{t,i}-1)+\frac{1}{h_t}f(a_{t,i}+1)+\frac{h_t}{h_t-2}f(a_{t,i})$

代入$E(\varphi (A_{n+1})-\varphi (A_n)|A_0,A_1,...A_n)=-1$,也就是$E(\varphi (A_{n+1})-\varphi (A_n)|A_n)=-1$(显然这里当前局面也只与上一个局面有关)，有

${\sum }_{i=1}^{h_t}f(a_{t,i})=[{\sum }_{i=1}^{h_t}\frac{1}{h_t}f(a_{t,i}-1)+\frac{1}{h_t}f(a_{t,i}+1)+\frac{h_t}{h_t-2}f(a_{t,i})]+1$

$={\sum }_{i=1}^{h_t}(\frac{1}{h_t}f(a_{t,i}-1)+\frac{1}{h_t}f(a_{t,i}+1)+\frac{h_t}{h_t-2}f(a_{t,i})+\frac{1}{h_t})$

抽象出$f(a)=\frac{1}{h}f(a-1)+\frac{1}{h}f(a+1)+\frac{h}{h-2}f(a)+\frac{1}{h}$

$f(a+1)-f(a)=f(a)-f(a-1)-1$

令$g(a)=f(a)-f(a-1),有g(a)=g(0)-a$，则$f(a)=f(0)+ag(0)-\frac{a(a+1)}{2}$

取$f(0)=g(0)=0$,则$f(a)=-\frac{a(a+1)}{2}$

所以$E(t)=E(\varphi (A_0))-E(\varphi (A_t))={\sum }_{i=1}^{n}f(a_{0,i})-f(m)$

未完待续