Две случайные последовательности

[files]

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

Имеется последовательность натуральных чисел $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$ тоже случайна?

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

[atlakatl]

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

[Евгений Машеров]

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

для битов
и для полученных из них чисел

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

[files]

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

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

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

[slavav]

files в сообщении #1292580 писал(а):

Каждое из чисел $a_i$ натуральное и лежит в диапазоне от 0 до 15.

-- 16.02.2018, 09:40 --

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

[Евгений Машеров]

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

[slavav]

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

[Xaositect]

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

[Евгений Машеров]

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

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

Xaositect в сообщении #1292857 писал(а):

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

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

[Xaositect]

Евгений Машеров в сообщении #1292859 писал(а):

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

Ну я о том и говорю, их нет. А должны быть.

[slavav]

Евгений Машеров в сообщении #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)$.

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

[Евгений Машеров]

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

[slavav]

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

[Евгений Машеров]

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

[upgrade]

files в сообщении #1292580 писал(а):

Следует ли из этого, что и последовательность чисел $A$ тоже случайна?

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