Prawdopodobieństwo kolizji.

0

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ć.

0

Stricte zależy od zakresu losowo wybranych liczb. Np: liczby z zakresu 0..1
prawdopodobieństwo kolizji jest dokładnie 100%

1

@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

1
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/120
2/120+119/120118/1203/120 + ...

2

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1