Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
UNIVERSIDAD CENTRAL DEL ECUADOR
FACULTAD DE INGENIERIA,CIENCIAS FISICAS Y MATEMATICA
CARRERA DE INGENIERIA MATEMATICA
CADENAS DE MARKOV REVERSIBLES:ALGUNAS APLICACIONES.
TRABAJO DE GRADUACION PREVIO LA OBTENCION DEL
TITULO DE INGENIERA MATEMATICA
AUTOR: Guayanay Calva Liliana Marisol
TUTOR: Ing. Albuja Proano Guillermo Alexis, MSc.
QUITO, 12 DE DICIEMBRE
2016
AUTORIZACION DE LA AUTORIA INTELECTUAL
ii
CERTIFICACION DEL TUTOR
iii
APROBACION DEL JURADO O TRIBUNAL
iv
v
DEDICATORIA
A Dios y a la Virgen del Cisne, por permitirme el haber llegado hasta este
momento tan importante de mi formacion profesional y por haberme iluminado
en cada paso de mi vida.
A mi madre Julia, por haberme apoyado en todo momento, por sus consejos,
sus valores, por la motivacion constante que me ha permitido ser una persona
de bien, pero sobre todo, por su amor incondicional.
A mi padre Rodrigo, que su mayor ilusion fue verme convertida en toda una
profesional y a pesar de haberlo perdido antes de cumplir nuestro sueno se que
esta cuidandome y guiandome desde el cielo por siempre.
A todos mis hermanas y hermanos que siempre han estado junto a mı brindando-
me su apoyo, por compartir buenos y malos momentos.
A toda mi familia que de una u otra forma fueron indispensables durante esta
etapa de mi vida.
vi
AGRADECIMIENTO
Primeramente agradezco a Dios, por ayudarme en los momentos mas difıciles
de mi vida y estar siempre conmigo en cada paso que doy. Por permitirme
haber llegado hasta este momento tan importante en mi vida e iluminar mi
mente siempre.
A mi familia por su apoyo constante, amor incondicional que supieron entender
mis malos momentos y siempre estuvieron dandome animo para terminar este
proyecto.
A mi maestro Dr. Luis Horna, por toda la colaboracion, disposicion y ayuda
para que este proyecto pudiera realizarse.
Este trabajo no habrıa sido posible sin el apoyo y el estımulo de mi tutor de
proyecto de titulacion, Ing. Guillermo Albuja, MSc.
Tambien me gustarıa agradecerle al Ing. Ivan Naula y el Ing. Javier Gonzalez,
por su tiempo en la revision de este trabajo.
No puedo terminar sin agradecer a mis queridos companeros, amigos que me
brindaron su companıa durante todo el perıodo de estudio y permitieron entrar
en sus vidas durante estos anos.
Sin todos ustedes, este trabajo no habrıa sido posible.
vii
CONTENIDO
AUTORIZACION DE LA AUTORIA INTELECTUAL II
CERTIFICACION DEL TUTOR III
APROBACION DEL JURADO O TRIBUNAL IV
DEDICATORIA VI
AGRADECIMIENTO VII
RESUMEN XII
ABSTRACT XIII
INTRODUCCION 1
DEFINICION DEL PROBLEMA 3
I. MARCO TEORICO 6
1.1. Base teorica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1. Procesos Estocasticos . . . . . . . . . . . . . . . . . . . . 6
1.1.2. Propiedad de Markov . . . . . . . . . . . . . . . . . . . . 7
1.1.3. Ecuacion de Chapman-Kolmogorov. . . . . . . . . . . . . 10
1.1.4. Recurrencia y Transitoriedad . . . . . . . . . . . . . . . 13
1.1.5. Cadena de Markov reversible en el tiempo . . . . . . . . 16
1.1.5.1. Calculo de las probabilidades lımites . . . . . . 18
1.1.6. Cadena de Markov Reversible a tiempo continuo . . . . . 22
1.1.7. Convergencia al Equilibrio . . . . . . . . . . . . . . . . . 24
viii
1.1.8. Algoritmos de Cadenas de Markov . . . . . . . . . . . . 26
II. ALGUNAS APLICACIONES DE LAS CADENAS
DE MARKOV REVERSIBLES 31
2.1. Metodos de Monte Carlo con cadenas de Markov . . . . . . . . . 31
2.1.1. Que es el metodo de Monte Carlo . . . . . . . . . . . . . 31
2.2. Metodos de Monte Carlo con cadenas de Markov Reversibles:
Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.1. El Algoritmo de Hastings-Metropolis. . . . . . . . . . . 32
2.2.2. Ejemplo: Simulacion de la Distribucion Beta utilizando
el algoritmo de Hastings-Metropolis. . . . . . . . . . . . 34
2.2.3. La Urna de Polya . . . . . . . . . . . . . . . . . . . . . . 38
2.2.3.1. Probabilidad de Transicion del Modelo de la Ur-
na de Polya . . . . . . . . . . . . . . . . . . . . 38
2.2.3.2. Simulacion del Modelo de la Urna de Polya . . 44
2.2.4. El muestreador de Gibbs. . . . . . . . . . . . . . . . . . 46
III. CONCLUSIONES Y RECOMENDACIONES 52
3.1. CONCLUSIONES . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2. RECOMENDACIONES . . . . . . . . . . . . . . . . . . . . . . 53
A. ANEXOS 54
BIBLIOGRAFIA 56
ix
LISTA DE FIGURAS
1.1. Trayectoria obtenida despues de realizar 100 iteraciones. . . . . 12
1.2. Representacion grafica de los estados. . . . . . . . . . . . . . . . 14
1.3. Representacion grafica de los estados. . . . . . . . . . . . . . . . 15
1.4. Un grafo conectado con los pesos de arco. . . . . . . . . . . . . . 21
1.5. El grafo de un cuadrado. . . . . . . . . . . . . . . . . . . . . . . 25
1.6. Diagrama de flujo del Algoritmo de Cadena de Markov. . . . . . 28
1.7. Representacion del grafo con vertices adyacentes. . . . . . . . . 29
2.1. Sucesion de Xn para n = 1, ..., 5000 cuando se simula a partir del
algoritmo de Hastings-Metropolis con la distribucion uniforme
propuesta y Beta(2, 7; 6, 3). . . . . . . . . . . . . . . . . . . . . 35
2.2. Histogramas de beta Beta(2, 7; 6, 3) variables aleatorias con fun-
cion de densidad superpuestos. En el panel izquierdo, las varia-
bles se generan a partir del algoritmo de Hastings-Metropolis
con un distribucion uniforme, y en el panel derecho de las varia-
bles aleatorias se generaron directamente a traves de la funcion
rbeta(n; 2, 7; 6, 3). . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3. Histograma obtenido despues de realizar 10000 iteraciones. . . . 38
2.4. W0 = 4, B0 = 2, α = 1 y n = 1000 . . . . . . . . . . . . . . . . . 45
2.5. W0 = 4, B0 = 2, α = 1 y n = 1000 . . . . . . . . . . . . . . . . . 46
2.6. Sucesion de la distribucion marginal de X implementando el
muestreador de Gibbs sobre la base de 5000 iteraciones para m
= 15; a = 3; b = 7. . . . . . . . . . . . . . . . . . . . . . . . . 50
x
2.7. Histograma de la distribucion marginal de X implementando el
muestreador de Gibbs sobre la base de 5000 iteraciones para m
= 15; a = 3; b = 7. . . . . . . . . . . . . . . . . . . . . . . . . 50
2.8. Sucesion de la distribucion marginal de θ implementando el mues-
treador de Gibbs sobre la base de 5000 iteraciones para m = 15;
a = 3; b = 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.9. Histograma de la distribucion marginal de θ implementando el
muestreador de Gibbs sobre la base de 5000 iteraciones para m
= 15; a = 3; b = 7. . . . . . . . . . . . . . . . . . . . . . . . . 51
xi
RESUMEN
CADENAS DE MARKOV REVERSIBLES: ALGUNAS
APLICACIONES
Autor: Liliana Marisol Guayanay Calva
Tutor: Ing. Guillermo Alexis Albuja Proano, MSc.
En este trabajo se presenta un material escrito sobre las cadenas de Markov
reversibles en donde se exponen las definiciones, proposiciones y teoremas mas
importantes, ademas se presentan algunos ejemplos para reforzar la teorıa.
Se incluyen adicionalmente, algunas aplicaciones de las cadenas de Markov
reversibles las cuales son simuladas mediante los metodos de Monte Carlo,
tales como el algoritmo de Hastings-Metropolis y el muestreador de Gibbs.
PALABRAS CLAVES: PROCESOS ESTOCASTICOS/ CADENAS DE
MARKOV REVERSIBLES/ MATRIZ DE TRANSICION/ ALGORITMO DE
HASTINGS-METROPOLIS/ MUESTREADOR DE GIBSS/ SIMULACION.
xii
ABSTRACT
REVERSIBLE MARKOV CHAINS: SOME APPLICATIONS
Author: Liliana Marisol Guayanay Calva
Tutor: Ing. Guillermo Alexis Albuja Proano, MSc.
In this research paper we present a written material about the reversible Markov
chains where the most important definitions, propositions and theorems are
presented, some examples are also exposed to reinforce the theory. Additionally,
some applications of the reversible Markov chains are included and simulated
using the Monte Carlo methods, such as the Hastings Metropolis algorithm and
the Gibbs sampler.
KEYWORDS: STOCHASTIC PROCESSES/ REVERSIBLES MARKOV
CHAINS/ TRANSITION MATRIX/ HASTINGS-METROPOLIS ALGORITHM/
GIBSS SAMPLER/ SIMULATION.
I CERTIFY that the above and foregoing is a true and correct translation of
the original document in Spanish.
William Francisco Cueva Chinchay.
Certified Translator
ID: 1103480859
Certificacion No. 1031-02-273188
xiii
INTRODUCCION
Los procesos estocasticos son sucesiones de eventos gobernados por leyes pro-
babilısticas. Muchas aplicaciones de los procesos estocasticos aparecen en fısica,
ingenierıa, biologıa, medicina y otras disciplinas ası como tambien en otras ra-
mas de la matematica.
Los procesos estocasticos sirven para caracterizar y estudiar fenomenos alea-
torios que evolucionan, generalmente, con el paso del tiempo. Una clase muy
importante de este tipo de procesos la constituyen los procesos de Markov.
Deben su nombre a Andrey Markov, matematico ruso que postulo el principio
de que existen ciertos procesos cuyo estado futuro solo depende de su estado
presente y es independiente de sus estados pasados. Dichos procesos, denomi-
nados procesos de Markov, ası como un subconjunto de ellos llamados cadenas
de Markov reversibles, constituyen una herramienta matematica muy general
y poderosa para el analisis y tratamiento de un sinnumero de problemas de
caracterıstica aleatoria en campos de muy diversa ındole.
Este trabajo pretende, por tanto, hacer una revision teorica de cadenas de Mar-
kov reversibles y abordar su aplicabilidad mediante la simulacion con metodos
de Monte Carlo.
En la primera parte, se realiza la presentacion del problema, la justificacion y
los objetivos de la investigacion.
En el Capıtulo 1, se detallan conceptos y propiedades basicas que se utilizaran
para el desarrollo del trabajo, mismos que se dan desde el fundamento ma-
tematico.
En el Capıtulo 2, se analizan las aplicaciones de las cadenas de Markov rever-
sibles y se simula una cadena usando el algoritmo de Hastings-Metropolis y el
muestreador de Gibbs.
En el Capıtulo 3, se presentan las conclusiones y recomendaciones del presente
1
trabajo.
2
DEFINICION DEL PROBLEMA
PLANTEAMIENTO DEL PROBLEMA
En general, es difıcil simular el valor de un vector aleatorio X cuyas variables
aleatorias componentes son dependientes. En este trabajo se ampliara la teorıa
de cadenas de Markov reversibles y se presenta un metodo poderoso para ge-
nerar un vector cuya distribucion es aproximadamente la de X. Este metodo,
llamado metodo de Monte Carlo con cadenas de Markov, tiene la ventaja adi-
cional de que la funcion de masa (o densidad) de X puede estar dada salvo una
constante multiplicativa, lo cual es de gran importancia en las aplicaciones que
se desarrollan. Ademas, para construir una cadena de Markov con una funcion
de masa de probabilidad como distribucion lımite se utiliza el algoritmo de
Hastings-Metropolis y el muestreador de Gibbs.
FORMULACION DEL PROBLEMA
Hacer una revision teorica de cadenas de Markov reversibles, completando los
detalles de manera que el material presentado resulte facil de entender para el
lector interesado y abordar su aplicabilidad mediante la simulacion con metodos
de Monte Carlo.
JUSTIFICACION DEL PROBLEMA
Las cadenas de Markov y sus conceptos basicos fueron introducidos por Andrey
Markov durante 1907, el trabajo de Markov marca el inicio del desarrollo de
3
los procesos estocasticos formalmente. Weiner en 1923 fue el primero en tra-
tar rigurosamente el caso continuo de la cadena de Markov y fue Kolmogorov
en los anos 30 quien desarrollo la teorıa general de los procesos estocasticos.
El concepto de cadena de Markov fue sin duda una de las contribuciones mas
grandes de Markov, y ha sido reconocida durante el paso del tiempo, ya que dio
lugar a varias investigaciones en la teorıa de los procesos estocasticos en donde
la importancia de estudiar las cadenas como un estudio de variables aleatorias
es que una gran cantidad de aplicaciones tienen la propiedad de Markov.
Las cadenas de Markov reversibles son muy utiles en la Fısica, en Ciencias
Biologicas, en Ciencias Sociales, Finanzas, Estadıstica y Matematicas. En este
trabajo se busca brindar un documento sobre cadenas de Markov reversibles
mediante el estudio de la teorıa y de ejemplos bastante claros, ası mismo mos-
trar que las cadenas de Markov tienen diferentes aplicaciones y por ultimo
simular como se comportan las trayectorias de un proceso de este tipo.
Cabe senalar que el software empleado para realizar las simulaciones y graficas
correspondientes mostradas en este trabajo se realizaran con el programa R.
OBJETIVOS
Objetivo General
Elaborar un material escrito sobre cadenas de Markov reversibles y mostrar
algunas de sus aplicaciones.
Objetivos Especıficos
1. Estudiar las cadenas de Markov reversibles.
2. Exponer los metodos de cadenas de Markov Monte Carlo.
4
3. Utilizar metodos de simulacion como el Algoritmo de Hastings-Metropolis
y el Muestreador de Gibbs para generar trayectorias de una cadena de
Markov reversible.
4. Presentar algunas de las aplicaciones de cadenas de Markov reversibles
simuladas en R.
5
CAPITULO I
MARCO TEORICO
1.1. Base teorica
A lo largo de esta seccion se exponen diferentes definiciones y resultados fun-
damentales sobre procesos de Markov necesarios para el desarrollo del proyecto
de investigacion.
1.1.1. Procesos Estocasticos
Un proceso estocastico es un modelo matematico que describe el comportamien-
to de un sistema dinamico, sometido a un fenomeno de naturaleza aleatoria.
La presencia de un fenomeno aleatorio hace que el sistema evolucione segun un
parametro, que normalmente es el tiempo t cambiando probabilısticamente de
estado. Suponga que el sistema evoluciona de un estado a otro a lo largo del
tiempo de acuerdo con una cierta ley de movimiento, y sea Xt el estado del
sistema al tiempo t. Si se considera que la forma en la que el sistema evoluciona
es provocada por algun mecanismo aleatorio y no determinista, entonces puede
considerarse que Xt es una variable aleatoria para cada valor del subındice t.
Esta coleccion de variables aleatorias es la definicion de proceso estocastico, y
sirve como modelo para representar la evolucion aleatoria de un sistema a lo
largo del tiempo. En general, las variables aleatorias que conforman un proceso
no son independientes entre sı, sino que estan relacionadas unas con otras de
alguna manera particular.
6
La definicion de proceso estocastico toma como base un espacio de probabilidad
(Ω, F, P ) y puede enunciarse de la siguiente forma.
Dado el espacio de probabilidad (Ω, F, P ) de modo que para todo t ∈ T ⊂ R
fijo
Xt : (Ω, F, P ) −→ (RT ,B(RT ), Px)
esto es P (X−1t (B)) = Px(B) para todo B ∈ B donde RT es la familia de todas
las funciones reales de T en R.
B(RT ) σ-algebra de los bolerianos de RT .
Px distribucion de Xt.
Definicion 1. Un proceso estocastico es una coleccion de variables aleatorias
Xt : t ∈ T parametrizada por un conjunto T , llamado espacio parametral, en
donde las variables toman valores en un conjunto S llamado espacio de estados
[9].
1.1.2. Propiedad de Markov
Se considera como procesos estocasticos a tiempo discreto Xn : n ≥ 0
que cumplen la propiedad de Markov. Para describir a esta propiedad y va-
rias de sus condiciones equivalentes de una manera simple, a la probabilidad
P (Xn = xn) se le escribira como p(xn). El significado de la probabilidad con-
dicional p(xn+1 | xn) es similar.
Definicion 2. Una cadena de Markov es un proceso estocastico a tiempo dis-
creto Xn : n = 0, 1, ..., con espacio de estados discreto, y que satisface la
propiedad de Markov, esto es, para cualquier entero n ≥ 0, y para cualesquiera
7
estados x0, x1, . . . , xn+1 , se cumple [10]
p(xn+1 | x0, ..., xn) = p(xn+1 | xn) (1.1)
Para que la definicion anterior este mas clara se considera al tiempo n+1 como
un tiempo futuro, al tiempo n como el presente y a los tiempos 0, 1, 2, ..., n− 1
como el pasado, entonces la condicion (1.1) establece que la distribucion de
probabilidad del estado del proceso al tiempo futuro n+1 depende unicamente
del estado del proceso al tiempo presente n, y no depende de los estados en
los tiempos pasados 0, 1, 2, ..., n − 1. Para seguir se toma sin perdida de gene-
ralidad como espacio de estados de una cadena de Markov al conjunto discreto
0, 1, 2, ... , o cualquier subconjunto finito que conste de los primeros elemen-
tos de este conjunto. Una cadena de Markov se dice que es finita si su espacio
de estados es un conjunto finito.
Probabilidad de Transicion. Sean i y j dos estados de una cadena de
Markov. A la probabilidad
P (Xn+1 = j | Xn = i)
expresada por pij(n, n + 1), que representa la probabilidad de transicion del
estado i en el tiempo n, al estado j en el tiempo n+1. Dichas probabilidades se
conocen como las probabilidades de transicion en un paso. Cuando los numeros
pij(n, n+1) no dependen de n se dice que la cadena es estacionaria en el tiempo.
Las probabilidades de transicion en un paso se escriben como pij si se asume tal
situacion. Si se varıa los ındices i y j, sobre el conjunto de estados 0, 1, 2, ...
, se obtiene la matriz de probabilidades de transicion en un paso:
P =
0
1
2...
p00 p01 p02 · · ·
p10 p11 p12 · · ·
p20 p21 p22 · · ·...
......
(1.2)
8
La entrada (i, j) de la matriz (1.2) es la probabilidad de transicion pij, es decir,
la probabilidad de pasar del estado i al estado j en una unidad de tiempo.
Ejemplo 1. (Predecir el tiempo) Se supone que la probabilidad de lluvia del
dıa de manana depende de las condiciones climaticas anteriores solo a traves
de si o no esta lloviendo hoy y no de las condiciones climaticas del pasado.
Suponga tambien que si llueve hoy, entonces manana llovera con a de proba-
bilidad; y si no llueve hoy, entonces manana llovera con probabilidad b. Si se
dice que el proceso esta en el estado 0 cuando llueve y el estado 1 cuando no
llueve, entonces el precedente es una cadena de Markov de dos estados cuyas
probabilidades de transicion estan dadas por:
P =
a 1− a
b 1− b
Proposicion 1. La matriz de probabilidades de transicion P = (pij) cumple
las siguientes dos propiedades [10]:
a) pij ≥ 0 para todo i , j.
b)∑j
pij = 1 para todo i.
P se llama matriz estacionaria. Si ademas∑i
pij = 1 para todo j, P se llama
doble estocastica.
Distribucion de probabilidad inicial. Una cadena de Markov puede con-
siderarse que en general su evolucion inicia partiendo de un estado i cualquiera,
o mas generalmente considerando una distribucion de probabilidad inicial sobre
el espacio de estados. Una distribucion inicial para una cadena de Markov con
espacio de estados 0, 1, 2, .. es simplemente una distribucion de probabilidad
sobre este conjunto, es decir, es una coleccion de numeros p0, p1, p2, .. que son
no negativos y que suman uno. El numero pi corresponde a la probabilidad de
9
que la cadena inicie en el estado i.
Probabilidades de transicion en n pasos. La probabilidad de pasar del
estado i al tiempo m, al estado j al tiempo m+n esta dado por P (Xn+m = j |
Xm = i). Dado el supuesto de la condicion de homogeneidad en el tiempo, esta
probabilidad no depende realmente de m, por lo tanto coincide con P (Xn = j |
X0 = i), y se le denota por pij(n). A esta probabilidad tambien se le denota por
p(n)ij , en donde el numero de pasos n se escribe entre parentesis para distinguirlo
de algun posible exponente, y se le llama probabilidad de transicion en n pasos.
Haciendo variar i y j se obtiene la matriz de probabilidades de transicion en n
pasos que denotaremos por P (n):
P (n) =
p00(n) p01(n) · · ·
p10(n) p11(n) · · ·...
......
Si n = 1 simplemente se omite su escritura en estas probabilidades de transicion,
a menos que se quiera hacer enfasis en ello. Ademas, cuando n = 0 se define
pij(0) = δij =
0 si i 6= j
1 si i = j
Esta es la funcion delta de Kronecker la cual nos dice que despues de realizar
cero pasos la cadena no puede estar en otro estado mas que en su lugar de
origen.
1.1.3. Ecuacion de Chapman-Kolmogorov.
La ecuacion de Chapman-Kolmogorov es una formula que permite descompo-
ner la probabilidad de pasar del estado i al estado j en n pasos, en la suma
de probabilidades de las trayectorias que van de i a j, y que atraviesan por un
estado k cualquiera en un tiempo intermedio r.
10
Teorema 1. (Ecuacion de Chapman-Kolmogorov)
Para cualquier par de numeros enteros r y n tales que 0 ≤ r ≤ n , y para
cualesquiera estados i y j se cumple [10]
pij(n) =∑k
pik(r)pkj(n− r)
Demostracion 1. Por el teorema de probabilidad total y la propiedad de Mar-
kov,
pij(n) = P (Xn = j | X0 = i)
=∑k
P (Xn = j,Xr = k,X0 = i)/P (X0 = i)
=∑k
P (Xn = j | Xr = k)P (Xr = k | X0 = i)
=∑k
pkj(n− r)pik(r).
Ejemplo 2. Se considera el ejemplo 1. En el que el tiempo es considerado como
una cadena de Markov de dos estados. Si a = 0, 7 y b = 0, 4, entonces, calcular
la probabilidad de que llueva cuatro dıas a partir de hoy ya que esta lloviendo
hoy.
Solucion: La matriz de probabilidad de transicion en un paso esta dada por
P =
0, 7 0, 3
0, 4 0, 6
Por lo tanto,
11
P (2) = P 2 =
0, 7 0, 3
0, 4 0, 6
· 0, 7 0, 3
0, 4 0, 6
=
0, 61 0, 39
0, 52 0, 48
,
P (4) = (P 2)2 =
0, 61 0, 39
0, 52 0, 48
· 0, 61 0, 39
0, 52 0, 48
=
0, 5749 0, 4251
0, 5668 0, 4332
y la probabilidad P 4
00 deseada es igual 0,5749.
Figura 1.1: Trayectoria obtenida despues de realizar 100 iteraciones.
12
1.1.4. Recurrencia y Transitoriedad
Definicion 3. Se dice que una cadena de Markov es irreducible si todos los
estados se comunican entre sı [9].
Definicion 4. Si todos los estados son ergodicos, es decir, recurrentes, no nu-
los y aperiodicos entonces se define la cadena como ergodica [12].
Definicion 5. Se dice que un estado i es recurrente si la probabilidad de even-
tualmente regresar a i, partiendo de i, es uno, es decir, si
P (Xn = i para algun n ≥ 1 | X0 = i) = 1.
Un estado que no es recurrente se llama transitorio, y en tal caso la probabili-
dad anterior es estrictamente menor que uno [10].
Proposicion 2. (Criterio para la recurrencia) El estado i es
1. recurrente si, y solo si∞∑n=1
pii(n) =∞
2. transitorio si, y solo si∞∑n=1
pii(n) <∞
[9].
Proposicion 3. Sea j un estado transitorio. Para cualquier estado inicial i,
se cumple que∞∑n=1
pij(n) <∞. En consecuencia, lımn→∞
pij(n) = 0 [9].
Proposicion 4. Toda cadena de Markov finita tiene por lo menos un estado
recurrente [9].
13
Ejemplo 3. Sea una cadena con la siguiente matriz de transicion
P =
0 1
214
14
12
12
0 0
0 0 1 0
0 0 12
12
representada por el diagrama
Figura 1.2: Representacion grafica de los estados.
El estado 1 es transitorio puesto que,
p11(1) = 0
p11(2) =1
2· 1
2=
(1
2
)2
p11(3) =
(1
2
)3
· · · = · · ·
p11(n) =
(1
2
)n,
ası,
p11 =∞∑n=1
p11(n) =∞∑n=2
(1
2
)n=
1
1− 12
− 1
2− 1 =
1
2< 1
14
luego 1 es un estado transitorio.
Ejemplo 4. Sea una cadena con la siguiente matriz de transicion
P =
12
12
0
0 0 1
1n+1
0 nn+1
representada por el diagrama
Figura 1.3: Representacion grafica de los estados.
Se tiene que
p11(1) =1
2
p11(2) = 0
p11(3) =1
2· 1 · 1
4
en general, para n ≥ 4,
p11(n) =1
2· 1 · 3
4· 4
5· · · n− 1
n· 1
n+ 1=
3
2n(n+ 1).
15
ası,
p11 =1
2+
1
8+
3
2
∞∑n=4
1
n(n+ 1).
Se tiene que como
1
n(n+ 1)=
1
n− 1
n+ 1
∞∑n=4
1
n(n+ 1)= lım
N−→∞
N∑n=4
(1
n− 1
n+ 1
)= lım
N−→∞
(1
4− 1
N + 1
)=
1
4,
entones
p11 =1
2+
1
8+
31
24= 1,
lo que significa que 1 es un estado recurrente.
1.1.5. Cadena de Markov reversible en el tiempo
Sea Xn−2, Xn−1, Xn, ... una cadena de Markov ergodica estacionaria que tiene
probabilidades de transicion Pij y probabilidades estacionarias πi. Luego, a
partir del tiempo n se traza la sucesion de estados que van hacia atras en el
tiempo Xn, Xn−1, Xn−2, ....Entonces la nueva sucesion de estados es una cadena
de Markov con probabilidades de transicion Qij definida por
Qij = PXm = j | Xm+1 = i
=PXm = j,Xm+1 = i
PXm+1 = i
=PXm = jPXm+1 = i | Xm = j
PXm+1 = i
=πjPjiπi
.
16
Para verificar que el proceso inverso es una cadena de Markov, se demuestra la
siguiente igualdad,
PXm = j | Xm+1 = i,Xm+2, Xm+3, ... = PXm = j | Xm+1 = i
Primero se supone que el momento actual esm+1. Luego, puesto queX0, X1, X2, ...
es una cadena de Markov, se tiene que el estado futuro Xm+2, Xm+3, ... dado el
estado actual Xm+1 es independiente del estado pasado Xm. Entonces, como la
relacion de independencia es simetrica se tiene que Xm+1, Xm es independiente
de Xm+2, Xm+3, ....
Por lo tanto, el proceso inverso es tambien una cadena de Markov con proba-
bilidades de transicion dadas por
Qij =πjPjiπi
[12].
Definicion 6. Cadena de Markov reversible en el tiempo
Una cadena de Markov estacionaria, ergodica se dice que es reversible en el
tiempo, si Qij = Pij para toda i, j. La condicion para la reversibilidad en el
tiempo tambien se puede expresar como
πiPij = πjPji para todo i, j (1.3)
La condicion en la ecuacion (1.3) afirma que, para todos los estados i y j la
velocidad a la que el proceso va de i a j (es decir, πiPij) es igual a la velocidad
a la que va desde j a i (es decir, πjPji). Esta es una condicion necesaria para
la reversibilidad desde una transicion de i a j yendo hacia atras en el tiempo
la cual es equivalente a una transicion desde j a i yendo hacia adelante en el
tiempo [12].
Proposicion 5. Suponga una cadena de Markov ergodica irreducible que tiene
17
probabilidades de transicion Pij. Si se encuentra numeros no negativos xi, i =
1, ..., N tales queN∑i=1
xi = 1 y satisfacen la ecuacion xiPij = xjPji para todo i 6=
j entonces la cadena de Markov es reversible en el tiempo y xi son las probabi-
lidades lımites πi.
Demostracion 5. Suponga que existen numeros positivos xi, i = 1, ..., N tales
que
xiPij = xjPji para todo i 6= j,
N∑i=1
xi = 1 (1.4)
luego, sumando las ecuaciones anteriores sobre todos los estados i, tenemos,
N∑i=1
xiPij = xj
N∑i=1
Pji = xj
y como las probabilidades limitantes πi, i = 1, ...N son la unica solucion de
πi =N∑j=1
πjPij, i = 1, ..., N
N∑i=1
πi = 1
entonces,se deduce que πi = xi para todo i [13].
1.1.5.1. Calculo de las probabilidades lımites
Sea P la matriz de transicion de una cadena de Markov. Sea P (n) la matriz de
transicion en el paso n. Sea P n la n-esima potencia de la matriz de transicion.
Sea∏
= lımn→∞
P n, si existe el lımite. Sea ~π el vector de las probabilidades
lımites, si este existe.
Entonces, se tiene
∏= lım
n→∞P (n) = lım
n→∞P n
y cada fila comun de∏
, ~π es el vector lımite.
18
Proposicion 6. Una cadena de Markov con probabilidad de transicion P es
reversible si∏∗P es simetrica donde ∗ significa la multiplicacion componente
a componente.
Demostracion 6. Sea R =∏T ∗P .
∏=
π1 π2 π3 · · ·
π1 π2 π3 · · ·
π1 π2 π3 · · ·...
......
. . .
Luego,
R =
π1 π1 π1 · · ·
π2 π2 π2 · · ·
π3 π3 π3 · · ·...
......
. . .
∗
p11 p12 p13 · · ·
p21 p22 p23 · · ·
p31 p32 p33 · · ·...
......
. . .
=
π1p11 π1p12 π1p13 · · ·
π2p21 π2p22 π2p23 · · ·
π3p31 π3p32 π3p33 · · ·...
......
. . .
Si se tiene una matriz simetrica, es decir si πipij = πjpji para todo i, j, significa
que la ecuacion de balance se cumple. Por tanto, la matriz de transicion P es
reversible. Caso contrario P no es reversible [7].
Ejemplo 5. Tomando la matriz de transicion del Ejemplo 2 y aplicando la
Proposicion 6 se quiere comprobar si se trata de una cadena de Markov rever-
sible.
19
Solucion Sea
P =
0, 7 0, 3
0, 4 0, 6
∏= P 100 =
0, 5714286 0, 4285714
0, 5714286 0, 4285714
R = (P 100)T ∗ P =
0, 4000000 0, 1714286
0, 1714286 0, 2571429
Ası se tiene el vector lımite π(0, 5714286, 0, 4285714) de P y se ve que la matriz
resultante es simetrica. Por tanto la cadena de P es reversible.
Definicion 7. Un grafo G consiste en un conjunto de vertices V (G), un con-
junto de aristas E(G), y una relacion que se asocian con cada arista dos vertices
llamados sus puntos finales [14].
Dos vertices u y v son adyacentes si existe una arista que los conecte.
Definicion 8. Un grafo G es conexo, si dados u y v dos vertices de G existe
al menos un camino de u a v [14].
Ejemplo 6. Considere un grafo conexo arbitrario que tiene un numero wij
asociado con el arco (i, j) para cada arco. En la Figura 1.4 se muestra el grafo.
Considere ahora una partıcula que se mueve de vertice a vertice de esta manera:
Si en algun momento la partıcula reside en el vertice i, entonces el siguiente
movimiento sera al vertice j con probabilidad Pij donde
Pij =wij∑j
wij
20
donde wij es 0 si (i, j) no es un arco. Por ejemplo, para el grafo de la Figura
1.4, P12 = 33+1+2
= 12.
Figura 1.4: Un grafo conectado con los pesos de arco.
Cuya matriz de transicion es:
P =
0 12
0 16
13
1 0 0 0 0
0 0 0 0 1
15
0 0 0 45
16
0 12
13
0
Las ecuaciones de reversibilidad en el tiempo
πiPij = πjPji
reducidas a
πiwij∑j
wij= πj
wji∑i
wji
o, equivalentemente, puesto que wij = wji
πi∑j
wij=
πj∑i
wji
21
lo cual es equivalente a
πi∑j
wij= c
o
πi = c∑j
wji
o, ya que 1 =∑i
πi
πi =
∑j
wji∑i
∑j
wji
Como los πi dados por esta ecuacion satisfacen las ecuaciones de reversibili-
dad de tiempo, se deduce que el proceso es reversible en el tiempo con estas
probabilidades limitantes. Para el grafo de la Figura 1.4 se tiene que que
π1 =6
32, π2 =
3
32, π3 =
6
32, π4 =
5
32, π5 =
12
32 .
Teorema 2. (Criterio de Kolmogorov)
Una cadena de Markov estacionaria es reversible si y solo si las probabilidades
de transicion satisfacen
p(j1, j2)p(j2, j3)...p(jn−1, jn)p(jn, j1) = p(j1, jn)p(jn, jn−1)...p(j3, j2)p(j2, j1)
para cualquier sucesion de estados j1, j2, ..., jn ∈ E.
1.1.6. Cadena de Markov Reversible a tiempo continuo
Procesos Reversibles Suponga que se tiene una cadena de Markov de tiem-
po continuo Xt que toma valores en el espacio de estados S (finito o infinito
22
contable) con tasas de transicion α(x, y). Si π es cualquier medida sobre S,
es decir, una funcion no negativa sobre S, entonces la cadena se dice que es
reversible con respecto a la medida π si para todo x, y ∈ S,
π(x)α(x, y) = π(y)α(y, x)
Se dice que la cadena es simetrica si para todo x,y
α(x, y) = α(y, x)
Note que una cadena es simetrica si y solo si esta es reversible con respecto a
la medida uniforme π(x) = 1, x ∈ S [6].
Ejemplo 7. Sea G = (V,E) un grafo. Se escribe x v y si los vertices x y y
son adyacentes, es decir, una arista conecta los dos vertices,
Sea la cadena de Markov cuyos estados son los vertices del grafo. En cada
intervalo de tiempo, la cadena elige de forma aleatoria un nuevo estado entre
los estados adyacentes al estado actual. La matriz de transicion para esta cadena
esta dada por
α(x, y) =1
d(x), (x, y) ∈ E,
donde d(x) es el numero de vertices adyacentes a x. Entonces la cadena es
reversible con respecto a la medida π(x) = d(x). Si por el contrario se elige
α(x, y) = 1, (x, y) ∈ E,
la cadena es simetrica y por tanto es reversible con respecto a la medida uni-
forme.
23
1.1.7. Convergencia al Equilibrio
Sea Xt una cadena de Markov irreducible de tiempo continuo con tasas α(x, y),
reversible con respecto a la medida de probabilidad π. Se supone que el espacio
de estados es finito, S = 1, ..., N. Se considera el caso en que A es simetrica ,
pero estas ideas se mantienen en todas las cadenas reversibles. Hay un numero
de maneras de medir la distancia entre dos medidas de probabilidad π y v sobre
S. Una definicion muy natural es la variacion total distancia definida por
‖π − v‖TV = max|π(A)− v(A)| : A ⊂ S.
Es facil ver que se obtiene el maximo en el conjunto A = x : π(x) ≥ v(x).Por
tanto,
‖π − v‖TV =∑
π(x)≥v(x)
(π(x)− v(x))
=1
2
∑π(x)≥v(x)
(π(x)− v(x)) +∑
π(x)<v(x)
(v(x)− π(x))
=
1
2
∑x∈S
|π(x)− v(x)|
=1
2
∑x∈S
1
N|Nπ(x)−Nv(x)|.
En la ultima expresion, la 1/N representa la medida uniforme en S y Nπ, Nv
son las “derivadas” de π, v con respecto a esta medida. Otra medida de la
distancia que no es tan natural, pero a veces es mas facil de analizar es la L2
o la distancia de cuadratico medio,
‖π − v‖L2 =
[∑x∈S
1
N|Nπ(x)−Nv(x)|2
] 12
.
24
Note que ‖π− v‖L2 = N12‖π− v‖ donde ‖ · ‖ denota la norma Euclidiana usual
en RN . La desigualdad de Cauchy-Schwartz
|v · w| ≤ ‖v‖12‖v‖
12 ,
da la desigualdad
‖π − v‖L2 ≥ 2‖π − v‖TV [6].
Ejemplo 8. Considere el paseo aleatorio en el grafo formado por los 4 vertices
de un cuadrado y sus lados, que corresponde con el siguiente grafo de transicion,
donde todas las probabilidades son 12, y los vertices estan enumerados 1, 2, 3, 4.
Figura 1.5: El grafo de un cuadrado.
Su matriz de transicion es:
A =
0 1
20 1
2
12
0 12
0
0 12
0 12
12
0 12
0
Esta cadena es irreducible y recurrente positiva, y su medida invariante es
25
π(14, 14, 14, 14). Por otra parte tenemos
A2 =
12
0 12
0
0 12
0 12
12
0 12
0
0 12
0 12
Ası, se puede obtener todas las potencias de A, es decir, A2n+1 = A y A2n = A2.
En particular, por ejemplo, la sucesion A(n)(1, 1) vale 12
si n es par, y 0 si n es
impar, por lo que claramente no converge cuando n −→∞. Sin embrago, se ve
que converge a 14
en promedio.
1.1.8. Algoritmos de Cadenas de Markov
Una aplicacion reciente de la teorıa de la cadena de Markov ha estado en si-
mulaciones de Monte Carlo de sistemas aleatorios. Estas simulaciones siempre
utilizan numeros aleatorios distribuidos uniformemente entre 0 y 1. Como ejem-
plo, suponga que esta interesado en estudiar las propiedades de las matrices
aleatorias cuyas entradas son 0 y 1. Como espacio de probabilidad que se puede
elegir es el conjunto S de N ×N matrices M, con
M(i, j) = 0 o 1, 1 6 i, j 6 N.
Una medida de probabilidad natural serıa la medida uniforme en todos los 2N2
de tales matrices. Escribir un algoritmo para producir una matriz aleatoria de
esta distribucion es facil elegir N2 numeros aleatorios uniformes U(i, j), 1 ≤
i, j ≤ N, y el conjunto
M(ij) = δij =
0, si U(i, j) < 0, 5
1, si U(i, j) ≥ 0, 5
Se necesita del orden de N2 operaciones para producir una matriz de N ×N ,
y claramente toda matriz en S tiene la misma probabilidad de ser producida.
Ahora suponga que se cambia de espacio de probabilidad y decir que solo se
26
esta interesado en matrices en S que no tienen dos 1 juntos. Sea T las matrices
en S con dos 1 no juntos, es decir, las matrices M ∈ S tal que
M(i− 1, j) = M(i+ 1, j) = M(i, j − 1) = M(i, j + 1) = 0,
Si M(i, j) = 1. Suponga tambien que se pretende poner la medida de proba-
bilidad uniforme en T . Si bien es facil de definir esta medida, es un problema
difıcil de determinar c(N), el numero de elementos de T. Existe una constante
β ∈ (1, 2) tal que
lımN→∞
c(N)1N2 = β
(De manera que el numero de elementos en T es de aproximadamente βN2),
pero el valor exacto de β no se conoce. Lo que se hace es ejecutar una cadena
de Markov irreducible con el espacio de estado T cuya medida invariante es
la distribucion uniforme. entonces se puede comenzar con cualquier matriz en
T ; ejecutar la cadena de tiempo suficiente para que la cadena esta cerca del
equilibrio; y luego elegir la matriz que se tiene en ese punto. Para este ejemplo,
el algoritmo es el siguiente:
1. Comenzar con cualquier matriz M ∈ T , por ejemplo, la matriz con todas
las entradas de cero.
2. Elegir una de las entradas al azar, es decir, elegir un par ordenado (i, j)
de la distribucion uniforme en la N2 pares ordenados.
3. Considerar la matriz donde se puede cambiar solo la entrada (i, j) de M.
Si esta nueva matriz esta en T , se deja que esto sea el nuevo valor de la
cadena; si la nueva matriz no esta en T , no se ofrece ninguna variacion
en el valor de la cadena; volver al paso 2.
Este algoritmo es una simulacion de la cadena de Markov de tiempo discreto
con el espacio de estado T y de probabilidades de transicion
27
P(M,M′) = N−2,
Si M,M′ ∈ T difieren en exactamente una entrada; P(M,M′) = 0 si M y M′
difieren en mas de una entrada; y P(M,M) es todo lo que se necesita para que
las filas se suman a 1. P es una matriz simetrica e irreductible. Por lo tanto P
es una cadena de Markov reversible con el espacio de estado T y su distribucion
invariante es la medida uniforme. En este ejemplo, se necesitan por lo menos
N2 pasos para acercarse, ya que cada una de las entradas deben tener una
oportunidad de ser cambiadas [6].
Figura 1.6: Diagrama de flujo del Algoritmo de Cadena de Markov.
Ejemplo 9. Sea G = (V,E) un grafo tal que cada vertice es adyacente maximo
a k vertices. Sea f una funcion positiva en V y π es su medida de probabilidad
π(v) =f(v)∑
w∈V f(w).
28
Se escribe v v w si (v, w) ∈ E y el conjunto
P (v, w) =1
kmın
1,f(w)
f(v)
, v v w
y
P (v, v) = 1−∑wvv
P (v, w).
Entonces P es una cadena de Markov irreducible y reversible con respecto a π.
Este tipo de Algoritmo se lo conoce como Algoritmo de Hastings-Metropolis en
cual se lo vera de manera mas detallada en el capıtulo siguiente .
Para entender un poco mejor el ejemplo anterior acontinuacion se lo hara con
datos
Ejemplo 10. Sea
Figura 1.7: Representacion del grafo con vertices adyacentes.
la matriz de los pesos de grafo anterior es de la siguiente forma:
W =
0 2 4 3 1
2 0 3 0 0
4 3 0 0 2
3 0 0 0 0
1 0 2 0 0
29
para obtener la medida de probabilidad o vector de probabilidad lımite se utiliza
π(v) =f(v)∑
w∈V f(w).
Ası, se tiene
π(1) =2 + 4 + 3 + 1
(2 + 4 + 3 + 1) + (2 + 3) + (4 + 3 + 2) + (3) + (1 + 2)=
1
3.
π(2) =2 + 3
(2 + 4 + 3 + 1) + (2 + 3) + (4 + 3 + 2) + (3) + (1 + 2)=
1
6.
π(3) =4 + 3 + 2
(2 + 4 + 3 + 1) + (2 + 3) + (4 + 3 + 2) + (3) + (1 + 2)=
3
10.
π(4) =3
(2 + 4 + 3 + 1) + (2 + 3) + (4 + 3 + 2) + (3) + (1 + 2)=
1
10.
π(5) =1 + 2
(2 + 4 + 3 + 1) + (2 + 3) + (4 + 3 + 2) + (3) + (1 + 2)=
1
10.
Luego, la matriz de transicion esta dada por:
P =
0 0,20 0,40 0,30 0,10
0,40 0 0,60 0 0
0,44 0,33 0 0 0,22
1 0 0 0 0
0,33 0 0,67 0 0
Para verificar que es reversible se aplica la Proposicion 6. Ası se tiene:
(P 100)T ∗ P =
0 0,0667 0,1333 0,1 0,0333
0,0667 0 0,1 0 0
0,1333 0,1 0 0 0,0667
0,1 0 0 0 0
0,0333 0 0,0667 0 0
Por tanto, P es una cadena de Markov irreducible y reversible con respecto a
π.
30
CAPITULO II
ALGUNAS APLICACIONES DE LAS CADENAS DE
MARKOV REVERSIBLES
2.1. Metodos de Monte Carlo con cadenas de
Markov
2.1.1. Que es el metodo de Monte Carlo
El Metodo Monte Carlo o Simulacion Monte Carlo agrupa una serie de proce-
dimientos que analizan distribuciones de variables aleatorias usando simulacion
de numeros aleatorios. El termino Monte Carlo se aplica a un conjunto de meto-
dos matematicos que se empezaron a usar en los anos 1940 para el desarrollo de
armas nucleares en Los Alamos. Consisten en resolver un problema mediante la
invencion de juegos de azar cuyo comportamiento simula algun fenomeno real
gobernado por una distribucion de probabilidad o sirve para realizar un calcu-
lo. Mas tecnicamente, un Monte Carlo es un proceso estocastico numerico, es
decir, una secuencia de estados cuya evolucion viene determinada por sucesos
aleatorios.
El metodo de Monte Carlo permite resolver problemas matematicos mediante la
simulacion de variables aleatorias. John Von Neumann, en los anos 40 y con los
primeros ordenadores, aplica la simulacion para resolver problemas complejos
que no podıan ser resueltos de forma analıtica. Monte Carlo y su casino estan
relacionados con la simulacion. La ruleta, juego estrella de los casinos, es uno
de los aparatos mecanicos mas sencillos que nos permiten obtener numeros
31
aleatorios para simular variables aleatorias.
2.2. Metodos de Monte Carlo con cadenas de
Markov Reversibles: Algoritmos
De manera general, es muy difıcil simular el valor de un vector aleatorio X
cuyas variables aleatorias componentes son dependientes. En este capıtulo se
presentan los principales algoritmos para construir una cadena de Markov con
una funcion de masa de probabilidad dada como distribucion lımite. En los si-
guientes algoritmos se muestra, para un conjunto dado de numeros positivos bj,
j = 1, ..., N , la forma de construir una cadena de Markov cuyas probabilidades
lımite sean πj = bj/N∑i=1
bi [13].
2.2.1. El Algoritmo de Hastings-Metropolis.
Sean b(j), j = 1, ...,m numeros positivos, y sea B =m∑j=1
b(j). Se supone que
m es grande, que B es difıcil de calcular y que se quiere simular una variable
aleatoria con funcion de masa de probabilidad
π(j) = b(j)/B, j = 1, ...,m
Para simular una sucesion de variables aleatorias cuyas distribuciones convergen
a π(j), j = 1, ...,m, se determina una cadena de Markov que sea facil de simular
y cuyas probabilidades limites sean las πj. Esto se lo hace con El algoritmo de
Hastings-Metropolis que nos proporciona un metodo para construir una cadena
de Markov reversible en el tiempo con las probabilidades lımites deseadas [10].
Sea Q una matriz de probabilidades de transicion de Markov irreducible sobre
los enteros 1, ...,m, donde q(i, j) representa el elemento de Q en el renglon i y la
columna j. Sea Xn, n ≥ 0 una cadena de Markov como sigue. Cuando Xn = i,
se genera una variable aleatoria X tal que PX = j = q(i, j), j = 1, ...,m. Si
32
X = j, entonces Xn+1 es igual a j con probabilidad α(i, j) y es igual a i con
probabilidad 1− α(i, j). En estas condiciones, se puede ver que la sucesion de
estados formara una cadena de Markov con probabilidades de transicion Pij
dadas por
Pi,j = q(i, j)α(i, j), si j 6= i
Pi,i = q(i, i) +∑k 6=i
q(i, k)(1− α(i, k))
Esta cadena de Markov sera reversible en el tiempo y tendra probabilidades
estacionarias π(j) si
π(i)Pi,j = π(j)Pj,i para j 6= i
que es equivalente a
π(i)q(i, j)α(i, j) = π(j)q(j, i)α(j, i)
Para verificar que esto se satisface se considera
α(i, j) = mın
(π(j)q(j, i)
π(i)q(i, j), 1
)= mın
(b(j)q(j, i)
b(i)q(i, j), 1
)
[13].
El algoritmo de Hastings-Metropolis para generar una cadena de Markov rever-
sible en el tiempo, cuyas probabilidades lımites son π(j) = b(j)/B, j = 1, ...,m.
El algoritmo tiene los siguientes pasos:
1. Elegir una matriz Q de probabilidades de transicion, de Markov, irre-
ducible, con probabilidades de transicion q(i, j), i, j = 1, ...,m. Ademas,
elegir algun valor entero k entre 1 y m.
2. Sean n = 0 y X0 = k.
3. Generar una variable aleatoria X tal que PX = j = q(Xn, j) y generar
33
un numero aleatorio U .
4. Si U < [b(X)q(X,Xn)]/[b(Xn)q(Xn, X)], entonces NS = X; en caso con-
trario, NS = Xn.
5. n = n+ 1, Xn = NS.
6. Ir al paso 3.
[10]
2.2.2. Ejemplo: Simulacion de la Distribucion Beta uti-
lizando el algoritmo de Hastings-Metropolis.
En el siguiente ejemplo se aplica el algoritmo de Hastings-Metropolis.
Ejemplo 11. Simular numeros aleatorio con distribucion Beta(a, b) utilizando
el algoritmo de Hastings-Metropolis.
Sea la cadena de Markov donde su probabilidad de transicion viene dada por
la distribucion de probabilidad de una variable uniforme sobre [0,1], lo que
significa que no depende de el valor anterior de la cadena.
Luego se da valores a los parametros a = 2, 7 y b = 6, 3 para aplicar el algoritmo
de Hastings-Metropolis y ası obtener lo siguiente [11]:
Sintaxis de R: Muestra de la distribucion beta utilizando el algoritmo de
Hastings-Metropolis.
a=2.7; b=6.3; # inicializar valores
N=5000
X=rep(runif(1),N) # inicializar cadena
for (i in 2:N)
Y=runif(1)
alpha=dbeta(Y,a,b)/dbeta(X[i-1],a,b)
X[i]=X[i-1] + (Y-X[i-1])*(runif(1)<alpha)
34
par(mfrow=c(1,3))
plot(X,type = "l", xlab = "Iteraciones",
ylab = "X",xaxp=c(0,5000,100),col="red")
hist(X, prob= T, main="Histograma de Beta",
xlab= "X", ylab="Frecuencias", col=11)
curve(dbeta(x,2.7,6.3),add = T, col="red")
x <- rbeta(5000,2.7,6.3)
hist(x, prob=T, main="Histograma de Beta",
xlab= "X", ylab="Frecuencias", col=12)
curve(dbeta(x,2.7,6.3), add = T, col="red")
Figura 2.1: Sucesion de Xn para n = 1, ..., 5000 cuando se simula a partir
del algoritmo de Hastings-Metropolis con la distribucion uniforme propuesta y
Beta(2, 7; 6, 3).
35
Figura 2.2: Histogramas de beta Beta(2, 7; 6, 3) variables aleatorias con fun-
cion de densidad superpuestos. En el panel izquierdo, las variables se generan a
partir del algoritmo de Hastings-Metropolis con un distribucion uniforme, y en
el panel derecho de las variables aleatorias se generaron directamente a traves
de la funcion rbeta(n; 2, 7; 6, 3).
Se ve que el histograma obtenido de la simulacion con 5000 iteraciones se ajus-
ta a la forma de la distribucion de probabilidad beta propuesta.
Por lo tanto, el algoritmo de Hastings-Metropolis es una buena herramienta
para simular los valores de dicha distribucion y se espera que funcione para las
demas funciones de distribucion de probabilidad.
Ejemplo 12. Simular una distribucion de Cauchy C(0, 1)
f(x | 0, 1) =1
π(1 + x2)
utilizando el algoritmo de Hastings-Metropolis.
Sea la cadena de Markov donde su probabilidad de transicion viene dada por
la distribucion de probabilidad de una variable normal con desviacion estandar
36
igual a 2.
Sintaxis de R: Muestra de la distribucion de Cauchy C(0, 1) utilizando el
algoritmo de Hastings-Metropolis.
sigma <- 2
N <- 10000
x <- rep(0,N)
x[1] <- rnorm(1)
for(i in 2:N)
y <- x[i-1]+sigma*rnorm(1)
u <- runif(1)
ratio <-
(dcauchy(y)*dnorm(x[i-1],y,sigma))/
(dcauchy(x[i-1])*dnorm(y,x[i-1],sigma))
alpha <- min(1,ratio)
if(u<=alpha) x[i] <- y
else x[i] <- x[i-1]
library(MASS)
truehist(x)
curve(dcauchy(x),-30,30,add=TRUE,col="red")
title("Histograma de valores simulados
y la funci\’on de densidad")
Luego, de simular la distribucion se obtiene:
37
Figura 2.3: Histograma obtenido despues de realizar 10000 iteraciones.
2.2.3. La Urna de Polya
Sea el esquema del modelo de la Urna de Polya. Una urna contiene Wn bolas
blancas y Bn bolas negras en el instante n. Se extrae al azar una bola, se
reemplaza y se anaden α bolas del mismo color a la urna. La sucesion
Wn
Wn +Bn
, n −→∞
converge con probabilidad 1 a una variable aleatoria que tiene distribucion beta
con parametros a = W0/α, b = B0/α [8].
2.2.3.1. Probabilidad de Transicion del Modelo de la Urna de Polya
Suponga que inicialmente se tiene W0 bolas blancas y B0 bolas negras en una
urna. Sea Wn el numero de bolas blancas obtenidas en los primeros n sorteos.
Por tanto, Bn = n −Wn es el numero de bolas negras hasta n y el numero
total de bolas blancas en la urna es W0 + αWn mientras que el numero total
38
de bolas negras es B0 +α(n−Wn). Como los sorteos son de forma aleatoria, la
probabilidad de extraer una bola blanca en el siguiente paso depende solo del
numero de bolas blancas y bolas negras en la urna. Es decir,
P [Wn+1 = Wn + 1|Wn = i] =W0 + αi
W0 +B0 + αn
y
P [Wn+1 = Wn|Wn = i] =B0 + α(n− i)W0 +B0 + αn
Por tanto, Wn es una cadena de Markov en el tiempo discreto.
Note que los posibles valores para Wn son 0, 1, ..., n, entonces cuando Wn = i,
las probabilidades de transicion son
pij(n, n+ 1) =
W0+αi
W0+B0+αn, j = i+ 1,
B0+α(n−i)W0+B0+αn
, j = i,
0 , caso contrario.
Como las probabilidades dependen de n, entonces la cadena de Markov es no
homogenea [7].
Ejemplo 13. En este ejemplo se calcula la matriz de probabilidades del Modelo
de Urna de Polya tomando los valores iniciales B0 = 2,W0 = 4, α = 1 y n = 10,
con el fin de ver si se trata de una cadena de Markov reversible.
39
Solucion Sea la matriz de transicion en el paso n = 10
P 10 =
0,69 0,31 0 0 0 0 0 0 0 0
0 0,62 0,38 0 0 0 0 0 0 0
0 0 0,56 0,44 0 0 0 0 0 0
0 0 0 0,50 0,50 0 0 0 0 0
0 0 0 0 0,44 0,56 0 0 0 0
0 0 0 0 0 0,38 0,62 0 0 0
0 0 0 0 0 0 0,31 0,69 0 0
0 0 0 0 0 0 0 0,25 0,75 0
0 0 0 0 0 0 0 0 0,19 0,81
0 0 0 0 0 0 0 0 0. . .
Entonces, se tiene
P ∗ (P 10)T =
0,47 0 0 0 0 0 0 0 0 0
0 0,39 0 0 0 0 0 0 0 0
0 0 0,32 0 0 0 0 0 0 0
0 0 0 0,25 0 0 0 0 0 0
0 0 0 0 0,19 0 0 0 0 0
0 0 0 0 0 0,14 0 0 0 0
0 0 0 0 0 0 0,10 0 0 0
0 0 0 0 0 0 0 0,06 0 0
0 0 0 0 0 0 0 0 0,04 0
0 0 0 0 0 0 0 0 0. . .
Como el modelo de Urna de Polya es una cadena de Markov no homogenea,
entonces no tiene el vector lımite ~π y por tanto es una cadena de Markov no
estacionaria. Ademas, a pesar de que al final se obtiene una matriz simetrica,
se concluye que la Urna de Polya no es una cadena de Markov reversible por
definicion de reversibilidad.
40
Teorema 3. La sucesion (ρn)n ≥ 0, ρn =Wn
Wn +Bn
converge con probabilidad
1 a una variable aleatoria ρ∞ cuya distribucion es una Beta(W0
α, B0
α) [2].
Demostracion 3 Sea
Xn =
1 si una bola blanca fue extraıda en el sorteo n-esimo.
0 si caso contrario.
Defina Fn = σ(Xi; 1 ≤ i ≤ n) como la filtracion natural de esta sucesion y note
que, (Xn+1 | Fn) sigue una distribucion Ber(Wn
Wn +Bn
).
Se muestra que (ρn)n ≥ 0 es una F −martingala.
E(ρn+1 | Fn) = E
(Wn+1
Wn+1 +Bn+1
|Fn)
= E
(Wn+1
W0 +B0 + (n+ 1)α| Fn
)=
1
W0 +B0 + (n+ 1)αE (Wn + αXn+1 | Fn)
=1
W0 +B0 + (n+ 1)α
(Wn + α
Wn
Wn +Bn
)(2.1)
=Wn(Wn +Bn + α)
W0 +B0 + (n+ 1)α)(Wn +Bn)
=Wn(Wn +Bn + α)
Wn +Bn + α)(Wn +Bn)
=Wn
Wn +Bn
= ρn
En (2.1) se utiliza el hecho de que (Xn+1 | Fn) sigue una distribucion Ber(
Wn
Wn+Bn
).
Como E(ρn+1 | Fn) = ρn, se sigue que la sucesion (ρn) es una martingala y por
definicion, una submartingala. Note que ρn ≤ 1, ∀n ∈ N . Entonces el Teorema
de la convergencia de martingalas garantiza que existe una variable aleatoria
41
ρ∞ tal que
ρn −→ ρ∞, n −→∞
Luego de verificar que la sucesion ρn converge a una variable aleatoria ρ∞, se
puede estudiar la distribucion de esta variable.
Sea W nk como el conjunto de k bolas blancas en los primeros n sorteos. Se sigue
entonces que
P (W nk ) =
(n
k
)W0(W0 + α)...(W0 + (k − 1)α)B0(B0 + α)(B0 + (n− k − 1)α)
(W0 +B0)(W0 +B0 + α)...(W0 +B0 + (n− 1)α)(2.2)
Con la ecuacion (2.2) se obtiene que la sucesion Xn no posee independencia
entre sus terminos, es decir que la probabilidad de retirar k bola blancas en
los primeros n sorteos, (0 ≤ k ≤ n) no depende de la sucesion de colores
elegidos al azar, pero solo el numero acumulado de cada color. Ası las variables
X2, X2, ..., Xn de la Urna de Polya son permutables, mas no independientes.
Dividiendo todos los terminos del numerador y el denominador de (2.2) por α,
y llamando W0
αy B0
αde W y B, respectivamente y usando los hechos:
1. Γ(W ) = (W − 1)!
2. WΓ(W ) = Γ(W + 1),
Se obtiene,
Γ(W+k)Γ(W )︷ ︸︸ ︷
(W + 1)...(W + k − 1)
Γ(B+n−k)Γ(B)︷ ︸︸ ︷
B(B + 1)...(B + (n− k − 1))
(W +B)(W +B + 1)(W +B + (n− 1))︸ ︷︷ ︸Γ(W+B+n)
Γ(W+B)
=Γ(W + k)
Γ(B)
Γ(B + n− k)
Γ(B)
Γ(W +B)
W +B + n
=β(W + k,B + n− k)
β(W,B)
=β(W0
α+ k, B0
α+ n− k
)β(W0
α, B0
α
)
42
esto es:
P (Wk) =
(n
k
)β(W0
α+ k, B0
α+ n− k
)β(W0
α, B0
α
)Tomando la funcion caracterıstica, se tiene:
φρn(t) = E(eitρn) =n∑k=0
(n
k
)eit
W0+kαW0+B0+nα
∫ 1
0
pk(1− p)n−k pW−1(1− p)B−1
β(W,B)dp
= eit
W0W0+B0+nα
1
β(W,B)
∫ 1
0
n∑k=0
(n
k
)(pe
it αW0+B0+nα
)k(1− p)n−kpW−1(1− p)B−1dp
por el Teorema Binomial, se obtiene
= eit
W0W0+B0+nα
1
β(W,B)
∫ 1
0
(pe
it αW0+B0+nα + (1− p)
)npW−1(1− p)B−1dp
Tomando(pe
it αW0+B0+nα + (1− p)
)ny dividiendo el numerador y el denomina-
dor del exponente it W0
W0+B0+nαpor α, se tiene
(pe
itW+B+n + (1− p)
)n=
[p
(1 +
it
W +B + n+O
(1
n2
))+ (1− p)
]n=
[p+
itp
W +B + n+O
( pn2
)+ 1− p
]n=
[1 +
itp
W +B + n+O
( pn2
)]n−−−→n→∞
eitp
Entonces por el Teorema de la Convergencia Dominada, y tomando el lımite
cuando n −→∞,
lımn→∞
eitW0
W0+B0+nα1
β(W0
α, B0
α
) ∫ 1
0
eitppW0α−1(1− p)
B0α−1dp
=1
β(W0
α, B0
α
) ∫ 1
0
eitppW0α−1(1− p)
B0α−1dp
que es la funcion caracterıstica de la distribucion Beta(W0
αB0
α
). Entonces, por
el Teorema de la continuidad de Paul Levy, se tiene que ρ∞ converge a una
distribucion Beta(W0
α, B0
α
).
43
2.2.3.2. Simulacion del Modelo de la Urna de Polya
Se simulara el Modelo de la Urna de Polya basandose en la anterior descripcion
y el Teorema 3. Por un lado, se quiere ver si la proporcion de las bolas blancas
despues de varios ensayos es estacionaria; Por otro lado, queremos verificar que
ρ∞ −→ Beta(W0
α, B0
α
)por ajuste de curvas.
La figura siguiente es el resultado de la simulacion con los valores iniciales W0,
B0 y α.
Sintaxis de R: Muestra del Modelo de la Urna de Polya.
w<-4 # Bolas blancas
b<-2 # Bolas negras
alpha<-1 # valor de alpha
n<-1000 # n ensayos
p<-matrix(0,n,1)
for (i in 1:n)
u <- runif(n)
if (u >= (b/(w+b)))
w = w + alpha
else
b = b + alpha
p[i] = w/(w + b)
X = c(1:n)
plot(X, p,type = "l",main = "Proporcion de Bolas Blancas",
xlab = "N ensayos",ylab = "Proporcion ",col="blue")
44
Figura 2.4: W0 = 4, B0 = 2, α = 1 y n = 1000
.
En la figura, donde las bolas blancas son mas que las negras en el momento
inicial se observa que los resultados de la proporcion es estacionaria despues de
varios ensayos, y los resultados seran mas de 0,5 en la mayorıa de veces, lo que
significa que una vez que las bolas blancas son mas al principio, seran mas en
la mayorıa de las veces .
La figura siguiente muestra la distribucion de la proporcion de bolas blancas.
Sintaxis de R: Muestra de la Distribucion Beta a la que converge el Modelo
de la Urna de Polya.
n<-1000 # n ensayos
p<-matrix(0,n,1);
for (k in 1:n)
w<- 4
b<- 2
45
for (j in 1:n)
sorteo<-sample(0:1,size=1,prob=c(w,b)/(w+b))
w<-w +(1-sorteo)
b<-b+sorteo
p[k]<-w/(w+b)
hist(p, freq=F,main="Funcion de Densidad aproximada de la
funcion Beta", xlab= "Proporcion de bolas blancas
despues de 1000 ensayos", ylab= "Densidad", col=15)
curve(dbeta(x,4,2),add =T, col="blue")
Figura 2.5: W0 = 4, B0 = 2, α = 1 y n = 1000
Con la figura anterior se aprecia que ρ∞ −→ Beta(W0
α, B0
α
).
2.2.4. El muestreador de Gibbs.
El muestreador de Gibbs es un caso especial del algoritmo de Hastings-Metropolis.
Sea X = (X1, ..., Xn) un vector aleatorio con funcion de masa de probabilidad
46
p(x), la cual solo esta determinada salvo una constante multiplicativa, y su-
ponga que se quiere generar un vector aleatorio cuya distribucion sea la de la
distribucion condicional de X, dado que X ∈ A para algun conjunto A. Es
decir, generar un vector aleatorio con funcion de masa
f(x) =p(x)
PX ∈ Apara x ∈ A
El muestreador de Gibbs supone que para cualquier i, i = 1, ..., n y cualesquiera
valores xj, j 6= i, se generar una variable aleatoria X con la funcon de masa de
probabilidad [13]
PX = x = PXi = x | Xj = xj, j 6= i
Esto funciona si primero se considera una cadena de Markov con estados x =
(x1, ..., xi, ..., xn) ∈ A ; luego se utiliza el algoritmo de Hastings-Metropolis con
las probabilidades de transicion de Markov definidas como sigue. Siempre que el
estado actual sea x, se genera una coordenada que tiene la misma probabilidad
de ser cualquiera de los valores 1, ..., n. Si la coordenada i es la elegida, entonces
se genera una variable aleatoria X con funcion de masa de probabilidad PX =
x = PXi = x | Xj = xj, j 6= i y X = x, entonces se considera el estado
y = (x1, ..., xi−1, xi, xi+1, ..., xn) para la transicion. Ası, el muestreador de Gibbs
emplea el algoritmo de Hastings-Metropolis con
q(x, y) =1
nPXi = x | Xj = xj, j 6= i =
1
n
p(y)
PXj = xj, j 6= i
Como la funcion de masa objeto es f , el vector y se acepta como el nuevo
estado con probabilidad
α(x, y) = mın
(f(y)q(y, x)
f(x)q(x, y), 1
)
47
Como para x ∈ A y y 6∈ A.
f(y)q(y, x)
f(x)q(x, y)= 0
se ve que el siguiente estado es y si y ∈ A, o sigue siendo x si y 6∈ A. En resumen,
la cadena de Markov reversible en el tiempo, con probabilidades estacionarias
dadas por f , generada por el muestreador de Gibbs es la siguiente.
1. Sea x = (x1, ..., xn)un vector en A para el cual p(x) > 0.
2. Sea I una variable aleatoria que toma uno de los valores 1, ..., n donde
cada valor tiene la misma probabilidad de ocurrir.
3. Si I = i, generar el valor de una variable aleatoria X tal que
PX = x = PXi = x | Xj = xj, j 6= i
4. Si X = x y (x1, ..., xi−1, xi, xi+1, ..., xn) ∈ A , entonces el nuevo valor de
xi es igual a x. En caso contrario, se mantiene el valor de xi.
5. Regresar al paso 2 [12].
Ejemplo 14. Considerando el par de distribuciones
X | θ v Bin(m, θ), θ v Be(a, b),
que conducen a la distribucion conjunta
f(x, θ) =
(a
b
)Γ(a+ b)
Γ(a)Γ(b)θx+a−1(1− θ)m−x+b−1.
La correspondiente distribucion condicional de X | θ esta dada anteriormente,
mientras que θ | x ∼ Be(x+ a,m− x+ b) [11]. Implementando el muestreador
de Gibbs, se obtiene:
Sintaxis de R: Muestra de la distribucion conjunta entre la distibucion
beta y beta-binomial utilizando el muestreador de Gibbs.
48
N=5000 #inicializar valores
m=15
a=3
b=7
X=T=array(0,dim=c(N,1)) #inicializar array
T[1]=rbeta(1,a,b) #inicializar cadena
X[1]=rbinom(1,m,T[1])
for (i in 2:N) #bucle de muestreo
X[i]=rbinom(1,m,T[i-1])
T[i]=rbeta(1,a+X[i],m-X[i]+b)
plot(X,type = "l", xlab = "Iteraciones",
ylab = "X",xaxp=c(0,5000,100),col="red")
#hist(X,freq = F, prob= T,
main="Histograma de Beta-binomial",
xlab= "X", ylab="Densidad marginal", col=11)
#plot(T,type = "l", xlab = "Iteraciones",
ylab = "Theta",xaxp=c(0,5000,100),col="black")
#hist(T, freq = F, prob= T, main="Histograma de Beta",
xlab= "Theta", ylab="Densidad marginal", col=15)
49
Figura 2.6: Sucesion de la distribucion marginal de X implementando el mues-
treador de Gibbs sobre la base de 5000 iteraciones para m = 15; a = 3; b =
7.
Figura 2.7: Histograma de la distribucion marginal de X implementando el
muestreador de Gibbs sobre la base de 5000 iteraciones para m = 15; a = 3; b
= 7.
50
Figura 2.8: Sucesion de la distribucion marginal de θ implementando el mues-
treador de Gibbs sobre la base de 5000 iteraciones para m = 15; a = 3; b =
7.
Figura 2.9: Histograma de la distribucion marginal de θ implementando el
muestreador de Gibbs sobre la base de 5000 iteraciones para m = 15; a = 3; b
= 7.
La verdadera distribucion marginal de θ es Be(a, b) y la distribucion marginal
de X es beta-binomial.
51
CAPITULO III
CONCLUSIONES Y RECOMENDACIONES
3.1. CONCLUSIONES
Cabe indicar que dicho proyecto de titulacion que se presento no debe
interpretarse como si fuese un artıculo completo. Mas bien, el objetivo es
mostrarles informacion de cadenas de Markov reversibles de forma sencilla
y ver que se pueden aplicar a las diferentes distribuciones.
La importancia de exponer metodos de cadenas Markov Monte Carlo para
este trabajo y especialmente el uso de la simulacion radica en la necesidad
cierta de ver como se comportan las trayectorias de un proceso de este
tipo, pues nos permite tener una mejor idea de lo que esta pasando con
la cadena.
Las cadenas de Markov reversibles son un gran aporte de las matematicas
y no es necesario tener grandes conocimientos sobre el tema para poder
entender su funcionamiento.
Los Metodos de Monte Carlo facilitan la generacion de muestra de vec-
tores aleatorios con distribuciones estacionarias, estos metodos son de
gran utilidad al momento de generar vectores aleatorios cuyas variables
aleatorias componentes son dependientes.
Los Metodos de Monte Carlo estan fundamentados en la construccion de
cadenas de Markov reversibles en el tiempo con una funcion de masa de
probabilidad dada como distribucion lımite.
52
3.2. RECOMENDACIONES
Una vez concluido el proyecto de titulacion, se considera investigar otros
metodos de simulacion para comparar los resultados y reafirmar el com-
portamiento de dicho proceso.
A medida que transcurre el tiempo se van modificando y optimizando
los metodos de simulacion de Monte Carlo es por eso que se recomienda
utilizar los actualizados para tener mejores resultados.
Estudiar los proceso estocastico mediante la simulacion de los metodos
de Monte Carlo.
Se recomienda extender los alcances de las aplicaciones con datos reales.
53
CAPITULO A
ANEXOS
Distribucion Beta
Definicion: Sean a, b ∈ R. La funcion de densidad de la Distribucion Beta
es:
f(x; a, b) =1
β(a, b)xa−1(1− x)b−1, 0 < x < 1,
donde a > 0, b > 0 y β(a, b) es la funcion Beta dada por:
β(a, b) =
∫ 1
0
xa−1(1− x)b−1dx, a > 0, b > 0.
Por ultimo la funcion caracterıstica de la distribucion Beta(a, b) esta dada por:
φX(t) = E(eitX) =
∫ 1
0
e(itx)fX(x)dx =1
β(a, b)
∫ 1
0
eitxxa−1(1− x)b−1dx
Martingalas
Definicion de Filtracion: Una filtracion es una sucesion creciente (Fn)n≥1
de sub σ−algebras F1 ⊂ F2 ⊂ ... ⊂ Fn. Una sucesion de variables aleatorias
(Xn)n≥1 en (Ω,F) es adaptada a (Fn)n≥1 si Xn ∈ Fn,∀n. Una sucesion dupla
(Xn,Fn)n≥1, donde (Fn)n≥1 es una filtracion y (Xn)n≥1 es adaptada a (Fn)n≥1
es llamada sucesion estocastica.
54
Definicion de Filtracion Natural: Cuando una filtracion es asociada a una
sucesion de variables aleatorias como Fn = σ(Y1, ..., Yn), la llamamos filtracion
natural asociada a (Yn)n≥1).
Definicion de Martingala: Una sucesion estocastica (Xn,Fn)n≥1), en la
cual Xn ∈ L1 es llamada
una martingala si, para todo n ≥ 1,
E(Xn+1 | Fn) = Xn
una submartingala si, para todo n ≥ 1,
E(Xn+1 | Fn) ≥ Xn
una supermartingala si, para todo n ≥ 1,
E(Xn+1 | Fn) ≤ Xn
Teorema de convergencia de martingalas: Sea (Y,F) una submartingala
y suponga que ∃M ;∀n, E(Y +n ) ≤M . Entonces existe una variable aleatoria Y∞,
tal que Yn −→ Y∞.
55
BIBLIOGRAFIA
[1] Bartle, G., (1995), The Elements of Integration and Lebesgue Measure,New York - Estados Unidos, Eastern Michigan University and Universityof Illinois, Wiley Classic Library, Jhon Wiley & Sons, INC.
[2] Freedman, D., (1965), Bernard Freedman’s Urn, Estados Unidos, Uni-versity of California-Berkeley.
[3] Gamerman, D. and Freitas Lopes, H., (2006), Markov Chain MonteCarlo: Stochastic Simulation for Bayesian Inference, Estados Unidos,Chapman & Hall/CRC, Second Edition.
[4] Grigoriu, M., (2002), Stochastic Calculus: Applications in Science andEngineering, Ithaca- Estados Unidos, Cornell University School of Civil.
[5] Karlin, S., (1975), A First Course in Stochastic Processes, New York-SanFrancisco, Academic Press, Second Edition.
[6] Lawler, G., (2006), Introduction to Stochastic Processes, Estados Unidos,Chapman & Hall/CRC.
[7] Kijima, M., (1997), Markov Processes for Stochastic Modeling, Japan-Tokyo, University of Tsukuba.
[8] Nadarajah, S. and Gupta, A., (2004), Handbook of Beta Distributionand Its Applications, U.S.A., Marcel Dekker.
[9] Rincon, L., (2011), Introduccion a los procesos Estocasticos, Mexico -Mexico, Departamento de Matematicas - Facultad de Ciencias UNAM.
[10] Rincon, L., (2012), Introduccion a los procesos Estocasticos, Mexico -Mexico, Departamento de Matematicas - Facultad de Ciencias UNAM.
56
[11] Robert, Christian P. and Casella, G., (2010), Introducing Mon-te Carlo Methods with R, Springer New York Dordrecht Heidelberg London.
[12] Sheldon, M. Ross, (2007), Introduction to Probability Models, Berkeley-California, University of California, Ninth Edition.
[13] Sheldon, M. Ross, (1999), Simulacion, Prentice Hall, Mexico, SegundaEdicion.
[14] West, Douglas B., (2001), Introduction to Graph Theory, India, Uni-versity of Illinois-Urbana, Second Edition.
57