CADENAS DE MARKOV

ANDRÉI MARKOV

(Riazán, 1856 - San Petersburgo, 1922)

Matemático y lingüista nacido en Ryazan, Rusia. Estudió y se doctoró en la Universidad de San Petersburgo, donde comenzó su labor docente en 1886. Es a comienzos del siglo XX cuando da continuidad a los estudios de su maestro Pafnuty Chebyshev sobre los cálculos matemáticos de la lógica de la probalidad. So obra tuvo continuidad en su hijo, de igual nombre que él, Andrei Markov (1903-1979). Falleció en San Petersburgo en 1922.
Estudió, entre otros muchos aspectos, las construcciones lingüísticas a partir del cálculo matemático (1913). Así, por ejemplo, analizó la novela de Puschkin Eugenio Oniegui, y dedujo que las letras del alfabeto cirílico, como las de cualquier otro alfabeto, iban apareciendo relacionadas con las que las precedían en la escritura. La nueva letra está determinada por la anterior, pero es independiente de la manera en la que aparece respecto de las anteriores... Existe, pues, una continuidad predecible, en la medida que una serie de caracteres permite anticipar la probabilidad de otra sucesión de caracteres. Marvok aplicó los cálculos probabilistas a diversas esferas del conocimiento y de la ciencia. A las relaciones matemáticas probabilistas de las construcciones seriadas -un texto, por ejemplo- se las ha denominado los 'procesos de Markov' o 'cadenas de Markov', que Norbert Wiener estudió en profundidad para sus elaboraciones teóricas. Sus postulados están considerados como los antecedentes de la teoría matemática de la información.
Entre otros campos de la investigación, el modelo de Markov está siendo aplicado al análisis tendencial o prospectivo del desarrollo tecnológico, como instrumento de cálculo de que un hecho ocurra. Para ello se utilizan dos factores probabilísticos: la secuencia de los hechos y el tiempo transcurrido entre acontecimientos sucesivos, esto es, la transición de estados y tiempo de permanencia en el estado.

CADENAS DE MARKOV

Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. “Recuerdan” el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.

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 equipo.

El análisis de Markov, llamado así en honor de un matemático ruso que desarrollo el método en 1907, permite encontrar la probabilidad de que un sistema se encuentre en un estado en particular en un momento dado. Algo más importante aún, es que permite encontrar el promedio a la larga o las probabilidades de estado estable para cada estado. Con esta información se puede predecir el comportamiento del sistema a través del tiempo.

MATRIZ DE TRANSICIÓN

Esta es una matriz cuadrada, donde el número de renglones y de columnas será igual al de estados que tenga la cadena de Markov, siendo cada elemento de la matriz, la probabilidad de transición respectiva de pasar del estado que encabeza el renglón donde está ubicado el elemento hacia el estado encabezado por la columna.

Veamos un ejemplo:

El comportamiento de cambio de marca de los consumidores ha sido modelado como una cadena de Markov, para ayudar a desarrollar las estrategias de mercadotecnia.

A manera de ejemplo, observemos el comportamiento de cambio de marca descrito en la tabla 1 para una muestra de 250 consumidores de un producto.

Tabla 1. Número de consumidores que cambian la marca i en la semana 6 por la marca j en la semana 7

El primer renglón indica que, de 80 personas que compraron la marca 1 en la semana 6, 72 volvieron a adquirirla en la semana 7, 4 prefirieron la marca 2 y 4 la marca 3. Sin embargo, nótese que 12 personas cambiaron la marca 2 por la marca 1 y 2 personas cambiaron la marca 3 por la marca 1. Así pues, para la marca 1, la pérdida de 8 clientes se compensó con creces por la conquista de 14 clientes. Entre la sexta y la séptima semanas, la marca 1 aumentó su participación en el mercado de 32% (80/250) a 34,4 % (86/250).

La matriz de probabilidades de transición para la tabla de contingencia es P:

CALCULO DE PROBABILIDADES DE LA MATRIZ DE TRANSICIÓN

Dados {a_0j} y P de una cadena de Markov, nos interesa conocer la probabilidad de que ocurra E_j en la transición n. Estas se conocen como las probabilidades absolutas del sistema después de un número Específico n de transiciones. Llamemos {a_nj} estas probabilidades absolutas después de n transiciones. La expresión general de {a_nj} en términos de {a_0j} y P se puede calcular de la siguiente manera:

También

Donde p(2)_kj = Σp_ki*p_ij es la probabilidad de transición de dos pasos o de segundo orden, es decir, la probabilidad de ir del estado k al estado j en exactamente dos transiciones.

Por inducción se puede ver que:

Donde p_ij es la probabilidad de transición de n pasos u orden n dada por la formula recursiva:

En general para todo i y j,

Los elementos de una matriz de transición más alta p(n)_ij se obtienen de forma directa por multiplicación matricial. Así:

Y en general

Por tanto, si las probabilidades absolutas se definen en forma vectorial

Como

Entonces:

MATRIZ DE TRANSICION EN ESTADO ESTABLE

Un estado es estable cuando ya no hay cambios en el sistema, es decir que se alcanza el equilibrio. Una manera posible de obtener las condiciones del sistema para el estado estable es repetir iterativamente los cálculos para cada periodo con el fin de hallar el periodo con aquellas probabilidades que se mantienen constantes o no cambian.

Sin embargo también es posible utilizar los métodos para resolver sistemas de ecuaciones que nos permiten encontrar directamente estas probabilidades de estado estables.

EJEMPLO:

A partir de la siguiente matriz de transición, determinar las probabilidades en estado estable.

En primera medida lo que hacemos es hallar la traspuesta de la matriz de transición, es decir:

Por lo tanto el sistema de ecuaciones es el siguiente:

Esta ultima ecuación es agregada siguiendo la propiedad de que la sumatoria las probabilidades de los estados debe ser igual a 1.

Resolviendo el anterior sistema de ecuaciones tenemos las probabilidades en estado estable:

 

X=0.1875

Y=0.25

Z=0.2917

K=0.271

MATRIZ REGULAR

Una matriz estocástica es regular, cuando todos los elementos de una potencia son positivos.

Como ejemplo, tomaremos nuestra matriz estocástica de la diapositiva anterior la elevamos al cuadrado:

MATRIZ ERGÓDICA

Una cadena de Markov es ergodica si todos sus estados son no nulos, no periódicos y recurrentes.

Las cadenas de Markov ergodicas cumplen la siguiente propiedad:

El límite lım_n→0 p(n)_ij existe y es independiente del estado inicial i. Lo denominaremos π_j.

CLASIFICACION DE LOS ESTADOS DE LA CADENA DE MARKOV

Los estados de una cadena de Markov se clasifican dependiendo de la fracción de tiempo que la cadena pasa en cada uno de ellos.

Los estados de una cadena de Markov pueden ser:

• Transitorios: Un estado es transitorio si después de haber entrado a este estado, el proceso no regresara a él.
• Recurrentes: Se dice que un estado es recurrente si después de haber entrado a este estado el proceso definitivamente regresara a ese estado. Por consiguiente, un estado es recurrente si y solo si no es transitorio.
• Absorbentes: Un estado se llama absorbente si después de haber entrado ahí el proceso nunca saldrá de ese estado. Por consiguiente, el estado i es un estado absorbente si y solo si Pij=1.

MATRIZ FUNDAMENTAL

La matriz fundamental es muy útil para el análisis y solución de situaciones en las cuales aparecen estados absorbentes.

La metodología para obtener la matriz fundamental es la siguiente:

1. Obtener la matriz de transición en la forma usual, incluyendo los estados absorbentes.
2. Identificar de la matriz de transición los renglones correspondientes a la matriz absorbente
3. De lo que ha quedado de la matriz de transición en el paso anterior, dividirlo en dos partes: N que será la parte no absorbente y A que contendrá los estados absorbentes
4. Obtenemos la matriz U mediante la siguiente fórmula:

U=I-N

Donde I es la matriz identidad.

    5. Finalmente, se obtiene la matriz identidad de la siguiente manera:

X=U^-1

Donde X representa la inversa de U, la cual se obtiene por algunos métodos como el Gauss- Jordan.

EJEMPLO RESUELTO:

Cada familia norteamericana se puede clasificar como habitante de una zona urbana, rural ó suburbana, durante un año determinado el 15% de las familias urbanas se cambian a la zona suburbana y el 5 % a la zona rural. El 6% de las familias suburbanas pasan a la zona urbana y el 4% a la rural, el 4% de las familias rurales pasan a la zona urbana y el 6% a la suburbana.

A.      Construya la matriz de transición

Solución:

Debemos definir los estados

        Eo = Zona urbana

        E1 = Zona Rural

        E2 = Zona Suburbana

	Eo	E1	E2
Eo	0.8	0.05	0.15
E1	0.04	0.90	0.06
E2	0.06	0.04	0.90

B.       Si una familia vive actualmente en la zona urbana ¿Cual es la probabilidad que después de dos años viva en la zona urbana?

Solución:

Buscamos T²

	Eo	E1	E2
Eo	0.651	0.091	0.258
E1	0.0716	0.8144	0.114
E2	0.1036	0.075	0.8214

La probabilidad de que una familia viva en la zona urbana transcurrido 2 años es 0.651.   

C.       Suponga que en la actualidad  el 40% de las familias viven en la zona urbana, el 35% en la zona suburbana y el 25 en la zona rural. Después de dos años ¿Qué porcentaje de familias vivirá en la zona urbana?

Solución:

Debemos identificar el vector cuyos valores se toman de los porcentajes que nos da el problema; como se muestra a continuación:

0.4

0.25

0.35

Buscamos P*T²

Lo que nos da como resultado el siguiente vector fila:

0.31456

0.26625

0.41919

Con lo cual se concluye que aproximadamente el 31.45% vivirá en la zona urbana.




BIBLIOGRAFÍA:
http://www.infoamerica.org/teoria/markov1.htm