Simple Uniform hashing with chances of no collision

Question

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)

• Nathaniel: 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?
• Mike: @Nathaniel Although, it isnt really consequential to my later question, this link was my reference: iq.opengenus.org/probability-of-collision-in-hash/…

Answer 1

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$.

• Mike: 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$"
• Nathaniel: This is a simple function analysis. Consider the derivative of the function and find where it reaches zero.
• Mike: True, Thanks; Understood now. Are there any other alternative ways of showing that inequality is feasible apart from taking the derivative?