Collisions in random functions

Question

Consider a random function, from $\{0, 1\}^n$ to $\{0, 1\}^n$.

For a particular string $y^{*} \in \{0, 1\}^n$ in the image of the function, in expectation over the randomness, how many strings in the domain map to $y^{*}$? Additionally, what is the variance of this distribution?

My intuition says that it should be only constantly many, at most, because a random function should not have too many collisions with high probability. But I do not know how to make this formal.

Answer 1

• $y^*$ is one of the $2^n$ strings in $\{0, 1\}^n$
• any string $x$ is mapped to $y^*$ with probability $2^{-n}$ independently of the others
• so the total number mapped to $y^*$ has a binomial distribution $\text{Bin}(2^n,2^{-n})$
• which has mean $1$
• and variance $1-2^{-n}$
• and for large $n$ is close to a Poisson distribution with parameter $1$