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

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

http://xkcd.com/221/

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

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

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

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

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

Ответ 10

Для кого-либо еще с этой проблемой, я использовал uuid.uuid4(), и он работает как шарм.

Ответ 11

Есть парадокс дня рождения. Принимая это во внимание, вы понимаете, что вы говорите, что поиск "764, 3875, 4290, 4378, 764" или что-то в этом роде не слишком случайен, потому что число в этой последовательности повторяется. Истинный способ сделать это - сравнить последовательности друг с другом. Я написал python script, чтобы сделать это.

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)