Timeline for Average number of rows to fit all elements in a multiset of natural numbers
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 3, 2016 at 21:01 | vote | accept | marcella | ||
| Dec 3, 2016 at 21:01 | comment | added | Pat Devlin | Well $2n p_0$ is simply the expected number of symbols of type corresponding to $p_0$. The other calculation you could find in a lot of probability books. You want to assume say the thing is uniform over $R$ and see what the answer is (bound each tail probability by something like Chernoff and see what a union bound says). [could have a typo in that second bound; didn't think too hard] If you want tighter control, try a second moment calculation. If you want even tighter control, you have options. | |
| Dec 3, 2016 at 20:57 | comment | added | marcella | Is there a proof? | |
| Dec 3, 2016 at 20:53 | history | answered | Pat Devlin | CC BY-SA 3.0 |