势函数与鞅的停时定理
势函数和鞅的停时定理
前置芝士
鞅：
鞅是一类特殊的随机过程，假设我们从一开始就在观察一场赌博游戏，现在已经得到了前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]\),即时停时刻的期望（注意这里我们不要求该随机过程是一个鞅）
为此，我们引入一个势函数\(\phi(X)\)
并且\(\phi(x)\)满足如下性质：
- \(\forall n<t, E(\phi(A_{n+1})-\phi(A_n)|A_0,A_1,...A_n)=-1\),即势能不断降低
- \(E(\phi(A_t))=C\),是一个常值
那么如果我们令\(X_t=\phi(A_t)+t\),则\(E(X_{n+1}-X_n|x_0,x_1...x_n)=E(\phi(A_{n+1})-\phi(A_n)+1|x_0,x_1...x_n)=E(\phi(A_{n+1})-\phi(A_n)|x_0,x_1...x_n)+1=0\)
我们发现随机过程\(X_t\)就是一个鞅了
那么由鞅的停时原理，\(E(X_t)=E(X_0)\),即\(E(\phi(A_t)+t)=E(\phi(A_0)+0)\),也即\(E(\phi(A_t))+E(t)=E(\phi(A_0))\)
所以我们得到\(E(t)=E(\phi(A_0))-E(\phi(A_t))\),根据我们之前定义的性质，\(E(\phi)A_t\)为一个常值，而\(E(\phi(A_0))\)显然也是一个常值，所以只要能找到这个满足条件的势函数，就能很方便的求出\(E(t)\)
这里我们只是在随机过程\(X_t\)中应用了停时定理，对原本的随机过程\(A_t\)并没有做什么限制
接下来结合具体的题目来讨论一下如何构造这样的一个势函数
大意：
有n个人在玩传球游戏，一开始第\(i\)个人有\(a_i\)个球。每一次传球，等概率随机选中一个球，设其当前拥有者为\(i\)，\(i\)将这个球等概率随机传给另一个人\(j(j\neq i)\)。当某一个人拥有所有球时，停止游戏。问游戏停止时的期望传球次数。
记球的总数为m
不妨记状态\(A_t=(a_{t,1},a_{t,2}...a_{t,n})\),一个n维向量，分别表示 在时刻t，第i个人手中球的数量，显然它唯一地表示了某一个时刻的全局状态
也就是说，我们现在就把这个游戏过程抽象成了一个随机过程\(A_0,A_1....\),并且其停时为t。那么按照之前所说，我们需要去定义一个势函数\(\phi(A_t)\),为了计算方便，我们可以将\(\phi\)具体到A的每一维向量，不妨记为\(\phi(A_t)=\sum_{i=1}^{n}f(a_{t,i})\),这里f是什么我们并不知道，但是如果我们知道了f，其实也就是相当于构造出了这个势能函数
这里再把我们定义的\(\phi\)的性质再放一下
\(\phi(x)\)满足如下性质：
- \(\forall n<t, E(\phi(A_{n+1})-\phi(A_n)|A_0,A_1,...A_n)=-1\),即势能不断降低
- \(E(\phi(A_t))=C\),是一个常值
那么我们首先来考虑第一个性质，为了方便，不妨先考虑\(E(\phi(A_{n+1})|A_0,A_1,...A_n)\)
发现传球过程就是一个\(Markov\)过程，并且该时刻的状态只与上一个时刻的状态有关,所以\(E(\phi(A_{n+1})|A_0,A_1,...A_n)=E(\phi(A_{n+1})|A_n)\)
考虑一次转移的所有可能
i传球给j的概率是\(\Large \frac{a_{t,i}}{m}\frac{1}{n-1}\)
\(\large E(\phi(A_{n+1})|A_n)=\sum_{i=1}^{n}\sum_{j\neq 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})]\)
\(\large =\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(\phi(A_{n+1})-\phi(A_n)|A_0,A_1,...A_n)=-1\)
\(E(\phi(A_{n+1})-\phi(A_n)|A_0,A_1,...A_n)=E(\phi(A_{n+1})-\phi(A_n)|A_n)\)
\(\large =(\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\)
所以\(\large \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分配到每一个和式里面去，这样左右的形式就统一了
所以\(\large \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}}{m}]\)
那么不妨记\(\large 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}{m}\)
这样和式还是成立的，我们也成功抽象出了f函数
再转化一下，\(\large 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，也就是相当于得到了势函数\(\phi(x_t)=\sum_{i}f(x_{t,i})\)
然后考虑势函数的第二个性质：\(E(\phi(A_t))=C\)是一个常值
显然\(E(\phi(A_t))=\sum_{i}f(a_{t,i})=f(m)+(n-1)f(0)\)是一个常值
所以根据我们的结论，\(E(t)=E(\phi(A_0))-E(\phi(A_t))=\sum_{i}f(a_{0,i})-f(m)-(n-1)f(0)=\sum_{i}f(a_{0,i})-f(m)\)
这样我们就非常方便的得到了停时的期望
不妨来看一个近一点的例子
大意：
n个人，每个人手中初始有\(a_i\)个硬币，每次随机选择两个人，第一个人给第二个人一个硬币，如果某个人手中没有硬币了，则立即退出游戏，不再回来。当某一个人拥有全部硬币时，游戏结束
问停时的期望
题意与上一题十分相像，但是该题存在人数不固定的情况，所以我们描述游戏局面的时候要稍微改变一下
还是令\(m=\sum a_i\)
令\(A_t=(a_{t,1},a_{t,2}...a_{t,h_t})\)来描述第t个时刻的局面，其中\(h_t\)表示当前的剩余人数，显然它不是一个固定的值。但是我们能保证\(\forall i\leq h_t,a_{t,i}>0\)
仿照上一题的思路，我们令\(\phi(A_t)=\sum_{i=1}^{n}f(a_{t,i})\)作为势函数，尝试确定f
\(\large E(\phi(A_{n+1})|A_n)=\sum_{i=1}^{h_t}\sum_{j\neq 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})]\)
\(\large =\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})\)
代入\(\large E(\phi(A_{n+1})-\phi(A_n)|A_0,A_1,...A_n)=-1\),也就是\(\large E(\phi(A_{n+1})-\phi(A_n)|A_n)=-1\)(显然这里当前局面也只与上一个局面有关)，有
\(\large \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\)
\(\large =\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})\)
抽象出\(\large 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(\phi(A_0))-E(\phi(A_t))=\sum_{i=1}^{n}f(a_{0,i})-f(m)\)
未完待续