randomthoughts.hatenablog.com
randomthoughts.hatenablog.com
randomthoughts.hatenablog.com
グリコの洞窟をいったん離れ、三項係数の林を探検した俺は、三項係数という強力な武器を手にすることができた。完全に三項係数を理解することはできなかったものの、単純化したグリコ問題に解をもたらすことができた。
ここで再びグリコの洞窟に戻り、もともとの問題に挑戦してみる。
5人でゲームをする。5人の持ち点は最初0点で、毎ターンに1/2の確率で0点、1/6の確率で1点、1/3の確率で2点を追加する。しかし、1人が10点に達してゲームが終了したとき、全員の得点が7点以上である確率を求めよ。
まず、mターン後に得点がn点である確率\(p(m,n)\)を求める。
三項係数を\((x^2+x+1)^n\)の展開式の\(x^r\)の係数として表したように、\(p(m,n)\)を何かの多項式の展開式の係数として表したい。\((\frac{1}{3}x^2 + \frac{1}{6} x + \frac{1}{2})^m\)なんてのはどうだろう？xの指数を得点とみると、2点の時1/3、1点の時1/6、0点の時1/2というように、見ることができる。しかも、確率の和は1だから、展開式の係数の和も1になるはずだが、これは展開前の多項式の係数の和が1だから成り立つはずである。うまく行きそうだ。
この式を手計算で展開するのは大変だから、数学ソフトMathematicaを使って展開すると、このようになる。
なんと、展開式の係数が、第1話で示した確率の表の値と、見事に一致する！
よって、\(p(m,n)\)は\((\frac{1}{3}x^2 + \frac{1}{6} x + \frac{1}{2})^m\)の展開式の\(x^n\)の係数として表すことができる。
これを数式であらわしてみよう。二項式の場合は、展開式の係数を二項係数を含む式で表すことができるが、三項式の場合は、試してみればわかるが、三項係数を含む式で表すことはできそうにない。しかしそれでも、三項係数の式を求めるプロセス、考え方は、そのまま応用できる。
多項定理より、
\[
\begin{align}
(\frac{1}{3}x^2 + \frac{1}{6} x + \frac{1}{2})^m &= \sum_{\substack{a+b+c=m \\ a,b,c \ge 0}} \frac{m!}{a!b!c!} \left( \frac{1}{3}x^2 \right)^a \left( \frac{1}{6}x \right)^b \left( \frac{1}{2} \right)^c \\
&= \sum_{\substack{a+b+c=m \\ a,b,c \ge 0}} \frac{m!}{a!b!c!} \frac{2^a 3^c}{6^m} x^{2a+b}
\end{align}
\]
よって、
\[
p(m,n) = \sum_{\substack{a+b+c=m \\ 2a+b=n \\ a,b,c \ge 0}} \frac{m!}{a!b!c!} \frac{2^a 3^c}{6^m}
\]
aは0から\(\lfloor \frac{n}{2} \rfloor \)までの値を取り、\(a=k\)のとき\(b=n-2k, \quad c=m-n+k\)となるから、
\[
\begin{align}
p(m,n) &= \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \frac{m!}{k!(n-2k)!(m-n+k)!} \frac{2^k 3^{m-n+k}}{6^m} \\
&= \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} {}_mC_{n-k} \cdot {}_{n-k}C_{k} \frac{2^k 3^{m-n+k}}{6^m}
\end{align}
\]
これもゲーゲンバウアー多項式か何かを使えば閉じた式で表せるのかもしれないが、そもそもそれがどういう仕組みか理解していないので、ここではこれ以上の変形はしないことにする。上の式は、コンピュータで容易に実装できる関数なので、これもMathematicaで定義し、使うことにする。
上の式を用いて\(p(m,n)\)を定義し、試しにm=4についてその値を計算してみると、
となり、確かに上の式が正しいことがわかる。これで、あらゆるm、nの値に対して、確率を求めることができるようになった。
道具はそろった。それでは洞窟の奥へと進もう。
求める確率は、1人が10点に到達したとき、全員が7点以上の確率である。ここで、mターン目にゲームが終わるとしよう。そうすると、求める確率は、mターン目に1人が10点に到達したとき、全員が7点以上の確率を求めて、それをすべてのmに対して足し合わせればよい。グリコのゲームでは、有限のターン数で絶対にゲームは終わる。なぜなら、各ターンで誰かは勝ち、階段を上るからである。しかし、この（言い換えられた）グリコ問題では、mは無限大になりうる。全員が0点というのが永遠に続くことができるからだ。この違いの原因は、得点する確率が全員独立であると仮定したことにある。つまり、隣の人がじゃんけんに勝とうが負けようが、自分の勝敗には関係ないということである。そんなことは本来のじゃんけんではありえないことなのだが、全員独立としないとどう計算したらいいのかわからないので、他の人に関係なく1/2で0点、1/6で1点、1/3で2点とした。これでは正しい結果は得られないが、少なくとも近い値は出ると思う。計算にはコンピュータを使うが、無限に足し合わせるわけにはいかないので、十分大きいmの値で切り上げる。まあ、mが十分大きければ確率は無視できるほど小さくなるので、大勢に影響はない。
ここで注意しなければならないことは、1人が10点に到達するというのは少なくとも1人が10点に到達するということである。2人が同時に10点に到達してゲームが終わるというのは、実際のグリコのゲームでもありうる。
mターン目に1人だけが10点に到達するとき、その1人の選び方は\(_5C_1=5\)通りある。その人がm-1ターン目に8点で、mターン目で2点獲得して10点に到達する確率は、\(\frac{1}{3}p(m-1,8)\)。m-1ターン目に9点で、mターン目で1点か2点獲得して10点以上に到達する確率は、\(\frac{1}{2}p(m-1,9)\)。そしてほかの4人が7点以上9点以下である確率は、\(\left( p(m,7) + p(m,8) + p(m,9) \right)^4\)である。よって、mターン目に1人だけが10点に到達する確率は、
\[
5 \left( \frac{1}{3}p(m-1,8) + \frac{1}{2}p(m-1,9) \right) \left( p(m,7) + p(m,8) + p(m,9) \right)^4
\]
同様に考えて、mターン目に2人、3人、4人、5人が10点以上に到達する確率は、それぞれ、
\[
10 \left( \frac{1}{3}p(m-1,8) + \frac{1}{2}p(m-1,9) \right)^2 \left( p(m,7) + p(m,8) + p(m,9) \right)^3
\]
\[
10 \left( \frac{1}{3}p(m-1,8) + \frac{1}{2}p(m-1,9) \right)^3 \left( p(m,7) + p(m,8) + p(m,9) \right)^2
\]
\[
5 \left( \frac{1}{3}p(m-1,8) + \frac{1}{2}p(m-1,9) \right)^4 \left( p(m,7) + p(m,8) + p(m,9) \right)
\]
\[
\left( \frac{1}{3}p(m-1,8) + \frac{1}{2}p(m-1,9) \right)^5
\]
と求まる。ここで、5人同時にゴールするというのは実際のグリコのゲームではありえないことだが、言い換えられた問題では可能になってしまう。ここまでいろいろと元の問題と違うところがあると、本当に正しい方向に進んでいるのか不安になるのだが、このまま続けてみる。
これらの確率を足し合わせると、
\[
\left( \frac{1}{3}p(m-1,8) + \frac{1}{2}p(m-1,9) + p(m,7) + p(m,8) + p(m,9) \right)^5 - \left( p(m,7) + p(m,8) + p(m,9) \right)^5
\]
となる。これがmターン目にゲームが終了する確率である。
ゲームは最短で5ターンで終わる（誰かが5回連続で2点を獲得したとき）。だから、求める確率は、mを5から無限大まで足し合わせることで得られる。無限大までは計算できないから、m=100で切り上げるとする。Mathematicaに上で求めた式を入力し、5から100まで足し合わせると、
0.0897131、約9パーセントと求まる。
mの上限を色々変えて計算してみると、m=20からm=10000までは0.0897131のまま変化しないことが分かった。mをもっと増やせば変わるかもしれないが、変わったとしてもせいぜい最後の桁が1から2に代わる程度だと思うから、これを最終的な答えとしてよいだろう。
さてこれは正しい答えなのか？この問題は今まで見たことがないもので、解に至った過程も今まで経験したことのないようなものだった。問題も言い換えることによってゲームの性質がところどころ変わってしまった。もしかしたら今までやったことは全部無駄で、全然違う答えが得られたのかもしれない。
得られた約9パーセントという値が正しいかどうかを判断するのは難しい。直感的にはもうちょっと高くてもいいんじゃないかと思うが、90パーセントとか、0.00005パーセントとかという絶対ありえないような値ではないから、あっているような気もする。というかあっていてほしいと願う。
実際にグリコをやって本当に確率が9パーセントになるのか試してもいいが（1000回くらいやればある程度信頼できる値が得られるかな）、俺の残り限られた青春をグリコに費やすのは御免だ。だから、コンピューターでシミュレーションしてみる。コンピューターがグリコをしている間に、俺は受験生生活を楽しむことができるというわけだ。
Pythonで簡単なプログラムを書く。まず、じゃんけんをして、勝敗に応じて得点が入るようにする関数を定義する。ここでは、言い換えられたグリコ問題のように、じゃんけんで勝つ確率が独立であるとせずに、実際のじゃんけんと同じように働くようにしてある。
import random def play(points): # points players can get by winning rock-paper-scissors point = random.random() if (point < 1/3): # rock point = 1 else: # paper or scissors point = 2 # number of players to win rock-paper-scissors num_win = random.randint(1,4) # randomly shuffle the player numbers players_win = list(range(5)) random.shuffle(players_win) # take the first (num_win) players and add points to them for i in range(num_win): points[players_win[i]] += point return points
この関数を1回呼ぶごとに、グリコのゲームが1ターン進む。
コンピューターにグリコを10万回させる。
count = 0 total = 100000 for i in range(total): # points of each player points = [0] * 5 while (all(points[i] < 10 for i in range(5))): points = play(points) if all(points[i] >= 7 for i in range(5)): count += 1 print(count / total)
このプログラムを実行したとき、俺の今までの努力が報われるかどうかが決まる。もしこれで30パーセントとか出たら、俺の今までの数学の森での冒険はすべて無駄となる。頼む、9パーセントに近い値が出てくれ！
0.10526
10.5パーセントッっっっっっ！！！！！！！！
何回かプログラムを走らせても毎回10パーセントちょっとの値が得られるので、これが真の値だと思われる。
俺が求めた9パーセントに近い値が得られた！
しかし1パーセントの差があるのが気に入らない。やはりこの差は、問題文を言い換えたことによるゲームの性質の変化に起因するものなのだろうか？言い換えられたグリコ問題の確率を計算するプログラムも試しに書いてみた。play関数の実装を少し変えるだけだ。
def play(points): for i in range(5): point = random.random() if (point < 1/2): # lose point = 0 elif (point < 1/2 + 1/6): # rock point = 1 else: # papers or scissors point = 2 points[i] += point return points
さて、これも10万回プレイさせて、確率を求めてみる。
0.08904
なんと、8.9パーセント！！！！！！！！
素晴らしい、感動だ。俺が三項定数の研究から得られた洞察を駆使して求めた理論値が、10万回のシミュレーションによって得られた実験値と非常に近い値になった！
********************************************************************************
ついに、一回は断念したグリコの洞窟の奥にたどり着くことができた俺は、言葉では言い表せないほどの高揚感と達成感、そして数学への敬意を感じていた。突然迷い込んだ数学の森で、躓きながらも長い間歩いてきたが、ついに、一つの冒険が終わりを迎えたようだ。洞窟の奥にあったのは、「数の宇宙」だった。
「宇宙は数学という言語で書かれている」とガリレオは言った。世界は物理法則によって支配されており、物理法則は数学で記述されている。グリコだってそうだ。俺がこの冒険で見つけ出したように、グリコの根底には、数学がある。私たちは、身の回りの事象を司る数に目を向けることで、世界をよりよく知り、よりよく生きることができるのだ。そして数学は、絶対に嘘をつかない。これが、数学の森での旅を終えた俺が一番深く実感したことだ。
古代ギリシャの哲学者ピタゴラスは、万物は数であると考えた。世界は、数が織りなすハーモニーなのだ。もしかすると、俺が迷い込んだ数学の森こそが、現実世界なのかもしれない。宇宙のすべては、数学でできているから。
********************************************************************************
世界最大の都市、東京。ここでは、1千万を超える人たちが忙しい日々を送っている。この中には数学を駆使して社会に貢献している人や、数学の美しさに取りつかれ、数学者として生きている人もいるだろう。しかし、そのうちのいったい何人が、三項係数の存在を知っているだろうか？5人で30段の階段でグリコをして、ゲームが終了したとき、全員が21段目以上に到達している確率が約10パーセントであることを知っている人はいるのだろうか？そして、新宿の地下通路に、数学の森への入り口があることを、誰が知っているのだろうか？
俺は階段を上るたびに、数学の森での冒険を思い出す。鬱蒼とした三項係数の林、人々を寄せ付けないゲーゲンバウアーの崖、そして謎に包まれたグリコの洞窟の奥で見つけた、数の宇宙。驚きと感動に満ちたこの数学の森で、方程式たちと触れ合った日々を、俺は絶対に忘れない。
数学の森に行くには、特定の時間に、特定の場所にいる必要はない。あなたが望めば、入り口はいつでも、どこにでも現れる。好奇心と虚数単位（\(i\)、アイ、愛）さえあれば、向こうからあなたを迎えに来る。
さあ、無限の数学の森へ、一緒に行こう。
深淵なる数学の森の冒険 完
