Générateur de nombre aléatoire imparfait?

Question

J'ai utilisé this générateur de nombre aléatoire pondéré.

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 

comme suit:

# 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) 

Je vois assez souvent 7, 8, 9, 10 dans le résultat.

Existe-t-il une preuve ou une garantie que cela est correct pour la théorie des probabilités?

Answer 1

Ceci est mathématiquement correct. C'est une application de inverse transform sampling (bien que la raison pour laquelle cela fonctionne dans ce cas devrait être relativement intuitive). Je ne connais pas Python, donc je ne peux pas dire s'il y a des subtilités qui rendent cette implémentation particualr invalide.

Answer 2

Edit: comme une note de côté: Je pense que votre code est équivalent à

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) 

réponse originale:

La méthode est correcte. Voici un exemple complet, créant la table de fréquences et la comparant avec les poids demandés.

Avec 100000 itérations, rien n'indique que vous n'obtenez pas ce que vous avez demandé. Le 'attendu' est la probabilité que vous avez demandé, 'obtenu' est la fraction de fois que vous avez réellement cette valeur. Rapport devrait être proche de 1 et il est:

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. 

Voici le code:

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])