期望中的停时
参考自：### 鞅与停时定理学习笔记
这或许是一个比较抽象的套路吧，知道的就会，不知道的就不会。
我们可以如下描述这个套路，或者说利用势能函数 \(\Phi\) 来理解。
对于随机事件 \(\{A_0, A_1, ...\}\)，存在一个最终局面 \(A_t = e\)，我们需要求 \(A_t\) 第一次出现在 \(A\) 中的时间的期望，也就是 \(E(t)\)。
我们需要构造出满足如下条件的势能函数 \(\Phi(A)\) ：
- \(E(\Phi(A_{n + 1}) - \Phi(A_n) | A_0, A_1, \ldots, A_n) = -1\)
- \(\Phi(A_t)\) 是常数，并且 \(i = t \iff \Phi(A_t) = \Phi(A_i)\)。
于是对于整个局面：
- \(E(\Phi(A_t) + t) = E(\Phi(A_0))\)
也就是最终局面的势能函数 - 初始局面的势能函数即是期望步数。
由于满足了 \(\Phi(A_t)\) 是常数，那么我们就可以得到：
- \(E(t) = E(\Phi(A_0) - \Phi(A_t)) = \Phi(A_0) - \Phi(A_t)\)
当然，在实际做题中，我们也可以令 \(\Phi(A_0)\) 是小的那个，从而答案为 \(\Phi(A_t) - \Phi(A_0)\)
## Company Acquisitions
在此题中，我们设对于一个跟着 \(x\) 个元素的节点的势能函数为 \(f(x)\)。
那么此时局面的势能即 \(\sum f(x_i)\)，答案为 \(\Phi(A_t) - \Phi(A_0) = f(n - 1) - \sum f(x_i)\)。
那么我们现在考虑如何构造 \(f(x)\)，我们从两个元素开始，设分别跟着 \(a, b\) 个节点，那么：
\[f(a) + f(b) + 1 = \frac 1 2 (f(a + 1) + b f(0) + af(0) + f(b + 1))
\]
为了使得 \(f(0)\) 为常数，我们不妨设 \(f(0) = 0\)，那么存在：
\[f(a) + f(b) + 1 = \frac 1 2 (f(a + 1) + f(b + 1))
\]
如此还是抽象，我们不妨继续假设 \(a = b\)，那么：
\[2f(a) + 1 = f(a + 1)
\]
于是可以得出 \(f(a) = 2^a - 1\)，带入原式中仍然成立，于是可以如此定义。
那么最终的答案就简单了。