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.

  • 1
    $\begingroup$ 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. $\endgroup$ Oct 18 at 14:00
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 18 at 14:06
  • $\begingroup$ @ Emil Jeřábek Thanks. Is this the fastest known? $\endgroup$
    – Com
    Oct 18 at 14:07
  • 2
    $\begingroup$ @user154062, can you please edit the post to explain the context in which your problem arises? Also, what you have found so far? $\endgroup$
    – Neal Young
    Oct 18 at 16:00
  • 1
    $\begingroup$ @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). $\endgroup$
    – Neal Young
    Oct 20 at 0:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.