I will present a recent result of Christiani, Pagh, and Thorup: Consider an unknown set $S=\{x_1$<$x_2 < \ldots$<$x_n\}$ of $n$ numbers, and a probability distribution $p_1,p_2,\ldots,p_n$ on this set. We can sample elements of this set, where element $x_i$ is sampled with probability $p_i$. The goal is to find the smallest element in $S$, using a ``small'' number of samples.

It is easy to see that we can find the smallest element with probability at least $1-\epsilon$, by taking $O(\log(1/\epsilon)/p_1)$ samples. For this, we must know the value of $p_1$.

I will present Confirmation Sampling: Assume we know that $p_1 = \max(p_1,p_2,\ldots,p_n)$, but we do not know the actual value of $p_1$. Then using an expected number of $O(\log(1/\epsilon)/p_1)$ samples, we find the smallest element in $S$ with probability at least $1-\epsilon$.