Сложность и оптимальные алгоритмы моделирования дискретных распределений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

Результаты диссертации лежат в основе метода Монте-Карло и имеют первостепенное значение при решении естественнонаучных задач методами статистического моделирования.

ОГЛАВЛЕНИЕ

Как отмечается в известной монографии М.Ермакова [-I] , Э1, "моделирование случайных величин..., которое является основньм содержанием метода Монте-Карло, предполагает возможность их конструирования при помощи некоторого сл^щайного механизма".При традиционном подходе к моделированию случайные величины с неравномерныгш законами распределения выражаются через равномерно распределенные в интервале (0,<[) случайные величины, которые, в свою очередь, могут быть заданы конструктивно, например, отождествляя их двоичные знаки с исходами подбрасывания симметричной монеты.В диссертации развивается предложенный в недавно переведенной на русский язык работе Д.Кн^та и Э.Яо |22] новый подход, заключающийся в непосредственном преобразовании с л у ч а й н ы х б и т о в (исходов подбрасывания симметричной монеты) в случайные величины с неравномерными распределениями. Предложенная Кнутом и Яо модель такого преобразования позволяет не только строго обосновать остающиеся в рамках традиционного подхода весьма неопределенными такие понятия, как "трудоемкость" (сложность) алгоритмов, их "эффективность" (оптимальность) и т.п., но и построить алгоритмы, достигающие теоретические границы сложности моделирования любого вероятностного распределения. Ограничение в диссертации дискретными распределениями позволяет дать достаточно замкнутое и вполне законченное рассмотрение этого важного для приложений случая. При этом в дополнение к пионерской работе Кнута и Яо, в которой основной акцент сделан на принципиальные вопросы сложности: моделирования вероятностных распределений, настоящая работа характеризуется своей алгоритмической направленностью и включает в себя изложение алгоритмов, имеющих натленьшую сложность.Данные алгоритмы основаны на фундаментальной работе Кнута и Яо, необходимые сведения из которой приводятся в требуемой для наших целей форме и дополняются следующими теоретическими результатагли по сложности моделирования дискретных распределений.Введенное в работе Кнута и Яо понятие ДЦР-дерева, как модели преобразования случайных битов в случайные величины с дискретны1Ш распределенияьш, порождает следующий вопрос: а для всех ли распределений существуют подобные деревья? В диссертации утверждается, что ЦЦР-деревья, включая и оптимальные, могут быть построены для любого дискретного распределения. Более того, результатом проведенного доказательства этого утверждения являются установленные более сложным путем в работе Кнута и Яо условие оптимальности ЦЦР-деревьев и нижняя граница среднего числа случайных битов, необходщшх для выполнения ДЦР-алгоритмов для данного распределения.Далее, в работе Кнута и Яо показано, что последняя величина, как мера сложности моделирования любого дискретного распределения, не более чем на 2 единицы превышает его энтропию. Оказывается, что соответствующая "избыточность" представляет собой среднее значение энтропии (условных) распределений вероятностей достижения из корня оптимального ЦДР-дерева концевых узлов, помеченных одним и тем же значением моделируемой сл^'чайной величины, для которой имеет место оценка Кнута и Яо.В диссертации установлены точные верхние и нижние границы сложности оптимальных ДДР-алгоритмов для конечных дискретных распределений, при этом рассмотрение вероятностей, представленных как конечный^, так и бесконечньм числом двоичных знаков, естественным образом расширяет соответствующий результат Кнута и Яо.В связи с установленными экстремальньшш границами сложности оптимальных ЦЦР-алгоритмов возникает следующий вопрос. Нельзя ли указать алгоритм моделирован1'1я произвольного дискретного распределения, который не являясь в общем случае оптимальным, имеет сложность, не превосходящую верхнюю границу сложности оптимальных алгоритмов? Оказывается, что шжно,и самое интересное состоит в том, что подобньм алгоритмом является не специально построенный для этой цели алгоритм, а "битовый" вариант наиболее привлекательного в практическом отношении метода для моделирования случайных величин, принимающих конечное число значений как с двоично рациональными, так и с "двоично иррациональньили" вероятностяьш. Более того, в диссертации показано, что среди традиционных методов моделирования дискретных распределений с;у'ществует алгоритм (точнее, может быть сведен к таковому), который достигает нижнюю границ^ '- сложности ГЩР-алгоритмов для случайных величин, принимающих конечное число значений с двоично рациональными вероятностями.Согласно установленной в диссертации энтропийной мере сложности моделирования дискретных распределений, энтропия, как фундаментальная ншсняя граница сложности ЦДР-алгоритмов,в общем случае не достигается (при этом в диссертации получена характеризация распределений вероятностей, сложность моделирования которых совпадает с их энтропией). Тем не менее в диссертации показано, что существует такой способ моделирования любого дискретного распределения, который позволяет сколь угодно близко подойти к этому теоретическому пределу. ©орма изложения материала такова, что в рамках кавдого отдельного раздела приводятся только те сведения, которые действительно необходимы для решения задачи, вынесенной в его заголовок.Поскольку оптимальные "битовые" алгоритмы представляют, повидимому, больше теоретический, нежели практический интерес, диссертация дополнена рассмотрением традиционного подхода к моделированию дискретных распределений с з^ором на новые результаты, пол^^енные автором диссертащад. Здесь в той или иной степени затронуты практически все известные к настоящему времени традиционные методы моделирования дискретных распределений. Дополнительный материал тесно связан с основной частью диссертации в том смысле, что ряд изложенных традиционных методов моделирования II представляет интерес не только с практической, но и со сложностной точек зрения. Это, в частности, касается "табличных" методов моделирования дискретных распределений, сложностному анализу которых посвящен отдельный раздел основной части диссертации, и так называемых "бета-методов" моделирования биномиального распределения, один из которых южет быть сведен к оптимальному (по крайней мере, по порядку) битовому алгоритму моделирования данного распределения. Обратно, сложностной анализ традиционных алгоритмов моделирования указывает пути модификации последних с целью существенного улучшения их характеристик.Что касается оптимальности (где оптимальность понимается в том сьлысле, что среди всех пригодных для этой цели алгоритмов алгоритм В требует в среднем наименьшего числа случайных битов, когда усреднение проводится по всевозможным их последовательностям) , то данный факт по существу вытекает из оптимальности используемого в нем правила моделирования распределения (1.2). Ниже будет показано, что каково бы ни было распределение вероятностей, среднее число случайных битов, необходимых для его моделирования, не меньше энтропии моделируемого распределения и эта граница (равная в данном случае ) достигается алгоритмом i b на распределении (€.2).Рассмотренный пример показывает, что в ряде случаев традиционные методы моделирования могут быть сведены к оптимальньм алгоритмам, преобразующим случайные биты в случайные величины с соответств^пощими распределениями. Однако подобные примеры скорее являются исключением, нежели правилом, что требует введения некоторой общей модели преобразования случайных битов в дискретные случайные величины, в рамках которой можно корректно поставить задачу оценки сложности моделирования с последующим построением алгоритмов, имеющих наименьшую сложность.

1. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1975, 472с.

2. К нут Д., Я о Э. Сложность моделирования неравномерных распределений. Кибернетич.сб., нов.сер., вып.19, М.: Мир, 1983, с.97-158.

3. Походзей Б.Б. Оптимальный; метод моделирования распределения Бернулли. Изв.АН СССР. Техн.киберн., 1982,I, с.207-208.

4. Походзей Б.Б. Преобразование случайных битов в случайные величины с конечными дискретными распределениями. -Вестник Ленингр.ун-та, 1983, вып.З, № J3, с.31-36.

5. Martin N.F.G., England J.W. Mathematical theory of entropy. Reading: Addison -Wesley, 1981, 257 P«

6. Маршалл А.,0лкин И. Неравенства: теория мажо-ризации и ее приложения. М.: Мир, 1983 , 576с.

7. Походзей Б.Б. Табличные методы моделирования дискретных распределений. Л5|урн.вычисл.матем.и матем.физ, э 1983, т.23, № 2, с.483-488.

8. Walker A.J. An efficient method for generating discrete random variables with given distributions. ACM Trans. Math. Software, 1977, v. 3, N 3, p.253-256.

9. M a r s a g 1 i a G. Generating discrete random variables in a computer. Communs ACM,1963» v.6, IT 1,p.37-38.

10. Походзей Б.Б, Об оптимальности метода Марсальи для моделирования дискретных распределений. Вестник Ленингр. ун-та, 1983, вып.4, № 19, с.105-107.

11. Е р м а к о в С.М., Походзей Б.Б. Методы моделирования дискретных случайных величин, основанные на рандомизации параметров распределений. Журн.вычисл.матем. и матем.физ., 198I, т.21, № 5, с.1323-1326.

12. П о х о д з е й Б.Б. Преобразование "случайных битов в биномиально распределенные случайные величины. Вестник Ленингр.ун-та, 1983, вып.2, № 7, с.37-40.

13. Ahrens J.H.DieterU. Computer method for sampling from gamma,beta,Pcisson and binominal distributions. Computing, 1974-, v.12, N 3, p.223-246,

14. П о л л я к Ю.Г. 0 моделировании случайных величин, связанных со схемой независимых испытаний. Изв.АН СССР, Техн.киберн., 1968, № I, с.201-202.

15. К н у т Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М.: Мир, 1977, 724с.

16. W а 1 k е г А • New fast method for generating discrete random numbers with arbitrary frequency distributions. -Ele-ctron.Lett. ,1974-, v. 10,N 8, p.127-128.

17. Chen H.-C.,A s a .и Y. On generating random variables from an empirical distribution.- Amer.Inst.Industr. Engnrs. Trans.,1974» v.6, N 2, p.163-166.

18. Cheng R.C.H. The generation of gamma variables with nonintegral shape parameters. Appl. Statist., 1977,v. 26, N 1, p. 71-75.

19. Походзей Б.Б. Составной метод моделирования распределения Пуассона. Журн.вычисл.матем.и матем.физ., 1979,т.19, № 5, с.1327-1329.

20. Походзей Ё.Б. Бета- и гамма-методы моделирования биномиального и пуассоновского распределений. Журн.вычисл. матем.и матем.физ., 1984, т.24, № 2, с.187-193.