# Fastest algorithm for non-empty bins

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.

• Hmm. The algorithm I can think of is to independently draw two random nonempty bins by rejection sampling, and output 1 or 0 according to whether they are the same bin. This takes $2n/k$ samples in expectation. Oct 18, 2022 at 14:00
• Oh, better: draw one nonempty bin by rejection sampling (that is, keep sampling bins until you find a nonempty one), and output $s/n$, where $s$ is the number of samples you took. Oct 18, 2022 at 14:06
• @ Emil Jeřábek Thanks. Is this the fastest known?
– Com
Oct 18, 2022 at 14:07
• @user154062, can you please edit the post to explain the context in which your problem arises? Also, what you have found so far? Oct 18, 2022 at 16:00
• @mathworker21, in that case, by an adversary argument, $\Omega(n)$ queries are required, essentially because the alg must distinguish $k=1$ (when $X$ has to be one all the time) from $k=2$ (when $X$ can be 1 at most half the time). Oct 20, 2022 at 0:46