Timeline for A balls and urns model for a hashing problem
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2015 at 19:01 | answer | added | esg | timeline score: 3 | |
| Mar 3, 2015 at 16:41 | vote | accept | Mark Wildon | ||
| Mar 3, 2015 at 10:31 | answer | added | Lucas | timeline score: 0 | |
| Mar 3, 2015 at 4:20 | comment | added | usul | @DouglasZare, I see the difference: I was not thinking of the hash function being fixed and unchanging throughout the process. | |
| Mar 3, 2015 at 4:16 | comment | added | Douglas Zare | @usul: I don't think your model fits the motivation. | |
| Mar 3, 2015 at 4:13 | comment | added | usul | @DouglasZare, yes, in the model I propose, I think that the expected wait time is exactly $\sum_{r=1}^{\infty} r \frac{1}{N}\left(1-\frac{1}{N}\right)^{r-1} = N$. | |
| Mar 3, 2015 at 2:58 | comment | added | Douglas Zare | @usul: There are two ways to stop. You can stop because you encounter the index of the special ball (and you would wait an average of $(N+1)/2$ before that happens) or you can stop because a different ball is sent to the same location as the special ball. Conditional on the first not happening, the second happens with probability $1/N$ each time, so in some sense you would expect to check $N$ balls before that happens. | |
| Mar 3, 2015 at 1:20 | comment | added | usul | I think your model and your motivation do not match very well. The motivation suggests a simpler model where $c$ is in an arbitrary bin $\{1,\dots,N\}$ and we throw balls uniformly at random into the $N$ bins until we hit the bin containing $c$. | |
| Mar 2, 2015 at 22:51 | answer | added | Douglas Zare | timeline score: 3 | |
| Mar 2, 2015 at 21:58 | comment | added | Douglas Zare | Why does your hash function have the same domain and range? You can ask the same thing without this restriction. | |
| Mar 2, 2015 at 19:43 | history | asked | Mark Wildon | CC BY-SA 3.0 |