You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Given how complex igraph_rng_get_pois() is, this is likely quite inefficient. Another method that is likely more efficient is floor(log(1-r) / log(1-p)) where r is uniform variate from $[0,1)$. I am not sure why we're not using this, but I suspect that there must be good reasons. The current implementation is lifted from R's source code, which I am inclined to trust.
There may be precision issues with the naive implementation, especially when $p \ll 1$.
The reference they give is:
* NOTES
*
* We generate lambda as exponential with scale parameter
* p / (1 - p). Return a Poisson deviate with mean lambda.
* See Example 1.5 in Devroye (1986), Chapter 10, pages 488f.
*
* REFERENCE
*
* Devroye, L. (1986).
* Non-Uniform Random Variate Generation.
* New York: Springer-Verlag.
* Pages 488f.
This is a very old reference. There is a much more recent one we should review and possible adopt the ideas from,
Why is this important? It is critical to efficient sampling fro the $G(n,p)$ model, which is also the motivation for the Bringmann and Friedrich paper. Good precision with very small $p$ is critical for this use case.
The text was updated successfully, but these errors were encountered:
igraph's geometric sampler,
igraph_rng_get_geom()
is currently implemented as follows:Given how complex$[0,1)$ . I am not sure why we're not using this, but I suspect that there must be good reasons. The current implementation is lifted from R's source code, which I am inclined to trust.
igraph_rng_get_pois()
is, this is likely quite inefficient. Another method that is likely more efficient isfloor(log(1-r) / log(1-p))
wherer
is uniform variate fromhttps://github.com/wch/r-source/blob/trunk/src/nmath/rgeom.c
There may be precision issues with the naive implementation, especially when$p \ll 1$ .
The reference they give is:
This is a very old reference. There is a much more recent one we should review and possible adopt the ideas from,
https://link.springer.com/chapter/10.1007/978-3-642-39206-1_23
Karl Bringmann & Tobias Friedrich: Exact and Efficient Generation of Geometric Random Variates and Random Graphs https://doi.org/10.1007/978-3-642-39206-1_23
Also useful: https://peteroupc.github.io/randmisc.html#On_Geometric_Samplers
Why is this important? It is critical to efficient sampling fro the$G(n,p)$ model, which is also the motivation for the Bringmann and Friedrich paper. Good precision with very small $p$ is critical for this use case.
The text was updated successfully, but these errors were encountered: