■

A paradoxical property of the monkey book
Sebastian Bernhardsson, Seung Ki Baek and Petter Minnhagen
J. Stat. Mech. (2011) P07013

ECCSで，韓国人の研究者から紹介してもらった論文．
Monkey bookというのは，猿にタイプライターを打たせて，アルファベット＋スペースでランダムにタイプさせて，スペースに区切られた続きアルファベットを「単語」と見なすと文章ができて，さらには本ができるだろう，という思考実験に似たもの．無限時間やらせると，いつかはすごーーーーく低い確率でも，シェイクスピアの本だって再現できるだろう，という話である．

Monkey bookで，すべてのタイピングは独立に起きると考えると，解析解も簡単に出せる．
このとき連続近似で，word-frequency distributionはベキ分布=Zipf則になる．
あとは実際にアルファベットが4つの場合でコンピュータシミュレーションの場合と比較すると，解析解は連続に対して，どうしてもシミュレーションは離散になりスパイク上に分布が散らばる分布になる．
解析解の場合のHeaps則，平均な異なり単語数単純に計算できて，pdfの時のZipfのベキ指数がγとすると，Heapsの指数はγ-1になる．(Eq.(5))

で，どこがParadoxicalなのかというと，Monkey bookのシミュレーションの場合のHeaps則のカーブはこのEq.(5)で再現できるのに，連続の場合に正直にサンプルした場合(sampled book)の場合にはHeaps則のカーブがEq.(5)の解析解からずれる，という矛盾である．
この理由は，Heaps則は，word-frequency distributionのサイズから独立（本全体のサイズによらない定常性）であることを仮定しているのに，実際にはシミュレーションではそうならないから，らしい．

最後に，実データとランダムシャッフルしたデータでもHeaps則のカーブはほぼ似たものが得られるが，やはりEq.(5)の解析解とはずれている．結局，解析解と一致するのはスパイク上にword-frequency distributionが散らばるMonkey bookだけ，という結論．
Monkey bookがHeaps' lawの解析解と一致するのは，word-frequency distributionがスムーズではないからだ，という結論．

この論文の解析解の出し方は，シンプルだけど，自分たちがこれまでやってきたのと一致．
しかし，解析解はMonkey bookでないと適用できない，というのではuselessだなあ．