О некоторых статистических свойствах преобразования «Book Stack»

Авторы

  • Андрей Важевич Бзикадзе
  • Владимир Викторович Некруткин

Аннотация

В статье изучаются статистические свойства так называемого преобразования «Book Stack», предложенного Б. Я. Рябко (Пробл. передачи инф., т. 16, вып. 4, 1980) в качестве процедуры сжатия информации. Это же преобразование было использовано Б. Я. Рябко и А. И. Пестуновым (Пробл. передачи инф., т. 40, вып. 1, 2004) при построении одноименного статистического теста. Тест предназначен для проверки гипотезы H0 о том, что имеющаяся «входная» повторная выборка соответствует дискретному равномерному распределению с известным носителем. При этом предлагается проверять эту гипотезу не для «входной» выборки, а для новой, полученной с помощью «Book Stack»-преобразования. Тем самым возникает естественная задача сравнения результатов применения одного и того же статистического теста к «входной» и «выходной» выборкам. При выполнении нулевой гипотезы эти процедуры являются эквивалентными, однако при отклонениях от H0 это, вообще говоря, уже не так. Результаты сравнения критериев, конечно, зависят от класса рассматриваемых альтернатив. В статье рассматривается естественная альтернатива, состоящая в том, что исходная повторная выборка соответствует дискретному, но не равномерному распределению с фиксированным носителем. При этом показано, что некоторые стандартные критерии для проверки гипотезы H0 оказываются более мощными при их применении к «входной» выборке, чем к преобразованной. В частности, этоимеет место для критерия отношения правдоподобия и (с некоторыми формальными ограничениями) к критерию χ2. Библиогр. 14 назв.

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

1. Рябко Б.Я., Пестунов А.И. «Стопка книг» как новый статистический тест для случайных чисел // Проблемы передачи информации. 2004. Т. 40, вып. 1. С. 73-78.

2. Монарев В.А., Рябко Б.Я. Экспериментальный анализ генераторов псевдослучайных чисел при помощи нового статистического теста // Ж. вычисл. матем. и матем. физ. 2004. Т. 44, вып. 5. С. 812-816.

3. Ryabko B., Stognienko V., Shokin Yu. A new test for randomness and its application to some cryptographic problems // Journal of Statistical Planning and Inference. 2004. Vol. 123, N 2. P. 365-376.

4. Ryabko B., Monarev V. Using information theory approach to randomness testing // Journal of Statistical Planning and Inference. 2005. Vol. 133. P. 95-110.

5. Doroshenko S. et al. On ZK-crypt, Book Stack, and statistical tests // IACR Cryptology ePrint Archive. 2006. P. 1-8. URL: http://eprint.iacr.org/2006/196.pdf (дата обращения: 27.08.2016).

6. Doroshenko S., Ryabko B. The experimental distinguishing attack on RC4 // IACR Cryptology ePrint Archive. 2006. P. 1-4. URL: http://eprint.iacr.org/2006/070.pdf (дата обращения: 27.08.2016).

7. Рябко Б.Я. Сжатие данных с помощью стопки книг // Проблемы передачи информормации. 1980. Т. XVI, вып. 4. C. 16-20.

8. Bentley J., Sleator D, Tarjan R., Wei V. A locally adaptive data compression scheme // Commun. ACM. 1986. Vol. 29, N 4. P. 320-330.

9. Seward J. bzip2 and libbzip2, version 1.0.5: A program and library for datacompression, 2007. URL: http://www.bzip.org/1.0.5/bzip2-manual-1.0.5.pdf (дата обращения: 27.08.2016).

10. Read T., Cressie N. Goodness-of-Fit statistics for discrete multivariate data. New York: Springer-Verlag, 1988. 224 p.

11. Ширяев А.Н. Вероятность. Т. 1. М.: Изд-во МЦНМО, 2004. 520 c.

12. Файнстейн А. Основы теории информации. М.: ИИЛ, 1960. 144 с.

13. Hoeffding W. Asymptotically optimal test for multinomial distributions // Ann. Math. Stat. 1965. Vol. 36, N 2. P. 269-401.

14. L'Ecuyer P., Compagner A., Cordeau J-F. Entropy tests for random number generation // Les Cahiers du GERAD, no. G-96-41, 1996, P. 1-22.

Загрузки

Опубликован

20.08.2020

Как цитировать

Бзикадзе , А. В., & Некруткин, . В. В. (2020). О некоторых статистических свойствах преобразования «Book Stack». Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 3(4), 533–543. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8658

Выпуск

Раздел

Математика