Timeline for How to generate numbers based on an arbitrary discrete distribution?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2013 at 11:44 | comment | added | probabilityislogic | Just to add a quick note on sorting - this will be effective only if you do it once at the start of a sampling scheme - so it won't do well for cases where the probabilities are themselves sampled as part of a larger overall scheme (eg. $p_{j}\sim\text{Dist}$ and then $Pr(Y=j)=p_{j}$). By sorting in this case you are adding the sorting operation into every iteration of sampling - which will be adding $O(n\log(n))$ time to each iteration. However, it may be useful to sort by an approximate guess at the size of the probabilities at the start in this case. | |
| Apr 21, 2012 at 16:35 | comment | added | jbowman | The algorithm is faster if you sort the categories in decreasing order of probability. That way, you do fewer tests (on average) per random number generated. | |
| Apr 20, 2012 at 23:59 | history | answered | David M Kaplan | CC BY-SA 3.0 |