Assume we have $n$ bins, and exactly $k>0$ of them, are non-empty. Furthermore, assume that we can check if a specific urn is empty in constant time. I am looking for a randomized algorithm that outputs a number $𝑌 ≥ 0$, such that $E[𝑌] = 1/k$.
I am looking for fastest algorithm which can solve the above problem in expectation. Please refer me to the paper or material which covers it.
One idea is randomly pick a bin and repeat it until non empty is found. Let us say $r$ rounds requires then return $r/n$. The runtime will be $O(n/k)$. I looking for the faster known for this problem.