Rejection method

The rejection method (also acceptance rejection method ; rejection sampling ) is a method for generating random numbers for a given distribution and goes back to John von Neumann . It can be used when the inversion of the distribution function is not possible or too complex.

idea

${\displaystyle F\,}$be the distribution function of the distribution for which random numbers are to be generated. be an auxiliary distribution function for which  random numbers can be generated in a simple way - for example using the inversion method. Let it be further and the associated densities . ${\displaystyle G\,}$ ${\displaystyle f\,}$ ${\displaystyle g\,}$

In order to be able to apply the rejection method, a constant must also exist, so that is satisfied for each . This is needed because the area under a density function is always 1. Without the prefactor, there would inevitably be positions . ${\displaystyle k\in \mathbb {R} }$ ${\displaystyle f(x)\leq k\cdot g(x)}$ ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle f(x)>g(x)}$

Let us now be standard random numbers and random numbers that satisfy the distribution function . ${\displaystyle u_{i}\,}$ ${\displaystyle v_{i}\,}$ ${\displaystyle G\,}$

Then the random number of the distribution function is sufficient . In a sense, you are waiting for a first hit that is below . ${\displaystyle j:=\inf\{n\geq 1\mid k\cdot u_{n}\cdot g(v_{n})<f(v_{n})\}}$ ${\displaystyle x:=v_{j}}$ ${\displaystyle F}$ ${\displaystyle f}$

In other words: random numbers are generated according to the distribution function, and the number becomes with the probability ${\displaystyle v_{i}}$ ${\displaystyle G}$ ${\displaystyle v_{n}}$

${\displaystyle p={\frac {f(v_{n})}{k\cdot g(v_{n})}}}$

accepted (acceptance), i.e. when it is the first time . The preceding random numbers are rejected (rejection). ${\displaystyle u_{n}<p}$

Simple example

In order to choose a random number , whereby each number should occur with the same probability , one can throw a conventional dice . If a 6 appears, you roll again. Usually, however, a number between 1 and 5 (inclusive) will appear on the first throw. ${\displaystyle \{1,2,3,4,5\}}$ ${\displaystyle {\tfrac {1}{5}}}$

implementation

In terms of programming, the rejection method is generally implemented as the following pseudocode :

   function F_verteilte_Zufallszahl()
     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 passes is (see below, efficiency ). ${\displaystyle k}$

Graphic illustration

Example: The first hit is indicated by C here

One can imagine the method in such a way that in the xy-plane between the x-axis and the graph of random points evenly distributed on the surface are scattered. As the x-coordinate of the point , take the G-distributed random number , and the y coordinate is obtained from the standard distributed number : . ${\displaystyle k\cdot g(x)}$ ${\displaystyle i}$ ${\displaystyle v_{i}}$ ${\displaystyle u_{i}}$ ${\displaystyle y_{i}=u_{i}\cdot k\cdot g(v_{i})}$

Of these random points, those above the graph of ( ) are discarded . The x-coordinates of the remaining points are then distributed according to the density function . ${\displaystyle f(x)}$ ${\displaystyle y_{i}>f(v_{i})}$ ${\displaystyle f(x)}$

In order to generate a random number according to this distribution, new random points are generated until one is below (point C in the picture). Its x-coordinate is the random number we are looking for. ${\displaystyle f(x)}$

Efficiency

The area under the density function is 1, and under is the area accordingly . Therefore, standard random numbers and random numbers that suffice have to be consumed on average until the first hit is achieved. It is therefore advantageous if the auxiliary density approximates the density as well as possible so that one can choose small. ${\displaystyle f(x)}$ ${\displaystyle k\cdot g(x)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle k}$

literature

• Donald E. Knuth : The Art of Computer Programming . Volume 2: Seminumerical Algorithms. 3. Edition. Addison-Wesley, Reading MA et al. a. 1997, ISBN 0-201-89684-2 , pp. 120ff. ( Addison-Wesley Series in Computer Science and Information Processing ).
• Luc Devroye: Non-Uniform Random Variate Generation . (PDF) Springer-Verlag, New York NY a. a. 1986, ISBN 0-387-96305-7 , p. 41ff.

Individual evidence

1. ^ John von Neumann: Various techniques used in connection with random digits. Monte Carlo methods . In: Nat. Bureau Standards , 12, 1951, pp. 36-38.