2025-11-18T09:52:13.048748

Simulating Keystroke and Computing the Theoretical Probability of Infinite Monkey Theorem with Markov Process

Yi, Zhou, Jiang
The Infinite Monkey Theorem states that if one monkey randomly hits the keys in front of a typewriter keyboard during an infinite amount of time, any works written by William Shakespeare will almost surely be typed out at the end of the total text. Due to the seemingly low chance of typing the exact literature works, our group are motivated to find out the expected time the Hamlet, our target text, being typed out by simulated random typing on a standard keyboard. For finding the answer, 30 users randomly typed characters into a file. Then, the frequency of each characters occurred following the previous character is calculated. This conditional probability is used to build the Markov matrix by considering all 128 times 128 cases. Finally, the expected time we estimated is about 10 to the power of 34 (min), which is surprisingly lower than the theoretical computation, and not achievable at all even in the cosmic time.
academic

キーストロークシミュレーションとマルコフ過程による無限猿定理の理論確率計算

基本情報

  • 論文ID: 2511.11760
  • タイトル: Simulating Keystroke and Computing the Theoretical Probability of Infinite Monkey Theorem with Markov Process
  • 著者: Juncheng Yi, Hongyi Jiang, Kaiwen Zhou（ワシントン大学）
  • 分類: physics.soc-ph, math.PR, stat.ME
  • 発表時期: 2022年（データ収集期間：2022年6月12日～26日）
  • 論文リンク: https://arxiv.org/abs/2511.11760

要約

無限猿定理は、猿が無限時間にわたってランダムにタイプライターのキーボードを叩けば、ほぼ確実にシェイクスピアのあらゆる作品を打ち出すことができると述べている。本研究では、実験的方法によりランダムタイピングで『ハムレット』を生成するのに必要な期待時間を推定した。研究者は30名のボランティアからランダムタイピングデータを収集し、文字間の条件付き確率を計算し、128×128のマルコフ行列を構築した。研究の結果、『ハムレット』の最初の78文字を正しく打ち出すまでの期待時間は約10^134分（宇宙年齢の約1.41533×10^117倍）であることが判明した。この結果は、理論的な独立性仮定に基づく計算結果よりもやや低いものの、依然として完全に実現不可能である。

研究背景と動機

1. 研究課題

本研究は、無限猿定理における具体的な問題を定量化することを目的としている：ランダムタイピングでシェイクスピアの『ハムレット』全文を生成する確率と期待時間はいくらか？

2. 問題の重要性

  • 理論的価値：無限猿定理は確率論における古典的な思考実験であるが、実際の人間のタイピング行動に基づく実証的推定が不足している
  • 教育的意義：極めて小さい確率事象と数学的確率の実際の意味を理解するのに役立つ
  • 方法論的革新：文字列生成確率計算へのマルコフ連鎖の適用可能性を探索する

3. 既存方法の限界

  • 独立等確率仮定：従来の方法は各文字が独立で等確率で出現すると仮定しており、これは実際のタイピング行動と一致しない
  • 実証データの欠如：2002年のプリマス大学の実際の猿実験では、実際の状況は理論よりもはるかに複雑であることが示された（猿は大量の「S」を打ち出し、キーボードを破損した）
  • 文字間依存性の無視：既存のシミュレーション方法は、キーボードレイアウトとタイピング習慣による文字間の依存関係を十分に考慮していない

4. 研究動機

研究者はグラフ尤度法（graph likelihood approach）に着想を得て、キーボード上の文字には空間的依存性が存在すると考えた。つまり、ある文字を打った後、その隣接文字を打つ可能性がより高いということである。したがって、マルコフ連鎖モデルを使用してランダムタイピングプロセスをより現実的にシミュレートすることを提案した。

中核的貢献

  1. 実際のタイピングデータに基づくマルコフ遷移行列の構築：30名のボランティアからランダムタイピングサンプル（約10万文字）を収集し、文字間の条件付き遷移確率を計算し、128×128のマルコフ行列を確立した
  2. 有理数ストレージスキームの提案：Pythonの浮動小数点精度の制限（約10^-16）に対処するため、分子と分母を分離して保存する有理数方法を採用し、10^-134レベルの極小確率を計算できるようにした
  3. キーボードタイピング頻度の地理的可視化の実装：ArcGISとGeoPandasを使用してキーボードヒートマップを作成し、人間のランダムタイピングの空間分布パターンを直感的に表示した
  4. マルコフ連鎖収束性の理論的証明の提供：Bolzano-Weierstrass定理とBanach圧縮写像原理に基づき、マルコフ行列の収束性を証明した
  5. 定量的推定結果の提供：ランダムタイピングで『ハムレット』の最初の78文字を生成する確率が10^-134であることを計算し、対応する期待時間が10^134分であることを示した

方法の詳細説明

タスク定義

入力：標準タイプライターキーボード（LG Rog Strix Flare）上のランダムタイピング列
出力：シェイクスピアの『ハムレット』完全テキストを正しく打ち出す確率と期待時間
制約条件：

  • 標準化キーボード（機能キーを除去、文字キーを保持）を使用
  • 実際の人間のタイピング行動データに基づく
  • 文字間のマルコフ依存関係を考慮

モデルアーキテクチャ

1. データ収集プロセス

標準化キーボード定義：

  • 簡略版：26個の小文字のみ（ASCII 97-122）
  • 現実版：すべての一般的な文字キー（ASCII 32-126と改行文字10）
  • ARMOURY CRATEソフトウェアを使用して機能キーの機能を除去

実験プロトコル（各参加者ごと）：

  1. アイマスクで視線を遮蔽
  2. 各タイピングセッションは150秒間継続（予想1200～1500文字を生成）
  3. 各参加者が4回のタイピングタスクを完了（簡略版2回、現実版2回）
  4. 合計30×4=120個のサブサンプルを収集

頻度計算方法：

  • 通常の文字：出現回数を直接累計
  • Caps Lock：連続した大文字小文字パターンを検出して推定（例：「小-大-大」または「大-小-小」列）
  • Shiftキー：隣接文字の大文字小文字変化を検出し、左右Shiftキーの長さ比（5.01:6.17）に基づいて頻度を配分

2. マルコフ行列の構築

遷移確率の定義： Pu,v=P(現在の文字が u ∣ 前の文字が v)P_{u,v} = P(\text{現在の文字が}\ u\ |\ \text{前の文字が}\ v)

ここで u,v∈[0,127]u, v \in [0, 127] はASCIIコード値である。

行列構造：

  • 簡略版：26×26行列（小文字のみ）
  • 現実版：96×96行列（ASCII 32-126と改行文字）

正規化条件： ∑u=0127Pu,v=1,∀v\sum_{u=0}^{127} P_{u,v} = 1, \quad \forall v

各行は、前の文字が与えられたときのすべての可能な後続文字の確率分布を表す。

3. 累積分布関数（CDF）行列

加重ランダムウォークを実装するため、遷移確率行列をCDF行列に変換する：

Si,v=∑u=0iPu,vS_{i,v} = \sum_{u=0}^{i} P_{u,v}

ここで S127,v=1S_{127,v} = 1（CDF特性を満たす）。

整数化処理： CDF行列に 101810^{18} を乗じて整数行列 S~\tilde{S} に変換し、後続の計算を容易にする： S~i,v=Si,v×1018\tilde{S}_{i,v} = S_{i,v} \times 10^{18}

4. 文字生成アルゴリズム

初期文字：26個の小文字から均一にランダムに選択（確率1/26）

後続文字生成（疑似コード）：

前の文字 v（ASCIIコード値）が与えられた場合：
1. 遷移行列の第 v 行を特定
2. Python randint() を使用してランダム整数 k ∈ [1, 10^18] を生成
3. S[m,v] ≥ k/10^18 となる最小の列インデックス m を見つける
4. ASCIIコード値が m である文字を返す

5. 列の確率計算

目標テキスト列 c1c2...cnc_1c_2...c_n（例：『ハムレット』）に対して：

P(列)=P(c1)×∏i=2nP(ci∣ci−1)P(\text{列}) = P(c_1) \times \prod_{i=2}^{n} P(c_i|c_{i-1})

ここで：

  • P(c1)=1/26P(c_1) = 1/26（初期文字は均一分布）
  • P(ci∣ci−1)P(c_i|c_{i-1}) はマルコフ行列から取得

有理数実装： 各確率は(分子、分母)ペアとして保存され、浮動小数点精度の損失を回避する：

class Rational:
    def __init__(self, numerator, denominator):
        self.num = numerator
        self.den = denominator
    
    def multiply(self, other):
        return Rational(self.num * other.num, 
                       self.den * other.den)

技術的革新点

1. マルコフ依存性のモデリング

従来の方法との違い：従来の独立等確率仮定では、『ハムレット』の短い列の確率は： P独立=(195)nP_{\text{独立}} = \left(\frac{1}{95}\right)^n

本方法は文字間の依存性を考慮する： Pマルコフ=126×∏i=2nP(ci∣ci−1)P_{\text{マルコフ}} = \frac{1}{26} \times \prod_{i=2}^{n} P(c_i|c_{i-1})

妥当性：キーボードの空間レイアウトにより隣接キーがより連続して押される可能性が高く、人間の無意識的なタイピング行動と一致する

2. スパース行列処理戦略

問題：10万文字のサンプルでは、すべての128²=16,384種類の文字遷移をカバーできない
解決策：

  • モデルの限界を認め、最初のゼロ確率遷移までのみ計算
  • ブートストラップ方法を使用しない（存在しないエッジを導入して元のデータを歪める可能性を回避）
  • 結果を「最初の78文字」の確率として明確に表示

3. 数値精度の保証

課題：5文字の短い単語の確率は既に10^-7に達し、10文字を超えるとPythonの浮動小数点精度を超える
革新：全プロセスで有理数演算を使用し、正確な計算能力を維持

4. 収束性の理論的保証

固有値分解に基づくマルコフ行列の収束性の証明：

  • マルコフ行列は必ず固有値λ₁=1を持つ
  • 他の固有値は|λᵢ|<1を満たす
  • Gram-Schmidt直交化とCauchy-Schwarz不等式を通じて圧縮写像特性を証明

実験設定

データセット

サンプル規模：

  • 参加者：30名のボランティア（25名が中国語を母語とする）
  • 総サンプル：120個のサブサンプル（各参加者4個）
  • 総文字数：約100,000文字
  • 平均タイピング速度：760文字/分

データバージョン：

  1. 簡略版：26文字サンプル（60ファイル）
  2. 現実版：全文字サンプル（60ファイル）

目標テキスト：

  • 出典：GitHubの『ハムレット』版（hamlet.txt）
  • 文字数：完全テキスト（実際には第78文字までのみ計算）

評価指標

  1. 列生成確率：P(目標列)P(\text{目標列})
  2. 期待生成時間：E[τ]=1/P×(文字数/760)E[\tau] = 1/P \times (\text{文字数}/760) 分
  3. キーボードヒートマップ：各キーの相対頻度の空間分布
  4. マルコフ行列のスパース度：ゼロ要素の比率

比較方法

論文は厳密な方法比較実験を実施していないが、文献レビューで以下の比較基準に言及している：

  1. 独立等確率モデル：各文字が独立で等確率（1/95）であると仮定
  2. 進化アルゴリズム：「遺伝」を通じて文字頻度分布を最適化
  3. グラフ確率法：問題をグラフ頂点生成確率に再構成

実装の詳細

プログラミング環境：

  • 言語：Python
  • 主要ライブラリ：NumPy（行列演算）、GeoPandas（地理的可視化）、Fractions（有理数）

可視化ツール：

  • ArcGIS/ArcMap：キーボード形状ファイル（.shp）の作成
  • GeoPandas：頻度データと地理的形状の統合

マルコフ行列計算：

# 疑似コード例
for each sample file:
    for i in range(1, len(text)):
        prev_char = text[i-1]
        curr_char = text[i]
        transition_count[prev_char][curr_char] += 1
    
# 確率に正規化
for v in all_chars:
    total = sum(transition_count[v])
    for u in all_chars:
        P[u][v] = transition_count[v][u] / total

実験結果

主要な結果

1. 列生成確率

最初の78文字の確率（有理数形式）：

  • 分子：1241桁の数字
  • 分母：1375桁の数字
  • 簡略推定：P≈10−134P \approx 10^{-134}

完全な確率表現（部分表示）：

分子 = 399770177810507862706549314796261397652584412911038561649332165981925926705239960397734...
分母 = 748723275279540762914329174346517245028241767538803575420430089763950062541466819509857...

2. 期待生成時間

E[τ]=110−134×78760 分=10134×0.1026 分E[\tau] = \frac{1}{10^{-134}} \times \frac{78}{760} \text{ 分} = 10^{134} \times 0.1026 \text{ 分}

宇宙スケールでの比較： E[τ]≈1.41533×10117×宇宙年齢E[\tau] \approx 1.41533 \times 10^{117} \times \text{宇宙年齢}

（宇宙年齢は約138億年≈7.26×10^15分）

3. ゼロ確率遷移の出現位置

『ハムレット』列の確率を計算する際：

  • 第79文字でゼロ確率遷移が初めて出現
  • 具体的な遷移：'P' → 'e'（データセットで観測されていない遷移）
  • その後のすべての確率がゼロになる

可視化結果

1. 人間のランダムタイピングパターン

発見：

  • スペースキー：頻度が最も高い（他のキーを大きく上回る）
  • 分布形状：2次元の準正規分布を呈する
  • ピーク領域：RキーとJキー付近（キーボード中央）に集中
  • 端のキー：頻度が著しく低い

2. 『ハムレット』の文字分布

比較による発見：

  • スペースキーは『ハムレット』でより高い頻度を示す（テキスト内の単語間にスペースが必要）
  • 文字分布はより英語の言語統計規則に従う
  • ランダムタイピングパターンとの間に顕著な差異がある

3. マルコフ行列の特性

スパース性：

  • 128×128行列に多くのゼロ要素
  • 10万文字のサンプルではすべての遷移をカバーできない
  • スパース性により長い列の確率が急速にゼロに低下

実験的発見

1. 方法論的発見

  • サンプル量の必要性：10万文字は16,384個のすべての遷移確率を埋めるには不十分
  • 初期文字仮定の影響：初期文字が均一分布（1/26）であることの最終確率への影響は限定的
  • 有理数方法の必要性：浮動小数点数は第10文字後に失効

2. 人間の行動パターン

  • キーボード中央への嗜好：ランダムタイピング時に中央のキー位置を叩く傾向
  • 空間依存性の存在は限定的：隣接キーの条件付き確率はやや高いが、効果は予想より小さい
  • 文化的背景の影響：30名中25名が中国語を母語とする参加者で、タイピング習慣に影響を与える可能性

3. 理論と実際

  • マルコフモデルの利点は限定的：依存性を考慮しているが、行列のスパース性のため、実際に計算可能な長さはむしろ制限される
  • 独立仮定がより実用的である可能性：長い列に対して、独立モデルは不正確だが少なくとも完全な推定を提供できる

関連研究

1. 無限猿定理の計算方法

独立等確率モデル（Stewart, 2009）：

  • 仮定：各文字は独立で、確率は均一（1/k、kは文字セットサイズ）
  • 利点：計算が簡単で、任意の長さの列を処理可能
  • 欠点：キーボードレイアウトとタイピング習慣を無視

進化アルゴリズム（Zito, 2016）：

  • 方法：「猿の個体群」をシミュレートし、優秀な個体の文字頻度を後代に遺伝
  • 利点：文字分布を自動的に最適化可能
  • 欠点：「適応度」関数の定義が必要で、計算が複雑

グラフ確率法（Banerji et al., 2014）：

  • 方法：問題をグラフ生成確率に再構成
  • 利点：理論的枠組みが優雅
  • 欠点：実際のタイピング行動との対応関係が不明確

2. 実証実験

プリマス大学実験（2002）：

  • 実際の猿を使用した実験
  • 結果：猿がキーボードを破損し、大量の「S」のみを生成
  • 示唆：実際の状況は理論よりもはるかに複雑

3. 本論文の位置付け

独立モデルとの比較：

  • 利点：実際のタイピング行動により適合
  • 欠点：サンプル需要が大きく、計算長が制限される

進化アルゴリズムとの比較：

  • 利点：実際のデータに基づき、適応度の人為的設計が不要
  • 欠点：自動的に最適化できない

グラフ法との比較：

  • 利点：文字遷移を直接モデル化し、物理的意味が明確
  • 欠点：理論的深さが不足

結論と考察

主要な結論

  1. 確率の極小性：ランダムタイピングで『ハムレット』の最初の78文字を生成する確率は約10^-134で、完全なテキストの確率はこれより遥かに小さい
  2. 時間の到達不可能性：期待時間は10^134分で、宇宙年齢の約10^117倍であり、完全に実現不可能
  3. マルコフモデルの限界：理論的にはより合理的だが、スパース行列の問題により実用性が制限される
  4. 人間のタイピングパターン：キーボード中央への嗜好を示すが、空間依存性は予想より強くない

限界

1. データレベル

  • サンプル量不足：10万文字ではすべての文字遷移をカバーできない
  • 参加者の偏り：83%の参加者が中国語を母語とする者で、文化的偏りの可能性
  • Shiftキー推定の不正確性：Shiftキーの使用パターンを正確に追跡できない

2. 方法レベル

  • スパース行列の問題：ゼロ確率遷移により計算が早期に終了
  • 初期文字仮定：均一分布仮定に実証的支持がない
  • ブートストラップ未使用：データの真実性を保証できるが、平滑化技術の適用を検討していない

3. 適用性の制限

  • 「人間のような」ランダムタイピングにのみ適用可能で、実際の猿には適用不可
  • 特定のキーボードレイアウト（LG Rog Strix Flare）に依存
  • タイピング速度の変化を考慮していない

今後の方向

  1. サンプル規模の拡大：百万レベルの文字サンプルを収集してより多くの遷移確率を埋める
  2. ブートストラップ方法の探索：データの真実性を保証しながら平滑化技術の適用を研究
  3. 高次マルコフ連鎖：前2～3文字の依存関係を考慮
  4. 文化間比較：異なる言語背景の参加者のタイピングパターンを比較
  5. 理論的改善：スパースマルコフ連鎖の確率推定理論を研究

深層的評価

利点

1. 方法の革新性

  • 実証データ駆動：実際の人間のタイピングデータを使用してマルコフモデルを構築した初の試み
  • 有理数スキーム：極小確率の数値計算問題を巧妙に解決
  • 可視化の革新：キーボードヒートマップが空間分布の直感的な洞察を提供

2. 理論的厳密性

  • 収束性証明：Bolzano-Weierstrass定理に基づく完全な証明を提供
  • 数学的導出が明確：CDF構築、確率計算などのステップが論理的に厳密
  • 仮定が明確：初期文字の均一分布などの仮定を明確に述べている

3. 実験設計

  • 標準化制御：キーボード、アイマスク、時間などの実験条件を統一
  • 倫理的配慮：参加者の知情同意を明確に述べている
  • 二重版設計：簡略版と現実版が相互に検証

4. 限界の誠実な議論

  • 第78文字までしか計算できないことを坦白に認める
  • サンプル量不足の問題を明確に指摘
  • データを歪める可能性のあるブートストラップ方法を使用しない

不足

1. 方法レベル

  • 致命的なスパース性の問題：コア方法はデータ不足のため目標を達成できない（完全な『ハムレット』確率の計算）
  • 初期文字仮定の検証不足：均一分布仮定が実証的に検証されていない
  • 隣接キー依存性の十分な活用不足：空間依存性仮定を提案しているが、モデルでキーボード幾何構造を明示的にモデル化していない

2. 実験設計の欠陥

  • 参加者の同質性：83%が中国語を母語とする者で、代表性が不足
  • サンプル量計画の不適切さ：事前にすべての遷移をカバーするために必要なサンプル量を推定すべきだった
  • 対照実験の欠如：独立モデルとの定量的比較を実施していない

3. 結果解釈

  • 「より低い」という誤解を招く表現：要約で結果が「理論計算より驚くほど低い」と述べているが、実際には10^134は依然として天文学的数字で、スパース性のため理論値と比較できない
  • 実用価値が限定的：最初の78文字の確率は完全な定理の理解に限定的な役割しか果たさない

4. 技術的詳細

  • Caps Lock計数アルゴリズムが粗い：連続した大文字小文字パターンに基づく推定は誤差が大きい可能性
  • Shiftキー配分方法の簡略化：長さ比による配分は実際の使用習慣（右手タイピング者はより左Shiftを使用する可能性）を無視

影響力

1. 学術的貢献

  • 学際的試み：確率論、人機相互作用、データ可視化を結合
  • 方法論的探索：実際のデータに基づく確率モデリングのケーススタディを提供
  • 教育的価値：極小確率の実際の意味を生き生きと示す

2. 実用的価値

  • 直接的応用が限定的：スパース性の問題により方法の一般化が困難
  • 啓発的意義：大規模遷移行列モデリングのデータ需要を明らかにする
  • 可視化ツール：キーボードヒートマップ方法は人機相互作用研究に応用可能

3. 再現性

  • 利点：実験プロセス、コードスニペット、データ処理ステップを詳細に説明
  • 不足：完全なコードとデータセットが公開されていない
  • 反復可能性：他の研究者は方法を反復可能だが、データを再度収集する必要がある

適用シーン

1. 適切な応用

  • 短い列の確率推定：10～50文字の短い列に対して方法は実行可能
  • タイピング行動研究：キーボードヒートマップは人機相互作用分析に使用可能
  • 確率教育：極小確率の直感的な教育ケースとして機能

2. 不適切な応用

  • 長いテキスト生成確率：スパース性の問題により長い列を処理できない
  • リアルタイム応用：有理数計算の複雑性が高い
  • キーボード間の一般化：モデルは特定のキーボードレイアウトに依存

3. 改善方向

  • 言語モデルの事前知識を統合
  • ベイズ平滑化を使用してゼロ確率を処理
  • 高次マルコフ連鎖を考慮

参考文献

論文が引用している主要な文献：

  1. Ross, S. M. (1976). A first course in probability. - 確率論の基礎
  2. Nast, C. (2007). The Typing Life. The New Yorker. - プリマス猿実験の報道
  3. Stewart, I. (2009). Professor Stewart's Hoard of Mathematical Treasures. - 従来の独立モデル
  4. Zito (2016). monkeys_typing_shakespeare (GitHub) - 進化アルゴリズムの実装
  5. Banerji et al. (2014). A Notion of Graph Likelihood and an Infinite Monkey Theorem. J. Phys. A - グラフ確率法
  6. Pal & Mesikepp. Finite Markov chains and Monte-Carlo methods - マルコフ連鎖理論
  7. Jolliffe & Cadima (2016). Principal component analysis: a review. Phil. Trans. R. Soc. A - PCA方法

総括的評述

これは野心的だが実行上に根本的な欠陥を持つ学部生研究論文である。研究者は実際のデータとマルコフモデルを通じて無限猿定理の確率推定を改善しようとしており、この考え方自体は革新的である。しかし、10万文字のサンプル量は128×128遷移行列のモデリングを支持するには遠く及ばないため、中核的な目標（完全な『ハムレット』確率の計算）を達成できず、最初の78文字の結果のみを得た。

論文の最大の価値は研究プロセスにおける困難を誠実に示すことにあり、スパース行列の問題、数値精度の課題など、後続の研究者にとって警告的な意義がある。キーボードヒートマップの可視化と有理数計算スキームは光点だが、方法論上の根本的な問題を補うことはできない。

研究を真に価値あるものにするには、以下が必要である：

  1. サンプル量を少なくとも100倍拡大（千万文字レベルに達する）
  2. ゼロ確率を処理するための平滑化技術を使用
  3. 独立モデルとの厳密な定量的比較を実施
  4. 方法の適用範囲を明確に述べる（短い列）

総合的に、これは有益な探索的試みだが、成熟した学術成果までの距離はまだ遠い。