All Questions
Tagged with birthday collision-detection
4
questions
0
votes
1
answer
61
views
Collisions in a Sample [closed]
Based on birthday paradox;
Let $d$ be the set of elements randomly chosen from a set of $n$ distinct elements then
a) What is expected number of unique elements in $d$ (remaining will be repetition of ...
- 143
5
votes
1
answer
200
views
Birthday paradox - variance, parallelisation, simple proofs?
I am looking for an elementary proof of the fact that expected time for finding a colision with $n$ bins is $\sqrt{\frac{\pi n}{2}} + O(1)$. The proof that I knows relies on the asymptotic expansion ...
- 2,889
0
votes
1
answer
221
views
What is the probability of two random elements from two lists are equal? (formal proof)
Suppose $L_1$ and $L_2$ are the lists of random uniform elements with sizes $m$. The elements are from $\{0,1\}^{n}$, e.g. the binary vector in $F_2^n$. What is the probability that $x_1 \in L_1$ and $...
- 161
0
votes
1
answer
63
views
closed form of multiple in the probability of a two to one collision problem (birthday paradox).
I have a problem where I need to find the chance of finding a collision in a two to one set of size $N$. For example: Let's say I have 10 indices. There are then 5 pairs that map to the same output. ...
- 113