# Simple Uniform hashing with chances of no collision

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)

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

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