一個碰撞需要多少個樣本（生日悖論）

只是想了解生日悖論。使用下面的代碼，我發現我需要平均12個樣本以獲得生日相撞。
不明白爲什麼它遠低於正常 23人得到一次生日碰撞的一半機會。即使我使用PyCrypto的StrongRandom，結果也不會改變。一個碰撞需要多少個樣本（生日悖論）

from random import randint 
from Crypto.Random.random import StrongRandom 
EXPERIMENTS_NUM = 10000 
SET_SIZE = 365 
SUBSET = 23 

where_collision_found = list() 
rnd = StrongRandom() 
for experiment in range(EXPERIMENTS_NUM): 
    for i in range(1,SET_SIZE + 2): 
    collision_found = False 
    #Generate a subset 
    # subset = [rnd.randint(1, SET_SIZE) for x in range(i)] 
    subset = [randint(1, SET_SIZE) for x in range(i)] 
    # Check for collision 
    flags = [False for x in range(SET_SIZE + 1)] 
    for k in range(i): 
     if flags[subset[k]]: #Collision found 
     collision_found = True 
     else: 
     flags[subset[k]] = True 

    if collision_found: 
     # print 'Collision found in set:', subset 
     break 
    where_collision_found.append(i) 
print 'average collision:', sum(where_collision_found)/float(len(where_collision_found)), 'in', EXPERIMENTS_NUM, 'experiments'

結果：
average collision: 12.1277 in 10000 experiments

來源

2016-04-03 Sergey

求和'where_collision_found'的意義是什麼？ –

只是爲了得到平均值：'sum/count' – Sergey

'where_collision_found'是一年中的某一天，如果沒有碰撞，則'366'。取其平均值不是碰撞的可能性。 –

我不是什麼你的代碼做的非常清楚。下面是我所做的只是現在：

from random import randrange 
N = 365 
ns = [] 
for _ in range(10000): 
    n = 0 
    seen = set() 
    while True: 
     b = randrange(N) 
     n += 1 
     if b in seen: 
      break 
     seen.add(b) 
    ns.append(n) 
print(sum(ns)/float(len(ns)))

和輸出從樣本來看：

24.6577

這是一件好事。你期望的「23」是分佈的中位數;預計平均值（平均值）爲24.61659 ...見這裏： https://en.wikipedia.org/wiki/Birthday_problem#Average_number_of_people

來源

2016-04-03 18:16:36

感謝您的清晰插圖，但我仍然不明白爲什麼我的代碼沒有顯示約24 ... – Sergey

我誠實地不知道你的代碼是在計算什麼。你迫使子集（真正的列表 - 選擇替換）具有許多特定的，增加的大小，這與底層問題無關。這不是需要修復的代碼 - 它是對問題的建模。我給出的代碼顯示了一個簡單的問題建模 - 並不奇怪，使用正確的*模型*結果也如預期一樣。 –

那麼，在你的例子中，迭代中的每個子集都依賴於前一個子集（因爲你只是爲它添加一個新值）。我想這不是從某一組隨機抽樣的最佳方式。在我的示例中，我在每次迭代中生成新的子集，並以某種方式影響結果。我想我真的需要研究這個主題，但不知道在哪裏（維基百科，不幸沒有幫助） – Sergey

一個碰撞需要多少個樣本（生日悖論）

回答

相關問題