# Estimating the probability to have already been seen

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:

$$P(X\in S)$$

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?

• Hint: as a function of the sample size, compute the chance of not seeing any outcome lying within a set of probability $p$.
– whuber
Feb 6, 2018 at 21:20
• I would say this is equivalent to the following problem: "Suppose you flipped a coin $N$ times and only ever observed heads on every flip. Given this information, what is the probability that the next flip will be tails?" This can be answered with simple Bayesian inference, with a nice Beta prior on the coin outcomes. Feb 6, 2018 at 21:22
• @Bridgeburners: it can't work because the estimator would only be a function of $n$. ($\frac{1}{n+1}$ for uniform prior). Actually it should depend a lot on what you've seen: for example if you've seen $n$ different values, then you can be quite sure you've seen only a very small part of the mass. Feb 7, 2018 at 10:44
• @whuber: I don't see what you have in mind (except $1-(1-p)^n$). I don't see how to use this... Feb 7, 2018 at 10:51

$$p_0=P(X\notin S)\approx\frac{n_1}{n}$$
where $n_1$ is the number of values that appear exactly once in the sample.
This shows the evolution of the Good-Turing estimator $p_0$ in a real life sampling session. While noisy at start-up, it becomes quite stable when reaching small values that can be used as a cutoff.