Почему невозможно произвести действительно случайные числа?

47

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

У него есть следующий абзац, который я полностью не в состоянии понять.

К сожалению, генерация случайных чисел выглядит намного проще, чем есть на самом деле. Действительно, на самом деле невозможно произвести действительно случайные числа на любом детерминированном устройстве. Фон Нейман [Neu63] сказал это лучше всего: «Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха». Лучшее, на что мы можем надеяться, это псевдослучайные числа, поток чисел, который выглядит как если они были созданы случайным образом.

Почему невозможно создать действительно случайные числа в любом детерминированном устройстве? Что означает это предложение?

Винот Кумар СМ
источник
86
Вы действительно спрашиваете, почему вы не можете произвести действительно случайное число на детерминированном устройстве? Разве в вопросе уже нет ответа?
Херби
37
Если все числа, которые вы генерируете, должны быть уникальными, они не являются случайными. Вполне возможно, что настоящий генератор случайных чисел даст один и тот же результат десять раз подряд.
TMN
28
Есть недостаток в поиске случайных чисел, которые являются уникальными . Если вы ограничиваете числа быть уникальными , то они не случайны, так как случайность требует возможности повторения независимо от того, насколько невероятным.
Марк Бут
13
За пределами компьютера, является ли случайное число действительно случайным? Брось кубик, это физика с большим количеством векторов.
MPelletier
9
@MPelletier: не совсем. Квантовая механика может (как только ученые выяснили больше из этого) может подразумевать существование истинной случайности, в зависимости от вашего определения случайности.
Брайан

Ответы:

65

Нужно искать криптографически безопасный генератор псевдослучайных чисел . Большинство PRNG являются генераторами линейной конгруэнции ( next numberкак и линейная функция previous number), поэтому, если вы next numberстроите график против, previous numberвы получите график параллельных линий. CSPRNG не будет этого делать. Компромисс в том, что они медленные.

Я группирую генераторы случайных чисел на 3 категории :

  1. Достаточно хорошо для домашней работы.
  2. Достаточно хорош, чтобы поспорить с вашей компанией.
  3. Достаточно хорош, чтобы сделать ставку на свою страну.

Почему невозможно создать действительно случайные числа в любом детерминированном устройстве?

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

Tangurena
источник
1
Вот почему невозможно получить действительно случайное число. Даже если последовательность никогда не повторяется, что не гарантируется для случайных чисел, другой прогон программы с теми же входами даст те же результаты. Таким образом, кто-то еще может воспроизвести ваши случайные числа в более позднее время, что означает, что они не были действительно случайными вообще.
Спенсер Рэтбун
2
@ user973810 Проблема с этим определением из теории информации состоит в том, что вы не можете продемонстрировать фактический случайную последовательность. Мы можем доказать для любого разумного языка определения, что почти каждая бесконечная последовательность (в техническом смысле) является случайной, потому что она вообще не может быть описана в языке. Что более полезно, так это концепция генератора случайных последовательностей: не тот, который генерирует случайную последовательность, а тот, который генерирует последовательность случайным образом.
Жиль "ТАК - перестань быть злым"
13
Немного придирки: некоторые люди, а именно физики-ядерщики и физики элементарных частиц, совершенно уверены, что такие процессы, как атомный распад , действительно случайны.
Дэвид З
9
@ Дэвид: Мы можем пойти немного дальше, чем это даже. Различные эксперименты по неравенству Белла показывают, что некоторые квантовые процессы окончательно непредсказуемы . Они могут быть случайными в некотором философском смысле, или они могут зависеть от нелокальных скрытых переменных, но любой случай препятствует надежному предсказанию.
dmckee
7
@dmckee: да, я просто подумал, что было бы легче избежать попыток объяснить связь между неравенством Белла и коллапсом волновой функции в комментариях к prog.SE. Люди всегда могут зайти на наш сайт, если им любопытно ;-) Tangurena: правда, Эйнштейн действительно говорил это, но это просто означало, что он действительно хотел, чтобы вселенная была детерминированной. Это не так. Эксперименты, проведенные после смерти Эйнштейна, показали это довольно убедительно (исключая нелокальные скрытые переменные, иначе странность ). То, что он Эйнштейн, не означает, что он был прав во всем.
Дэвид Z
22

Истинная случайность подразумевает недетерминизм. Если это детерминистический, он может быть точно предсказан (это то, что означает детерминизм); если это можно предсказать, это не случайно.

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

Чтобы решить эту проблему, многие современные UNIX и Unix-подобные имеют ядра RNG, которые используют физические источники шума для генерации истинной случайности.

Другой распространенный подход - взять текущее время в качестве начального числа для детерминированного ГСЧ ( srand(time(NULL));на С); Криптографически говоря, это бесполезно, так как текущее время не секрет, но для таких вещей, как физическое моделирование или видеоигры, это достаточно хорошо.

tdammers
источник
Обратите внимание, что неповторение также невозможно для любого генератора с ограниченным выходным значением (ограниченным числом битов). Но, конечно, длина цикла детерминированного генератора, скорее всего, намного меньше теоретического максимума, который является всеми возможными перестановками.
9000
@ 9000: Конечно, это не так. Возьмите иррациональное число, используйте цифры (любое основание) в качестве «случайной» последовательности. Boom! неповторяющаяся последовательность (по определению) и все еще ограниченная (до вашей базы).
ThePopMachine
@ThePopMachine: вы можете генерировать неповторяющуюся последовательность битов любой длины, эквивалентную неповторяющейся последовательности чисел неограниченной длины. Вы не можете сгенерировать неповторяющуюся последовательность целых чисел ограниченной величины (например, 32-разрядных); как только вы сгенерировали все перестановки 32-битных значений, последовательность должна повториться. Ты прав; мы просто говорим о разных вещах.
9000
@ 9000: нет ласки. Вы сделали общее заявление, которое является ложным. Если вы на самом деле просто пытаетесь найти не более чем n ^ k разных последовательностей длины k для n разных значений, и поэтому оно должно повторяться, то это довольно очевидно и не интересно.
ThePopMachine
2
@ThePopMachine: Я был бы признателен, если бы вы немного успокоились. Процитируем: «неповторение также невозможно для любого генератора с ограниченным выходным значением (ограниченным числом битов)». То, о чем вы явно говорите, - это неограниченное число битов, как последовательность [двоичных] цифр иррационального числа. Ваше утверждение, хотя и верно, не имеет отношения к проблеме.
9000
10

Вторая глава книги « Моделирование дискретных событий: первый курс » Лоуренса Лимиса дает фантастическое введение в генераторы случайных чисел (или, точнее, генераторы псевдослучайных чисел).

Отрывок из его книги хорошо объясняет это, на мой взгляд:

Исторически три типа генераторов случайных чисел использовались в вычислительных приложениях: (a) генераторы поиска в стиле 1950-х годов, такие как, например, корпоративная таблица RAND с миллионами случайных цифр; (б) аппаратные генераторы, такие как, например, тепловые устройства с «белым шумом»; и (c) алгоритмические (программные) генераторы. Из этих трех типов только алгоритмические генераторы получили широкое признание. Причина этого заключается в том, что только алгоритмические генераторы могут удовлетворить все следующие общепринятые критерии генерации случайных чисел. Генератор должен быть:

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

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

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

riwalk
источник
7

Потому что Вам нужно код записи , чтобы генерирует случайные числа и код является НЕ случаен. (Это детерминировано)

Таким образом, вы начинаете со значения «Seed value (s)», которое выбирается как «Random» (обычно текущая отметка времени), а затем используете его в алгоритме, чтобы начать генерировать числа. Но весь набор основан на оригинальной стоимости Seed!

Так что, если вы снова запустите свой код с точно такими же значениями Seed, вы получите ТОЧНЫЙ набор данных! Как любой разумный человек может назвать это случайным? Но он уверен , делает LOOK случайным.


Что касается того, чтобы сделать их уникальными, после генерации номера просто проверьте, есть ли у вас этот номер, если он есть, выбросьте его и сгенерируйте новый.

Идиоты
источник
13
С другой стороны, повторяющиеся псевдослучайные числа могут быть полезны для отладки.
Дэвид Торнли
5

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

Джеймс Маклеод
источник
1
Это действительно комментарий, а не ответ, так как он на самом деле не отвечает на вопрос .
Марк Бут
5

У меня есть очень простое определение псевдослучайного :

Слишком много неизвестных переменных для прогнозирования.

У меня также есть простое определение True Random :

Бесконечные неизвестные переменные.

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

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

Скотт Риппи
источник
1
Ну, «время» - плохой пример того, что нельзя предсказать. С другой стороны, движение мыши, микрофонный вход и т. Д. Являются непредсказуемыми.
HoLyVieR
3

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

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

Unkwntech
источник
5
Как физик, занятый неполный рабочий день, генераторы, основанные на квантовых событиях (насколько мы можем сказать), действительно случайны. Люди, которым не нравится случайность, с самого начала пытаются исключить случайность из квантовой механики, и все, что она делает, - это накапливает больше доказательств того, что она действительно случайна.
Дэвид Торнли
@DavidThornley, ... пока кто-нибудь не выяснит формулу.
CaffGeek
1
@Chad: нет формулы в обычном смысле; это было исключено экспериментами EPR. Конечно, можно предположить, что все это детерминировано, но не так легко понять.
Дэвид Торнли
@DavidThornley, я знал, что это неправильное слово. Я думаю, что мы знаем, что я пытался сказать. Почти каждый раз, когда кто-то говорит, что что-то невозможно, кто-то в конечном итоге доказывает, что он неправ. Это человеческая природа.
CaffGeek
2
Это все равно, что сказать, что в конце концов кто-то собирается создать машину, способную решить проблему остановки, потому что кто-то сказал, что это невозможно. Дело не в том, чтобы найти уравнение, оно на самом деле является случайным в соответствии со всеми проведенными экспериментами и той математикой, которая подтверждает это.
Алекс
2

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

Баладжи Вишванатан
источник
2

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

Поэтому, если f (x) = z, f (x)! = Y, если y не равно z. Это функция. Представьте себе JavaScript:

function Add(A, B) {
      return A + B;
}

var addedNumber = Add(2,3);//returns 5
addedNumber = Add(2,3);//still 5

Независимо от того, сколько раз вы вызываете, Add(2,3)он всегда вернет 5. Другими словами, Add () является детерминированной функцией.

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

Теперь здесь все становится интересно.

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

Заметьте, что фон Нейман утверждает, что «арифметические методы получения [...]». Речь не идет о человеческом входе, параллельности, выборочных скоростях ветра, считываемых с точного прибора, или о других неалгоритмических способах получения случайного ввода для детерминированной функции.

Это просто говорит о том, что функция или система функций не станет внезапно недетерминированной. Другими словами, Add (2,3) не будет каким-либо образом возвращать 6 или что-либо, кроме 5, при тех же входных данных . Это невозможно.

Автор цитирования делает еще один шаг вперед.

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

Контекст предварительно определен как «на любом детерминированном устройстве». Я мог бы закончить спор здесь. Но что, если мы изменим контекст, введя новый элемент в систему? Недетерминированный элемент, добавленный в качестве входных данных, делает систему недетерминированной системой. Хотя, удаляя недетерминированный элемент, мы возвращаемся к детерминированной системе. Если мы можем каким-то образом отследить или иным образом воспроизвести входные данные, мы можем воспроизвести результат. Но весь этот абзац тангениален тому, что говорит автор. Помните контекст.

Можно спорить о значении недетерминизма. Еще раз загар. Помните контекст.

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

P.Brian.Mackey
источник