Générateur de nombres aléatoires imparfaits?

Question

j'ai utilisé cette générateur de nombres aléatoires pondérés.

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.

Y a-t-il une preuve ou une garantie que cela est correct à la théorie des probabilités?

Answer 1

C'est mathématiquement correct. C'est une application de Échantillonnage de transformation inverse (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 partiale invalide.

Answer 2

Edit: comme une note latérale: je pense que votre code équivaut à

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. Vous trouverez ci-dessous un exemple complet, créant le tableau de fréquence 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ée, «Got» est la fraction des fois où vous avez réellement obtenu cette valeur. Le rapport doit ê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])