lecturas-cadenas de markov

©Prof. Raúl Espejo Rodarte

UABC

VALLE DORADO

FCAYS

2. MÉTODOS CUANTITATIVOS AVANZADOS

2.12. LECTURAS

2.12.3. Cadenas de Markov

UABC FCAyS (795) 1

©Prof. Raúl Espejo Rodarte (11950) [email protected] 6461766600x173 Métodos Cuantitativos Avanzados (12464) Lecturas

2.12.4 Cadenas de Markov

Son sistemas matemáticos que experimentan transiciones de un estado a otro en un espacio de estados.

Una cadena de Markov es una serie de eventos aleatorios, en la cual la probabilidad de que ocurra un

evento depende del evento inmediato anterior. En efecto, las cadenas son procesos caracterizados por su

falta de memoria. “olvidan” toda la cadena de eventos anteriores, y solamente el último evento

condiciona las posibilidades del próximo evento. 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.

Tienen muchas aplicaciones como modelos estadísticos de procesos del mundo real.

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.

La tarea más difícil es reconocer cuándo puede aplicarse. La característica más importante que hay

que buscar en la memoria de un evento a otro.

2.12.3.1. Ejemplos:

1. El movimiento aleatorio en la recta numérica, en cada periodo la posición puede cambiar con la

misma probabilidad hacia adelante o hacia atrás. Las probabilidades de incrementar son las

mismas que de decrementar. Desde cada posición hay dos posibles transiciones: el siguiente entero

o el anterior. Por ejemplo si la posición actual es la 7, entonces la transición a 6 tiene una

probabilidad de .5, sin importar que haya sucedido antes.

2.12.3.1.1. Aplicación a la administración:

2.12.3.1.1.1. Planeación de Personal.

El análisis de transición puede ser útil al planear satisfacer las necesidades de personal. Muchas firmas

emplean trabajadores de diferentes niveles de clasificación dentro de la misma categoría de trabajo. Esto

es común para personal de confianza, oficinistas, obreros calificados, no calificados y personal

profesional. La firma debe tener el número de empleados en cada nivel de clasificación para

proporcionar la oportunidad de promoción adecuada, cumplir con las habilidades necesarias para el

trabajo y controlar la nómina. Una planeación de personal a largo plazo apropiada requiere que se

considere el movimiento de personas tanto hacia arriba en el escalafón de clasificación como hacia

afuera de la organización. El análisis de Markov puede ayudar en este esfuerzo de planeación. El

movimiento de personal a otras clasificaciones puede considerarse como una cadena de Markov.

UABC FCAyS (795) 2



Se supone que hay tres clasificaciones; el grado 1 es la más baja. Además, los descensos se consideran

raros y se omiten. El estado “salen” es absorbente, el cual incluye renuncias, ceses, despidos,

jubilaciones y muertes. Por supuesto, todos los empleados finalmente alcanzan este estado. Las

transiciones del grado 1 al grado 2 y del grado 2 al grado 3 representan promociones. Como

transiciones de probabilidad, están controladas por la firma, puede establecerse el nivel que la firma

determine que es necesario para cumplir sus objetivos. Como ejemplo, supóngase que la firma tiene en

este momento 30 empleados del nivel 3, 90 empleados del grado 2 y 300 empleados del grado 1 y que

desea mantener este nivel de empleados durante el próximo año. Por experiencia, se espera que salgan el

30% de los empleados de grado 1 al año, el 20% de los empleados de grado 2 y el 10% de aquellos que

están en el grado 3. ¿Si la política es contratar sólo en los niveles de clasificación más bajos, cuántos se

deben contratar y cuántos se deben promover el siguiente año para mantener estables los niveles? Este

problema puede resolverse sin el análisis de Markov, pero el modelo es útil para ayudar a conceptualizar

el problema. Como se trata sólo de un ciclo, se usa el análisis de transición. El análisis comienza con el

grado más alto. No se hacen promociones pero el 10%, o sea 3, sale. Todos ellos deben de reemplazarse

por promociones del grado 2. En el nivel de clasificación 2, el 20% sale y se deben promover 3, con una

pérdida de 21. Esto se debe compensar por promoción del grado 1. Al pasar al grado 1, el 30% sale y

21 deben promoverse, lo cual una pérdida total de 111. Por tanto, el siguiente año se deben contratar

111 empleados del nivel 1. En este ejemplo se derivan algunas tasas de transición a partir de

consideraciones externas.

2.12.3.1.2. Otras Aplicaciones

2.12.3.1.2.1. Economía y finanzas

Las cadenas de Markov se pueden utilizar en modelos simples de valuación de opciones para

determinar cuándo existe oportunidad de arbitraje, así como en el modelo de colapsos de una bolsa de

valores o para determinar la volatilidad 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 equipo.

2.12.3.1.2.2. Biología

2.12.3.1.2.2.1. Hábitos Alimenticios.

Una creatura que come frutas, carne y verduras, con las siguientes reglas: solo come una vez al día, si

ayer comió carne, ahora no y comer frutas o verduras tiene la misma probabilidad. Si ahora come frutas,

mañana comerá frutas con una probabilidad de .1, verduras con probabilidad de .5 o carne con una

probabilidad de .4. Cuando coma verduras, al día siguiente consumirá exclusivamente frutas (40% de

probabilidad), o carne con un 60% de probabilidad. Su régimen alimenticio puede ser modelado con una

cadena de Markov, ya que su selección actual solo depende de la selección anterior. Una propiedad

estadística que se podría calcular es el porcentaje esperado de tiempo en que esta criatura come carne, en

un periodo de tiempo muy largo.

2.12.3.1.2.2.2. Estrategia Alimenticia.

http://es.wikipedia.org/wiki/Arbitraje_%28econom%C3%ADa%29

http://es.wikipedia.org/wiki/Bolsa_de_valores

http://es.wikipedia.org/wiki/Bolsa_de_valores

http://es.wikipedia.org/wiki/Volatilidad_%28finanzas%29

http://es.wikipedia.org/w/index.php?title=Deudores_morosos&action=edit&redlink=1

http://es.wikipedia.org/w/index.php?title=Administraci%C3%B3n_de_personal&action=edit&redlink=1

UABC FCAyS (795) 3



La estrategia de la araña. En un cuarto que dividimos en tres espacios:

A la entrada

B la vecindad de la telaraña,

T la telaraña,

Con dimensiones A >> B >> T.

La mosca presenta un vuelo errático (para confundir a sus

depredadores).

Estando en A, tiene probabilidades de permanecer en A (90%),

pasar a B (10%) y no tiene forma de llegar a la telaraña.

Estando en B, tiene probabilidad de pasar a A (40%),

permanecer en B (45%), caer en la telaraña (5%).

Estando en la telaraña significa su muerte, por lo que las

posibilidades de pasar a las zonas A y B es 0 y la de permanecer

en T es de 100%.

En este ejemplo el estado T (†la muerte) es un estado

absorbente, porque una vez que el sistema se encuentra en ese estado, no lo abandona jamás.

Se demuestra, por cadenas de Markov, que todas las moscas que entren al cuarto cerrado, tarde o

temprano caen en la telaraña, que a pesar de estar escondida y ser pequeña, demuestra ser una estrategia

infalible. (Recordemos que el metabolismo de la araña es muy lento y puede vivir en estado suspendido,

casi sin consumir alimento durante mucho tiempo, el movimiento en la telaraña la reanima, bajando

rápidamente por su alimento). Muchos depredadores tienen esta estrategia: Tortuga caimán, los

cocodrilos, muchos peces, etc.

2.12.3.1.2.3. Meteorología

Si consideramos el clima de una región a través de distintos días, es claro que el estado actual solo

depende del último estado y no de toda la historia en sí, de modo que se pueden usar cadenas de Markov

para formular modelos climatológicos básicos. Por ejemplo se han desarrollado modelos de recurrencia

de las lluvias basados en cadenas de Markov.3

2.12.3.1.2.3.1. Determinación del clima

En Ensenada, BC, México llueve después de un día soleado en aproximadamente 20 días al año, y en

5 ocasiones de esos días lluviosos, también llueve al día siguiente.

Soleado Lluvioso S L Soleado 345/365=0.9452 20/365=0.0548 rrrrrrrrrrrrrrrr S 0.9452 0.0548 Lluvioso 15/20=.75 5/20=.25 L .75 .25

Dadas la condición actual puede predecirse la siguiente:

Ahora está lloviendo x0=[0, 1]; mañana: 𝐱𝟏 = [𝟎 𝟏] [. 𝟗𝟒𝟓𝟐 . 𝟎𝟓𝟒𝟖. 𝟕𝟓 . 𝟐𝟓

] = [. 𝟕𝟓 . 𝟐𝟓] hay una

probabilidad de 75% que mañana esté soleado.

En el análisis se obtiene que se llega al estado estable, que indica que la probabilidad de lluvias es de

6.8% y de que no llueva 93.2%

T

B

A

http://es.wikipedia.org/wiki/Cadena_de_M%C3%A1rkov#cite_note-3

UABC FCAyS (795) 4



2.12.3.1.2.4. Simulación

Las cadenas de Markov son utilizadas para proveer una solución analítica a ciertos problemas de

simulación, por ejemplo en teoría de colas el Modelo M/M/14 es de hecho un modelo de cadenas de

Markov.

2.12.3.1.2.1. Física

Se usan en muchos problemas de la termodinámica y la física estadística.

2.12.3.1.2.1.1. Cadena de Ehrenfest

Modela el intercambio de moléculas de gas entre dos urnas. Apéndice

2.12.3.1.2.1.2. Modelo de Difusión de Laplace

Apéndice

2.12.3.1.2.2. Juegos de azar

Son muchos los juegos de azar que se pueden modelar a través de 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, es una de las aplicaciones de las cadenas de Markov en este rubro.

Los juegos de tablero jugados con dados: Turista, Monopolio, Serpientes y Escaleras, la Oca, etc.

en los que la próxima casilla solo depende de la casilla en que se encuentre actualmente el jugador, y un

evento probabilístico normado por el (los) dado(s). Pueden determinarse las probabilidades de

ocurrencia de las diferentes celdas, en las que hay algunas que tienen una probabilidad mayor y son en

las que se ubican penalidades o castigos.

2.12.3.1.2.3. Genética

Se emplean cadenas de Markov en teoría de genética de poblaciones, para describir el cambio de

frecuencias génicas en una población pequeña con generaciones discretas, sometida a deriva genética.

Ha sido empleada en la construcción del modelo de difusión de Motō Kimura.

2.12.3.1.2.4. Música

Diversos algoritmos de composición musical usan cadenas de Markov, por ejemplo el software

Csound o Max

2.12.3.1.2.5. Operaciones

Se emplean cadenas de Markov en inventarios, mantenimiento, flujo de proceso

2.12.3.1.2.6. Redes Neuronales

Se utilizan en las máquinas de Boltzmann (redes neuronales)

2.12.3.1.2.1. Modelos epidemiológicos

Una importante aplicación de las cadenas de Markov se encuentra en el proceso Galton-Watson. Éste

es un proceso de ramificación que se puede usar, entre otras cosas, para modelar el desarrollo de una

epidemia (véase modelaje matemático de epidemias).

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_colas

http://es.wikipedia.org/w/index.php?title=Modelo_M/M/1&action=edit&redlink=1

http://es.wikipedia.org/w/index.php?title=Modelo_M/M/1&action=edit&redlink=1

http://es.wikipedia.org/w/index.php?title=Ruina_del_jugador&action=edit&redlink=1

http://es.wikipedia.org/wiki/Deriva_gen%C3%A9tica

http://es.wikipedia.org/wiki/Mot%C5%8D_Kimura

http://es.wikipedia.org/w/index.php?title=Algoritmo_de_composici%C3%B3n_musical&action=edit&redlink=1

http://es.wikipedia.org/wiki/Csound

http://es.wikipedia.org/wiki/Max_%28programa%29

http://es.wikipedia.org/w/index.php?title=M%C3%A1quinas_de_Boltzmann&action=edit&redlink=1

http://es.wikipedia.org/wiki/Proceso_Galton-Watson

http://es.wikipedia.org/wiki/Modelaje_matem%C3%A1tico_de_epidemias

UABC FCAyS (795) 5



2.12.3.1.2.2. Internet

El pagerank de una página web (usado por Google en sus motores de búsqueda) se define a través 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.

2.12.3.1.2.3. Caso de Aplicación:

2.12.3.1.2.3.1. Análisis de Participación de Mercado.

El análisis de transición puede ser útil para analizar la lealtad del público. La fidelidad de un cliente a

un mercado particular solo se puede manejar de manera estadística y por tanto, probabilística. En el

devenir del tiempo, este estadístico aleatorio corresponde a una variable estocástica. Se trata de estimar

la probabilidad de que un cliente que usó un mercado, regrese a ese mercado. La investigación pretende

contabilizar cuantos clientes de un supermercado (Suriana), hacen su siguiente compra en dicho

almacén. Una planeación de lealtad comercial a largo plazo apropiada requiere que se considere el

movimiento de clientes tanto hacia otra tienda como hacia ésta, pues no se puede estimar el costo de la

pérdida de un cliente. El análisis de Markov puede ayudar en este esfuerzo de planeación: El

movimiento de clientes a otros mercados puede considerarse como una cadena de Markov.

Se ha determinado que del seguimiento de los clientes del almacén Suriana Bahía, indica que el 93%

de ellos hicieron su compra anterior en esta misma tienda. Y que 8% de los clientes hicieron sus

compras en esta tienda pero la vez anterior no.

Suriana Otro Suriana .93 1-.93=.07 Otro .08 1 - .08 = .92

𝑴 = [. 𝟗𝟑 . 𝟎𝟕. 𝟎𝟖 . 𝟗𝟐

]

En este ejemplo se derivan algunas probabilidades de transición a partir de consideraciones externas.

2.12.4. Conceptos básicos

2.12.4.1. Estados

Llamamos un estado a la condición única de un elemento del espacio de estados que denotaremos por

S: un conjunto exhaustivo y mutuamente excluyente de todas las posibilidades en que puede estar el

sistema. A los diferentes estados los nombraremos si donde i es un elemento del conjunto formado por

todos los números enteros no negativos desde 1 hasta n, que es el número de estados posibles. Al estado

inicial, si se requiere, lo llamaremos s1.

2.12.4.1.1. Ejemplo

Todos los estados posibles son S= {1, 2, 3, 4,5}. Generalizando S= {s1, s2,…s5}, en donde n es 5. Otra

forma de escribirlo es S= {si}, con i є {1, 2, 3, 4, 5}.1

1 i es un elemento del conjunto cuyos elementos son 1, 2, 3, 4 y 5

0 1 0 .93 .07 1 .08 .92

http://es.wikipedia.org/wiki/Pagerank

http://es.wikipedia.org/wiki/Google

UABC FCAyS (795) 6



st, representa el estado del sistema en el tiempo t, una categoría mutuamente exclusiva y

colectivamente exhaustiva con característica de interés medible en el tiempo t, Por ejemplo, el proceso

estocástico, s1, s2, s3, … puede representar la colección de niveles de inventario semanales (o mensuales)

de un producto dado, o puede representar la colección de demandas semanales (o mensuales) de este

producto.

2.12.4.2. Tiempos Discretos

Aunque es posible definir procesos de Markov en tiempo continuo, se simplifican los problemas si

establecemos que el sistema solo es evaluado en momentos precisos, sin poder decir nada de las

condiciones y posibles situaciones que pudieran suceder entre observaciones del sistema. Podemos asumir

que los cambios que suceden entre observaciones no son significativos en relación al cambio que hay

entre dichos instantes.

2.12.4.3. Espacio de Estados

Un modelo de Markov consiste en una serie de eventos aleatoriamente seleccionados de un conjunto de

estados discretos (Espacio de Estados). Este conjunto (S) es colectivamente exhaustivo2 y mutuamente

excluyente3. Describe todos los posibles estados donde el sistema puede estar y cada estado excluye la

ocurrencia de todos los demás. La transición del estado i a j ocurre con una probabilidad Pi,j

Podemos pensar en un modelo de Markov como una simple línea de transferencia.

2.12.4.4. Proceso Estocástico

Un proceso estocástico se define como una colección indexada de variables aleatorias

{St}= {s0, s1, s2,…, st,…}, donde el subíndice t toma valores de un conjunto T dado, que frecuentemente

se toma como el conjunto de los enteros no negativos (como el tiempo discreto).

2.12.4.5. Procesos de Markov

Se dice que un proceso estocástico tiene la propiedad markoviana (de primer orden) si el estado en el

lapso de tiempo t (actual) es st, en el próximo lapso de tiempo

P{ st+1 = j | s0 =k0, s1 =k1, s2 =k2 , … st-1 = kt-1 , st= i}= P {st+1 =j | st = i }4,

Para toda t = 1, 2, … y para toda sucesión { k0, k1, k2 , … , kt-1, i, j}5. (Historia previa de estados).

El siguiente estado solo depende del estado actual, y su probabilidad de llegar al siguiente estado.

Se puede demostrar que esta propiedad markoviana es equivalente a establecer una probabilidad

condicional de cualquier “evento” futuro dados cualesquier “eventos“ pasados y el estado actual xt+1, es

independiente de todo evento anterior a xt.

Las probabilidades condicionales P{st+1 = j | st = i} se llaman probabilidades de transición. Si para cada

i y j, P{st+1=j | st=i}=p{s2=j|s1=i}, para toda t = 1, 2, …

2 Que todos los estados posibles son elementos de dicho conjunto

3 Que solo existe posibilidad de estar en uno (y sólo uno) de los estados factibles en un tiempo dado.

4 Probabilidad de que el siguiente estado sea j dado que todos los estados anteriores fueron conocidos, es igual a la

probabilidad de que el estado siguiente sea i solamente está condicionada al estado actual

__________________________________________________________________________________________________ 5 Toda la historia previa del sistema

UABC FCAyS (795) 7



Entonces se dice que las probabilidades de transición (de un paso) son estacionarias (La probabilidad

de pasar de un estado i a un estado j siempre es la misma), y por lo general se denotan por pi,j. Así, tener

probabilidades de transición estacionarias implica que las probabilidades de transición no cambian con el

tiempo. En otras palabras, el siguiente estado solo depende del estado actual.

La existencia de probabilidades de transición estacionarias (de un paso) también implica que, para cada

i, j y n (n=1,2,…): P{st+n=j|st=i}=P{sn=j|s1=i}, para toda t=1,2,⋯. Estas probabilidades condicionales

casi siempre se denotan por pi,j y se llaman probabilidades de transición de n pasos. Así, pi,j es

simplemente la probabilidad condicional de que la variable aleatoria s, comenzando en el estado i, se

encuentre en el estado j después de n pasos (unidades de tiempo).

Como la pi,j son probabilidades condicionales, deben satisfacer las propiedades:

𝟎 ≤ 𝐏𝐢,𝐣(𝐧)≤ 𝟏 ∀ 𝐢, 𝐣; 𝐧 = 𝟏, 𝟐,⋯

6

𝟏 = ∑ 𝐏𝐢,𝐣(𝐧)𝐧

𝐣=𝟏 7

Condiciones suficientes para definir una distribución de probabilidad.

2.12.4.1. Orden

Es el número de estados previos que definen el nuevo estado, aquí solo discutimos cadenas de primer

orden pues sólo dependen del estado anterior.

2.12.4.2. Ensayos

Llamamos un ensayo a la observación del estado en el momento oportuno. Es un elemento del espacio

de estados.

2.12.4.3. Transiciones

Es el cambio de un estado a otro. Dentro del espacio de estados, el proceso empieza en algún estado, y

se mueve sucesivamente de un estado a otro. Cada uno de estos cambios de estado le llamamos etapa, si

actualmente se encuentra en el estado i, y consecuentemente se moverá al estado j, con una probabilidad

pi,j, que no depende de que estados antecedieron al estado actual. Si esta es constante se dice que el

sistema es estacionario.

La probabilidad pi,j, se llama probabilidad de transición. El estado puede permanecer en ese mismo

estado con probabilidad pi,i. Una distribución de probabilidad inicial, definida en S, especifica el estado

inicial. Usualmente se establece que es un estado inicial

2.12.4.3.1. Homogeneidad

Una cadena de Markov se dice homogénea si la probabilidad de ir del estado i al estado j en un paso no

depende del tiempo en el que se encuentra la cadena, esto es:

𝐏(𝐱𝐧 = |𝐱𝐧−𝟏 = 𝐢) = 𝐏(𝐱𝟏 = 𝐣|𝐱𝟎 = 𝐢) Para todo n y para cualquier i, j. Si para alguna pareja de estados y para algún tiempo n la propiedad antes mencionada no se cumple

diremos que la cadena de Markov es no homogénea

6 Todos son números positivos menores o iguales que 1

7 Todas juntas suman 1

UABC FCAyS (795) 8



2.12.4.3.2. Recurrente

En una cadena de Markov con espacio de estados E, si x ∈ E se define la probabilidad de recurrencia del

estado x (que eventualmente pueda a volver a estar en ese estado)

𝐿𝑥 = 𝑃(𝑥𝑛 = 𝑥 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔𝑢𝑛𝑎 𝑛 ∈ 𝑁 | 𝑥0 = 𝑥) Es la probabilidad de que estando en algún estado, pueda volver a estar en él, en algún periodo futuro.

Y diremos que:

x es estado recurrente si Lx = 1 es seguro que estando en algún estado, pueda volver a estar en él.

2.12.4.3.2.1. Transitorio

x es transitorio si Lx < 1 hay estados en los que la posibilidad de volver a suceder no es seguro.

2.12.4.3.2.2. Absorbente

Un estado x es absorbente si

𝑝𝑥,𝑥 = 1

Una clase de comunicación es clase recurrente si todos sus estados son recurrentes.

Sea , si x∈Ediremos que:

x es cero-recurrente si

x es positivo-recurrente si

El real se interpreta como el tiempo promedio de recurrencia.

2.12.4.3.3. Periódico

El periodo de un estado x∈E se define como:

donde denota el máximo común divisor.

Si d(x)=1 diremos que x es un estado aperiódico.

Una cadena de Markov se dice aperiódica si todos sus estados son aperiódicos.

2.12.4.4. Cadenas irreducibles

Una cadena de Markov se dice irreducible si se cumple cualquiera de las siguientes condiciones

(equivalentes entre sí):

Desde cualquier estado de E se puede acceder a cualquier otro.

Todos los estados se comunican entre sí.

C(x)=E para algún x∈E.

C(x)=E para todo x∈E.

El único conjunto cerrado es el total.

La cadena de Ehrenfest o la caminata aleatoria sin barreras absorbentes son ejemplos de cadenas de

Markov irreducibles.

2.12.4.5. Cadenas positivo-recurrentes

Una cadena de Markov se dice positivo-recurrente si todos sus estados son positivo-recurrentes. Si la

cadena es además irreducible es posible demostrar que existe un único vector de probabilidad invariante y

está dado por:

http://es.wikipedia.org/wiki/M%C3%A1ximo_com%C3%BAn_divisor

http://es.wikipedia.org/wiki/Cadena_de_Ehrenfest

http://es.wikipedia.org/wiki/Camino_aleatorio

UABC FCAyS (795) 9



2.12.4.6. Cadenas regulares

Ergódico

Una cadena de Markov se dice regular (también primitiva o ergódica) si existe alguna potencia positiva

de la matriz de transición cuyas entradas sean todas estrictamente mayores que cero.

Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena se tiene que:

donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad w, que

resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas regulares, éste vector

invariante es único.

2.12.4.7. Cadenas absorbentes

Una cadena de Markov con espacio de estados finito se dice absorbente si se cumplen las dos condiciones

siguientes:

1. La cadena tiene al menos un estado absorbente.

2. De cualquier estado no absorbente se accede a algún estado absorbente.

Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos

los siguientes resultados:

Su matriz de transición siempre se puede llevar a una de la forma

donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz

nula y R alguna submatriz.

, esto es, no importa en donde se encuentre la cadena, eventualmente

terminará en un estado absorbente.

2.12.4.8. Diagramas de transiciones

Es un grafo dirigido en el que los estados se representan como globos y las transiciones como flechas,

rotuladas con una probabilidad, como el que se muestra en la figura siguiente, en la que se ilustra un

sistema de Markov con cinco estados posibles: S= {s1, s2, s3, s4 y s5}. La probabilidad condicional o de

transición de moverse de un estado a otro se indica en el diagrama como p1,2 (probabilidad de ir al estado

1 al estado 2).

Significan una herramienta idónea para entender el problema y asignarle las características de diseño

como fase inicial para la elaboración de la matriz de transición.

UABC FCAyS (795) 10



2.12.4.8.1. Probabilidades de transición

La medida de posibilidades de cambiar de un estado a otro le llamamos probabilidad de transición. Son

probabilidades de estar en un nuevo estado, condicionadas de haber estado en otro. La probabilidad de

que i sea el siguiente evento generado es una probabilidad condicional: probabilidad de estar en el estado j dado que estaba en el estado i: P(j | i). Esto se llama probabilidad de transición del estado i al estado j que

denotaremos por pij. Para describir completamente una cadena de Markov es necesario conocer todos los

estados y todas las probabilidades de transición.

Todas las posibilidades de salir de un estado hacen el evento seguro, esto es, la suma de las

probabilidades de salir de un estado es 1. Esto hace de cada estado y sus posibles transiciones una

Distribución de Probabilidad

2.12.4.9. Matriz de transición

Otro recurso para definir las probabilidades de transición, es usar una matriz de transición. La matriz

de transición para el ejemplo del diagrama de estados se muestra a continuación:

Estado Final 1 2 3 4 5

Inicial

1 P1,1 P1,2 0 0 P1,5 P1,1+p1,2+p1,5=1 2 0 P2,2 P2,3 0 P2,5 P2,2+p2,3+p2,5=1

3 0 P3,2 P3,3 P3,4 P3,5 P3,2+p3,3+p3,4+p3,5=1

4 0 0 0 P4,4 P4,5 P4,4+p4,5=1 5 0 0 0 0 P5,5 P5,5=1

Generalizando para una matriz de transición de m estados:

P1,1

S1 S2

S5

P1,2

S4

P3,3

P3,4

P3,3

S3

P2,2

P24

P2,5

P3,2 P2,3

P3,4 P3,5

P5,5

P1,5

UABC FCAyS (795) 11



Estado Final 1 2 3 … m

Inicial

1 P1,1 P1,2 P1,3 … P1,m P= 2 P2,1 P2,2 P2,3 … P2,m 3 P3,1 P3,2 P3,3 … p2m … … … … … … m pm1 pm2 pm2 … pmm

Si se define a M como la matriz de transición de un paso8:

𝐌(𝟏) = 𝐌 = [

𝐩𝟏,𝟏 𝐩𝟏𝟐𝐩𝟐,𝟏 𝐩𝟐,𝟐

⋯ 𝐩𝟏,𝐦⋯ 𝐩𝟐,𝐦

⋮ ⋮𝐩𝐦,𝟏 𝐩𝐦,𝟐

⋱ ⋮⋯ 𝐩𝐦,𝐦

]

Donde Pi,j es la probabilidad (condicional) de pasar al estado j habiendo estado en el estado i , lo que

ocasiona una suma horizontal de 1 pues hay una certeza de que habiendo estado en el estado i pase a

cualquier estado, lo que significa que los estados son mutuamente excluyentes y colectivamente

exhaustivos.

Cada renglón constituye una distribución de probabilidad, que como tal tiene las siguientes

características:

𝟎 ≤ 𝐩𝐢,𝐣 ≤ 𝟏 ∀ 𝐢, 𝐣 ∈ {𝟏, 𝟐,⋯ , 𝐧} 9

𝟏 = ∑ 𝐩𝐢,𝐣 𝐧𝐣=𝟏 ∀ 𝐢 ∈ {𝟏, 𝟐,⋯ , 𝐧} 10

La matriz M, proporciona una completa descripción del proceso de Markov la cual se usará para hacer

los análisis correspondientes para responder numerosas preguntas sobre el sistema.

2.12.4.9.1. Vector de Estados Iniciales

Es un renglón que indica una distribución de probabilidad de estar en los diferentes estados en este

momento �⃗⃗� (𝟎)

. Si se multiplica por M, se obtiene las probabilidades en el periodo siguiente.

�⃗⃗� (𝟏)= �⃗⃗�

(𝟎)𝐌

Así, empezando en el estado [1,0], que significa haber sido cliente en Suriana, la probabilidad para la

etapa siguiente es

[𝟏, 𝟎] [. 𝟗𝟑 . 𝟎𝟕. 𝟎𝟖 . 𝟗𝟐

]=[.93, 07]

2.12.4.9.2. Probabilidad de transición de n pasos.

Una vez que se ha definido la matriz de transición, que es de un solo lapso de tiempo (se trata de una

cadena de Markov de primer orden), es posible obtener la matriz de transición a dos o más periodos de

tiempo. Para ello hay que considerar todos los estados intermedios posibles

8 El superíndice n no se escribe cuando n=1.

9 0 menor o igual que la probabilidad de pasar del estado i al estado j menor o igual que 1 para toda i y j elementos del

conjunto cuyos elementos son 1, 2, etcétera, hasta en número m 10

1 es igual a la suma de todas las transiciones posibles desde un estado i, para todos los estados posibles.

UABC FCAyS (795) 12



2.12.4.9.2.1. Representación de árbol

Para mostrar cómo es que para cada transición se deben tomar los estados intermedios factibles

presentamos el siguiente diagrama de árbol. Como todos estos son procesos independientes, pues no hay

ninguna relación entre si, las probabilidades de dos eventos consecutivos se multiplican para obtener la

probabilidad de que así suceda.

UABC FCAyS (795) 13



S1

S1

S1 P11*P11

P(S1|S1)= P11*P11 + P12*P21 + … +P1m*Pm1

𝐏(𝐒𝟏 | 𝐒𝟏) = ∑𝐏𝟏,𝐤

𝐧

𝐤=𝟏

∙ 𝐏𝐤,𝟏

S2 P11*P12 ⁞ ⁞

Sm P11*P1m

S2

S1 P12*P21 S2 P12*P22 ⁞ ⁞

Sm P12*P2m ⁞ ⁞

⁞ ⁞

⁞ ⁞

Sm

S1 P1m*Pm1 S2 P1m*Pm2 ⁞ .

Sm P1m*Pmm

S2

S1

S1 P21*P11

P(S1|S2)= P11*P12 + P12*P22 + … +P1m*Pm2

𝐏(𝐒𝟏 | 𝐒𝟐) = ∑𝐏𝟏,𝐤

𝐧

𝐤=𝟏

∙ 𝐏𝐤,𝟐

S2 P21*P12 ⁞ ⁞

Sm P21*P1m

S2

S1 P22*P21 S2 P22*P22 ⁞ ⁞

Sm P22*P2m ⁞ ⁞

⁞ ⁞

⁞ ⁞

Sm

S1 P2m*Pm1 S2 P2m*Pm2 ⁞ ⁞

Sm P2m*Pmm ⁞ ⁞

⁞ ⁞

⁞ ⁞

⁞ ⁞

Sm

S1

S1 Pm1*P11

P(S1|Sm)= P11*P1m + P12*P2m + … +P1m*Pmm

𝐏(𝐒𝟏 | 𝐒𝐧) = ∑𝐏𝟏,𝐤

𝐧

𝐤=𝟏

∙ 𝐏𝐤,𝐧

S2 Pm1*P12 ⁞ ⁞

Sm Pm1*P1m

S2

S1 Pm2*P21 S2 Pm2*P22 ⁞ ⁞

Sm Pm2*P2m ⁞ ⁞

⁞ ⁞

⁞ ⁞

Sm

S1 Pmm*Pm1 S2 Pmm*Pm2 ⁞ ⁞

Sm P2m*Pmm

UABC FCAyS (795) 14



𝐏(𝐬𝐢|𝐬𝐣) = ∑𝐩𝐢,𝐤 ∙ 𝐩𝐤,𝐣 ∀ 𝐢, 𝐣 ∈ {𝟏, 𝟐, 𝟑.⋯ ,𝐦}

𝐧

𝐤=𝟏

11

Conforme al algoritmo de multiplicación de matrices:

C=A·B

Matrices de dimensiones a * b y b * c, dan como resultado una matriz a * c. En matrices, el orden de los

factores si altera el producto. Hay matrices que no se pueden multiplicar

𝐜 = [

𝐚𝟏,𝟏 𝐚𝟏,𝟐𝐚𝟐,𝟏 𝐚𝟐,𝟐

⋯ 𝐚𝟏,𝐧⋯ 𝐚𝟐,𝐧

⋮ ⋮𝐚𝐦,𝟏 𝐚𝐦,𝟐

⋱ ⋮⋯ 𝐚𝐦,𝐧

] ∙

[ 𝐛𝟏,𝟏 𝐛𝟏,𝟐𝐛𝟐,𝟏 𝐛𝟐,𝟐

⋯ 𝐛𝟏,𝐪⋯ 𝐛𝟐,𝐪

⋮ ⋮𝐛𝐧,𝟏 𝐛𝐧,𝟐

⋱ ⋮⋯ 𝐛𝐧,𝐪]

𝐂 =

[ 𝐚𝟏,𝟏 ∙ 𝐛𝟏,𝟏 + 𝐚𝟏,𝟐 ∙ 𝐛𝟐,𝟏 +⋯+ 𝐚𝟏,𝐧 ∙ 𝐛𝐧,𝟏 𝐚𝟏,𝟏 ∙ 𝐛𝟏,𝟐 + 𝐚𝟏,𝟐 ∙ 𝐛𝟐,𝟐 +⋯+ 𝐚𝟏,𝐧 ∙ 𝐛𝐧,𝟐𝐚𝟐,𝟏 ∙ 𝐛𝟏,𝟏 + 𝐚𝟐,𝟐 ∙ 𝐛𝟐,𝟏 +⋯+ 𝐚𝟐,𝐧 ∙ 𝐛𝐧,𝟏 𝐚𝟐,𝟏 ∙ 𝐛𝟏,𝟐 + 𝐚𝟐,𝟐 ∙ 𝐛𝟐,𝟐 +⋯+ 𝐚𝟐,𝐧 ∙ 𝐛𝐧,𝟐

⋯⋯

⋮ ⋮𝐚𝐦,𝟏 ∙ 𝐛𝟏,𝟏 + 𝐚𝐦,𝟐 ∙ 𝐛𝟐,𝟏 +⋯+ 𝐚𝐦𝐧 ∙ 𝐛𝐧,𝟏 𝐚𝐦,𝟏 ∙ 𝐛𝟏,𝟐 + 𝐚𝐦,𝟐 ∙ 𝐛𝟐,𝟐 +⋯+ 𝐚𝐦,𝐧 ∙ 𝐛𝐧,𝟐

⋱⋯ ]

𝐂 =

[ ∑𝐚𝟏,𝐣 ∙ 𝐛𝐣,𝟏

𝐧

𝐣=𝟏

∑𝐚𝟏,𝐣 ∙ 𝐛𝐣,𝟐

𝐧

𝐣=𝟏

∑𝐚𝟐,𝐣 ∙ 𝐛𝐣,𝟏

𝐧

𝐣=𝟏

∑𝐚𝟐,𝐣 ∙ 𝐛𝐣,𝟐

𝐧

𝐣=𝟏

⋯ ∑𝐚𝟏,𝐣 ∙ 𝐛𝐣,𝐪

𝐧

𝐣=𝟏

⋯ ∑𝐚𝟐,𝐣 ∙ 𝐛𝐣,𝐪

𝐧

𝐣=𝟏

⋮ ⋮

∑𝐚𝐦,𝐣 ∙ 𝐛𝐣,𝟏

𝐧

𝐣=𝟏

∑𝐚𝐦,𝐣 ∙ 𝐛𝐣,𝟐

𝐧

𝐣=𝟏

⋱ ⋮

⋯ ∑𝐚𝐦,𝐣 ∙ 𝐛𝐣,𝐪

𝐧

𝐣=𝟏 ]

Al producto de una matriz cuadrada (necesariamente) por si misma le llamamos cuadrado (notación que

se extiende a cualquier potencia). Observando la analogía con las fórmulas obtenidas del árbol anterior:

𝐌𝟐 = 𝐌 ∙ 𝐌 =

[ ∑𝐩𝟏,𝐣 ∙ 𝐩𝐣,𝟏

𝐧

𝐣=𝟏

∑𝐩𝟏,𝐣 ∙ 𝐩𝐣,𝟐

𝐧

𝐣=𝟏

∑𝐩𝟐,𝐣 ∙ 𝐩𝐣,𝟏

𝐧

𝐣=𝟏

∑𝐩𝟐,𝐣 ∙ 𝐩𝐣,𝟐

𝐧

𝐣=𝟏

⋯ ∑𝐩𝟏,𝐣 ∙ 𝐩𝐣,𝐧

𝐧

𝐣=𝟏

⋯ ∑𝐩𝟐,𝐣 ∙ 𝐩𝐣,𝐧

𝐧

𝐣=𝟏

⋮ ⋮

∑𝐩𝐧,𝐣 ∙ 𝐩𝐣,𝟏

𝐧

𝐣=𝟏

∑𝐩𝐧,𝐣 ∙ 𝐩𝐣,𝟐

𝐧

𝐣=𝟏

⋱ ⋮

⋯ ∑𝐩𝐧,𝐣 ∙ 𝐩𝐣,𝐧

𝐧

𝐣=𝟏 ]

𝐌𝟐 = [

𝐏(𝐬𝟏 → 𝐬? → 𝐬𝟏) 𝐏(𝐬𝟏 → 𝐬? → 𝐬𝟐)𝐏(𝐬𝟐 → 𝐬? → 𝐬𝟏) 𝐏(𝐬𝟐 → 𝐬? → 𝐬𝟐)

⋯ 𝐏(𝐬𝟏 → 𝐬? → 𝐬𝐦)⋯ 𝐏(𝐬𝟐 → 𝐬? → 𝐬𝐦)

⋮ ⋮𝐏(𝐬𝐦 → 𝐬? → 𝐬𝟏) 𝐏(𝐬𝐦 → 𝐬? → 𝐬𝟐)

⋱ ⋮⋯ 𝐏(𝐬𝐦 → 𝐬? → 𝐬𝐦)

]

11

Probabilidad de que suceda Si dado que sucedió Sj, es igual a la suma desde k=1 hasta k=n de los productos de las

probabilidades de transición 𝐩𝐢,𝐤 𝑝𝑜𝑟 𝐩𝐤,𝐣 , para toda i, j elementos del conjunto {1, 2,3,…, n}.

UABC FCAyS (795) 15



𝐌𝟐 =

[ 𝐩𝟏,𝟏

(𝟐)𝐩𝟏,𝟐(𝟐)

𝐩𝟐,𝟏(𝟐)

𝐩𝟐,𝟐(𝟐)

⋯ 𝐩𝟏,𝐧(𝟐)

⋯ 𝐩𝟐,𝐧(𝟐)

⋮ ⋮

𝐩𝐦,𝟏(𝟐)

𝐩𝐦,𝟐(𝟐)

⋱ ⋮

⋯ 𝐩𝐦,𝐦(𝟐)

]

Las ecuaciones de Chapman-Kolmogorov proporcionan un método para calcular estas probabilidades de

transición de n pasos:

𝐏𝐢,𝐣(𝐧)=∑𝐏𝐢,𝐤

(𝐦)∙ 𝐏𝐤,𝐣

(𝐧−𝐦) ∀ 𝐢, 𝐣, 𝐤 𝐲 𝟎 ≤ 𝐦 ≤ 𝐧

𝐦

𝐤=𝟎

Estas ecuaciones simplemente señalan que al ir de un estado i al estado j en n pasos, el proceso estará en

algún estado k después de exactamente m (menor que n) pasos.

Es solo la probabilidad condicional de que, si se comienza en el estado i, el proceso vaya al estado k

después de m pasos y después al estado j en n- m pasos.

Los casos especiales de m=1 y m=n-1 conducen a las siguientes expresiones, para toda i, j, y n de lo

cual resulta que las probabilidades de transición de n pasos se pueden obtener a partir de las

probabilidades de transición de un paso de manera recursiva. Para n=2,

𝐌𝐢,𝐣(𝟐)=∑𝐩𝐢,𝐤 ∙ 𝐌𝐤,𝐣 ∀ 𝐢, 𝐣, 𝐧

𝐧

𝐤=𝟏

Note que las 𝐩𝐢,𝐣(𝟐)

son los elementos de la matriz 𝐌𝟐, pero también debe de observarse que estos

elementos, se obtienen multiplicando la matriz de transición de un paso por sí misma; esto es:

𝐌𝟐 = 𝐌 ∗ 𝐌. En términos más generales, se concluye que la matriz de probabilidades de transición de n pasos se

puede obtener de la expresión:

M(n) = M * M .... M = Mn = MMn-1 = Mn-1 M.

Entonces, la matriz de probabilidades de transición de n pasos se puede obtener calculando la n-ésima

potencia de la matriz de transición de un paso. Para valores no muy grandes de n, la matriz de transición

de n pasos se puede calcular en la forma que se acaba de describir, pero cuando n es grande, tales cálculos

resultan tediosos y, más aún, los errores de redondeo pueden causar inexactitudes.

2.12.4.9.2.1.1. Vector de estados en el periodo k

�⃗⃗� (𝟏)= �⃗⃗�

(𝟎)𝐌

�⃗⃗� (𝟐)= �⃗⃗�

(𝟏)𝐌 = (�⃗⃗�

(𝟎)𝐌)𝐌) = �⃗⃗�

(𝟎)𝐌𝟐

…

�⃗⃗� (𝐤)= �⃗⃗�

(𝟎)𝐌𝒌

UABC FCAyS (795) 16



2.12.4.9.2.2. Ejemplo12 :

[1] [2]Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar

cada semana. Sean D1, D2, ... las demandas de esta cámara durante la primera, segunda, ... , semana,

respectivamente. Se supone que las Di son variables aleatorias independientes e idénticamente distribuidas

que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el

momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el

número de cámaras al final de la semana dos, etc. Suponga que X0 = 3. El sábado en la noche la tienda

hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda hace un pedido que le

entregan el lunes en el momento de abrir la tienda. La tienda usa la siguiente política para ordenar:

Si no hay cámaras en inventario al final de la semana, se surten 3.

De otra manera, no se surten cámaras.

Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {Xt} para t=0, 1, ... es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los

enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana.

La demanda se conduce de manera exponencial (todos los eventos son independientes entre si), que para

explicar el número de clientes que vienen por semana es la distribución de Poisson que tiene dos

parámetros: la media (λ que es el promedio de clientes semanales en un largo lapso de tiempo), y el

número de clientes semanales, Así la probabilidad de que lleguen x clientes semanales, cuando en

promedio llegan λ es:

𝐏(𝐱; 𝛌) =𝛌𝐱𝐞−𝛌

𝐱!

Se tiene que la demanda cuando se tiene una esperanza (media) de 3, λ=3

A B C D

1 _λ = 3

2

X={

0 0.04978707 =POISSON(B2,$B$1,FALSO)

3 1 0.14936121 =POISSON(B2,$B$1,FALSO)

4 2 0.22404181 =POISSON(B2,$B$1,FALSO)

5

3 o mas 0.57680992 =1-SUMA(C2:C4)

6

2 o mas 0.80085173 =1-SUMA(C2:C3)

7 1 o mas 0.95021293 =1- C2

Para que la semana termine con i cámaras, dado que la semana anterior terminó con j cámaras:

0 1 2 3

0 P(DEMANDA ≥3) P(DEMANDA =2) P(DEMANDA =1) P(DEMANDA =0)

1 P(DEMANDA ≥1) P(DEMANDA =0) 0 0

2 P(DEMANDA ≥2) P(DEMANDA =1 P(DEMANDA =0) 0

3 P(DEMANDA ≥3) P(DEMANDA =2) P(DEMANDA =1) P(DEMANDA =0) La matriz de transición es:

M =

0.57680992 0.22404181 0.14936121 0.04978707

0.95021293 0.04978707 0 0

0.80085173 0.14936121 0.04978707 0

0.57680992 0.22404181 0.14936121 0.04978707

12

En la resolución numérica de este ejemplo usaremos el ®Excel de ®MicroSoft para su programación

UABC FCAyS (795) 17



M(2) = M2=

0.69393096 0.17384708 0.10102554 0.03119643

0.59540056 0.21536618 0.14192495 0.04730832

0.64373623 0.19429678 0.12209493 0.03987206

0.69393096 0.17384708 0.10102554 0.03119643 Así, dado que tiene una cámara al final de una semana, la probabilidad de que no haya cámaras en

inventario dos semanas después es 0.5954 ; es decir, 𝐏𝟏,𝟎(𝟐)= 𝟎. 𝟓𝟗𝟓𝟒 . De igual manera, dado que se

tienen dos cámaras al final de una semana, la probabilidad de que haya tres cámaras en el almacén dos

semanas después es 𝐏𝟐,𝟑(𝟐)= 𝟎. 𝟎𝟑𝟗𝟖𝟕

La matriz de transición de cuatro pasos también se puede obtener de la siguiente manera:

M(4) = M4 = M(2) * M(2)

2.12.4.9.3. Estado estacionario

El cálculo de la probabilidad de que sistema se encuentre en algún estado, no depende del estado inicial,

y puede considerarse que es la tendencia del estado al transcurrir mucho tiempo.

En el ejemplo del almacén de cámaras, se observa que ya en la potencia 10 todos los renglones se

parecen, esto implica que sin importar como termine en la semana anterior, dentro de diez semanas solo se

puede decir cuál es la probabilidad que tiene cada uno de los estados posibles.

M10 =

0.67026158 0.18374318 0.11087649 0.03511875

0.67026012 0.18374379 0.1108771 0.03511899

0.67026085 0.18374349 0.11087679 0.03511887

0.67026158 0.18374318 0.11087649 0.03511875 Siempre y cuando la matriz no sea periódica siempre se llega a la situación de que al multiplicarla una

vez más por si misma todos los renglones iguales, ya no cambian.

Sea M la matriz de transición de una cadena de m estados. Existe un vector

m ,,, 21 Llamado distribución de estado estable o distribución de equilibrio tal que

m

m

m

k

k

MLim

21

21

21

)(

En particular

MMMaa

1

mmmm

m

m

m

m

m

m

m

m

ppp

p

p

pp

pp

,2,1,

,2

,1

2,21,2

2,11,1

21

21

21

21

21

21

ppppppmmmm 1,1,221,111,1,221,111

)1(0

ppppppmmmm 2,2,222,112,2,222,112

)1(0 … …

…

UABC FCAyS (795) 18



)1(,,22,11,,22,11 0 ppppppmmmmmmmmmmm

Y, por tratarse de una distribución de probabilidad:

m

211

Hay m+1 ecuaciones y m incógnitas, desechamos una de ellas, ya que las primeras m ecuaciones no

son linealmente independientes y la sustituimos por la propiedad de distribución de probabilidad (los

renglones suman 1, última ecuación), y expresando el sistema de ecuaciones matricialmente tenemos

100

1

1

1

1

1

,2,1,

)1(,1

)1(,1

2,21,2

2,11,1

21

mmmm

m

m

m

ppp

p

p

pp

pp

1

,2,1,

)1(,1

)1(,1

2,21,2

2,11,1

21

1

1

1

1

1

100

mmmm

m

m

m

ppp

p

p

pp

pp

La distribución de probabilidad resultante (el estado estable) es el último renglón de la matriz invertida

En el caso de una Cadena de Markov periódica, no existe esta tendencia, pues fluctúa de estado en

estado, sin embargo al aplicarle el procedimiento anterior se encuentra en la solución la probabilidad de

que el sistema se encuentre en dicho estado. Para el segundo ejemplo periódico se tiene 0.3333333, 0.0333333, 0.3, 0.2166667, 0.1166667 como las probabilidades de que el sistema se encuentre en el

estado 1, 2, 4 y 5, respectivamente, como se hace notar el estado 1 se repite cada tres etapas, estando ahí

1 de cada tres: 1/3 del tiempo.

La programación ®SciLab es la siguiente:

function Mss=MarkovSS(M); Mss=[M-eye(),ones(length(M)^.5,1)]; Mss=inv(Mss(:,2:$)); Mss=Mss($,:);

endfunction

2.12.4.9.3.1. Ejemplos

P =

0.57680992 0.22404181 0.14936121 0.04978707

0.95021293 0.04978707 0 0

0.80085173 0.14936121 0.04978707 0

0.57680992 0.22404181 0.14936121 0.04978707

P-I =

-0.42319008 0.22404181 0.14936121 0.04978707

0.95021293 -0.95021293 0 0

0.80085173 0.14936121 -0.95021293 0

0.57680992 0.22404181 0.14936121 -0.95021293 Sustituyendo la última columna por unos

-0.42319008 0.22404181 0.14936121 1 0.95021293 -0.95021293 0 1

UABC FCAyS (795) 19



0.80085173 0.14936121 -0.95021293 1 0.57680992 0.22404181 0.14936121 1

Invirtiendo la matriz

-1 -8.763E-17 -8.763E-17 1

-0.29461996 -0.85902501 0.1166861 1.03695887

-0.18374333 0.05834304 -0.91736805 1.04276834

0.67026124 0.18374333 0.11087664 0.0351188

Que después de premultiplicar por [0, 0, 0, 1] obtenemos: 0.67026124 0.18374333 0.11087664 0.0351188

2.12.4.9.3.1.1. Ejercicio.

Si

.13533532706706..5939942

01353353..8646647

.1353353.2706706.5939942

M entonces

.1030706.2384058.6585236

.1030706.2384058.6585236

1.1192029.8807971 -.2384058-

101 -

100

1.2706706.5939942

1.8646647 -.8646647

12706706..4060058 -

100

1

321

2.12.4.9.3.1.2. Ejercicio.

3.6.31

32

12.

119.10

__

21

1

21

3

1

3

23

10

3

10

101.2.

11

3.

10

1.2.

11

2.1.

10

8.2.

1.9.

entoncesM

UABC FCAyS (795) 20



2.12.4.9.3.1.3. Ejercicio.

M

3.4.3.

3.5.2.

3.6.1.

1

321

14.3.

115.2.

16.11.

100

3.5.2.

3....49090....20909.

1...0909.1...0909.

1...1818....8181.

100

2.12.4.9.3.1.4. Ejercicio.

Una cola M/M/1/n como se verá en la sección 2.12.5, se puede simular de la siguiente manera:

Cada estado corresponde a la cantidad de clientes en el sistema, siendo los estados diferentes {0,1,…}, en

el que los estados de valores muy grandes se descartan por tener una probabilidad ínfima. La matriz de

estados será:

Según la distribución de probabilidad de Poisson, con esperanza λ las probabilidades de que ocurra un

número de eventos X es de:

!);(

xxP

x

e

La probabilidad de que no arribe nadie es de:

eeP

!0

)0;(

0

La probabilidad de que arribe un cliente (es el complemento de que no llegue ningún cliente) 1-eλ. La

probabilidad de que uno o más clientes sean atendidos es de 1-eµ.

En el estado inicial cuando hay cero clientes en la línea, las flechas que salen del globo 0 deben sumar

1, por lo que la flecha de transición 0,0 tiene una probabilidad de 1-(1-eλ)=eλ.

La capacidad del sistema es para n clientes en la cola, por eso la cadena termina ahí…

ee

eeee

eee

eeeeeee

ee

11

1

111

1

0

1

0

1

1

000

000

000

0

0

0

0

0

0

0

0

0

10

1

0

0 1

n

e-λ

1-e-λ

1-e-µ

e-λ+ e-µ-1 1-e-λ

1-e-µ

e-µ

1-e-µ

n-1

e-λ+ e-µ-1 1-e-λ

UABC FCAyS (795) 21



Para programación en SCILAB:

la=.3; //λ mu=.375;//μ N=256; mt=zeros(N,N); mt(1,1)=exp(-la); mt(1,2)=1-exp(-la); mt(N,N-1)=1-exp(-mu); mt(N,N)=exp(-mu); for k=2:N-1; mt(k,k)=exp(-la)+exp(-mu)-1; mt(k,k-1)=1-exp(-mu); mt(k,k+1)=1-exp(-la); end; M=(mt-eye()); M=[M(:,1:N-1),ones(N,1)]; M=inv(M); M=M(N,:);plot(M) em=M*(0:N-1)'// Cálculo de la esperanza 7.1735632 vm= (M*((-em:N-1-em)').^2)^.5// Cálculo de la Desviación estándar 8.4180513

Conforme a la sección 2.12.4.7 Principales Relaciones,

1825.2

9

75.*75.3

9

)375.3(*75.3

3

)(

22

Lq

2.12.4.9.3.1.5. Ejercicio.

Suponga que toda la industria de refrescos produce dos sodas. Cuando una persona ha comprado la

sabor 1, hay una probabilidad de 90 % de que su siguiente compra se de sabor 1. Si una persona compró

sabor 2, hay un 80 % de probabilidades que su próxima compra sea de sabor 2.

𝑃 = [. 9 . 1. 2 . 8

] [𝜋1𝜋2] = [

. 9 − 1 . 21 1

]−1

∙ [01] = [

−.1 . 21 1

]−1

∙ [01] =

1

−.3[1 −.2−1 −.1

] ∙ [01] = [

23⁄

13⁄]

Por lo tanto, después de largo tiempo, hay probabilidad 2/3 de que una persona dada compre soda 1 y 1/3

de probabilidad de que una persona compre soda 2.

UABC FCAyS (795) 22



2.12.4.9.3.1.6. Ejercicios.

⌈. 1 . 9. 9 . 1

⌉ ⇛≫ [−5

9⁄59⁄

. 5 . 5] ⌈

. 5 . 5

. 9 . 1⌉ ⇛≫ [

−57⁄

57⁄

914⁄

514⁄] ⌈

. 4 . 6

. 9 . 1⌉ ⇛≫ [

−23⁄

23⁄

. 6 . 4]

UABC FCAyS (795) 23



2.12.4.9.4. Tiempo de primer paso

Es la esperanza (o promedio a largo plazo) del número de transiciones que tienen que transcurrir para

pasar del estado i al estado j, por primera vez.

2.12.4.9.5. Recurrencia

Es la esperanza del número de transiciones que tienen que transcurrir para regresar a un estado dado. Es

el tiempo de primer paso de ir del estado i al estado i. Si todos los estados del sistema tienen tiempos

de recurrencia finitos, se dice que es recurrente. Se puede demostrar que es el inverso de πn.

El estado i es Recurrente si ∑ 𝐟𝐢,𝐢(𝐧)= 𝟏∞

𝐧=𝟏 Siempre hay posibilidad de regresar al estado i

es Absorbente si ∑ 𝒑𝐢,𝐢 = 𝟏∞𝐧=𝟏 Una vez que el proceso se encuentra en el estado i no

abandona

es Transitorio si ∑ 𝐟𝐢,𝐢(𝐧)< 𝟏∞

𝐧=𝟏 Una vez que el proceso se encuentra en el estado i existe

una probabilidad >0 de no regresar

2.12.4.9.5.1. Tiempo de primer paso

En una secuencia dada, como, por ejemplo:

s0=1, s1=3, s2=0, s3=2, s4=1, s5=3, s6=2, … ,

el tiempo de primer paso para ir al estado 3 al

estado 1 es de 1 semana, el tiempo de primer

paso para ir del estado 3 al estado 2 es de 2 semanas y el tiempo de recurrencia del estado 3

es de 4 semanas (el tiempo de primera pasada

del estado 3 al estado 3).

Los tiempos de primer paso son variables

aleatorias, que representan el promedio de todos

los tiempos de paso del estado i al estado j. Este

promedio que es la suma de todos los tiempos

posibles multiplicados por su probabilidad se le

llama Esperanza matemática.

Sea fi,jn la probabilidad de que el tiempo de

primera pasada del estado i al estado j sea n.

Si n > 1, entonces el tiempo de primera pasada

es n si la primera transición es del estado i a otro

estado k y el tiempo de pasada del estado

intermedio k a estado j es n-1, estas

probabilidades obedecen a las siguientes

relaciones recursivas:

𝒇𝒊,𝒋(𝟏)= 𝒑𝒊,𝒋

𝟏 = 𝒑𝒊,𝒋

𝒇𝒊,𝒋(𝟐)=∑𝒑𝒊,𝒌

(𝟏)𝒇𝒌,𝒋(𝟏)

𝒌≠𝒋

𝒇𝒊,𝒋(𝟑)=∑𝒑𝒊,𝒌

(𝟏)𝒇𝒌,𝒋(𝟐)

𝒌≠𝒋

⋮

𝒇𝒊,𝒋(𝒏)=∑𝒑𝒊,𝒌

(𝟏)𝒇𝒌,𝒋(𝒏−𝟏)

𝒌≠𝒋

Estas probabilidades satisfacen las siguientes

relaciones recursivas:

𝐟𝐢,𝐣(𝟏)= 𝐩𝐢,𝐣

𝟏 = 𝐩𝐢,𝐣

𝒇𝒊,𝒋(𝟐)= 𝒑𝒊,𝒋

𝟐 − 𝒇𝒊,𝒋(𝟏)𝒑𝒊,𝒋

𝒇𝒊,𝒋(𝟑)= 𝒑𝒊,𝒋

𝟑 − 𝒇𝒊,𝒋(𝟏)𝒑𝒊,𝒋(𝟐)− 𝒇𝒊,𝒋

(𝟐)𝒑𝒊,𝒋

⋮ 𝒇𝒊,𝒋(𝒏)

= 𝒑𝒊,𝒋𝒏 − 𝒇𝒊,𝒋

(𝟏)𝒑𝒊,𝒋(𝒏−𝟏)

− 𝒇𝒊,𝒋(𝟐)𝒑𝒊,𝒋

(𝒏−𝟐)⋯− 𝒇𝒊,𝒋

(𝒏−𝟏)𝒑𝒊,𝒋

𝒇𝒊,𝒋(𝒏)= 𝒑𝒊,𝒋

(𝒏)−∑𝒇𝒊,𝒋

(𝒌)𝒑𝒊,𝒋(𝒏−𝒌)

𝒏−𝟏

𝒌=𝟏

Lo que permite el cálculo recursivo de la

probabilidad del tiempo de primer paso del estado

i al estado j en n pasos, usando como datos las

probabilidades de transición de un paso. En el

ejemplo, la distribución de probabilidad de los

tiempos de primer paso del estado 3 al estado 0 se

obtiene como sigue:

En el ejemplo del almacén de fotografía:

Con λ=1:

𝑴 = [

. 𝟎𝟖 . 𝟏𝟖𝟒. 𝟔𝟑𝟐 . 𝟑𝟔𝟖

. 𝟑𝟔𝟖 . 𝟑𝟔𝟖𝟎 𝟎

. 𝟐𝟔𝟒 . 𝟑𝟔𝟖. 𝟎𝟖 . 𝟏𝟖𝟒

. 𝟑𝟔𝟖 𝟎

. 𝟑𝟔𝟖 . 𝟑𝟔𝟖

]

𝒇𝒊,𝒋(𝟏)= 𝒑𝒊,𝒋

(𝟏)

UABC FCAyS (795) 24



𝒇𝟏,𝟎(𝟏)=. 𝟔𝟑𝟐 𝒇𝟐,𝟎

(𝟏)=. 𝟐𝟔𝟒 𝒇𝟑,𝟎

(𝟏)=. 𝟎𝟖

𝒇𝒊,𝒋(𝟐)=∑𝒑𝒊,𝒌𝒇𝒌,𝒋

(𝟏)

𝒌≠𝒋

𝒇𝟑,𝟎(𝟐)=∑𝒑𝟑,𝒌𝒇𝒌,𝟎

(𝟏)

𝒌≠𝟎

𝒇𝟑,𝟎(𝟐)= 𝒑𝟑,𝟏𝒇𝟏,𝟎

(𝟏)+ 𝒑𝟑,𝟐𝒇𝟐,𝟎

(𝟏)+ 𝒑𝟑,𝟑𝒇𝟑,𝟎

(𝟏)

𝒇𝟑,𝟎(𝟐)=. 𝟏𝟖𝟒 ∗. 𝟔𝟑𝟐+.𝟑𝟔𝟖 ∗. 𝟐𝟔𝟒+.𝟑𝟔𝟖 ∗. 𝟎𝟖 =. 𝟐𝟒𝟑

Que es la probabilidad de pasar del estado 3 al

estado 0 en una pasada y en dos pasadas,

respectivamente.

Para cada transición i,j, las diferentes, tienen las

propiedades:

𝟎 ≤ 𝒇𝒊,𝒋(𝒏)

≤ 𝟏

∑𝒇𝒊,𝒋(𝒏)

≤ 𝟏

∞

𝒏=𝟏

Si esta suma es estrictamente menor que uno

significa que existe una probabilidad de que el

sistema puede nunca alcanzar el estado j desde el

estado i. Si la suma si es 1, entonces se dice que esa

transición es recurrente, y las 𝐟𝐢,𝐣(𝐧)

para toda n,

constituyen una distribución de probabilidad

para la variable aleatoria: tiempo de primera

pasada (la esperanza del número de transiciones

en que el sistema termina en el estado j empezando en el estado i), que se define como

sigue:

𝛍𝐢,𝐣 =

{

∞ 𝐬𝐢 ∑ 𝐟𝐢,𝐣(𝐧)

∞

𝐧=𝟏

<

. . . . . . . . .

𝟏

∑𝐧 𝐟𝐢,𝐣(𝐧)

∞

𝐧=𝟏

𝐬𝐢 ∑ 𝐟𝐢,𝐣(𝐧)

∞

𝐧=𝟏

= 𝟏}

𝒔𝒊 ∑ 𝒇𝒊,𝒋(𝒏)∞

𝒏=𝟏 = 𝟏, 𝝁𝒊,𝒋 satisface

unívocamente la ecuación:

𝛍𝐢,𝐣 = 𝟏 +∑𝐩𝐢,𝐤𝛍𝐤,𝐣𝐤≠𝐣

Cuya primera transición puede ser al estado j (1), o a cualquier otro estado k, si la primera

transición es a un estado diferente a j (k≠j) lo que

ocurre con probabilidad pi,k, sumando todas las

posibilidades.

𝝁𝟑,𝟎 = 𝟏 + 𝒑𝟑,𝟏𝝁𝟏,𝟎 + 𝒑𝟑,𝟐𝝁𝟐,𝟎 + 𝒑𝟑,𝟑𝝁𝟑,𝟎

𝝁𝟐,𝟎 = 𝟏 + 𝒑𝟐,𝟏𝝁𝟏,𝟎 + 𝒑𝟐,𝟐𝝁𝟐,𝟎 + 𝒑𝟐,𝟑𝝁𝟑,𝟎

𝝁𝟏,𝟎 = 𝟏 + 𝒑𝟏,𝟏𝝁𝟏,𝟎 + 𝒑𝟏,𝟐𝝁𝟐,𝟎 + 𝒑𝟏,𝟑𝝁𝟑,𝟎

𝟏 = 𝒑𝟑,𝟏𝝁𝟏,𝟎 + 𝒑𝟑,𝟐𝝁𝟐,𝟎 + 𝒑𝟑,𝟑𝝁𝟑,𝟎 − 𝝁𝟑,𝟎

−𝟏 = 𝒑𝟑,𝟏𝝁𝟏,𝟎 + 𝒑𝟑,𝟐𝝁𝟐,𝟎 + (𝒑𝟑,𝟑 − 𝟏)𝝁𝟑,𝟎

(𝒑𝟏,𝟏−𝟏)𝝁𝟏,𝟎 + 𝒑𝟏,𝟐𝝁𝟐,𝟎+𝒑𝟏,𝟑𝝁𝟑,𝟎 = −𝟏

𝒑𝟐,𝟏𝝁𝟏,𝟎 + (𝒑𝟐,𝟐 − 𝟏)𝝁𝟐,𝟎+𝒑𝟐,𝟑𝝁𝟑,𝟎 = −𝟏

𝒑𝟑,𝟏𝝁𝟏,𝟎 + 𝒑𝟑,𝟐𝝁𝟐,𝟎 + (𝒑𝟑,𝟑 − 𝟏)𝝁𝟑,𝟎 = −𝟏

[

𝒑𝟏,𝟏 − 𝟏 𝒑𝟏,𝟐 𝒑𝟏,𝟑𝒑𝟐,𝟏 𝒑𝟐,𝟐 − 𝟏 𝒑𝟐,𝟑𝒑𝟑,𝟏 𝒑𝟑,𝟐 𝒑𝟑,𝟑 − 𝟏

] ∗ [

𝝁𝟏,𝟎𝝁𝟐,𝟎𝝁𝟑,𝟎

] = [−𝟏−𝟏−𝟏]

([

𝒑𝟏,𝟏 𝒑𝟏,𝟐 𝒑𝟏,𝟑𝒑𝟐,𝟏 𝒑𝟐,𝟐 𝒑𝟐,𝟑𝒑𝟑,𝟏 𝒑𝟑,𝟐 𝒑𝟑,𝟑

] − [𝟏 𝟎 𝟎𝟎 𝟏 𝟎𝟎 𝟎 𝟏

]) ∗ [

𝝁𝟏,𝟎𝝁𝟐,𝟎𝝁𝟑,𝟎

]

= [−𝟏−𝟏−𝟏]

Si agregamos el primer renglón por inducción,

y reordenamos para evitar los signos:

(

[

𝟏 𝟎𝟎 𝟏

𝟎𝟎

𝟎𝟎

𝟎 𝟎 𝟏 𝟎𝟎 𝟎 𝟎 𝟏

] −

[ 𝟎 𝒑𝟎,𝟏𝟎 𝒑𝟏,𝟏

𝒑𝟎,𝟐𝒑𝟏,𝟐

𝒑𝟎,𝟑𝒑𝟏,𝟑

𝟎 𝒑𝟐,𝟏 𝒑𝟐,𝟐 𝒑𝟐,𝟑𝟎 𝒑𝟑,𝟏 𝒑𝟑,𝟐 𝒑𝟑,𝟑]

)

∗ [

𝝁𝟎,𝟎𝝁𝟏,𝟎𝝁𝟐,𝟎𝝁𝟑,𝟎

] = [

𝟏𝟏𝟏𝟏

]

UABC FCAyS (795) 25



Que para despejar, la matriz que premultiplica,

pasa premultiplicando su inversa:

[

𝛍𝟎,𝟎𝛍𝟏,𝟎𝛍𝟐,𝟎𝛍𝟑,𝟎

] =

(

[

𝟏 𝟎𝟎 𝟏

𝟎𝟎

𝟎𝟎

𝟎 𝟎 𝟏 𝟎𝟎 𝟎 𝟎 𝟏

] −

[ 𝟎 𝐩𝟎,𝟏𝟎 𝐩𝟏,𝟏

𝐩𝟎,𝟐𝐩𝟏,𝟐

𝐩𝟎,𝟑𝐩𝟏,𝟑

𝟎 𝐩𝟐,𝟏 𝐩𝟐,𝟐 𝐩𝟐,𝟑𝟎 𝐩𝟑,𝟏 𝐩𝟑,𝟐 𝐩𝟑,𝟑]

)

−𝟏

∗ [

𝟏𝟏𝟏𝟏

]

Y para los demás

[

𝛍𝟎,𝟏𝛍𝟏,𝟏𝛍𝟐,𝟏𝛍𝟑,𝟏

] =

(

[

𝟏 𝟎𝟎 𝟏

𝟎𝟎

𝟎𝟎

𝟎 𝟎 𝟏 𝟎𝟎 𝟎 𝟎 𝟏

] −

[ 𝐩𝟎,𝟎 𝟎

𝐩𝟎,𝟎 𝟎

𝐩𝟎,𝟐𝐩𝟏,𝟐

𝐩𝟎,𝟑𝐩𝟏,𝟑

𝐩𝟎,𝟎 𝟎 𝐩𝟐,𝟐 𝐩𝟐,𝟑𝐩𝟎,𝟎 𝟎 𝐩𝟑,𝟐 𝐩𝟑,𝟑]

)

−𝟏

∗ [

𝟏𝟏𝟏𝟏

]

Etcétera Para el ejemplo que estamos usando, todos los

estados son recurrentes:

𝝁𝟏,𝟎 = 𝟏 + 𝒑𝟏,𝟏𝝁𝟏,𝟎 + 𝒑𝟏,𝟐𝝁𝟐,𝟎 + 𝒑𝟏,𝟑𝝁𝟑,𝟎

𝝁𝟐,𝟎 = 𝟏 + 𝒑𝟐,𝟏𝝁𝟏,𝟎 + 𝒑𝟐,𝟐𝝁𝟐,𝟎 + 𝒑𝟐,𝟑𝝁𝟑,𝟎

𝝁𝟑,𝟎 = 𝟏 + 𝒑𝟑,𝟏𝝁𝟏,𝟎 + 𝒑𝟑,𝟐𝝁𝟐,𝟎 + 𝒑𝟑,𝟑𝝁𝟑,𝟎

𝝁𝟏,𝟎 = 𝟏+. 𝟑𝟔𝟖 𝝁𝟏,𝟎 + 𝟎 𝝁𝟐,𝟎 + 𝟎 𝝁𝟑,𝟎

𝝁𝟐,𝟎 = 𝟏+. 𝟑𝟔𝟖 𝝁𝟏,𝟎+.𝟑𝟔𝟖 𝝁𝟐,𝟎 + 𝟎 𝝁𝟑,𝟎

𝝁𝟑,𝟎 = 𝟏+. 𝟏𝟖𝟒 𝝁𝟏,𝟎+.𝟑𝟔𝟖 𝝁𝟐,𝟎+. 𝟑𝟔𝟖 𝝁𝟑,𝟎

𝝁𝟏,𝟎 = 𝟏+.𝟑𝟔𝟖 𝝁𝟏,𝟎

𝝁𝟏,𝟎 =𝟏

𝟏−. 𝟑𝟔𝟖= 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓

𝝁𝟐,𝟎 = 𝟏+. 𝟑𝟔𝟖 ∗ 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓+.𝟑𝟔𝟖 𝝁𝟐,𝟎

𝝁𝟐,𝟎 = 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓+.𝟑𝟔𝟖 𝝁𝟐,𝟎

𝝁𝟐,𝟎 =𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓

𝟏−. 𝟑𝟔𝟖= 𝟐. 𝟓𝟎𝟑𝟔𝟎𝟓𝟐

𝝁𝟑,𝟎 = 𝟏+. 𝟏𝟖𝟒 ∗ 𝟏. 𝟓𝟖𝟐𝟐𝟕𝟖𝟓+. 𝟑𝟔𝟖∗ 𝟐. 𝟓𝟎𝟑𝟔𝟎𝟓𝟐+.𝟑𝟔𝟖 𝝁𝟑,𝟎

𝝁𝟑,𝟎 = 𝟐. 𝟐𝟏𝟐𝟒𝟔𝟔+.𝟑𝟔𝟖 𝝁𝟑,𝟎

𝝁𝟑,𝟎 =𝟐. 𝟐𝟏𝟐𝟒𝟔𝟔

𝟏−. 𝟑𝟔𝟖= 𝟑. 𝟓𝟎𝟎𝟕𝟑𝟕𝟑

La esperanza para saber cuántos periodos se

han de esperar hasta que el sistema termine con 0

cámaras:

F0= π0μ0,0+ π1μ1,0+ π2μ2,0+ π3μ3,0.

F0= .2856541*3.5007373 + .2848349*1.5822785 + .2631808* .5036052 + .1663302*3.5007373 = 2.6918673

Cada 2.7 semanas se termina con 0 artículos.

Programación Scilab //mi ejemplo con lambda =3

p=[0.57680992 0.22404181 0.14936121 0.04978707; 0.95021293 0.04978707 0 0 ; 0.80085173 0.14936121 0.04978707 0 ; 0.5768 0.2240 0.1493 0.0497];

//Ejemplo del Hillier, mi ejemplo con lambda=1

P=[.08 .184 .368 .368; .632 .368 0 0; .264 .368 .368 0; .08 .184 .368 .368];

//En el cálculo de fij, probabilidad de una pasada de ir del estado i al estado j

for k=1:4; P0=P;P0(:,k)=[0,0,0,0]’;//lambda=1 P0=inv(eye(4,4)-P0)*ones(4,1); U(:,k)=P0;//Columna k de U P0=p;P0(:,k)=[0,0,0,0]’;//lambda=3 P0=inv(eye(4,4)-P0)*ones(4,1); u(:,k)=P0;//Columna k de u end; pp=diag(u)’;PP=diag(U)’; pi=diag(ones(4,4)./u)’;PI=diag(ones(4,4)./U)’;

Resultados Scilab pp = 1.4919556 4.675136 8.2737728 28.47478

1.0523957 5.4423746 9.3261685 29.527175 1.2178187 4.9926607 9.0190331 29.692599 1.4919556 4.675136 8.2737728 28.47478

PP = 3.5007373 3.9727943 3.5085305 6.0121357 1.5822785 3.510806 5.090809 7.5944142 2.5036052 3.2418002 3.7996698 8.5157409 3.5007373 3.9727943 3.5085305 6.0121357

u =1.4919556 5.4423746 9.0190331 28.47478 U =3.5007373 3.510806 3.7996698 6.0121357 pi =0.6702612 0.1837433 0.1108766 0.0351188 PI =0.2856541 0.2848349 0.2631808 0.1663302

2.12.4.9.6. Cadenas Periódicas

Se llama así a la cadena que al cabo de algunos

pasos regresa al mismo estado. El número de

pasos que tarda en repetirse se llama periodo.

A continuación se muestra la matriz de

transición de una Cadena de Markov de periodo

igual a dos.

UABC FCAyS (795) 26



𝑀 = [0 . 1 . 91 0 01 0 0

] 𝑀2 = [1 0 00 . 1 . 90 . 1 . 9

]

𝑀3 = [0 . 1 . 91 0 01 0 0

] . . .

Aquí se muestra una cadena de periodo de tres

𝐵 =

[ 0 . 1 . 9 0 00 0 0 . 2 . 8011

000

0 . 7 . 30 0 00 0 0 ]

𝐵2 =

[ 0 0 0 . 65 . 351 0 0 0 0100

0. 1. 1

0 0 0. 9 0 0. 9 0 0 ]

𝐵3 =

[ 1 0 0 0 00 . 1 . 9 0 0000

. 100

. 9 0 00 . 65 . 350 . 65 . 35]

𝐵4 =

[ 0 . 1 . 9 0 00 0 0 . 2 . 8011

000

0 . 7 . 30 0 00 0 0 ]

2.12.4.9.7. Estados Absorbentes

Un estado de una cadena de Markov se le

denomina absorbente si es imposible

abandonarlo. Una cadena de Markov se dice

absorbente si tiene al menos un estado absorbente

accesible desde cualquier estado. Un estado que

no es absorbente se dice que es transitorio.

2.12.4.9.7.1. Ejemplo

El camino de Briagoberto Un borracho solo camina a lo largo de la calle

Ruiz. Él vive en la esquina Ruiz y Boulevard

Costero y la cantina está en la calle 4.

En cualquier esquina su desorientación es tal

que puede caminar hacia el Oeste o hacia el Este

con la misma probabilidad. Si llega a su casa su

vieja lo retiene y lo acuesta a dormir. Si llega al

bar, se embriaga de tal modo que se queda tirado

ahí.

La matriz de transición es la siguiente, con

estados absorbentes en 0 y en 4:

P =

0 1 2 3 4 0 1 0 0 0 0 1 ½ 0 ½ 0 0 2 0 ½ 0 ½ 0

3 0 0 ½ 0 ½ 4 0 0 0 0 1

Los estados 1, 2 y 3 son estados transitorios y los

estados 0 y 4 son estados absorbentes.

¿Cual es la probabilidad de que eventualmente

termine en un estado absorbente?

¿En promedio, cuanto tiempo vagará antes de

permanecer en alguno de los estados absorbentes?

¿Cuál es la esperanza de encontrarlo en cada

esquina?

La respuesta a estas preguntas depende, en

general, del estado en que el proceso empieza, así

como de las probabilidades de transición.

Este es un ejemplo de una matriz de transición

absorbente,

m=[ .98 .01 0 .01 0 0 0 0 0 .25 .25 .25 0 .25 0 0 0 0 0 1/3 1/3 0 0 1/3 0 0 0 .25 0 0 .25 .25 0 .25 0 0 0 .2 0 .2 .2 .2 0 .2 0 0 0 .25 0 .25 .25 0 0 .25 0 0 0 1/3 0 0 1/3 1/3 0 0 0 0 0 .25 0 .25 .25 .25 0 0 0 0 0 .01 0 .01 .98 ]

UABC FCAyS (795) 27



2.12.4.9.7.2. Forma Canónica

Considérese una cadena de Markov absorbente.

Renumeramos sus estados para que los estados

transiente estén al principio. Si hay r estados

absorbentes y t estados transiente, la matriz de

transición tendrá la siguiente forma canónica:

CONSIDERAR UNA SUBMATRIZ

ABSORBENTE.

En la que I es una matriz identidad n*n, 0 es

una matriz r*t de ceros y Q es una matriz t*t. Los primeros t estados son transiente y los

últimos r estados son absorbentes.

In Section 11.1, we saw that the entry p(n)

ij of

the matrix Pn is the probability of being in the

state sj after n steps, when the chain is started in

state si. A standard matrix algebra argument

shows that Pn is of the form

where the asterisk ∗ stands for the t-by-r matrix

in the upper right-hand corner of Pn. (This

submatrix can be written in terms of Q and R, but

the expression is complicated and is not needed at

this time.) The form of Pn shows that the entries

of Qn give the probabilities for being in each of

the transient states after n steps for each possible

transient starting state. For our first theorem, we

prove that the probability of being in the transient

states after n steps approaches zero. Thus, every

entry of Qn must approach zero as n approaches

infinity (i.e, Qn → 0).

2.12.4.9.7.3. The Fundamental

Matrix Theorem 11.4 For an absorbing Markov chain

the matrix I − Q has an inverse N and N = I + Q +

Q2 + · · · . The ij-entry nij of the matrix N is the

expected number of times the chain is in state sj ,

given that it starts in state si. The initial state is

counted if i = j.

Definition 11.3 For an absorbing Markov chain

P, the matrix N = (I − Q)−1 is called the

fundamental matrix for P. The entry nij of N

gives the expected number of times that the

process is in the transient state sj if it is started in

the transient state si.

Example 11.14 (Example 11.13

continued) In the Drunkard’s Walk examp transition

matrix in canonical form is

P =

. 1 2 3 0 4

1 0 ½ 0 ½ 0

2 ½ 0 ½ 0 0

3 0 ½ 0 0 ½

0 0 0 0 1 0

4 0 0 0 0 1

From this we see that the matrix Q is

Q=

0 ½ 0

½ 0 ½

0 ½ 0 and

I − Q =

1 −1/2 0

−1/2 1 −1/2

0 −1/2 1 Computing (I − Q)−1, we find

N = (I − Q)−1 =

1 2 3

1 3/2 1 ½

2 1 2 1

3 ½ 1 3/2

From the middle row of N, we see that if we

start in state 2, then the expected number of times

in states 1, 2, and 3 before being absorbed are 1,

2, and 1. 2 .

UABC FCAyS (795) 28



2.12.4.9.7.4. Probabilidad de

Absorción Teorema: En una cadena de Markov la

probabilidad de que el proceso sea absorbido es

1. (siempre y cuando todos los estados sean

alcanzables y exista al menos una subcadena

absorbente.

Theorem 11.3 In an absorbing Markov chain,

the probability that the process will be absorbed

is 1 (i.e., Qn → 0 as n → ∞).

2.12.4.9.7.5. Time to Absorption

We now consider the question: Given that the

chain starts in state si, what is the expected

number of steps before the chain is absorbed?

The answer is given in the next theorem.

Theorem 11.5 Let ti be the expected number of

steps before the chain is absorbed, given that the

chain starts in state si, and let t be the column

vector whose ith entry is ti. Then

t = Nc ,

where c is a column vector all of whose

entries are 1.

2.12.4.9.7.6. Absorption

Probabilities Theorem 11.6 Let bij be the probability that an

absorbing chain will be absorbed in the absorbing

state sj if it starts in the transient state si. Let B be

the matrix with entries bij . Then B is an t-by-r

matrix, and

B = NR ,

where N is the fundamental matrix and R is

as in the canonical form.

Example 11.15 (Example 11.14

continued) In the Drunkard’s Walk example, we found that

N =

N=

3/2 1 ½

1 2 1

½ 1 3/2

Hence,

t=Nc

3/2 1 ½

*

1

=

3

1 2 1 1 1

½ 1 3/2 1 3

2.12.4.9.8. Costos

2.12.4.10. Paquete

computacional QSA,QSB,

2.12.4.11. Ejercicios de Aplicación

UABC FCAyS (795) 29



2.12.4.12. Bibliografía

[

1]

F. S. Hillier y G. J. Lieberman, Investigación de Operaciones, 7a ed., México DF,

DF: McGraw-Hill, 2002.

[

2]

D. R. Anderson, D. J. Sweeney y T. A. Williams, Introducción a los Modelos

Cuantitativos para Administración, 3a ed., DF, México: Grupo Editorial

Iberoamericano, 1993.

[

3]

J. Norris, «Markov Chains,» University of Cambridge, Mayo 2012. [En línea].

Available: http://www.statslab.cam.ac.uk/~james/Markov/. [Último acceso: 06

Mayo 2014].

2.12.5. Apéndice

2.12.5.1. Cadena de Ehrenfest

Modela el intercambio de moléculas de gas entre dos urnas.

Supongamos que tenemos dos urnas: U1 y U2. En ellas están distribuidas d bolas

numeradas; en cada paso, se elige un número al azar entre S={1, 2, ... , d}. A

continuación se observa en qué urna está la bola con el número elegido y se cambia de

urna.

2.12.5.1.1. Modelo Ehrenfest

Definimos la variable aleatoria Xn que denota el número de bolas en la urna U1 al

tiempo n, el espacio de estados es E={0, 1, 2, … ,d} y la matriz de transición definida por

𝐏𝐱,𝐲 =

{

𝐱𝐝⁄ 𝐬𝐢 (𝐱 > 𝟎, 𝐲 = 𝐱 − 𝟏)

(𝐝 − 𝐱)𝐝⁄ 𝐬𝐢(𝐱 < 𝐝, 𝐲 = 𝐱 + 𝟏)

𝟎 𝐨𝐭𝐫𝐚 𝐜𝐨𝐧𝐝𝐢𝐜𝐢ó𝐧 }

2.12.5.1.1.1. Ejemplo

Para 3 bolas: 3=d E={0,1,2,3)

y x

0 1 2 3

0

0/3 si 0>0, 2=0-1 (3-0)/3 si 0<3 0=0+1 0 otra Condición




1





2





3





UABC FCAyS (795) 30



y x

0 1 2 3

0 0 1 0 0 1 1/3 0 2/3 0 2 0 2/3 0 1/3 3 0 0 1 0

2.12.5.2. The Bernoulli-Laplace Chain

The Bernoulli-Laplace chain, named for Jacob Bernoulli and Pierre Simon Laplace, is a simple

discrete model for the diffusion of two incompressible gases between two containers. Like

the Ehrenfest chain, it can also be formulated as a simple ball and urn model. Thus, suppose that

we have two urns, labeled 0 and 1. Urn 0 contains j balls and urn 1 contains k balls,

where j,k∈N+. Of the j+k balls,r are red and the remaining j+k−r are green. At each discrete

time, independently of the past, a ball is selected at random from each urn and then the two balls

are switched. The balls of different colors correspond to molecules of different types, and the

urns are the containers. The incompressible property is reflected in the fact that the number of

balls in each urn remains constant over time.

Let Xn denote the number of red balls in urn 1 at time n∈N. Note that

a. k−Xn is the number of green balls in urn 1 at time n.

b. r−Xn is the number of red balls in urn 0 at time n.

c. j−r+Xn is the number of green balls in urn 0 at time n.

X=(X0,X1,X2,…) is a Markov chain on the state space S={max{0,r−j},…,min{k,r}} with the

transition probability matrix P given by

P(x,x−1)=(j−r+x)xjk,P(x,x)=(r−x)x+(j−r+x)(k−x)jk,P(x,x+1)=(r−x)(k−x)jk;x∈S

Consider the special case j=k, so that each container has the same number of particles. The state

space is S={max{0,r−k},…,min{k,r}} and the transition probability matrix is

P(x,x−1)=(k−r+x)xk2,P(x,x)=(r−x)x+(k−r+x)(k−x)k2,P(x,x+1)=(r−x)(k−x)k2;x∈S

Consider the special case j=k=r, so that each container has the same number of particles, and

this is also the number of type 1 particles. The state space is S={0,1,…,k} and the transition

probability matrix is

P(x,x−1)=x2k2,P(x,x)=2x(k−x)k2,P(x,x+1)=(k−x)2k2;x∈S

http://www.math.uah.edu/stat/markov/Ehrenfest.html

http://www.math.uah.edu/stat/markov/Introduction.html

UABC FCAyS (795) 31



Consider the Bernoulli-Laplace chain with j=10, k=5, and r=4. Suppose that X0 has the uniform

distribution on S.

a. Explicitly give the transition probability function in matrix form.

b. Compute the probability density function, mean and variance of X1.

c. Compute the probability density function, mean and variance of X2.

d. Compute the probability density function, mean and variance of X3.

e. Sketch the initial probability density function and the probability density functions in

parts (a), (b), and (c) on a common set of axes.

Answer:

Run the simulation of the Bernoulli-Laplace experiment for 10000 steps and for various values

of the parameters. Note the limiting behavior of the proportion of time spent in each state.

2.12.5.2.1. Invariant and Limiting Distributions

The Bernoulli-Laplace chain is irreducible and aperiodic.

The invariant distribution is the hypergeometric distribution with population parameter j+k,

sample parameter k, and type parameter r. The probability density function is

f(x)=(rx)(j+k−rk−x)(j+kk),x∈S

Thus, the invariant distribution corresponds to selecting a sample of k balls at random and

without replacement from the j+k balls and placing them in urn 1.

The mean return time to each state x∈S is

μ(x)=(j+kk)(rx)(j+k−rk−x)

Pn(x,y)→f(y)=(ry)(r+k−rk−y)/(j+kk) as n→∞ for (x,y)∈S2.

In the simulation of the Bernoulli-Laplace experiment, vary the parameters and note the shape

and location of the limiting hypergeometric distribution. For selected values of the

parameters, run the simulation for 10000 steps and and note the limiting behavior of the

proportion of time spent in each state.

2.12.5.2.2. Reversibility

The Bernoulli-Laplace chain is reversible.

Run the simulation of the Bernoulli-Laplace experiment 10,000 time steps for selected values of

the parameters, and with initial state 0. Note that at first, you can see the arrow of time. After

a long period, however, the direction of time is no longer evident.

http://www.math.uah.edu/stat/markov/Recurrence.html

http://www.math.uah.edu/stat/markov/Periodicity.html

http://www.math.uah.edu/stat/markov/Limiting.html

http://www.math.uah.edu/stat/urn/Hypergeometric.html

http://www.math.uah.edu/stat/markov/TimeReversal.html

lecturas-cadenas de markov

Documents