Rejection sampling

The rejection method ( also Acceptance - Rejection method;. Engl rejection sampling) is a method of generating random numbers to a predetermined distribution and goes back to John von Neumann. It can be used when the application of the inversion method would be difficult because of the complexities of the function.

Idea

Is in this case the distribution function of the distribution to be generated to the random numbers. is an auxiliary distribution function, to which in a simple way - can generate random numbers - such as the inversion method. There are further and its density.

To apply the rejection method, must also exist a constant, so that for each satisfied. Which is required because the surface is below a density function always 1. Without the pre-factor, therefore, there would inevitably places.

Are now standard random numbers and random numbers that satisfy the distribution function.

Then enough with the random number of the distribution function. To a certain extent is waiting for a first goal, which is below.

In other words are random numbers generated according to the distribution function, and the number is in each case with the probability

Accepted ( Acceptance ), ie when for the first time. The previous random numbers are, however, rejected ( rejection ).

Simple Example

To select a random number from where each number should occur with the same probability, we can take a conventional dice. If one 6, one throws a renewed time. Usually, however, a number between 1 and 5 ( inclusive) will already appear on the first throw.

Implementation

Programmatically, the rejection method is implemented in general as the following pseudocode:

F_verteilte_Zufallszahl function ()       var x, u       repeat         x: = G_verteilte_Zufallszahl ()         u: = gleichförmig_verteilte_Zufallszahl ()       until u * k * g ( x) < f ( x)       return x     end The expected value for the number of loop iterations (see below, efficiency).

Graphical illustration

The method can be thought of as that are scattered uniformly distributed on the surface of random points in the xy plane between the x- axis and the graph. As an x - coordinate of the point, take the G- distributed random number, and the y coordinate is obtained from the standard distributed number.

Of these random dots those are discarded, which lie above the graph of (). The x-coordinates of the remaining points are then distributed according to the density function.

To generate a random number according to this distribution, so new random points are generated until one is below ( in the image of point C). Its x -coordinate is the required random number.

Efficiency

The area under the density function is 1, and the surface accordingly. Why must the average standard random numbers and random numbers that satisfy, be consumed until the first match is achieved. Therefore, it is advantageous if the auxiliary density, the density as well as possible approximated, so that you can choose small.