# 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

This problem is known as Good-Turing frequency estimation. It is maybe historically one of the very first methods for this kind of discrete problems.

Probability of seen/unseen is the easiest part of Good-Turing's problem. You want to estimate the probability for a randomly picked object to be "unseen". Good-Turing estimator is simply:

$$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 is the "raw" estimator. Then Good-Turing use a method known as "smoothing" but this method is mainly useful for the rest of the problem: estimating the frequencies of each object that has already been seen, especially many times. The raw estimate of the unseen is already good. You can read more here: Good-Turing without tears.

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. 