АЛГОРИТМИЧЕСКАЯ СТАТИСТИКА, обзорный доклад

Пытаясь формализовать задачу алгоритмической статистики, Колмогоров предложил такую модель: для данного объекта (двоичного слова) $x$ мы ищем хорошую "статистическую модель" – распределение вероятностей на двоичных словах – можно ограничиться конечными распределениями или даже равномерными распределениями на конечных множествах. Тогда "качество" конечного $A$ (содержащего $x$) как модели измеряется двумя параметрами, предложенными Колмогоровым: его сложностью (модель должна быть простой) и "дефектом случайности $x$ в $A$" (модель должна улавливать все закономерности в $x$ — $x$ должно быть "типичным элементом $A$"). Имея слово $x$, мы можем изучать, какие комбинации этих параметров реализуемы ($\alpha$-$\beta$-стохастичность). Другой подход - искать "двухчастные описания" $x$ – сначала задаётся множество, а затем порядковый номер $x$ в этом множестве; этому подходу соответствует "структурная функция", предложенная Колмогоровым. Наконец, можно изучать колмогоровскую сложность с ограничением на время. Родственные подходы изучались под названием logical depth и sophistication разными авторами. В последние полтора десятилетия выяснилось, что с логарифмической точностью они оказываются эквивалентными – и хотя с практической точки зрения ограничения на время, тут появляющиеся, неразумно большие, но это важный нетривиальный результат о колмогоровской сложности (Беннетт, Витаньи, Верещагин, Бауэенс, другие.).