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

作者: , 共 427 字
系列:生活中的数学

查看该系列所有文章

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

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

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

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

Q. E. D.

系列: 生活中的数学 »
今天上课的时候老师讲的,我觉得很有意思。
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
类似文章:
2007 年,我们讨论过一个算法问题, perfect shuffle ,据称是个微软面试题:
理论计算机(I)课上讲的一个问题,很有意思。
以前提到过,理论计算机这门课会邀请一些正在这边访问的教授来讲课,由于是本科生,所以这些教授一般都是讲些有趣的东西,比如之前的overhang 堆积木 - 能伸出桌面多远?。今天这次课,来自 Aarhus 的Peter Bro Miltersen讲了一个很有趣的游戏问题。
碎碎念 » TED, 魔术
刚看了一个 TED 视频,大衛布萊恩: 如何閉氣超過十七分鐘,里面有这么一段
相似度: 0.057
经济金融 » 股市, 赌场
牛人说的:股市和赌场有很多共同点,但他们有一点不一样,这一点使得股市不如赌场那样充满暴力。那就是股市里没有特定的交易对手
相似度: 0.055
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。
相似度: 0.051
首先申明一下,赌博是不对的,下面的讨论也更多是理论性的。
碎碎念 » 心理学,
4 月 26 日,在爱达荷州秋季大型科学展览会上,一个来自鹰石中学的高中生的方案获得了一个一等奖。
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自姚期智教授的理论计算机( I )的授课内容——我是其助教之一。