Say I have some universal hash table of size $m$ and random input data set of size $n$. Let's define $I_{i}$ indicator RV as probability that while inserting ith key to the table collision happened.

I want to bound probability that number of collisions is far from its expected value $E(|col|) = \frac {{n}\choose{2}}{m}$. For this I want to use Chernoff, $|col|=\sum{i=1}^{n}$.

But what I can not understand are the given indicator RVs $I_{i}$ mutually independent or not?

  • $\begingroup$ I think it depends on how you handle collisions. $\endgroup$ – Christian Sievers Oct 18 '16 at 1:35
  • $\begingroup$ @Christian Sievers I just increase counter and make slot used. $\endgroup$ – Nathan Oct 18 '16 at 1:36
  • $\begingroup$ You use the next slot, so that after $i$ insertions, whether there were collisions or not, $i$ slots are used? Then it seems to me that the $i+1$st entry should have collision probability $i/m$ and be independent from earlier collisions. $\endgroup$ – Christian Sievers Oct 18 '16 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.