False positive probability Assumption:We have good hash functions,look random. Given m bits for filter and n elements,choose number k of hash functions to minimize false positives: ■Let p=Pr[cell is empty ]=(1-1/m)kne-kn/m ■Let f=Pr[false pos]=(1-p)(1-e-kn/m As k increases,more chances to find a 0,but more 1's in the array. Find optimal at k=(In 2)m/n by calculus. f=Pr[false pos]=0.61285mlm 99 False positive probability  Assumption: We have good hash functions, look random.  Given m bits for filter and n elements, choose number k of hash functions to minimize false positives:  Let  Let  As k increases, more chances to find a 0, but more 1’s in the array.  Find optimal at k = (ln 2) m / n by calculus. kn kn m p m e / Pr[cell is empty ] ( 1 1 / )      k kn m k f Pr[false pos ] ( 1 p ) ( 1 e )  /      / Pr[false pos] 0.61285m n f  