Forsythe’s algorithm

May 8, 2010

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

In connection with the Bernoulli factory post of last week, Richard Brent arXived a short historical note recalling George Forsythe’s algorithm for simulating variables with density exp{-G(x)} when 0le G(x)le 1 (the extension to any upper bound is straightforward). The idea is to avoid computing the exponential function by simulating uniforms u_i until

G(x) ge u_1 ldots ge u_{n-1} le u_n

since the probability of this event is

dfrac{G(x)^{n-1}}{(n-1)!} - dfrac{G(x)^{n}}{n!}

its expectation is exp{G(x)} and the probability that n is even is exp{-G(x)}. This turns into a generation method if the support of G is bounded. In relation with the Bernoulli factory problem, I think this has potential applications in that, when the function G(x) is replaced with an unbiased estimator the subsequent steps remain valid. This approach would indeed involve computing one single value of G(x), but this is also the case with Latuszyński et al.’s and our solutions… So I am uncertain as to whether or not this has practical implications. (Brent mentions normal simulation but this is more history than methodology.)

Filed under: R, Statistics Tagged: Bernoulli factory, George Forsythe, John von Neumann, Monte Carlo methods, normal distribution, series expansion, simulation

To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R. offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , , , , , ,

Comments are closed.


Mango solutions

RStudio homepage

Zero Inflated Models and Generalized Linear Mixed Models with R

Quantide: statistical consulting and training


CRC R books series

Contact us if you wish to help support R-bloggers, and place your banner here.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)