# Inverse Transformation

`may be most generally presented in terms of cumulative distribution function (CDF):X`

`is a continuous one. In what follows, we assume thatF(x)`

`is steadily increasing, though assuming a non-steadily increasing function with a limited number of intervals where it steadily increases leads to trivial complications and generalizations of what follows.F(x)`

`is a variate with a uniform distribution on the interval (0, 1), then the variateU`

`is ofX`

`distribution:F(x)`

- Generate a uniformly distributed random number meeting the requirements: 0 <
< 1.u - Assume
as a random number of the distributionx = G(u).F(x)

`in a closed form is often hard to find, while numerical solution to the following equation is excessively time-consuming:G(u)`

`= 0, 1, 2, ... withk`

`probability. Then the distribution function is the sum:pk`

`. If a continuous functionx`

`exists in a closed form so thatG(u)`

`is monotone, then generation of random numbers of the distributionG(u)`

`can be implemented as follows:F(x)`

- Generate a uniformly distributed random number meeting the requirements: 0 <
< 1.u - Assume
as a random number of the distributionk = floor(G(u)).F(x)

`does exist, as it is easy to prove:G(u)`

`function is too hard. An acceptable solution may be found using numerical search forG(u)`

`proceeding fromk`

`, the task is reduced to table lookup. AsF(k)`

`is a monotonically increasing function, you may use search algorithms that are considerably more efficient than exhaustive search. The efficiency is solely dependent on the size of the table.F(k)`