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

基本信息

• 论文ID: 2511.11760
• 标题: Simulating Keystroke and Computing the Theoretical Probability of Infinite Monkey Theorem with Markov Process
• 作者: Juncheng Yi, Hongyi Jiang, Kaiwen Zhou (University of Washington)
• 分类: 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. 马尔可夫矩阵构建

转移概率定义： $P_{u,v} = P(\text{当前字符为}\ u\ |\ \text{前一字符为}\ v)$

其中 $u, v \in [0, 127]$ 为ASCII码值。

矩阵结构：

• 简化版本：26×26矩阵（仅小写字母）
• 现实版本：96×96矩阵（ASCII 32-126加换行符）

归一化条件： $\sum_{u=0}^{127} P_{u,v} = 1, \quad \forall v$

每行代表给定前一字符时，所有可能后续字符的概率分布。

3. 累积分布函数（CDF）矩阵

为了实现加权随机游走，将转移概率矩阵转换为CDF矩阵：

$S_{i,v} = \sum_{u=0}^{i} P_{u,v}$

其中 $S_{127,v} = 1$（满足CDF性质）。

整数化处理： 将CDF矩阵乘以 $10^{18}$ 转换为整数矩阵 $\tilde{S}$，便于后续计算： $\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. 找到最小的列索引 m 使得 S[m,v] ≥ k/10^18
4. 返回 ASCII值为 m 的字符

5. 序列概率计算

对于目标文本序列 $c_1c_2...c_n$（如《哈姆雷特》）：

$P(\text{序列}) = P(c_1) \times \prod_{i=2}^{n} P(c_i|c_{i-1})$

其中：

• $P(c_1) = 1/26$（首字符均匀分布）
• $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_{\text{独立}} = \left(\frac{1}{95}\right)^n$

本方法考虑字符间依赖： $P_{\text{马尔可夫}} = \frac{1}{26} \times \prod_{i=2}^{n} P(c_i|c_{i-1})$

合理性：键盘空间布局使得相邻键更容易连续按下，符合人类无意识打字行为

2. 稀疏矩阵处理策略

问题：10万字符样本无法覆盖所有128²=16,384种字符转移
解决方案：

• 承认模型局限性，仅计算到首个零概率转移为止
• 不使用Bootstrap方法（避免引入不存在的边，扭曲原始数据）
• 明确标注结果为"前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(\text{目标序列})$
2. 期望生成时间：$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 \approx 10^{-134}$

完整概率表达式（部分展示）：

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

2. 期望生成时间

$E[\tau] = \frac{1}{10^{-134}} \times \frac{78}{760} \text{ 分钟} = 10^{134} \times 0.1026 \text{ 分钟}$

宇宙尺度对比： $E[\tau] \approx 1.41533 \times 10^{117} \times \text{宇宙年龄}$

（宇宙年龄约138亿年≈7.26×10^15分钟）

3. 零概率转移出现位置

在计算《哈姆雷特》序列概率时：

• 第79个字符处首次遇到零概率转移
• 具体转移：'P' → 'e'（数据集中未观测到此转移）
• 导致后续所有概率为0

可视化结果

1. 人类随机打字模式

发现：

• 空格键：频率最高（远超其他键）
• 分布形状：呈现二维类正态分布
• 峰值区域：集中在R和J键附近（键盘中部）
• 边缘键：频率显著较低

2. 《哈姆雷特》字符分布

对比发现：

• 空格键在《哈姆雷特》中频率更高（文本中词间需要空格）
• 字母分布更符合英语语言统计规律
• 与随机打字模式存在显著差异

3. 马尔可夫矩阵特征

稀疏性：

• 128×128矩阵中大量元素为0
• 10万字符样本无法覆盖所有可能转移
• 稀疏度导致长序列概率快速降为0

实验发现

1. 方法论发现

• 样本量需求：10万字符远不足以填充所有16,384个转移概率
• 首字符假设的影响：首字符采用均匀分布（1/26）对最终概率影响有限
• 有理数方法的必要性：浮点数在第10个字符后即失效

2. 人类行为模式

• 键盘中心偏好：随机打字时倾向于击打中部键位
• 空间依赖性存在但有限：相邻键的条件概率略高，但效应不如预期显著
• 文化背景影响：25/30参与者为中文母语者，可能影响打字习惯

3. 理论vs实际

• 马尔可夫模型的优势有限：虽然考虑了依赖性，但由于矩阵稀疏性，实际可计算长度反而受限
• 独立假设可能更实用：对于长序列，独立模型虽不精确但至少能给出完整估计

相关工作

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. 方法层面

• 稀疏矩阵问题：零概率转移导致计算提前终止
• 首字符假设：均匀分布假设缺乏实证支持
• Bootstrap未使用：虽然能缓解稀疏性，但可能扭曲数据

3. 适用性限制

• 仅适用于"类人类"随机打字，不适用于真实猴子
• 依赖特定键盘布局（LG Rog Strix Flare）
• 未考虑打字速度的变化

未来方向

1. 扩大样本规模：收集百万级字符样本以填充更多转移概率
2. Bootstrap方法探索：在保证数据真实性前提下，研究平滑技术的应用
3. 多阶马尔可夫链：考虑前2-3个字符的依赖关系
4. 跨文化对比：比较不同语言背景参与者的打字模式
5. 理论改进：研究稀疏马尔可夫链的概率估计理论

深度评价

优点

1. 方法创新性

• 实证数据驱动：首次使用真实人类打字数据构建马尔可夫模型
• 有理数方案：巧妙解决了极小概率的数值计算问题
• 可视化创新：键盘热力图提供直观的空间分布洞察

2. 理论严谨性

• 收敛性证明：提供了基于Bolzano-Weierstrass定理的完整证明
• 数学推导清晰：CDF构建、概率计算等步骤逻辑严密
• 假设明确：清楚说明了首字符均匀分布等假设

3. 实验设计

• 标准化控制：统一键盘、眼罩、时长等实验条件
• 伦理考虑：明确说明参与者知情同意
• 双版本设计：简化版和现实版相互验证

4. 诚实的局限性讨论

• 坦诚承认只能计算到第78个字符
• 明确指出样本量不足的问题
• 不使用可能扭曲数据的Bootstrap方法

不足

1. 方法层面

• 致命的稀疏性问题：核心方法因数据不足而无法完成目标（计算完整《哈姆雷特》概率）
• 首字符假设缺乏验证：均匀分布假设未经实证检验
• 相邻键依赖性未充分利用：虽提出空间依赖假设，但未在模型中显式建模键盘几何结构

2. 实验设计缺陷

• 参与者同质性：83%为中文母语者，代表性不足
• 样本量规划不当：事前应估算所需样本量以覆盖所有转移
• 缺乏对照实验：未与独立模型进行定量对比

3. 结果解释

• "更低"的误导性表述：摘要称结果"surprisingly lower than theoretical computation"，但实际上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. 明确说明方法的适用范围（短序列）

总体而言，这是一次有益的探索性尝试，但距离成熟的学术成果尚有距离。