결함있는 난수 생성기?

Question

나는 가중 난수 생성기 this을 사용했습니다.

import random 

def weighted_choice(weights): 
    totals = [] 
    running_total = 0 

    for w in weights: 
     running_total += w 
     totals.append(running_total) 

    rnd = random.random() * running_total 
    for i, total in enumerate(totals): 
     if rnd < total: 
      return i 

는 다음과 같이

# The meaning of this dict is a little confusing, so here's the explanation: 
# The keys are numbers and values are weights of its occurence and values - 1 
# are weights of its disoccurence. You can imagine it like biased coins 
# (except for 2 which is fair coin). 
probabilities = { 0 : 1.0, 1 : 1.0, 2 : 0.5, 3 : 0.45, 4 : 0.4, 5 : 0.35, 
        6 : 0.3, 7 : 0.25, 8 : 0.2, 9 : 0.15, 10 : 0.1 
        } 
    numberOfDeactivations = [] 
    for number in probabilities.keys(): 
    x = weighted_choice([probabilities[number], 1 - probabilities[number]]) 
    if x == 0: 
     numberOfDeactivations.append(number) 
    print "chance for ", repr(numberOfDeactivations) 

내가 7, 8, 9, 10 결과에 꽤 자주 참조하십시오.

이것이 확률 이론에 대한 올바른 증거가 있습니까?

Answer 1

이것은 수학적으로 정확합니다. inverse transform sampling의 응용 프로그램입니다 (이 경우 작동하는 이유는 비교적 직관적이어야합니다).

파이썬에 대해 잘 모르겠습니다. 따라서이 구현 방법을 사용할 수 없도록 만드는 미묘한 차이가 있는지 말할 수는 없습니다.

Answer 2

편집 : 보조 노트로 : 내가 생각하는 코드는

import random 
probabilities = { 0 : 1.0, 1 : 1.0, 2 : 0.5, 3 : 0.45, 4 : 0.4, 5 : 0.35, 
        6 : 0.3, 7 : 0.25, 8 : 0.2, 9 : 0.15, 10 : 0.1} 
numberOfDeactivations=filter(
     lambda kv:random.random()<=probabilities[kv] , probabilities) 

원래 대답하는 것과 같습니다

방법은 올바른 것입니다. 다음은 빈도 테이블을 만들고 요청 된 가중치와 비교하는 완전한 예입니다.

100000 번 반복으로 요청한 것을 얻지 못했다는 것을 나타내는 것은 없습니다. '예상'은 요청한 확률이며, '얻은'은 실제로 그 값을 얻은 시간의 비율입니다. 비율이 1에 가까워 야하고있다 : 여기

0, expected: 0.2128 got: 0.2107 ratio: 1.0100 
    1, expected: 0.2128 got: 0.2145 ratio: 0.9921 
    2, expected: 0.1064 got: 0.1083 ratio: 0.9825 
    3, expected: 0.0957 got: 0.0949 ratio: 1.0091 
    4, expected: 0.0851 got: 0.0860 ratio: 0.9900 
    5, expected: 0.0745 got: 0.0753 ratio: 0.9884 
    6, expected: 0.0638 got: 0.0635 ratio: 1.0050 
    7, expected: 0.0532 got: 0.0518 ratio: 1.0262 
    8, expected: 0.0426 got: 0.0418 ratio: 1.0179 
    9, expected: 0.0319 got: 0.0323 ratio: 0.9881 
10, expected: 0.0213 got: 0.0209 ratio: 1.0162 

A total of 469633 numbers where generated for this table. 

코드입니다 : "매우 자주"무엇

import random 

def weighted_choice(weights): 
    totals = [] 
    running_total = 0 
    for w in weights: 
     running_total += w 
     totals.append(running_total) 
    rnd = random.random() * running_total 
    for i, total in enumerate(totals): 
     if rnd < total: 
      return i 


counts={ k:0 for k in range(11)} 
probabilities = { 0 : 1.0, 1 : 1.0, 2 : 0.5, 3 : 0.45, 4 : 0.4, 5 : 0.35, 
        6 : 0.3, 7 : 0.25, 8 : 0.2, 9 : 0.15, 10 : 0.1 
        } 

for x in range(100000): 
    numberOfDeactivations = [] 
    for number in probabilities.keys(): 
    x = weighted_choice([probabilities[number], 1 - probabilities[number]]) 
    if x == 0: 
     numberOfDeactivations.append(number) 
    for k in numberOfDeactivations: 
    counts[k]+=1.0 

sums=sum(counts.values()) 
counts2=[x*1.0/sums for x in counts.values()] 

print "ratio expected frequency to requested:": 

# make the probabilities real probabilities instead of weights: 
psum=sum(probabilities.values()) 
for k in probabilities: 
    probabilities[k]=probabilities[k]/psum 

for k in probabilities: 
    print "%3d, expected: %6.4f got: %6.4f ratio: %6.4f" %(k,probabilities[k],counts2[k], probabilities[k]/counts2[k])