算法随机性

概述

算法随机性（Algorithmic Randomness）将"随机性"从概率分布的集合性质转化为单个对象的内禀性质：一个字符串如果无法被显著压缩（K(x) ≈ |x|），它就是随机的。

关键内容

Kolmogorov 的定义

一个长度为 n 的字符串 x 是 c-随机的，如果 K(x) ≥ n - c。

即如果一个字符串不能被显著压缩（最短程序几乎和字符串本身一样长），它就是"随机的"。

直觉

• "00000000"（全零）不随机——"打印 n 个 0"是很短的程序
• "01010101"（交替）不随机——"重复 01"是很短的程序
• "10110100..."（看似无规律）如果没有比自身更短的描述，就是随机的

革命性意义

这一定义将"随机性"从概率分布的集合性质转化为单个对象的内禀性质——一个字符串是否随机，取决于它自身的算法结构，而非它来自什么分布。

与 von Mises 集体概念的比较

von Mises (1919) 曾试图用"集体"(Kollektiv)的概念定义随机序列——一个无限序列是随机的，如果它的频率极限存在且任何可计算的子序列选择规则都不能改变这些极限。Kolmogorov 的算法随机性定义更简洁、更根本。

Martin-Löf 随机性

Martin-Löf (1966) 基于 Kolmogorov 的思想发展了算法随机性的严格理论，给出了无限序列随机性的精确定义，与 Kolmogorov 有限字符串的随机性定义互补。

来源

• raw/books/信息论/09_kolmogorov_1965_three_approaches_to_information.md — Kolmogorov (1965) 深度解析

相关

• 柯尔莫哥洛夫复杂性 — 定义基础
• 算法信息论 — 所属学科
• 安德烈·柯尔莫哥洛夫 — 提出者