Введение
Глава 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