Хорошая и ПРОСТАЯ мера случайности

Что лучший алгоритм должен взять длинную последовательность целых чисел (скажите, что 100,000 из них), и возвращают измерение того, насколько случайный последовательность?

Функция должна возвратить единственный результат, сказать 0, если последовательность не все, что все случайные, до, говорят 1, если совершенно случайный. Это может дать что-то промежуточное, если последовательность несколько случайна, например, 0.95 могла бы быть довольно случайная последовательность, тогда как 0.50 мог бы иметь некоторые неслучайные части и некоторые случайные части.

Если бы я должен был передать первые 100 000 цифр Pi к функции, то она должна дать число очень близко к 1. Если я передал последовательность 1, 2... 100,000 к нему, он должен возвратиться 0.

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

Есть ли такое животное?

…..

Обновление 24 сентября 2019: Google, возможно, просто возвестил эру квантового превосходства, говорит:

"Квантовый компьютер Google по сообщениям смог решить вычисление — доказательство случайности чисел, произведенных генератором случайных чисел — через 3 минуты и 20 секунд, которые возьмут самый быстрый традиционный суперкомпьютер в мире, Саммит, приблизительно 10 000 лет. Это эффективно означает, что вычисление не может быть выполнено традиционным компьютером, делая Google первым для демонстрации квантового превосходства".

Так, очевидно, существует алгоритм для "доказывания" случайности. Кто-либо знает, каково это? Этот алгоритм мог также обеспечить меру случайности?

38
задан lkessler 25 September 2019 в 01:04
поделиться

10 ответов

Это можно сделать следующим образом:

CAcert Research Lab выполняет Анализ генератора случайных чисел .

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

Таким образом, можно написать функцию, которая принимает случайную последовательность и выполняет 7 тестов. Если какой-либо из 7 тестов является «Неслучайным», тогда функция возвращает 0. Если все 7 тестов - «Нет проблем», то она возвращает 1. В противном случае она может вернуть некоторое промежуточное число в зависимости от количества тесты входят как «потенциально детерминированные».

Единственное, чего не хватает в этом решении, - это код для 7 тестов.

13
ответ дан 27 November 2019 в 03:43
поделиться

Ваш вопрос отвечает сам собой. «Если бы я передал функции первые 100 000 цифр Пи, она должна была дать число, очень близкое к 1», за исключением того, что цифры Пи не являются случайными числами, поэтому, если ваш алгоритм не распознает очень конкретную последовательность как не являющуюся случайный, тогда это не очень хорошо.

Проблема в том, что существует много типов неслучайности: - например. «121,351,991,7898651,12398469018461» или «33,27,99,3000,63,231» или даже «14297141600464,14344872783104,819534228736,3490442496» определенно не случайны.

Я думаю, что вам необходимо определить аспекты случайность, которая важна для вас - распределение, распределение цифр, отсутствие общих факторов, ожидаемое количество простых чисел, фибоначчи и другие «особые» числа и т. д.

PS. Быстрый и грязный (и очень эффективный) тест на случайность заключается в том, имеет ли файл примерно тот же размер после сжатия.

18
ответ дан 27 November 2019 в 03:43
поделиться

Вы можете попробовать сжать последовательность в zip-архиве. Чем лучше вы добьетесь успеха, тем менее случайна последовательность.

Таким образом, эвристическая случайность = длина почтового индекса / длина исходной последовательности

8
ответ дан 27 November 2019 в 03:43
поделиться

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

Набор DIEHARD является стандартом де-факто для этого вида тестирования, но он не возвращает ни одного значения и не является простым.

ENT - последовательность псевдослучайных чисел Программа тестирования представляет собой более простую альтернативу, которая объединяет 5 различных тестов. На веб-сайте объясняется, как работает каждый из этих тестов.

Если вам действительно нужно только одно значение, вы можете выбрать один из 5 ЛОР-тестов и использовать его. Тест хи-квадрат , вероятно, будет лучшим для использования, но он может не соответствовать определению простого.

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

7
ответ дан 27 November 2019 в 03:43
поделиться

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

Entropy formula

Вам просто нужно вычислить частоты каждого числа в последовательности. Это даст вам p (xi) (например, если 10 появляется 27 раз, p (10) = 27 / L, где L равно 100.000 для вашего случая.) Это должно дать вам меру энтропии.

Хотя это не даст вам число от 0 до 1. По-прежнему 0 будет минимальной неопределенностью. Однако верхняя граница не будет равна 1. Для этого вам нужно нормализовать вывод.

5
ответ дан 27 November 2019 в 03:43
поделиться

"Насколько случайна эта последовательность?" - сложный вопрос, потому что по сути вас интересует, как была сгенерирована последовательность. Как говорили другие, вполне возможно генерировать последовательности, которые кажутся случайными, но не происходят из источников, которые мы считаем случайными (например, цифры числа пи).

Большинство тестов на случайность стремятся ответить на несколько иные вопросы, а именно : «Является ли эта последовательность аномальной по отношению к данной модели?». Если ваша модель бросает десятиугольные кости, то довольно легко количественно оценить, насколько вероятно, что последовательность сгенерирована на основе этой модели, и цифры числа Пи не будут выглядеть аномально. Но если ваша модель: «Можно ли эту последовательность легко сгенерировать из алгоритма?» становится намного труднее.

3
ответ дан 27 November 2019 в 03:43
поделиться

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

0
ответ дан 27 November 2019 в 03:43
поделиться

То, что вы ищете, не существует, по крайней мере, так, как вы это сейчас описываете.

Основная проблема заключается в следующем:
Если он случайный, то он пройдет тесты на случайность; но обратное неверно - не существует теста, который может проверить случайность.

Например, можно иметь очень сильные корреляции между элементами, находящимися далеко друг от друга, и, как правило, для этого нужно явно тестировать. Или можно было бы иметь плоское распределение, но сгенерированное очень неслучайным образом. И т. Д. И т. Д.

В конце концов, вам нужно решить, какие аспекты случайности важны для вас, и проверить их (как Джеймс Андерсон описывает в своем ответе). Я уверен, что если вы думаете о чем-то, что неочевидно, здесь люди помогут.

Между прочим, я обычно подхожу к этой проблеме с другой стороны: мне дают некоторый набор данных, который ищет все, что я вижу, совершенно случайно, но мне нужно определить, есть ли где-то закономерность. Очень неочевидно,

3
ответ дан 27 November 2019 в 03:43
поделиться

В компьютерном зрении при анализе текстур возникает проблема попытки измерить случайность текстуры, чтобы сегментировать ее. Это в точности то же самое, что и ваш вопрос, потому что вы пытаетесь определить случайность последовательности байтов / целых чисел / чисел с плавающей запятой. Лучшее обсуждение энтропии изображений, которое я смог найти, - это http://www.physicsforums.com/showthread.php?t=274518 .

По сути, это статистическая мера случайности для последовательности значений.

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

2
ответ дан 27 November 2019 в 03:43
поделиться

@JohnFx «... математически невозможно».

плакат гласит: взять длинную последовательность целых чисел ...

Таким образом, точно так же, как пределы используются в исчислении, мы можем принять значение за значение - изучение Хаотики показывает, что конечные пределы могут «включаться сами по себе», создавая тензорные поля, которые обеспечивают иллюзию абсолютного (-ых), и которые могут работать, пока есть время и энергия. . Из-за кривизны пространства-времени нет совершенства, поэтому фраза « ... скажем, 1, если совершенно случайна. » является неправильным.

{ отметил : об этом было предоставлено множество наблюдений - избавьте меня}

В соответствии с вашей позицией, даны два байта [] из нескольких k, каждый из которых рандомизирован независимо - операция не может быть получена " измерение того, насколько случайна последовательность "Статья в Wiki информативна и делает определенные шаги, раскрывающие суть дела, но

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

Группа физиков из Инсбрука, Австрия во главе с Кристианом Роосом и Райнер Блатт, впервые доказано в комплексном эксперименте что невозможно объяснить квантовые явления в неконтекстуальных

Источник: Science Daily

Давайте рассмотрим неслучайные движения ящериц. Источник стимула, который запускает сложные движения в опавших хвостах леопардовых гекконов, в соответствии с вашим исходным, исправленным гипертезом, никогда не будет известен. Мы, опытные компьютерщики, страдаем от невинной проблемы, которую представляют новички, слишком хорошо зная, что в контексте незапятнанного и первозданного разума они являются жемчужинами и зародышами упреждающего мышления.

Если мысленное поле исходной ящерицы создает тензорное поле (разберитесь с ним, ребята, это передовые исследования в области сублинейной физики), тогда мы могли бы иметь «лучший алгоритм для получения длинной последовательности» цивилизации, начиная с События Тоба и заканчивая Хаотической инверсией ". совместным слабым измерением с запутанная пара фотонов », автор: Казухиро Ёкота, Такаши Ямамото, Масато Коаши и Нобуюки Имото из Высшая школа инженерии Наука в Осакском университете и CREST Фотонная квантовая информация Проект в городе Кавагути

Источник: Science Daily

(учитывая дихотомию жуткий / познаваемый)

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

Когда тело просыпается, возникает почти неизбежный всплеск, но это похоже на звонок в дверь, разговор о котором приводит к интересной области статистических исследований доступности финансирования: сколько мыслей можно поддерживать синхронно? Я считаю, что двойственность - это практический рабочий предел, в триединстве он либо нарушается при следующей мысли, либо длится недолго.

Возможно, работа Йокоты и др. Могла бы выявить источник ложного сетевого трафика ... возможно, это призраки.

разговор об этом приводит к интересной области статистических исследований доступности финансирования: сколько мыслей можно поддерживать синхронно? Я считаю, что двойственность - это практический рабочий предел, в триединстве он либо нарушается при следующей мысли, либо длится недолго.

Возможно, работа Йокоты и др. Могла бы выявить источник ложного сетевого трафика ... возможно, это призраки.

разговор об этом приводит к интересной области статистических исследований доступности финансирования: сколько мыслей можно поддерживать синхронно? Я считаю, что двойственность - это практический рабочий предел, в триединстве он либо нарушается при следующей мысли, либо длится недолго.

Возможно, работа Йокоты и др. Могла бы выявить источник ложного сетевого трафика ... возможно, это призраки.

1
ответ дан 27 November 2019 в 03:43
поделиться
Другие вопросы по тегам:

Похожие вопросы: