ISSN 1991-3087

Свидетельство о регистрации СМИ: ПИ № ФС77-24978 от 05.07.2006 г.

ISSN 1991-3087

Подписной индекс №42457

Периодичность - 1 раз в месяц.

Вид обложки

Адрес редакции: 305008, г.Курск, Бурцевский проезд, д.7.

Тел.: 8-910-740-44-28

E-mail: jurnal@jurnal.org

Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

Статистические критерии для оценки энтропии

 

Ставер Елена Владимировна,

магистрант физико-математических наук.

Научно-образовательный центр «Современные системы обучения».

 

Моя основная цель – получить случайную последовательность. Можно сделать период последовательности длинным и при практических применениях он не будет повторяться [1]. Это важный критерий, но нет гарантии того, что последовательность будет использоваться в реальных приложениях.

Теоретическая статистика предоставляет количественные меры случайности. Существует теоретически бесконечное число критериев, которые можно использовать для проверки последовательности на случайность.

Если критерии T1, T2,…Tn подтверждают, что последовательность ведет себя случайным образом, это еще не означает, что проверка Tn+1-го критерия будет успешной [1]. Но каждая успешная проверка дает все больше уверенности в случайности последовательности. Обычно к последовательности применяется множество статистических критериев, и если она удовлетворяет этим критериям, то последовательность считается случайной.

 

Критерий на равномерное распределение

Этот критерий является важным методом проверки качества линейных конгруэнтных ГСЧ [1]. Испытанием для проверки случайности будет последовательность, связанная со свойствами распределений t последовательных элементов последовательности. Если задана последовательность Un с периодом m, то для построения критерия необходимо изучить множество всех m точек

{(Un,Un+1, … Un+t-1) | 0 ≤n≤m}                                                                                (1)

в t-мерном пространстве. Задана линейная конгруэнтная последовательность {Хо,а,с,m) с максимальным периодом длиной. В последнем случае прибавляется точка (0, 0, ...,0) к множеству (1), чтобы всегда было ровно m точек. При таком предположении (1) переписываем выражение:

                                                   (2)

Представляет собой элемент, следующий за x. Здесь рассматривается лишь множество всех таких точек в t-мерном пространстве, а не порядок, в котором они генерируются.

 

Критерий перестановок

Выборка является равномерно распределенной, после перемешивания она должна удовлетворять начальным критериям. Ожидается, что первоначальная оценка результатов будет основываться на «перемешанных» выборках, так как результаты, полученные на оригинальной выборке, либо необычайно высоки, либо низки, т.е. являются неточными [1]. Если выборка не является равномерно распределенной, то некоторые оценочные результаты могут сильно отличаться на оригинальной и «перемешанной» выборке.

 

Проверка по критерию «хи-квадрат»

Критерий «хи-квадрат» — является важным методом, который используется наряду с другими критериями. Для моего случая проверка по данному критерию позволяет узнать, насколько созданный мной реальный ГСЧ будет удовлетворять требованию равномерного распределения [1].

Частотная диаграмма реального ГСЧ представлена на рисунке 1. Закон распределения эталонного ГСЧ равномерный, то вероятность pi попадания чисел в i-ый интервал равна pi = 1/k. В каждый из k интервалов попадет ровно по pi · N чисел.

 

Рис. 1. Частотная диаграмма реального ГСЧ.

 

Реальный ГСЧ будет генерировать числа, распределенные по k интервалам, и в интервал попадет по ni чисел [1]. Нужно рассмотреть квадраты разностей между полученным количеством чисел ni и «эталонным» pi · N. Слаживая их, в результате получим:

 χ2эксп. = (n1 – p1 · N)2 + (n2 – p2 · N)2 + … + (nk – pk · N)2.

Чем меньше разность в каждом из слагаемых, тем сильнее закон распределения случайных чисел, генерируемых реальным ГСЧ, тяготеет к равномерному [1]. В предыдущем выражении каждому из слагаемых приписывается одинаковый вес; для статистики «хи-квадрат» необходимо провести нормировку каждого i-го слагаемого, поделив его на pi · N:

 Описание: [ Формула 06 ]

Наконец, полученное выражение более компактное уравнение:

 Описание: [ Формула 07 ]

Так можно получить значение критерия «хи-квадрат» для экспериментальных данных.

Приемлемым считают p от 10% до 90%.

Если χ2эксп. больше χ2теор., то генератор не удовлетворяет требованию равномерного распределения, так как полученные значения ni очень отличаются от теоретически допустимых pi · N и не могут рассматриваться как случайные [1]. Устанавливается большой доверительный интервал, в котором ограничения на числа становятся очень нежесткими, требования к числам — слабыми. При этом будет наблюдаться очень большая абсолютная погрешность.

 

Литература

 

1.                  http://csrc.nist.gov/publications/PubsSPs.html «DRAFT - SP800-90b».

 

Поступила в редакцию 11.10.2012 г.

2006-2018 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.