摸箱子问题以及应用

作者:, 发表于

理论计算机笔记

查看该系列所有文章

以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的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.

Q.E.D.


上一篇:概率论感觉测试2008年9月29日
所有大学生都应该学的两门课程,一是经济学,二是概率论,这两门课分表代表着一种生活中的思维方式。来测试一下你的概率论学得怎么样吧。题目

下一篇:堵猫游戏2009年5月15日
试试吧。 当在全平面棋盘上玩这个游戏的时候,我们总是可以把猫围在一个特定的区域之内,但是这个游戏提供的范围太小了,好像并不总能够


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。