Reconstructing the number of distinct elements from a random projection

Question

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$?

Answer 1

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.