2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Две случайные последовательности
Сообщение15.02.2018, 02:33 


19/05/13
4
Здравствуйте, уважаемые участники форума.
Я не математик, пожалуйста, отнестись к моему вопросу с пониманием.

Имеется последовательность натуральных чисел $A = a_1, a_2, … , a_n$. Каждое из чисел $a_i$ натуральное и лежит в диапазоне от 0 до 15.
Из последовательности чисел $A$ получили последовательность $B$ путем замены каждого $a_i$ на его 4-разрядный двоичный эквивалент. Полученная последовательность $B = b_1, b_2, … b_{4n}$. Каждое $b_i$ это 0 или 1.
Пример: последовательность А = 5,8,10,15,…,3 преобразовали в последовательность B = 0101100010101111 … 0011.

Двоичную последовательность $B$ прогнали через тесты типа NIST или DIEHARD и пришли к выводу, что она случайна.
Следует ли из этого, что и последовательность чисел $A$ тоже случайна?

Спасибо за ответы.

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


21/09/12

1871
Отсюда следует, что и $A$, исследованная данным тестом, будет признана случайной. На самом деле, это может оказаться отрезок с $100000000$ по $100001000$-й знак десятичного разложения числа $\sqrt{306+\sin(15 \cdot \cos\sqrt{\pi})}$
А так да, десятичная последовательность всё равно переведётся в двоичную тестом - что и приведёт к одинаковому результату.

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


11/03/08
9493
Москва
Этот вывод можно было бы сделать, если бы члены битовой последовательности входили одинаковым образом. Однако у нас есть биты, соответствующие старшему разряду, и соответствующие младшим. И если неслучайны лишь соответствующие старшим, то случайность младших битов может замаскировать факт зависимости старших, при этом значения полученных из этих битовых последовательностей чисел будут определяться прежде всего старшими битами, и будут неслучайны. Хотя выявить факт неслучайности части битов статистическими методами можно, обычные тесты, не нацеленные особо на эту проблему, скорее всего это пропустят.
В качестве примера построим такую последовательность (ради "выпуклости" не по 4 бита, а по 16), причём все биты, кроме старших, случайны, а старшие попеременно принимают значения 0 и 1.
Вот автокорреляционные функции:
Изображение
для битов
и для полученных из них чисел
Изображение
Видно, что при кажущейся случайности и независимости битов числа явно закономерны.

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение16.02.2018, 06:07 


19/05/13
4
Евгений Машеров, спасибо за развернутый ответ.

Скажите, пожалуйста, если ли какой-то способ протестировать на случайность именно последовательность чисел, «собранных» из двоичных разрядов (в моем случае по 4 разряда)?
Насколько я разобрался, тот же тест NIST на уровне чисел не работает, а работает только на уровне двоичных разрядов. Я могу прогнать через NIST двоичные разряды моих чисел, на как мы уже выяснили, случайность двоичной последовательности вовсе не означает случайность числовой последовательности, полученной из двоичной.

Спасибо за ответ.

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


26/05/14
981
files в сообщении #1292580 писал(а):
Каждое из чисел $a_i$ натуральное и лежит в диапазоне от 0 до 15.


-- 16.02.2018, 09:40 --

Тесты показали независимость отдельных битов. Отсюда следует что распределение цифр равномерное, распределение пар цифр равномерное и так далее, то есть исходная последовательность случайна.

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


11/03/08
9493
Москва
Вы очень правильно выбрали слово - "показали", не "доказали". Потому как статистические тесты не доказывают в смысле математического доказательства, а только снижают вероятность ошибки до допустимой. Проверяя на независимость, мы строим условное распределение одной величины в зависимости от другой (обычно какую-то обобщающую характеристику распределения) и сравниваем полученные условные распределения (или их характеристики). Если величины независимы - распределения должны быть равны. Но в силу конечности выборки, взятой для теста, они будут отягощены случайными отклонениями. Поэтому мы проверяем не на равенство, а на малость отклонений, рассчитывая вероятность получить, при условии независимости, отклонение такое же или большее, чем полученное нами. Если вероятность достаточно велика - мы верим в независимость, если мала - отвергаем.
Но в данном примере, поскольку биты на результат влияют по-разному, зависимость одних только старших битов будет замаскирована поведением младших, а вот в значении полученного числа - проявится.

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение16.02.2018, 15:58 
Заслуженный участник


26/05/14
981
Вы подразумеваете что порядок чисел важен? Это не так. Соответственно и все биты равно важны. То что анализ не заметил зависимости в четверти данных - маловероятно.

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


06/10/08
6422
По крайней мере NIST проверяет распределение длины участков из одних нулей и одних единиц, так что схема Евгений Машеров не пройдет - не будет длинных последовательностей одинаковых бит.

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


11/03/08
9493
Москва
Порядок битов важен ipso facto того, что это биты числа, имеющие в нём разный вес.
А разные статистические свойства битовых последовательностей и образованных из них чисел - увы, случаются. В своё время пытались прекрасно работавшие генераторы случайных битов на сдвиговых регистрах использовать для формирования случайных чисел. Получилось плохо.

-- 16 фев 2018, 16:10 --

Xaositect в сообщении #1292857 писал(а):
По крайней мере NIST проверяет распределение длины участков из одних нулей и одних единиц, так что схема Евгений Машеров не пройдет - не будет длинных последовательностей одинаковых бит.


А их в предложенной схеме и нет.

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


06/10/08
6422
Евгений Машеров в сообщении #1292859 писал(а):
А их в предложенной схеме и нет.
Ну я о том и говорю, их нет. А должны быть.

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение16.02.2018, 16:31 
Заслуженный участник


26/05/14
981
Евгений Машеров в сообщении #1292859 писал(а):
Порядок битов важен ipso facto того, что это биты числа, имеющие в нём разный вес.

Проведём мысленный эксперимент: $P$ - процедура оценки случайности последовательности целых чисел в диапазоне $[0, M)$.
$P: [0, M)^N \to [0, 1]$ - оценивает вероятность что данная последовательность случайна.
Берём биекцию $B: [0, M) \to [0, M)$.

Тогда верна аксиома о том что хороший критерий случайности не зависит от биективного отображения элементов последовательности:
$P((x_i)_{i=1}^N) = P((B(x_i))_{i=1}^N)$.

А раз так то все биты равно важны.

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


11/03/08
9493
Москва
Я не спрашиваю, как Вы доказываете аксиому. Какие Вы ГСЧ писали и тестировали?

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение16.02.2018, 19:31 
Заслуженный участник


26/05/14
981
Никакие.
Моя мысль состоит в том что если $P$ не отвечает аксиоме, то им не стоит пользоваться. С учётом того что алфавит маленький (16 значений).

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


11/03/08
9493
Москва
Значит, Вы останетесь вообще без тестов ГСЧ. Поскольку все они "не отвечают аксиоме".

 Профиль  
                  
 
 Re: Две случайные последовательности
Сообщение16.02.2018, 19:52 


07/08/14
4231
files в сообщении #1292580 писал(а):
Следует ли из этого, что и последовательность чисел $A$ тоже случайна?

По крайней мере, можно сделать вывод, что количество значений некоторой величины, на котором постоянное правило генерации значений можно выявить (и тем самым определить эту величину как неслучайную), больше имеющегося количества значений.

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

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



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

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


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

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