Быстрые алгоритмы решения задачи фон Неймана-Элайеса и ее обобщений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

Глава 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. Применение метода в случае марковского источника . . 52 Выводы.

Глава 4. Быстрый метод генерации случайных величин с распределением вероятностей на цепных дробях

4.1. Введение

4.2. Описание алгоритма и его свойства.

4.3. Быстрый метод генерации случайных величин с заданным распределением вероятностей на коэффициентах цепных дробей.

Выводы.

Актуальность темы

Задача построения эффективных методов получения случайных величин изучается многими исследователями в силу своей теоретической важности для дискретной математики, криптографии, информатики, теории сложности, а также высокой практической значимости при применении в системах защиты информации, численных методах и целом ряде других областей.

Методы получения случайных величин можно условно разбить на две группы. Первую группу составляют методы, которые позволяют генерировать последовательности равномерно распределенных независимых ("идеальных") случайных величин. Методы генерации случайных величин с заранее заданным (неравномерным) распределением вероятностей образуют вторую группу. В частности, представляет интерес задача генерации вероятностных распределений, задаваемых на числах, представленных цепными дробями, впервые рассмотренная Д. Кнутом и А. Яо (D. Knuth, A. Yao).

Методы генерации случайных величин разрабатывались и изучались в работах Дж. фон Неймана (J. von Neumann), П. Элайеса (Р. Elias), М. Блюма (М. Blum), Д. Кнута (D. Knuth), Й. Переса (Y. Peres),

Б. Я. Рябко, А. П. Фионова, С. Верду (S. Verdu) и многих других исследователей как у нас в стране, так и за рубежом.

Существует несколько естественных постановок задачи и требований к алгоритмам. При первой постановке задачи предполагается, что входом является последовательность случайных величин, порожденных некоторым источником информации, которая преобразуется (или кодируется) в последовательность случайных величин с равномерным (для задачи фон Неймана-Элайеса) или заранее заданным вероятностным распределением (для задачи Кнута-Яо и других обобщений задачи фон Неймана-Элайеса). Рассматриваются две естественные постановки задачи получения случайных величин: точная и приближенная. Точные методы позволяют генерировать случайные величины с заранее заданным вероятностным распределением. Приближенные методы дают возможность получить выходную последовательность мало отличающуюся (с некоторой наперед заданной погрешностью) от последовательности с заданным распределением. Кроме того, задача получения случайных величин рассматривается для источников как с известной, так и с неизвестной статистикой.

Наряду с описанной постановкой задачи фон Неймана-Элайеса существуют и другие подходы к моделированию случайных величин и случайных прцессов. Подход, связанный с разработкой так называемых экстракторов, позволяет получать почти "идеальные" случайные биты из последовательности, порожденной неизвестным низкоэн-тронийным источником, причем к входной последовательности под мешиваются "идеальные" случайные биты. Так как при этом входная последовательность расходуется неэффективно, то данный подход не рассматривается в диссертации. Среди исследователей, изучающих экстракторы можно назвать Н. Нисана (N. Nisan), А. Та-Шма (А. Та-Shma), М. Санта (М. Santha), У.В. Вазирани (U. V. Vazirani) и других. Кроме того имеются работы, в которых изучаются различные аспекты существования преобразователей случайных величин. К ним можно отнести работы Р. М. Колпакова, Р. Г. Бухараева и других.

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

Известные до недавнего времени методы получения случайных величин были весьма трудоемкими с вычислительной точки зрения. Для достижения произвольно низких избыточности и (или) погрешности эти методы требовали экспоненциально растущего объема памяти (или

СЧ 1fw ТТ /"Ч TTATTTTTTf^ ТТТ ТТА Г\ Г\ /-1ГПТ ГТТТАП А ППАА f ЛТТТТ А^ГЧ Л ^ Г\ ТТ/" Т Т АШТАТЛА TTTt АПА ЛТТЛ Т il W11 л-\к±(ли> 1 W j^Ct'V j. j 1ЦУ1 \j J> Villi VV/ Cif W ± IVITI U^liVl vs JL>/Y v/l^l J-Vi w WirilVJ. вола).

Цель работы

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

Задачи исследования

Для достижения указанных целей в рамках диссертационной работы решаются следующие задачи.

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

2. Построение эффективных методов получения равновероятностных и независимых случайных величин с заданной погрешностью для источников с известной и неизвестной статистикой.

3. Построение быстрого метода получения случайных величин с бернуллиевским распределением на коэффициентах цепных дробей.

4. Построение быстрого метода перевода цепных дробей в обыкновенные.

Методы исследования

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

Научная новизна результатов работы

1. Разработан метод получения равновероятных и независимых двоичных случайных величин (задачи фон Неймана-Элайеса), обеспечивающий произвольно низкую избыточность при неэкспоненциальном росте времени кодирования. Данный метод является универсальным, т. е. не требует знания статистики источника входных символов.

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

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

Основные положения, выносимые на защиту

1. Для задачи фон Неймана-Элайеса разработан метод, обеспечивающий произвольно низкую избыточность и требующий логарифмического роста времени обработки одного входного символа.

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

3. Разработан быстрый метод получения случайных величин с задаваемым бернуллиевским распределением на коэффициентах цепных дробей.

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

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

Основные выводы

1. Для объема памяти генератора М и времени вычисления Т разработанного метода получения равновероятностных и независимых случайных величин (задача фон Неймана-Элайеса) справедливы соотношения:

Т = 0(log3 N log log N), M = 0(N log2 N), где N — длина блока.

2. Для задачи получения равномерно распределенных случайных величин с заданной погрешностью р в случае известной статистики источника построен метод с логарифмической вычислительной сложностью

Т = О (log - log log - log log log , \ p p p;

M = О (bg - j

P>

3. Для случая неизвестной статистики источника метод имеет следующие характеристики

11 1\

Т = О log - log log - log log log - , \ p p pj

Для уменьшения требуемого объема памяти применяется концепция мнимого скользящего окна, однако такой подход использует рандомизацию.

4. В случае марковского источника порядка р временная сложность метода остается прежней, а объем памяти увеличивается в раз, где s — мощность входного алфавита.

5. Сложность получения случайных величин с распределением на цепных дробях определяется сложностью перевода цепных дробей в обыкновенные.

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

ЗАКЛЮЧЕНИЕ

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Бабкин В.Ф. Метод универсального кодирования источника независимых сообщений неэкспоненциальной трудоемкости // Проблемы передачи информации 1971. Т. 7, вып. 4. С.13-21.

3. Биллингслей П. Эргодическая теория и информация. М.: Мир, 1969.

4. Бухараев Р. Г. Автоматная методология исследования случайных последовательностей // Математические вопросы кибернетики. Вып 8. 2000. С. 43-58.

5. Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.

6. Колпаков Р. М. Критерий порождения множеств рациональных вероятностей в классе булевых функций // Дискретный анализ и исследование операций. Сер. 1. Новосибирск: ИМ СОРАН, 1999. Т. 6. № 2. С 41-61.

7. Колпаков Р. М. О преобразовании булевых случайных величин // Математические вопросы кибернетики. Вып 8. 2000. С. 227-252.

8. Кричевский Р. Е. Оптимальное кодирование источника на основе наблюдений // Проблемы передачи информации 1975. Т. 11, вып. 4. С. 37-42.

9. Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.

10. Пинскер М.С. Информация и информационная устойчивость случайных величин и процессов // Проблемы передачи информации М.: Изд-во АНСССР, вып. 7. 203 с. I960.

11. Постников А.Г. Арифметическое моделирование случайных процессов. М.: Изд-во АНСССР, 1960. Труды математического института им. В. А. Стеклова, Т. 57.

12. Рябко Б.Я. Быстрая нумерация комбинаторных объектов // Дискретная математика. 1998. Т. 10, вып. 2. С. 101-119.

13. Рябко Б. Я. Быстрый алгоритм адаптивного кодирования // Проблемы передачи информации 1990. Т. 26, вып. 4. С. 24-37.

14. Рябко Б. Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения // Проблемы передачи информации 1995. Т. 31, вып. 1. С. 3-12.

15. Рябко Б. Я. Сжатие данных с помощью "мнимого скользящего окна" // Проблемы передачи информации 1996. Т. 32, вып. 2. С. 22-30.

16. Рябко Б. Я., Фионов А. Н. Быстрый метод полной рандомизации сообщений // Проблемы передачи информации 1997. Т. 33, вып. 3. С. 3-14.

17. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации 1999. Т.35, вып. 4. С. 95-108.

18. Чисар И., Кернер Я. Теория информации: Теоремы кодирования для дискретных источников без памяти. М.: Мир. 1985.

19. Фионов А.Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. Серия 1. 1997. Т. 4, № 2. С. 51-74.

20. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир, 1984.

21. Хинчин А.Я. Цепные дроби. М.: Мир, 1978.

22. Abrahams J. Generation of discrete distribution from biased coins // IEEE Trans. Inform. Theory. 1996. V. 42, № 5. P. 1541-1546.

23. Bell Т. C., Cieary J. G., Witten I. H. Text compression. Englewood Cliffs, NJ: Prentice Hall, Inc., 1990.

24. Blum M. Independent unbiased coin flips from a correlated biased source — a finite state Markov chain // Combinatorica. 1986. V. 6, №2. P. 97-108.

25. Cover T.M. Enumerative source encoding // IEEE Trans. Inform. Theory. 1973. V. 19, Ш 1. P. 73-77.

26. Davisson L.D. Comments on "Sequence time coding for Data compression" // Proc. IEEE. 1966. V.54, № 2. P. 2010.

27. Elias P. The efficient construction of an unbiased random sequence, // Ann. of Math. Statist. 1972. V. 43, № 3. P. 864-870.

28. Gray R.M., Neuhoff D.L., Shields P.C. A generalization of Ornstein's distance with applications to information theory // Ann. Probab. 1975. V. 3, P. 515-528.

29. Han T.S. Theorems on the variable length intristic randomness // IEEE Trans. Inform. Theory. 2000. V. 46, № 6. P. 2108-2117.

30. Han T.S. The reliability functions of the general source with fixed-length coding // IEEE Trans. Inform. Theory. 2000. V. 46, № 6. P. 2117-2133.

31. Han S., Hoshi M. Interval algorithm for random number generation // IEEE Trans. Inform. Theory. 1997. V. 43, № 2. P. 599-611.

32. Han S., Verdii S. Approximation theory of output statistics / / IEEE Trans. Inform. Theory. 1993. V. 39, W 3. P. 752-772.

33. Hoeffing W., Simons G. Unbiased coin tossing with a biased coin, // Ann. Math. Stat. 1970. V. 41, № 2. P. 341-352.

34. Jeiinek F. Probabilistic information theory. New York: McGraw-Hill, 1968.

35. Juels A., Jakobsson M., Shriver Б., Hillyer B.K. How to turn loaded duce into fair coins // IEEE Trans. Inform. Theory. 2000. V. 46, № 3. P. 911-922.

36. Knuth D., Yao A. The complexity of nonuniform random number generation // Algorithms and complexity. Recent results and new directions., New York: Academic press, 1976. P. 357-428.

37. Nisan N., Ta-Shma A. Extracting randomness: Asurvey and new constructions // J. Comput. Syst. Sci. 1999. V. 58, № 1. P. 148-173.

38. Nisan N., Zuckerman D. Randomnessis linear in space // J. Comput. Syst. Sci. 1996. V. 52, № 1. P. 43-52.39. von Neumann J. Various techniques used in connection with random digits // J. Res. Nat. Bur. Stand. Appl. Math. Ser. 1951. V. 3, P. 3638.

39. Lynch T.Y. Sequence time coding for data compression // Proc. IEEE. 1966. V. 54, № 2. P. 2010.

40. Peres Y. Iterating von Neumann's procedure for extracting random bits // Ann. Statist. 1992. V.20, № 1. P. 590-597.

41. Rissanen J. J. Generalized Kraft inequality and arithmetic coding // IBM J. Res. and Dev. 1976. V. 20, № 5. P. 198-203.

42. Rissanen J. J., Langdon G. G. Arithmetic coding // IBM J. Res. and Dev. 1979. V. 23, № 2. P. 149-162.

43. Roche J.R. Efficient generation of random variables from biased coins // Proc. IEEE Int. Symp. on Information Theory (Budapest, Hungary, 1991.)

44. Ryabko B. Y. Fast and effective coding of information sources // IEEE Trans. Inform. Theory. 1994. V. 40, № 1. P. 96-99.

45. Samuelson P. A. Constructing an Unbiased Random Sequence //J. Amer. Statist. Assoc. 1968. V. 63, P. 1526-1527.

46. Santha M., Vazirani U. V. Generating quasi-random sequences from semi-random sources //J. Comput. Syst. Sci. 1986. V. 33, № 1. P. 75-87.

47. Steinberg Y., Verdia S. Simulation of random processes and rate-distortion theory // IEEE Trans. Inform. Theory. 1996. V. 42, №. 1. P. 63-86.

48. Stout Q.F., Warren B. Tree algorithms for unbiased coin tossing with a biased coin // Ann. Prob. 1984. V. 12, № 1. P. 212-222.

49. Vembu S., Verdu S. Generating random bits from arbitrary source: fundamental limits // IEEE Trans. Inform. Theory. 1995. V. 41, № 5. P. 1322-1332.

50. Visweswariah K., Kulkarni S.R., Verdu S. Separation of random number generation and resolvability // IEEE Trans. Inform. Theory. 2000. V. 46, № 6. P. 2237-2242.

51. Witten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Comm. of the Assoc. Сотр. Math. 1987. V. 30, № 6. P. 520-540.

52. Работы автора, в которых изложены основные результаты диссертации1. Статьи

53. Мачикина Е.П., Рябко Б.Я. Быстрый метод перевода цепных дробей в обыкновенные // Дискретная математика. 1999. Т. 11, вып. 4. С. 152-156.

54. Рябко Б.Я., Мачикина Е.П. Эффективное преобразование случайных последовательностей в равновероятностные и н езависи-мые // Проблемы передачи информации 1999. Т. 36, вып. 2. С. 23-28.

55. Рябко Б.Я., Мачикина Е.П. Эффективный метод генерации равномерно распределенных случайных чисел // Проблемы передачи информации 2002. Т. 38, вып. 1.

56. Ryabko В., Matchikina Е. Fast and efficient construction for unbiased random sequence // IEEE Trans. Inform. Theory. 2000. V. 46, № 3. P. 1090-1093.1. Доклады на конференциях

57. Ryabko В., Matchikina Е. Fast and efficient method of constructing an unbiased random sequence // Международная Сибирская конференция по исследованию операций. Материалы конференции, Новосибирск: Изд-во Ин-та математики СО РАН, 1998. С. 150.

58. Ryabko В., Matchikina Е. Fast and efficient construction of an unbiased random sequence // Proceeding of the International Symposium on Information Theory, 1999, Cambridge, USA, August 16-21. P. 815.

59. Ryabko В., Matchikina E. Efficient methods for generating approximately equiprobable random bits / / Proceeding of the International Symposium on Information Theory, 2002, Lausanne, Switzerland, June 30-July 5. P. 912.