Сложность и оптимальные алгоритмы моделирования дискретных распределений

• Автор: Походзей, Борис Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Ленинград
• Количество страниц: 93 c. : ил

ПРЕДИСЛОВИЕ

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

Цель и содержание работы.

1. ПРЕДВАРИТЕЛЬНЫЙ ПРИМЕР

Моделирование распределения Бернулли.

2. ПРЕОБРАЗОВАНИЕ СЛУЧАЙНЫХ БИТОВ В СЛУЧАЙНЫЕ ВЕЛИЧИНЫ

С КОНЕЧНЫМИ ДИСКРЕТНЫМИ РАСПРЕДЕЛЕНИЯМИ

Понятие ПДР-дерева и ПДР-алгоритма. Существование ПДР-деревьев, критерий их оптимальности и нижняя граница сложности ПДР-алгоритмов. Оптимальный алгоритм моделирования конечного дискретного распределения. Энтропийная мера сложности оптимальных ПДР-алгоритмов. Экстремальные границы сложности оптимальных алгоритмов.
3. ПРЕОБРАЗОВАНИЕ СЛУЧАЙНЫХ БИТОВ В СЛУЧАЙНЫЕ ВЕЛИЧИНЫ
С ПРОИЗВОЛЬНЫМИ ДИСКРЕТНЫМИ РАСПРЕДЕЛЕНИЯМИ
Понятие оптимальности "в самом сильном смысле" и его следствия. Оптимальные ЦДР-алгоритмы с бесконечной сложностью. Фундаментальность энтропии как нижней границы сложности моделирования любого дискретного распределения. Процедура "уточнения" БДР-деревьев. Оптимальный алгоритм моделирования произвольного дискретного распределения.
4. СЛОЖНОСТЬ ТАБЛИЧНЫХ МЕТОДОВ МОДЕЛИРОВАНИЯ КОНЕЧНЫХ
ДИСКРЕТНЫХ РАСПРЕДЕЛЕНИЙ
Простейший табличный метод. Экстремальные границы сложности табличного метода Уолкера. Оптимальность табличного метода Марсальи.

5. СПЕЦИАЛЬНЫЕ АЛГОРИТМЫ МОДЕЛИРОВАНИЯ ЦЕЛОЧИСЛЕННЫХ
СЛУЧАЙНЫХ ВЕЛИЧИН
Биномиальное распределение. Распределение Бернулли. "Урезанное" геометрическое распределение. Дискретное равномерное распределение. Сложность моделирования целочисленных случайных величин.
ДОПОЛНЕНИЕ. НОВЫЕ ИДЕИ В МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ
РАСПРЕДЕЛЕНИЙ
Табличные методы моделирования конечных дискретных распределений. Альфа-, бета- и гамма-методы моделирования дискретного равномерного, биномиального и пуассоновского распределений. Моделирование отрицательного биномиального распределения методом отбора.
ЛИТЕРАТУРА

(од, >=^ а) • • • г{а-о ;л «;
где через обозначен логический оператор
^ _ [ А при ^ ~
1 V при <У- — Л
Для реализации преобразования (5.!) требуется ровно столько случайных битов и соответствующих логических операций, какова длина двоичного представления р (подчеркнем при этом существенность конечности данного представления).
Оказывается Сз] , что преобразование (5.1) может быть сведено к оптимальному алгоритму В из разд.'!, исходя из следующего обстоятельства.
Лем м а 8. Пусть случайные величины

г, г , .р
(если таких Ь нет, то ь полагается равной
считается, что (, ). Тогда случайные величины
тождественно равны. Доказательство проводится по индукции. При ^ “ А перебор всевозможных значений и
показывает, что случайная величина
'(<), А
у, 0 = И ’
<%4 рО) 1 0 ,