랜덤은 거의 랜덤하지 않습니까?

랜덤은 거의 랜덤하지 않습니까?

---

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 번의 반복이었다. 이것이 표준 라이브러리에서 얻을 수있는 최상의 결과입니까?

---

생일 패러독스 또는 PRNG가 생각보다 더 자주 중복을 생성하는 이유.

OP의 문제에는 몇 가지 문제가 있습니다. 하나는 위에서 언급 한 생일 패러독스 이고 두 번째는 생성되는 항목의 특성으로, 주어진 숫자가 반복되지 않는다는 것을 본질적으로 보장하지는 않습니다.

Birthday Paradox는 주어진 값이 생성기 기간 동안 두 번 이상 발생할 수있는 경우 적용됩니다. 따라서 값 샘플 내에서 중복이 발생할 수 있습니다. 생일 패러독스의 영향은 그러한 복제물을 얻을 수있는 실제 가능성이 상당히 중요하고 그 사이의 평균 기간이 생각보다 짧다는 것입니다. 지각 된 확률과 실제 확률 사이의 이러한 불협화음으로 인해 Birthday Paradox 는 순진한 직관적 추정이 크게 틀릴 가능성 이있는 인지 편향 의 좋은 예입니다 .

의사 난수 생성기 (PRNG)에 대한 간단한 입문서

문제의 첫 번째 부분은 난수 생성기의 노출 된 값을 훨씬 더 작은 숫자로 변환하여 가능한 값의 공간이 줄어든다는 것입니다. 일부 의사 난수 생성기 는 해당 기간 동안 값을 반복하지 않지만이 변환은 도메인을 훨씬 더 작은 도메인으로 변경합니다. 더 작은 도메인은 '반복 없음'조건을 무효화하므로 상당한 반복 가능성을 기대할 수 있습니다.

예를 들면 같은 일부 알고리즘, 선형 합동 PRNG는 ( A'=AX|M) 할 전체 기간 동안 보증 고유성을. LCG에서 생성 된 값에는 누산기의 전체 상태가 포함되며 추가 상태는 유지되지 않습니다. 생성기는 결정적이며 기간 내에서 숫자를 반복 할 수 없습니다. 주어진 누산기 값은 가능한 연속 값을 하나만 의미 할 수 있습니다. 따라서 각 값은 생성기 기간 내에 한 번만 발생할 수 있습니다. 그러나 이러한 PRNG의 기간은 상대적으로 작으며 (LCG 알고리즘의 일반적인 구현의 경우 약 2 ^ 30) 고유 값의 수보다 클 수 없습니다.

모든 PRNG 알고리즘이이 특성을 공유하는 것은 아닙니다. 일부는 기간 내에 주어진 값을 반복 할 수 있습니다. OP의 문제에서 Mersenne Twister 알고리즘 (Python의 임의 모듈 에서 사용됨 )은 2 ^ 32보다 훨씬 긴 기간을 갖습니다. Linear Congruential PRNG와 달리 누산기에 추가 상태가 포함되어 있으므로 결과는 순수하게 이전 출력 값의 함수가 아닙니다. 32 비트 정수 출력과 ~ 2 ^ 19937의 기간을 사용하면 이러한 보장을 제공 할 수 없습니다.

Mersenne Twister는 우수한 통계적 및 기하학적 특성과 매우 오랜 기간 동안 시뮬레이션 모델에 사용되는 PRNG에 바람직한 특성을 가지고 있기 때문에 PRNG에 널리 사용되는 알고리즘입니다.

• 좋은 통계적 특성 은 알고리즘에 의해 생성 된 숫자가 다른 숫자보다 나타날 확률이 훨씬 높은 숫자없이 균등하게 분포되어 있음을 의미합니다. 통계적 속성이 좋지 않으면 결과에 원치 않는 왜곡이 발생할 수 있습니다.

• 좋은 기하학적 특성 은 N 개의 숫자 집합이 N 차원 공간에서 초평면에 있지 않음을 의미합니다. 잘못된 기하학적 특성은 시뮬레이션 모델에서 잘못된 상관 관계를 생성하고 결과를 왜곡 할 수 있습니다.

• 긴 기간은 시퀀스가 ​​시작 부분으로 돌아 가기 전에 많은 숫자를 생성 할 수 있음을 의미합니다. 모델에 많은 수의 반복이 필요하거나 여러 시드에서 실행되어야하는 경우 일반적인 LCG 구현에서 사용할 수있는 2 ^ 30 정도의 이산 숫자로는 충분하지 않을 수 있습니다. MT19337 알고리즘은 2 ^ 19337-1 또는 약 10 ^ 5821이라는 매우 긴 기간을 갖습니다. 이에 비해 우주의 총 원자 수는 약 10 ^ 80 개로 추정됩니다.

MT19337 PRNG에 의해 생성 된 32 비트 정수는 그러한 긴 기간 동안 반복을 피하기 위해 충분한 이산 값을 나타낼 수 없습니다. 이 경우 중복 값이 ​​발생할 가능성이 높으며 샘플이 충분히 크면 불가피합니다.

간단히 말해서 생일 역설

이 문제는 원래 방에있는 두 사람이 같은 생일을 공유 할 확률로 정의됩니다. 요점은 방에 있는 두 사람이 생일을 같이 할 수 있다는 것입니다. 사람들은 방에있는 누군가가 특정 개인과 생일을 공유 할 확률로 문제를 순진하게 오해하는 경향이 있으며, 이는 사람들이 확률을 과소 평가하게 만드는 인지 편향의 원인입니다. 이것은 잘못된 가정입니다. 특정 개인과 일치해야하는 요구 사항이 없으며 두 개인이 일치 할 수 있습니다.

두 개인간에 일치가 발생할 확률은 특정 날짜에 일치 할 필요가 없기 때문에 특정 개인과 일치 할 확률보다 훨씬 높습니다. 오히려 생일이 같은 사람을 두 명만 찾으면됩니다. 이 그래프 (주제에 대한 Wikipedia 페이지에서 찾을 수 있음)에서 우리는 방에 23 명만 있으면 이런 식으로 일치하는 두 사람을 찾을 확률이 50 %임을 알 수 있습니다.

주제에 대한 Wikipedia 항목에서 멋진 요약을 얻을 수 있습니다 . 영업 이익의 문제에서, 우리는 우리의 확률을 알고 싶어 ( '사람'으로 동일시) 생성 임의의 값의 주어진 숫자에 대해 4,500 가능한 '생일'보다는 365이 어떤 순서에서 나타나는 두 개의 동일한 값을.

OP 문제에 대한 Birthday Paradox의 가능한 영향 계산

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)

This produces a sensible looking result of p=0.669 for a match occurring within 100 numbers sampled from a population of 4500 possible values. (Maybe someone could verify this and post a comment if it's wrong). From this we can see that the lengths of runs between matching numbers observed by the OP seem to be quite reasonable.

Footnote: using shuffling to get a unique sequence of pseudo-random numbers

See this answer below from S. Mark for a means of getting a guaranteed unique set of random numbers. The technique the poster refers to takes an array of numbers (which you supply, so you can make them unique) and shuffles them into a random order. Drawing the numbers in sequence from the shuffled array will give you a sequence of pseudo-random numbers that are guaranteed not to repeat.

Footnote: Cryptographically Secure PRNGs

The MT algorithm is not cryptographically secure as it is relatively easy to infer the internal state of the generator by observing a sequence of numbers. Other algorithms such as Blum Blum Shub are used for cryptographic applications but may be unsuitable for simulation or general random number applications. Cryptographically secure PRNGs may be expensive (perhaps requiring bignum calculations) or may not have good geometric properties. In the case of this type of algorithm, the primary requirement is that it should be computationally infeasible to infer the internal state of the generator by observing a sequence of values.

---

Before blaming Python, you should really brush up some probability & statistics theory. Start by reading about the birthday paradox

By the way, the random module in Python uses the Mersenne twister PRNG, which is considered very good, has an enormous period and was extensively tested. So rest assured you're in good hands.

---

If you don't want repetative one, generate sequential array and use random.shuffle

---

As an answer to the answer of Nimbuz:

http://xkcd.com/221/

---

True randomness definitely includes repetition of values before the whole set of possible values is exhausted. It would not be random otherwise, as you would be able to predict for how long a value would not be repeated.

If you ever rolled dice, you surely got 3 sixes in row quite often...

---

Python's random implementation is actually quite state of the art:

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

---

That's not a repeater. A repeater is when you repeat the same sequence. Not just one number.

---

You are generating 4500 random numbers from a range 500 <= x <= 5000. You then check to see for each number whether it has been generated before. The birthday problem tells us what the probability is for two of those numbers to match given n tries out of a range d.

You can also invert the formula to calculate how many numbers you have to generate until the chance of generating a duplicate is more than 50%. In this case you have a >50% chance of finding a duplicate number after 79 iterations.

---

You have defined a random space of 4501 values (500-5000), and you are iterating 4500 times. You are basically guaranteed to get a collision in the test you wrote.

To think about it another way:

• When the result array is empty P(dupe) = 0
• 1 value in Array P(dupe) = 1/4500
• 2 values in Array P(dupe) = 2/4500
• etc.

So by the time you get to 45/4500, that insert has a 1% chance of being a duplicate, and that probability keeps increasing with each subsequent insert.

To create a test that truly tests the abilities of the random function, increase the universe of possible random values (eg: 500-500000) You may, or may not get a dupe. But you'll get far more iterations on average.

---

For anyone else with this problem, I used uuid.uuid4() and it works like a charm.

---

생일 역설이 있습니다. 이것을 고려하면 "764, 3875, 4290, 4378, 764"또는 이와 유사한 것을 찾는 것은 그 시퀀스의 숫자가 반복되기 때문에 그다지 무작위가 아니라는 것을 알게됩니다. 이를 수행하는 진정한 방법은 시퀀스를 서로 비교하는 것입니다. 이를 위해 파이썬 스크립트를 작성했습니다.

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)

참고 URL : https://stackoverflow.com/questions/2145510/random-is-barely-random-at-all