0
$\begingroup$

I know that if I have $n$ different values in an array of size $m$ (where $m>n$) under simple uniform hashing, the average probability of the total number of collisions is: $$\sum_{i=1}^{n-1}\frac{i}{m}=\frac{n(n-1)}{2m}$$

Since it is known that the probability of no collision is $$1\cdot\left(1-\frac{1}{m}\right)\cdot\left(1-\frac{2}{m}\right)\cdots\left(1-\frac{n-1}{m}\right)$$ My question is $\textbf{how to prove}$ that the chances of no collision is $\textbf{at most}$ $\left(1-\frac{n-1}{2m}\right)^n$(viewing it as an the upper bound)

$\endgroup$
2
  • $\begingroup$ What is an "average probability"? Your first sum cannot be a probability, because it can be $>1$ (for example with $m = 5$ and $n = 4$). Did you perhaps mean the expected number of collisions? $\endgroup$
    – Nathaniel
    Nov 22, 2022 at 17:03
  • $\begingroup$ @Nathaniel Although, it isnt really consequential to my later question, this link was my reference: iq.opengenus.org/probability-of-collision-in-hash/… $\endgroup$
    – Mike
    Nov 22, 2022 at 17:14

1 Answer 1

0
$\begingroup$

You want to prove the following: $$\prod\limits_{i=0}^{n-1}\left(1-\frac{i}m\right)\leqslant \left(1-\frac{n-1}{2m}\right)^n$$

One way to prove it is to prove: $$\left(1-\frac{i}m\right)\left(1-\frac{n-1-i}m\right)\leqslant\left(1-\frac{n-1}{2m}\right)^2$$ for all $i\in \{1, …, \left\lfloor\frac{n-1}2\right\rfloor\}$. This is quite feasible, it follows from the fact that the function $x\mapsto x(n-1-x)$ reach its maximum in $x=\frac{n-1}2$.

$\endgroup$
3
  • $\begingroup$ Great, many thanks! Why is the maximum of the function used here; maybe could you explain further your last statement "$x\mapsto x(n-1-x)$ reaches its maximum in $x=\frac{n-1}2$" $\endgroup$
    – Mike
    Nov 22, 2022 at 18:36
  • $\begingroup$ This is a simple function analysis. Consider the derivative of the function and find where it reaches zero. $\endgroup$
    – Nathaniel
    Nov 22, 2022 at 18:43
  • $\begingroup$ True, Thanks; Understood now. Are there any other alternative ways of showing that inequality is feasible apart from taking the derivative? $\endgroup$
    – Mike
    Nov 23, 2022 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.