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

StackOverflow https://stackoverflow.com/questions/2145510

  •  23-09-2019
  •  | 
  •  

Вопрос

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

Это было полезно?

Решение

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


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

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

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

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

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

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

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

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

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

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

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

Коротко о парадоксе дня рождения

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

This graph shows the probability of a shared birthday as the number of people in the room increases. For 23 people the probability of two sharing a birthday is just over 50%.

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

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

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

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

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

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

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

Другие советы

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

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

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

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

http://xkcd.com/221/

alt text

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

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

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

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

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

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

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

Если подумать об этом по-другому:

  • Когда массив результатов пуст, P(dupe) = 0
  • 1 значение в массиве P(dupe) = 1/4500
  • 2 значения в массиве P(dupe) = 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)
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top