トランプのボゴソート

Math

ボゴソートとして52枚のトランプを投げる例が載っていますが、これが一体何回目のシャッフルでソートできる確率が 50% を越えるのかという話題があったので、やってみました。
1回の試行で揃う確率は \frac{1}{52!} なので、揃わない確率は 1-\frac{1}{52!} で、n 回連続で揃わない確率は (1-\frac{1}{52!})^n です。
この n がいくつになったら 0.5 未満になるかという問題なので、(1-\frac{1}{52!})^n=0.5 を解けばいいということになります。


で、簡単に式変形して n=\log_{1-\frac{1}{52!}}{0.5} を出してあとは計算するだけ。
まあこんなの普通に計算できるわけがないので、Wolfram 先生にお願いしてみました。

これによると 55907986708849934223332477802005467883470846982724974136224702698354.733... らしいので、55907986708849934223332477802005467883470846982724974136224702698355 回やれば 0.5 未満になり、ソートできる確率が 50% を越えそうです。


1ミリ秒間に 55907986708849934223332477802005467883470846982724974136224702698355 回シャッフルできるコンピュータがあればボゴソートもそれなりに使えそうですね。