Введение

Понятие случайной последовательности играет ключевую роль в теории вероятностей и статистике. Эта концепция обычно основывается на представлении о последовательности случайных величин, и многие статистические обсуждения начинаются со слов: "пусть X1, …, Xn – независимые случайные величины". Однако, как отмечал Д. Х. Леммер в 1951 году: "Случайная последовательность – это нечёткое понятие, в котором каждый элемент непредсказуем для непосвящённого, а его цифры проходят ряд тестов, традиционно используемых статистиками". Аксиоматическая теория вероятностей намеренно избегает определения случайной последовательности. Традиционная теория вероятностей не устанавливает, является ли конкретная последовательность случайной, но обычно переходит к обсуждению свойств случайных величин и стохастических последовательностей, исходя из некоторого понимания случайности. Школа Бурбаки рассматривала выражение "рассмотрим случайную последовательность" как языковое злоупотребление.

Ранняя история

Эмиль Борель был одним из первых математиков, формально рассмотревших случайность в 1909 году. В 1919 году Рихард фон Мизес дал первое определение алгоритмической случайности, вдохновленное законом больших чисел, хотя он использовал термин «коллективная», а не «случайная» последовательность. Используя концепцию невозможности выигрышной стратегии в азартных играх, фон Мизес определил бесконечную последовательность нулей и единиц как случайную, если она не является смещенной и обладает свойством устойчивости частоты, то есть частота нулей стремится к 1/2, и любая подпоследовательность, которую можно выбрать из нее с помощью «правильного» метода отбора, также не является смещенной. Критерий отбора подпоследовательностей, предложенный фон Мизесом, важен, поскольку, хотя последовательность 0101010101 не является смещенной, при выборе нечетных позиций мы получаем 000000, которая не является случайной. Фон Мизес так и не формализовал полностью свое определение правильного правила отбора для подпоследовательностей, но в 1940 году Алонзо Черч определил его как любую рекурсивную функцию, которая, прочитав первые N элементов последовательности, решает, следует ли ей выбирать элемент N+1. Черч был пионером в области вычислимых функций, и его определение опиралось на тезис Черча-Тьюринга о вычислимости. Это определение часто называют случайностью Мизеса — Черча.