# The number of distinct samples to get distinct integers

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

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

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

• @lulu Is it clearer now?
– user35671
Commented Apr 5, 2021 at 12:52
• 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!
– lulu
Commented Apr 5, 2021 at 12:55
• @lulu you may be right that you need to know those. That would be interesting in itself.
– user35671
Commented Apr 5, 2021 at 12:56
• So we can assume that the probabilities of all $N$ integers are known?
– user
Commented Apr 5, 2021 at 13:04
• @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.
– user35671
Commented Apr 5, 2021 at 13:09

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.
If $$N$$ is large, and $$s$$ is not small, this doesn't sound practical to me, and simulation might be the best approach.