fixedpoint.jp - トランプを何回混ぜれば十分にランダムになるか?




トランプを何回混ぜれば十分にランダムになるか?

トランプは遊戯だけでなくギャンブルや手品に用いられる際、カードの山(deck)における順番を不規則にするため混ぜるという行為(shuffle)を行います。混ぜる方法はさまざまありますが、riffle shuffleと呼ばれる半分ずつにした山を交叉させる混ぜ方が効率がいいことが知られています。

52枚のdeckについては、数学者にしてマジシャンでもあるDiaconisらによる研究成果(1992)で、riffle shuffleを7回繰り返せば十分ランダムになるということが証明されました。

しかしさらに、Trefethenらがランダムネスを測る基準を見直すとriffle shuffleを6回すれば十分だということを示しています: How many shuffles to randomize a deck of cards? (2000)

前者はtotal variation norm、後者はentropyでランダムネスを測っています。


© 2006-2016 fixedpoint.jp