Wie viele Proben für eine Kollision benötigt werden (Geburtstagsparadox)

Question

Nur versuchen, Geburtstagsparadox zu verstehen. Mit einem folgenden Code habe ich herausgefunden, dass ich im Durchschnitt 12 Proben um eine Geburtstagskollision zu bekommen brauchen.
Kann nicht verstehen, warum es viel niedriger ist als normal 23 Menschen, um eine Chance von 1/2 Geburtstagskollision zu bekommen. Das Ergebnis ändert sich nicht, selbst wenn ich StrongRandom von PyCrypto verwende.

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' 

Ergebnis:
average collision: 12.1277 in 10000 experiments

Answer 1

Ich bin nicht wirklich klar, was Ihr Code tut. Hier ist, was ich habe gerade jetzt:

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

Und Ausgabe von einem Probelauf:

24.6577 

Das ist gut. Die "23", die Sie erwarten, ist der Median der Verteilung; der Mittelwert (Durchschnitt) wird voraussichtlich 24.61659 sein ... Siehe hier: https://en.wikipedia.org/wiki/Birthday_problem#Average_number_of_people