2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Две случайные последовательности
Сообщение16.02.2018, 20:04 
Заслуженный участник


26/05/14
618
Даже на алфавите из 16 значений?
Усовершенствуем тест ГСЧ. Выполним его $16!$ раз для всевозможных перестановок алфавита последовательности, результат усредним.
Это долго, но реально. Вот тест отвечающий аксиоме. Жаль что не все они такие. :)

-- 16.02.2018, 20:06 --

Добавлю, что мой пример непрактичен. Я только продемонстрировал теоретическую возможность

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение17.02.2018, 05:44 
Аватара пользователя


26/05/12
759
приходит весна?
У топикстартера битовая последовательность получена прямым сочленением битовых представлений чисел с фиксированной разрядностью. Если же вместо фиксированной разрядности взять какой-нибудь код Хаффмана, то всё станет совсем плохо. Например, возьмём английский алфавит, сопоставим каждой букве какое-нибудь случайное значение частотности, построим префиксный код и возьмём текст, где случайные гласные и случайные согласные чередуются через один, и преобразуем согласно полученному коду. Результирующая битовая последовательность вряд ли будет содержать хоть какой-то намёк на закономерность чередования, которая лежит в её основе.

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение17.02.2018, 20:32 
Заслуженный участник
Аватара пользователя


11/03/08
6064
Москва
files в сообщении #1292754 писал(а):
Насколько я разобрался, тот же тест NIST на уровне чисел не работает, а работает только на уровне двоичных разрядов. Я могу прогнать через NIST двоичные разряды моих чисел, на как мы уже выяснили, случайность двоичной последовательности вовсе не означает случайность числовой последовательности, полученной из двоичной.


Используйте DIEHARD, он не только с битами умеет...

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение17.02.2018, 22:39 
Заслуженный участник
Аватара пользователя


11/03/08
6064
Москва
В общем, изящное рассуждение, что если биты случайны, то и функция от них случайна, не то, чтобы неверно. Оно просто сюда не относится. У нас не случайные биты, а биты, выдержавшие тест на случайность. Статистический тест. Который может давать ошибочные результаты. Ложноположительные и ложноотрицательные диагнозы. При заданной длине выборки мы можем маневрировать лишь меж ними. Чтобы одновременно сократить и число ложноположительных, и ложноотрицательных (ошибок I и II рода), надо увеличивать выборку. Мы можем придти к выводу, что длина выборки достаточна, чтобы вероятности ошибок были бы нужной малости, и поэтому верить результатам теста.
Но в данном примере биты участвуют в формировании числа в разной степени. Старший бит вносит больше, чем все остальные вместе взятые. Что приводит к тому, что статистические характеристики набора чисел, сформированных из битовой последовательности, определяются четвертью наличных бит - только "старшими". То есть эффективная длина выборки оказывается в разы меньше формальной длины её, и может оказаться, что при том, что формальная длина выборки достаточна для суждения о распределении, в действительности данных недостаточно.
Я бы советовал вместо специализированных тестов NIST, ориентированных на проверку битовых последовательностей, использовать проверку чисел, скажем, из DIEHARD. Вообще, лучше проверять именно то, что желаешь использовать.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу Пред.  1, 2

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group