Timeline for lower bound the probability of at least L collisions
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 12, 2018 at 7:40 | vote | accept | Memphisd | ||
| Oct 12, 2018 at 3:00 | history | edited | Iosif Pinelis |
edited tags
|
|
| Oct 12, 2018 at 2:58 | answer | added | Iosif Pinelis | timeline score: 1 | |
| Oct 11, 2018 at 20:31 | answer | added | usul | timeline score: 2 | |
| Oct 11, 2018 at 8:35 | comment | added | Memphisd | @lcv Unfortunately, Markov gives a bound on not getting to many collisions, but lower bounding the probability of obtaining at least $L$ collisions seems not possible. Markov $\Pr[X\geq \alpha\cdot\mathbb{E}[X]]\leq\frac{1}{\alpha}$. For $\alpha\leq1$ the bound collapses to something trivial. Which is quite intutive, cause theoretically, it could be possible, that in most iterations far less than $L$ collisions appear and there are some where all pairs form a collision. Of course, this won't happen for the special case here, but this remains to be shown. | |
| Oct 11, 2018 at 7:53 | comment | added | lcv | If you only want to use the first moment you can use Markov’s inequality. | |
| Oct 11, 2018 at 5:51 | history | asked | Memphisd | CC BY-SA 4.0 |