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 D-L_\delta]\ge 1-\delta$?

(We can assume that $k=\omega(D)$).

EDIT: The nice answer by @assaferan doesn't actually solves my problem. I'm trying to figure the number of distinct elements in the input sequence by looking at $Z$. If we assume that $n=D$ then I already have my answer. It's interesting for me to understand what can be done without assuming we know $D$ (i.e., using only $n,k$ and $Z$).

I guess that it'd be more accurate to state it as follows:

Assuming that we know $n,k,Z$, how can we find a good bound $L_\delta$ such that $\Pr[D> Z+L_\delta]\le \delta$?