Cadenas de Markov

La idea

Una cadena de Markov describe un sistema que salta entre un número finito de estados y cuya única memoria es el presente: la probabilidad de pasar al siguiente estado depende de dónde estamos ahora, no de cómo hemos llegado. Toda esa información cabe en una matriz de transición P cuya entrada pᵢⱼ es la probabilidad de ir del estado i al estado j. Como desde i hay que ir a alguna parte, cada fila suma uno y todas las entradas son no negativas: por eso se llama matriz estocástica.

Si x es un vector fila con la probabilidad de estar en cada estado, un paso de tiempo se calcula multiplicando x·P, y n pasos equivalen a x·Pⁿ. La operación es la misma que aplicar una transformación lineal repetidamente, de modo que el comportamiento a largo plazo lo gobiernan los valores propios de P. El mayor de todos es siempre λ = 1 —consecuencia de que las filas sumen uno— y su vector propio por la izquierda es la pieza clave del análisis.

Ese vector, normalizado para que sus componentes sumen uno, es la distribución estacionaria π: cumple π·P = π y por tanto no cambia con el tiempo. En una cadena regular, aquella en la que desde cualquier estado se puede alcanzar cualquier otro en un número fijo de pasos, las iteraciones convergen a π sea cual sea la distribución inicial, y el segundo valor propio en módulo —siempre menor que uno— marca la velocidad de esa convergencia. El inverso 1/πᵢ es el tiempo medio que tarda el sistema en volver al estado i.

Fórmulas clave

• Matriz estocásticapᵢⱼ ≥ 0, Σⱼ pᵢⱼ = 1
• Propiedad de MarkovP(Xₙ₊₁ = j | Xₙ = i, …, X₀) = P(Xₙ₊₁ = j | Xₙ = i)
• Evoluciónxₙ₊₁ = xₙ · P, xₙ = x₀ · Pⁿ
• Distribución estacionariaπ · P = π, Σᵢ πᵢ = 1
• Lectura espectralπ es vector propio por la izquierda con λ = 1
• Tiempo medio de retornomᵢ = 1 / πᵢ

Dónde se aplica

El algoritmo PageRank modela a un internauta que sigue enlaces al azar: la distribución estacionaria de esa cadena es la importancia de cada página. En meteorología se usan cadenas de Markov sencillas para generar series sintéticas de clima con las que dimensionar embalses o plantas solares. En finanzas, las agencias publican matrices de transición de calificación crediticia y con ellas se estima la probabilidad de impago a varios años. En fiabilidad industrial, los estados «funcionando / degradado / averiado» forman una cadena cuya estacionaria da la disponibilidad media de la máquina, y en generación de texto las cadenas de Markov fueron el primer modelo del lenguaje.

Con programación (Python)

P = [[0.7, 0.2, 0.1],
     [0.3, 0.4, 0.3],
     [0.2, 0.3, 0.5]]
nombres = ["sol", "nubes", "lluvia"]

def paso(x):
    return [sum(x[i]*P[i][j] for i in range(3)) for j in range(3)]

x = [1.0, 0.0, 0.0]
for n in range(1, 21):
    x = paso(x)
    if n in (1, 2, 3, 6, 12, 20):
        print("paso", n, [round(v, 5) for v in x])

def estacionaria(iteraciones=800):
    y = [1/3, 1/3, 1/3]
    for _ in range(iteraciones):
        y = paso(y)
    return y

pi = estacionaria()
print("estacionaria:", [round(v, 6) for v in pi])
print("pi P       :", [round(v, 6) for v in paso(pi)])
for i, nom in enumerate(nombres):
    print(f"{nom:7} pi = {pi[i]:.4f}   retorno medio = {1/pi[i]:.2f} dias")
print("desde lluvia tras 40 pasos:", [round(v, 6) for v in estacionaria(40)])

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Valores y vectores propios · Matrices como transformaciones · Probabilidad clásica · Teorema de Bayes