标签：停时 势能 期望 函数 Phi 35 算法 我们

期望中的停时

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

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

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

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

标签：停时,势能,期望,函数,Phi,35,算法,我们
From： https://www.cnblogs.com/jeefy/p/17808216.html