Assume we have an unknown sequence $x_1,\ldots, x_n\in \mathcal U$.
We get to observe the sequence $h(x_1),h(x_2),\ldots, h(x_n)$, where $h:\mathcal U\to \{1,\ldots, k\}$ is a random function such that for every $i\in \mathcal U$, $h(i)$ is uniformly distributed over $\{1,\ldots,k\}$ independently of all others.
Denote by $D$ the number of distinct elements in $x_1,\ldots, x_n$, and by $Z$ the number of distinct elements in $h(x_1),h(x_2),\ldots, h(x_n)$.
Obviously, we always have $Z\leq D$.
What can we say about a lower bound for $Z$?
How can we find a good bound $L_\delta$ such that $\Pr[Z\ge C-L_\delta]\ge 1-\delta$?
(We can assume that $k=\omega(D)$).