<p>Assume we have <span class="math-container">$n$</span> bins, and exactly <span class="math-container">$k&gt;0$</span> 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 <span class="math-container">$ ≥ 0$</span>, such that
<span class="math-container">$E[] = 1/k$</span>.</p>
<p>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.</p>
<p>One idea is randomly pick a bin and repeat it until non empty is found. Let us say <span class="math-container">$r$</span> rounds requires then return <span class="math-container">$r/n$</span>. The runtime will be <span class="math-container">$O(n/k)$</span>. I looking for the faster known for this problem.</p>

CC BY-SA 4.0
2022-10-18T14:00:08.517Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-10-18T14:06:10.127Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-10-18T14:07:50.283Z
@
Emil Jeřábek Thanks. Is this the fastest known?
Com
CC BY-SA 4.0
2022-10-18T14:36:53.370Z
It’s the fastest known to *me* after giving it 5 minutes of thought. I have no idea if a better one is known to humanity.
Emil Jeřábek
CC BY-SA 4.0
2022-10-18T15:51:54.960Z
@EmilJeřábek, yes, yes, I think a faster one is known.  This would make an excellent homework question!  Here's a hint (in [ROT13](https://puretables.com/rot13-to-text)):
Tvira na rcfvyba > 0, V pna qb vg va rcfvyba rkcrpgrq dhrevrf.
Neal Young
CC BY-SA 4.0
2022-10-18T16:00:34.190Z
@user154062, can you please edit the post to explain the context in which your problem arises?  Also, what you have found so far?
Neal Young
CC BY-SA 4.0
2022-10-19T07:53:53.270Z
@NealYoung LOL. However: jung vs lbh erfgevpg L gb or orgjrra mreb naq bar?
mathworker21
CC BY-SA 4.0
2022-10-20T00:46:19.343Z
@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).
Neal Young
CC BY-SA 4.0
2022-10-21T12:57:29.607Z
@ 
Neal Young Above problem is related to the paper: https://arxiv.org/pdf/1711.07567.pdf
Com
CC BY-SA 4.0
2022-10-21T17:33:23.190Z
Is that paper about estimates that hold with high probability?  That would have a different answer than "in expectation" (from the post).
Neal Young
CC BY-SA 4.0
2022-10-22T02:14:19.783Z
@
Neal Young Yes true. I am looking for an answer in expectation.
Com
<reference-request>
Fastest algorithm for non-empty bins
Com
# Fastest algorithm for non-empty bins

(Asked by: username_0 on 2022-10-18)

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.

**Tags:** reference-request
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: @ Emil Jeřábek Thanks. Is this the fastest known?  
> **username_1**: It’s the fastest known to *me* after giving it 5 minutes of thought. I have no idea if a better one is known to humanity.  
> **username_2**: @EmilJeřábek, yes, yes, I think a faster one is known.  This would make an excellent homework question!  Here's a hint (in [ROT13](https://puretables.com/rot13-to-text)): Tvira na rcfvyba > 0, V pna qb vg va rcfvyba rkcrpgrq dhrevrf.  
> **username_2**: @user154062, can you please edit the post to explain the context in which your problem arises?  Also, what you have found so far?  
> **username_3**: @NealYoung LOL. However: jung vs lbh erfgevpg L gb or orgjrra mreb naq bar?  
> **username_2**: @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).  
> **username_0**: @  Neal Young Above problem is related to the paper: https://arxiv.org/pdf/1711.07567.pdf  
> **username_2**: Is that paper about estimates that hold with high probability?  That would have a different answer than "in expectation" (from the post).  
> **username_0**: @ Neal Young Yes true. I am looking for an answer in expectation.  

---

## 0 answers

