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