Considering a discrete variable $X$ with unknown distribution and having values in an unknown finite set, and a sample of $n$ independent observations of $X$, I want to estimate the probability that a new independent observation already belongs to the sample.
More formally, call $S$ my sample as a set, I want to estimate:
The practical application is to stop a costly sampling to discover all the possible values of a variable when this probability has (with reasonable certainly) reached a certain threshold like for example 95%: "I stop because I think the values I've not seen yet represent less than 5% of the mass".
Imagine you have sampled $X$ a hundred times, and you have seen 10 possible values:
- value A: 50 times
- value B: 25 times
- value C: 15 times
- value D: 3 times
- value E: 2 times
- 5 other values one time each
Informally you can the think that $P(A)>0.45$, $P(B)>0.20$.... Thus you can think that $P(X\in S)>0.65$ with a rather high certainty.
Similar work have been done about entropy and support estimation: Estimating the unseen. Maybe the article provides a solution to what I'm trying to do, but it's very challenging for me to read.
Do you know of any approach that would be simpler or easier to understand?