stat341f11

Sampling - Sept 20, 2011

From [math]\displaystyle{ x ~ f(x) }[/math] sample [math]\displaystyle{ x_{1}, x_{2}, ..., x_{1000} }[/math]

Sample from uniform distribution.

Computers cant generate random numbers as they are deterministic but can produce pseudo random numbers.

Multiplicative Congruential

• involves three integers
• a, b, m
• an initial value x₀, we call the seed
• a sequence of integers is defined as

[math]\displaystyle{ x_{k+1} = (ax_{k} + b) \mod{m} }[/math]

example: a=13 b=0 m=31 x₀=1 creates a uniform histogram

• the first 30 terms in the sequence are a permutation of integers from 1 to 30 then the sequence repeats itself
• values are between 0 and m-1
• if you divide it by m-1 the result is numbers uniformly distributed in the interval of 0 and 1
• in matlab the values choosen are a=7⁵ b=0 m=2³¹-1 due to a 1988 paper showing they are optimal

Inverse Transform Method

[math]\displaystyle{ P(a\lt x\lt b)=\int_a^{b} f(x) dx }[/math]

[math]\displaystyle{ cdf=F(x)=P(X\lt =x)=\int_{-\infty}^{x} f(x) dx }[/math]

Assume cdf & cdf ^-1 can be found

Theorem: Take u~Uniform[0,1] and let [math]\displaystyle{ x=F^{-1}(u) }[/math]. Then x has distribution function [math]\displaystyle{ F() }[/math], where [math]\displaystyle{ F(x)=P(X\lt =x) }[/math]

Let [math]\displaystyle{ F^{-1}() }[/math] denote the inverse of [math]\displaystyle{ F() }[/math]

ie [math]\displaystyle{ F(x)=u \implies x=F^{-1}(u) }[/math] Take the the exponential distribution for example

[math]\displaystyle{ f(x)={\lambda}e^{-{\lambda}x} }[/math]

[math]\displaystyle{ F(x)=\int_0^x {\lambda}e^{-{\lambda}u} du }[/math]

[math]\displaystyle{ F(x)=1-{\lambda}e^{-{\lambda}x} }[/math]

[math]\displaystyle{ {\lambda}e^{-{\lambda}x}=1-F(x) }[/math]

[math]\displaystyle{ {-{\lambda}x}=ln(1-F(x)) }[/math]

[math]\displaystyle{ x=\frac{ln(1-F(x))}{-\lambda} }[/math]

[math]\displaystyle{ F^{-1}(x)=\frac{-ln(1-F(x))}{\lambda} }[/math]

1. Draw u~Uniform[0,1] 2. [math]\displaystyle{ x=\frac{-ln(1-F(u))}{\lambda} \lt math\gt p(F^{-1}(u)\lt =x) }[/math] [math]\displaystyle{ p(F(F^{-1}(u))\lt =F(x)) }[/math] [math]\displaystyle{ p(u\lt =F(x)) }[/math] [math]\displaystyle{ =F(x) }[/math] => data points generated have cdf F(x) This same technique can be applied to the discrete case Generate a discrete random variable x that has probability mass function [math]\displaystyle{ p(x=x_i)=P_i }[/math] where [math]\displaystyle{ x_0\lt x_1\lt x_2... and \sum p_i=1 }[/math] 1 u~uniform[0,1] 2 x=x_i if <math>F(x_{i-1})<u<=F(x_i)</math