Download - Método Alias (Walter 1977) Permite generar de manera eficiente v.a.d. Con soporte finito. Supongamos que se desea generar la v.a.d. X con función de cuantía

Método Alias (Walter 1977)

Permite generar de manera eficiente v.a.d. Con soporte finito. Supongamos que se desea generar la v.a.d. X con función de cuantía P = { pi : i = 1,2,...,n }

donde Q(k) es una distribución concentrada en a lo sumo dos puntos {1,2,...,n}. La demostración de esta descomposición se basa en:

1

1

)(

1

1 n

k

kQn

P

Método de ComposiciónCaso Especial

Método de ComposiciónCaso Especial

Lema1: Sea P = { pi : i=1,2,...,n} función de cuantía

Entonces:

a) Existe i {1,2,...,n} tal que pi <

b) Para tal i, existe j con i j tal que pi + pj

Dem : Reducción al absurdo

11n

11n

TransformacionesTransformaciones

Distribución Binomial

Para generar una v.a.d. X ~ B(n,p)

independientes

Algoritmo

P1 : Hacer X = 0

P2 : Efectuar n réplicas- Generar U ~ U(0,1)Si U < p , Hacer X = X + 1Si U p , Hacer X = X + 0

P3 : Generar salida XObservación: Método propuesto requiere de generar “n” números aleatorios y n comparaciones

),1(~;1

pBZZX i

n

ii

Métodos EspecíficosMétodos Específicos

Un método alternativo es el método de inversión basado en la relación recursiva siguiente

[Fórmula recursiva]

Sea)(

)1)(1(

)()1( iXP

pi

piniXP

)(;)( iXPFiXPP


Algoritmo

P1 : Genera U ~ U(0,1)

P2 : Hacer i = 0 , P = F = (1-p)n

Hasta que U < F

Hacer P = P , F = F + P

i = i + 1

P3 : Generar salida X = i

)1)(1(

)(

pi

pin


Distribución Poisson

Para generar la distribución de Poisson P() con pequeño, utilizando el método de inversión.

P(X = i + 1) =

usando P = P(X = i) , F = P(X i)

)()1(

iXPi


Algoritmo

P1 : Genera U ~ U(0,1)

P2 : Hacer i = 0 F = P = Exp(-)

Hasta que U < F

Hacer P = P , F = F + P

i = i + 1

P3 : Generar salida X = i

)1( i


Distribución Geométrica

Para generar una v.a.d. X ~ G(p), es posible discretizar

Y ~ exp(). Sea X = [y]

Entonces P[x = r] =P(r Y < r +1), r=0,1,2,..

=

es la función de cuantía de una Geo(p=1-exp(-))

Tomando = -ln(1-p) X = ~ Geo(p)

));1(exp()exp()exp(1

rrdssr

r

][ )1ln(lnpU


Distribución Hipergeométrica

Para generar una distribución Hipergeométrica H(m,n,p) se efectúan n extracciones sin reposición de un conjunto de m elementos de dos clases {p m C1 y m(1-p) C2 }

AlgoritmoP1 : Hacer X = 0, C1 = mp C2 = m-C1

P2 : Repetir n veces Generar U ~ U(0,1) Si U C1/m hacer X = X+1 , C1 = C1 - 1 sino , C2 = C2 - 1

Hacer m = m - 1P3 : Generar salida X


Distribuciones Multivariadas

Distribuciones Independientes

El caso más simple lo constituye el de distribuciones marginales independientes

con x = (x1, x2,...,xp) Basta con generar cada componente Xi, como distribución univarianda y salir con

X = (X1, X2, ..., Xp)

p

iix xFxF

i1

)()(


Distribuciones Dependientes

Distribuciones Dependientes con condicionadas disponibles. Utilizando la descomposición

F(x) = F1(x1) • F2(x2 / x1)...• F(xp / x1,x2,...,xp-1)

Si disponemos de las distribuciones

Xi / X1, ..., Xi-1 i = 1,2,...,p

AlgoritmoP1 : Desde i=1,2,...,p Generar Xi ~ Xi / x1, ..., xi-1

P2 : Generar salida x = (x1,x2,...,xp)


Estadísticos de Orden

Para muestrear (X(1), X(2),...,X(p)), el estadístico de orden

asociado a m.a.s. X1,X2,...,Xp de X. La forma obvia de

muestrear es hacerlo de (X1,X2,...,Xp). Alternativamente,

podemos generar la muestra de orden. Por ejemplo, si

conocemos la inversa generalizada F, podemos generar

números aleatorios (U(1), U(2),...,U(p)) y salir X(i) = F(U(i)).

Para ello es necesario generar una muestra ordenada de

números aleatorios (U(1), U(2),...,U(p)) .


Algoritmo

P1 : Generar U(1), U(2),...,U(p) ~ U(0,1)

P2 : Hacer U(p) = (Up)1/p

U(k) = U(k+1) Uk1/k


Distribuciones Discretas

Las distribuciones discretas multivariadas no difieren de las univariadas. El soporte puede ser grande, pero los métodos, inversión, alias, etc. funcionan bien.

Ejemplo : Distribución bivariada (X,Y) con soporte {1,2,...,L}x{1,2,...,M} tenemos

Pxy = P(X x) + P(X=x, Y=y)

indexado en x.


Métodos Específicos

Para generar X = (X1, X2,...,Xp) ~ N(, ) se usa el método de descomposición de Cholesky.

Sea = L Lt, para alguna matriz L.

Entonces si Z = (Z1, Z2,...,Zp) ~ N(0, Ip)

la variable X = (, LZ) ~ N(, )


Distribución de Wishart

Para generar una v.a.c. W ~ W(n,,) para = 0, si = LLt y V = Zi Zi

t ; Zi normales p-variantes N(0, Ip) , i = 1,2,...,n

Entonces:

W = L V Lt ~ W (n,,0)

n

i 1


Algoritmo

P1 : Generar Zij ~ N(0,1) i = 1,2,...,n j=1,2,...,n

P2 : Hacer V = Zi Zit

P3 : Hacer W = L V Lt

P4 : Salida W

n

i 1


El algoritmo implica generar “np” normales estándar. Una reducción del esfuerzo de cálculo se obtiene utilizando la descomposición de Bartlett.

En el caso no centrado ( 0), es una matriz simétrica definida no negativa. Sea = t su descomposición de Cholesky y u1, u2, ..., up las filas de .

Entonces, podemos escribir :

donde se genera W, similar al caso = 0 usando np normales estándares.

n

pk

ttkk

p

k

tkkkk LZLZLZLZW

11

))((


Distribución Multinomial (p-dimensional).

Para generar la Distribución Multinomial de parámetros

q1, q2, ..., qp X = (X1, X2, ..., Xp) ~ M(n, q1,...,qp) con :

Como Xi ~ B(n, qi) i = 1,2,...,p

Xi / X1=x1,..., Xi-1=xi-1, ~ B(n-x1...-xi-1, wi)

i = 2,3,...,p con wi =

pinXqqp

ii

p

iii ,...,2,1,0,1

1 1

121 ......1 i

i

qqq

q


Entonces resulta el Algoritmo

P1 : Hacer mientras m=n i=1, w=1, Xi = 0, i=1,...,p

Mientras m 0

Generar Xi ~ B(m, qi/w)

Hacer m = m-Xi , w =1 - qi , i = i+1


Generación de Procesos Estocásticos

Generación de Familias de v.a. {Xt}t T

Comenzaremos con las cadenas de Markov homogéneas.

Cadena de Markov en Tiempo Discreto

Para generar una cadena de Markov con espacio de estado S y matriz de transición P = [pij] donde pij = P(Xn+1=j / X = i). La forma más simple de simular la transición (n+1)-ésima, conocida Xn, es generar Xn+1~{pxnj : j S}


Alternativamente se puede simular Tn, el tiempo hasta el

siguiente cambio de estado y, después el nuevo estado

Xn+Tn. Si Xn = s, Tn ~ G(pss) y Xn+Tn tiene una distribución

discreta con cuantía {psj / (1 - pss) : j S \ {s}}.

Para muestrear N transiciones de la cadena suponiendo Xo = io

Algoritmo

Hacer t=0, Xo = ioMientras t < NGenerar h ~ G(pxtxt)Generar Xt+h ~ {pxtj / (1 - pxtxt) : j S \ {s}}.Hacer t=t+h


OBS. 1) La primera forma de simular una cadena de Markov, que corresponde a una estrategia

sincrónica, es decir en la que el tiempo de simulación avanza a instantes iguales.

2) La estrategia asincrónica es más complicada de simular [Ver. B. Ripley 1996]


Cadenas de Markov en Tiempo Continuo

La simulación asincrónica de cadenas de Markov en tiempo continuo es sencilla de implantar.

- Las cadenas de Markov de Tiempo Continuo vienen caracterizadas por los parámetros vi de las distribuciones exponenciales de tiempo de permanencia en el estado i y la matriz de transición P; con pii = 0; pij = 1

- Sea Pi la distribución de la fila i-ésima. Entonces si Xo= io, para simular hasta T se tiene :

ji


Algoritmo

Hacer t = 0, Xo = io , j = 0

Mientras t < N

Generar tj ~ exp(vxj)

Hacer t = t + tj

Hacer j = j + 1

Generar Xj ~ Pxj-1


Proceso de Poisson

En el Proceso de Poisson P(), el número de eventos NT en un intervalo (0,T) es P(T) y los NT ~ U(0,T)

Algoritmo

- Generar NT ~ P(T)

- Generar U1, ..., UT ~ U(0,T)


OBS :

1) Para procesos de Poisson no homogéneos, con intensidad (t) y u(t) = (s) ds . Entonces

- Generar NT ~ P(u(t))

- Generar T1, T2 ,..., TNT ~

2) Los procesos de Poisson son un caso particular de los procesos de renovación. La forma de generar los primeros se extiende a los procesos de renovación.

t

0

],0[)( TIt


- Sean S0 = 0, S1, S2, ... Los tiempos de ocurrencia

- Ti = Si - Si-1 los tiempos entre sucesos.

- Para un proceso de renovación, los Ti son v.a.i.i.d. según cierta distribución .

- Simular hasta el instante T.

Hacer S0 = 0Mientras Si < T

Generar Ti ~ Hacer Si = Ti + Si-1

Hacer i = i + 1


Procesos no Puntuales (Movimiento Browniano)

- La simulación de procesos (no puntuales) en tiempo continuo es más complicada que la simulación de procesos puntuales.0

- Una solución es generar procesos en suficientes instantes discretos y aproximar la trayectoria por interpolación.


Como ejemplo, consideremos el movimiento Browniano con parámetro 2

- X0 = 0

- Para s1 t1 s2 t2 ..... sn tn las v.a. Xt1 - Xs1, ..., Xtn - Xsn son independientes

- Para s < t, Xt - Xs ~ N(0, (t-s) 2)

- Las trayectorias son continuas


Entonces para t fijo,

Hacer X0 = 0

Desde i = 1 hasta n

Generar Yi ~ N(0, (t-s) 2)

Hacer Xit = X(i-1)t + Yi

Interpolar la trayectoria en {(it, Xit)}

Otros ejemplos de Simulación de Procesos continuos [Ver B. Ripley 1987]


El Proceso de Gibbs

El creciente interés en los métodos de cadenas de Markov, se debe al uso en Inferencia Bayesiana del Muestrador de Gibbs. [Geman (1984)]

Ejemplo: Sean (X,Y) v.a.d. Bernoulli con distribución

x y P(X,Y)0 0 p1

1 0 p2 pi = 10 1 p3 pi > 01 1 p4


P(X=1) = p2 + p4 (Marginal)

P(X/Y=1) =

P(X=1/Y=1) =

Las Distribuciones condicionales

1

0

4

3

xp

xp

43

4

ppp

)1/1()1/0(

)0/1()0/0(

xyPxyP

xypxyPAyx

42

4

42

2

31

3

31

1

ppp

ppp

ppp

ppp

yxA


Algoritmo

Escoger Y0 = y0 , j =1Repetir Generar Xj ~ X/Y = yj-1

Generar Yj ~ Y/X = xj

j=j+1

Entonces {Xn} define una cadena de Markov con matriz de transición

A = Ayx Axy

43

4

43

3

21

2

21

1

ppp

ppp

ppp

ppp

xyA


Como las probabilidades pi > 0, la cadena es ergódica y tiene distribución límite, que es la marginal de X

Xn X ; Yn Y ; (Xn, Yn) (X,Y)

OBS: 1) El procedimiento descrito se llama muestrador de Gibbs [Gibbs Sampler] y nos proporciona una cadena de Markov, con distribución límite deseada y se puede generalizar.

Para muestrear un vector aleatorio p-variante

X = (X1, X2, ..., Xp) con distribución , conociendo

las distribuciones condicionadas Xs/Xr, r s


Sea (xs/xr, r s) Dist. Condicionada

El [Gibbs Sampler] en este caso es

- Escoger X10, X2

0,..., Xp0 ; j = 1

RepetirGenerar X1

j ~ X1/ X2j-1,..., Xp

j-1 Generar X2

j ~ X2/ X1j, X3

j-1,..., Xpj-1

....Generar Xp

j ~ Xp/ X1j, X2

j,..., Xp-1j

j = j+1


Se puede verificar que Xn = (X1n, X2

n,..., Xpn) define una

cadena de Markov con Matriz de transición

Pg(Xn, Xn+1) =

Bajo condiciones suficientemente generales [Ver Roberts Smith (1994)]

p

j

nj

nj

ni ijXijXx

1

11 ),;;/(


Ejemplo : Muestrear la densidad

(x1/x2) =

siendo D = R+ R

(x1/x2) =

(x2/x1) =

x1/x2 ~

x2/x1 ~ N(0, 2=(1/2x1))

),()]1(exp[ 21221

1 xxIxxD

]exp[ 221xx

)]1(exp[ 221)(

),(

2

21 xxxxx

]1exp[ 22x


El muestreador Gibbs

Escoger x20 ; j = 1

Repetir

Generar X1j ~ exp[1+(x2

j-1)2]

Generar X2j ~ N(0, 1/2x1

j)

OBS: Las secuencias podrían efectuarse en forma aleatoria en lugar de usar la secuenciación natural

Estudiar el Algoritmo de Metropolis-Hastings.


Download - Método Alias (Walter 1977) Permite generar de manera eficiente v.a.d. Con soporte finito. Supongamos que se desea generar la v.a.d. X con función de cuantía

Top Related