Колмогоров и случайность.
в 1933 году советский математик написал тонкую книгу. он формализовал вероятность за 60 страниц. то что философы спорили веками — стало аксиомами. и ещё он спросил: что значит быть по-настоящему случайным?
| тема | история математики · вероятность · сложность Колмогорова |
| читать | ~8 минут |
| связано | вероятность · цепи Маркова · парадоксы · информация |
В 1933 году Андрей Николаевич Колмогоров опубликовал «Grundbegriffe der Wahrscheinlichkeitsrechnung» — «Основные понятия теории вероятностей»1. Тонкая книга. 60 страниц на немецком. Она закрыла вопрос который мучил математиков 300 лет: что такое вероятность формально?
До Колмогорова было несколько конкурирующих определений. Классическое: вероятность = благоприятные исходы / все исходы. Работает только для симметричных ситуаций. Частотное: вероятность = предел частоты при бесконечных повторениях. Не применимо к единичным событиям. Субъективное: вероятность = степень уверенности. Слишком расплывчато для строгой математики.
Колмогоров предложил аксиоматический подход. Вероятность — функция P на σ-алгебре событий:
2. P(Ω) = 1 — вероятность всего пространства равна 1
3. P(A ∪ B) = P(A) + P(B) если A и B несовместны
Три аксиомы. Из них выводится вся теория вероятностей. Условная вероятность. Независимость. Математическое ожидание. Закон больших чисел. Центральная предельная теорема. Всё — из трёх аксиом.
Колмогоров не говорил что такое вероятность физически. Он говорил как с ней работать математически. Это и есть сила аксиоматического подхода.
Колмогоров был советским математиком. Родился в 1903 году. Умер в 1987. Работал в МГУ 60 лет. Его интересы: теория вероятностей, математическая логика, топология, теория функций, гидродинамика, педагогика. В 1941 году объяснил турбулентность. В 1954 году — устойчивость солнечной системы (КАМ-теория)4. Один из самых широких математиков XX века.
Но самый странный его вопрос — про случайность.
Что значит что последовательность случайна? Возьми монетку. Подбрось 100 раз. Запиши результат: 0100110101001110010101101001… Случайна ли она?
Интуитивно: случайная последовательность не имеет паттернов. Но любая конкретная последовательность имеет вероятность (1/2)¹⁰⁰ — такую же как ОООООООО…О (100 орлов подряд). Все последовательности одинаково вероятны. Так что же делает одну «случайной» а другую — нет?
В 1960-х Колмогоров предложил ответ2: случайность через сложность. Колмогоровская сложность строки s — это длина кратчайшей программы которая её генерирует.
где U — универсальная машина Тьюринга.
100 орлов подряд: программа «напечатай 100 орлов» — короткая. K мала. Строка не случайна. Случайная последовательность: кратчайшая программа — сама эта последовательность. K ≈ длина строки. Строка несжимаема.
Случайность = несжимаемость = отсутствие паттернов.
Проблема: K невычислима3. Нельзя написать программу которая считает K(s) для любой s. Это следствие теоремы Гёделя и задачи остановки Тьюринга. Случайность определена точно — но неопределяема алгоритмически.
Мы можем приближать K: gzip, bzip2, LZ77 — все алгоритмы сжатия ищут паттерны и убирают их. Хорошо сжимается → малая K → не случайно. Не сжимается → большая K → скорее всего случайно.
Это применяется в криптографии: хороший генератор случайных чисел производит несжимаемые последовательности. В тестировании программного обеспечения. В машинном обучении: MDL (minimum description length) — модель которая сжимает данные лучше — обобщает лучше.
Колмогоров дал математике два подарка. Первый: строгое основание теории вероятностей. Второй: определение случайности через информацию.
Оба — через простоту и минимальность. Три аксиомы. Кратчайшая программа. Это его стиль.
«вероятность — это мера нашего незнания а не свойство мира.»
— Андрей Колмогоров