期望中的停时

参考自：### 鞅与停时定理学习笔记

这或许是一个比较抽象的套路吧，知道的就会，不知道的就不会。

我们可以如下描述这个套路，或者说利用势能函数 $\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$，带入原式中仍然成立，于是可以如此定义。

那么最终的答案就简单了。