의사 난수 생성기는 반복 가능성이 낮습니까?

Question

그래서 그들은 동전을 50 번 던지고 50 번 머리에 올리면 다음 플립의 50/50이고 다음 플립의 1/4은 여전히 ​​그렇다고 말합니다. 이 같은 원칙이 컴퓨터 의사 난수 발생기에 적용되는지 생각하십니까? 나는 그들이 긴 뻗기를 위해 동일한 수를 반복 할 확률이 적다는 것을 이론화한다.

나는 이것을 몇 번 실행했는데 그 결과는 믿을만하지만, 나는 그것이 비정상적인 결과를 얻기 위해 얼마나 많은 시간을 할애해야하는지 궁금해.

def genString(iterations): 
    mystring = '' 
    for _ in range(iterations): 
     mystring += str(random.randint(0,9)) 
    return mystring 


def repeatMax(mystring): 
    tempchar = '' 
    max = 0 
    for char in mystring: 
      if char == tempchar: 
        count += 1 
        if count > max: 
          max = count 
      else: 
       count = 0 
      tempchar = char 
    return max 


for _ in range(10): 
    stringer = genString() 
    print repeatMax(stringer) 

나는 모두 7 개와 6 개가 있습니다. 이 프로그램을 1000 번 실행하면 정규 분포를 근사치로 나타내지 않습니까? 아니면 비교적 예측 가능하다고 생각합니까? 의사 난수 생성의 예측 가능성을 이해하려고합니다.

Answer 1

특정 패턴을 생성하지 못하는 것은 PRNG의 약점이지만 반복되는 숫자가 무작위로 반복 될 확률이 너무 적어 약점을 입증하기 어렵습니다.

PRNG가 (일반적으로) 40 억 개의 숫자 시퀀스를 생성 한 다음 처음부터 다시 반복하는 것을 의미하는 32 비트 상태 만 사용하는 것은 매우 합리적입니다. 이 경우 50 코 인 플립의 순서가 일 것입니다. 아마도이 일어나지 않을 것입니다 (4 천억의 확률로 1 할 확률로 성공하면 성공할 수 없습니다). 하지만 그렇다면 이 너무 자주 나타나는 것입니다..

피상적으로 특정 생성기에 대한 더 깊은 분석없이 출력에서 ​​미리 지정된 패턴을 찾을 수 있는지 여부를 테스트하기 위해 k 차원 등분을 찾고 있습니다. 귀하의 발전기가 적어도 50 차원의 등분위를 요구한다면 당신은 적어도 한 번 50 헤드 상태를 볼 수 있습니다.

그러나 생성기가 32 비트 결과를 출력하지만 각 결과가 헤드 또는 테일에 매핑되는지 여부 만 테스트하는 경우 생성기가 k- 차원 테스트에 실패하더라도 성공 가능성이 있으며 그 가능성은 생성자와 매핑 함수의 세부 사항.

한 번에 한 비트 만 반환하도록 생성기의 구현을 조정하면 50 비트의 상태 (또는 잠재적으로 18 비트 정도)에서 50 개의 헤드를 집어 넣으려고 시도 할 수 있지만 그 생성기 아마 결함 일 것이다). 발전기가 2 ** 50 개의 가능한 모든 주를 방문한다면, 그 주 중 하나는 연속으로 50 개의 머리를 생산할 것입니다. 인접한 상태가 더 많은 0으로 시작하거나 끝나면 몇 가지 더 많은 머리를 얻을 수 있습니다.