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

作者:
系列:生活中的数学

查看该系列所有文章

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

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

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

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

Q. E. D.

系列: 生活中的数学 »
今天上课的时候老师讲的,我觉得很有意思。
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自 姚期智 教授的理论计算机( I )的授课内容——我是其助教之一。
碎碎念 » 心理学,
4 月 26 日,在爱达荷州秋季大型科学展览会上,一个来自鹰石中学的高中生的方案获得了一个一等奖。
这个问题有许多不同形式的阐述方式和变种,应用范围也很广。下面应该是比较吸引人和简单的那种,来自 姚期智 教授的理论计算机( I )的授课内容——我是其助教之一。