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

Я сделал это, чтобы проверить случайность 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 итерация перед повторителем. Это лучший результат, который вы можете получить от стандартной библиотеки?

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

В проблеме 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% вероятностью найти двух таких совпадений таким образом.

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

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

Для последовательности из 100 чисел у нас есть пары (см. Понимание проблемы ), которые потенциально могут совпадать (т. Е. Первое может соответствовать второму, третьему и т. Д., Второе может соответствовать третьему, четвертому и т. Д. И т. Д.), Поэтому количество потенциально возможных комбинаций больше, чем 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 , используются для криптографических приложений, но могут быть неподходящими для моделирования или общих приложений случайных чисел. Криптографически безопасные ГПСЧ могут быть дорогими (возможно, требующими больших вычислений) или могут не иметь хороших геометрических свойств. В случае этого типа алгоритма основное требование состоит в том, чтобы с вычислительной точки зрения было невозможно вывести внутреннее состояние генератора, наблюдая за последовательностью значений.

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

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

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

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

http://xkcd.com/221/

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

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

Случайная реализация Python на самом деле довольно современна:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

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

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

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

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

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

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

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

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

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

Есть парадокс дня рождения. Принимая это во внимание, вы понимаете, что вы говорите, что нахождение «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)