New answers tagged

1 vote

Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing

What is the probability of both being in slot 1, both being in slot 2, …., both being in slot m? And since these events are separate, you can add up those m probabilities and get the probability that ...
gnasher729's user avatar
  • 27.8k
1 vote

Number of non-zero elements in intersection of two bloom filters

Focus on a particular bit position, say the $i$th bit position. Let $E$ be the event that this bit is set in $B(X) \land B(Y)$. Now all you need to do is to estimate $\Pr[E]$. Then the expected ...
D.W.'s user avatar
  • 154k

Top 50 recent answers are included