Computational Physics

Exercises 611

01

x

h(x)

P(x)

rejected

accepted

Figure B.1. The von Neumann method for generating nonuniform random

numbers.

two numbersvxandvywhich are both distributed according to a Gaussian. This is
called theBox–Müller method.
If we cannot find a primitive function forP, we must use a different method. A
method by Von Neumann uses at least two uniform random numbers to generate
a single nonuniform one. Suppose we want to have a distributionP(x)forxlying
betweenaandb. We start by constructing a generator whose distributionhsatisfies
h(x)>αP(x)on the interval[a,b]. A simple choice is of course the uniform
generator, but it is efficient to have a functionhwith a shape roughly similar to
that ofP. Now for everyxgenerated by theh-generator, we generate a second
random numberyuniformly between 0 and 1 and check ifyis smaller or larger
thanαP(x)/h(x).Ifyis smaller, thenxis accepted as the next random number
and ifyis larger thanαP(x)/h(x), it is rejected. The procedure is represented in
Figure B.1. Clearly, it is important to have as few rejections as possible, which can
be achieved by choosinghsuch thatαP(x)/h(x)is as close as possible to 1 forx
betweenaandb.

Exercises

B.1 Schrage’s method[5]enables us to carry out the transformationaxnmodmas it
occurs in the modulo random number generator without causing overflow, even when
axnis greater than the computer’s word size. It works as follows. Suppose that for a
givenaandm, we have two numbersqandrsatisfying

m=aq+r with 0≤r<q.