1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Presumably $C=D$, right? $\endgroup$ Jan 29, 2017 at 17:12
  • $\begingroup$ @AnthonyQuas - yes, a typo, thanks ! – $\endgroup$
    – R B
    Jan 30, 2017 at 6:33
  • $\begingroup$ please fix the $C=D$ typo so readers aren't confused. $\endgroup$
    – kodlu
    Jan 30, 2017 at 7:08

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I think this isn't quite right. The correct question has $Z_i=1$ if $i$ does not lie in $h(x_1),\ldots,h(x_{i-1})$ (have we seen this symbol before or not?) If there is a repeat, you are removing all of the repetitions. $\endgroup$ Jan 30, 2017 at 6:54
  • 2
    $\begingroup$ @AnthonyQuas - I think that the answer is correct. Note that he sums the $Z_i$'s over $\{1,...,k\}$ and not $\{1,.,,.,n\}$. $\endgroup$
    – R B
    Jan 30, 2017 at 16:18
  • $\begingroup$ Thinking about it a bit more, this doesn't really solves my problem. I'm trying to figure the number of distinct elements in the input sequence by looking at $Z$. If I 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$). $\endgroup$
    – R B
    Feb 1, 2017 at 15:13
  • $\begingroup$ Do you have any information about the apriori distribution of D? If so, you could just use Bayes. Else, there is little you can say about the probability, only about the likelihood. $\endgroup$
    – assaferan
    Feb 2, 2017 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.