[
https://issues.apache.org/jira/browse/MATH-1220?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14516401#comment-14516401
]
Otmar Ertl commented on MATH-1220:
----------------------------------
The avg. number of iterations until a random value is accepted can be bound by
a constant that is independent of the number of points and the exponent.
Therefore, the O(1) runtime complexity is ensured. See the output of the
testPerformance() unit test, which shows that the avg. number of consumed
uniformly distributed random numbers is limited, which is directly connected to
the number of iterations.
I can imagine to generalize the rejection sampling method in its basic form.
Basically, you need to define two methods, a method to generate a value from
the instrumental distribution and a method to calculate the corresponding
acceptance rate for that value. However, there are many rejection sampling
methods that do not fit into this basic scheme (see for example the Ziggurat
algorithm or the Monty Python method to generate normal distributed values).
Furthermore, defining a method to calculate the acceptance rate is not feasible
in all cases, because it restricts transformations of the inequality
(acceptance rate < uniformly distributed random value). For example, the
proposed method could also be optimized without the definition of an explicit
method for the acceptance rate (a division could be replaced in favor of a
mutliplication).
> More efficient sample() method for ZipfDistribution
> ---------------------------------------------------
>
> Key: MATH-1220
> URL: https://issues.apache.org/jira/browse/MATH-1220
> Project: Commons Math
> Issue Type: Improvement
> Reporter: Otmar Ertl
> Attachments: patch_v1
>
>
> Currently, sampling from a ZipfDistribution is very inefficient. Random
> values are generated by inverting the CDF. However, the current
> implementation uses O(N) power function evaluations to calculate the CDF for
> some point. (Here N is the number of points of the Zipf distribution.) I
> propose to use rejection sampling instead, which allows the generation of a
> single random value in constant time.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
