CADENAS DE MARKOV INTRODUCCION

CADENAS DE MARKOV 

Introducción

Un proceso o sucesión de eventos que se desarrolla en el tiempo en el cual el resultado  en cualquier etapa contiene algún elemento que depende del azar se denomina proceso  aleatorio o proceso estocástico. Por ejemplo, la sucesión podría ser las condiciones del tiempo en Paraná en una serie de días consecutivos: el tiempo cambia día a día de una manera que en apariencia es algo aleatoria. O bien, la sucesión podría consistir en los precios de las acciones que cotizan en la bolsa en donde otra vez interviene cierto grado de aleatoriedad. 

Un ejemplo simple de un proceso estocástico es una sucesión de ensayos de Bernoulli, por ejemplo, una sucesión de lanzamientos de una moneda. En este caso, el resultado en cualquier etapa es independiente de todos los resultados previos (esta  condición de independencia es parte de la definición de los ensayos de Bernoulli). Sin embargo, en la mayoría de los procesos estocásticos, cada resultado depende de lo  que sucedió en etapas anteriores del proceso. Por ejemplo, el tiempo en un día determinado no es aleatorio por completo sino que es afectado en cierto grado por el tiempo de días previos. El precio de una acción al cierre de cualquier día depende en cierta medida del comportamiento de la bolsa en días previos. 

El caso más simple de un proceso estocástico en que los resultados dependen de otros, ocurre cuando el resultado en cada etapa sólo depende del resultado de la etapa anterior y no de cualquiera de los resultados previos. Tal proceso se denomina proceso de Markov o cadena de Markov (una cadena de eventos, cada evento ligado al precedente). Estas cadenas reciben su nombre del matemático ruso Andrei Andreevitch Markov (1856-1922). Como mencionamos antes, estas cadenas tiene memoria, recuerdan el último evento y eso condiciona las posibilidades de los eventos futuros. Esto justamente las distingue de una serie de eventos independientes como el hecho de tirar una moneda. Este tipo de proceso presenta una forma de dependencia simple, pero muy útil en muchos modelos, entre las variables aleatorias que forman un proceso  estocástico. Se utilizan, por ejemplo, para analizar patrones de compra de deudores morosos, para planear necesidades de personal, para analizar el reemplazo de un equipo, entre otros. 

Definición

Una cadena de Markov es una sucesión de ensayos similares u observaciones en la cual cada ensayo tiene el mismo número finito de resultados posibles y  en donde la probabilidad de cada resultado para un ensayo dado depende sólo del resultado del ensayo inmediatamente precedente y no de cualquier resultado previo.


Propiedad de Markov:  Dada una secuencia de variables aleatorias ...... , , , X1 X2 X3,
tales que el valor de  Xn es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de  Xn+1 en estados pasados es una función de  Xn por sí sola, entonces:

Donde xi es el estado del proceso en el instante i.

Esta identidad es la denominada propiedad de Markov: El estado en t + 1 sólo depende del estado en t y no de la evolución anterior del sistema.



Matriz de transición

Al trabajar con cadenas de Markov, a menudo es útil pensar la sucesión  de ensayos como experimentos efectuados en cierto sistema físico, cada resultado dejando a este sistema en cierto estado. Por ejemplo, consideremos una sucesión de elecciones políticas en cierto país: el sistema podría tomarse como el país mismo y cada elección lo dejaría en cierto estado, es decir en el control del partido ganador. Si sólo hay dos partidos  políticos fuertes, llamados A y B, los que por lo regular controlan el gobierno, entonces podemos decir que el país se encuentra en el estado A o B si el partido A o B ganara la elección. Cada ensayo (o sea cada elección), coloca al país en uno de los dos estados A o B. Una sucesión de 10 elecciones podría producir resultados tales como los siguientes:

A, B, A, A, B, B, B, A, B, B 

La primera elección en la sucesión deja en el poder al partido A, la segunda fue ganada por el partido B, y así sucesivamente, hasta que la décima elección la gane el partido B. Supongamos que las probabilidades de que el partido A o B ganen la próxima elección son determinadas por completo por el partido que está en el poder ahora. Por ejemplo podríamos tener las probabilidades siguientes:

• Si el partido A está en el poder, existe una probabilidad de ¼  que el partido A ganará la próxima elección y una probabilidad de ¾  de que el partido B gane la elección siguiente.
• Si el partido B está en el poder, hay una probabilidad de 1/3 de que el partido A gane la elección siguiente y una probabilidad de 2/3 que el partido B permanezca en el poder.

En tal caso, la sucesión de elecciones forman una cadena de Markov, dado que las probabilidades de los dos resultados de cada elección están determinadas por el resultado de la elección precedente.
Lo descrito anteriormente puede representarse gráficamente usando la siguiente red:

Los círculos A y B se denominan nodos y representan los estados del proceso, las flechas que van de un 

nodo a si mismo o al otro son los arcos y representan la probabilidad de cambiar de un estado al otro.

La información probabilística que se acaba de dar se puede representar de manera 

conveniente por la siguiente matriz:

Esta matriz se denomina matriz de transición. Los elementos de la matriz de transición representan las probabilidades de que en el próximo ensayo el estado del sistema del partido indicado a la izquierda de la matriz cambie al estado del partido indicado arriba de la matriz.

Definición: Consideremos un proceso de Markov en que el sistema posee n estados posibles, dados por los números 1, 2, 3, …., n. Denotemos pij  a la probabilidad de que el sistema pase al estado j después de cualquier ensayo en donde su estado era i antes del ensayo. Los números ij p se denominan probabilidades de transición y la matriz nxnP =  (pij)   se conoce como matriz de transición del sistema.

Observaciones:

1) La suma 1 ..... pi1 + pi2 + ......+ pin = 1. Esta suma representa la probabilidad de que el sistema pase a uno de los estados 1, 2, …., n dado que empieza en el estado i. Ya que el sistema ha de estar en uno de estos n estados, la suma de probabilidades debe ser igual a 1. Esto significa que los elementos en cualquier renglón de  la matriz de transición deben sumar 1. 

2) Cada elemento  pij ≥ 0

CADENAS DE MARKOV

Definición: (proceso estocástico) Un proceso estocástico es una colección indexada de variables aleatorias: { X_t } donde tÎT (conjunto de enteros no negativos) y X_tÎZ (conjunto de características medibles en t. Z = {0, 1, 2, ..., M).

Definición: (cadena de Markov) Una cadena de Markov es un proceso estocástico que cumple la siguiente propiedad (llamada propiedad Markoviana)

P[X_t+1 = jú X₀ = k₀, X₁ = k₁, …, X_t-1 = k_t-1, X_t = i] = P[X_t+1 = jú X_t = i],

para todo t=0, 1,… y cualesquiera estados i, j, k_r Î Z; a la probabilidad P[X_t+1 = jú X_t = i] = p_ij la llamaremos probabilidad de transición del estado i al estado j.

Definición: Si se cumple que P[X_t+1 = jú X_t = i] = P[X₁ = jú X₀ = i] para todo i, j Î Z. y todo t = 0,1,… entonces se dice que las probabilidades de transición, de un paso, son estacionarias.

Se puede demostrar que lo anterior implica que

P[X_t+n = jú X_t = i] = P[X_n = jú X₀ = i], para todo t = 0,1,…

Esta probabilidad la denotamos p_ij⁽ⁿ⁾ = probabilidad de transición de n pasos, la cual cumple además que:

1) p_ij⁽ⁿ⁾ ³ 0,   2) 

las cuales se presentan en la Matriz de probabilidades de transición

ECUACIONES CHAPMAN-KOLMOGOROV:

La siguiente relación se cumple para las probabilidades de una cadena de Markov finita con probabilidades estacionarias:

Para m = 1 tenemosresulta que las probabilidades de transición de n pasos las podemos obtener a partir de las probabilidades de transición de un paso de manera recursiva. Por ejemplo para n = 2 tenemos: que corresponde a la expresión que calcula, por definición, el producto de matrices. Por lo tanto P⁽²⁾ = PxP = P². Por inducción obtenemos P⁽ⁿ⁾ = PxP^n-1 = Pⁿ.

PROBABILIDADES NO CONDICIONALES DE UN ESTADO

En una cadena de Markov, las probabilidades de transición son probabilidades condicionales. Si se desea la probabilidad no condicional P[X_n = j]. Especifiquemos P[X₀ = i] = a_i  para i = 0, 1, 2. … entonces:

P[X_n = j] = P[X₀ = 0].pⁿ_0J + P[X₀ = 1].pⁿ_1J + P[X₀ = 2].pⁿ_2J + … +

+ P[X₀ = M].pⁿ_MJ + …

CLASIFICACION DE ESTADOS:

Definiciones: 1) El estado j es accesible desde el estado i si existe n tal que p_ij⁽ⁿ⁾ > 0.

2) Si i es accesible desde j y j es accesible desde i se dice que i y j se comunican (i C j)

La relación C cumple las siguientes propiedades:

·      i C i

·      si i C j entonces j C i

·      si i C j y j C k entonces i C k.

Recordar que si A es un conjunto no vacío y R es una relación en A, se dice que R es una relación de equivalencia en A si R es reflexiva, simétrica y transitiva. Además toda relación de equivalencia induce una partición en el conjunto donde se define.

C es una relación de equivalencia en el conjunto de estados de una cadena de Markov, entonces ella define clases (o una partición) en dicho conjunto de estados.

3) Si existe solo una clase entonces se dice que la cadena de Markov es irreducible

4) ¿Un proceso que está en estado i regresará a él?

Sea f_ii la probabilidad de que un proceso regrese al estado i estando en dicho estado.

i se llama recurrente si f_ii = 1

i se llama transitorio si f_ii < 1

i se llama absorbente si p_ii = 1

PROPIEDADES DE f_ii

·      El número esperado de períodos que el proceso está en estado i es infinito si un estado es recurrente.

·      Si un estado es transitorio y la probabilidad de que regrese al estado i es f_ii entonces la probabilidad de que no regrese al estado i será 1 - f_ii y el número esperado de períodos en que el proceso está en estado i es 1/(1 - f_ii).

·      La recurrencia es una propiedad de clase es decir todos los estados de una clase son recurrentes (o transitorios).

·      No todos los estados pueden ser transitorios. Esto implica que en una cadena de Markov irreducible todos los estados son recurrentes.

Proposición: El estado i es recurrente si  y es transitorio si .

Corolario: Si el estado i es recurrente y se comunica con el estado j entonces j es recurrente.

PROPIEDADES A LARGO PLAZO:

Consideramos dos propiedades adicionales de las cadenas de Markov.

Definición: El estado i se dice que tiene período d si cuando quiera que n no es divisible por d y d es el mayor entero con esta propiedad. Un estado con período 1 se dice que es aperiódico. Se puede demostrar que la periodicidad es una propiedad de clase, es decir, si el estado i tiene período d y los estado i y j se comunican entonces j también tiene período d.

Ejemplo: Comenzando en estado i. Puede ser posible que el proceso entre en el estado i en los tiempos 2, 4, 6, 8, …, en este caso decimos que el estado i tiene período 2.

Definición: Si un estado i es recurrente, se dice que es recurrente positivo si, comenzando en i el tiempo esperado hasta que el proceso retorne al estado i es finito. Se puede demostrar que la recurrencia positiva es una propiedad de clase. Pueden existir estados recurrentes que no son recurrentes positivos.

Estados recurrentes positivos aperiódicos son llamados ergódicos.

Enunciado:

Para una cadena de Markov irreducible y ergódica el    existe y es independiente de i. Además p_J es solución única no negativa de:

, así como 

Los  se llaman probabilidades de estado estable de la cadena de Markov y se cumple que  donde   es el tiempo esperado de recurrencia.

TIEMPOS DE PRIMERA PASADA

Algunas veces es necesario referirse al número de transiciones que hace el proceso al ir del estado i al estado j por primera vez. A este lapso de tiempo se le llama tiempo de primera pasada. Si i = j se llama tiempo de recurrencia del estado i.

Los tiempos de primera pasada son variables aleatorias cuyas distribuciones de probabilidad dependen de las probabilidades de transición.

Si f_ij⁽ⁿ⁾ denota la probabilidad de que el tiempo de primera pasada del estado i al estado j es n, tenemos las siguientes fórmulas recursivas:

f_ij⁽¹⁾ = p_ij⁽¹⁾ = p_ij ;               f_ij⁽²⁾ =    f_ij⁽ⁿ⁾ = 

Para i y j fijos f_ij⁽ⁿ⁾ son números no negativos tales que .El tiempo esperado de primera pasada del estado al estado j, se define así:

Siempre que  m_ij satisface la ecuación  Lo que significa que la primera transición desde el estado i puede ser al estado j o algún otro estado k. Si es al estado j el tiempo de primera pasada es 1. Ahora si la primera transición es a un estado k, (k ¹ j) lo que ocurre con probabilidad p_ik, el tiempo esperado de primera pasada condicional del estado i al estado j es 1 + p_ikm_kJ, al sumar todas las posibilidades se obtiene la fórmula: