# Expected number of distinct integers found with variable stopping time

This is a simplified/special case version of a previous question.

Consider the integers $$\{1,\dots, N\}$$ for some positive integer $$N$$. Let us suppose that for each $$\{1, \dots, N\}$$ there is an associated probability $$p_1, \dots, p_N$$. We also define an integer threshold $$1 \leq n < N$$.

We sample independently and repeatedly from $$\{1,\dots, N\}$$. For each $$i \in \{1,\dots, N\}$$ we sample the integer $$i$$ with probability $$p_i$$. We sample repeatedly until we have found $$x$$ distinct integers and then stop.

I would like to know how to compute the expected number of distinct integers less than or equal to the threshold $$n$$ that have been sampled.

If we knew that we would take $$s$$ samples, we can you compute the expected number of distinct integers less than or equal to $$n$$ that have been sampled. This is

$$n-\sum_{i=1}^n(1-p_i)^s.$$

However in my problem the number of samples is itself a random variable that depends on parameter $$x$$ and the different probabilities $$p_i$$.

Bounty notes

An exact solution has been given by @forgottenarrow . However it is computationally infeasible for anything but the smallest value of $$N$$. As I would like to compute this in practice for large $$N$$ but reasonably small $$n$$, is there a more computationally efficient algorithm or approximations/lower bounds one can use?

Let $$S$$ be the set of distinct values sampled. Note that $$S$$ is a random subset of $$\{1,\dots,N\}$$ of size $$x$$. We want the expected size of the set $$\{s \in S: s \leq n\}$$. The trick to solving this is the following claim:

Claim: If $$S'$$ is the set obtained from sampling $$x$$ integers from $$\{1,\dots,N\}$$ without replacement, then $$S'$$ and $$S$$ have the same distribution. Therefore, we can instead compute the expected size of the set $$\{s \in S': s \leq n\}$$.

Proof: This is trivially true when $$x=1$$ because we need precisely one sample to get a single distinct element. Suppose this is true for sets of up to size $$x-1$$. Let $$A \subset \{1,\dots,N\}$$ be a non-random set of size $$x$$ and for any $$a \in A$$, let $$A_a = A\setminus \{a\} = \{c \in A: c \neq a\}$$. Let $$S_{-1}$$ be the first $$x-1$$ distinct integers sampled with replacement and $$S'_{-1}$$ be the set of $$x-1$$ integers sampled without replacement. Then by our inductive assumption, for any $$a \in A$$, $$P(S_{-1} = A_a) = P(S'_{-1} = A_a)$$. Let $$p_{Aa} = \sum_{i\in A_a} p_i$$.

$$P(S = A|S_{-1} = A_a) = p_a + p_ap_{Aa} + p_ap_{Aa}^2 + \dots = \frac{p_a}{1 - p_{Aa}} = P(S' = A|S'_{-1} = A_a).$$

Thus,

$$P(S= A) = \sum_{a \in A} P(S = A|S_{-1} = A_a)P(S_{-1} = A_a) = \sum_{a \in A} P(S' = A|S'_{-1} = A_a)P(S'_{-1} = A_a) = P(S'= A).$$

By induction, it follows that $$S$$ and $$S'$$ have the same distribution. $$\tag*{\blacksquare}$$

So now the problem becomes much simpler in concept. For any $$i \leq N$$, we simply need to compute $$q_i := P(i \in S')$$, or the probability that we grab $$i$$ if we sample $$x$$ times without replacement. Then the size of the set $$\{s \in S': s\leq n\}$$ will be given by $$\sum_{i=1}^n q_i$$. When the integers are sampled with uniform probability, this is easy to compute, but in general the formula is messy. We can compute it using a brute force computation. First, the probability that we choose $$i$$ immediately is $$p_i$$. The probability we choose $$i$$ on the second attempt is given by,

$$\sum_{j \neq i} p_j\frac{p_i}{1 - p_j}.$$

The probability we choose $$i$$ on the third attempt is given by,

$$\color{red}{\sum_{\{j_1,j_2\}\neq i\text{ distinct}} p_{j_2}\frac{p_{j_1}}{1 - p_{j_2}}\frac{p_i}{(1 - p_{j_2})(1 - p_{j_1})}.}$$

Generalizing and putting this all together, we get

$$\color{red}{q_i = \sum_{y = 1}^x \sum_{\substack{\{j_k \neq i\text{ distinct}\}\\k=1,\dots,y-1}}\left(\prod_{k=1}^{y-1}\frac{p_{j_k}}{\prod_{\ell = 1}^{k-1} (1 - p_{j_{\ell}})}\right)\frac{p_i}{\prod_{\ell = 1}^{y-1} (1 - p_{j_{\ell}})}.}$$

Finally,

$$E[|\{s \in S': s\leq n\}|] = E\left[\sum_{i=1}^n \mathbb{I}\{i \in S'\}\right] = \sum_{i=1}^n P(i \in S') = \sum_{i=1}^n q_i.$$

I have no idea if this can be simplified further. Note that when $$p_1 = p_2 = \cdots = p_N = 1/N$$, then the order in which we sample the integers doesn't matter. Everything simplifies really nicely and we get $$E[|\{s \in S': s\leq n\}|] = \frac{xn}{N}$$.

Edit: Of course I made a mistake in computing $$q_i$$. In the probability that $$i$$ is sampled third, we condition on the event that neither $$j_1$$ nor $$j_2$$ are sampled. This happens with probability $$(1 - p_{j_2} - p_{j_1})$$ instead of $$(1 - p_{j_2})(1 - p_{j_1})$$ giving us,

$$\sum_{\{j_1,j_2\}\neq i\text{ distinct}} p_{j_2}\frac{p_{j_1}}{1 - p_{j_2}}\frac{p_i}{(1 - p_{j_2} - p_{j_1})}.$$

Similarly, when we expand everything out, we get

$$q_i = \sum_{y = 1}^x \sum_{\substack{\{j_k \neq i\text{ distinct}\}\\k=1,\dots,y-1}}\left(\prod_{k=1}^{y-1}\frac{p_{j_k}}{1 - \left(\sum_{\ell = 1}^{k-1} p_{j_{\ell}}\right)}\right)\frac{p_i}{1 - \left(\sum_{\ell = 1}^{y-1} p_{j_{\ell}}\right)}.$$

• This looks like a completely infeasible sum to do if I have understood it correctly. Is there an approximation or are there bounds? Apr 10, 2021 at 16:58
• First, please note the edit. I made a mistake while computing that sum. We can directly lower bound the probability $q_i$ by looking at the probability that $i$ is sampled after $x$ attempts with replacement. This would give us $q_i \geq 1 - (1 - p_i)^x$. I have a rough idea how we might derive an upper bound, but I'll need to think it through a little more. I wouldn't be surprised if there is some clever recursion scheme for quickly computing that sum. I wasn't able to derive such a scheme though. Otherwise, if we had more info on $\{p_i\}$, it might be possible to come up with something. Apr 11, 2021 at 3:28
• That lower bound for $q_i$ is the same as the expectation in the question. Is it possible to get anything higher? Apr 11, 2021 at 11:13
• Give me a couple day to think about it and I'll see if I can come up with better upper/lower bounds. I'm not sure how strong they will be for very general $\{n_i\}$. Apr 11, 2021 at 20:15
• I gave it a try. The bounds I came up with ended up being pretty terrible. Hope someone else is able to come up with something good. Good luck! Apr 13, 2021 at 12:17