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$ Commented Oct 18, 2022 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$ Commented Oct 18, 2022 at 14:06
  • $\begingroup$ @ Emil Jeřábek Thanks. Is this the fastest known? $\endgroup$
    – Com
    Commented Oct 18, 2022 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
    Commented Oct 18, 2022 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
    Commented Oct 20, 2022 at 0:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.