Descargue el artículo completo dando clic AQUÍ

Estado del arte y propuesta de tema
Página 1 de 7
Estado de Arte sobre las Cadenas Ergódicas de Markov __________________
Por: Ing. David Alberto Rojas Rodríguez 1
Resumen: Procesos de Markov, específicamente las cadenas ergódicas son una matriz de resolución de
problemas de toda índole industrial, cotidiana, servicios, entre otras, en donde cada cadena (tema en estudio)
y sus entradas (características, variables, etc.) cumplen tres requisitos primordiales, a saber, sus estados o
entradas deben ser irreductibles, positivamente recurrentes y aperiódicas, sólo así se podrá llamar y utilizar como
ergódica. La aplicación de las cadenas ergódicas trabaja con probabilidades discretas y cubren campos en
donde se quiere investigar el comportamiento de un evento, que depende del evento inmediatamente anterior
a éste. Esto porque la memoria de las cadenas ergódicas de Markov sólo permite ir un eslabón atrás, es decir si
el estado actual es n, se puede ir a n+1 e inclusive regresar a ese estado. Esta propiedad se convierte en una
limitante de la teoría cuando se necesita trabajar con eventos y proyectarlos hacia el futuro o ir a periodos
pasados, debido a que paulatinamente se perderá conocimiento valioso y el grado de probabilidad obtenido
finalmente, estará caracterizado por un alto sesgo estadístico. Así como el efecto látigo afecta los eventos a
medida que crecen en el tiempo a razón de n+1 sin tener un claro horizonte de donde debe detenerse.
Palabras clave: Cadenas ergódicas, irreductible, aperiódica, recurrente.
I.
Marco Teórico
Según lo menciona Hillier & G. Lieberman, una cadena
de Markov es ergódica si todos sus estados son no nulos,
no periódicos y recurrentes.
Para que una cadena de eventos sea ergódicos deben
cumplir una propiedad primordial; el límite lim n  0 Pij( n )
existe y es independiente del estado inicial i. Lo
denominaremos  j :
j
de i a j. Si es posible el tránsito en ambos sentidos,
entonces los dos estados están comunicados.
Por ejemplo se tienen los estados 1 y 2, los cuales están
comunicados. Además 1, 2 y 3 son accesibles desde 0,
pero este último no es accesible desde ningún otro
estado.
Ilustración 1: Diagrama de estados iniciales
 lim n 0 Pij( n )

j
Las
probabilidades
límites
se
denominan
probabilidades de estado estable. Si los límites anteriores
existen, entonces:
lim n (
1
N
n
P
(k )
ij
) j
k 1
La aplicación de las Cadenas de Markov abarcan
sistemas de producción y procesos estadísticos de toda
naturaleza, sin embargo las Cadenas que son Ergódicas
tienen un área de influencia establecida, caracterizada
por factores propios de su aplicación, lo cual se
evidencia mediante el estudio del estado del arte.
Por otra parte en su libro sobre Teoría Elemental de la
Probabilidad y de los Procesos Estocásticos, el físico Kai
Lai Chung se refiere a que una Cadena de Markov es
ergódica si y sólo si es irreductible, positivamente
recurrente y aperiódica. El teorema de Chung define de
manera concisa las propiedades descritas. El término
Cadenas irreductibles según Chung, se refiere a que el
estado j es accesible desde el i si es posible transitar
desde i a j en un número finito de pasos, es decir, si
pij(n)>0 para algún n. Esto equivale a decir que existe,
sobre el diagrama de transición, algún camino que lleva
1
Profesor Universidad Técnica Nacional
Cuando un subconjunto de estados es tal que todos
ellos están comunicados unos con otros se dice que
dicho subconjunto constituye una clase comunicante.
Estas clases deben ser además conjuntos maximales, lo
que implica que cada estado sólo puede estar en una
clase y que dos estados que comunican deben estar
siempre en la misma clase. En el ejemplo anterior hay
dos clases comunicantes, una formada por los estados 1
y 2, y otra por el estado 3. Para que una cadena sea
irreducible se debe cumplir que todos sus estados se
comuniquen unos con otros, es decir, si están todos
contenidos en una única clase comunicante.
El físico Lai Chung define las Cadenas recurrentes, como
aquellas en las que cuando se tiene un estado i, se tiene
la probabilidad de volver en algún momento a dicho
estado. Se dice que el estado i es recurrente si fi=1 y que
es transitorio si fi<1. Es decir, un estado es transitorio si,
estando en él, existe la posibilidad de salir y no volver a
pasar por él.
Estado del arte y propuesta de tema
Página 2 de 7
Por ejemplo en el escenario de la Ilustración #1, sobre
los estados de la cadena 0, 1, 2 y 3; los estados 1, 2 y 3
son recurrentes, el 0 es un estado transitorio.
Es importante tener en consideración que todos los
estados en una misma clase comunicante son del
mismo
tipo,
recurrentes
o
transitorios.
Como
consecuencia, en una cadena finita e irreducible todos
los estados serán recurrentes.
Ejemplo de aplicación #1: En el proceso binomial todos
los estados son transitorios. Sin embargo, se puede
demostrar que en un paseo aleatorio simétrico todos los
estados son recurrentes, si bien dejan de serlo si el paseo
no es simétrico. Entonces suponga que la cadena está
en este momento en un estado recurrente i. Se sabe
entonces que tarde o temprano la cadena volvería a
dicho estado con probabilidad 1. Ahora se debe
estudiar la variable Ti tiempo que se tarda en volver al
estado i. En particular es importante conocer la
esperanza matemática de esta variable, E[Ti] (lo cual
puede no ser fácil). Cuando dicha esperanza es finita
entonces el estado es positivamente recurrente. Así
mismo la cadena es positivamente recurrente cuando
todos sus estados también lo son.
Observación relevante #1: Toda cadena finita y
recurrente es positivamente recurrente.
Cadenas aperiódicas: Al tener un estado recurrente i, la
cadena volvería a pasar por i infinitas veces. La
información sobre los instantes en que esto puede
ocurrir viene dada por pii(n), que representa la
probabilidad de que se vuelva a él en n pasos.
Ejemplo de aplicación #2: La siguiente cadena es
periódica con periodo d=3:
Ilustración 2: Ejemplo de aplicación #2
Ilustración 3: Ejemplo de aplicación #3
Por tanto se tiene ya una serie de ideas para reconocer
cuando se está ante una cadena ergódica. En este tipo
de cadenas ocurre que:
lim n   P ( n )  1T 
Lo cual implica:
lim n   p (n)  lim n   p (0) P ( n )  p (0)1T   
Ya que
p(0)1T  1
Observación relevante #3: si P tiene dimensión finita y no
contiene ceros, la cadena de Markov asociada será
ergódica.
II.Acerca del proceso
Para conceptualizar el campo de estudio específico, es
primordial realizar una investigación acerca de sucesos
pasados que se relacionen en contexto y forma,
además
de
conocer
previas
investigaciones,
metodologías y sobre todo alcances obtenidos con el
tema en estudio. El objetivo de este estado del arte es
informarse acerca del conocimiento que existe respecto
al tema (cadenas ergódicas), esto será una base para
darle la dirección correcta a la investigación. Cuando
es exhaustivo el proceso, se genera conocimiento
importante que lleva a plasmar los resultados de
manera más concisa, razón que lleva al investigador a
recopilar documentos interdisciplinarios que converjan
en el tema tratado.
III.Investigaciones relacionadas al tema tratado
Las Cadenas Ergódicas de Markov, surgen en el año de
1907, cuando el matemático ruso Andrei Andreevitch
Markov realiza su investigación sobre teorías de
probabilidades.
Observación relevante #2: Nótese que todos los estados
en una misma clase comunicante tendrán siempre el
mismo periodo, por tanto, cuando existe una cadena
irreducible se puede calcular el periodo de dicha
cadena, o sea que una cadena irreducible es
aperiódica cuando sus estados tienen periodo d=1.
Ejemplo de aplicación #3. La siguiente cadena es
aperiódica:
Existe un amplio rango o campos de aplicación de las
cadenas ergódicas de Markov, a saber, se pueden
utilizar para procesos de negocios, donde se utilizan
para analizar patrones de compra de los clientes y de
sus deudores morosos, ayudan en la planeación de
necesidades de personal y en la industria son
manipuladas para analizar la necesidad del remplazo
de equipos, campo concerniente a la investigación de
Estado del arte y propuesta de tema
Página 3 de 7
donde la entrada j,i es Pij(inf)=Lim ninfinito Pijn ,
pero como Pij(inf)=Pii(inf) se concluye que la matriz
M(infinita) tiene sus columnas iguales, esto es de la
forma :
operaciones pero observada desde otra arista de
resolución. Además en ciencias exactas como en el
campo de la física, ingeniería, biología, medicina y
matemáticas, inclusive.
La investigación y aplicación de las cadenas ergódicas
de Markov están determinadas por la aplicación de sus
límites dentro del campo estadístico, según lo plantea
Restrepo y Ossa en su tesis sobre Investigación de
Operaciones y Estadística, donde se encuentran
plasmadas las condiciones necesarias para tener una
cadena ergódica, con una condición suficiente, si existe
un n>0 tal que Pijn >0, donde i, j=0,1,2....m. la cadena de
Markov, con esta propiedad, se llama ergódica.
n
Entonces, Pij
y como

  k  0 ( Pikn * Pkj ) ,
luego  j 
P  1 , entonces 
n
j  0 ij
j 0

k 0
(k * Pkj )
Ilustración 4: matriz M(infinita)
2.
 j 1
Teorema #1: Para una cadena de Markov ergódica,
 j  Lim n  Pijn existe
y
j
( j pertenece0,...m) es la
única solución no negativa de
 j . Entonces:
 j   k  0 (k * Pkj ) y 
asintótico
de
Pn,
es
decir
Lim n Pn entonces el
problema es encontrar las condiciones para que este
límite exista y en caso de existir, surge la incógnita
¿dependerá del estado inicial del sistema? Bajo
condiciones de “regularidad” la distribución asintótica
existe y bajo estas condiciones la distribución en el límite
será independiente de la distribución inicial.
Teorema básico del límite para cadenas de Markov: En
una cadena de Markov recurrente
irreducible y
aperiódica se tiene que:
1
Lim ninfinito Piin =
Σinfn=1 n fiin
Siendo fii la probabilidad de que el proceso regrese al
estado i dado que comienza en el estado i. Y además
Lim n Pijn  Lim n Pijn .Del
Ahora si Limninfinito(Piin=π=0) y la clase es
j 0 j  1
El entendimiento de los límites ergódicos en las cadenas
de Markov es fundamental para establecer hasta
donde se extiende el campo de estudio en tiempo y
espacio, es decir que la necesidad de conceptualizar
los estados y su relación es fundamental en las cadenas
y está dado por Pn =Mn P0. Y si existe un comportamiento
teorema se pueden sacar
fuertes conclusiones:
1. Si M=Pij es la matriz de transición de una cadena
de Markov, y suponiendo que esta cadena es
recurrente, irreducible y aperiódica, se
garantiza la existencia de la matriz M(infinita)
Sea C una cadena irreducible y recurrente,
entonces Pijn=0 para i pertenece a C y j no
pertenece a C dado n. Esto es, toda vez que
entremos en C no es posible abandonarlo,
luego la matriz Pij con i,j perteneciendo a C
estará asociada a una cadena de Markov
irreducible y recurrente luego el teorema básico
es aplicable si la clase resulta ser aperiódica.
recurrente se dirá entonces que la clase es
débilmente ergódica o nula recurrente.
El valor
Σinfn=1(n fiin=mi). Se define como el tiempo medio
de recurrencia del estado i. Ahora se asegura, sin
demostración, que bajo las condiciones de regularidad
del teorema anterior, que Lim ninfinito Piin=1/mi=πi.
Teorema#2: En una clase aperiódica positiva recurrente
con estados i=0, 1,2,…, n; Se tiene que:
inf
Lim n Piin   i   inf
k  0 k ; k  o k  1
(1)
Cualquier conjunto
i que satisfaga (1) se llama
probabilidad de distribución estacionaria de la cadena
de Markov.
Observe que si Pij es la matriz de transición asociada a
una clase recurrente ergódica positiva, entonces la
ecuación  i 

inf
k 0
kPkjk
llevada
a
matricial es:
Ilustración 5: =Forma Matricial de πi
su
forma
Estado del arte y propuesta de tema
Página 4 de 7
Establece claramente que (π1, π2, π3.....)t es un auto
vector (a la derecha) de la matriz Pij asociado al auto
valor 1. Para esto se debe entender que la matriz de
Markov tiene un auto valor igual a 1, más aún, este valor
será el mayor, en valor absoluto, si la matriz es primitiva,
esto es si todas sus entradas son positivas para alguna
potencia de la matriz.
La aplicación de una Cadena Ergódica a los problemas
más comunes que existen en el entorno cotidiano, se
puede observar en la tesis doctoral de Moreno Díaz,
sobre los Modelos Multivariables para Variables
Ordinales: Aplicaciones en Estudios de Calidad del
Servicio, en la misma Moreno Díaz define tres conceptos
primordiales para iniciar una aplicación de Markov de
este tipo, para Díaz una Cadena es Ergódica si todos los
estados de una Cadena de Markov son recurrentes,
aperiódicos y se comunican entre sí. Mientras que
define un estado recurrente como el estado i, si fii=1.
Esto significa que siempre que parta del estado i, se
podrá regresar a él (en un tiempo finito). Siguiendo la
misma filosofía ergódica se puntualiza el estado
periódico cuando existe un estado recurrente i, con
periodo k>1, si k es el menor número tal que todas las
trayectoria que parte de i y regresan a i, tienen longitud
múltiplo de k. Si no es periódico se le dice aperiódico.
Ejemplo de aplicación #4: En un modelo para el
desplazamiento poblacional, para efectos de una
investigación, en un determinado país, una familia
puede clasificarse como habitante de zona urbana,
rural o suburbana. Se ha estimado que durante un año
cualquiera, el 15% de todas las familias urbanas se
cambian a zona suburbana y el 5% a zona rural. El 6% de
las familias suburbanas pasan a zona urbana y el 4% a
zona rural. El 4% de las familias rurales pasan a zona
urbana y el 6% a zona suburbana.
Pregunta interesante: ¿Existe una probabilidad límite de
que el sistema se encuentre en el estado j, después de
muchas transiciones, y que esta probabilidad sea
independiente del estado inicial?
Afirmación: Si P es la matriz de transición de una
Cadena de Markov que tiene los estados {1,2,...k},
entonces, para j=1,2,.., k:
lim n Pi ,( nj )   j
Escrito de otra forma:
1  2 . . .  k
1  2 . . .  k
lim lim P n  . .
n 
..
...
...
... ...
a)  j  0
k
b)  j    i Pi , j
esto es  t   t
i 1
k
c )  j  1
j 1
Dado que la matriz del ejemplo 3 es ergódica, se tiene
que:
 0,80

( 1 ,  2 ,  3 )  ( 1 ,  2 ,  3 ) 0,06
 0,04

0,05 

0,90 0,04 
0,06 0,90 
0,15
1   2   3  1
Una opción es:
 1  0,80 1  0,06 2  0,04 3
 2  0,15 1  0,90 2  0,06 3
1  1   2   3
Cuya solución es:
( 1 ,  2 ,  3 )  (0.2077 , 0.4918 , 0.3005 )
Es decir, si con el paso del tiempo se mantiene el
comportamiento descrito por el modelo (lo cual es muy
poco
probable)
después
de
muchos
años,
aproximadamente, el 21% de la población ocupará las
zonas urbanas, el 49% las zonas suburbanas y el 30% la
rural.
La filosofía de las cadenas ergódicas se ve expuesta en
la tesis de Ciencias y Telecomunicaciones del Ing.
Blasco, tomando un escenario donde hay una cadena
estacionaria, con una distribución inicial p(0)=¼.
Considerando una distribución inicial distinta la cadena
deja de ser estacionaria, sin embargo presenta un
comportamiento muy interesante ya que, a largo plazo,
cuando pasa mucho tiempo, se alcanza una
distribución estacionaria que además resulta ser ¼, es
decir:
Lim n P(n)  
De hecho, esta distribución estacionaria es siempre la
misma independientemente de cuál haya sido la
distribución inicial. Cuando una cadena de Markov se
comporta de esta manera, necesariamente es una
cadena ergódica. El siguiente resultado permite
reconocer cuando una cadena tiene esta propiedad:
Teorema #3: Una cadena de Markov es ergódica si y
sólo si es irreducible, positivamente recurrente y
aperiódica.
1  2 . . .  k
Para obtener los
 j se tiene presente las ecuaciones
de estado estable:
IV.Conclusiones y recomendaciones para el
planteamiento de investigaciones futuras
Estado del arte y propuesta de tema
1) La aplicación de las cadenas de Markov y
propiamente las cadenas ergódicas se ha hecho desde
hace más de un siglo y su vigencia a la actualidad sigue
siendo de aplicación real en procesos industriales,
médicos, comerciales, académicos, meteorológicos,
entre otros muchos. Se vuelve aún más interesante el
factor de que la teoría no ha cambiado en su
conceptualización y sigue aplicando igualmente para
cualquier campo cuantitativo de estudio.
2) Independientemente del contexto de aplicación de
las cadenas ergódicas, la asignación de las
probabilidades y datos recopilados, el método siempre
es el mismo para la resolución de un problema.
3) Las cadenas de Markov son mecanismos que
ayudan a solventar necesidades creadas en las
personas por falta de conocimiento de los eventos
futuros en donde la información recolectada no es un
buen punto de referencia debido a la variabilidad de
los procesos y los sesgos en la recolección de datos; por
lo tanto el estudio de eventos anteriores de manera
inmediata origina panoramas realistas y aplicables, con
estados originales y probabilidades de 1.
4) Los procesos estocásticos “reviven” eventos para
colocar al investigador en un presente inmediato, de
esta manera puede enterarse antes de continuar con
los procesos de recolección de datos si en realidad está
en el espacio y tiempo correctos o si en contraposición
necesita de nuevas guías que lo orienten hacia las
repuestas que necesita para solventar sus objetivos de
investigación.
5) Como toda herramienta metodológica las cadenas
de Markov presentan resultados que ayudan a aclarar
el panorama hacia una determinada situación, sin
embargo es el investigador que basado en esa
información de verá concluir y tomar las decisiones
atinadas que beneficien o refuten de manera
satisfactoria las pruebas.
6) La flexibilidad de las cadenas de Markov permiten
realizar estudios en ambientes hostiles desde el punto de
vista de recolección de datos o metodologías que se
adecuen a los objetivos del proyecto, esto porque no se
necesitan grandes historiales de información, ya que el
presente es necesario para justificar acciones futuras y
realistas.
V.
Propuesta del tema y justificación
Una cadena de Markov se puede caracterizar por la
probabilidad de ir al estado n+1 condicionada a que
antes se encontraba en el estado n:
P( X n 1 / X n )
Que es la probabilidad de transición del proceso, la
propiedad de las cadenas de Markov es que las
Página 5 de 7
transiciones entre los estados, sólo pueden producirse
entre estados vecinos, dicho de otra manera, sólo se
puede llegar del estado n al estado n+1 ó n-1.
Las cadenas de Markov al trabajar con poblaciones
asumen la homogeneidad de las mismas, o sea que un
cambio o una estructuración por conglomerados o
subdivisiones hace que el resultado de cada uno venga
precedido por el general al obtenido por Markov
(tomado como cadena ergódica), esto genera un
“conflicto matemático” porque al realizar nuevos
cambios en la población, la data anterior pierde validez
y veracidad, o sea se convierte en un error irrevertible
en los resultados, sesgando por completo el estudio.
Si no se detecta este tipo de problemas en los estudios
basados en las cadenas ergódicas muchos datos
erróneos serán base para toma de decisiones
importantes de gran impacto. Si a esta misma población
se le aplica un estudio similar bajo la misma línea
teórica, entonces se obtendrán resultados diferentes e
inclusive veraces, por ejemplo un estudio de
investigación de operaciones sobre la asignación de
rutas en la distribución logística de una empresa versus
el estudio de Markov sobre los estados actuales y futuros
de la misma distribución logística.
Las cadenas de Markov al trabajar con poblaciones
asumen la homogeneidad de las mismas. Cuando se da
un efecto de látigo en una población cada una de los
estados involucrados sufre un efecto en incremento o
decremento de una variable específica. Markov no
detecta esa variabilidad mediante su estudio, es decir
que las cadenas ergódicas a pesar de ser precisas en
sus resultados, el investigador debe asumir el riesgo de
fallar en las probabilidades de estado al no utilizar la
metodología apropiada.
VI.Bibliografía
Kai Lai Chung. Elementary Probability Theory with
Stochastic Processess. Third Edition. Editorial Reverté, S.A.
Una Aplicación de las Cadenas de Markov en un
Proceso industrial. Ing. Jorge Hernán Restrepo, Msc
Carlos Alberto Ossa. Universidad Tecnológica de Pereira.
Doctorado en Investigación de Operaciones y
Estadística, 2004.
Modelos Multivariables para Variables Ordinales:
Aplicaciones en Estudios de Calidad de Servicio. Msc.
Arminda Moreno Díaz. Tesis doctoral, Facultad de
Estado del arte y propuesta de tema
Informática, Departamento de Inteligencia Artificial.
Universidad Politécnica de Madrid. 2001.
Cadenas
de
Markov,
Ciencias
de
las
Telecomunicaciones. Ing. Ángel Blasco, Msc. Tesis
doctoral, Ingeniería de Telecomunicaciones. Universidad
de Alcalá. 2009.
Markov Chain
Monte Carlo, Innovations
and
Applications. W S Kendall & F Liang & J-S Wang. World
Scientific Publishing Co. Pte. Ltd. Singapore, 2005.
Domínguez Machuca. Dirección de Operaciones
aspectos tácticos y operativos en la producción y los
servicios. Mc Graw Hill. 2008.
Hiller, F. y Liebernan, G. (1993). Introducción a la
investigación de operaciones. (7ª ed.) México: Mc Graw
Hill.
Bieman, H., Bonini, C., y Hausman, W. (1999). Análisis
cuantitativo para los negocios. (9ª, ed.) Bogotá: Mc
Graw Hill.
Taha, H. (1998). Investigación de operaciones, una
introducción. (6ª.ed). México: Prentice Hall.
Página 6 de 7
Estado del arte y propuesta de tema
Página 7 de 7

Download Report