Случайное это почти случайно?

Question

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сноска: криптографически защищенные PRNG

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

Answer 2

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

Кстати, модуль random в Python использует PRNG Mersenne twister , который считается очень хорошим, имеет огромный период и был тщательно протестирован. Так что будьте уверены, что вы в хороших руках.

Answer 3

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

Answer 4

В качестве ответа на ответ Nimbuz:

http://xkcd.com/221/

Answer 5

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

Answer 9

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

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

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

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

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

Answer 10

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