“在公平币空间上,通过全部 Martin Löf 检验蕴含可计算随机性:可计算非负赌徒的严格越界开集形成合法检验。后者再蕴含 Schnorr 随机性;这些是同一空间中序列类的强弱包含,不是三种…”
形式陈述
设
一个
不要求各
直觉
同一个有限串在不同模型下可以很普通,也可以极其罕见。随机性首先是“相对于指定可计算概率源没有有效可识别的零测异常”,不是“每个比特都有一半机会为一”。
更换测度应同时更换检验预算和信息基准。若真实硬币偏向正面,却仍以公平币模型检查长期频率,检验发现的是源模型不匹配。
例子与边界
偏置币的预算要重新算
对可计算
取 [101] 的质量为
因此
可计算序列也可能对某个测度随机
若
所以“随机序列必不可计算”依赖公平币或适当无原子条件,不能照搬到所有可计算测度。对于
压缩基准变成自信息
对可计算概率测度,广义 Levin–Schnorr 刻画以前缀复杂度给出
这不是把公平币的串长直接换一个符号。正向在发现程序
反向取失败检验的第
零概率前缀使右边为无穷,因此不可能满足;正质量原子的前缀自信息有界,与上例相容。偏置币典型频率下,每位自信息趋于二元熵
推论与应用
这里还可讨论无限序列之间的可计算映射
若这种全定义映射把可计算测度
典型集通常控制有限块的频率或自信息,随机性则要求逃过所有有效零测异常。源模型相同是比较二者的前提,通过某一有限样本频率检验不等于认证无限序列随机。
参考资料
- [1] Péter Gács, Lecture Notes on Descriptional Complexity and Randomness,§§2.3.5–2.3.6,尤其 Theorem 2.3.4 的可计算测度复杂度刻画。
- [2] André Nies, Computability and Randomness, 2009,Martin-Löf 随机性和可计算概率测度。