4. ПОЛУЧЕНИЕ СЛУЧАЙНОГО ЧИСЛА R ОТ 0 ДО 1

Если метод Монте-Карло осуществляется вручную (без помощи машин), то для получения случайного числа от 0 до 1 чаще всего применяются так называемые таблицы случайных чисел. Эти таблицы приводятся во многих руководствах по математической статистике и вычислительной технике (см. например, [18, 19]). Таблицы содержат чередующиеся в случайном порядке цифры

При составлении таблиц приняты меры к тому, чтобы каждая из этих цифр встречалась примерно одинаково часто и независимо от других.

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

Пусть, например, требуется получить число R с четырьмя знаками после запятой. Обратимся к таблице случайных чисел и возьмем оттуда любую группу из четырех рядом стоящих знаков, например 7643. Будем считать, что наше случайное число приняло значение 0,7643. Следующий раз, когда придется бросать единичный жребий, возьмем следующие четыре цифры Пусть они, например, будут 3312 — значит, следующее случайное число будет 0,3312, и т. д. Можно брать цифры, стоящие не рядом, а через одну; или же в начале и в конце столбца, или строки — словом, любым способом, лишь бы принцип выбора не был никак связан со значениями самих цифр.

Для розыгрыша случайного числа R вручную можно применять не только таблицы случайных чисел, но и другие датчики, например диск, проградуированный в мелких делениях, размеченных числами от 0 до 1 (рис. 8.14). В центре диска закреплена хорошо уравновешенная стрелка, приводимая во вращение, например, электромотором, включаемым нажатием кнопки. После отпускания кнопки стрелка останавливается в случайном положении, и конец ее указывает случайное число

Если метод Монте-Карло осуществляется не вручную, а на ЭЦВМ, то для выбора случайного числа от 0 до 1 могут применяться как физические датчики случайных чисел, так и вычислительные алгоритмы для получения так называемых «псевдослучайных» чисел.

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

Пусть имеет случайный шум (т. е. случайным образом меняющееся напряжение ) (рис. 8.15), который мы сравниваем с некоторым постоянным уровнем Такой шум может быть положен в основу правила выработки случайного числа от 0 до 1. Предположим, что ЭЦВМ работает в двоичном коде; тогдс случайное число от 0 до 1 представляет собой двоичную правильную дробь, в которой на каждом месте одинаково вероятны знаки 0 или 1. Условимся считать, что очередной двоичный знак случайного числа будет 0, если за некоторый промежуток времени Т шум превысил уровень четное число раз, и 1 — если нечетное. Теперь предположим, что таких датчиков работают одновременно и посылают случайные знаки 0 и 1 в двоичных разрядов регистра некоторого числа R.

Рис. 8.14

Рис. 8.15

Тогда, если интервал времени Т взять достаточно большим так, чтобы на нем укладывалось достаточно много колебаний шума то четное и нечетное числа превышений уровня будут встречаться в среднем одинаково часто, и -разрядное двоичное число будет распределено приблизительно равномерно на участке 0,1.

Можно предложить и другие принципы формирования случайных чисел на основе того или другого физического случайного процесса; все они требуют оборудования ЭЦВМ специальными датчиками случайных чисел. Для неспециализированной ЭЦВМ, только эпизодически привлекаемой к моделированию операций методом Монте-Карло, это оборудование себя не оправдывает. Гораздо чаще при моделировании методом Монте-Карло пользуются так называемыми псевдослучайными числами. Так называются числа, вырабатываемые (вычисляемые) самой машиной по некоторому правилу (алгоритму), построенному так, чтобы знаки 0 и 1 встречались в среднем одинаково часто, и, кроме того, чтобы зависимость как между отдельными знаками, так и между сформированными из них многозначными числами практически отсутствовала. Для получения псевдослучайных чисел пользуются разными приемами. Например, можно перемножить два произвольных -значных двоичных числа и из произведения взять средних знаков — это будет число затем перемножить и повторить процедуру и т. д. Существуют способы получения псевдослучайных чисел, основанные не на перемножении чисел, а на их сдвиге друг относительно друга на несколько разрядов; после сдвига производится сложение и затем выбор из суммы средних знаков, и т. д.

Различные способы получения псевдослучайных чисел подробно описываются в специальных руководствах (см., например, [ 15, 27]).

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

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