cadena de Markov

# tag · @ author · ! scientist

Una cadena de Markov es un modelo estocástico que describe una secuencia de estados en la que la probabilidad de transición al siguiente estado depende exclusivamente del estado actual (propiedad de Markov). Formalmente: P(X_{n+1}=x | X_n=x_n,...,X_0=x_0) = P(X_{n+1}=x | X_n=x_n). Las cadenas pueden ser discretas o continuas en el tiempo, con un número finito o numerable de estados. Herramientas principales: matriz de probabilidades de transición, distribución estacionaria, ecuaciones de Chapman–Kolmogorov.

History

El matemático ruso Andréi Markov, a principios del siglo XX, estudió secuencias de variables aleatorias dependientes e introdujo el concepto de cadena para mostrar que incluso en textos aleatorios se pueden encontrar regularidades estadísticas.

How it works

Como en el juego de la 'Serpiente' en el teléfono, donde la serpiente se mueve por las casillas eligiendo la dirección aleatoriamente, pero solo desde la posición actual. Si se sabe dónde está ahora, no importa cómo llegó allí: es la propiedad de falta de memoria.

💡 La primera aplicación práctica de las cadenas de Markov fue el análisis de la alternancia de vocales y consonantes en 'Eugenio Oneguin': Markov demostró que no era aleatoria y predijo las letras futuras del texto.

Una cadena de Markov es un proceso estocástico con tiempo discreto y espacio de estados finito o numerable que posee la propiedad de Markov: la distribución condicional de los estados futuros depende solo del estado actual y no de la trayectoria pasada. Se define por una distribución inicial y una matriz de probabilidades de transición P = (p_{ij}), donde p_{ij} = P(X_{n+1}=j | X_n=i). La cadena se llama homogénea si los p_{ij} no dependen de n. Conceptos clave: clasificación de estados (recurrentes, transitorios, periodicidad), ergodicidad (existencia de una distribución límite), distribución estacionaria π (πP = π). Para cadenas finitas irreducibles y aperiódicas existe una única distribución estacionaria a la que convergen las distribuciones de los estados. Las cadenas de Markov de tiempo continuo se describen mediante una matriz de intensidades Q. Aplicaciones: algoritmo de Metropolis–Hastings en Monte Carlo, modelos ocultos de Markov en reconocimiento de voz, teoría de colas.

History

Andréi Andréyevich Markov introdujo las cadenas en 1906 al estudiar la ley de los grandes números para variables dependientes. Su motivación fue refutar la afirmación de Nekrasov de que la independencia es necesaria para las leyes estadísticas. Más tarde, en la década de 1930, Kolmogorov desarrolló la teoría general de los procesos de Markov. A mediados del siglo XX, las cadenas de Markov se convirtieron en una herramienta central en investigación de operaciones, física (modelo de Ising) e informática (generación de texto, PageRank).

How it works

Matemáticamente, una cadena de Markov se define por un vector de probabilidades inicial π^{(0)} y una matriz estocástica P. Entonces la distribución después de n pasos es: π^{(n)} = π^{(0)} P^n. La propiedad de falta de memoria significa que para predecir el futuro basta con conocer solo el estado actual. El comportamiento a largo plazo se determina por la descomposición espectral de la matriz P: si existe un único vector propio por la izquierda con valor propio 1 (distribución estacionaria), entonces π^{(n)} → π cuando n→∞. Ecuaciones de Chapman–Kolmogorov: P^{(n+m)} = P^{(n)} P^{(m)}, que expresan la composición de transiciones. Para tiempo continuo: dπ/dt = πQ, donde Q es la matriz de intensidades de transición.

p_{ij}^{(n+m)} = \sum_{k} p_{ik}^{(n)} p_{kj}^{(m)}

p_{ij}^{(n)} es la probabilidad de transición del estado i al estado j en n pasos; suma sobre todos los estados intermedios k.

Open problems & fun facts

Problema de aceleración de la convergencia para cadenas con mezcla lenta (por ejemplo, en distribuciones multidimensionales con picos agudos).; Desarrollo de algoritmos eficientes para estimar probabilidades de eventos raros en sistemas complejos.; Análisis de modelos ocultos de Markov con estados ocultos continuos de alta dimensionalidad.

💡 Las cadenas de Markov subyacen al algoritmo PageRank que originalmente dio éxito a Google: las páginas de internet se modelan como estados, y las transiciones son los hipervínculos; el rango de una página es la probabilidad estacionaria de visita en un paseo aleatorio con retorno.

No articles yet

cadena de Markov

History

How it works

History

How it works

History

How it works

Open problems & fun facts

Related articles