我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:满堂彩 > 后发制人 >

Penney 的游戏:正所谓后发制人先发制于人

归档日期:07-04       文本归类:后发制人      文章编辑:爱尚语录

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

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

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

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

  你或许想问,如果已知我的硬币序列是“正反反”,那么你应该选择一个怎样的硬币序列,就能保证获胜概率超过我呢?研究表明,你可以选择“正正反”,这样一来,我们两人的获胜概率将会变为 1:2 ,换句线 的概率获胜。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 。因而,如果两名玩家都采用最优策略的线 之一,从而避免 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) 。

  别忘了,上述概率值仅仅是 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 的获胜概率为

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

  0或者 W1当中的任意一个,得到的是一个与 p2无关的数,它正是 (2 (1/2)n-1)/3 。下图是 n = 3 时 W0和 W1的图像,可以看到两个图像相交在一起,形成了一条高度大约为 0.58 的交线。至此,我们便成功地证明了,当 n>

  2 时,不管 A 选的 01 串是什么, B 总能有针对性地选择另一个 01 串,使得获胜概率可以高达 50% 以上。

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

  有人或许想问,这些概率值都是怎么计算出来的呀? 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) 。举几个例子:

  其实,之前在证明这个游戏对 B 更有利的时候,证明过程当中有一个小漏洞,我们有意没说:如果 Py = 000…00 的线P 将会等于 Py ;类似地,如果 Py = 111…11 的线P 将会等于 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 的获胜概率降到最低。

  n-2+ 1) : (2n-1+ 1) 。当 n = 3 时,查阅上面给出的表格可知, A 的最优策略可以是 010, 011, 100, 101 当中的任意一个。当然, A 的最优策略并不能让 A 的获胜概率大于 50% ,只能让 A 的损失尽可能地小罢了。

  对结论我有一个简单的解释,不知道对不对:假设A的串长度是n,在抛出A串全部n次结果前,必然先抛出A串前n-1次结果,那么无论B选“1+A(n-1)”或者“0+A(n-1)”都会导致B比A提前一步完成,即B赢。

  应该不一定吧 比如玩家A的序列是P-1-P-0,最后一个0即为文中的y,B的序列为0-P-1-P,当实际序列1-P-1-P-y,y=1时,这时A最后一段不完美了,但是却还是进行了一半,而B确实是从新起点开始

  正序信息是指“如果A是正反反 那B的公平正序信息必需反正正 也可以成为负正序信息”

  不过大多数时候 千术就用“逆序信息来模糊负正序信息” 所以导致了“正反反倒过来读的反反正”

  甲对乙说:“我们这样打赌吧。你随意选一个由红和黑组成的三个颜色的组合,比如说红-红-黑,或者黑-红-黑,或者红-红-红。然后我就选另外一个三个颜色的组合。然后我们一起定一个时间,开始观察那台机器中滚出来的球的颜色,看谁的组合作为一个整体先出现。谁的先出现就算谁赢了。我用5:4的赌金和你打赌。每次我们赌的规则都是如此,你先选组合,好吗?”

  乙想了一下:“任意一种组合出现的概率都是1/8,我们是平等的,但是他每次押的赌金都比我多,看来我是可以赚的。”于是就同意了。

本文链接:http://meimeisyo.com/houfazhiren/90.html