1. Случайные числа и случайные цифры. Таблицы случайных цифр. 2

3. Датчики случайных чисел. 2

4. Сравнение трех способов с практической точки зрения. 3

5. Метод псевдослучайных чисел. 4

6. Стандартный датчик псевдо-сдучайных чисел реализованный на ЭВМ 4

7. Простые алгоритмы. Длина отрезка апериодичности 5

9. Алгоритм Д. Неймана 6

10. Алгоритм Д. Леммера 6

11. Тесты для проверки случайных цифр 7

12. Проверка псевдослучайных чисел. 7

13. Моделирование дискретных случайных величин. 7

14. Оптимизация метода интервалов 8

15. Моделирование случайных событий. 8

16.Моделирование случайных непрерывных величин. 9

17.Моделирование многомерной случайной точки. 10

18.Поправки к приближенным распределениям. 10

19.Разделение области моделирования случайной величины. 11

20.Общая характеристика методов. 12

21.Метод Неймана. 12

22.Модифицированный метод Неймана. 13

24.Метод Метрополиса 13

25.Моделирование усеченных распределений. 14

26.Выбор равномерно распределенных точек в сложных пространственных областях. 14

27.Простейший метод вычислений. 15

28.Геометрический метод. 15

29.Сравнение точности методов Монте Карло. 15

30.Сравнение трудоемкости различных алгоритмов Монте Карло. 16

31. Моделирование процесса переноса и Метод имитации для решения задач о прохождении излучения через слой. 17

1. Случайные числа и случайные цифры. Таблицы случайных цифр.

Как пра­вило. в качестве стандартной выбирают непрерывную случайную величину , равномерно распределенную и интервале (0,1). Основные характеристики этой величины: при 0 <<1 плотность, а функция распределения; математическое ожидание, дисперсия.

Заметно реже в качестве стандартной используют дискретную случайную величину , которая с одинако­вой вероятностью может принимать 10 значений 0, 1, 2,...,9.

Величина будет называтьсяслучайным числом, а величина случайной цифрой.

Чтобы установить связь между и, разложим чис­лов бесконечную десятичную дробь:

(1)

Последняя запись означает, что

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

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

Вторая трудность связана с «незаконностью» много­кратного использования одной и той же таблицы. Наконец, отметим еще известный парадокс: в боль­шой таблице найдутся плохие участки. (Например, в таблице, содержащей 10¹⁰⁰ цифр, вполне вероятно найти 100 нулей подряд). Очевидно, самостоятельное исполь­зование таких участков недопустимо.

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

это потребуется.

3. Датчики случайных чисел.

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

Нетрудно представить себе счетчик, который подсчи­тывает количество

флуктуации напряжения шумящего прибора, превышающих заданный уровеньза фикси­рованное время(рис. 2). Еще проще устроить счет­чик, который выдавал бы число(mod 2), т. е. 0 при четном и 1 при нечетном. Если вероятности появле­ния 0 и 1 в таком процессе равны между собой, то мож­но считать, что устройство вырабатывает случайную по­следовательность двоичных цифр.

Если вероятность появления нуля отлична от поло­вины , то можно ввести какую-нибудь схе­му стабилизации вероятности. Например, можно груп­пировать цифры парами и выдавать 0 при получении пары 01 и 1 — при получении пары 10, а пары 00 и 11 просто опускать. Так как, то в результате получим последовательность нулей и единиц с равными вероятностями.

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

Применение датчиков случайных чисел свободно от тех недостатков, которые препятствуют широкому при­менению таблиц: не требуется места во внутреннем на­копителе и запас чисел практически неограничен. Тем не менее подавляющее большинство задач, решенных методом Монте-Карло, сосчитано без применения дат­чиков. Ибо датчики имеют свои, недостатки. Во-первых, числа, выработанные датчиком, нельзя воспро­извести. Это затрудняет контроль расчетов и делает невозможным счет на таких ЭВМ, на которых двойной пересчет является правилом. Во-вторых, приходится содержать и эксплуатировать дополнительное устройст­во, которое требует ухода и регулярной проверки «ка­чества» вырабатываемых чисел с помощью специальных тестов.

Основные области применения датчиков — системы автоматического регулирования и аналоговые вычисли­тельные машины, а не методы Монте-Карло.