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