New answers tagged probability-theory
1
vote
Accepted
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 ...
1
vote
Accepted
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.♦
- 154k
Top 50 recent answers are included
Related Tags
probability-theory × 478algorithms × 103
randomized-algorithms × 74
probabilistic-algorithms × 49
algorithm-analysis × 32
information-theory × 32
machine-learning × 31
hash × 28
graphs × 26
complexity-theory × 25
combinatorics × 24
data-structures × 23
statistics × 23
hashing × 23
randomness × 22
markov-chains × 21
sampling × 20
entropy × 18
computer-networks × 16
hash-tables × 16
time-complexity × 11
sorting × 10
random-number-generator × 10
optimization × 9
trees × 9