Expected number of distinct integers found with variable stopping time

Question

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?

Answer 1

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)}.$$