estocastico

Vista previa del material en texto

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA
“ANTONIO JOSE DE SUCRE”
VICERRECTORADO BARQUISIMETO
DIRECCIÓN DE INVESTIGACION Y POSTGRADO
Aula Virtual - Lapso Académico Año 2022
PROCESOS ESTOCASTICOS
Eribert De Oliveira – CI 24336535
Profesor: María Aranguren
Barquisimeto, Diciembre de 2022
CADENA DE MARKOV
 La cadena de Markov, también conocida como modelo de Markov o proceso de Markov, es un concepto desarrollado dentro de la teoría de la probabilidad y la estadística que establece una fuerte dependencia entre un evento y otro suceso anterior. Su principal utilidad es el análisis del comportamiento de procesos estocásticos.
 Según señaló Markov, en sistemas o procesos estocásticos (es decir, aleatorios) que presentan un estado presente es posible conocer sus antecedentes o desarrollo histórico. Por lo tanto, es factible establecer una descripción de la probabilidad futura de los mismos.Más formalmente, la definición supone que en procesos estocásticos la probabilidad de que algo suceda solamente depende del pasado histórico de la realidad que estamos estudiando. Por este motivo, a menudo se dice que estas cadenas cuentan con memoria.
 La base de las cadenas es la conocida como propiedad de Markov, la cual resume lo dicho anteriormente en la siguiente regla: lo que la cadena experimente en un momento t + 1 solamente depende de lo acontecido en el momento t (el inmediatamente anterior).
Dada esta sencilla explicación de la teoría, puede observarse que es posible a través de la misma conocer la probabilidad de que un estado ocurra en el largo plazo. Esto ayuda indudablemente a la predicción y estimación en largos periodos de tiempo.
Una cadena de Markov tiene probabilidades de transición estacionarias si para cualquier par de estados si y sj existe una probabilidad de transición pij tal que:
 Un aspecto interesante en una cadena de Markov es su comportamiento a largo plazo. Intuitivamente, el comportamiento a largo plazo en una cadena de Markov (en caso que este exista), es un vector de probabilidades xx que nos indica las probabilidades de estar en cada uno de los estados después un número grande de repeticiones. De manera formal, el comportamiento a largo plazo en una cadena de Markov (en caso que este exista) se define como:
Nota: Existen cadenas de Markov que no tienen comportamiento a largo plazo definido. Sin embargo, existen condiciones que garantizan que una cadena de Markov tenga comportamiento a largo plazo bien definido, por ejemplo, si la matriz de transición PP tiene todas sus entradas estrictamente positivas se puede demostrar que la cadena de Markov tiene un comportamiento a largo plazo que está bien definido y este comportamiento a largo plazo es único.
Definición: Supongamos que tenemos una cadena de Markov con matriz de transición PP. Decimos que un vector xx es un vector estacionario si xx es un vector de probabilidad, es decir, si sus entradas son mayores o iguales a cero y suman 1 y además Px=xPx=x.
 Notemos que si xx es un vector estacionario, entonces Px=xPx=x, esto significa que xx es un vector propio de PP asociado al valor propio λ=1λ=1. En otras palabras, un vector estacionario es un vector propio de PP asociado al valor propio λ=1λ=1 que también es un vector de probabilidad.
Teorema: Si una cadena de Markov tiene comportamiento a largo plazo definido, entonces ese comportamiento a largo plazo es un vector estacionario.
Características:
· Número finito y conocido de estados.
· Probabilidades de transición conocidas y constantes. 
Se puede, eventualmente, pasar de un estado a cualquier otro. 
· No son ciclos simples.
Elementos de una Cadena de Markov:
Para definirla es necesario determinar:
· El conjunto de estados del sistema
· La definición de transición
· Una ley de probabilidad condicional, que defina la probabilidad como del nuevo estado en función de los anteriores. 
· Los estados son una caracterización de un sistema en un instante dado. 
· El estado de un sistema en un instante t es una variable cuyos valores sólo pueden pertenecer al conjunto de estados del sistema. 
· El estado del sistema en el tiempo t+1 dependerá solo del estado del sistema en el tiempo t
Aplicaciones
Meteorología: Si consideramos el tiempo atmosférico de una región a través de distintos días, es posible asumir que el estado actual solo depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos.
 Por ejemplo, se han desarrollado modelos de recurrencia de las lluvias basados en cadenas de Markov. 
Modelos epidemiológicos: Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Este es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una epidemia (véase modelaje matemático de epidemias).
Internet: El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través de una cadena de Markov, donde la posición que tendrá una página en el buscador será determinada por su peso en la distribución estacionaria de la cadena.
Simulación: Las cadenas de Márkov son utilizadas para proveer una solución analítica a ciertos problemas de simulación, por ejemplo en teoría de colas el Modelo M/M/14​ es de hecho un modelo de cadenas de Markov.
Juegos de azar: Son muchos los juegos de azar que se pueden modelar a través de una cadena de Márkov. El modelo de la ruina del jugador (Gambler's ruin), que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero, es una de las aplicaciones de las cadenas de Márkov en este rubro.
Economía y finanzas: Las cadenas de Márkov se pueden utilizar en modelos simples de valuación de opciones para determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de valores o para determinar la volatilidad de los precios. En los negocios, las cadenas de Márkov se han utilizado para analizar los patrones de compra de los deudores morosos, para planear las necesidades de personal y para analizar el reemplazo de equipo.
Genética: Se emplean cadenas de Márkov en teoría de genética de poblaciones, para describir el cambio de frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética. Ha sido empleada en la construcción del modelo de difusión de Motō Kimura.
Música: Diversos algoritmos de composición musical usan cadenas de Márkov, por ejemplo el software Csound o Max. Uno de los compositores que usó esta técnica en sus composiciones fue Iannis Xenakis con su obra Analoguique A et B (1958–59).
Operaciones: Se emplean cadenas de Márkov en inventarios, mantenimiento y flujo de proceso.
Redes neuronales: Se utilizan en las máquinas de Boltzmann.
Ejemplo:
 Consideremos el vector estacionario para el ejemplo de los camiones. Se puede demostrar que en este caso hay un comportamiento a largo plazo bien definido y por lo tanto el comportamiento a largo plazo está dado por el vector estacionario. Calculemos este comportamiento a largo plazo. En este ejemplo la matriz de transición está dada por:
 Calculemos primero el espacio propio de PP asociado al valor propio λ=1λ=1. Por definición E1=Nul(P−I)E1=Nul(P−I). Reduciendo la matriz P−IP−I obtenemos:
 Así que E1E1 contiene los vectores de la forma donde z es una variable libre:
  Por lo tanto, E1=gen Por definición un vector estacionario xx es un vector en E1E1 que además xx es un vector de probabilidad y por lo tanto x=
 Con z+z+z=1z+z+z=1, de donde z=13z=13. Luego, 
 Es decir, la probabilidad de que, a largo plazo, un camión cualquiera de la empresa seencuentre en una determinada ciudad es 1313.
CADENAS DE MARKOV ABSORBENTES
Un estado i de una cadena de Markov se dice absorbente si es imposible abandonarlo (e.d. pii = 1). Es, por tanto, un tipo particular de estado recurrente. Una cadenade Markov se dice absorbente si posee al menos un estado absorbente y desde cada estado es posible llegar al estado absorbente (no necesariamente en un paso). Comentario. Se puede ver que, en una cadena absorbente, todos los estados que no son absorbentes son transitorios. Ejemplo. Supongamos el caso de la ruina del jugador. Este juega a un juego que tiene ´ probabilidad 1/2 de ganar un dólar y probabilidad 1/2 de perderlo. Parara cuando se quede sin dinero o cuando alcance 4 dólares. La matriz de transición es:
Desde cualquiera de los estados 1, 2 y 3 es posible alcanzar en un numero finito de pasos los estados absorbentes 0 y 4. Por tanto, la cadena es absorbente. Los estados 1, 2 y 3 son transitorios. 
 La pregunta más obvia que se puede hacer en este tipo de cadenas es: ¿cuál es la probabilidad de que el proceso alcance alguna vez un estado absorbente? Otras preguntas interesantes son: 
a) Dado un estado absorbente, ¿cuál es la probabilidad de que el proceso finalice precisamente en dicho estado? 
b) ¿En promedio, cuánto le costara al proceso ser absorbido?
c) c) En promedio, ¿cuántas veces pasará el proceso por cada estado transitorio?
 Las respuestas a estas preguntas dependerán en general no sólo de las probabilidades de transición, sino también del estado en el que se encuentre el proceso al empezar. En realidad, ya podemos contestar a la primera de las preguntas.
Teorema 1: En una cadena de Markov absorbente, la probabilidad de estar en un estado transitorio después de n pasos tiende a cero cuando n → ∞. De aquí se sigue que en una cadena de Markov absorbente con un número finito de estados, la probabilidad de que el proceso sea absorbido es 1.
Forma canoníca y matriz fundamental. Número medio de pasos por un estado:
 Consideremos cualquier cadena de Markov arbitraria. Reenumeramos los estados para poner los transitorios primero. Si hay r estados absorbentes y t transitorios la matriz de probabilidades de transición tendrá la siguiente forma canoníca:
 Aquí I es la matriz identidad de orden r, 0 es una matriz nula r × t, R es una matriz t × r y Q es una matriz t × t. Multiplicando por bloques tenemos que P n es de la forma:
 Donde Re está en función de R y Q (es irrelevante lo que sea). Cada entrada de Qn corresponde a la probabilidad de estar en un estado transitorio después de n pasos, y por tanto, por el teorema anterior, tiende a cero. Es decir, Qn −−−→ n→∞ 0. Teorema 2. Para una cadena de Markov absorbente, la matriz I−Q tiene una inversa: N, que se le llama matriz fundamental. La entrada ij de la matriz N: nij es el número de veces esperado que la cadena pasa por el estado j, dado que empiece en el estado i. Si i = j, el estado inicial se cuenta.
Teorema 2: Para una cadena de Markov absorbente, la matriz I−Q tiene una inversa: N, que se le llama matriz fundamental. La entrada ij de la matriz N: nij es el número de veces esperado que la cadena pasa por el estado j, dado que empiece en el estado i. Si i = j, el estado inicial se cuenta.
Ejemplo: Continuamos con el ejemplo anterior. La matriz de transición en forma canoníca es:
De aquí vemos que la matriz Q es:
 Notar que la matriz Q también puede ser obtenida sin pasar por la matriz en forma canoníca. Simplemente hay que eliminar de la matriz de transiciones las filas y columnas correspondientes a estados absorbentes.
Calculando su inversa (I − Q) −1 tenemos:
 De esta matriz podemos deducir, por ejemplo, que si empezamos en el estado 2, el número esperado de pasos en los estados 1 2 y 3 antes de ser absorbido son 1, 2 y 1.
Tiempo de absorción: Ahora contestemos a la siguiente pregunta referida al ejemplo anterior. Si empezamos en el estado 2, ¿Cuál es en media el tiempo en ser absorbido? parece logico que sea 1 + 2 + 1 = 4.
Teorema 3: Dada una cadena que empieza en el estado si, denotamos por ti el tiempo promedio del número de pasos antes de que la cadena sea absorbida (i.e., el tiempo medio de absorción de todas las posibles realizaciones de una cadena que empieza en sí). ti se obtiene sumando todos los elementos de la fila i-esima de la matriz fundamental del proceso.
Probabilidades de absorción:
 Teorema 4: Llamamos bij a la probabilidad de que dada una cadena absorbente que empieza en el estado transitorio si, una realización de dicha cadena sea absorbida por el estado absorbente sj .Sea B la matriz con entradas bij . Entonces B es una matriz t × r y.
 B = NR, donde N es la matriz fundamental y R es el bloque que nombramos en la forma canoníca.
 Ejemplo: Continuando el ejemplo anterior de la ruina del jugador.
Por lo tanto:
 Esto quiere decir que si empezamos desde el estado 1, hay probabilidad 3/4 de quedar absorbidos por 0 y 1/4 de terminar absorbidos por 1.
CADENAS DE MARKOV TIEMPO CONTINUO
Una cadena de Markov de tiempo continuo es un proceso estocástico que tiene la propiedad Markoviana de que la distribución condicional del estado futuro en el tiempo, dado el estado presente y todos los estados pasados depende solamente delestado presente y es independiente del pasado. 
 Al igual que el caso discreto, se conocen como las probabilidades de transición. Si, además, es independiente de, entonces la cadena de Markov de tiempo continuo se dice tener probabilidades de transición estacionarias u homogéneas. Todas las cadenas de Markov que consideramos serán asumidas a tener probabilidades de transición estacionaria.
 Suponga que una cadena de Markov de tiempo continuo entra en el estado en algún tiempo, digamos en el tiempo 0, y suponga que el proceso no deja el estado (eso es no ocurre ninguna transición) durante las próximas unidades de tiempo, ¿cuál es la probabilidad de que el proceso no deje el estado durante las siguientes unidades de tiempo? Para responder esto note que como el proceso está en el estado en el tiempo, se sigue, por la propiedad Markoviana, que la probabilidad de que permanezca en ese estado durante el intervalo es justo la probabilidad no condicional de que este permanezca en el estado para al menos unidades de tiempo. 
 Es decir, si denotamos como la cantidad de tiempo que el proceso permanece en el estado antes de hacer una transición a un estado diferente, entonces
para todo Por lo tanto, la variable aleatoria continua , posee la propiedad de pérdida de memoria, y por lo que se ha visto en cursos de probabilidades solamente la distribución exponencial posee esta propiedad. Por lo tanto, concluimos que, tiene distribución exponencial, con parámetro, el cual, por lo general, depende del estado .
 Además, la propiedad de Markov también implica que el próximo estado visitado, es independiente de. Así, cuando el proceso deja el estado, este entra al estado con probabilidad (por definición), donde:
 De hecho, lo anterior nos da una manera de construir una cadena de Markov de tiempo continuo. Ya que una cadena de Markov de tiempo continuo es un proceso estocástico que tiene las propiedades de que cada vez que entra en un estado.
· La cantidad de tiempo que permanece en ese estado antes de hacer una transición a un estado diferente se distribuye exponencial con parámetro, y
· Cuando el proceso deja el estado, este entrará al estado con alguna probabilidad, llamémosla,, donde.
El proceso es llamado una cadena de Markov de tiempo continuo, el cual se define formalmente como
Construcción de la cadena, conocidas las tasas: 
Denotamos:
	 
 La tasa a la que Xt abandona el estado i. Si λi = 0 significaría que nunca abandona dicho estado, luego asumimos que λi > 0 y se puede calcular la probabilidad de que la cadena vaya a j cuando deja i como: 
 Es decir, Xt permanece en i durante un tiempo distribuido según una exponencial de tasa λi y luego va al estado j con probabilidad r(i, j).
Ejemplo. Proceso de Yule: Este es el modelo más simple de crecimiento de una población (e.g. bacterias) donde no hay muertes y cada individuo se subdivide con tasa β, de modo que: 
 y el resto de valores q(i, j)=0. Si se empieza con un soloindividuo entonces el salto a n + 1 individuos se hace en el tiempo Tn = t1 + ··· + tn, donde tn se distribuye como una exponencial con parámetro βn. E(ti) = 1/βi , de modo que:
Cuando n → ∞. Se puede demostrar que Tn → ∞.
Cálculo de la probabilidad de transición:
Se trata de calcular la probabilidad de transición pt a partir de las tasas de salto q. Para ello se usa la ecuación de Chapman-Kolmogorov considerando k = i y calculando el siguiente límite: 
Donde 
Por definición de las tasas de salto
Para i ≠j, y operando se obtiene la siguiente relación:
Para simplificar esta expresión se define la matriz:
 A la matriz Q se le denomina, también, generador infinitesimal de la cadena.
 La suma de las filas de Q es 0, ya que λi =∑j ≠iq (i, j). . Los elementos fuera de la diagonal son no negativos y los de la diagonal son no positivos. 
La ecuación (1) se puede escribir como: 	
Esto es una ecuación diferencial matricial cuya solución es: 
Se puede obtener también que: 
 
 Es decir: ptQ = Qpt, lo cual no resulta siempre cierto al multiplicar matrices, y la razón de este hecho se encuentra en que pt = se construye a partir de potencias de la matriz Q :
Probabilidades límite:
 Al igual que en el caso discreto interesa estudiar el comportamiento a largo plazo de la cadena. La teoría es equivalente a los procesos discretos: se supone que la cadena es irreducible, así, todos los estados comunican, es decir para todo i, j se tiene que existen i1, i2,...ij tal que q(i, i1), q(i1, i2),...,q(ij , j) son todos estrictamente positivos. Así, se obtiene que si una cadena de Markov Xt es irreducible y tiene distribución estacionaria π1, entonces:
 En las cadenas de Markov en tiempo discreto, la distribución estacionaria es solución de la ecuación πpt = π. Como en tiempo continuo no existe un primer t > 0, se necesita 7 una condición más fuerte: se dice que π es una distribución estacionaria si πpt = π para todo t > 0. 
Esta condición es complicada de comprobar porque implica conocer todas las pt que no son, a menudo fáciles de calcular. Por ello, se hace en términos de la matriz Q, esto es: 
 Donde λi = ∑j≠i q (i, j) es la tasa total de transiciones a partir de i. Se tiene que π es una distribución estacionaria si sólo si πQ = 0. Esto se puede ver de manera intuitiva, sustituyendo en la condición anterior el valor de Q, de modo que la condición πQ = 0 queda como: 
 Otra manera de verlo es que la probabilidad límite no debe cambiar con el tiempo así como: entonces es decir, la derivada es igual a 0 y pt es constante, y en este caso, π es un autovector de Q con autovalor 0.
Proposición: 
Si se verifica que: para todo j, k, entonces π es una distribución estacionaria. Se demuestra sumando sobre todo k ≠ j y reordenando el resultado.
Procesos de nacimiento y muerte:
 En este caso, el espacio de estados es S = {0, 1, 2,...,N} y los cambios en los estados siempre son desde n hasta n + 1, ó desde n hasta n − 1. 
 De manera intuitiva se puede considerar el estado del sistema como el tamaño de la población que se puede incrementar en 1 por un nacimiento, o decrecer en 1 por una muerte.
 Para describir la cadena, asumimos que las tasas de nacimiento son λn, n = 0, 1, 2,..., N − 1 y las tasas de muerte son µn, n = 1, 2, 3,...,N Si la población es n, entonces los nuevos individuos aparecen con tasa λn y los individuos dejan la población con tasa µn (de modo que si la población es 0 entonces no puede haber muertes, de modo que µ0 = 0). Así:
Aplicamos la condición:
Entonces: 
Si se vuelve a usar esta ecuación de la misma manera, se tiene que:
Esto es:
Iterando de la misma manera, se obtiene que:
 Se puede observar que si el espacio de estados es S = {0, 1, 2,...,N}, entonces µ0 = 0 y λn = 0, de modo que esos términos no pueden aparecer en la fórmula anterior.
Ejemplo. Supongamos una peluquería que corta el pelo a un ritmo o tasa de 3 personas por hora, esto es, cada corte de pelo requiere una cantidad de tiempo que se distribuye como una exponencial de media 20 minutos. Supongamos que los clientes llegan según un proceso de Poisson de tasa 2, pero que se marchan si las dos sillas de la salita de espera están ocupadas. 
 Se trata de calcular la fracción de tiempo que las dos sillas están ocupadas. También, interesa averiguar cuántos clientes son atendidos por hora, a largo plazo. Se define el estado como el número de clientes en el sistema, de modo que S = {0, 1, 2, 3}. A partir del enunciado se deduce que:
Aplicamos la condición (2) y se obtiene:
Fijamos, por ejemplo, π(0) = c y resolviendo el sistema anterior, se obtiene
La suma de todas ellas debe ser igual a 1, luego
Luego
Esto significa que un 8 /65 del tiempo del tiempo ambas cadenas están llenas de modo que se pierde esa fracción de clientes, y así un 57/65, es decir un 87.7 % de los clientes es atendido. Como la tasa de llegada original es de 2 personas entonces se corta el pelo a una media de 2 · 57/65 = 114/65 = 1,754 personas por hora.
Bibliográfica
· Diseño e implementación de un sistema electrocardiográfico digital, USA. Astro Data, 1996.
· El electrocardiograma, Dr. Luis Azcona, España 2000.
· ELECTROCARDIOGRAMA, Robledo Carmona, Juan Manuel, Jiménez Navarro, Manuel,
Málaga España.
· El libro de Reif, Fundamentals of Statistical And Thermal Physics. El capítulo 1 es una introducción a los métodos estocásticos, centrada en las caminatas al azar. No trata propiamente de cadenas de Markov. Se recomienda leer de principio a fin la sección 1.5.
· 
1