Inverse function as a method to generate rvs

In this post I attempt to explore some basic intuition about the inverse function as a method to generate random variables.

PDF and CDF

Suppose there is a probability density function f. One can easily calculate the cumulative density function F as:

F(x) = \int_{-\infty}^x f(t) dt = g_x

Where g_x \in [0, 1].

PDF – example

Let’s generate a probability density function f based on a polynomial equation k.  Suppose we want this pdf to describe the probability of some variable x \in r, where r is the region {[-4, -1] \cup [+1, +4]}. We define k arbitrarily as:

k = -(x^2 - 1)(x^2 - 16)

k

It is necessary to adjust this polynomial function to a factor of h defined by:

h = \int_{-4}^{-1} k dx + \int_{1}^{4} k dx = \frac{1044}{5}

Therefore, the probability density function f is a piecewise function defined as:

f = \begin{cases} 0 &\quad\text{if } x \in r^c \\ \frac{k}{h} &\quad\text{if } x \in r \ \end{cases}

pdf

By doing so, we can be confident that:

\int_{-\infty}^{\infty} f(t) dt = 1

CDF – example

Naturally, the cdf function is just an integral. But due to the fact that the pdf we are using is a pisewise function, we must divide the integrals across the region. So the cdf function F would have the following form:

F = \begin{cases} I_1 &\quad\text{if } x \leq -4 \\ I_2 &\quad\text{if } -4 < x \leq -1 \\ I_3 &\quad\text{if } -1 < x \leq 1 \\ I_4 &\quad\text{if } 1 < x \leq 4 \\ I_5 &\quad\text{if } 5 < x \ \end{cases}

We can figure the value of I_i intuitively.

I_1 = 0

I_2 = \int_{-4}^x \frac{k}{h} dx = \frac{1}{3132} (1408 - 240 x +85 x^3 - 3 x^5) 

I_3 = \int_{-4}^{-1} \frac{k}{h} dx = \frac{1}{2}

I_4 = \int_{-4}^{-1} \frac{k}{h} dx + \int_{1}^x \frac{k}{h} dx =  \frac{1}{3132} (1724- 240 x +85 x^3 - 3 x^5) 

I_5 = \int_{-4}^{-1} \frac{k}{h} dx + \int_{1}^4 \frac{k}{h} dx =  1

As a result we have:

cdf

Inverse function

The inverse function of F is expressed as F^{-1} such that:

F^{-1} (g_x) = x

In more general terms, if y = f(x), the inverse function  y^{-1} = f(y)  must satisfy y^{-1}(f(x))=x.

Example I

To begin with a simple example assume we have a pdf f_2 that describes the density function of an x variable:

f_2 = \begin{cases} \frac{6-3x}{6} &\quad\text{if } 0 < x \leq 2 \\ 0 &\quad\text{if } x \leq 0 \cup 2 < x \ \end{cases}

The cdf is then:

F_2  = \begin{cases} a &\quad\text{if } x \leq 0 \\ b &\quad\text{if } 0 < x \leq 2 \\ c &\quad\text{if } 2 < x \ \end{cases}

where:

a = 0

b = a +\frac{1}{6} \int_0^{x} (6-3x) dx = \frac{1}{6}(6x - \frac{3}{2} x^2)

c = a +\frac{1}{6} \int_0^{2} (6-3x) dx = 1

ex1

The inverse function f^{-1} can only be deduced on increasing f functions. For this reason, only the b component of the piecewise cdf is going to be calculated. We can easily find the solution with x = \frac{-B \pm \sqrt{B^2 - 4 A C}}{2 A}. The general approach is to define y = f(x) and solve for x.

b^{-1} = \begin{cases} 2(1-\sqrt{1-x})  \\ 2(1+\sqrt{1-x}) \ \end{cases}

Since we expect that b^{-1} (1) = 2 and b^{-1} (0) = 0 we can rule out the second solution.

 

F_2^{-1} = 2(1-\sqrt{1-x}) 

ex1_inv

Example II

If we try to follow the same steps shown in Example I to calculate the inverse function of f, we would probably fail. High order polynomial function are difficult (if not impossible) to solve with analytical methods. Therefore, a numerical method is suggested for this problem.

At a first glance, switching from an analytical approach to a numeric method does not seem appealing. Nonetheless, in many cases we are better off working on a problem with a non-parametrical estimated density function (obtained from the empirical data) that with an analytical function determined by assumptions.

The first step is to have available the numeric data of the x-axis, pdf and cdf values.

data_gn

The cdf function F maps a variable in the x-axis to only one value in the y-axis. The inverse method F^{-1} suggest the contrary; mapping the a variable form the y-axis into the x-axis.

 So let’s suppose that we want to know the value of F^{-1} (u). The first step is to find the position of the nearest value yet smaller than u in the vector containing the data of the cdf. If the value is really close, the next step would be to use the position obtained to figure out what is the correspondent x-value. Pretty straight forward, right? There would not be problem with this if the “nearest value” is indeed significantly near to u. Due to the fact that this situation is not commonly true, an interpolation technique is recommended.

To maintain simplicity, linear interpolation is frequently used. Assume that the closest value to u in the vector containing the data of the cdf is in the i-th position. Lets call the x-axis vector x and the cdf vector z. Linear interpolation uses a simple linear model to estimate the corresponding x-value for u. In essence:

\hat{x} = \frac{x[i+1]-x[i]}{z[i+1]- z[i]} (u - z[i]) + x[i]

Since we know that z[i] < u and z[i]  is the closest value smallest value to u we also know that u < z[i+1] . By definition, cdf are increasing functions so F^{-1}(z[i]) < F^{-1}(u) < F^{-1}(z[i+1]) must also hold true. As a result F^{-1}(u) \approx \hat{x} .

inverse_func

Inverse method

If there is a random variable u drawn from a uniformly distribution U[0,1], then y is a random variable with f distribution only if y = F^{-1} (u) .

Then by using random uniformly distributed variables we can simulate any distribution. The following code shows the implementation of the numeric method to calculate the inverse function.

As a result, the inverse method allowed us to generate 5000 random variables that apparently distribute according to f .

rel_ud
A simple plot showing in the x-axis the set of uniformly distributed rv and on the y-axis the rv generated when applying the inverse method. 

first50
This plot illustrates how the transformation works, taking each uniform-rv as an input and generating the desired-rv as an otuput. 
simul_rand
The frequency histogram of the desired-rv shows that they distribute as f.


As it can be seen, the inverse method approach to generate random variables is a handy tool. The methodology allows us to apply this technique with analytical or numeric methods.

In further posts, we will explore how a density distribution can be estimated via non-parametric statistics. We will enhance monte-carlo simulations by doing so and hopefully build accurate predictive models. The inverse methodology is at the core of many high level simulations.

 


 

 

 

 

 

Advertisements