【转Matrix67】Penney 游戏 这博弈NB啊

让我们来玩一个游戏。连续抛掷硬币，直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者，那么我获胜，你需要给我 1 元钱；如果是后者，那么你获胜，我会给你 1 元钱。你愿意跟我玩这样的游戏吗？换句话说，这个游戏是公平的吗？

乍看上去，你似乎没有什么不同意这种玩法的理由，毕竟“正反反”和“反反正”的概率是均等的。连续抛掷三次硬币可以产生 8 种不同的结果，上述两种各占其中的 1/8 。况且，序列“正反反”和“反反正”看上去又是如此对称，获胜概率怎么看怎么一样。

实际情况究竟如何呢？实际情况是，这个游戏并不是公平的——我的获胜概率是你的 3 倍！虽然“正反反”和“反反正”在一串随机硬币正反序列中出现的频率理论上是相同的，但别忘了这两个序列之间有一个竞争的关系，它们要比赛看谁先出现。一旦抛掷硬币产生出了其中一种序列，游戏即宣告结束。这样一来，你就会处于一个非常窘迫的位置：不管什么时候，只要掷出了一个正面，如果你还没赢的话，你就赢不了了——在出现“反反正”之前，我的“正反反”必然会先出现。

事实上，整个游戏的前两次硬币抛掷结果就已经决定了两人最终的命运。只要前两次抛掷结果是“正正”、“正反”、“反正”中的一个，我都必胜无疑，你完全没有翻身的机会；只有前两次掷出的是“反反”的结果，你才会赢得游戏的胜利。因此，我们两人的获胜概率是 3:1 ，我的优势绝不止是一点。

你或许想问，如果已知我的硬币序列是“正反反”，那么你应该选择一个怎样的硬币序列，就能保证获胜概率超过我呢？研究表明，你可以选择“正正反”，这样一来，我们两人的获胜概率将会变为 1:2 ，换句话说你将会有 2/3 的概率获胜。 Using your Head is Permitted 趣题站 2014 年 5 月的趣题对此进行了更深一步的探究。

A 、 B 两人打算玩这么一个游戏。首先， A 选择一个长度为 n 的正反序列，然后 B 再选择另一个长度为 n 的正反序列。之后，不断抛掷硬币，哪名玩家所选的正反序列最先出现，哪名玩家就获胜。我们的问题是，假如两名玩家都采取最优策略的话，对于哪些 n ，游戏对玩家 A 更有利一些（换句话说，玩家 A 拥有超过 50% 的胜率），对于哪些 n ，游戏对玩家 B 更有利一些（换句话说，玩家 B 拥有超过 50% 的胜率）。今后，为了方便起见，我们用数字 1 代表“正面”，用数字 0 代表“反面”。

当 n = 1 时，两名玩家的获胜概率显然相同。当 n = 2 时，可以验证，除了 00 打 10 以及 11 打 01 的胜率之比是 1:3 以外，其他所有情况（包括 00 打 11 、 00 打 01 、 01 打 10 、 11 打 10 等四种）的胜率之比都是 1:1 。因而，如果两名玩家都采用最优策略的话， A 一定会选择 01 和 10 之一，从而避免 B 获得 3 倍于自己的胜率。最终结果便是，两人的胜率之比维持在 1:1 的位置，获胜概率仍然相同。令人意想不到的是，当 n > 2 时，游戏总是对玩家 B 更有利的。换句话说，我们要证明，当 n > 2 时，不管 A 选择的 01 串是什么，玩家 B 总能有针对性地选择一个恰当的 01 串，使得他获胜的概率大于 50% 。事实上，我们会证明这样一个结论：玩家 B 总可以截取 A 所选的 01 串的前 n – 1 位，再在前面加上一个数字 0 或者数字 1 作为自己的 01 串，从而使得自己获胜的概率至少有 (2 – (1/2)n-1)/3 。

不妨把 A 选择的 01 串记作 Py （其中 P 是一个长度为 n – 1 的 01 串， y 则表示数字 0 或者数字 1 ），我们先来看看，如果 B 选择的 01 串是 0P ，结果将会怎样。

不断抛掷硬币，直到最近 n – 1 次硬币抛掷结果正好是序列 P 。这有三种情况：情况一，最近 n 次硬币抛掷结果是 0P ；情况二，最近 n 次硬币抛掷结果是 1P ；情况三，目前硬币抛掷次数还不足 n 次。情况三是最为特殊的，它意味着整个游戏的前 n – 1 次硬币抛掷结果正好就是序列 P ，其概率为 (1/2)n-1 。让我们假设情况一出现的概率是 p1 ，则情况二出现的概率就是 1 – (1/2)n-1 – p1 。

如果出现了情况一，那么玩家 B 就直接获胜了，游戏结束；如果出现了情况二或者情况三，那么游戏仍需继续进行下去。不妨把此时的游戏局面叫做节点 X 。现在，玩家 A 离胜利已经非常接近了。如果下一次抛掷硬币的结果正好是 y ，那么玩家 A 就获胜了，游戏结束；如果下一次抛掷硬币的结果是 y （这里 y 表示与 y 相反的数字），那么游戏将会到达另外一个关键的中间状态：最近 n 次硬币抛掷结果为 Py 。对于两名玩家来说，这是全新的起跑线。如果下一次出现 P 的时候，它前面的那个数字是 0 ，那么玩家 B 就直接获胜了，游戏结束；如果下一次出现 P 的时候，它前面的那个数字是 1 ，那么游戏状态又会回到节点 X ，玩家 A 将会再次得到一个制胜的绝佳机会。不妨假设以 Py 打头的随机 01 序列中，下一个 P 的前面正好是数字 0 的概率为 p2 ，那么下一个 P 的前面正好是数字 1 的概率就是 1 – p2 。于是，整个游戏的状态转移图如下图所示。

玩家 B 获胜的概率就可以用 p1 和 p2 表示出来了。首次出现 P 的时候玩家 B 就获胜的概率为 p1 ，有另外 1 – p1 的概率进入节点 X 。进入节点 X 以后， A 将会有 1/2 的概率获胜， B 将会有 (1/2) · p2 的概率获胜，其余情况下游戏局面将会回到节点 X ，刚才的各种事件会以相同比例的概率再次发生，并且有可能一遍一遍地重复下去。因此，总的来说，进入节点 X 以后，两名玩家的获胜概率之比是 (1/2) : ((1/2) · p2) ；进而得出，进入节点 X 以后，玩家 B 获胜的概率就是 ((1/2) · p2) / (1/2 + (1/2) · p2) = p2 / (1 + p2) 。

综上所述，玩家 B 的获胜概率应为：

W0 = p1 + (1 – p1) · p2 / (1 + p2)

别忘了，上述概率值仅仅是 A 在选择了 01 串 Py 之后， B 以 0P 应对时获胜的概率。如果 B 选择以 1P 应对呢？整个游戏的状态转移图将会变成下面这样。

前面我们说过，硬币序列里第一次出现 P 的时候，最近 n 次硬币抛掷结果是 0P ，最近 n 次硬币抛掷结果是 1P ，目前硬币抛掷次数还不足 n 次，这三种情况的发生概率分别为 p1 、 1 – (1/2)n-1 – p1 和 (1/2)n-1 。然而，这次玩家 B 选择的 01 串变成了 1P ，因而游戏开始时进入两条支线的概率就成为了图中所示的那样。另外，从 Py 出发随机产生 01 串，下次出现 P 时它的前面正好是数字 1 的概率为 1 – p2 ，因而我们需要把第一幅状态转移图当中的所有 p2 都替换成 1 – p2 。可以计算出，进入节点 X 以后，两人的胜率之比为 (1/2) : ((1/2) · (1 – p2)) ，其中 B 的获胜概率为

((1/2) · (1 – p2)) / (1/2 + (1/2) · (1 – p2)) = (1 – p2) / (2 – p2)

玩家 B 的总获胜概率就是：

W1 = 1 – (1/2)n-1 – p1 + ((1/2)n-1 + p1) · (1 – p2) / (2 – p2)

我们要证明的即是， W0 和 W1 总有一个大于等于 (2 – (1/2)n-1)/3 。注意到，如果固定 p2 不变，把 W0 和 W1 都看作是关于 p1 的函数，那么 W0 将会是一个线性递增函数， W1 则是一个线性递减函数，因此最坏的情况将会发生在 W0 = W1 的时候，此时 W0 和 W1 中的较大值达到最小。解得

p1 = (1/3) · (2 – (1/2)n-1 – p2 – (1/2)n-1 · p2)

把上式代回 W0 或者 W1 当中的任意一个，得到的是一个与 p2 无关的数，它正是 (2 – (1/2)n-1)/3 。下图是 n = 3 时 W0 和 W1 的图像，可以看到两个图像相交在一起，形成了一条高度大约为 0.58 的交线。至此，我们便成功地证明了，当 n > 2 时，不管 A 选的 01 串是什么， B 总能有针对性地选择另一个 01 串，使得获胜概率可以高达 50% 以上。

事实上，如果把玩家 A 的选择记作 Py ，那么玩家 B 的最优策略一定就是 0P 和 1P 之一。这个结论是由 Leonidas Guibas 和 Andy Odlyzko 在 1978 年合写的一篇论文里证明的。当 n = 3 时，玩家 B 的最优策略可以归纳如下：

掌握了上面这个表格的话，你就拥有了一个骗小女生的绝好工具。 YouTube 的 Scam School系列视频上就介绍了这个 bar trick ：把游戏规则告诉小女生，让她先选一个长度为 3 的硬币序列，然后你再按照上表选择一个对应的硬币序列，你便能保证获得至少 2 倍于她的胜率。重复多次游戏，你将会以很惊人的大比分获胜。你甚至不需要刻意去背表格，只需要记住：如果对方的选择是 wxy ，那么你选择 xwx 就行了。

当然，玩家 B 的最优选择也并不总是把 Py 的第 2 位取反后加在 P 的前面。当 n = 5 时，如果 A 选择了 10110 ，那么 B 选择 11011 会得到 7/12 ≈ 58% 的胜率，而选择 01011 则会得到 17/24 ≈ 71% 的胜率，后者才是他的最优选择。 Leonidas Guibas 和 Andy Odlyzko 认为，玩家 B 究竟是选 0P 更好还是选 1P 更好，这并没有一个明显的规律。

有人或许想问，这些概率值都是怎么计算出来的呀？ John Conway 在 Winning Ways for Your Mathematical Plays 的第 4 卷中提到了一种方法。假如 a 和 b 是两个 n 位 01 串。如果 a 和 b 完全相等，那么记一个数字 1 ，如果不相等，那么记一个数字 0 。接下来，比较 a 的后面 n – 1 位以及 b 的前面 n – 1 位，如果相等，那么接着记一个数字 1 ，如果不相等，那么接着记一个数字 0 。接下来，比较 a 的后 n – 2 位以及 b 的前 n – 2 位，并根据比较结果记下数字 0 或者数字 1 。不断这样做下去，直到最后比较 a 的最后面 1 位和 b 的最前面 1 位，并产生新的数字。在整个过程中，你会依次记下 n 个数字，最终会得到一个 n 位的 01 串。把它当作一个二进制数，并转换成十进制。我们把最终的结果记为 L(a, b) 。举几个例子：

• L(10110, 10110) = (10010)2 = 18
• L(10110, 01011) = (00001)2 = 1
• L(01011, 01011) = (10000)2 = 16
• L(01011, 10110) = (01001)2 = 9

那么， 01 串 a 和 b 的胜率之比就是

(L(b, b) – L(b, a)) : (L(a, a) – L(a, b))

因此， 10110 和 01011 的胜率之比就是 (16 – 9) : (18 – 1) ，也就是 7:17 。刚才玩家 B 的获胜概率 17/24 ≈ 71% 就是用这种方法算出来的。不过， John Conway 本人似乎从未发表过这个神奇公式的正确性证明。

其实，之前在证明这个游戏对 B 更有利的时候，证明过程当中有一个小漏洞，我们有意没说：如果 Py = 000…00 的话，那么 0P 将会等于 Py ；类似地，如果 Py = 111…11 的话，那么 1P 将会等于 Py 。这违反了游戏的规则（两人不能选取相同的 01 串），而且也没法套在刚才的状态转移图里。好在，这两种情况单独分析起来非常容易。事实上，我们很容易证明， A 永远不应该选择 000…00 或者 111…11 ，因为这是最笨的策略。如果 A 选择的是 000…00 ，那么 B 只需要选择 100…00 即可。容易看出，只有开局后的前 n 位硬币序列恰好是 000…00 的情况下， A 才能获胜，如果第 n 次抛掷硬币以后 A 还没获胜的话，那么 B 就锁定胜局了——在出现 000…00 之前， 100…00 必然会先出现。因此， A 的胜率仅为 (1/2)n ，而 B 的胜率则为 1 – (1/2)n 。为什么说这是 A 最笨的策略呢？这是因为，不管 A 选择了什么 01 串，他获胜的概率至少也有 (1/2)n （即开局后的前 n 位硬币序列恰好如 A 所选的情况），因而刚才那种策略的获胜概率已经达到下限，糟糕得不能再糟糕了。类似地，如果 A 选择 111…111 ，那么 B 可以选择 011…11 ，这同样能让 A 的获胜概率降到最低。

讨论到这里，大家肯定想要问：那么， A 的最优策略又是什么呢？

1992 年， János Csirik 在一篇论文中指出，当 n > 3 时， A 的最优策略之一是 1000…0011 （中间有 n – 3 个数字 0 ），此时 B 应该选择 01000…001 来应对，两人的胜率之比将会变成 (2n-2 + 1) : (2n-1 + 1) 。当 n = 3 时，查阅上面给出的表格可知， A 的最优策略可以是 010, 011, 100, 101 当中的任意一个。当然， A 的最优策略并不能让 A 的获胜概率大于 50% ，只能让 A 的损失尽可能地小罢了。

对了，这个有趣的游戏叫做 Penney’s game ，它是由 Walter Penney 在 1969 年提出来的。