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.
 A: 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.
