摸箱子问题以及在Static data structure problems上的应用

zhiqiang十二月 16, 2008 计算机科学

以前提到过，理论计算机这门课会邀请一些正在这边访问的教授来讲课，由于是本科生，所以这些教授一般都是讲些有趣的东西，比如之前的overhang 堆积木 - 能伸出桌面多远？。今天这次课，来自Aarhus的Peter Bro Miltersen讲了一个很有趣的游戏问题。

现在有100个箱子，有一个学生，一张写着他的名字的名片被放在某个随机选择的箱子里面。现在这个学生可以检查不超过一半也就是50个箱子，希望能够把它的名字找出来。

很显然，这个学生没有什么好的方法，随机选择50个箱子打开，有一半的概率可以发现含有它的名字纸条的箱子。

OK，现在还是100个箱子，但是有100个学生，写着这些学生的名字的100张纸条随机放入100个箱子里(每个箱子恰好一张纸条)。现在每个学生可以检查不超过一半也就是50个箱子，每个学生希望能找到含有自己名字的箱子。如果在游戏中，所有学生都是独立的（他们不能互相讨论以及看到其他人的开箱结果），问所有学生都实现目标的概率有多大？

如果把每个学生的结果认为是独立的，那么成功的概率只有2^{-100}，但其实我们可以做的比这要好得多。事实上，让每个学生都找到含有自己名字的箱子的概率可以高达0.3。

假设学生的名字就是它的编号，从1到100。第i个箱子里的编号是\pi(i)。第i个学生这样做：先打开第i个箱子，再打开第\pi(i)个箱子，再打开第\pi(\pi(i))个箱子，以此继续下去，直到发现写着自己名字（也就是i）的纸条或者打开箱子数到达50个为止。

那么当且仅当在i到\pi(i)这个置换中含有长度超过50的圈时，有学生找不到含有自己名字的箱子。这个概率是\sum_{j=51}^{100}1/j \sim \ln 2（注意一个随机置换里含有一个长度为j的圈的概率为1/j）。

所以上面策略的成功概率为 1-\ln 2 \sim 0.3。

类似于以前提到的帽子游戏一以及帽子游戏二，我们要最大化一个团体都成功的概率，但是每个单个个体成功的概率又是一定的，那么我们只需要设计策略时，让大家要么几乎同时成功，要么几乎同时失败。就像上面的策略里，如果有人失败，意味着排列中有一个长度很大（大于n/2）的圈，这个圈上所有人同时也会失败，通过把失败的实例重合到一起，这样就提高了总体成功的概率。

上面这个问题不是孤立的，它可以应用在static data structure problems的下界证明上。对于后面这个问题，在最近是一个很热门的研究领域，但在这里写了也没人看，知道这个问题的也不需要看，所以我只提一下我们还可以做什么，下面是一个open problem，可以直接得出一个data structure问题的一个下界，是一个可以写学术论文的题目：

Open problem：假设现在有2n个箱子，n个学生，学生们的名字纸条被放入随机选中的n个箱子里。现在每个学生可以检查不超过一半也就是n个箱子，以找到含有自己名字的箱子。问这时候学生可以采取什么样的策略最大化所有学生都成功找到含有自己名字的箱子的概率。

期望结果：证明指数级小的下界或者找到常数概率的策略。

有兴趣的可以参考The cell probe complexity of succinct data structures.

关于, , , »
  • 策略游戏：医生和病人（I） 我很早之前就想过这个问题，但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案，故记录在此。有兴趣的可以自己想...
  • "完美"的洗牌次数 - 7次 在大家玩牌的时候，每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌，但多少次洗牌才是正当的呢？就我多次打牌的观察，...
  • 最佳约会策略 题外话：最近阅微堂发的都是网友转发的政治方面的文章，不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题，已经被研究了很多年，有...
  • 征集3个人分蛋糕的方法 Yao在课程《理论计算机II》的第一节课上提到的一个问题： 三个人如何平分一块蛋糕？ 要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自...
  • 杀人的理论分析 “杀人”，英文名为"Mafia Game"，广泛流传于国内外。上个星期我们在玩的时候被Elchanan Mossel发现，然后他给了一个talk，内容就是杀人的理论分析。 ...
  • 帽子游戏二 这个题目听说是MSRA的面试题。 在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参...
  • 硬币游戏 Alice和Bob两人玩一种硬币游戏。游戏在一个$$2\times2$$的棋盘上进行，棋盘上每个格子上都有一枚硬币。在每一回合，Alice可以决定选择翻转某两枚或者一...
  • TCS: 拜占庭将军问题 (The Byzantine Generals Problem) 这个问题在Yao的理论计算机课上整整讨论了2节课。它是一个算法设计问题，也极具趣味性。下面是它的一些介绍和解决方案([1])。 拜占庭帝国就是5...
  • 硬币游戏的答案 前两天贴出了一个硬币游戏，希望寻找一种胜利策略。这是一个非常有意思的题目，没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布...
  • Google的疯狂面试题 有一些是火星题，比如最后一个海盗分金，不太可能还用来作为面试题，估计是被拉过来凑数的。 原文（英文）直接到这里看吧，27floors给出了中文翻...
15条留言 -> 跳到留言表格
  • At 2008.12.16 17:56, Roy said:

    期待结果中所谓得常数概率的策略不是已经给出了吗？不是很理解。

    [Reply]
    • At 2008.12.16 20:05, zhiqiang said:

      注意open problem里面的箱子个数有2n个，也就是有些箱子将是空的。这样最开始那个0.3的策略就不能用了。

      [Reply]
    • At 2008.12.16 19:16, DavidW said:

      有趣。但是如何论证0.3就是最大值呢？

      [Reply]
      • At 2008.12.16 20:06, zhiqiang said:

        因为成功概率之多为0.5，所以只有常数倍数的gap，在我们理论计算机领域已经不考虑了 :)

        [Reply]
      • At 2008.12.16 19:16, DaiLiang said:

        是不是这些问题（比如这个问题，还有那个帽子问题）都可以等价于一个编码问题，最后都可以根据香农的编码理论可以有一个压缩的方法（虽然未必能达到压缩的极限）？

        [Reply]
        • At 2008.12.17 01:21, Zig said:

          我还以为miltersen转行去做game不做data structure了呢。

          [Reply]
          • At 2008.12.17 21:34, stone said:

            "一个随机置换里含有一个长度为j的圈的概率为1/j"
            应该是小于等于1/j吧!

            [Reply]
            • At 2008.12.17 22:11, zhiqiang said:

              没有错，就是恰好是1/j。

              [Reply]
              • At 2008.12.18 09:56, stone said:

                j=1表示所有置换都含有长为1的圈？

                [Reply]
                • At 2008.12.18 11:21, zhiqiang said:

                  嗯，那个结论需要“j>n/2”。

                  [Reply]
            • At 2008.12.20 11:02, jiapeng said:

              现在我们正在参加一个知识比赛，我感觉这个里面也涉及一个团队成功的问题。特向你请教。

              6队参加比赛，每对3人。

              给出6道判断题，每题10分，所有参赛队员均须做答，主持人每读完一题并提示开始做答后（读题的时候题目会打在背景上，因此队员可以看到整个题目，也就是有讨论的时间），所有参赛队员第一时间同时举牌作答，若该参赛队其中一名队员答错或犯规，则取消该名队员速答题后续题目答题资格，余下队员继续作答直至全部淘汰或本环节结束；

              举例：第一道题，如果3个队员都答对，加30分，3人继续比赛
              如果2个队员都答对，加20分，答对的2人继续比赛

              请教，对于这个规则，选择怎样的策略比较好呢？

              [Reply]
              • At 2008.12.20 11:57, zhiqiang said:

                我的感觉是这样的比赛中，三名队员几乎是互相独立的，对每个人来说，都是答错了都被淘汰，没看出能有什么团体的策略在里面。

                [Reply]
                • At 2008.12.28 14:48, riker said:

                  problem本身描述不严谨?若该参赛队其中一名队员答错或犯规,如果2个队员都答对
                  没理由一个参赛队的3人持最终不同的意见&result啊？

                  [Reply]
                • At 2010.02.17 16:22, 添夏 said:

                  思虑挺神奇 不过细节还有点错误
                  似乎仅当j=n的时候才会出现概率是1/j的情况（n！/（n-1）！），而且显然ln2不等于0.301 0.301是以十为底的对数

                  [Reply]
                  • At 2010.02.17 16:26, 添夏 said:

                    其他时候概率的确是1/j sorry刚才组合数算错了 不过ln2的确不是0.301

                    [Reply]
                    (Required)
                    (Required, not published)

                      B | I | U | D | 添加链接 | 插入引用 | 插入代码 | 插入表情 | 甲 | + | ?
                    «
                    »
                    guest | 注册 | 管理 | English | 繁體 | https

                    阅微堂

                    zhiqiang's personal blog
                    Loading...
                    Loading...
                    Loading...