Forsythe’s algorithm

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 0\le 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.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: