Cadenas de Markov en tiempo discreto: sistemas complejos e inteligencia artificial

Dificultad

Fácil 25%

Contenido

Tiempo discreto Cadenas de Markov

Cuando estamos en presencia de un fenómeno aleatorio, notamos que el futuro depende solo del presente. Es en esta condición que se pueden modelar las cadenas de Markov en tiempo discreto.

Deje (X_no) una secuencia de variables aleatorias con valores en un conjunto finito de J estados, X_t= j es el estado del sistema en el tiempo t. Decimos que X_no es una cadena de Markov de transición si qq es n, qq es i₀,…, I_{n + 1} :

P (X_{(n + 1)}= yo_{(n + 1)} | X_no = yo_no,…, X₀= yo₀) = P (X_{(n + 1)} = yo_{(n + 1)} | X_no = yo_no)

Se dice que tal proceso no tiene memoria. El valor de esta probabilidad se denota por p_{n (n + 1)}.

Notamos que X₀ no está fijada por la definición, esta ley se llama ley inicial. El vector de las probabilidades iniciales se denota por π, con π_j= P (S₀= j) con j incluido en el conjunto finito y la suma de π_j=1.

El vector de probabilidades de transición se denota por v_I (pag_i0,…, PAG_ij) con j incluido en el conjunto finito y la suma de p_ij=1.

La matriz de probabilidad de transición es la concatenación de los vectores de probabilidad de transición. Por lo tanto, todos los términos son positivos o cero, la suma de los términos en una línea es igual a 1. Las potencias de una matriz de transición (o matriz estocástica) son matrices estocásticas.

Cadenas de Markov de tiempo discreto homogéneas

Se dice que una cadena de Markov es homogénea en el tiempo si las probabilidades de transición no se ven afectadas por una traducción a lo largo del tiempo. Es decir, no depende de n. Las probabilidades de transición permanecen estacionarias a lo largo del tiempo.

Pongamos un ejemplo. Siempre que un jugador tenga dinero, juega apostando £ 1. Gana £ 1 con una probabilidad de py pierde su apuesta con una probabilidad (1-p) con p entre 0 y 1. El juego termina cuando tiene £ 3.

Podemos definir cuatro estados: 0, 1, 2, 3, que representan el dinero que tiene. La matriz de transición es la siguiente:

Las cadenas de Markov en tiempo discreto pueden tener una ley inicial que se presenta en forma de vector estocástico (la suma es igual a 1). Esta ley representa la distribución en el origen.

Representación de cadenas de Markov en tiempo discreto

El gráfico asociado con un proceso de markov está formado por los puntos que representan los estados del proceso del conjunto finito, y por los arcos correspondientes a las posibles transiciones p_ij.

Denotemos por Q la matriz de transición. Una secuencia de estados (x₁, X₂,. . . , X_metro) define un camino de longitud m que va desde x₁ a x_metro en el gráfico asociado con la cadena de Markov homogénea si y solo si Q (x₁, X₂) Q (x₃, X₄). . .Q (x_m-1, X_metro)> 0.

Cuando intentamos simular los primeros estados de cadenas de Markov en tiempo discreto homogéneo (X_no) del espacio de estados finito X = {1 ,. . . , N} descrito solo por su ley inicial y su matriz de transición Q podemos usar el siguiente algoritmo:

La probabilidad de estar en un estado j desde un estado i después de n iteraciones equivale a multiplicar la matriz de transición Q^no por el vector inicial. La respuesta es entonces Q^no(yo, j).

Gráficos reducidos de cadenas de Markov de tiempo discreto

Un estado j es accesible desde un estado i si existe una probabilidad estrictamente positiva de alcanzar el estado j desde el estado i en un número finito de transiciones. Desde un punto de vista de Teoría de grafos, j es accesible desde un estado i si hay un camino entre i y j.

Si el estado j es accesible desde el estado i y, a la inversa, el estado i es accesible desde el estado j, entonces decimos que los estados i y j se comunican. Esto da como resultado el hecho de que i y j están en el mismo circuito.

Un gráfico reducido es una partición de una cadena de Markov en clases de equivalencia, de modo que todos los estados de una clase se comunican entre sí.

Las clases de equivalencia son las siguientes:

se dice que una clase es transitoria si es posible dejarla, pero en este caso, el proceso nunca podrá volver a ella;
se dice que una clase es recurrente o persistente si no se puede abandonar. si un clase recurrente se compone de un solo estado, se dice que es absorbente.

Si la partición en clases de equivalencia induce solo una clase recurrente, se dice que la cadena de Markov es irreducible. Una cadena de Markov tiene al menos una clase recurrente.

Ejemplo de cadenas de Markov de tiempo discreto

Estamos interesados en el desarrollo de un bosque natural en una región templada en una parcela. Nuestro modelo tiene 3 estados. El estado 1 es el de vegetación compuesta por pastos u otras especies con bajo balance de carbono; l'état 2 correspond à la présence d'arbustes dont le développement rapide nécessite un ensoleillement maximal et dont le rendement carbone sera maximale, et l'état 3 celui d'arbres plus gros qui peuvent se développer dans un environnement semi ensoleillé (considéré comme un bosque). Si estos tres estados se denotan respectivamente por h, a, f (para hierba, arbustos, bosque), el conjunto de estados posibles para un punto dado de esta gráfica es el conjunto s={h, a, f}. En la parcela, se identifican en el suelo un gran número de puntos distribuidos en una cuadrícula regular y se registra el estado de la vegetación en cada uno de estos puntos a intervalos de tiempo fijos. Este tipo de programa se llama autómata celular.

Al observar la evolución durante un intervalo de tiempo, se puede determinar para cada estado i∈S la proporción de puntos que pasaron al estado j∈S, y anotar p_ij esta proporción. Si las diferentes proporciones así señaladas (hay 9) cambian poco de un intervalo de tiempo al siguiente, podemos suponer que no cambian con el tiempo y podemos mirar las probabilidades para cualquier punto de pasar del estado i en el estado j para un intervalo de tiempo. Supongamos, por ejemplo, que en este gráfico, estas probabilidades son las siguientes:

Si X₀ indicar el estado de un punto en el tiempo t = 0 y X₁ el estado del mismo punto en t = 1, por ejemplo, tenemos la probabilidad de pasar del estado de arbusto en t = 0 al estado de bosque en t = 1 se escribe P (X₁= f: X₀= a) es igual a 0, 4.

El conjunto de estados S y la matriz de transición P constituyen un ejemplo de cadena de Markov. También podemos representar esta cadena de Markov mediante el siguiente gráfico:

En este modelo, podemos entonces calcular la probabilidad de cualquier sucesión de estados, llamada trayectoria de la cadena de Markov. Por ejemplo, la probabilidad de que en un punto de la gráfica observemos la sucesión de estados (h, h, a, f, f) se calcula de la siguiente manera:

donde π₀ es la probabilidad de estar en el estado en el momento inicial t = 0.

Observación del estado en el que se ubican los distintos puntos de la parcela en el tiempo inicial t₀ permite determinar las proporciones iniciales de cada uno de los 3 estados. Para eso, se anota para cada punto el estado en el que se encuentra y se calcula la proporción de puntos de cada uno de los estados posibles. Podemos ver cada proporción como la probabilidad de que un punto de la gráfica se encuentre en uno de los estados en el instante inicial. Así, si tenemos por ejemplo π₀ = (0.5, 0.25, 0.25), esto significa que la mitad de los puntos de la parcela están inicialmente en el estado h, una cuarta parte en el estado ay una cuarta parte en el estado f. Pero también podemos interpretar esto considerando que cualquier estado tiene una probabilidad 50% de estar en el estado h, 25% de estar en el estado ay 25% de estar en el estado f. Es por esto que la proporción de individuos de la población estudiada ubicados en cada uno de los estados,

se llama ley de probabilidad inicial o distribución inicial. Cuando uno elige un modelado por una cadena de Markov, el objetivo a menudo es determinar la evolución de la distribución de estados a lo largo del tiempo. Por ejemplo, si la parcela considerada arriba está cubierta por un tercio de bosque en el momento inicial, ¿crecerá esta proporción, tenderá a 100%, por el contrario tenderá a cero o se acercará a un valor? Tipo límite de equilibrio ecológico?

Veremos que si conocemos la distribución inicial podemos calcular la distribución en el tiempo t = 1, luego en el tiempo t = 2 y así sucesivamente. Calculemos para t = 1:

Deducimos que π₁(h) es el producto escalar del vector π₀ con la primera columna de la matriz P. Del mismo modo, comprobamos que π₁(a) es el producto escalar del vector con la segunda columna de la matriz P y que π₁(f) es el producto escalar del vector con la tercera columna de la matriz P. Resumimos esto: π₁= π₀pag.