Случайность вообще не случайна?

79

Я сделал это, чтобы проверить случайность randint:

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

Я пробовал примерно в 10 раз больше, и лучший результат - 121 итерация перед повторителем. Это лучший результат, который вы можете получить от стандартной библиотеки?

орокусаки
источник
56
«Программист-прагматик», правило 26. «Выберите« Не сломлен ». Редко можно найти ошибку в ОС, компиляторе или даже стороннем продукте или библиотеке. Ошибка скорее всего в приложении. Или в данном случае применение теории вероятностей.
11
Просто придирки: uniques = set () и uniques.add (x) были бы более подходящими (эффективными).
Эрик О Лебигот
22
Одно из ключевых свойств парадокса дней рождений - то, что они противоречат интуиции. Если вы не знаете об этом или не имеете некоторого опыта в теории вероятностей, у вас не обязательно будет причина для поиска по ключевым словам. Одно из УТП сайтов вопросов и ответов заключается в том, что вы можете задавать вопрос в терминах, которые никогда бы не совпали с ответами на вопрос, если бы вы выполняли чистый поиск по ключевым словам, не зная, что искать.
ConcernedOfTunbridgeWells
7
@okoku: (по поводу вашего ответа на ConcernedOfTunbridge): то, о чем вы говорите, - это совсем другая проблема. Первый - это вероятность получить одну и ту же карту дважды подряд; другая - вероятность получить ЛЮБУЮ из предыдущих N-1 карт после N пиков. Среднее количество карт с более совершенной ГСЧ для второй задачи должна быть около 67; учитывая, что у вас где-то от 8 до 121, это звучит примерно правильно.
BlueRaja - Дэнни Пфлугофт
5
вы путаете случайное с равномерным распределением. Генератор случайных чисел может многократно возвращать одно и то же значение многократно. Если вам нужен генератор равномерно распределенных случайных чисел, это совершенно другая проблема, это проблема перетасовки, а не проблема генератора.

Ответы:

287

Парадокс дня рождения, или почему ГПСЧ производят дубликаты чаще, чем вы думаете.


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

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

Краткое руководство по генераторам псевдослучайных чисел (ГПСЧ)

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

Некоторые алгоритмы, такие как линейный конгруэнтный PRNG ( A'=AX|M), действительно гарантируют уникальность для всего периода. В LCG сгенерированное значение содержит все состояние аккумулятора, и никакое дополнительное состояние не сохраняется. Генератор является детерминированным и не может повторять число в течение периода - любое заданное значение аккумулятора может означать только одно возможное последовательное значение. Следовательно, каждое значение может встречаться только один раз за период работы генератора. Однако период такого PRNG относительно невелик - около 2 ^ 30 для типичных реализаций алгоритма LCG - и не может быть больше, чем количество различных значений.

Не все алгоритмы ГПСЧ разделяют эту характеристику; некоторые могут повторять заданное значение в течение периода. В задаче OP алгоритм Мерсенна Твистера (используемый в модуле случайных чисел Python ) имеет очень большой период - намного больше 2 ^ 32. В отличие от линейного конгруэнтного ГПСЧ, результат не является исключительно функцией предыдущего выходного значения, поскольку аккумулятор содержит дополнительное состояние. С 32-битным целочисленным выводом и периодом ~ 2 ^ 19937 он не может предоставить такую ​​гарантию.

Mersenne Twister - популярный алгоритм для ГПСЧ, поскольку он имеет хорошие статистические и геометрические свойства и очень долгий период - желательные характеристики для ГПСЧ, используемого в имитационных моделях.

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

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

  • Длительный период означает, что вы можете сгенерировать много чисел, прежде чем последовательность вернется к началу. Если модели требуется большое количество итераций или ее нужно запускать из нескольких начальных значений, то 2 ^ 30 или около того дискретных чисел, доступных из типичной реализации LCG, может оказаться недостаточным. Алгоритм MT19337 имеет очень большой период - 2 ^ 19337-1, или около 10 ^ 5821. Для сравнения, общее количество атомов во Вселенной оценивается примерно в 10 ^ 80.

32-битное целое число, произведенное ГПСЧ MT19337, не может представлять достаточно дискретных значений, чтобы избежать повторения в течение такого большого периода. В этом случае вероятны повторяющиеся значения, которые неизбежны при достаточно большом объеме выборки.

В двух словах о парадоксе дня рождения

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

Этот график показывает вероятность общего дня рождения по мере увеличения количества людей в комнате.  Для 23 человек вероятность того, что двое разделят день рождения, составляет чуть более 50%.

Вероятность совпадения между любыми двумя людьми намного выше, чем вероятность совпадения с конкретным человеком, поскольку совпадение не обязательно должно быть до определенной даты. Скорее всего, вам нужно найти только двух людей с одинаковым днем ​​рождения. Из этого графика (который можно найти на странице в Википедии по данному вопросу) мы видим, что нам нужно всего 23 человека в комнате, чтобы с 50% вероятностью найти двух таких совпадений таким образом.

Из статьи в Википедии по этому поводу мы можем получить хорошее резюме. В задаче OP у нас есть 4500 возможных «дней рождения», а не 365. Для заданного числа сгенерированных случайных значений (приравниваемых к «людям») мы хотим знать вероятность появления любых двух одинаковых значений в последовательности.

Расчет вероятного влияния парадокса дня рождения на проблему ОП

Для последовательности из 100 чисел у нас есть (100 * 99) / 2 = 4950 пары (см. Понимание проблемы ), которые потенциально могут совпадать (т. Е. Первое может соответствовать второму, третьему и т. Д., Второе может соответствовать третьему, четвертому и т. Д. И т. Д.), Поэтому количество потенциально возможных комбинаций больше, чем 100.

Из расчета вероятности получит выражение 1 - (4500! / (4500 ** 100 * (4500-100)!) . Следующий фрагмент кода Python ниже делает наивную оценку вероятности появления совпадающей пары.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

Это дает разумно выглядящий результат p = 0,669 для совпадения в пределах 100 чисел, выбранных из совокупности из 4500 возможных значений. (Может быть, кто-нибудь сможет это проверить и опубликовать комментарий, если это неправильно). Из этого мы можем видеть, что продолжительность пробегов между совпадающими числами, наблюдаемыми OP, кажется вполне разумной.

Сноска: использование перемешивания для получения уникальной последовательности псевдослучайных чисел

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

Сноска: Криптографически безопасные ГПСЧ

Алгоритм МП не является криптографически безопасным, поскольку относительно легко вывести внутреннее состояние генератора, наблюдая за последовательностью чисел. Другие алгоритмы, такие как Blum Blum Shub , используются для криптографических приложений, но могут быть неподходящими для моделирования или общих приложений случайных чисел. Криптографически безопасные ГПСЧ могут быть дорогими (возможно, требующими больших вычислений) или могут не иметь хороших геометрических свойств. В случае этого типа алгоритма основное требование состоит в том, чтобы с вычислительной точки зрения было невозможно вывести внутреннее состояние генератора, наблюдая за последовательностью значений.

обеспокоены TunbridgeWells
источник
Одно исправление: при правильном использовании ГПСЧ на основе LCG не гарантируется уникальный результат для всего цикла. Например, традиционный Turbo Pascal LCG имеет (IIRC) 31 бит внутреннего состояния, но он генерирует только 15-битные числа, которые могут повторяться и повторяются в течение одного цикла.
Porculus
46

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

Между прочим, randomмодуль на Python использует ГПСЧ-вращатель Мерсенна , который считается очень хорошим, имеет огромный срок эксплуатации и был тщательно протестирован. Так что будьте уверены, что вы в надежных руках.

Эли Бендерский
источник
42

Если вы не хотите повторения, сгенерируйте последовательный массив и используйте random.shuffle

ТЫ
источник
3
Боже, я люблю random.shuffle. Это одно из стержней моего проекта :)
PizzAzzra
40

В ответ на ответ Нимбуза:

http://xkcd.com/221/

альтернативный текст

Творог
источник
7
RFC 1149.5 определяет 4 как стандартное случайное число, проверенное IEEE.
Zano
15

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

Если вы когда-нибудь бросали кости, вы наверняка довольно часто получали 3 шестерки подряд ...

Ber
источник
4

Это не повторитель. Репитер - это когда вы повторяете одну и ту же последовательность . Не одно число.

Леннарт Регебро
источник
4

Вы генерируете 4500случайные числа из диапазона 500 <= x <= 5000. Затем вы проверяете, был ли каждый номер создан ранее. Задача дня рождения говорит нам, какова вероятность совпадения двух из этих чисел при заданных nпопытках за пределами диапазонаd .

Вы также можете инвертировать формулу, чтобы вычислить, сколько чисел вам нужно сгенерировать, пока вероятность создания дубликата не превысит 50%. В этом случае у вас есть >50%шанс найти повторяющееся число после 79итераций.

liwp
источник
1

Вы определили случайное пространство из 4501 значения (500-5000) и выполняете итерацию 4500 раз. Вы в основном гарантированно получите коллизию в написанном вами тесте.

Чтобы подумать об этом по-другому:

  • Когда результирующий массив пуст P (dupe) = 0
  • 1 значение в массиве P (дублирование) = 1/4500
  • 2 значения в массиве P (дублирование) = 2/4500
  • и т.п.

Таким образом, к тому времени, когда вы дойдете до 45/4500, вероятность того, что эта вставка будет дубликатом, составляет 1%, и эта вероятность будет расти с каждой последующей вставкой.

Чтобы создать тест, который действительно проверяет возможности случайной функции, увеличьте вселенную возможных случайных значений (например: 500-500000). Вы можете получить или не получить обман. Но в среднем вы получите гораздо больше итераций.

французский
источник
3
Ваша математика неверна из-за проблемы с днем ​​рождения. Смотрите другие ответы. После 45 вставок у вас есть 1% шанс повторить первую вставку, но у вас также есть 44 других отдельных вставки, которые вы могли повторить.
jcdyer
0

Для всех, кто столкнулся с этой проблемой, я использовал uuid.uuid4 (), и он отлично работает.

орокусаки
источник
3
Тогда вопрос можно было бы лучше сформулировать так: «Я хочу сгенерировать серию неповторяющихся чисел, похоже, Python randint () этого не делает - что делает?» а не «Генератор случайных чисел в Python плохой» :-) Если предположить, что uuid4 () действительно случайный, он все равно может повторяться - что очень маловероятно. Какие фактические свойства вы хотите от цифр? Не повторяется? Случайно? (Выберите один.) Не повторяется часто? (Используйте больший диапазон INT, эффективно все uuid4, это кажется.) Что именно вы хотите использовать числа для реального вопроса.
agnoster
@agnoster Я действительно не собирался оскорблять Python, но случайный: отсутствие предсказуемости, без какого-либо систематического шаблона и повторяющийся шаблон: шаблон группы элементов, который повторяется снова и снова. Видите ли, случайный генератор не является случайным, если он повторяется, потому что тогда он имеет шаблон.
орокусаки
9
Ваше определение «случайного» неверно. Серьезно, вернитесь и перечитайте отрывки о парадоксе дня рождения. По-настоящему генератор случайных чисел будет повторяться гораздо чаще, чем вы ожидаете интуитивно. Как указывает @ConcernedOfTunbridgeW, вероятность повторения в диапазоне 500-5000 в пределах первых 100 чисел составляет ~ 66%, что, я считаю, совсем не противоречит тому, что вы наблюдали. Случайность не означает «без повторов», это просто означает ... ну, случайность. Фактически, если вы гарантируете отсутствие повторов, генератор должен быть менее случайным, чтобы обеспечить это.
agnoster
1
Вопрос о том, для чего вам нужны эти числа, все еще остается в силе. Если вам нужны неповторяющиеся числа, почему? uuid4 () (если он действительно случайный) не отличается от randint () с очень большим диапазоном. Если вы хотите, чтобы последовательность была трудно угадываемой, устранение повторов на самом деле причиняет вам боль, потому что, когда я вижу число, скажем, 33, я понимаю, что все, что будет дальше , не содержит 33. Так что запрет на повторение на самом деле делает вашу последовательность более предсказуемой, понимаете?
agnoster
0

Есть парадокс дня рождения. Принимая это во внимание, вы понимаете, что вы говорите, что нахождение «764, 3875, 4290, 4378, 764» или что-то в этом роде не является случайным, потому что число в этой последовательности повторяется. Верный способ сделать это - сравнить последовательности друг с другом. Для этого я написал скрипт на Python.

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)
малиновый парень
источник
Этот ответ был дан много лет назад (см. Выбранный ответ выше). Это не называется парадоксом дня рождения, поскольку это не парадокс, а проблема дня рождения.
orokusaki