Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

シャッフルしたカードを順番にならべていったら、その並び順と同じ数が出てこない確率はどれくらいだろうか

今日の料理

f:id:nisemono_san:20160808113612j:plain

メンチカツサンドを汚なく作る方法。

トレーズというゲーム、そしてその問題

トレーズ(treize)というゲームがある。このゲームの名前はフランス語で13を表している。このゲームは、ジョーカーを抜いた52枚のトランプを使って遊ぶ。

まず、トランプを良くシャッフルする。そのトランプのカードに1から順番を付けながらめくっていく。このとき、順番と同じ番号が出た場合は勝利し、次のプレイヤーに残りのトランプを渡す。当然ながら、順番とカードの数が一致しないときもある。このとき、プレイヤーは負けということになる。

そこで、このカードゲームにならって、我々は13枚のカードを用意することにしよう。そして、このカードを順番を付けながらめくっていった場合、果して順番と一致しない数しか出ない確率はどれほどになるだろうか。さらに、もしこのカードの枚数を2倍に増やした場合、勝つ確率は上がるだろうか。それとも下るだろうか。

相対確率を調べる

上記の問題は、『反直感の数学パズル』から引用したものである。ちなみに相対確率(試行から当てはまったものを使う方法)では、次のようにして調べることができる。

def treize n
  card = [*0..(n - 1)].shuffle
  card.each_with_index do |k, i|
    return true if k == i
  end
  return false
end

TIMES = 100000

2.upto(52) do |n|
  win = 0
  1.upto(TIMES) do
    win += 1 if treize n
  end
  puts "#{n}枚の当たった回数は#{win}, 確率は#{win.to_f / TIMES}"
end

このようにして出力した結果は下のようになる。

13枚の当たった回数は63272, 確率は0.63272
26枚の当たった回数は63277, 確率は0.63277
39枚の当たった回数は63165, 確率は0.63165
52枚の当たった回数は63187, 確率は0.63187

本書には、13枚で1枚以上当たる確率と、52枚一枚以上当たる確率は、理論上「0.632121」まで一致すると伸べている。

完全順列

先ほどの、任意のカードをシャッフルして、順番と一致しないということを言いかえると、{1, 2, 3, ... , n}の順列とそれがシャッフルしてできた順列({a1, a2, a3, .. , an}と表記する)を照らしあわせると、それぞれの位置において同じ要素が現れない、という風に説明できる。これを完全順列と言うらしい。

さて、もしこのゲームにおいて外れる確率を計算したいとするならば、完全順列の総数を、順列の総数で割ればいいということになる。そこで、本書で紹介されているベルヌーイの方法を利用することにする。

包除原理を使う

包除原理とは、例えばAとBという集合があるとし、nをそこに属する要素を求める関数であると定義した場合、n(A \cup B)に属する要素を求めるにはどうすればいいか、ということである。

もちろん、AとBが独立している場合(つまり、要素の重複が存在しない場合)、n(A) + n(B)とすることで計算ができる。とはいえ、あらかじめ、AとBが独立しているかどうかがわからない場合、n(A) + n(B) - n(A \cap B)とする。理由は、Aを数え、かつBを数えた場合、AとBに属している数は2度数えられているという計算になるからだ。

さて、集合が2つの場合はわかった。今度は3つの集合であるA, B, Cの場合を考えてみよう。最初同様に、n(A) + n(B) + n(C)を計算する。当然ながら、n(A \cap B)n(A \cap C)n(B \cap C)の場合は前出同様、2重に数えられているわけだから、これを消す。

しかし、ちょっと考えてみよう。n(A \cap B \cap C)は、この段階でどれだけ含まれているか。まず、n(A) + n(B) + n(C)の段階で3回数えられている。そのあとn(A \cap B)n(A \cap C)n(B \cap C)で3回除去されているので、実質計算されていないことになる。これではまずいので、n(A \cap B \cap C)を足しあわせることにする。

ここで、ある法則性が理解できる。先ほどの集合の名前A, B, CをA1, A2, A3と表現した場合、まず最初にそれぞれの総数をとりあえず求め、そのあとに、2組の重複、つまりは偶数組は引き算をおこない、そして、3組の重複 、つまりは奇数組は足すとよい。これは集合が4つある場合もそうであるので、もし手元に手軽なノートがあるならば、各自で確認して欲しい。

完全順序と包除原理

さて、そこで完全順序の求めかたを考えてみよう。そこで、わかりやすいように、順列が{1, 2, 3}の場合を考えてみよう。

まず最初にこの順列をシャッフルして取りうる全ての数を計算する。そのリストを上げると下のようになる。

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}

この程度なら個数は数えあげられるのだけれど、今はロジックを確認するためのものだから勘弁して欲しい。

まずそれぞれの順列に対して{a1, a2, a3}という名前を付ける。まず最初のケースとして{a1 = 1}, {a2 = 2}, {a3 = 3} という場合を取りあげる(今後、このように完全順序にならないものを「固定した」と表現する)。このとき、元の順列と、上記の事例は完全順序ではないので排除される。

{2, 3, 1}
{3, 1, 2}

実際、ここで既に要素は出ているのだが、あくまで包除原理にもとづいて計算を進める。先に言うと、奇数回で消さなければならない要素は{1, 2, 3}である。そこで、偶数回である今回は、{a1 = 1, a2 = 2}, {a2 = 2, a3 = 3} といった配列を足すことにする。とはいえ、これに当てはまるのは {1, 2, 3}だけなので、{1, 2, 3}を足すことになる。

{1, 2, 3}
{2, 3, 1}
{3, 1, 2}

で、これを改めて消すと、元の組みあわせが出てくる。

この説明を元に公式を作ると、次のようになる。まずa_nはn個が固定された(つまり、完全順序数とならない)組みあわせ数だと考えて欲しい。

 n! - a_1(n - 1)! + a_2(n - 2)! - a_3(n - 3)! + ... 1

そこで、{a1}や{a1, a2}の組み合わせの総数が必要となる。これは箱の中にボールが入っていて、そこから取りだすときの組みあわせと考えるとわかりやすい。

先の例であるならば、固定された要素数は1個である。その1個をボールから取り出す可能性は3つある。なので、3になり、そして残りの順序を計算する。これは_nC_r = \frac{n!}{r!(n - r)!}という公式があるので、これを利用し、変形すると、次のようになる。

 n! - \frac{n!}{1!(n - 1)!}(n! - 1)! + \frac{n!}{2!(n - 2)!}(n - 2)! - \frac{n!}{3!(n - 3)(n - 3)!} + ... 1

ということになる。良く見れば、分母は削ることができる。なので、さらに簡略化して

 n! - \frac{n!}{1!} + \frac{n!}{2!} - \frac{n!}{3!} + ... 1

とでき、さらに共通のn!をまとめれば、次の公式が出てくる。

 n!(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} ... + (-1)^{n}\frac{1}{n!}

実際にこれを利用して3を計算すると、次のようになる。

 6(\frac{2}{6})

また、5を計算すると、44となり、本書と一致する。そして、確率を計算する場合、完全順序の総数を順序の総数で割れば良い。なので、実質:

 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} ... + (-1)^{n}\frac{1}{n!}

ということになる。そして、この式からわかるように影響する分子はどんどん大きくなっていくため、枚数をいくら増やしても、その確率にほぼ影響は無い(興味がある人は実際にコードを書いて検証してみるといいかもしれない)。

まとめ

だいたい、エントリを書く前にノートに草稿を書くという律儀なことをしているのだけれど、このエントリを書くためにノートを4ページくらい使った。とはいえ、それを使うだけの納得感は味わえたので、非常によかった。数学の良さがわかるように、一歩くらいは前進したのかもしれない。

反直観の数学パズル―あなたの数学的思考力を試す14の難問

反直観の数学パズル―あなたの数学的思考力を試す14の難問