入れ替えをしまくって全部が入れ替わる確率・統計

１～６４個数字を選びここから２個選んで場所を入れ替え、それからまた2個選んで入れ替えるのを繰り返したら全部が入れ替わる確率はどのくらいでしょうか？
６４個から２個選ぶ組み合わせは2016個ありますが、例えば６４回やってもずっと同じ場所にいる確率は０にはならないので・・・
何回ぐらい入れ替えたら許容範囲になるのかおしえてもらいませんか？
閾値とかを設けてカイ二乗とかでだせばいいのか

１
＿＿＿＿＿＿
６４！×６３！とかでかい数字でしょうか

No.3 ベストアンサー 回答者： stomachman 回答日時： 2021/01/13 21:18

1〜Nの数を並べ替えるやり方はN!通りある。

その中で、「全部が入れ替わる」状態というのは「どのk(1〜N)についてもk番目の数がkではない」ということでしょう。
　そういう並べ方の場合の数は、Nが大きい時、全体(N!通り)の1/e ≒ 0.368倍になることが知られています。（eは自然対数の底, 2.71828… という数値です。）例えば N=4のときで0.375, N=5のとき0.367ぐらいですから、N=64なら文句なしに0.368である。
　ですから、ランダムに「入れ替えをしまく」った結果「全部が入れ替わる」状態になる確率は64.2%です。いくら頑張って「入れ替えをしまく」っても、これが平衡状態です。

　さて、ご質問は、この平衡状態に達するにはどのぐらい頑張ればいいか、ということでしょう。
　最初に1〜Nの数を小さい順に並べてあったとして、その中から2つをランダムに選んで入れ替える、という操作をN/2回繰り返したとき、一度も選ばれない数が残っている確率もまた、1/eです。そして、入れ替えの操作をさらにm倍（すなわちmN/2回）繰り返せば、その確率は1/(e^m)になる。
　なので、「一度も選ばれない数が残っている確率」を例えば0.1%になるようにしたければ、m=7ぐらい、つまり7×64/2 回ぐらい操作を行えばいいということです。

…ということをご理解の上で、「許容範囲」とはどういうことなのか、もう一度お考えになってはいかがでしょうか。

この回答へのお礼

回答ありがとうございます。
丁寧な説明ありがとうございます。
m＝7というのはどこからでてきたのでしょうか？
1/(2.71828＾7)
＝0.000911886
m＝6は0.00247
で認識は合ってますでしょうか？

お礼日時：2021/01/14 09:31

No.5 回答者： stomachman 回答日時： 2021/01/14 13:00

No.3へのコメントについてです。

> m＝7というのはどこからでてきたのでしょうか？
> 1/(2.71828＾7)
> ＝0.000911886

その通りです。だから 1/(2.71828＾7) ≒ 0.1%です。

この回答へのお礼

ありがとうございました。
参考になりました。

お礼日時：2021/01/14 15:32

No.4 回答者： stomachman 回答日時： 2021/01/13 21:43

No.3訂正です。

> 「全部が入れ替わる」状態になる確率は64.2%

「全部が入れ替わる」状態になる確率は36.8%です。

No.2 回答者： yhr2 回答日時： 2021/01/13 14:18

「64 個からランダムに２個を選んで入れ替える」という操作を繰り返していくことを考えて、「１回も選ばれていない数がある」ということは「入れ替わっていない数がある」ということですから、少なくともどの数字も「少なくとも１回は選ばれている」ということが必要です。

これは「１回も選ばれていない数がある」ということの余事象です。

「ｎ回操作を行なったときに、ある数が１回も選ばれない」確率は、二項分布なので（各回で選ばれる確率 = 2/64, 選ばれない確率 = 62/64, 実際に選ばれる回数 = 0）
　P(n, 0) = nC0 * (2/64)^0 * (62/64)^n = (31/32)^n
です。

従って「どの数字も少なくとも１回は選ばれている」確率は
　1 - (31/32)^n
ただし、64 個すべての数字を選ぶには、最低でも n≧32 でないといけません。
n → ∞ の極限では「１」になりますが、有限の n では「１」未満です。

こんな感じで考えてみればよろしいのでは？

ただし、複数回選ばれて、結局元の位置に戻ってしまったというものは考えていません。そこまで考えるには「何と何の数字を交換するか」というところまで立ち入らないといけませんので、ちょっとお手上げです。

この回答へのお礼

回答ありがとうございます。
反復事象で順当に全てが1回で入れ替われば最低32回というのはわかりました。複数回選ばれた過程を考えてました。絶対100パーセントにはなり得ないですよね。元に戻る場合もありますしね。

お礼日時：2021/01/14 09:37