https://www.cnblogs.com/TinyWong/p/12887591.html orz
全文参考照抄这位神仙的博客。
可能有很多地方不严谨，因为博主毕竟才高中，而数学水平还停留在初中，所以鞅和停时定理的绝大部分推导和证明都看不懂……
大概是解决这样的一类问题：给定一个初始状态和目标状态，中间每步操作都随机，问期望多少步之后可以结束。
例题：
其中第二题较为简单，而一三题如果用正常的思路可能比较难做。（虽然第一题正解的确没用这个）
有一个东西叫做鞅，本来是表示一种赌博策略的，但这不重要。
鞅是一个随机过程 \(\{X_0,X_1,\cdots\,\}\) ，满足 \(\mathbb{E}[X_t]<\infty, \mathbb{E}[X_{t+1}-X_t\mid X_0,X_1\cdots X_t]=0\) 。
意思是对于任意有限的 \(t\) ， \(E[X_t]\) 有界；不管 \(X_0\cdots X_t\) 是什么，下一次随机的期望收获为 0 。
但是这有什么用呢？
考虑这么一个随机过程 \(\{A_0,A_1,\cdots\,\}\) ，也就是题目给的随机过程。我们想要求 \(\mathbb{E}[T]\) ，其中 \(T\) 为停时。
构造一个势函数 \(\phi\) ，使得 \(\mathbb{E}[\,\phi(A_{t+1})-\phi(A_t)\,|\,A_0,A_1,\cdots,A_t\,]=-1\) ，然后设 \(X_t=\phi(A_t)+t\) ，那么就可以得到 \(\mathbb{E}[\,X_{t+1}-X_t\,|\,A_0,A_1,\cdots,A_t\,]=0\) 。
不过这个条件并不是怎样都要满足：在 \(A_t\) 为终止态时，（应该）可以不必满足这个条件。
至于第一个条件，由于 \(t\) 是确定的，所以 \(\mathbb{E}[X_t]\) 基本上也可以确定是有界的。
所以 \(\{X_0,X_1,\cdots\,\}\) 是鞅。而鞅的性质 \(\mathbb{E}[X_T]=\mathbb{E}[X_0]\) 即可推出 \(\mathbb{E}[T]=\phi[A_0]-\phi[A_T]\) 。注意 \(A_T\) 是题目给出的，是确定的。
所以问题就转化为构造 \(\phi\) 。
\(\phi\) 函数还要满足一些其他条件，比如只根据 \(\phi(A)\) 即可判断 \(A\) 是否是目标状态。
题目太多，只讲第一题。
设状态 \(A_t\) 中每个人的饼干数为 \(a_{t,i}\) 。对于这样的题，一般（大概）设 \(\phi(A_t)=\sum f(a_{t,i})\) 。
显然 \(\mathbb{E}[\phi(A_{t+1})]\) 只和 \(\mathbb E[\phi(A_t)]\) 有关，所以 \(\mathbb{E}\left[\phi\left(A_{t+1}\right) \mid A_{t}, \ldots, A_{0}\right]=\mathbb{E}\left[\phi\left(A_{t+1}\right) \mid A_{t}\right]\) 。
设 \(m\) 为总球数。
为了求出 \(\mathbb{E}\left[\phi\left(A_{t+1}\right) \mid A_{t}\right]\) ，可以枚举每一种丢饼干的方法，得到
令 \(\mathbb{E}[\,\phi(A_{t+1})-\phi(A_t)\mid A_t\,]=-1\) ，得到
注意把 \(-1\) 塞进求和号里变成 \(a_i\over m\) 的细节：这样可以使得每个 \(a_i\) 互不影响。
于是构造 \(f(a)\) 满足
此时这个函数的递推式只和前后有关，或者说只和前面两项有关，所以只要把 \(f(0),f(1)\) 构造出来就做完了。
把 \(a=0\) 代入得到 \(f(0)=f(1)\) ，所以不妨设 \(f(0)=f(1)=1\) （当然取任何值都应该是对的），然后递推即可。
最后答案即为
但在这题中其实我不是很确定能否通过 \(\phi(A)\) 推出 \(A\) 是否为终止状态，所以 /fad
原文：https://www.cnblogs.com/p-b-p-b/p/13297098.html