Jeżeli mamy przykładową funkcję haszującą:
a%120.
a - jest liczą naturalną.
To jakie jest prawdopodobieństwo uzyskania kolizji przy 15 losowo wybranych liczbach?
Głównie chodzi mi o wzór z którego możemy to policzyć.
Stricte zależy od zakresu losowo wybranych liczb. Np: liczby z zakresu 0..1
prawdopodobieństwo kolizji jest dokładnie 100%
@matwiej zakładając że losowania są niezależne (tzn mamy faktyczną losowość, a nie losowość wg jakiegoś rozkładu) to
- w pierwszym losowaniu szansa jest 0
- w drugim 1/120
- w trzecim 2/120
... - n-tym n-1/120
edytowane, faktycznie zaćpałem :P
Shalom napisał(a):
@matwiej zakładając że losowania są niezależne (tzn mamy faktyczną losowość, a nie losowość wg jakiegoś rozkładu) to w każdym losowaniu oprócz pierwszego masz 1/120 że trafi się kolizja. Więc efektywnie masz 141/120 = 0,1167
@Shalom, jesteś pijany czy z prawdopodobieństw miałeś dwóje?
Drugie losowanie ma szanse na kolizję 1/120, trzecie 2/120 ostatnie 14/120.
czyli 1/120+119/1202/120+119/120118/1203/120 + ...
Mozna tez policzyc prawdopodobienstwo zdarzenia odwrotnego: ze kolizja nie nastapi:
Pierwsza liczbe mozna wybrac na 120 sposobow
Druga liczbe mozna wybrac na 119 sposobow
...
Pietnasta liczba mozna wybrac na 120-15+1 sposobow
Czyli prawdopodobienstwa ze nie bedize kolizji jest p=120119...106 / (120^15)
Prawdopodobienstwo, ze kolizja nastapi wynosi 1-p