Хорошая и простая мера случайности

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

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

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

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

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

.....

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

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

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

Ответ 1

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

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

Страница их результатов оценивает каждую случайную последовательность, используя 7 тестов (Энтропия, День рождения, Матричные звания, Матричные звания 6x8, Минимальное расстояние, Случайные сферы, и Squeeze). Каждый результат теста затем кодируется цветом как один из "Нет проблем", "Потенциально детерминированный" и "Не произвольный".

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

Если вам действительно нужно только одно значение, вы можете выбрать один из 5 тестов ENT и использовать его. Chi-Squared test, вероятно, будет лучше всего использовать, но это может не соответствовать определению простого.

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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

Ответ 8

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

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

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

Ответ 9

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

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

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

{ отмечен: были предоставлены достаточные наблюдения по этому поводу - пощадите меня

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

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

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

Источник: Science Daily

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

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

"Прямое наблюдение парадокса Харди совместным слабым измерением с запутанная пара фотонов", автор Кадзухиро Йокота, Такаши Ямамото, Масато Коаши и Нобуюки Имото из Высшая инженерная школа Наука в Университете Осаки и CREST Photonic Quantum Information Проект в городе Кавагути

Источник: Science Daily

(с учетом жутки/познавательной дихотомии)

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

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

Возможно, работа Yokota et al может показать источник ложного сетевого трафика... может быть, это призраки.

Ответ 10

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

Ответ 11

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

Подумайте о безопасности пароля.

Вопрос был о "длинных" числовых последовательностях, "скажем, 100.000", но не указывает, что является критерием для "длинных". Для паролей 8 символов могут считаться длинными. Если эти 8 символов были "случайными", это можно считать хорошим паролем, но, если его легко угадать, бесполезным паролем.

Общие правила для паролей состоят в том, чтобы смешивать прописные буквы, цифры и специальные символы. Но обычно используемый "Password1" все еще плохой пароль. (хорошо, пример с 9 символами, извините). Итак, сколько из методов других ответов вы применяете, вы также должны проверить, встречается ли пароль в нескольких словарях, включая наборы утечек паролей.

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

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

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

Пример пароля - только один пример того, насколько важен этот вопрос случайности; подумайте также о шифровании. Случайность - это святой Грааль безопасности.