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

让我们来玩一个游戏。连续抛掷硬币,直到最近三次硬币抛掷结果是“正反反”或者“反反正”。如果是前者,那么我获胜,你需要给我 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 的最优策略可以归纳如下:

如果 A 选的是 那么 B 应该选 两人的胜率之比
000 100 1:7
001 100 1:3
010 001 1:2
011 001 1:2
100 110 1:2
101 110 1:2
110 011 1:3
111 011 1:7

掌握了上面这个表格的话,你就拥有了一个骗小女生的绝好工具。 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 年提出来的。

55 条评论

  • 左耳朵在听

    前排0.0

  • Gothic

    大神…

  • classicallzk

    太神奇了……改天和人玩玩

  • 渊栩

    感觉挺好玩,明天和朋友试试~

  • 哈哈

    好高端

  • godultimate24

    终于等到你

  • Maigo

    这个问题在《具体数学》里面讲了10页啊!

  • dr what

    好极了,我这就去用这个骗小女生去,大家等着我的捷报吧!

  • 绅士

    不应该是Penny吗……

  • D-LIGHT

    刚刚买了你的那本书,很有意思!!!
    每次读都有种茅塞顿开的感觉。

  • fjzzq2002

    很有意思!

  • cookie

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

    • Karson

      1f1Olá meninas, no início de janeiro eu comprei três luvinhas de inverno na asos, o total ficou em 29,90 USD e janeiro, o único acÂsir©Ãcƒmo foi um valor de 1,19 USD que veio na minha fatura e eu acho que foi porque usei o paypal, mas não fui taxada não, por isso fiquei na dúvida sobre o sistema de impostos já que vocês informam que como a asos é PJ então deveria haver imposto em todas as compras. Sim ou não? Abraços

  • Leonhardt24

    “那么游戏将会到达另外一个关键的中间状态:最近 n 次硬币抛掷结果为 Py 。对于两名玩家来说,这是全新的起跑线。”
    应该不一定吧 比如玩家A的序列是P-1-P-0,最后一个0即为文中的y,B的序列为0-P-1-P,当实际序列1-P-1-P-y,y=1时,这时A最后一段不完美了,但是却还是进行了一半,而B确实是从新起点开始

    • Dr. What

      这没关系的。不管它完美不完美,你提到的都只是p2的细节问题,是从节点出发后到哪边的概率。这可能会影响p2的大小,也就是可能会对B选择0还是1有影响,但是对题目本身的证明没有影响。

  • rookiepig

    请问matrix67的邮箱是啥? 想发个邮件,问个问题 -.-

    网上搜出来这个:“我的邮箱是 matrix67 at tom.com ,或者 gs.matrix67 at gmail.com”
    靠谱么?

  • Error202

    具体数学中有很详细的推导过程

  • godultimate24

    上面第二个转移图应该不是2+p,而只是p吧

  • saber_Wen

    我觉得很奇怪,要是不是两个人玩呢,比如A选000,B选100,C选110,D选011,E选001,F选100。按照理论,胜率是B>A,C>B,D>C,E>D,F>E,但是F跟B是一样的胜率。如果我们考虑足够大的比赛次数,A-F均参加比赛,按照上面的逻辑不是最终胜的次数应该F>E>D>C>B>A么,但是B=F,哪里不对呢。

    • saber_Wen

      所以我感觉还是一样的胜率合理一些

    • JerryRoc

      六个人,3bit只有六种情况,这样三个数字出来之后必定会结束,不满足题目条件了,如果少一个人才可以讨论,这时候作为最后一个人,如果别人前N-1个序列一样,结论还是一样的。

    • 3244353552

      在这种概率型的游戏里,B>A,C>B,D>C,E>D,F>E并不代表F>B或者B>F。M的有一篇文章里就讲过

  • elf

    把倒数第二位取反加到头上,反正就是让A极可能多的位数帮B打基础

  • T00T

    正反概念的赌博 只要关注正序信息 就可以知道是否公平!
    正序信息是指“如果A是正反反 那B的公平正序信息必需反正正 也可以成为负正序信息”
    不过大多数时候 千术就用“逆序信息来模糊负正序信息” 所以导致了“正反反倒过来读的反反正”

  • toutatis2010

    厉害,学习了!明天骗人去!嘻嘻

  • Psycho7

    前来围观大神了,学习学习!想当初还是在搜Miller-Rabin素数测试的时候看到顾大神的博客,随后发现挺有意思的就一直在看,书昨天也到手了感觉挺好玩的。

  • 方程

    虽然比赛最终一定会有一方胜利(无限长的01串总会出现任意的子串),但如果真的要比赛一会,n最好不要选得太大。n超过10之后,比赛已经很难在合理的现实耗时内决定胜负了……

  • fjzzq2002

    M大牛N日不更…

  • XFause

    恭喜开始继续月更..真是把妹绝技啊…

  • Wangzhpp

    想起来了用AC自动机+高斯消元做的某OI题……

  • 可测松鼠

    代替榴莲阅。

  • Yhzhtk

    有意思,表面看概率一定认为异议。实际却不是,因为他是一个未知长度的序列

  • Dapper

    真的超有意思,主要是在已知序列长度上做文章了

  • 闲云野鹤

    网上有个类似的智力趣题:
    赌场里的约定
    在拉斯维加斯的赌场里,一台机器中正在随意滚出红球和黑球,滚出这两种球的概率都是1/2。机器前甲乙两人正在讨论打赌的事。
    甲对乙说:“我们这样打赌吧。你随意选一个由红和黑组成的三个颜色的组合,比如说红-红-黑,或者黑-红-黑,或者红-红-红。然后我就选另外一个三个颜色的组合。然后我们一起定一个时间,开始观察那台机器中滚出来的球的颜色,看谁的组合作为一个整体先出现。谁的先出现就算谁赢了。我用5:4的赌金和你打赌。每次我们赌的规则都是如此,你先选组合,好吗?”
    乙想了一下:“任意一种组合出现的概率都是1/8,我们是平等的,但是他每次押的赌金都比我多,看来我是可以赚的。”于是就同意了。
    请问,如果甲乙两人都足够聪明,那么这个赌约对谁有利? 为什么?

  • 闲云野鹤

    四川教育出版社1989年出版的一套《数学小品译丛》中的一本书《数学瑰宝 第3辑》第138页有对这个问题的简明分析,是加拿大滑铁卢大学的Ross Honsberger教授写的文章,一个很有名的数学科普作者。

  • zy498420

    随机过程的问题,用随机变量去建模,容易骗到小孩子

  • Fan Jin 金帆

    如果B将A的序列完全取反,会不会概率就一样了呢?

  • Sunslikes

    您好,实在是有趣,请问我可以转载您的文章吗,我会注明文章的出处的,谢谢。

  • Jodi

    Cotoranulatigns to Cool N Collective and Mr Repole on the great performance! I too would be conflicted. I love to see these tough older guys on the track but I'd worry every day he'd get hurt. Maybe a nice second career as a track pony?

  • tombwen

    【序列 P ,其概率为 (1/2)n-1 。让我们假设情况一出现的概率是 p1 ,则情况二出现的概率就是 1 – (1/2)n-1 – p1 】这段我真没看明白,P的概率是所有样本得出来的,那p2又不是p1和p的补集,概率怎么能那么算?这不是人为放大了概率吗?

  • Senny

    如果是1010和0101呢?

  • 吾读

    看过了。很好很强大。

发表评论