3
$\begingroup$

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?

$\endgroup$
1
4
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ This looks like a completely infeasible sum to do if I have understood it correctly. Is there an approximation or are there bounds? $\endgroup$
    – graffe
    Apr 10 '21 at 16:58
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 11 '21 at 3:28
  • $\begingroup$ That lower bound for $q_i$ is the same as the expectation in the question. Is it possible to get anything higher? $\endgroup$
    – graffe
    Apr 11 '21 at 11:13
  • 1
    $\begingroup$ 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\}$. $\endgroup$ Apr 11 '21 at 20:15
  • 2
    $\begingroup$ 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! $\endgroup$ Apr 13 '21 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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