# Sampling from a discrete space until we've observed more than 90% of it

Suppose we run a poll with a single question. It's a free question, not multiple choice - a question like "what is your favorite food", not "who will you be voting for". There is an unknown but finite number of answers among the population, equipped with an unknown distribution. After $n$ questions, we have a set of $n$ responses, many of which will be duplicates of one another. How do we know when the set of answers we've received so far covers more than, say, 90% (in probability) of the answer space of the entire population?

Formally, let $\mathbb P$ be the set of discrete distributions on a countably infinite set which are of finite support. Let $X_1, X_2, X_3, ...$ be independently sampled from some fixed $P\in\mathbb P$. We would like a stopping time $T$ such that

$$\forall P\in\mathbb P,\quad P\big(P(\{X_1, ... X_T\})\geq1-\epsilon\big)\geq1-\alpha$$

Where $\epsilon > 0$, $\alpha > 0$ are fixed parameters.

• If there are a lot of unique answers in the population (a lot of foods that are the favourite of only one person) then you may need to sample a very large fraction of the population to see 90% of them, and you won't know that. Imagine two situations -- situation 1 has 85 pretty common choices and 15 unique ones and situation 2 has 85 common choices and 5 unique ones. After collecting a largish sample you have 87 items in your set. How can you distinguish situation 1 (where you don't have 90%) from situation 2 (where you do)? Commented May 19, 2017 at 6:53

I'll call the parameters $\epsilon, \alpha$ in the question the threshold and the level, respectively.

I don't have a full answer, but (if the below is all correct) I can construct a (likely inefficient) strategy solving the threshold $\epsilon$ problem with level $\alpha$ for any $\epsilon, \alpha$ pair, as long as the underlying distribution is assumed to be uniform (but on a set of unknown size).

Fix a function $f$ mapping positive integers to positive integers. Every time the space is sampled (polled), the response will either be an answer we've already seen, or a new answer. The strategy consists in stopping when we haven't received a new answer in "too long", where "too long" is determined by the function $f$: if we've received $n$ distinct answers so far, then we stop after a run of $f(n)$ old answers. For example, if $f$ is identically equal to $3$, we might observe the answers $1, 1, 2, 1, 2, 4, 1, 2, 4$ and then stop.

Let $P_n$ be the uniform probability distribution on an answer space of $n$ answers. Then the probability of succeeding (stopping after having observed $1-\epsilon$ of the space) is:

$$P_n(\text{Success})=\prod_{i=1}^{(1-\epsilon)n}\left[1-\left(\frac{i}{n}\right)^{f(i)}\right]\geq \prod_{i=1}^{\infty}\left[1-\left(1-\epsilon\right)^{f(i)}\right]$$

This infinite product can be bounded below quite easily by noting that, for $x\in[0, 1]$, there exists some constant $c$ such that $\log(1-y)\geq-cy$ for all $y\in[0, x]$, in particular for $y=x^{f(i)}$. Thus

$$P_n(\text{Success})\geq \exp\left(-c\sum_{i=1}^\infty(1-\epsilon)^{f(i)}\right)$$

so that by choosing $f$ to make that infinite sum sufficiently small, the right hand side can be made arbitrarily close to $1$, yielding a strategy of arbitrarily high level for any threshold $\epsilon$. For example we can take $f(i)=ki$ for sufficiently large $k$. Note that $c$ grows something like exponentially quickly as $\epsilon\to 0$, so for large thresholds, $f$ would need to grow very quickly in order to make the sum small enough to compensate, presumably yielding very inefficient strategies.