Gerador de números aleatórios com defeito?

Question

eu usei esse gerador de números aleatórios ponderados.

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

do seguinte modo:

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

Eu vejo com bastante frequência 7, 8, 9, 10 no resultado.

Existe alguma prova ou garantia de que isso está correto para a teoria da probabilidade?

Answer 1

Isso é matematicamente correto.É uma aplicação de amostragem por transformada inversa (embora a razão pela qual funciona neste caso deva ser relativamente intuitiva).

Não conheço Python, então não posso dizer se há alguma sutileza que torne essa implementação específica inválida.

Answer 2

Editar:como uma nota rodapé:Eu acho que seu código é equivalente a

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)

Resposta original:

O método está correto.Abaixo segue um exemplo completo, criando a tabela de frequências e comparando com os pesos solicitados.

Com 100.000 iterações, nada indica que você não obteve o que solicitou.O 'esperado' é a probabilidade que você solicitou, 'obteve' é a fração de vezes que você realmente obteve esse valor.A proporção deve ser próxima de 1 e é:

  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. 

Aqui está o código:

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