# Hash table are collision events independent

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?

• I think it depends on how you handle collisions. – Christian Sievers Oct 18 '16 at 1:35
• @Christian Sievers I just increase counter and make slot used. – Nathan Oct 18 '16 at 1:36
• 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. – Christian Sievers Oct 18 '16 at 11:08