1
$\begingroup$

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.

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

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.