von Neumann rejection

A simple and ingenious method for generating random points with a probability distribution $P(x)$ was deduced by von Neumann. Draw a plot with you probability distribution, and on the same graph, plot another curve $f(x)$ which has finite area and lies everywhere above your original distribution. We will call $f(x)$ the ``comparison function''. Generate random pairs $(x_i,y_i)$ with uniform distribution inside $f(x)$. Whenever the point lies inside the area of the original probability, we accept it, otherwise, we reject it. All the accepted points will be uniformly distributed within the original area, and therefore will have the desired distribution. The fraction of points accepted/rejected will deppend on the ratio between the two areas. The closer the comparison function $f(x)$ resembles $P(x)$, the more points will be accepted. Ideally, for $P(x)=f(x)$, all the points will be accepted, and none rejected. However, in practice, this is not always possible, but we can try to pick $f(x)$ such that we minimize the fraction of rejected points.

It only remains how to pick a number with probability $f(x)$. For this purpose, we utilize the method shown in the previous section, using a function whose indefinite intergral is know analitically, and is also analitically invertible. We then pick a random number $x$ and retrieve the corresponding $y(x)$ according to (266). Then, we generate a second random number and we use the rejection criterion.

An equivalent procedure consists of picking the second number between 0 and 1 and accept or reject according to wether is it respectively less than or greater than the ratio $P(x)/f(x)$