Генераторы случайных чисел (общие сведения).

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

Существуют три способа генерации случайных чисел (СЧ): аппаратный (физический), табличный (файловый) и алгоритмический (программный).

В аппаратном способе случайные числа вырабатываются специальным электронным устройством – генератором (датчиком) случайных чисел. Достоинствами являются: отсутствие дополнительных вычислительных операций ЭВМ по выработке случайных чисел, необходима только операция обращения к внешнему устройству ЭВМ (датчику), не ограниченный запас чисел, не требуется дополнительная память ЭВМ, высокая скорость работы, генерация " хороших" последовательностей случайных цифр и чисел. Недостатками являются: отсутствие гарантии качества последовательности непосредственно во время моделирования системы на ЭВМ (требуются периодические проверки), нельзя повторно получать при моделировании одинаковые последовательности чисел, необходимость дополнительного устройства.

В табличном способе случайные числа, оформленные в виде таблицы, помещаются в виде файла в память ЭВМ. Имеются специальные справочники, где содержатся таблицы случайных чисел, полученные в результате многократного выполнения каких-либо физических опытов. Эта таблица из справочника может быть введена в ЭВМ. Таблицы представляют собой последовательности цифр от 0 до 9, имеющих равную вероятность появления. Использование таких таблиц очень простое: если требуется случайная цифра, то берется первая попавшаяся позиция из таблицы. Если требуется n-позицонное случайное число, то выбирается n последовательных очередных цифр таблицы. Цифры выбираются в любом направлении и с любого места.

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

Недостатки: запас чисел ограничен, требуется большой объем памяти ЭВМ.

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

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

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

В качестве основных тестов используют проверки на равномерность, стохастичность и независимость. Проверка на равномерность осуществляется по гистограмме с использованием косвенных признаков. Проверка стохастичности наиболее часто проводится методами комбинаций и серий. Сущность метода комбинаций сводится к определению закона распределения длин участков между единицами (нулями) или закона распределения (появления) числа единиц (нулей) в n-разрядном двоичном числе. Серией называется любой отрезок последовательности случайных чисел, состоящий из следующих друг за другом элементов одного и того же рода. Число элементов в отрезке называется длиной серии. Проверка независимости проводится на основе вычисления корреляционного момента. При моделировании с использованием программных генераторов равномерных последовательностей важными характеристиками качества является длина периода P и длина отрезка апериодичности L. Длина отрезка апериодичности псевдослучайной последовательности есть наибольшее целое число, такое, что при событие не имеет места. Это означает, что все числа в пределах отрезка апериодичности не повторяются. Очевидно, что использование при моделировании систем последовательности чисел , длина которой больше отрезка апериодичности L, может привести к повторению испытаний, что не дает новых статистических данных. Из-за того, что разрядная сетка ЭВМ конечна, при формировании последовательности чисел рано или поздно одно из них совпадет с ранее вычисленным числом . После этого все формируемые далее числа будут совпадать с уже имеющимися и при этом будут следовать в том же порядке, т.е. числа при i=1, 2, … (см. рис. 7). Из рисунка видно, что в последовательности выделяют два участка – отрезок апериодичности, на котором не наблюдается повторение числовых последовательностей, и участок периодических последовательностей. Количество чисел, содержащихся в отрезке апериодичности, называют длиной отрезка апериодичности L, а множество чисел называют периодом последовательности Т.

 

 

L

 

0 1 2 3 l l+1 L-1 L L+1

 

T T

Рис. 7

Равномерно распределенные псевдослучайные числа проверяются: путем подсчета количества нулей и единиц в двоичном представлении числа (их количество должно быть примерно равным); подсчета количества различных групп (00, 11, 01, 10, 000, 111 и т.д.) в числе, их взаимосвязи и частоты повторения и рядом других проверок.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: