Быстрые алгоритмы решения задачи фон Неймана-Элайеса и ее обобщений

• Автор: Мачикина, Елена Павловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Новосибирск
• Количество страниц: 76 с.

Оглавление
ВВЕДЕНИЕ
Глава 1. Обзор известных методов получения случайных величин с заданным распределением
1.1. Введение
1.2. Основные определения и понятия
1.3. Основные методы для задачи фон Неймана-Элайеса .
1.3.1. Метод фон Неймана
1.3.2. Метод Элайеса
1.3.3. Метод Переса
1.4. Методы получения случайных величин с заданным распределением вероятностей
Выводы
Глава 2. Быстрый и эффективный метод преобразования произвольных случайных величин в равновероятные и независимые
2.1. Введение
2.2. Описание быстрого алгоритма
2.3. Основные свойства метода

2.4. Применение метода для недвоичных источников
2.5. Обобщение метода для марковских источников
2.6. Сравнение с другими методами
Выводы
Глава 3. Эффективный метод генерации равномерно распределенных случайных величин с заданной погрешностью
3.1. Введение
3.2. Основные определения и постановка задачи
3.3. Генерация почти равномерного распределения в случае известной статистики источника
3.4. Случай неизвестной статистики источника
3.5. Применение метода в случае марковского источника
Выводы
Глава 4. Быстрый метод генерации случайных величин с распределением вероятностей на цепных дробях
4.1. Введение
4.2. Описание алгоритма и его свойства
4.3. Быстрый метод генерации случайных величин с заданным распределением вероятностей на коэффициентах цепных дробей
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
Актуальность темы
Задача построения эффективных методов получения случайных величин изучается многими исследователями в силу своей теоретической важности для дискретной математики, криптографии, информатики, теории сложности, а также высокой практической значимости при применении в системах защиты информации, численных методах и целом ряде других областей.
Методы получения случайных величин можно условно разбить на две группы. Первую группу составляют методы, которые позволяют генерировать последовательности равномерно распределенных независимых (“идеальных”) случайных величин. Методы генерации случайных величин с заранее заданным (неравномерным) распределением вероятностей образуют вторую группу. В частности, представляет интерес задача генерации вероятностных распределений, задаваемых на числах, представленных цепными дробями, впервые рассмотренная Д. Кнутом и А. Яо (D. Knuth, A. Yao).
Методы генерации случайных величин разрабатывались и изучались в работах Дж. фон Неймана (J. von Neumann), П. Элайеса (Р. Elias), М. Блюма (М. Blum), Д. Кнута (D. Knuth), Й. Переса (Y. Peres),

Положим теперь 5 = £(г0,...,Г|А|_1) для некоторого вектора И = (По,, Тщ_{) и найдем выражения для величин из (2.21), (2.22). Мощность множества А — £(:т0г„1тр,|_1) задается следующей формулой

Пусть СЛОВО Х1Х2-.-ХМ принадлежит множеству £(Т0,...,Т|А|_1) • Вычислим величину р(х 1). Пусть для определенности Х = к, к = О,..., А — 1. Тогда
, , (ЛГ-1)! (То)!... (Дц)!
Р(1> (То)!... (I). — 1)!(7]/1|_1)! №
После упрощений получаем, что р(хф) — Тк/1V или
р(х1) = ТХк/М. (2.23)
Посчитаем теперь А^ац ... ад), А: = 1,..., N. Пусть £;(#! ... ж*) число вхождений символа г в подслово ад • • • г = 0,1,..., |А| — 1, к =
1,..., N. Тогда
_______________________(IV — к)
5 Х1"'Хк (По — £о(ж1 ■ • • Хк) ■ • • (Та-1 ~ ЬА-1{хг ...хк)! Найдем выражения для £г-(ац... ж*), г = 0,1,..., А — 1, к — 1,..., N.
Пусть для определенности ад- = в. Тогда
£,•(Жх... ад_х) + 1, если г = в;
£,(жх... ж*_х), если г ф в.
• • - ад) ■
После сокращений имеем
рЩМ = Г> = Г*‘(2.24)
Величины д(ац), д(ад/ац.. . ад_х) подсчитываются согласно (2.22) и ме-ют следующий вид

Я(Х1) = 2^-, (2.25)