Skip to content

定义Definition

可计算测度下的随机性

施工中 · 内容逐步修订

Randomness for computable measures

按可计算源的真实柱集概率定义有效检验,手算偏置币预算,并说明可计算原子、零概率前缀和信息密度。

形式陈述 ​

设 μ 是 Cantor 空间上的 Borel 概率分布。若存在统一可计算程序,输入有限串 σ 和精度 k,输出 μ([σ]) 的误差至多 2−k 的有理近似,则称 μ 可计算。

一个 μ-Martin-Löf 检验是统一有效开集列 (Un),满足 μ(Un)≤2−n。避开每个检验的交集的序列称为 μ-随机。这保持Martin-Löf 随机性的有效开集与量词,只把公平币预算换成真实源预算。[1]

不要求各 Un 的最终测度可计算,也不要求 μ 无原子。若讨论 Schnorr 版本,还须另加层测度统一可计算条件。

直觉

同一个有限串在不同模型下可以很普通,也可以极其罕见。随机性首先是“相对于指定可计算概率源没有有效可识别的零测异常”,不是“每个比特都有一半机会为一”。

更换测度应同时更换检验预算和信息基准。若真实硬币偏向正面,却仍以公平币模型检查长期频率,检验发现的是源模型不匹配。

例子与边界

偏置币的预算要重新算 ​

对可计算 p∈(0,1),独立 Bernoulli(p) 源满足

μp([σ])=p#1(σ)(1−p)#0(σ).

取 p=1/3,柱集 [101] 的质量为 (1/3)2(2/3)=2/27,不是公平币的 1/8。令 Un=[02n],则

μ1/3(Un)=(2/3)2n=(4/9)n≤2−n.

因此 (Un) 是一个统一有效的检验,全零序列被捕获。若误用 [0n],其质量 (2/3)n 大于 2−n,原预算不成立;增加前缀长度才修复检验。

可计算序列也可能对某个测度随机 ​

若 μ=δ0∞,则全零序列是可计算的,却是 μ-随机。任何包含它的集合测度都为一,不可能属于预算小于一的检验层。更一般地,任意正质量原子 X 都是其测度下的随机点:取 2−n<μ({X}) 即知 X∉Un。

所以“随机序列必不可计算”依赖公平币或适当无原子条件,不能照搬到所有可计算测度。对于 μ([σ])=0 的柱集,则恒取 Un=[σ] 就能排除其中全部序列。

压缩基准变成自信息 ​

对可计算概率测度,广义 Levin–Schnorr 刻画以前缀复杂度给出

X 为 μ-随机⟺∃c ∀nK(X↾n)≥−log2⁡μ([X↾n])−c.

这不是把公平币的串长直接换一个符号。正向在发现程序 p 输出 σ 后,等待严格不等式 μ([σ])<2−|p|−c 被可计算测度的误差界证实,再枚举这个柱集。同一输出在质量证明中只取最短程序,Kraft 不等式与并集界便把整层质量压到 2−c;这一过程对 c 统一,不要求判定等号。

反向取失败检验的第 2k 层,先用前缀页的不可撤回算法变成前缀自由清单。对其中正质量柱集,逐步求有理界 0<a≤μ([σ])≤b<2a,令 ℓ=⌈−log2⁡a⌉,便有 2−ℓ≤μ([σ]) 且 ℓ<−log2⁡μ([σ])+2。枚举请求 (ℓ−k,σ);因 μ([σ])≤2−2k,码长非负,全部层的共同权重至多 ∑k≥12kμ(U2k)≤1。同一 Kraft–Chaitin 机器给统一常数,检验每层命中即产生无界自信息亏损。若 X 有零质量前缀,恒定柱集检验和无穷自信息已直接处理;否则每个命中它的前缀都有正质量,上述求界必停。无需另行判定哪些柱集质量为零。

零概率前缀使右边为无穷,因此不可能满足;正质量原子的前缀自信息有界,与上例相容。偏置币典型频率下,每位自信息趋于二元熵 h(p),不必趋于一。比较不同源的复杂度时,先校准这条基准。

推论与应用

这里还可讨论无限序列之间的可计算映射 F:2N→2N:一台oracle 机器以输入序列为查询源,对每个序列及每个所求输出位都在有限步后给出答案。这不是把无限序列当作一次读完的有限字;每次有限输出仅查询有限多个输入位。

若这种全定义映射把可计算测度 μ 推到可计算测度 ν,则它把 μ-随机点送到 ν-随机点。对目标柱集,枚举所有已经产生相应输出前缀的有限查询轨迹,再把有限个指定坐标的答案补成有限前缀柱集,便能有效枚举其原像。因此把 ν-检验各层取原像,就得到同预算的 μ-检验。对仅几乎处处定义的映射,必须额外检查有效定义域及随机点是否位于其中,不能跳过这项条件。

典型集通常控制有限块的频率或自信息,随机性则要求逃过所有有效零测异常。源模型相同是比较二者的前提,通过某一有限样本频率检验不等于认证无限序列随机。

参考资料
关系图谱19 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

暂未标注直接上位概念。

下位 / 直接特例

类型化关系