§ 2. Генераторы случайных чисел

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

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

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

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

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

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

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

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

В настоящем параграфе мы остановимся на специальных устройствах, формирующих случайные величины вне машины путем физического моделирования некоторых случайных процессов. Такого рода устройства и называются обычно генераторами (или датчиками) случайных чисел. Основную роль играют генераторы случайных чисел, равномерно распределенных в интервале (О, 1) или, точнее говоря, генераторы квазиравномерных, в смысле § 1, случайных величин.

Как показано в § 1 настоящей главы, получение квазиравномерных чисел сводится к получению групп

независимых величин каждая из которых с вероятностью 0,5 принимает значение и с такой же Вероятностью значение

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

Имеются два основных вида физических источников для выработки случайных чисел

Первый способ основан на излучении радиоактивных веществ, второй способ — на собственных шумах электронных ламп.

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

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

Вероятность того, что будет сосчитано четное число частиц, равна тогда

Сосчитаем эту сумму, полагая

Отсюда видно, что вероятность появления за время четного числа части равна

Если значение достаточно велико, то это выражение близко к .

Величина равна математическому ожиданию ко личества частиц, зафиксированных за время

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

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

Считая, что при обычно используемой точности число берется с 15 двоичными знаками, отсюда можно вывести, что на получение одного равномерно распределенного числа тратится время в течение которого счетчик фиксирует порядка 150—200 радиоактивных частиц. При необходимости получать еще и нормально распределенные числа это время соответственно увеличивается. С этим связаны ограничения в применимости данного метода получения случайных чисел.

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

Определим теперь величину условием

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

если же то для определения берется первая из следующих пар принимающих разные значения. Если обозначить вероятность равенства через то вероятность того, что составляет

Легко видеть, что процесс поиска подходящей пары с вероятностью единица заканчивается в конечное число шагов и занимает в среднем

шагов. При значениях вероятности это составляет шага.

Второй прием особенно удобен, когда значение близко к половине. Он состоит в определении величины по правилу:

Пусть . В этом случае вероятность того, что составляет

т. е. гораздо ближе к половине, если прием легко итерируется. Именно, полагаем Тогда вероятности того, что связаны условием — которое и обеспечивает приближение к половине с увеличением 5. Если принять

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

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

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

где — любое целое число. Подсчитаем вероятность того, что если известно, что вероятность равенства равна

Ясно, что определяют исходя из биномиального распределения.

Именно, вероятность того, что равна

Отсюда

а вероятность того, что равна

Образуем разность этих равенств:

Отсюда получается

или

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

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

Рассмотренные здесь принципы могут быть использованы для построения многоразрядного генератора,

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

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