Probabilidade de falsos positivos

Temos um falso positivo quando temos os k bits iguais a 1 para um elemento não pertencente a C

A probabilidade de um falso positivo p_fp após inserimos m elementos é:

• P_fp = [ 1 - ( 1 - 1/n ) ]^k = ( 1 - a^k )^k

Aplicando lim_n -> inf (1 - 1/n)^n = e⁻¹

Que pode ser aproximada por:

• P_fp ~= ( 1 - e^( -km/n ) )^k

A probabilidade de falsos positivos depende de k, m e n