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

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

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

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

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

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

Тесты

Основная статья: Тесты на случайность

Первые тесты на случайные числа были опубликованы М.Г. Кендалл и Бернард Бабингтон Смит в Журнал Королевского статистического общества в 1938 г.[2] Они были построены на таких статистических инструментах, как Критерий хи-квадрат Пирсона которые были разработаны, чтобы различать, соответствуют ли экспериментальные явления их теоретическим вероятностям. Первоначально Пирсон разработал свой тест, показав, что ряд экспериментов с игральными костями W.F.R. Велдон не отображал "случайного" поведения.

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  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.cos.2015.05.005.
  6. ^ Кнут, Дональд (1998). Искусство программирования Том. 2: получисловые алгоритмы. Эддисон Уэсли. С. 93–118. ISBN  978-0-201-89684-8.

внешняя ссылка