"完美"的洗牌次数 - 7次

在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,多数人都不超过4次。

但就D. Aldous和P. Diaconis在1992的一个结果,要想达到“比较完美”的洗牌效果——洗完牌后牌局基本上随机分布,至少需要5次,要达到“完美”洗牌,则需要7次。但更多次数不会有太多改进。这还是对于一副牌而言的。对于两副牌则需要9次,6副牌需要洗12次。

所用方法是计算图上随机游走达到稳定分布的速度。而这个方法就应用于上面这个结果之后,对于理论计算机的概率算法产生了深远的影响,这也使得P.Diaconis的这篇论文超出了它本身看似玩物的领域。

再谈一下P. Diaconis,此君14岁离家,去做职业魔术师,没上高中,后来用白天魔术表演挣来的钱晚上念大学课程,最后获得哈佛的博士和斯坦福的教职。另传说中,此人赌技惊人,是赌场不受欢迎之人物。

  • 摸箱子问题以及在Static data structure problems上的应用 以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆...
  • 最佳约会策略 题外话:最近阅微堂发的都是网友转发的政治方面的文章,不爱看的人会比较痛苦。现在讨论一个轻松一点的话题。其问题,已经被研究了很多年,有...
  • 概率论感觉测试 所有大学生都应该学的两门课程,一是经济学,二是概率论,这两门课分表代表着一种生活中的思维方式。来测试一下你的概率论学得怎么样吧。题目...
  • TCS课堂笔记:数据库存储问题 理论计算机(I)课上讲的一个问题,很有意思。 已经一个n,m和$$\{1,2,\cdots, m\}$$里n个数,设计一种保存这n个元素的表的数据结构形式,使得对$$\{1,2,\cdots...
  • 帽子游戏二 这个题目听说是MSRA的面试题。 在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参...
  • 魔方里的数学 今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学...
  • 来活跃活跃大脑 多做思维游戏有助于保持和提高智商 选钱袋 现在有两个人,"酷毙"与"帅呆",正在花园里一边喝着酒,一边讨论关于精灵的神话。正好有个精灵从此...
  • 杀人的理论分析 “杀人”,英文名为"Mafia Game",广泛流传于国内外。上个星期我们在玩的时候被Elchanan Mossel发现,然后他给了一个talk,内容就是杀人的理论分析。 ...
  • TCS: 拜占庭将军问题 (The Byzantine Generals Problem) 这个问题在Yao的理论计算机课上整整讨论了2节课。它是一个算法设计问题,也极具趣味性。下面是它的一些介绍和解决方案([1])。 拜占庭帝国就是5...
  • 三门问题及相关 写篇三门问题的终结版。欢迎补充材料。 三门问题,亦称为蒙特霍问题(英文:Monty Hall problem),最初的表述形式: 参赛者会看见三扇关闭了的门,...
6条留言 -> 跳到留言表格
  • At 2006.12.15 18:25, zhouqb said:

    这个世界上天才太多了,唉。前段时间看了费米传的一部分,他读过的东西不会忘。还有一个Sun的人提到有个在学校被认为是智障的也成了Sun的院士

    • At 2006.12.15 18:29, Yin Zhangqi said:

      我看过这个人的8g,他的这个研究结果还真是很有意思。

      • At 2006.12.16 08:43, sssli said:

        完美

        • At 2006.12.16 08:51, wisagan said:

          感觉强人的事总是被越传越神。

          • At 2007.09.26 20:32, 魔方里的数学 @ 阅微堂 said:

            [...] 这样的图与以前提到过的洗牌模型里面的图非常相似,结构简单,定点巨多,但混合速度却特别快(从一点会以非常快的速度达到其它点),做算法的很喜欢这种图。 http://zhiqiang.org/blog/posts/mathmatics-in-rubik-cube-and-algorithm-2.html [...]

            • At 2008.08.21 20:55, 天山新怪 said:

              我在研究加密的时候,曾经设想过洗牌加密模型。 :-)

              (Required)
              (Required, not published)

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

              阅微堂

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