Transcript Lesson_7-RandomNumbers

ETM 607 – Random Number and
Random Variates
• Define random numbers and .pseudo-random numbers
• Generation of random numbers
• Test for random numbers
- Frequency tests
- Autocorrelation
• Random-Variate generation
- Inverse-transform technique
ETM 607 – Random Number and
Random Variates
Definitions:
Random number (Ri) – a value between 0 and 1.0, ~ U[0,1).
Random Variable – a variable with an associated probability
distribution.
Random Variable – a function that assigns a real number to each
outcome in the sample space (Feldman and Valdez-Flores).
ex. X ~ U[0,1)
Y ~ Exp(5.75)
Z ~ Normal(8.0,1.0)
ETM 607 – Random Number and
Random Variates
Random Number (Ri):
1, 0  x  1
f ( x) 
0, otherwise
E[ X ] 
ab 1

2
2
(b  a ) 2
1
V[X ] 

12
12
ETM 607 – Random Number and
Random Variates
Random Number (Ri) – statistical properties:
Uniformity – if divided into n intervals of equal length, then
the expected number of observations in each interval is n/N,
where N is the total number of observations.
Independence – the probability of a value in a particular
interval is independent of the previously generated value.
ETM 607 – Random Number and
Random Variates
Generation of Pseudo-Random Number:
Pseudo – false, or “not quite”.
Random numbers generated in a computer. Not exactly
random, but generated from an algorithm and are in fact
repeatable given same starting position (good for debugging).
ETM 607 – Random Number and
Random Variates
Generation of Pseudo-Random Number:
Goal – develop generation method such that output most
closely imitates ideal properties of uniformity and
independence.
Considerations
1. fast and efficient (in code)
2. portable to different computers
3. should have long cycles (before number pattern repeats)
4. Should be repeatable (for debugging)
5. Closely approximate true ~U[0,1)
ETM 607 – Random Number and
Random Variates
Linear Congruential Method:
Sequence of intergers: X1, X2, X3,…. Xn between 0 and m-1.
Xi+1 = (a Xi+ c) mod m
Where,
X0 - initial seed
a - multiplier
c – increment
m – modulus
Then,
Xi
Ri 
m
ETM 607 – Random Number and
Random Variates
Linear Congruential Method:
In class exercise:
Xi+1 = (a Xi+ c) mod m
Given,
X0 - 5376
a - 13
c–0
m – 10000
Find, R1 , R2 , R3 and R4
ETM 607 – Random Number and
Random Variates
Linear Congruential Method:
Why was m = 10000 effective (from a computational
perspective) in the example.
In computer algorithm, m is usually a function of 2b ,
producing same effect in binary terms.
Much research done to determine effective values of a and c to
produce long cycles, uniformity and independence.
ETM 607 – Random Number and
Random Variates
Combined Linear Congruential:
See book for combining linear congruential methods to
produce random number streams with large cycles / periods.
ETM 607 – Random Number and
Random Variates
Uniformity Tests :
Null hypothesis,
and
H0: Ri ~ U[0,1)
H1: Ri /~ U[0,1)
Level of significance, a = P(reject H0 | H0 true)
probability of rejecting the null hypothesis when in null
hypothesis is true.
Usually set a = .05 or .01, or probability is 5% or 1% of
rejecting null hypothesis when performing the test.
ETM 607 – Random Number and
Random Variates
Uniformity Tests – Kolmogorov-Smirnov:
Step 1 – rank data from smallest to largest Ri : R[1]  R[ 2]  R[3]  .....  R[ N ]
i

 R( i ) 
N

i  1

D   max  R( i ) 

1 i  N
N 


Step 2 - compute D  max

1i  N
Step 3 – compute D  max{ D  , D  }
Step 4 – Use Kolmogorov-Smirnov table A.8, selecting column associated
with significance level, and row where N is the number of observations.
Step 5 – If sample statistic D from step 3 is greater than Da, the null
hypothesis is rejected. If D <= Da, cannot detect difference between
random numbers and the uniform distribution.
ETM 607 – Random Number and
Random Variates
Uniformity Tests – Kolmogorov-Smirnov:
Excellent example in book, Ex. 7.6
insert Ex 7.6
ETM 607 – Random Number and
Random Variates
Uniformity Tests – Kolmogorov-Smirnov:
Excellent example in book, Ex. 7.6
insert Fig 7.2
ETM 607 – Random Number and
Random Variates
Uniformity Tests – Chi-Square Test:
(Oi  Ei ) 2
 
Ei
i 0
n
2
0
Where Oi is the number of observations within a
segment/range/cell, Ei is the expected number of observation
in the segment/range, and n is the number of
segments/ranges/cells.
For a uniform distribution that has n segments or ranges,
Ei 
N
n
ETM 607 – Random Number and
Random Variates
Uniformity Tests – Chi-Square Test:
Insert ex 7.7
ETM 607 – Random Number and
Random Variates
Independence Tests – Autocorrelation:
Recall correlation (r)
r = .334437
r = -1.0
r = 1.0
ETM 607 – Random Number and
Random Variates
Independence Tests – Autocorrelation:
Autocorrelation is correlation of a series of data to help
identify repeated patterns. Objective is to have autocorrelation
values near 0 for all lags.
Lag = 1, r = .171282
Lag = 3, r = -.51783
Lag is the interval
between
plotted vales.
Time series plot of 7.4.2 data
Lag = 2, r = -.16459
Lag = 5, r = .337725
ETM 607 – Random Number and
Random Variates
Independence Tests – Autocorrelation:
See book for statistical method of applying hypothesis testing
for the objective of 0 correlation at various time lags.
ETM 607 – Random Number and
Random Variates
Random-Variate Generation – Chapter 8:
Random-Variate generation is converting from a random
number (Ri) to a Random Variable, Xi ~ some distribution.
Inverse transform method:
Step 1 – compute cdf of the desired random variable X
Step 2 – Set F(X) = R where R is a random number ~U[0,1)
Step 3 – Solve F(X) = R for X in terms of R. X = F-1(R).
Step 4 – Generate random numbers Ri and compute desired
random variates:
Xi = F-1(Ri)
ETM 607 – Random Number and
Random Variates
Inverse transform method – Uniform Distibution Example:
Step 1 – compute cdf of the desired random variable X
0,
xa
xa
F ( x) 
, a xb
ba
1,
xb
Step 2 – Set F(X) = R where R is a random number ~U[0,1)
F ( x)  R 
xa
ba
Step 3 – Solve F(X) = R for X in terms of R. X = F-1(R).
R(b  a)  X  a,
X  R(b  a)  a
Step 4 – Generate random numbers Ri and compute desired
random variates:
Xi = Ri(b-a) + a
ETM 607 – Random Number and
Random Variates
Inverse transform method – Uniform Distibution Example:
Xi = F-1 (R) = Ri(b-a) + a
If Xi
~ U[5,10)
a=5
b =10
Ri
.5
.7
.1
Xi
.5(10 - 5)+5 = 7.5
.7(10 – 5) + 5 = 8.5
.1(10 – 5) + 5 = 5.5
ETM 607 – Random Number and
Random Variates
Inverse transform method – General Idea:
Mapping (or transforming) from cdf to Random Variable
Insert fig 8.2
ETM 607 – Random Number and
Random Variates
In class exercise:
Determine the inverse function F-1
for the triangular distribution.
If,
a=5
b=7
c = 10
Find X when R = .75.
2( x  a )
, a xb
(b  a )(c  a )
2(c  x)
f ( x) 
, bxc
(c  b)(c  a )
0, otherwise
0,
xa
( x  a) 2
, a xb
(b  a )(c  a )
F ( x) 
(c  x ) 2
1
, bxc
(c  b)(c  a )
1,
xc