Принцип невозможности игровой системы — это концепция в теории вероятности . Он утверждает, что в случайной последовательности методический выбор подпоследовательностей не изменяет вероятности отдельных элементов. Первая математическая демонстрация приписывается Ричарду фон Мизесу (который использовал термин «коллектив», а не «последовательность»). [1] [2]
Принцип гласит, что ни один метод формирования подпоследовательности случайной последовательности ( системы азартных игр ) не улучшает шансы на определенное событие. Например, последовательность честных подбрасываний монеты дает равные и независимые шансы 50/50 на выпадение орла и решки. Простая система ставок на выпадение орла при каждом 3-м, 7-м или 21-м подбрасывании и т. д. не изменяет шансы на победу в долгосрочной перспективе . Как математическое следствие теории вычислимости , более сложные стратегии ставок (такие как мартингейл ) также не могут изменить шансы в долгосрочной перспективе.
Математическая демонстрация фон Мизеса определяет бесконечную последовательность нулей и единиц как случайную последовательность , если она не смещена, имея свойство стабильности частоты . Благодаря этому свойству частота нулей в последовательности стабилизируется на уровне 1/2, и каждая возможная подпоследовательность, выбранная любым систематическим методом, также не смещена. [3]
Критерий выбора подпоследовательности важен, поскольку, хотя последовательность 0101010101... не смещена, выбор нечетных позиций приводит к 000000..., что не является случайным. Фон Мизес не полностью определил, что представляет собой «правильное» правило выбора для подпоследовательностей, но в 1940 году Алонзо Чёрч определил его как любую рекурсивную функцию , которая, прочитав первые N элементов последовательности, решает, хочет ли она выбрать элемент номер N+1. Чёрч был пионером в области вычислимых функций, и данное им определение опиралось на тезис Чёрча Тьюринга о вычислимости. [4] [5] [6]
В середине 1960-х годов А. Н. Колмогоров и Д. У. Лавленд независимо друг от друга предложили более разрешительное правило выбора. [7] [8] По их мнению, определение рекурсивной функции Чёрча было слишком ограничительным, поскольку оно считывало элементы по порядку. Вместо этого они предложили правило, основанное на частично вычислимом процессе, который, считывая любые N элементов последовательности, решает, хочет ли он выбрать другой элемент, который ещё не был считан.
Этот принцип оказал влияние на современные концепции случайности, например, на работу А. Н. Колмогорова по рассмотрению конечной последовательности как случайной (по отношению к классу вычислительных систем), если любая программа, способная сгенерировать последовательность, по крайней мере такой же длины, как и сама последовательность. [9] [10]