Reconstructing the number of distinct elements from a random projection 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$?

 A: Note first, that we may assume $n=D$ and all elements of the sequence distinct. 
To obtain a lower bound, we can start by considering the expectation.
Note that we can write $Z = \sum_{i=1}^{k} Z_i$, where $Z_i$ is the indicator random variable of whether $i$ lies in ${h(x_1),\ldots ,h(x_{n})}$ or not. 
Then $\mathbb{E}Z = \sum_{i=1}^{k} \mathbb{E}Z_i$.
But $Z_i$ is easy to compute. We have $Pr(Z_i = 1) = 1 - (1 - 1/k)^n$ since its complement is the probability that all $n$ values are not $i$. 
This implies that $\mathbb{E}Z = k\cdot (1 - (1 - 1/k)^n)$.
Next thing we have to consider is the variance.
Using again the indicator variables, we see that $V(Z) = \sum_{i,j=1}^{k} Cov(Z_i, Z_j) = \mathbb{E}Z_iZ_j - \mathbb{E}Z_i \cdot \mathbb{E} Z_j$.
Now, for $i \ne j$, $\mathbb{E}(1-Z_i)(1-Z_j) = Pr((1-Z_i)(1-Z_j)=1) = (1 - 2/k)^n$ since its complement is the probability that both our excluded.
This shows that $\mathbb{E}Z_iZ_j = (1-2/k)^n +\mathbb{E}Z_i + \mathbb{E}Z_j - 1$.
Plugging it back in the covariance definition, we see that $$ Cov(Z_i,Z_j) = (1-2/k)^n + 1 - 2(1-1/k)^n - (1 - (1 - 1/k)^n)^2  = (1-2/k)^n - (1-1/k)^{2n}$$ for $i \ne j$.
Also, $Var(Z_i) = (1-1/k)^n - (1-1/k)^{2n}$,
therefore $Var(Z) = k(k-1) \left( (1-2/k)^n - (1-1/k)^{2n} \right) + k\cdot \left ( (1-1/k)^n - (1-1/k)^{2n} \right) $
For a lower bound, we recall Chebyshev's Theorem:
$$ Pr(|Z-\mathbb{E}Z| \ge k \cdot \sigma) \le \frac{1}{k^2} $$
where here $\sigma = \sqrt{Var(Z)}$. 
Therefore, $ Pr(Z \ge \mathbb{E}Z - k \cdot \sigma) \ge 1 - \frac{1}{k^2} $, so letting $k = \delta^{-1/2}$, we have our answer.
One can approximate the expression $\mathbb{E}Z - k \cdot \sigma$ to obtain things that are nicer to work with, but this is essentially the answer.
