# Inverse Transformation

The probability distribution of a one-dimensional variate

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

.

Any CDF is defined on the whole real axis and is monotonically increasing, where

.

In case of continuous distribution, the cumulative distribution function

`is a continuous one. In what follows, we assume that`F(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)

Assuming the CDF steadily increases, the following single-valued inverse function should exist:

It is easy to prove that, if

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

`is of`X

`distribution:`F(x)

Thus, the inverse transformation method can be implemented as follows:

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

The only drawback of this approach is that

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

For discrete distributions, the CDF is a step function, the inverse transformation method still being applicable. For simplicity, assume that the distribution has probability mass points

`= 0, 1, 2, ... with`k

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

,

where is the maximum integer that does not exceed

`. If a continuous function`x

`exists in a closed form so that`G(u)

,

and

`is monotone, then generation of random numbers of the distribution`G(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)

For example, for the geometric distribution:

Then

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

However, for most cases finding the closed form for

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

`proceeding from`k

With tabulated values of

`, the task is reduced to table lookup. As`F(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)

You can apply an inverse transformation method to the s-dimensional quasi-random vectors. The resulting quasi-random sequence has the required s-dimensional non-uniform distribution.