clase 5.pdf

7/17/2019 clase 5.pdf

http://slidepdf.com/reader/full/clase-5pdf-568e07de3a35e 1/37

Generación de Números Aleatorios

y de Variables Aleatorias

Basados en apuntes de : Dr. Jose Sepulveda, UCF

7/17/2019 clase 5.pdf


r. os . ep ve a an om um ers an an om ar ates,

Definiciones:

Los NÚMEROS ALEATORIOS son observacionesindependientes tomadas de una distribución uniforme entre0 y 1 [0,1].

Propiedades: uniformidad e independencia.

Las VARIABLE ALEATORIAS son obervacionesindependientes tomadas desde una distribución específica.Una vez elegida la distribución a partir de los datosmuestreados (e.g., para representar tiempos entre llegadasde clientes/partes, tiempos entre reparaciones, etc.), elprograma de simulación deberá generar muestras aleatoriasindependientes a partir de las distribuciones seleccionadas,lo cual es realizado generando números aleatorios yaplicando transformaciones a estos números para obtener variables aleatorias.

f x if x elsewhere E x

F x if x F x x x F x x

( ) ; . ( ) . ; /

( ) ; ( ) ; ( )

= ≤ ≤ = =

= ≤ = ≤ ≤ = ≥

1 0 1 0 05 1 12

0 0 0 1 1 1

2σ

7/17/2019 clase 5.pdf


Dr. José A. Sepúlveda Random Numbers and Random Variates, 5

Generando Números Aleatorios de la distribución U(0,1)

Propiedades de un buen generador de números (Law y Kelton, 1991):

1. Números deben ser U(0,1) y no deben mostrar correlación entre ellos,

2. Deben ser rápidos, con un bajo requerimiento de almacenamiento y cicloslargos.

3. Números deben ser reproducibles (para verificación y experimentación), y

4. Deberían permitir generar varias secuencias independientes de númerosaleatorios a partir de diferentes semillas.

Las principales técnicas de genración involucran el uso de fórmulasrecursivas, e.g., generadores lineales congruenciales. – Una vez conocido el método y la semilla, cada número en la secuencia es

conocido (e.g., no aleatorio). Ellos son llamados “ pseudo aleatorios” por quese comportan como si fueran aleatorios:

• Uniformemente distribuidos

• Sin correlación, tendencia, ciclos, etc. (se comportan como si fueranindependientes)

7/17/2019 clase 5.pdf



Generadores Lineales Congruenciales

zi = (azi-1+c) (mod m)Procedimiento básico:

1. Fijar z0 (valor de la semilla) igual a algún entero no negativo.

2. Fijar i =1.

3. Fijar zi = (azi-1+c) (mod m).

4. Fijar u i = zi/m, donde u i es el número aleatorio generado.

5. Fijar i = i + 1. Ir al paso 3.

Donde m = es el módulo, en Arena: (231-1)

a = la constante multip licativa, en Arena: 16,807, y

c = el incremento, son todas constantes enteras, con 0< m, a < m,

c < m, y z0 < m. En Arena: 0

Cuandon c>0 tenemos un GLC aditivo. Si c=0 tenemos un GLCmultiplicativo

(azi-1+c)(mod m) es el restoasociado al dividir (azi-1+c) por m.

En todos los programas de simulación se puede especificar una semilla.

7/17/2019 clase 5.pdf



Ejemplo: LCG Zi=(5 Zi-1 + 3) (mod 16) with Z0 =7

I Z I I Z I I Z I I Z I

0 7 5 10 10 9 15 4

1 6 6 5 11 0 16 7

2 1 7 12 12 3 17 6

3 8 8 15 13 2 18 1

4 11 9 14 14 13 19 8El largo del ciclo es 16. Todos los valores posibles están

incluidos en (0, 15), la cual es la secuencia máxima, ciclo m.

Para calcular el n.a. generado, dividir cada Zi por m.

7/17/2019 clase 5.pdf


. . ,

Secuencias de Números Aleatorios

Considere el GLC Zi=(13 Zi-1) (mod 64) con

Z0 =1, 2, 3, y 4

– El periodo es determinado por la semilla (largos de 16, 8,16, 4, respectivamente). Por ejemplo, con Z0 =4: la

secuencia es 4, 52, 36, 20, 4.

Test de números aleatorios: – Test de frecuencia (test de uniformidad)

– Test de corridas (test de tendencia arriba o debajo de la

media)

– Test de autocorrelación test (test de correlación)

– Test de saltos (número de dígitos entre repeticiones)

– Poker test (test de grupos de números como una mano

de poker)

7/17/2019 clase 5.pdf


Tests de bondad de ajuste :

La meta es probar formalmente las

siguientes hipótesis nulas:H0: Las Xi son una muestra

independiente de la distribución fi jada

Prueba de Chi-cuadrado

Divida el rango de en intervalos k :

[a0, a1), ... , [a j-1, a j), …, [ak-1, ak)

F̂ x( )

F̂ x( )F̂ x( )

7/17/2019 clase 5.pdf


Fije N j = números de Xi en el intervalo jE j = número esperado de Xi en el

intervalo j si estuviesen correctos

= n

Entonces las estadísticas de chi-cuadradoson dadas por

Claramente, será “ pequeña” si es

un “ buen ajuste.”

χ

2

χ 2

( χ 2

0)

F̂ x( )

F̂ x( )

F̂ x( )

F̂ x( )

7/17/2019 clase 5.pdf


Rechazamos H0 al nivel α (ej., 0.1) si

donde es el (1 - α) - cuantil

para una distribución chi-cuadrado con

k - 1 g.l. (p. 709).

χ 2 > χ k - 1, 1 - α

2

χ k - 1, 1 - α2

7/17/2019 clase 5.pdf


Densidad de Chi-cuadrado con k - 1 df

Area achurada = α

21 1k ,

f(x)

x

0

No hay rechazo Rechazo

Figura 12. La disposición para la prueba de chi-cuadrado .

7/17/2019 clase 5.pdf


Recomendaciones para elegir losintervalos k :

• Use intervalos equidistantes enlugar de intervalos de igual amplitud.

• k 3 y E j 5 para todo j

7/17/2019 clase 5.pdf


Pruebas de Kolmogorov-Smirnov (K-S)

• Dn = distancia máxima vertical entre y

Fn(x) para todo x

• No hay intervalo de especificación

• Más poderoso que la prueba de chi-cuadrado

• Sólo aplicable a distribuciones

exponenciales, normales, log normales,

Weibull, log-logísticas, y uniformes

• Cada distribución tiene sus propios valores

Críticos

• A menudo mal utilizado en paquetes de

software de simulación y libros

F̂ x( )

7/17/2019 clase 5.pdf


1.0

0

0.5

(1)x (2)x (3)x (4 )x

x

4 ( )F x

Figura 11. Muestra de la función de distribución para n = 4.

7/17/2019 clase 5.pdf


Dr. José A. Sepúlveda, P.E. Input Data Analysis, 26

• Sea X1, X2, …, Xn (datos ordenados de menor a mayor valor), el

estadístico, Dn , se calcula de la siguinete manera:

donde:

• si , la distribución docimada es rechazada.

Kolmogorov-Smirnov Test

D D Dn n n= +m a x { , } _

D in

F X ni n

i+

≤ ≤= −⎧⎨

⎩⎫⎬⎭

m a x $ ( )( )1

D F X i

nni n

i

−

≤ ≤= −

−⎧⎨⎩

⎫⎬⎭

m a x $ ( )( )1

1

D d n n> −, 1 α

7/17/2019 clase 5.pdf


Pruebas de Anderson-Darling (A-D)

• Diseñadas para detectar discrepancias

en las colas de una distribución

• Más poderoso que la prueba K-S

• También aplicable a las distribuciones

Gamma y Tipo Pearson V• Cada distribución tiene sus propios

valores críticos

• A menudo mal utilizados en paquetes desoftware de simulación

7/17/2019 clase 5.pdf


Limitaciones de tests de bondad de

ajuste :• La hipótesis nula es a menudo falsa

• El poder de las pruebas es bajo paralos tamaños pequeños o moderados de

las muestras

• El poder de las pruebas se acerca a 1 amedida que el tamaño de las muestras

aumenta, causando que la hipótesis nula

sea rechazada

• Intervalos de especificación son

críticos para pruebas de chi-cuadrado

7/17/2019 clase 5.pdf



Procedimientos para generar Variables Aleatorias

Método de la Transformada Inversa

Método de Aceptanción/Rechazo

Método de Composición

Otros métodos empleando propiedades especiales

7/17/2019 clase 5.pdf



Método de la Transformada InversaInvolucra un procedimiento de cuatro pasos:

Sea: r = un número aleatorio

F-1 = la inversa de la función distribución acumulada deseadax = la variable aleator ia deseada.

Paso 1: Encontrar la función acumulada, F (x), para la

variable aleatoria deseada

Paso 2: Generar la inversa de F, F-1(r)

Paso 3: Generar una secuencia de números aleatorios r i(independientes, identicámente distr ibuidos UN[0,1] ).

Paso 4: Fijar x i=F -1(r i). Los x i’s son las variables aleatorias.

7/17/2019 clase 5.pdf



Ejemplo 1: v.a. empírica

Considere la función masa de probabilidades que describe el

número de clientes, x, en un grupo que entra a un restaurante:

x: 1 2 3 4 5 o más

probabildad: .1 .4 .1 .3 .1

Para generar muestras aleatorias de esta distribución utilizando el método de latransformada inversa::

Paso 1: Encontrar la función acumulada, F (x), para la v.a. encuestión, dónde

Paso 2: Generar la inversa de F, F-1(r)

F x X x( ) P≡ ≤( ) .

7/17/2019 clase 5.pdf



Ejemplo 1: v.a. empírica (cont.)

0.1

0.5

1.0

F(x)

x

1 2 3 4Paso 3: Generar secuencia de n.a. (independientes, identícamente distribuidos u[0,1]).

Example: r i : .23 .71 .54

Paso 4: Fijar x i =F -1(r

i ). Las x

i ’s son las v.a.

x 1

= F -1(r 1) = F -1(.23) = 2

x 2

= F -1(r 2) = F -1(.71) = 4

x 3

= F -1(r 3) = F -1(.54) = 3

0.6

0.9

Nota: si la v.a. es continua (0<=x<=5) (línea continuamente cresciente), se deberáinterpolar entre los puntos

50

7/17/2019 clase 5.pdf



Ejemplo 2: Distribución Exponencial

f t e e t F t e e t

=

t t t t ( ) ( )/ /= = ≥ = − = − ≥

= = =

− − − −

− −

10 1 1 0

1 2 2

β λ

μ λ β σ λ β

β λ β λ

Note that Also, 2

Let

Then and

Hence,

r F t e

r e t r

t r r

t

t

= = −

− = − = −

= − − = −

−

−

( )

( ) ln( )

ln( ) ln( )

1

1 11

1

λ

λ

λ

λ β

Pasos: 1. Generar r i2. Calcular ti = -ß ln (r i)

3. Repetir las veces necesarias

7/17/2019 clase 5.pdf



Random Numbers Streams in Arena

Arena has ten random number streams (subsequencespositioned around the enti re cycle) with initial seeds:

14561 25791 31131 22553 1212132323 19991 18765 14327 32535

for s treams on e through ten (the d efault), respectively.

A new repl ication uses the final seed value from theprevious replication as the ini tial seed – Can override us ing SEEDS element

– This element also al lows to generate anti thetic samples

between successive pairs o f repli cations (r .n. r in secondreplication = r .n. 1-r generated in f ir st repl ication)

– It also allows you to get ANY number of streams (Arena canprovide seeds for them automatically)

– You can also name streams and refer to them in variables andattributes

7/17/2019 clase 5.pdf



Step 1: Find the cumulati ve d istribution function, F (x), for therandom variab le in question, where:

Step 2: Find the inverse of F(x).

Step 3: Generate a sequence of random numbers (independent,identical ly distr ibuted uniform [0,1] random variates).

Example: r i: .21 .52 .34 .07 .92 .62Step 4: Set x i = F-1(r i). The x i’s are the random variates.

F ( x ) ( X x ) f ( y ) d y

. x

. x

x

= ≤ == =

− ∞∫P r

0 0 0 33

0 0 0 13

3

Inverse Trans formation Method: An Examp le for a Continuou sRando m Var iable

F r . x , x r − = = ∴ =1 0001 3 10003

x1

3 1000 0 21 5 94= =( )( . ) .

7/17/2019 clase 5.pdf



Consider th e continuous probability d istribution for the randomvariate, x , which gives the time (in minutes) required to repair aparticular machine. The d istribution function fo r this randomvariate is given by:

Use the inverse transformation method to generate samples for this random variate.

f x

x

x x

( ) =

≤

≤ ≤≤

⎧

⎨

⎪

⎩⎪

0 f o r 0 ,

.0 0 3 x f o r 0 1 0 ,0 f o r 1 0 .

2

f x( )

10 x

Inverse Trans formation Method: An Examp le for a Continuou sRando m Var iable

7/17/2019 clase 5.pdf



Other Distributions

f t

b a

a t b F t t a

b a

r F t t a

b at a b a r

( )

( )

; ( )

( ) ( )

=−

≤ ≤ = −

−

= = −

−= + −

1

Let then

Uniform

Weibull

( )

( ) ( )[ ]

f t t e t

F t e r t r

t

t

( )

( ) , ln

/

//

= ≥

= − = = − −

− −

−

β

α α

β

β α β

α β β

1

1

0

1 1hence

7/17/2019 clase 5.pdf



Comments on the Inverse Transform Method

Disadvantages:

– The difficulty associated with finding the inverse of the cumulative

distribution function, F-1, in some cases

– Not always the most efficient approach (i.e., other methods may

require less computation time)

Advantages:

– Facilitates some variance reduction techniques (especially wheresynchronization of random numbers is needed),

– Easy to generate from truncated distributions,

– Useful for generating order statistics....e.g., generate a random variatewhich is the smallest of 5 random variables with identical distributions(application: lifetime of a system with 5 identical components in series).

D J é A S úl d R d N b d R d V i 19

7/17/2019 clase 5.pdf



Convolution Methods

The probabil ity distribution of a sum of 2 or moreindependent r.v. is cal led a convolution of the

distr ibutions of the original variables. – Example: Erlang Distribution:

( ) ( )

⇒

= =⎛

⎝ ⎜

⎞

⎠⎟

∴ = − =

∑

∑

sum of k independent exponentially distributed r.v.,

each having mean =k

where exponential

β

μ β

β β π

X x xk

X k

r k

r

i

k

i

i

k k

i

1

11

1 1

~

ln ln

( ) x k ~ ,Erlang β

D J é A S úl d R d N b d R d V i t 20

7/17/2019 clase 5.pdf



Acceptance-Rejection Method

a b

M

f(x) defined over (a,b)

It has a maximum (M) at x=c

c

f(x)

x

Procedure: 1. Generate U1 and U2 , both ~uniform(0,1)

2. Determine x=a+(b-a) U1 and f(x)

3. Determine whether U2 M > f(x)If yes, reject x, go to 1

If no, accept x

Dr José A Sepúlveda Random Numbers and Random Variates 21

7/17/2019 clase 5.pdf



Acceptance-Rejection Example

Let ( ) f x x x x( ) = − ≤ ≤60 1 0 13 2

for , thus f(x) ~ Beta(4,3)

Note: M = 2.0736 occurs at x=0.6

Let U1 = 0.52 and U2 = 0.06 , then x1 = 0.52

f

M U

( . ) ( . ) ( . ) .

( . )( . ) .

052 60 052 0 48 194

2 0736 0 06 012

3 2

2

= =

= =

⇒ accept x = 0.52


7/17/2019 clase 5.pdf



Poisson Distr ibution

When th ere are n arr ivals in on e time uni t and the average ist t t t t t t

r r

r r r e r

n n n

i

n

i

n

n

i

n

i

n

i

n

i

1 2 1 2 1

1 1

1

1 1

1

1 1

1

1

11

1

+ + + ≤ < + + + +

− ≤ < −

≥ − > ≥ >

+

+

+ − +

∑ ∑

K K

λ λ

λ λ

ln ln

ln lnΠ Π Π Πor

λ :

( )( )

Procedure: Step 1. Set n = 0, P = 1

Step 2. Generate r and replace P by P

Step 3. If P < e accept N = notherwise, reject current n, increase n by 1, and

return to step 2.

Note: E(n +1) = +1 can be quite large

n+1

-

r n+1

λ

λ

,


7/17/2019 clase 5.pdf



Example: Generate Poisson r.v.

( )( )

( )( )

( )( )

( )( )

Let = 0.2 then

Step 1. n = 0, P = 1Step 2. r

Since P < , accept N = 0

Step 1. n = 0, P = 1

Step 2. r

Since P , reject N = 0

n = 1, r reject N = 1

n = 2, r

Since P <

-

1

-

1

-

2

3

λ λ

λ

λ

e e

P

e

P

e

P

P

e

= =

= = =

= = =

≥

= = =

= = =

−

−

0 2 08187

0 4357 1 0 4357 0 4357

08353 1 08353 08353

0 9952 08353 0 9952 08313

08004 08313 08004 0 6654

. .

. , . .

. , . .

. , . . . ,

. , . . .

λ

, accept N = 2


7/17/2019 clase 5.pdf



Non-Stationary Poisson

t

λ *

ti-1 ti

t

Procedure: 1. Set t = ti-1 Generate U1 and U2

2. Replace byt t U − 1 1λ *

ln

( )3. If , set and return; otherwise, reject and repeat.U

t t t

i2 ≤ =

λ

λ *

Note: If batch arrival situation:

1. Generate next arrival using an exponential distr. (group arrives)

2. Generate group size as 1+Poisson(average=k)

[need at least one person in group]


7/17/2019 clase 5.pdf


. José . Sepú veda a do Nu be s a d a do Va a es, 5

Employing Special Properties in Generating

Random Variates

Some random variables can be expressed as functions of other random

variables. For example, if Y has a standard normal distribution, and Zhas a chi-square distribution with k degrees of freedom, then

has a Student’s t-distribution with k degrees of freedom. Therefore, in

order to generate a random variate with a chi-square distribution with k

degrees of freedom, instead of using the inverse transform method

directly (which would be difficult), use the following procedure:

1. Generate Y ~ standard normal distribution,

2. Generate Z ~ chi-square with k d.f.,

3. Compute X Y Z k = / /

X Y Z k = / /


7/17/2019 clase 5.pdf


p ,

Normal Variates

( )

[ ]

z z iid N z B z B

B z z

B R

U B

1 2 1 2

2

1

2

2

2

2

2

1/2

0 1

2

0 2

, ~ ( , ) cos ; sin

~

ln

~ ,

= =

∴ = +

∴ = −

=

Θ Θ

Θ Θ

χ

π

υ (equivalent to an expo(2))

Also, and are independent

( ) ( ) ( ) ( )Procedure: 1. Generate r and r

Let z and z

1 2

1 22 2 2 2 2

1

1/2

2 1

1/2

2. ln cos ln sin= − = −r r r r π π

( )[ ] ( )

( )[ ] ( )

Example: Let r 1

2

= == − =

= − =

=

01758 01489

2 01758 2 01489 111

2 01758 2 01489 150

2

1

1/2

2

1/2

. , .

, ln . cos . .

ln . sin . .

r

Then z

z

π

π

B

z2

z1

Θ z1 axis

z2 axis


7/17/2019 clase 5.pdf


Binomial and Geometric Distr ibutions

Binomial Distribution1. Generate n U[0,1] values

2. Count how many values are <= p

3. The number found follows a b(x;n,p)

Geometric DistributionLet

x roundup r

p

x

x

= −

− −

⎧⎨⎩

⎫⎬⎭

=

ln( )

ln( )

, , ,

1

11

0 1 3

is the number of trials before the first success,

K

. . ,

7/17/2019 clase 5.pdf


Variance Reduction: Antithetic Variates

( ) ( ) ( ) ( )

( ) ( ) ( ) ( )

( ) ( ) ( ) ( )

( )

( ) ( )

Suppose we are interested in estimating with good precision:

Let E Y E Y Y Y

e.g., Y and Y are drawn from same population.

Let Y Y Y Y

and Y ,Y

If Y and Y are independent, Cov Y ,Y = 0

But, if Cov Y ,Y < 0, thenIf we do this n times,

Y

1 2 Y 1 2

1 2

1 2 1 2 Y Y Y

1 2

1 2 1 2

1 2

μ

μ σ

μ μ μ

σ

= = = =

= + ∴ = + = + =

= + +

<

V V

z E z E E

V z V Y V Y Cov

V z

Y

Y

2

1 2

2

21

2

1

2

1

2

1

2

14

14

2 12

12

/

( ) ( )

( )

V z V Y < which was our goal

How do we ensure Cov Y ,Y < 0?

Use COMPLEMENT of r in run 2.

1 2

1


7/17/2019 clase 5.pdf


Qué hemos aprendido ...

Motivación y Definiciones

Generación de Números Aleatorios – Procedimientos para genrar y tetear números aleatorios

Método de la Transformada Inversa

– Ejemplos con el Método de la Tranformada Inversa

– Ventajas y desventajas

Otros Métpdps

– Convolución – Acceptanción/Rechazo

– Métodos especiales de genración de v.a.

clase 5.pdf

Documents