Inverse Transform Sampling

by Weidong Liang

Beijing, 2014.04.03

Introduction

The inverse transform sampling method is a simple way for generating sample from a distribution, given the inverse of its cummulative distribution function.

This sampling method is based on the probability integral transform; which provides a way to convert a random variable of any given continuous distribution to one that obeys the uniform distribution. The basic idea is to generate a sample from the uniform distribution, and use the inverse of probability integeral transfrom to obtain a sample from the desired distribution. Specifically, given $ u \sim U(0, 1) $, we return $ x = CDF^{-1}(u) $ as the sample of the distribution D with cummulative distribution function $ CDF(x) $, and $ CDF^{-1}(x) $ is the inverse of $ CDF(x) $.

Simulation

For the following simulation, we use the inverse transform sampling to generate samples from the Exponential Distribution, and compare the histogram of these samples with the theoretical probability density function (pdf).

The Exponential Distribution has a simple pdf of $$ pdf(x) = \lambda \, e^{-\lambda x} $$ which can be integrated with respect to x to obtain the CDF of $$ CDF(x) = 1 - e^{-\lambda x} $$ solving for the inverse of CDF, we obtain: $$ CDF^{-1}(x) = -\frac{ln(1 - x)}{\lambda} $$ Pluging it into the inverse transform sampling algorithm; to generate $ x \sim Exp(\lambda) $, we generate $ u \sim U(0,1) $, and return $ -\frac{ln(1 - u)}{\lambda} $ as the desired sample.

Parameters:

NumberOfBuckets: NumberOfSamples: Lambda:

Algorithm

InverseTransformSampling( CDF(x) ) // Draw a sample from a distribution that has cummulative distribution function of CDF(x).

u <- U(0, 1) // generate u from a uniform random distribution [0, 1]
compute x such that u = CDF(x) // here we usually use inverse of CDF so that $ x = CDF^{-1}(u) $
return x

Implementation

Note

The exponential distribution describes the time between events in a Poisson process in which events occur continuously and independently at a constant average rate. Since its mean equals to $ \frac{1}{\lambda} $, distribution $ Exp(\lambda) $ can be used to model the waiting time between calls in a call-center having a mean waiting time of $ \frac{1}{\lambda} $ per second.