Taller1

File:LaboratorioUno-AlgebraLineal.pdf > MMS: Mathematical Foundations of M&S > Special:UserLogin > Taller1

Cadenas de Markov

Suponga que en una población pequeña hay tres sitios para comer, un restaurante de comida china un restaurante de comida mexicana y uno de comidas rápidas. Cada habitante del pueblo cena en alguno de los sitios o en casa.

Suponga que el 70% de los habitantes que cenan en el restaurante chino cambian el sitio de cena la siguiente vez, así: 20% en el restaurante mexicano, 20% en casa y 30% comidas rápidas. De los que cenan en el restaurante mexicano el 60% cambia la siguiente vez así: 10% comidas rápidas, 25% comida china y 25 % en casa. De manera similar, de quienes cenan comida rápida la siguiente vez 15% cenan mexicano, 25% comida china y 30% en casa . Finalmente, de quienes cenan en casa la siguiente vez 20% va al restaurante chino, 25% van al mexicano y 30% a comida rápida.

LLamaremos a esta situación un sistema. Una persona en el pueblo c¿puede cenar en uno de estos cuatro lugares, a cada uno de ellos lo llamremos estado. En el ejemplo, el sistema tiene cuatro estados. Estamos interesados en el exito económico de estos establecimientos, por ejemplo nos interesa saber después de cierto periodo de tiempo el ¿Cuál es porcentaje de los habitantes del pueblo que cenarán comida rápida?.

Suponga que hay un sistema físico o matemático que tiene k estados posibles y que en cualquier momento el sistema esta en uno y solamente uno de los k estados. Además suponga que todas las observaciones en un periodo (n-ésimo) de tiempo estan dadas. La probabilidad de que el sistema este en un estado específico depende de su estado en el periodo de tiempo anterior (n-1-ésimo). A este proceso se le conoce como proceso de Marcov.

En el ejemplo anterior, tenemos cuatro estados para el sistema. Defina a_ij como la probabilidad de el sistema de estar en el estado i después de haber estado en el estado j de cualquier observación. Así, la matriz A=(a_ij) es la matriz de trancisión de un estado a otro: La matriz de trancisión de la cadena de Marcov.

$A = \begin{bmatrix} .25&.20&.25&.30\\ .20&.30&.25&.30\\ .25&.20&.40&.10\\ .30&.30&.10&.30 \end{bmatrix}$

La primera columna representa el estado de cenar en casa, la segunda la de cenar comida china, la tercera cenar comida mexicana y la cuarta comida rápida. De manera similar las filas representan respectivamente, cenar en casa, en el restaurante chino, en el mexicano y comida rápida.

	$\begin{matrix} \mbox{H} & & \mbox{C} & & \mbox{M} & & \mbox{P} \\ \end{matrix}$
$A =$	$\begin{bmatrix} .25&.20&.25&.30\\ .20&.30&.25&.30\\ .25&.20&.40&.10\\ .30&.30&.10&.30 \end{bmatrix} \begin{matrix} H \\ C \\ M \\ P \end{matrix}$

Note que la suma de cada columna de la matriz es uno (1). Una matriz con esta propiedad es llamada una matriz estocástica, matriz de probabilidad o matriz de Marcov. ¿Cuál es la probabilidad de que en el sistema este en el i-ésimo estado en la n-ésima observación?

Para responder a esta pregunta, primero se define el vector de estado. Para una cadena de Marcov con k estados, el vector estado para una observación n es el vector columna definido por:

$x^{(n)} = \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_k\\ \end{bmatrix}$

donde x_i es igual a la probabilidad de que el sistema se encuentre en el i-ésimo estado en el momento de la observación. Note que la suma de los componentes del vector tiene que ser igual a uno. Cualquier vector columna donde x₁ + x₂ + ... + x_k = 1 es llamado vector de probabilidad.

En el ejemplo suponga que al principio cada habitante de la población cena en casa, así el vector de estado inicial x⁽⁰⁾ es $x^{(0)} = \begin{bmatrix} 1\\ 0\\ 0\\ 0\\ \end{bmatrix}$

Entonces en el siguiente periodo de observación, el vector de estado será x⁽¹⁾ $x^{(1)} = A x^{(0)} = \begin{bmatrix} .25\\ .20\\ .25\\ .30\\ \end{bmatrix}$

para la segunda observación el vector estado x⁽²⁾ será $x^{(2)} = Ax^{(1)} = \begin{bmatrix} .25&.20&.25&.30\\ .20&.30&.25&.30\\ .25&.20&.40&.10\\ .30&.30&.10&.30 \end{bmatrix} \begin{bmatrix} .25\\ .20\\ .25\\ .30\\ \end{bmatrix} \begin{bmatrix} .2550\\ .2625\\ .2325\\ .2500\\ \end{bmatrix}$

Note que podria calcularse x⁽²⁾ de manera directa usando x⁽⁰⁾ así: $x^{(2)} = Ax^{(1)} = A(Ax^{(0)}) = A^2 x^{(0)}$

De manera similar es posible encontrar el vector estado para las observaciones x⁽⁵⁾, x⁽¹⁰⁾ , x⁽²⁰⁾ etc.

$x^{(5)} = A^5 x^{(0)} = \begin{bmatrix} .2495\\ .2634\\ .2339\\ .2532\\ \end{bmatrix}\;\;\; x^{(10)} = A^10 x^{(0)} = \begin{bmatrix} .2495\\ .2634\\ .2339\\ .2532\\ \end{bmatrix}\;\;\; x^{(20)} = A^20 x^{(0)} = \begin{bmatrix} .2495\\ .2634\\ .2339\\ .2532\\ \end{bmatrix}$

Esto sugiere que el vector estado se aproxima a un vector así como el número de observaciones se incrementa. Pero este no es el caso de todas las cadenas de Marcov. por ejemplo si

$A = \begin{bmatrix} 0&1\\ 1&0\\ \end{bmatrix}, \text{ y } x^{(0)} = \begin{bmatrix} 1\\ 0\\ \end{bmatrix}$

es posible calcular los vectores de observación para diferentes periodos así:

$x^{(1)} = \begin{bmatrix} 0\\ 1\\ \end{bmatrix}\;\; x^{(2)} = \begin{bmatrix} 1\\ 0\\ \end{bmatrix}\;\; x^{(3)} = \begin{bmatrix} 0\\ 1\\ \end{bmatrix}\;\; x^{(4)} = \begin{bmatrix} 1\\ 0\\ \end{bmatrix}\;\cdots\;\; x^{(2n)} = \begin{bmatrix} 1\\ 0\\ \end{bmatrix}\;\; x^{(2n + 1)} = \begin{bmatrix} 0\\ 1\\ \end{bmatrix}$

Lo cual indica que el sistema oscila y no se puede aproximar a un vector ajustado.

Cadenas de Marcov regulares

Una matriz cuadrada A es regular si para algún entero n todas las entradas de Aⁿ son positivas.

Ejemplo

La matriz A no es una matriz regular porque para todos los enteros positivos sus entradas no son positivas

$A = \begin{bmatrix} 0&1\\ 1&0\\ \end{bmatrix}$

$A^{2n} = \begin{bmatrix} 1&0\\ 0&1\\ \end{bmatrix} \;\;\; A^{2n+1} = \begin{bmatrix} 0&1\\ 1&0\\ \end{bmatrix}$

La matriz B es regular porque para B¹ todas sus entradas son positivas.

$B^{1}=\begin{bmatrix} .25&.20&.25&.30 \\ .20&.30&.25&.30 \\ .25&.20&.40&.10 \\ .30&.30&.10&.30 \\ \end{bmatrix}$

Es posible mostrar que los eigenvalores de B son menores que 1 y que la multiplicidad algebraica de 1 es uno. Se puede mostrar que si B es una matriz regular entonces la matriz Bⁿ se aproxima a la matriz Q cuyas columnas son iguales a los vectores probabilidad q que son llamados vectores de estatdo estacionarios de las cadenas de Marcov regulares. Si B es regular, entonces $B^{n}\to Q = \begin{bmatrix} q_1 & q_1 & \cdots & q_1\\ q_2 & q_2 & \cdots & q_2\\ \vdots & \vdots & \ddots & \vdots \\ q_k & q_k & \cdots & q_k\\ \end{bmatrix} \text{donde } q_1 + q_2 + \cdots + q_{k} = 1$

Es posible mostrar que para cualquier vector probabilidad x⁽⁰⁾ cuando n se grande Aⁿx⁽⁰⁾ se aproxiam al vector de estado estacionario

$q=\begin{bmatrix} q_1\\ q_2\\ \vdots \\ q_k \end{bmatrix}\;\;\;\;\;\; A^{n}x^{(0)}\rightarrow q=\begin{bmatrix} q_1\\ q_2\\ \vdots \\ q_k \end{bmatrix}$

También se puede mostrar que el vector de estado estacionario es el único vector tal que $Aq=q$ por lo tanto q es un eigenvector de A y su eigen valor correspondiente es 1.

Ejercicio

Suponga que el ingreso por al ocupación de un niño, como un adulto, depende de los ingresos de ocupación de sus padres dada la siguiente matriz de transición, donde L = ingreso bajo, M ingreso medio y U = ingreso alto.

	Ingreso de los padres
Ingreso de los niños como adultos	$\begin{matrix} L & & H & & M \end{matrix}$
	$\begin{bmatrix} 0.5 & 0.2 & 0.1 \\ 0.3 & 0.6 & 0.4 \\ 0.2 & 0.2 & 0.5 \end{bmatrix} \begin{matrix} L\\ H\\ M \end{matrix}$

1. ¿Cuál es la probabilidad de que el nieto de una familia de bajos ingresos sea de altos ingresos?
2. En un tiempo largo, ¿qué porción de la población será de ingresos bajos?