Consider the integers $\{1,\dots, N\}$ for some large $N$. Let us suppose that for each $\{1, \dots, n\}$ there are associated probabilities $p_1, \dots, p_n$ with $n \ll N$.

We sample independently and repeatedly from $\{1,\dots, N\}$. For each $i \leq n$ we sample the integer $i$ with probability $p_i$. With probability $q= 1-\sum_{1}^np_i$ we sample some integer greater than $n$. We are not concerned with which integer in this case.

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


However I would like only to count the number of distinct samples. So, imagine I sample uniformly and independently as before but I only stop once I have sampled $s$ distinct values. At that point, what is the expected number of distinct values will are less than or equal to $n$?

As an example, say $N=10$, $n=3$ and we want $5$ distinct samples. If the samples are $\{1,5,1,1,2, 5, 6, 2, 3\}$ then we have found all three values less then or equal to $n$.

  • $\begingroup$ @lulu Is it clearer now? $\endgroup$
    – user35671
    Commented Apr 5, 2021 at 12:52
  • $\begingroup$ Not really. I don't see how it could be answered without knowing the individual probabilities for integers $>n$. As I say, a numerical example should help. Or perhaps I am just not thinking clearly this morning. In any case, good luck! $\endgroup$
    – lulu
    Commented Apr 5, 2021 at 12:55
  • $\begingroup$ @lulu you may be right that you need to know those. That would be interesting in itself. $\endgroup$
    – user35671
    Commented Apr 5, 2021 at 12:56
  • $\begingroup$ So we can assume that the probabilities of all $N $ integers are known? $\endgroup$
    – user
    Commented Apr 5, 2021 at 13:04
  • $\begingroup$ @user Yes if that is necessary. This is actually a practical question and $N$ will be large so if we can avoid using all of the probabilities that would be best but that may not be possible. $\endgroup$
    – user35671
    Commented Apr 5, 2021 at 13:09

1 Answer 1


I don't think you can do this without knowing the probability of every number, including those $>n$. We can view this as an absorbing Markov chain. The states are all sets of at most $s$ numbers from $\{1,2,\dots,N\}$. Those with cardinality $s$ are absorbing, and those with smaller cardinality are transient.

However, the chain is non-recurrent in the sense that once it leaves a state, it never returns to it, so we don't have to use matrices. For a single set $\{x\}$ the probability that it will be visited at some time is the probability that $x$ is the first sample, or $p_x$. For a doubleton $\{x,y\}$, the probability that it will be $$\frac{p_xp_y}{1-p_x}+\frac{p_yp_x}{1-p_y}$$ That is, either the first sample is $x$ and the first non-$x$ sample is $y$, or vice-versa.

Then we can continue similarly to compute the probabilities of visiting all the three-elements states and so on.

If $N$ is large, and $s$ is not small, this doesn't sound practical to me, and simulation might be the best approach.


Parallel computation is easy, of course, but you still have to know all the probabilities.


You must log in to answer this question.