"完美"的洗牌次数 - 7次 << 阅微堂



"完美"的洗牌次数 - 7次 « 阅微堂

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

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

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

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


Read full article from "完美"的洗牌次数 - 7次 « 阅微堂


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts