Генерирование равномерно распределённых случайных чисел

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

Каждая из десяти цифр от 0 до 9 будет появляться примерно один раз из 10 в равномерной последовательности случайных цифр. Каждой паре двух последовательных цифр следует появиться один раз из ста и т. д. Однако если взять конкретную случайную последовательность длиной в миллион цифр, то она не всегда будет содержать 100 000 нулей, 100 000 единиц и т. д. Действительно, возможность появления такой последовательности незначительна; на самом деле, если рассматривать достаточно большую совокупность таких последовательностей, то в среднем будет появляться 100 000 нулей, 100 000 единиц и т. д.

Любая конкретная последовательность, содержащая миллион цифр, так же вероятна, как и любая другая. Если мы выберем миллион цифр наудачу и если окажется, что первые 999 999 из них — нули, то вероятность того, что последняя цифра в этой последовательности — также нуль, все еще останется точно равной одной десятой в истинно случайной ситуации. Это утверждение большинству кажется парадоксальным, однако оно не противоречит реальности.

Первая попытка получения ПСП

Некоторые люди думают, что получать случайные числа легко. По их мнению для этого достаточно делать случайные сложные математические действия над исходным числом. Если мы откроем второй том всем известного Кнута, то узнаем, что в 1959 Кнут тоже пробовал построить генератор, основанный на такой идее. Его алгоритм выглядел так:

К1. [Выбрать число итераций.] Присвоить Y наибольшую значащую цифру Х. (Мы выполним шаги К2-К13 точно Y+1 раз, т. е. применим рандомизированные преобразования случайное число раз.)

К2. [Выбрать случайный шаг] Присвоить следующую наибольшую значащую цифру X. Переходим к шагу К(3 + Z), т. е. к случайно выбранному шагу в программе.

КЗ. [Обеспечить > 5 х 109] Если X < 5000000000, присвоить X значение X + 5000000000.

К4. [Средина квадрата.] Заменить X серединой квадрата X.

К5. [Умножить.] Заменить X числом (1001001001 X) mod 1010.

К6. [Псевдодополнение.] Если X < 100000000, то присвоить X значение X + 9814055677; иначе присвоить X значение 1010- X.

К7. [Переставить половины.] Поменять местами пять младших по порядку знаков со старшими.

К8. [Умножить.] Выполнить шаг К5.

К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.

К10. [Модифицировать на 99999.] Если А' < 105, присвоить X значение — X 2 +99999; иначе присвоить X значение X — 99999.

К11. [Нормировать.] (На этом шаге А' не может быть равным нулю.) Если X <109, то умножить X на 10.

К12. [Модификация метода средин квадратов.] Заменить Х на средние 10 цифр числа Х(Х — 1).

К13. [Повторить?] Если Y > 0, уменьшить У на 1 и возвратиться к шагу К2. Если Y = 0, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым «случайным» значением.

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