Timeline for Hashed coupon collector
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 7, 2019 at 6:15 | comment | added | Michael | Given a particular $h$ function, so you have values $K_1, ..., K_n$ that specify the number of customers who like each card $\{1, ..., n\}$, you can get a simple exact answer if you change the problem to assume each of the $r$ customers arrives according to an independent Poisson process of rate $\lambda$. | |
| Jun 16, 2019 at 20:44 | comment | added | John D | @Jan-ChristophSchlage-Puchta- I had hard times deriving any bound that I can work with by looking at all possible $h$ values. I'm also not looking for a tight bound, just some rough estimate on how this behaves would do, even in the case where the probability of being surjective is large. Specifically, I have $r\gg n$, and $\delta$ that can be a relatively large constant (say, 1/3). | |
| Jun 16, 2019 at 20:36 | history | edited | John D | CC BY-SA 4.0 |
added 1 character in body
|
| Jun 16, 2019 at 16:08 | comment | added | Jan-Christoph Schlage-Puchta | For any given map $h$ the probability can be computed by a weighted coupon colector problem. The distribution of $h$ can also be computed. The combination of both counting problems can become quite difficult, depending on what parameter range and what accuracy you look at. If $\delta$ is much bigger than the probability that $h$ is not surjective, you can neglect all "strange" partitions occurring as pre-image of $h$, and some standard coupon collector results suffice. If $\delta$ is close to that probability, the problem will become pretty difficult. | |
| Jun 16, 2019 at 16:00 | comment | added | Jan-Christoph Schlage-Puchta | @user44191: The random customers could either all be the one customer, that likes card 1, or all of them could be one of the two customers, who like card 2. | |
| Jun 16, 2019 at 2:25 | comment | added | user44191 | I think I must be missing something; how do you get $(1/3)^4 + (2/3)^4$? All probabilities should be dyadic, right? | |
| Jun 16, 2019 at 0:50 | review | Close votes | |||
| Jun 16, 2019 at 16:08 | |||||
| Jun 15, 2019 at 20:15 | review | First posts | |||
| Jun 15, 2019 at 21:24 | |||||
| Jun 15, 2019 at 20:14 | history | asked | John D | CC BY-SA 4.0 |