無限の猿定理

無限の猿定理 (Infinite monkey theorem) とは、ランダムな文字列入力を続ければどのような有限の文字列でも生成可能であるという定理である。これは「殆ど確実」という確率論の用語を端的に説明する例えとしてしばしば使用される。確率的にゼロではない事象は、十分に長い試行を重ねれば「殆ど確実」にいつか発生するが、文章が長くなればその試行回数は非常に膨大となる。

概要

この定理が猿に例えられるのは、猿があくまで文字入力が任意の介在する存在ではない事を示すメタファーである為である。猿をメタファーとした恐らく最初の例は1913年のÉmile Borelである。。出力される文章として言及される対象も様々であるが、最も多いのは、文字数の内訳が明らかで十分に長いテキストであるウィリアム・シェイクスピアの『ハムレット』である。

文字入力は各々が独立した事象である為、任意の有限の長さを持つ文字列を出力する確率は、入力文字数の逆数を出力文字数で乗じた数である。例えば50文字分のキーから6文字の文字列を出力する確率は\(\left(\cfrac{1}{50}\right)^{6}=\cfrac{1}{15625000000}=6.4\times10^{-11}\)である。出力する文字列が長くなればなるほどその値はゼロに近づくが、ゼロに等しくはならない為、十分に長い試行を重ねればいつかは生じる事になる。

より厳密には無限回の試行の列を標本とする空間に適切な確率概念を導入することで定式化することが出来る。キーの総数を\(N > 0\)と置く。このキーを無限回押すとし、正整数\(n\)に対し\(n\)回目に押されるキーを\(i_n\)と置く。入力したい文字列の長さを\(L > 0\)とし、その文字列を\(s_1 \cdots s_L\)と置く。「この試行の中で\(s_1 \cdots s_L\)という文字列が入力されるか否か」を直接考えるには無限回の試行（無限直積）に対し確率（測度空間）を考える必要があり理論上の複雑さがあるが、その近似的な問いである「この試行の中で\(n\)回目までに\(s_1 \cdots s_L\)という文字列が入力されるか否か」という正整数\(n\)に関する事象については古典的な確率の問題として捉えることが出来る。

ここで、正整数\(n\)に関する事象「\(i_{L(n-1)+1} \cdots i_{Ln} = s_1 \cdots s_L\)」を\(E_n\)と置くと、\(E_n\)が成り立つ確率は\(\frac{1}{N^L}\)である。\(E_1,E_2,\ldots\)は互いに独立であることから、正整数\(n\)に関する事象「\(E_1\)でなくかつ…かつ\(E_n\)でない」が成り立つ確率は\((1-\frac{1}{N^L})^n\)となる。\(1-\frac{1}{N^L}\)が\(1\)未満の正実数であることからこの\(n \to \infty\)による極限は\(0\)に収束する。それはすなわち、任意の\(p \in [0,1)\)に対しても、十分大きな正整数\(n\)を取れば、\(E_1,\ldots,E_n\)のいずれかが成り立つ確率は\(p\)より大きいということである。\(E_1,\ldots,E_n\)のいずれかが成り立つという事象は「この試行の中で\(Ln\)回目までに\(s_1 \cdots s_L\)という文字列が入力される」といういう事象を含意しているので、以上より任意の\(p \in [0,1)\)に対しても、十分大きな正整数\(n\)を取れば、この試行の中で\(n\)回目までに\(s_1 \cdots s_L\)という文字列が入力される確率は\(p\)より大きいということが分かる。大雑把に言えば、これは「試行回数を大きくしていけば、入力したい文字列がその試行回数内に入力される確率は、いくらでも\(1\)に近づく」ということを表す。

確率

文字列が長くなれば、任意の文字列が出力される確率は指数関数的に減少する為、試行回数は非常に膨大となる。『ハムレット』のような非常に長い文字列の場合、ゼロではないとは言えその試行は現実的な量では無くなる。『ハムレット』は13万2680文字のアルファベットで書かれており、句読点やスペースを含めれば19万9749文字となる。後者の場合、アルファベットは大文字小文字を区別し、その他の文字は12文字ある為、全部で64種類の文字のランダム入力から『ハムレット』を出力する必要がある。従って、その為の平均入力文字数の近似値は\(64^{199749} \approx 4.4 \times 10^{360783}\)となる。

非常に粗い例えとして、1秒間に\(10^{100}\)回ランダムキータップを行う猿が\(10^{100}\)匹存在し、\(10^{100}\)秒間入力したとしても、高々\(10^{300}\)オーダーである為、『ハムレット』が出力される可能性は非常に低い。なお、ここでの猿の数は観測可能な宇宙に存在する素粒子の総数と同程度、試行時間は宇宙全てのブラックホールが蒸発する時間と同程度である。

現実の猿

検討するまでもなく、ランダムキータップに現実の猿を起用する事は明らかに適していない。2003年にイギリスのペイントン動物園で6匹のクロザルに1ヶ月間キーボードとディスプレイを与える試験が行われたが、出力された文字は殆どがsからなる5ページの "文章" である。また、キーボードは石で叩かれたり糞尿がされるなど酷い状態となった。