• Author / Uploaded
• OskarSanchez

• Categories
• Cadena Markov
• Probabilidad
• Variable aleatoria
• Física y matemáticas
• Matemáticas

Citation preview

REPÚBLICA BOLIVARIANA DE VENEZUELA UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA ANTONIO JOSÉ DE SUCRE DIP – MAESTRÍA EN INGENIERÍA ELECTRÓNICA (OPCIÓN TELECOMUNICACIONES) Facilitadora: MSc. Marienny Arrieche Participantes: Ing. Héctor Martínez S. Ing. Oskar Sánchez G. Fecha: Noviembre, 2012

En el contexto científico - tecnológico actual, el cual se caracteriza por los aleatoriedad y dinamismo, se requiere de la utilización de modelos que permiten estudiar los procesos aleatorios en el tiempo, cuya base se sustenta en los procesos estocásticos. Los procesos estocásticos, se constituyen por familias de variables aleatorias definidas en el tiempo sobre un espacio de probabilidad.

X t :   , t  T    X t    X  , t  En este orden de ideas, las cadenas de Markov, constituyen un tipo especial de estos procesos, cuya propiedad fundamental indica que al conocer el estado de un proceso en un momento dado, su comportamiento futuro no depende del pasado. Es decir que al conocer el presente, el futuro es un estado independiente del pasado. Es de notar, que los procesos estocásticos se fundamentan en los valores que puede tomar una variable aleatoria (estado) por lo que se puede tener un espacio d estados discretos y un espacio de estados continuo. Por otro lado, la variable de tiempo puede ser de tipo discreto o de tipo continuo. Para ejemplificar, se pueden considerar los cambios de estado que ocurran en forma semanal, mensual, etc… lo cual se corresponde a un tiempo

discreto; mientras que para tiempo continuo, se pueden tomar en cuenta los cambios de ese estado en cualquier instante. En la Figura 1, se muestra la clasificación de los Procesos Estocásticos, referenciado al tipo de variables y al tiempo.

Figura 1: Clasificación de los Procesos Estocásticos

Es de notar, que dependiendo del tipo de proceso estocástico, se puede establecer un una forma de proceder en función a las cadenas de Markov, motivado a que las variables aleatorias inmersas dentro de estos procesos incluyen un formato de probabilidad condicionada, probabilidad de transición o cambio de estado. Un ejemplo, para una cadena de Markov, podría ser, considerar la revisión de un equipo transmisor al inicio de cada día, con la finalidad de verificar si está operativo o dañado. Esta revisión, permite generar un diagrama de estados, cuya relación entre ellos, sea el cambio de un estado a otro.

Figura 2: Matriz de Transición

Es de notar, que en un día cualquiera el transmisor puede estar dañado y al comenzar el siguiente día, solo puede ocurrir una de dos cosas: que continúe dañado o que haya sido reparado en ese día. Por otro lado, si el equipo del ejemplo, se encuentra

funcionando correctamente, al comenzar el siguiente día solo pueden ocurrir dos cosas: que se dañe o que continúe su correcto funcionamiento. En referencia al ejemplo anterior, es de interés cuestionarse sobre la probabilidad de operatividad existente en un día “n”. Este cuestionamiento, tiene como consecuencia una probabilidad de ocupación de estado, que se puede representar como

o también

, de forma análoga la probabilidad de que el transmisor esté dañado en la primera oportunidad de observación se representa como

; teniendo en cuenta que “0”

representa el estado: dañado y “1” representa el estado: operativo. Entonces, se puede determinar por cadenas de Markov:

Que se pueden, insertar en una matriz de estados:

En general, la cadenas de Markov con k estados posibles s1,

s2, s3,…, sky

probabilidades estacionarias. Para i= 1, 2, 3,…k y j= 1, 2, 3,…k, se denota como “p ij” a la probabilidad condicionada de que el proceso esté en el estado “sj” en un determinado momento, si estuvo en el estado “si” en el momento inmediatamente anterior. Entonces, la matriz de transición de la cadena de Markov se define como una matriz cuadrada de orden k x k de la siguiente forma:

En la cual el elemento en la fila i, columna j, Representa la probabilidad de transición de un paso. La representación de estados en forma matricial, tiene entre sus ventajas que facilitar el cómputo de las probabilidades de transición en más de una paso. Tal que P x P = P2, que se corresponde a las probabilidades de transición en dos pasos, y Pm es la matriz de transición en m pasos de la cadena de Markov

Cadenas de Markov en tiempo discreto

La definición de las cadenas de Markov para tiempos discretos requiere tomar en cuenta a una variable aleatoria en tiempo discreto { probabilidad viene dada por

} de tal manera que su

, que análogamente se puede representar como

), de allí que la probabilidad condicional para esa variable viene dada por

.

Entonces, se define una cadena de Markov como un proceso estocástico a tiempo discreto {

} con espacio discreto para cualquier entero

estado

y para cualquier

, que cumpla la condición

.

Cabe destacar, que la definición matemática anterior, tomar en cuenta a la variable discreta “n” como un elemento temporal, de tal manera que “n+1” representa un tiempo futuro, “n” un tiempo presente y los tiempos “0,1,…n-1” como tiempos pasados. Entonces, se puede evidenciar que la distribución de probabilidad del estado de proceso a tiempo futuro, depende exclusivamente del estado del proceso en el tiempo presente. “Utilizando la regla de multiplicación para probabilidades condicionales, se deduce que las probabilidades de una cadena de Markov debe satisfacer la relación…” ,

(Degroot, M; 1988, p. 70)

Cadenas de Markov de Tiempo Continuo

Existen ciertos casos (como en algunos modelos de líneas de espera) en los que se requiere un parámetro, generalmente denotado como “ t”, de tiempo continuo, debido a que la evolución de un proceso se está observando de manera continua a través del tiempo. Un proceso estocástico de tiempo continuo {

} es una cadena de Markov

de tiempo continuo que cumple con la propiedad markoviana. En este sentido, las cadenas de Markov deben cumplir con las siguientes propiedades. a)

Un número finito de estados.

b)

Probabilidades de transición estacionaria.

Variables Aleatorias Importantes:

Cada vez que el proceso entra en el estado , la cantidad de tiempo que pasa en ese estado antes de cambiar a un estado diferente, es una variable aleatoria

donde

. La distribución exponencial posee la propiedad de que la distribución de probabilidad de tiempo que falta para que el proceso haga una transición fuera de un estado siempre es la misma, independientemente de cuánto tiempo haya pasado el proceso en ese estado. Tiene solo un parámetro, llámese

, donde la media es

⁄

y la función de

distribución acumulada es: {

}

Para

Este resultado lleva a una forma equivalente de definir una cadena de Markov de tiempo continuo. tiene una distribución exponencial con media ⁄ .

a)

La variable aleatoria

b)

Cuando sale un estado

probabilidades

, como

, en donde satisface las condiciones. Para toda y ∑

c)

, el proceso cambia a otro estado

Para toda

El siguiente estado visita después el estado es independiente del tiempo que

paso en el estado . Las intensidades de transición son

para

Para Donde

es la función de probabilidad de transición de tiempo continuo.

Es importante destacar que al considerar un proceso de Markov en que el sistema posee “n” estadosposibles, dados por los números 1, 2, 3,..., n. Se denota al producto ij p a la probabilidad de queel sistema pase al estado j después de cualquier ensayo en donde su estado era i antesdel ensayo. Los números ij p se denominan probabilidades de transición y la matriz nxnP = (pij) se conoce como matriz de transicióndel sistema

Una cadena de Markov es un tipo especial de proceso estocástico, que sepuede describir como sigue: En cualquier instante de tiempo n dado, cuando el estadoactual todos los estados previos estados futuros

,...,

del proceso son conocidos, las probabilidadesde los

dependen solamente del estado actual

estados anteriores

,y

y no dependen de los

.Formalmente, una cadena deMarkov es un proceso

estocástico tal que para

y para cualquier sucesiónposible de estados

(op.cit; p. 70)

Estados Absorbentes

El estado K se llama estado absorbente si la probabilidad de transición (de un paso) , de manera que cada vez que la cadena llegue al estado

permanece ahí para

siempre. Si

es u estado absorbente y el proceso comienza en el estado , la probabilidad de

llegar en algún momento a

se llama probabilidad de absorción al estado

dado que el

sistema comenzó en . Si el estado

es absorbente, entonces el conjunto de probabilidades de absorción

satisface el sistema de ecuaciones. ∑

Para

Sujeta a las condiciones: . . Si el estado es recurrente e A partir de esto se deduce que una cadena de Markov se puede considerar como absorbente si tiene por lo menos un estado absorbente; así como también si es posible ir de cada estado no absorbente hasta por lo menos un estado absorbente, para lo que no es necesario efectuar esta transición en un solo paso, ni tener la probabilidad de alcanzar cada estado absorbente a partir de uno no absorbente. Cabe destacar, que a partir de este análisis se puede encontrar el número esperado de pasos antes de que el proceso sea absorbido, el número esperado de veces que el proceso está en cualquier estado no absorbente, y la probabilidad de absorción por cualquier estado.

Una vez, que una cadena llega a un estado absorbente, permanece allí para siempre, entonces si una cadena posee dos estados absorbentes, es claro que el proceso de elimina en uno de ellos.

Las Propiedades de Markov y Matrices de Transición

Los procesos estocásticos tienen ciertas restricciones como: 

Que el proceso sea de tiempo discreto.



Que tenga un espacio de estado numerable o finito.



Que el proceso satisfaga la propiedad de Markov.

Si los procesos estocásticos satisfacen las tres restricciones anteriormente mencionadas se les llama cadenas de Markov. Ecuaciones de Chapman – Kolmogorov

Al considerar la probabilidad condicional para dos estados sucesivos de una variable aleatoria, en n pasos, se utiliza un desarrollo matemático denominado ecuaciones de Chapman - Kolmogorov, las cuales permiten calcular probabilidades de transición en “n” pasos. ∑

, para toda i, j, y n con

En sentido general, estas ecuaciones permiten ir del estado “i” al estado “j” en “n” pasos, en los que el proceso se ubica en un estado “k” después de exactamente m (m < n) pasos. Los elementos

, representan la probabilidad condicional referida a los

estados i y j, la cual da origen a una ley con el mismo nombre, que establece que la probabilidad de que dos hechos sucedan conjuntamente debido al azar y que cumplan ciertas condiciones, es mínima.

La paradoja de Borel – Kolmogorov La paradoja de Borel – Kolmogorov, es una ambigüedad presente en el cálculo de una función de densidad de probabilidad condicional de una variable aleatoria dada otra, puede ser definida condicionalmente en un suceso cuya probabilidad es cero.

Clasificación de los Estados en Cadenas de Markov

Los estados en cadenas de Markov, se clasifican en: -

Accesibles.

-

Absorbentes.

-

Periódicos.

-

Recurrente.

-

Transciente.

-

Recurrente positivo

-

Recurrente nulo.

En referencia a los estados accesibles, se debe tener en cuenta la existencia de una probabilidad de nula que comenzando en un estado i se puede llegar a un estado j al cabo de un cierto numero de etapas, afirmando que el estado j es accesible desde i. Cabe destacar, que para llegar de un estado a otro un proceso puede pasar por diversos pasos, para lo cual no importa el valor exacto de la probabilidad para n pasos cualesquiera; no obstante debe verificarse esa condición de accesibilidad. Entonces se tiene que dos estados son accesibles (viceversa) si se dice que se comunican y que pertenecen a una misma clase de estados. Una cadena de Markov en la que todos sus estados son accesibles entre si, es irreductible, es decir que existe una única clase de estados. Otra clasificación de las cadenas de Markov obedece a los estados absorbentes, los cuales no se comunican entre si, es decir que no son accesibles. Los estados absorbentes pertenecen a una distinta clase de estados, entonces cuando se está en ellos la probabilidad de continuar en ese estado es 1. Es importante destacar, que los estados absorbentes definen una clase de estados por si mismos.

Por otro lado, se debe considerar que los estados se definen por un carácter periódico, el cual se define por la relación

0, la cual existe

solo para valores de n que se corresponden al conjunto (d, 2d, 3d,…). Si d = 1 decimos que el estado es aperiódico. También se puede considerar un estado periódico, si partiendo de ese estado, solo se puede volver a él en un numero de etapas que sea múltiplo de un cierto numero entero mayor que uno. Un estado es recurrente, en la medida que comenzando en él se tenga la certeza de volver en algún momento del tiempo (una determinada cantidad de etapas) sobre si mismo; y es transciente si no hay certeza de regresar a si mismo, generalmente debido a la existencia de una probabilidad no nula de acceder a un estado absorbente. Finalmente, en una cadena de Markov con una cantidad finita de estados, estos pueden ser recurrente positivo; mientras que si la cantidad de estados es infinita entonces son recurrente nulo.

Cadenas de Markov con parámetros continuos:

Las cadenas de Markov pueden operarse en tiempos continuos en los cuales las variables toman valores enteros. {

} , de tal manera que inicia en un estado

tiempo cero. El proceso permanece en ese estado un tiempo aleatorio salta a un nuevo estado

distinto del anterior, con un tiempo aleatorio

al

y seguidamente y así en forma

sucesiva. Entonces, los tiempos aleatorios T son los tiempos en los que el proceso está constante en alguno de sus estados y se denominan tiempos de estancia, mientras que los momentos en donde el proceso tiene saltos son los tiempos

para

. De allí que el proceso se puede representar como:

El proceso anteriormente descrito, representa un proceso de saltos, el cual necesariamente no tiene que estar definido para tiempos continuos. En un proceso de Markov a tiempo continuo, las probabilidades de saltos

y las probabilidades de

transición representas características diferentes del proceso. Las probabilidades de saltos

son probabilidades de cambio de un estado a otro cuando tiene un salto, mientras que las probabilidades de transición son las probabilidades de encontrar al proceso en un estado j partiendo de i, al término de un intervalo de tiempo de longitud t. Además, un proceso de Markov a tiempo queda completamente especificado por una distribución de probabilidad inicial en el espacio de estados, el conjunto de los parámetros no negativos de

y las probabilidades de saltos entre los estados i y j.

Aplicaciones de las Cadenas de Markov:

Las cadenas de Markov tienen aplicaciones en diversas ramas de la ciencia, como en la electrónica, donde se emplean técnicas que pueden contribuir con la detección de blancos aéreos mediante un RADAR como por ejemplo, todo esto usando métodos estocásticos de Markov. También posee aplicación en el reconocimiento de gestos faciales mediante visión artificial. Por otra parte, en la física las técnicas markovianas son usadas en muchos problemas de la termodinámica y la física estadística. En la meteorología de considerarse el clima de una región especifica a lo largo de diferentes días, puede determinarse que el estado actual es intrínseco del último estado y no de toda la cadena o historia en sí, de modo que se pueden usar cadenas de Markov para formular modelos climatológicos básicos. En la simulación las cadenas de Markov son utilizadas para proveer una solución analítica a ciertos problemas de electrónica y a otras ramas de la ingeniería más puntuales como el estudio de la investigación de operaciones. En internet la utilización la utilización de google en sus motores de búsqueda, es definido por medio 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. En los procesos epidemiológicos es importante destacar la aplicación de las cadenas de Markov con especial énfasis 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.

En los juegos de azar con muchos los problemas que se pueden modelar mediante una cadena de Markov. El modelo de la ruina del jugador, que establece la probabilidad de que una persona que apuesta en un juego de azar finalmente termine sin dinero por ejemplo. En la economía y finanzas los procesos markovianas se utilizan para modelos simples de valuación de opciones que permitan determinar cuando existe oportunidad de arbitraje, así como en el modelo de colapsos de la bolsa de valores o para determinar la volatidad de los precios. En los negocios, las cadenas de Markov 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 quipo. En la música se utilizan diferentes algoritmos de composición musical que usan cadenas de Markov, por ejemplo el software Csound o Max.

Ejemplo de Aplicaciones:

1. Detección de blancos aéreos por parte de un RADAR primario de vigilancia:  Objetivo: Detectar de forma positiva un blanco aéreo sin la colaboración de este. Se utiliza el método HRR (High Resolution Radar). Se basa en el estudio de las características del eco recibido. Tal y como lo muestra la figura.

Figura 4: Detección de blancos aéreos.

Figura 5: Forma de onda recibida. Se produce una reflexión radar diferente de en función de la forma del blanco. Todo esto depende de los centros de scatter:

Figura 6: Reflexión del Blanco  las señales a clasificar son muy parecidas entre sí.  Dependen del ángulo de observación.  Las regiones de decisión están muy solapadas.  La correlación equivoca a menudo la clasificación.

Figura 7: Posibles Blancos

Figura 8: Modelado en MATLAB

Figura 8: Proceso Markov  Resultados: Se utilizan secuencias de entrenamiento para cada modelo y existe una base de datos de observaciones con 800 arreglos de 10 elementos.

PORCENTAJE DE ERROR MODELOS DE MARKOV CORRELACIÓN Modelo 2

0%

40%

Modelo 3

0%

50%

Modelo 4

0%

40%

Modelo 5

0%

40%

Modelo 6

0%

40%

Modelo 7

0%

40%

Modelo 8

0%

30%

Modelo 9

0%

40%

2. Reconocimiento de Gestos:  Se han colocado unas pegatinas en la cara del usuario y se estudia su evolucion en la realizacion de gestos mediante cadenas de Markov.  Las pegatinas se segmentan mediante un algoritmo de detección de color con funciones gaussianas a priori.  Se han creado HMMs: Dos modelan la apertura de la boca y el último del estiramiento de la boca.

Figura 9: Proceso Markov

Figura 10: Matriz de Transición  Como observacion para obtener el grado de apertura del ojo se usa la coleanidad presentada por su contorno.  Como observación para estimar la apertura de la boca se utiliza la diferencia entre los centros de gravedad de las pegatinas superior e inferior de la boca.  Para el estiramiento se utiliza la diferencia de componentes x de las pegatinas izquierda y derecha.

Definición de estados:  Para los ojos: Cerrado, semicerrado y abierto.  Para la apertura de la boca: Abierta, semiabierta y cerrada.  Para el estiramiento de la boca: Estirada, semiestirada y encogida.  Se capturan abservaciones de cada tipo (boca y ojos) y se efectúa el entrenamiento de los 4 HMM.  El entrenamiento ajusta los valores de [A], [B] y [π].

Figura 11: Estados Posteriores

Figura 11: Estados de Posteriores

Referencias Bibliográficas:

Fonollosa, J y otros (2002). Métodos Cuantitativos de Organización Industrial II. UPC. España. [En línea] Disponible en: http://books.google.co.ve/ Rincón, L. (2012). Introducción a los procesos estocásticos. UNAM. México. Castro, A y Otros (2008). Manual de Investigación de Operaciones II. Instituto Tecnológico

de

Cerro

Azul,

México.

[En

línea],

Disponible

en:

http://es.scribd.com/doc/61178886/23/ESTADOS-ABSORBENTES Torres, H (2012). Cadenas de Markov con estados absorbentes. Blog Digital [En línea],

Disponible

en:

http://invop2.blogspot.com/2011/06/cadenas-de-markov-con-

estados.html S/A (2012). Cadenas de Markov – estados absorbentes y de tiempo continuo. Instituto

Tecnológico

de

Reynosa

[En

línea],

Disponible

en:

http://www.slideshare.net/albertojeca/cadenas-de-markov-estados-absorbentes-y-detiempo-continuo#btnNext Pacheco, J. (2003). Solución de un proceso markoviano por programación dinámica. [En línea], Disponible en: http://es.scribd.com/doc/52215031/8/ECUACIONES-DECHAPMAN-KOLMOGOROV Bergasa P. Luis M. Introducción a los modelos ocultos de Markov. [En línea], disponible

en,

http://www.bioingenieria.edu.ar/academica/catedras/metestad/Introduccion%20al%20Mode lo%20oculto%20de%20Markov.pdf