Статистическая случайность

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

Статистическая случайность не обязательно подразумевает «истинную» случайность , то есть объективную непредсказуемость . Псевдослучайность достаточна для многих целей, например, в статистике, отсюда и название «статистическая случайность».

Глобальная случайность и локальная случайность — это разные вещи. Большинство философских концепций случайности являются глобальными, поскольку они основаны на идее о том, что «в долгосрочной перспективе» последовательность выглядит действительно случайной, даже если некоторые подпоследовательности не будут выглядеть случайными. Например, в «истинно» случайной последовательности чисел достаточной длины вполне вероятно, что будут длинные последовательности, состоящие только из повторяющихся чисел, хотя в целом последовательность может быть случайной. Локальная случайность относится к идее о том, что могут существовать минимальные длины последовательностей, в которых аппроксимируются случайные распределения. Длинные отрезки одних и тех же чисел, даже те, которые генерируются «по-настоящему» случайными процессами, уменьшат «локальную случайность» выборки (она может быть локально случайной только для последовательностей из 10 000 чисел; взятие последовательностей из менее 1000 может не показаться случайным). вообще, например).

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

Законодательство об азартных играх определенные стандарты статистической случайности налагает на игровые автоматы .

Тесты

Первые тесты для случайных чисел были опубликованы М. Г. Кендаллом и Бернардом Бэбингтоном Смитом в Журнале Королевского статистического общества в 1938 году. ^[2] Они были построены на статистических инструментах, таких как критерий хи-квадрат Пирсона , который был разработан, чтобы определить, соответствуют ли экспериментальные явления их теоретическим вероятностям. Первоначально Пирсон разработал свой тест, показав, что ряд экспериментов с игральными костями, проведенных У.Ф.Р. Уэлдоном, не показали «случайного» поведения.

Первоначальные четыре теста Кендалла и Смита были проверкой гипотез , в которых в качестве нулевой гипотезы принималась идея о том, что каждое число в данной случайной последовательности имеет равную вероятность появления и что различные другие закономерности в данных также должны быть распределены равновероятно.

Частотный тест был очень простым: проверка наличия примерно одинакового количества 0, 1, 2, 3 и т. д.
Серийный тест делал то же самое, но для последовательностей из двух цифр за раз (00, 01, 02 и т. д.), сравнивая их наблюдаемые частоты с их гипотетическими предсказаниями, если бы они были равномерно распределены.
Покерный тест , тестируемый для определенных последовательностей из пяти номеров одновременно (AAAAA, AAAAB, AAABB и т. д.) на основе рук в игре в покер .
Тест на разрыв рассматривал расстояния между нулями (00 будет расстоянием 0, 030 будет расстоянием 1, 02250 будет расстоянием 3 и т. д.).

Если данная последовательность могла пройти все эти тесты в пределах заданной степени значимости (обычно 5%), то она считалась, по их словам, «локально случайной». Кендалл и Смит отличали «локальную случайность» от «истинной случайности» тем, что многие последовательности, созданные с помощью действительно случайных методов, могут не отображать «локальную случайность» в заданной степени — очень большие последовательности могут содержать множество строк из одной цифры. Это может быть «случайно» в масштабе всей последовательности, но в меньшем блоке оно не будет «случайным» (оно не пройдет тесты) и будет бесполезным для ряда статистических приложений.

Поскольку наборы случайных чисел становились все более распространенными, использовалось все больше тестов все более сложной сложности. Некоторые современные тесты отображают случайные цифры как точки на трехмерной плоскости, которые затем можно вращать для поиска скрытых закономерностей. В 1995 году статистик Джордж Марсалья создал набор тестов, известный как « твердые тесты» , которые он распространяет на компакт-диске с 5 миллиардами псевдослучайных чисел. В 2015 году Юнге Ван распространил пакет программного обеспечения Java. ^[3] для статистического дистанционного тестирования случайности.

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

Другие тесты:

Тест Monobit рассматривает каждый выходной бит генератора случайных чисел как тест подбрасывания монеты и определяет, близко ли наблюдаемое количество орлов и решек к ожидаемой частоте 50%. Число орлов в следе подбрасывания монеты образует биномиальное распределение .
Вальд -Вольфовиц проводит тестовые тесты на количество битовых переходов между 0 битами и 1 битами, сравнивая наблюдаемые частоты с ожидаемой частотой случайной последовательности битов.
Информационная энтропия
Автокорреляционный тест
Тест Колмогорова – Смирнова
Статистический тест на случайность, основанный на расстоянии. Юнге Ван показал ^[4]^[5] что стандарты тестирования NIST SP800-22 недостаточны для обнаружения некоторых недостатков генераторов случайности и предлагаемого теста случайности на основе статистического расстояния.
Оценка спектральной плотности ^[6] - выполнение преобразования Фурье «случайного» сигнала преобразует его в сумму периодических функций с целью обнаружения неслучайных повторяющихся тенденций.
Универсальный статистический тест Маурера
Тесты Дихарда

См. также

Ссылки

^ Пи кажется хорошим генератором случайных чисел, но не всегда лучшим , Чад Бутин, Университет Пердью
^ Кендалл, Миннесота ; Смит, Б. Бабингтон (1938). «Случайность и случайные числа выборки». Журнал Королевского статистического общества . 101 (1): 147–166. дои : 10.2307/2980655 . JSTOR 2980655 .
^ Юнге Ван. Методы статистического тестирования для генерации псевдослучайных чисел. http://webpages.uncc.edu/yonwang/liltest/
^ Юнге Ван: О разработке тестов LIL для (псевдо)случайных генераторов и некоторых экспериментальных результатах. PDF
^ Ван, Юнге; Никол, Тони (2015). «Статистические свойства псевдослучайных последовательностей и эксперименты с PHP и Debian OpenSSL». Компьютеры и безопасность . 53 : 44–64. дои : 10.1016/j.cose.2015.05.005 .
^ Кнут, Дональд (1998). Искусство компьютерного программирования Том. 2: Получисловые алгоритмы . Эддисон Уэсли. стр. 93–118. ISBN 978-0-201-89684-8 .

Внешние ссылки

DieHarder : бесплатный ( GPL ) C. набор тестов случайных чисел
Генерация случайных чисел с нормальным распределением

[1] Пи кажется хорошим генератором случайных чисел, но не всегда лучшим , Чад Бутин, Университет Пердью

[2] Кендалл, Миннесота ; Смит, Б. Бабингтон (1938). «Случайность и случайные числа выборки». Журнал Королевского статистического общества . 101 (1): 147–166. дои : 10.2307/2980655 . JSTOR 2980655 .

[3] Юнге Ван. Методы статистического тестирования для генерации псевдослучайных чисел. http://webpages.uncc.edu/yonwang/liltest/

[4] Юнге Ван: О разработке тестов LIL для (псевдо)случайных генераторов и некоторых экспериментальных результатах. PDF

[5] Ван, Юнге; Никол, Тони (2015). «Статистические свойства псевдослучайных последовательностей и эксперименты с PHP и Debian OpenSSL». Компьютеры и безопасность . 53 : 44–64. дои : 10.1016/j.cose.2015.05.005 .

[6] Кнут, Дональд (1998). Искусство компьютерного программирования Том. 2: Получисловые алгоритмы . Эддисон Уэсли. стр. 93–118. ISBN 978-0-201-89684-8 .

[1]

[2]

[3]

[4]

[5]

[6]