Цифровой журнал «Компьютерра» № 42

- Можно крутить рулетку, раскрасив предварительно круг в два цвета (например, в красный и черный); красный цвет может соответствовать единице, черный — нулю. К слову, этот возможный способ получения стандартных случайных чисел обусловил название методов Монте-Карло, ведь в знаменитом игорном центре тоже крутят рулетку. Недостаток этого способа получения случайных чисел: долгое время реализации и отсутствие автоматизации процесса получения случайных нулей и единиц. Зато здесь более-менее гарантирована вероятность 1/2, если круг раскрашен двумя цветами пополам.

Автоматизация процесса формирования мантиссы стандартного случайного числа связана с применением различных случайных шумов. Иногда используются шумы самого компьютера. Более надежными и быстрыми считаются квантовые генераторы случайных шумов, в которых используются специальные свойства потоков малых (элементарных) частиц.

Проблему получения равных вероятностей появления нуля и единицы часто решают следующим образом. Сигнал замеряют дважды. Возможны следующие исходы: оба раза сигнал был (состояние СС), оба раза сигнала не было (состояние НН), первый был — второго не было (состояние СН) и первый не был — второй был (состояние НС). Если даже вероятность появления сигнала не равнялась в точности 1/2, то все равно состояния НС и СН являются равновероятными. То есть можно фиксировать только эти два состояния (приписав, например, состоянию НС единицу, а СН — нуль), а состояния СС и НН игнорировать.

Есть много ученых и практиков, убежденных в том, что только физические датчики могут дать «настоящие», «поистине случайные» наборы нулей и единиц. Ирония ситуации состоит в том, что уверенность этих исследователей часто зиждется на незнании природы того или иного шума (а вдруг он возникает благодаря каким-то вполне детерминированным — неслучайным — процессам?!).

Применение физических датчиков в расчетах по методу Монте-Карло имеет следующие трудности и недостатки. Во-первых, надежный датчик представляет собой недешевый прибор, в котором кроме всего прочего должны быть предусмотрены быстрые обмены информацией с компьютером. Во-вторых, требуется постоянная проверка выдаваемых датчиком последовательностей (здесь используется мощный аппарат критериев и методик математической статистики), так как даже сверхнадежное техническое устройство дает сбои. В-третьих, имеются отмеченные выше трудности получения равномерного распределения стандартного случайного числа.

Поэтому большинство расчетов по методу Монте-Карло производится с использованием генераторов псевдослучайных чисел.

- Как устроены генераторы псевдослучайных чисел?

- Большинство таких генераторов основаны на применении так называемого метода вычетов и его модификаций. Идея довольно проста. Берется дробное число α_i с большим «хвостом» (то есть с длинной мантиссой), умножается на большое целое число M, в результате получается большое целое плюс дробная часть. Потом целую часть результата убирают, а дробную берут в качестве следующего числа:

α_i+1 = {Mα_i}

Оказывается, если множитель M взять достаточно большим (например, в современных генераторах используются множители порядка M = 5¹⁰⁰¹⁰⁹) получается, что «хвосты» α_i+1 ведут себя как настоящие стандартные случайные числа α.

На самом деле «настоящее» (теоретическое) значение стандартного случайного числа получить невозможно, так как α представляет собой дробь с бесконечной мантиссой, состоящей из нулей и единиц (такую дробь в принципе воспроизвести нельзя). Здесь ситуация похожа на проблему воспроизведения вещественных (в частности, иррациональных) чисел на компьютере.

На практике в методе вычетов при представлении чисел α_i берут «длинные» мантиссы (например, в современных генераторах используется T = 128 разрядов мантиссы).

В методе вычетов имеется также проблема периодичности: не позднее, чем через 2^T шагов произойдет «зацикливание» генератора. В расчетах по методу Монте-Карло не рекомендуется использование более чем L/2 обращений к генератору; здесь L — длина периода, равная числу шагов метода вычетов, после которого начинается повторение последовательности α_i. При удачном подборе множителя M можно получить величину периода L = 2^{T — 2} (это едва ли не «рекордный» результат). Для T = 128 величина L/2 равна 2¹²⁵, этого вполне хватает для широкого класса современных задач, решаемых с помощью численного статистического моделирования.

Решение проблем конечности мантиссы (периодичности) не гарантирует качества получаемых чисел α_i. Требуется проведение тестов, показывающих, что эти числа по свойствам близки к настоящим (теоретическим) стандартным случайным числам α (тем, что имеют бесконечную мантиссу). Здесь используют широкий спектр критериев и методик математической статистики.