無限の猿定理

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

概要

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

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

より厳密には、無限の猿定理が成り立つのは、ボレル・カンテリの第二補題の特別な場合である為である。\(k\)番目の文字列が与えられたテキストから始まるイベントを\(E_{k}\)とすると、ある一定の非ゼロの確率\(p\)で始まり、\(E_{k}\)は独立した確率空間の事象である為、総和は発散し、\(E_{k}\)が無限に生じる確率は1となる。

\(\displaystyle \sum_{k=1}^{\infty}P(E_{k})=\sum_{k=1}^{\infty}p=\infty\)

確率

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

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

現実の猿

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