CADENAS DE MÁRKOV

ANDRÉI MÁRKOV

Andréi Andréyevich Márkov: (14 de junio de 1856 - 20 de julio de1922) fue un matemático ruso conocido por sus trabajos en la teoría de los números y la teoría de probabilidades.

Márkov nació en Riazán, Rusia. Antes de los 10 años su padre, un funcionario estatal, fue trasladado a San Petersburgo donde Andréi entró a estudiar en un instituto de la ciudad. Desde el principio mostró cierto talento para las matemáticas y cuando se graduó en 1874 ya conocía a varios matemáticos de la Universidad de San Petersburgo, donde ingresó tras su graduación. En la Universidad fue discípulo de Chebyshov y tras realizar sus tesis de maestría y doctorado, en1886 accedió como adjunto a la Academia de Ciencias de San Petersburgo a propuesta del propio Chebyshov. Diez años después Márkov había ganado el puesto de académico regular. Desde 1880, tras defender su tesis de maestría, Márkov impartió clases en la Universidad y, cuando el propio Chebyshov dejó la Universidad tres años después, fue Márkov quien le sustituyó en los cursos de teoría de la probabilidad. En 1905, tras 25 años de actividad académica, Márkov se retiró definitivamente de la Universidad, aunque siguió impartiendo algunos cursos sobre teoría de la probabilidad.

A parte de su perfil académico, Andréi Márkov fue un convencido activista político. Se opuso a los privilegios de la nobleza zarista y llegó a rechazar las condecoraciones del propio zar en protesta por algunas decisiones políticas relacionadas con la Academia de Ciencias. Hasta tal punto llegó su implicación en la política que llegó a ser conocido con el sobrenombre de "el académico militante".

Márkov arrastró durante toda su vida problemas relacionados con una malformación congénita en la rodilla que le llevaría varias veces al quirófano y que, con el tiempo, fue la causa de su muerte cuando el 20 de julio del año 1922 una de las muchas operaciones a las que se sometió le produjo una infección generalizada de la que no pudo recuperarse.

Aunque Márkov influyó sobre diversos campos de las matemáticas, por ejemplo en sus trabajos sobre fracciones continuas, la historia le recordará principalmente por sus resultados relacionados con la teoría de la probabilidad. En 1887 completó la prueba que permitía generalizar el teorema central del límite y que ya había avanzado Chebyshov. Pero su aportación más conocida es otra.

Su trabajo teórico en el campo de los procesos en los que están involucrados componentes aleatorios (procesos estocásticos) darían fruto en un instrumento matemático que actualmente se conoce como cadena de Márkov: secuencias de valores de una variable aleatoria en las que el valor de la variable en el futuro depende del valor de la variable en el presente, pero es independiente de la historia de dicha variable. Las cadenas de Márkov, hoy día, se consideran una herramienta esencial en disciplinas como la economía, la ingeniería, la investigación de operaciones y muchas otras.

 CADENAS DE MÁRKOV

Las cadenas de Márkov son una herramienta para analizar el comportamiento y el gobierno de determinados tipos de procesos estocásticos, esto es, procesos que evolucionan de forma no determinística a lo largo del tiempo en torno a un conjunto de estados.

Una cadena de Márkov, por tanto, representa un sistema que varía un estado a lo largo del tiempo, siendo cada cambio una transición del sistema. Dichos cambios no están predeterminados, aunque sí lo está la probabilidad del próximo estado en función de los estados anteriores, probabilidad que es constante a lo largo del tiempo (sistema homogéneo en el tiempo). Eventualmente, es una transición, el nuevo estado puede ser el mismo que el anterior y es posible que exista la posibilidad de influir en las probabilidades de transición actuando adecuadamente sobre el sistema (decisión).

Conceptos básicos

Para el estudio de las cadenas de Márkov, deben tenerse en cuenta algunos conceptos claves como los siguientes:

ESTADOS

Los estados son la caracterización de la situación en que se halla el sistema en un instante dado, de dicha caracterización puede ser tanto cuantitativa como cualitativa.

El estado de un sistema en un instante t es una variable cuyos valores solo pueden pertenecer al conjunto de estaos en el sistema. El sistema modelizado por la cadena, por lo tanto, es una variable que cambia con el valor del tiempo, cambio al que llamamos transición.

MATRIZ DE TRANSICIÓN

Es el arreglo numérico donde se condensa las probabilidades de un estado a otro. Dicha matriz es cuadrada con tantas filas y columnas como estados que tiene el sistema, y los elementos de matriz representan la probabilidad de que el estado próximo sea el correspondiente a la columna si el estado actual es el correspondiente a la fila.

Posee 3 propiedades básicas:

1. La suma de las probabilidades de los estados debe ser igual a 1.
2. La matriz de transición debe ser cuadrada.
3. Las probabilidades de transición deben estar entre 0 y 1.

 MATRIZ REGULAR

Es una matriz cuadrada que posee inversa.

ESTADO RECURRENTE

Un estado es recurrente si después de haber entrado a este estado, el proceso definitivamente regresa a ese estado. Por consiguiente un estado es recurrente si y solo si no es transitorio.

MATRIZ ERGÓDICA

Si los estados en una cadena son recurrentes, aperiódicos y se comunican entre si, se dice que la matriz es ergódica. Ejemplo:

ESTADOS ABSORBENTES

Una cadena de Márkov en la que uno o más estados es un estado absorbente, es una cadena de Márkov absorbente. Se alistan los estados en el siguiente orden: primero los estados transitorios y luego los estado absorbentes. Suponga que hay s-m estados transitorios (t1, t2,…, ts-m) y m estado absorbentes (a1, a2,…, am), se escribe la matriz de probabilidades de transición P como sigue:

EJERCICIOS

Ahora veremos algunos ejemplos para ver como funcionan las cadenas de Márkov.

• CADENAS DE MÁRKOV ESTADO ESTABLE

La población colombiana cuenta con 3 principales centros de telefonía móvil como lo son: Comcel, Movistar y Tigo.

Los porcentajes actuales que tiene cada operador en el mercado actual son para Comcel 0.4, para Movistar 0.35 y para Tigo 0.25.

Según un estudio realizado se obtuvo como en un año fue el comportamiento de cada compañía y se arrojo la siguiente información: si en la actualidad el usuario es cliente de Comcel tiene una probabilidad de mantenerse en Comcel del 0.5 de que esta persona se cambie a Tigo  0.3 y que se pase a movistar de 0.2;si el usuario es cliente en la actualidad de movistar la probabilidad que permanezca en Movistar es de 0.4 de que se cambie a Tigo de 0.3 y a Comcel de 0.3 y un usuario de Tigo tiene una probabilidad de permanecer en Tigo de 0.60, de pasar a Comcel 0.2 y de pasarse a Movistar de 0.2.

Como podemos ver para este ejercicio lo primero que debemos identificar son los estados y su respectiva probabilidad de transición:

ESTADOS	COMCEL	MOVISTAR	TIGO
COMCEL	0,5	0,2	0,3
MOVISTAR	0,4	0,3	0,3
TIGO	0,2	0,2	0,6

Con estos datos tenemos la matriz de transición y tenemos el porcentaje de participación en el mercado de cada uno de los operadores y son los siguientes:

Lo que buscamos en este punto el conocer el porcentaje de participación que podría obtener cada compañía con el paso del tiempo, es decir que porcentaje de la población al paso de un año presentara Comcel, Movistar y Tigo.

Para el cálculo de este porcentaje debemos multiplicar la matriz de estado inicial P0 y la matriz de transición t.

PERIODO						T
P0	0,4	0,35	0,25		0,5	0,2	0,3
					0,4	0,3	0,3
					0,2	0,2	0,6
P1	0,39	0,235	0,375		0,5	0,2	0,3
					0,4	0,3	0,3
					0,2	0,2	0,6
P2	0,364	0,2235	0,4125		0,5	0,2	0,3
					0,4	0,3	0,3
					0,2	0,2	0,6
P3	0,3539	0,22235	0,42375

Esto nos indica que en 3 años P3 los porcentajes de la población colombiana para Comcel, Movistar y Tigo será 35,39%, 22,235% y 42,375% respectivamente.

Si continuamos hallando el estado de otros periodos, llegamos a un punto donde las probabilidad se mantiene y es a esto que llamamos Estado Estable. Para el calculo de esto podemos también usar métodos como reducción de ecuaciones o trabajar con matrices por el método de Gauss Jordan y de esta manera podemos obtener el Estado estable de cualquier matriz de transición.

Hallaremos el estado estable del ejercicio anterior por el método de reducción de ecuaciones:

1. Obtenemos las ecuaciones por medio de la transpuesta de la matriz de transición:

2. Organizando las ecuaciones tenemos:

De esta manera obtenemos el valor de cada una de las variables que representan los estados de este ejemplo, dando como resultado Comcel (x)=32,95%; Movistar (y)=22,22%; y Tigo (z)=42,85%.

• CADENAS DE MÁRKOV ESTADOS ABSORBENTES

La Universidad del Atlántico ha estudiado la trayectoria de sus estudiantes en la universidad y ha descubierto que:

a. 70% de los estudiantes de los ingresos regresaran el año siguiente como estudiantes de segundo año, el 15% volverá como estudiante de nuevo ingreso y el resto no regresara.

b. 75% de los estudiantes de segundo año volverán el año siguiente como estudiantes de tercer año, 15% volverá como estudiante de segundo año y el resto no regresara.

c. 80% de los estudiantes de tercer año regresara el año siguiente como estudiantes de último año, 10% volverá como estudiante de tercer año y el resto no regresara.

d. 85% de los estudiantes de último año se graduaran, 10% volverán como estudiantes de último año y el resto no regresara

Se pide:

a. Escriba la matriz de transición del anterior problema y determine si esa matriz es regular.

b. ¿Cuántos años pasara un estudiante de nuevo ingreso?

c. ¿Cuál es la probabilidad que se gradué un estudiante de nuevo ingreso?

Para la solución de este ejercicio debemos identificar los estados:

	1er Año	2do Año	3er Año	4to Año	Graduar	Retirar
1er Año	0,15	0,7	0	0	0	0,15
2do Año	0	0,15	0,75	0	0	0,1
3er Año	0	0	0,1	0,8	0	0,1
4to Año	0	0	0	0,1	0,85	0,05
Graduar	0	0	0	0	1	0
Retirar	0	0	0	0	0	1

Ahora pasamos a identificar los estados de transición y los estados absorbentes:

	1er Año	2do Año	3er Año	4to Año	Graduar	Retirar
1er Año	0,15	0,7	0	0	0	0,15
2do Año	0	0,15	0,75	0	0	0,1
3er Año	0	0	0,1	0,8	0	0,1
4to Año	0	0	0	0,1	0,85	0,05
Graduar	0	0	0	0	1	0
Retirar	0	0	0	0	0	1
			ESTADOS NO ABSORBENTES (TRANSITORIOS)
			ESTADOS ABSORBENTES

Ahora para encontrar la solución de este problema procedemos a restar a la matriz de no absorbente la matriz de identidad:

IDENTIDAD	1	0	0	0
	0	1	0	0
	0	0	1	0
	0	0	0	1

NO ABSORBENTE	0,15	0,7	0	0
	0	0,15	0,75	0
	0	0	0,1	0,8
	0	0	0	0,1

I-N		0,85	-0,7	0	0
		0	0,85	-0,75	0
		0	0	0,9	-0,8
		0	0	0	0,9

Al obtener la matriz I-N procedemos a hallar la inversa de esta matriz:

(I-N)-1	1,176470588	0,96885813	0,80738178	0,71767269
	0	1,17647059	0,98039216	0,87145969
	0	0	1,11111111	0,98765432
	0	0	0	1,11111111

Esta matriz se interpreta de la siguiente manera, los valores que hallamos son equivalentes a tiempo, es decir el tiempo en el cual un estado transitorio necesita para pasar el siguiente estado.

Luego multiplicamos la inversa de la matriz (I-N), por la matriz de estados absorbentes:

ABSORBENTE	0	0,15
	0	0,1
	0	0,1
	0,85	0,05

P=(I-A)-1*A		Graduar	Retirar
	1er Año	0,61002179	0,38997821
	2do Año	0,74074074	0,25925926
	3er Año	0,83950617	0,16049383
	4to Año	0,94444444	0,05555556

Esta matriz nos muestra las probabilidades que posee cada uno de los estados transitorios de caer en los estados absorbentes.

Para este ejemplo un estudiante de nuevo ingreso tiene una probabilidad de 61,002179% de graduarse. 

BIBLIOGRAFÍA
http://cadenasdemarkov.blogspot.com/