stat341 / CM 361

Computational Statistics and Data Analysis is a course offered at the University of Waterloo
Spring 2009
Instructor: Ali Ghodsi

Sampling (Generating Random numbers)

Lecture of May 12th, 2009

In order to study statistics computationally, we need a good way to generate random numbers from various distributions using computational methods, or at least numbers whose distribution appears to be random (pseudo-random). Outside a computational setting, this is fairly easy (at least for the uniform distribution). Rolling a die, for example, produces numbers with a uniform distribution very well.

We begin by considering the simplest case: the uniform distribution.

One way to generate pseudorandom numbers is using the Multiplicative Congruential Method. This involves three integer parameters a, b, and n, and a seed variable x0. This method deterministically (based on the seed) generates a sequence of numbers with a seemingly random distribution (with some caveats). It proceeds as follows:

$x_{i+1} = ax_{i} + b \mod{n}$

Inverse Transform Method

Step 1: Draw $U~ \sim~ Unif [0,1]$.
Step 2: Compute $X = F^{-1}(U)$.
Example:
Suppose we want to draw a sample from $f(x) = \lambda e^{-\lambda x}$ where $x\gt 0$.
We need to first find $F(x)$ and then $F^{-1}$.

$F(x) = \int^x_0 \theta e^{-\theta u} du = 1 - e^{-\theta x}$


$F^{-1}(x) = \frac{-log(1-y)}{\theta}$
Now we can generate our random sample $i=1\dots n$ from $f(x)$ by:

$1)\ u_i \sim UNIF(0,1)$
$2)\ x_i = \frac{-log(1-u_i)}{\theta}$


The $x_i$ are now a random sample from $f(x)$.
The major problem with this approach is that we have to find $F^{-1}$ and for many distributions it is too difficult to find the inverse of $F(x)$.