# Formula for the number of expected collisions

Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision.

Say instead that we have $m$ outputs. How many collisions can we expect in those $m$ outputs?

If there are $k$ inputs that all have the same output, we say there are $\binom{k}{2}$ collisions.

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions).
The reasoning is the obvious one; there are $\binom{m}{2}$ separate pairs, and each pair has a probability $2^{-n}$ of colliding (and hence has an expected number of collisions of $2^{-n}$), and the expected sum of a set of probabilistic values is the sum of each individual value's expectation. The probabilities are not independent (for example, if $H(x)=H(y)$ and $H(y)\ne H(z)$, we know that $H(x) \ne H(z)$); it turns out that the expected sum doesn't depend on independence.
• @rinat.io: I didn't see IamNick's question, however the answer is "those tables are addressing a different question than I did". I looked at the expected (average) number of collisions; the table looked at "at what point do you get at least one collision with the specified probability". The reason that an average of one collision doesn't occur precisely at $p=0.5$ is that you have a probability of having two collisions in the same collection; that bumps of the average, but doesn't change the probability of getting at least one collision – poncho Aug 4 '20 at 18:12