欠陥のある乱数発生器？

Question

私はこの重み付けランダム数ジェネレータ

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を参照してください。

これが確率論を正しいことであるという証明または保証はありますか？

Answer 1

これは数学的に正しいです。それは 逆変換サンプリング （でも機能しますが）のアプリケーションです。この場合は比較的直感的なはずです。

私はPythonを知りませんので、このApparitualの実装を無効にする微妙なものがあるかどうかは言えません。

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反復で、あなたが要求したものを手に入れないことを示すものは何もありません。「予想される」はあなたが要求した確率です、 'got'はあなたが実際にその価値を持っている時間のほんの数です。比率は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])

.