I will pre­sent a re­cent re­sult of Chris­tiani, Pagh, and Tho­rup: Con­sider an un­known set $S=\{x_1$<$x_2 < \ldots$<$x_n\}$ of $n$ num­bers, and a prob­a­bil­ity dis­tri­b­u­tion $p_1,p_2,\ldots,p_n$ on this set. We can sam­ple el­e­ments of this set, where el­e­ment $x_i$ is sam­pled with prob­a­bil­ity $p_i$. The goal is to find the small­est el­e­ment in $S$, using a ``small'' num­ber of sam­ples.

It is easy to see that we can find the small­est el­e­ment with prob­a­bil­ity at least $1-\ep­silon$, by tak­ing $O(\log(1/\ep­silon)/p_1)$ sam­ples. For this, we must know the value of $p_1$.

I will pre­sent Con­fir­ma­tion Sam­pling: As­sume we know that $p_1 = \max(p_1,p_2,\ldots,p_n)$, but we do not know the ac­tual value of $p_1$. Then using an ex­pected num­ber of $O(\log(1/\ep­silon)/p_1)$ sam­ples, we find the small­est el­e­ment in $S$ with prob­a­bil­ity at least $1-\ep­silon$.