Hash table are collision events independent

96 Views Asked by At

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?