Тип работы:
Предмет:
Язык работы:


Статистические свойства некоторых процедур сжатия данных

Работа №137600

Тип работы

Дипломные работы, ВКР

Предмет

информатика

Объем работы50
Год сдачи2017
Стоимость4220 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
34
Не подходит работа?

Узнай цену на написание


Введение
Глава 1. Семейство «Book Stack»-подобных преобразований . . . . . . . 9
1.1. Описание общей схемы преобразования
1.2. Описание стандартного «Book Stack»-преобразования
Глава 2. «Book Stack»-тест при отклонении от независимости: однородная марковская цепь
2.1. «Стопка книг» как марковская цепь
2.2. Закон Больших Чисел для частот выходной последовательности . . . . . 20
2.3. Центральные Предельные Теоремы для частот входной и выходной последовательностей
2.4. Сравнение предельных распределений входной и выходной последовательностей
2.5. Статистические приложения
Глава 3. «Order»-преобразование и «Order»-тест
3.1. Описание преобразования
3.2. Свойства «Order»-теста
3.3. Связь между предельными свойствами входной и выходной последовательностей
Заключение
Список литературы

Рассмотрим нулевую гипотезу о независимости и равномерной распределенности
некоторого набора дискретных случайных величин, имеющих одинаковый носитель.
Эта стандартная статистическая задача возникает, в частности, при проверке свойств
генераторов псевдослучайных чисел (в дальнейшем — ГСЧ), которые используются повсеместно, начиная от решения задач с помощью метода Монте-Карло, вплоть до задач
криптографии. «Качество» ГСЧ, определяемое их статистическими свойствами, оказывает существенное влияние, например, на результаты применения метода Монте-Карло.
Для проверки этих свойств существует несколько батарей тестов, среди которых
наиболее известные: система, разработанная NIST [1], в основном предназначенная для
криптографических генераторов, система под названием «Die Hard» [2], а также достаточно развитая и подробно документированная батарея «TestU01» [3].
В 2004 году появилась статья [4], в которой рассматривается новый тест для проверки свойств ГСЧ, названный «Book Stack». В основе теста лежит одноименное преобразование, предложенное в 1980 году в статье [5], применение которого заключалось в
описании простой и наглядной процедуры сжатия информации. В англоязычной литературе более распространено название «Move-to-Front» [6]. Алгоритм приобрел достаточно широкую популярность и ныне используется в некоторых утилитах для сжатия
данных — в основном как один из промежуточных шагов (см., например, [7]). После
[4] было опубликовано еще несколько статей [8]–[15], так или иначе касающихся теста
«Book Stack». В статье [11] теми же авторами предложен другой тест для проверки
свойств ГСЧ, названный «Order»-тест.
Авторами было предложено использовать «Book Stack»- и «Order»-преобразования5
для проверки свойств ГСЧ. Стиль тестирования — побитовый, то есть рассматриваются отдельные двоичные биты (или их группы) псевдослучайных чисел, вырабатываемые ГСЧ, которые проверяются на равномерную распределенность на соответствующем множестве. Поэтому стандартным выбором � является некоторая степень двойки.
С формальной точки зрения проверяется гипотеза H0, заключающаяся в том, что
последовательность {��}�>1 является последовательностью независимых случайных величин, причем P(�� = �) = 1/� при 1 6 � 6 �. Проверка осуществляется с помощью
стандартного критерия �2, причем в случае больших � производится приемлемая группировка. Суть «Book Stack»- и «Order»-теста согласно статье [4], однако, состоит в том,
что критерий �2 применяется не к исходным случайным величинам {��}�>1, а к преобразованным {��}�>1, причем с той же степенью свободы. При этом утверждается, что
«более вероятные буквы будут в среднем иметь более высокие частоты встречаемости»
(см., например, [15]).
Таким образом, можно рассматривать два критерия: �2, примененный к исходному
набору {��}�>1, и �2 — к преобразованному с помощью «Book Stack» или «Order» набору
{��}�>1. Авторами неявно утверждается, что «Order»- и «Book Stack»-преобразования
увеличивают мощность критерия, хотя теоретические и экспериментальные результаты, подтверждающие этот факт, в названных статьях отсутствуют, равно как не обсуждается и выбор альтернатив, относительно которых мощность должна потенциально
увеличиваться. Более того, утверждается, что предложенные тесты улавливают отклонения от «случайности» даже для тех генераторов, которые выдерживают проверку
некоторыми лучше изученными и более распространенными тестами.
В [14] приводятся результаты применения «Book Stack»-теста к линейным конгруэнтным генераторам (в дальнейшем — ЛКГ), рекомендованным в [16]. Утверждается,
что это лучшие генераторы в классе ЛКГ, отбор происходил на основе так называемого спектрального теста (рассматривается в [17]). Каждый генератор, который был
рассмотрен, в итоге отвергнут при применении «Book Stack».
В [11] рассматриваются результаты применения «Order»-теста к ЛКГ. После двойного тестирования не отвергнут только один мультипликативный генератор со следующими параметрами: модуль = 18776556235061 и период = 248.
В [18] рассматриваются некоторые генераторы, которые рекомендуются для практического применения (например Вихрь Мерсенна [19], который один из немногих выдерживает проверку «Book Stack»-тестом). В [12] «Book Stack» применяется к криптографическим генераторам.
В литературе (например в [8], [9] и [10]) также присутствует обсуждение программных реализаций алгоритма. В частности, в [8] приводится ссылка на компьютерную реализацию с описанием функциональности и краткой документацией. Обзор эффективных реализаций «Book Stack»-преобразования, а также реализаций в открытом доступе
c описанием их достоинств и недостатков cм. в [20].
Со статистической точки зрения задача заключается в сравнении мощностей критерия �2, примененного к исходному набору {��}�>1, и �2 — к преобразованному с помощью «Book Stack»- или «Order»-преобразования набору {��}�>1. Для доказательства
корректности тестов необходимо доказать, что случайные величины {��}�>1 независимы
и равномерно распределены на множестве S тогда и только тогда, когда этими же свойствами обладают случайные величины {��}�>1. Поскольку в цитированных статьях доказательство этого факта (а также ссылка на него) отсутствует, для «Book Stack»-теста
доказательство было проведено в [20] и в [21]. Для «Order»-теста корректность следует
из результатов, полученных в данной работе (подробнее в Главе 3).
Нельзя говорить о cравнении мощностей критериев без выбора определенной альтернативной гипотезы. В рамках выпускной квалификационной работы бакалавра [20]
и в [21] для «Book Stack» теста было проведено исследование альтернативной гипотезы, заключающейся в том, что случайные величины {��}�>1 являются независимыми
и одинаково, но не равномерно, распределенными. Было показано, что относительно
такого выбора альтернативной гипотезы мощность критерия «после» преобразования
«Book Stack», как правило, является асимптотически меньшей, чем мощность критерия «до» преобразования. В [21] для проверки нулевой гипотезы H0 помимо критерия
�2 было предложено использовать критерий отношения правдоподобия. Удалось доказать, что относительно той же альтернативы мощность такого критерия «после» «Book
Stack»-преобразования всегда является асимптотически меньшей, чем мощность критерия «до». Доказательство основывается на соотношении предельных распределений
исходной последовательности {��}�>1 и преобразованной — {��}�>1.
Задачей данной работы является изучение поведения «Book Stack»-теста против
альтернативы, заключающейся в том, что исходные случайные величины {��}�>1 образуют эргодическую однородную марковскую цепь со стационарным равномерным рас7
пределением. Удается показать, что против такой альтернативы критерий �2 до преобразования «Book Stack» оказывается несостоятельным, в то время как при некоторых
ограничениях такой же критерий «после» преобразования является состоятельным. Заметим, что доказательство вновь основывается на сравнении предельных распределений
исходной последовательности {��}�>1 и преобразованной — {��}�>1.
В работе также получено обобщение «Book Stack»-преобразования, для которого сохраняются многие теоретико-вероятностные результаты. В предположении, что
исходные случайные величины {��}�>1 образуют однородную марковскую цепь, удовлетворяющую некоторым свойствам, доказано наличие предельного распределения у преобразованных случайных величин {��}�>1, сходимость частот к которому обеспечивается
Законом Больших Чисел. Более того, доказана Центральная Предельная Теорема для
частот исходных и преобразованных случайных величин. Для (стандартного) «Book
Stack»-преобразования такие результаты получены в предположении эргодичности марковской цепи {��}�>1. Для обобщений «Book Stack»-преобразования те же результаты
получены при положительности всех переходных вероятностей марковской цепи {��}�>1.
В работе также изучаются свойства «Order»-теста. Удается доказать, что для
любого критерия для проверки H0, такого что его статистика зависит только от частот выборки и инвариантна относительно их перестановок, статистики «до» и «после»
«Order»-преобразования совпадают. С связи с этим применение «Order»-теста против
любой альтернативной гипотезы вряд ли является оправданным.
Общая структура работы следующая. В Главе 1 приводится описание семейства
преобразований, являющихся обобщением преобразования «Book Stack», а также вводятся основные обозначения. В Главе 2 рассматривается ситуация, состоящая в том, что
входная последовательность {��}�>1 образует однородную марковскую цепь: в разделе
2.1 дано описание преобразования всей «стопки книг» марковской цепью, в разделе 2.2
найдено стационарное распределение выходной последовательности {��}�>1, сходимость
к которому обеспечивается Законом Больших Чисел, в разделе 2.3 рассматриваются результаты, относящиеся к ЦПТ частот «входной» и «выходной» последовательности, а в
разделе 2.4 производится сравнение предельных распределений входной и выходной последовательности. В Главе 3 рассматривается «Order»-преобразование и «Order»-тест:
в разделе 3.1 приводится описание лежащего в основе теста «Order»-преобразования,
а также вводятся основные обозначения, в разделе 3.2 обоснована бесперспективность8
применения «Order»-теста, в разделе 3.3 произведено сравнение предельных распределений частот «входной» и «выходной» последовательностей

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!


В работе рассмотрены статистические тесты «Book Stack» и «Order» для проверки нулевой гипотезы о независимости и равномерной распределенности некоторого набора дискретных случайных величин, имеющих одинаковый носитель. В основе этих
тестов лежат соответственно «Book Stack»- и «Order»-преобразования. На вход преобразованиям подается набор дискретных случайных величин {��}�>1, принимающих
значения на множестве {1, 2, . . . , �}. Результатом применения преобразований является набор дискретных случайных величин {��}�>1. Нулевая гипотеза заключается в проверке независимости и равномерной распределенности набора дискретных случайных
величин {��}�>1. Согласно описанию тестов, основанных на преобразованиях, критерий
�2 применяется не к исходному набору {��}�>1, а к {��}�>1.
В работе теоретически показано, что при выборе альтернативной гипотезы, заключающейся в том, что входная последовательность {��}�>1 образует эргодическую однородную марковскую цепь, выходная последовательность, полученная с помощью «Book
Stack»-преобразования, {��}�>1 тоже имеет некоторое стационарное распределение, сходимость к которому обеспечена Законом Больших Чисел. Более того, показано, что в
таких предположениях выполняется и Центральная Предельная Теорема для частот.
В работе получено обобщение «Book Stack» преобразования. Для такого обобщения
те же теоретико-вероятностные результаты получены в предположении положительности всех вероятностей перехода «входной» однородной марковской цепи {��}�>1.
Для стандартного «Book Stack» преобразования в рамках той же альтернативы
произведено сравнение предельных распределений «входной» и «выходной» последовательности. Показано, что в случае, если стационарное распределение «входной» ЭОМЦ
является равномерным, то для очень широкого класса входных ЭОМЦ стационарное
распределение «выходной» последовательности будет отличным от равномерного.
Именно поэтому при выборе в качестве альтернативной гипотезы, состоящей в том,
что «входные» случайные величины {��}�>1 образуют эргодическую однородную марковскую цепь со стационарным равномерным распределением и матрицей переходных
вероятностей, след которой отличен от 1, применение «Book Stack»-теста оказывается
оправданным. Более того, применение этого теста может быть целесообразно и в рамках
других альтернатив, связанных с зависимостью {��}�>1.48
В работе также теоретически показано, что для «Order»-преобразования статистики любого статистического критерия для проверки гипотезы H0, которые определяются
только частотами выборки и инвариантны относительно их перестановок, посчитанные
по «входной» последовательности {��}� �=1 и «выходной» {��}� �=1 совпадают. Именно поэтому применение «Order»-теста вряд ли является целесообразным.
Таким образом, наиболее продуктивным представляется дальнейшее изучение поведения «Book Stack»-теста (и различных его обобщений) против различных альтернатив, связанных с зависимостью «входной» последовательности {��}�>1.


1. Rukhin A., Solo J., Nechvatal J. et al. — A Statistical Test Suite for Random and
Pseudorandom Number Generators for Cryptographic Applications. — National Institute
of Standards and Technology, 2010.
2. Marsaglia G. Diehard battery of tests of randomness. — 1995.
3. L’Ecuyer P., Simard R. TestU01: A C Library for Empirical Testing of Random Number
Generators // ACM Trans. Math. Softw. — 2007. — aug. — Vol. 33, no. 4.
4. Ryabko B., Pestunov A. “Book stack” as a new statistical test for random numbers. //
Probl. Inf. Transm. — 2004. — Vol. 40, no. 1. — P. 66–71.
5. Рябко Б. Я. Сжатие информации с помощью стопки книг // Проблемы передачи
информации. — 1980. — Т. 16. — С. 16–21.
6. A Locally Adaptive Data Compression Scheme / Jon Louis Bentley, Daniel D. Sleator,
Robert E. Tarjan, Victor K. Wei // Commun. ACM. — 1986. — apr. — Vol. 29, no. 4.
7. Seward J. — bzip2 and libbzip2, version 1.0.5: A program and library for
datacompression, 2007. — Accessed: 17.05.2017. URL: http://www.bzip.org/1.0.5/
bzip2-manual-1.0.5.pdf.
8. Doroshenko S., Fionov A., Lubkin A. On ZK-crypt, Book Stack, and Statistical Tests //
IACR Cryptology ePrint Archive. — 2006.
9. Doroshenko S., Ryabko B. The experimental distinguishing attack on RC4. — 2006.
10. Ryabko B. Y., Monarev V. A. Using information theory approach to randomness
testing // Statistical Planning and Inference. — 2005. — Vol. 133. — P. 95–110.
11. Монарев В. А., Рябко Б. Я. Экспериментальный анализ генераторов псевдослучайных чисел при помощи нового статистического теста // ЖВМ и МФ. — 2004. —
Т. 44, № 5. — С. 812–816.
12. Ryabko В., Monarev V., Shokin Y. A new test for randomness and its application to
some cryptographic problems // Statistical Planning and Inference. — 2004. — Vol. 123,
no. 2. — P. 365–376.
13. Рябко Б. Я., Монарев B. A., Шохин Ю. И. Новый класс статистических тестов для
случайных чисел и его применение в задачах криптографии. — 2005. — С. 211–220.
14. Рябко Б. Я., Пестунов А. И. «Стопка книг» как новый статистический тест для случайных чисел // Проблемы передачи иформации. — 2004. — Т. 40, № 1. — С. 73–78.50
15. Монарев В. А., Рябко Б. Я. Экспериментальный анализ генераторов псевдослучайных чисел при помощи нового статистического теста // Журнал вычислительной
математики и математической физики. — 2004. — Vol. 44, no. 5. — P. 812–816.
16. L’Ecuyer P. Tables of linear congruential generators of different sizes and good lattice
structure // Mathematics of Computation. — 1999. — Vol. 68. — P. 249–260.
17. Кнут Д. Э. Искусство программирования. — Издат. дом «Вилиамс», 2001. — Т. 2.
Получисленные алгоритмы. — 832 с.
18. Using Universal Coding Approach to Randomness Testing / Ed. by В. Ryabko,
V. Monarev, Yu. Shokin. — International Symposium on Information Theory, 2004.
19. Matsumoto M., Nishimura T. Mersenne twister: A 623-dimensionally equidistributed
uniform pseudo-random number generator // ACM Trans. Model. Comput. Simul. —
1998. — jan. — Vol. 8, no. 1. — P. 3–30.
20. Бзикадзе A. B. Некоторые Свойства Статистического Теста Book Stack : Бакалаврская Выпускная Квалификационная Работа / A. B. Бзикадзе ; Санкт-Петербургский Государственный Университет. — 2015.
21. Bzikadze A. V., Nekrutkin V. V. On some statistical properties of the “book stack”
transformation // Vestnik St. Petersburg University: Mathematics. — 2016. — Vol. 49,
no. 4. — P. 305–312. — URL: http://dx.doi.org/10.3103/S106345411604004X.
22. Ширяев А. Вероятность-1. — Изд-во МЦНМО, 2011. — ISBN: 9785940577522.
23. Сираждинов С., Форманов Ш. Предельные теоремы для сумм случайных векторов,
связанных в цепь Маркова. — Изд-во «Фан» Узбекской ССР, 1979.
24. Ширяев А. Вероятность-2. — Изд-во МЦНМО, 2011.
25. Боровков А. Теория вероятностей. — Изд-во «Наука», 1986.
26. Кельберт М. Я., Сухов Ю. М. Вероятность и статистика в задачах. — МЦНМО,
2009. — Т. 2, Марковские цепи как отправная точка теории случайных процессов и
их приложения.
27. Tavare S., Altham P. Serial dependence of observations leading to contingency tables,
and correctionts to chi-squared statistics // Biometrika. — 1983. — Vol. 70, no. 1. —
P. 139–44

Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ