Games People Don’t Play 续

数月前的 blog 提到的短文 Games People Don’t Play 中,作者最后留给读者下了一个未解的问题。这周末终于有时间静下心来解一下,却发现比原来想象的更困难(本来以为用型理论可以搞定,然后发现数值差太多了),于是最后只好作弊查出处 On the Autoreducibility of Random Sequences 了。

简述题目:
15人,头顶上随机分配红色或蓝色的帽子({R,B} i.i.d. 50% 概率)。每人能看到其他人的帽子颜色,但不知道自己的帽子颜色。每人可以选择猜测自己头上帽子的颜色,也可以选择放弃。成功的条件是至少有一人猜测,并且猜测全部都是正确的。不允许任何交流,也不知道别人是选择猜测还是放弃。事先可以交流并制定策略。

最简单的策略是统一指定一人作出猜测,这样是 50% 的成功率。

更优的策略涉及概率论和信息论的一些知识要点。因为有趣所以记叙于本文。

策略要点如下:

  1. 首先,任何一人的一次猜测只有 50% 的正确率。
    因为帽子是随机分配的,对于作出猜测的那个人来说,别人头上帽子的颜色和他的帽子的颜色完全没有相关性,加之不允许交流,这一情形完全等同于在他的猜测后再给他随机分配帽子。
    从这点看,上面 50% 的成功率似乎已经是最好的结果了。
  2. 但是还有另一个自由度,对于一人来说,他还能选择猜测的时机。
    简化起见,考虑只有3人的场景。策略是如果看到其他二人帽子颜色相同,就猜测相反颜色,否则放弃。考虑4种等概率情况,RRR,RRB,RBR,BRR (另外4种对称)。RRR 下全员猜错,而其它3种情况下都是一人猜测并猜对。这一策略下成功率上升至 3/4。
    注意在4种情况下总共3人做了6次猜测,一半正确一半错误,与(1)并不矛盾。可见,好的策略的必要条件是,如果结果成功,让尽可能少的人做猜测,而如果结果失败,则让每个人都做出猜测。
  3. 在人数增加的情况下,策略将更复杂。需要使用1位纠错码的知识,用来决定究竟由谁来做出猜测,猜红还是蓝。
    (查出处前,我的思路到这里,没有毅力继续找纠错码了)
  4. 其实,应用的纠错码仅仅是简单的 Hamming 码
    要点是把所有人头上的帽子排成一个码字。将这个码字看成是 (15, 11) Hamming 码。所有码字的数量是 2^15 = 32768,其中正确码字的数量是 2^11 = 2048。于是一个码字可能是正确码字,也可能是错误码字。如果是错误码字,仅在其中一位上,将红蓝反转,会得到正确码字(这是1位纠错码的定义)。实行策略则是,所有人都假定得到的是错误码字,那么只有一个人位于能纠正该错误码字的位置上,由他作出猜测。这样,如果分配下来帽子形成的的确是错误码字,则一人猜测正确,结果成功,如果是正确码字,则所有人都猜测错误,失败。成功的概率为 1 – 2^11 / 2^15 = 93.75% (就是 15/16,50%中猜对的被分配到15次的成功情况,失败的全部集中到1次失败情况)。
    这样解释稍抽象了些,仍以3人为例,使用的是 (3, 1) Hamming 码(就是3位重复码,正确码字为 RRR 和 BBB)。如果得到的是正确码字的 RRR,每人都假定错误码字并认为自己位于纠错位上(各人认为是 BRR,RBR,RRB),于是全员猜测并失败,而如果是 RRB,前两人无法纠错(对第一人来说,不管 RRB 还是 BRB 都不是正确码字,第二人类似)于是放弃,最后一人纠错,确定码字为 RRB,猜测正确。
Advertisements
This entry was posted in Science and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s