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

作者:, 发表于

理论计算机笔记

查看该系列所有文章

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

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

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

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

Q.E.D.


上一篇:TCS: 拜占庭将军问题 (The Byzantine Generals Problem)2006年9月22日
这个问题在Yao的理论计算机课上整整讨论了2节课。它是一个算法设计问题,也极具趣味性。下面是它的一些介绍和解决方案([1])。 拜占庭帝国就是5

下一篇:TCS课堂笔记:数据库存储问题2007年5月8日
理论计算机(I)课上讲的一个问题,很有意思。 已经一个n,m和$$\{1,2,\cdots, m\}$$里n个数,设计一种保存这n个元素的表的数据结构形式,使得对$$\{1,2,\cdots


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