knkn/mMath ()n:number ofmessagesm:number ofbloombitslim(1 +k:numberofhashfunctionsm->00mnknk-m)nkmm= lim(1:. lim(e=m-→80m>00(-m)mTwo potentialassumptions:m:bigenough...kn/m:constant
Math (I) n: number of messages m: number of bloom bits k: number of hash functions ( )*( ) ( ) 1 lim(1 ) 1 1 lim(1 ) lim(1 ) ( ) m m nk nk m nk m m m m e m e m m → − − − → → + = − = + = − Two potential assumptions: m: big enough. kn/m: constant
n:numberofmessagesm:numberofbloombitsk:numberofhashfunctionsInpracticetheprobabilitythata specific bitis still Oiskne-kn/m~e-kn/mrepresents the eapected fraction of o bits in the array.If thenumberofobits inthearrayis substantiallylessthanexpected,thentheprobability of a false positive will be higher than the quantity f that we computed.if X is a random variable corresponding to the number of o bits in a Bloom filter,then one can show, using the Azuma-Hoeffding inequality, that for any e > 0.P(IX - p'ml ≥ em) <2e-2e2m2 /nk
In practice n: number of messages m: number of bloom bits k: number of hash functions If the number of 0 bits in the array is substantially less than expected, then the probability of a false positive will be higher than the quantity f that we computed