Глава 8. Получение случайных чисел и букв Случайные последовательности

Предположим, у нас есть длинная последовательность нулей и единиц, то есть длинная двоичная последовательность. Что мы имеем в виду, когда говорим, что последовательность "случайная"? Первым очевидным критерием случайности будет такой: по‑видимому, логично предполагать, что она должна содержать "примерно равное количество" нулей и единиц. Но что означает здесь слово "примерно"?

Если длина последовательности ровно 1000 знаков, это совсем не означает, что мы обязательно требуем, чтобы в ней было ровно по 500 нулей и единиц. Но если в ней оказывается, например, 700 нулей и 300 единиц, то мы, конечно, подумаем, что это не случайная последовательность. Где-то посередине между этими двумя крайностями лежит граница приемлемости того, что мы готовы считать случайным: к примеру, 530 нулей и 470 единиц. Но у другого человека эти границы будут другими. Предположим, однако, что последовательность состоит из 500 нулей, за которыми следуют 500 единиц. Можем ли мы считать ее случайной, поскольку и тех, и других в ней ровно по 500? Конечно же нет, поскольку в случайной последовательности каждый из четырех двузначных наборов , 00, 01, 10 и 11, по нашему мнению, должен встретиться "около 250 раз", а здесь наборы 00 и 11 встречаются по 499 раз, 01 встречается только однажды, а 10 и вовсе отсутствует. Если же последовательность прошла и этот тест, мы поставим следующий вопрос: верно ли, что все восемь трехзначных наборов 000, 001, 010, 011, 100, 101, 110 и 111 встречаются "примерно по 125 раз", и так далее. Различных требований такого типа можно сформулировать бесконечно много. Существует обширная математическая литература по тестам, применяемым для проверки последовательностей, чтобы можно было обоснованно утверждать, что она "случайная". И наоборот, существует обширная литература, содержащая описание методов получения последовательностей, которые, не являясь в точности "случайными", удовлетворяют разнообразным тестам на случайность, и поскольку считаются достаточно непредсказуемыми, находят применение в определенных ситуациях. Если не вдаваться в подробности математических критериев проверки последовательности на случайность, то для наших целей подойдет следующее определение.

Определение 8.1

Двоичная последовательность считается случайной, если, сколько бы ее знаков нам ни было известно, вероятность появления нуля вслед за ними равна 0,5.

Именно так обстоит дело при многократном бросании "симметричной" монеты: вне зависимости от предыстории вероятность выпадения "орла" при очередном бросании всегда равна 0,5, или, если говорить об отклонении от среднего, "шансы равны".

Ничего особенного в двоичных последовательностях нет, и наше определение случайности можно с минимальными изменениями применить к последовательностям десятичных знаков или букв.

Определение 8.2

Последовательность десятичных знаков считается случайной, если, сколько бы ее знаков нам ни было известно, вероятность того, что следующий знак примет конкретное значение, равна 0,1.

Определение 8.3

Последовательность букв латинского алфавита считается случайной, если, сколько бы ее знаков нам ни было известно, вероятность того, что следом встретится конкретная буква, равна 1/26.