Ejemplos "sorprendentes" de cadenas de Markov

Question

Estoy buscando ejemplos de cadenas de Markov que sean sorprendentes en el siguiente sentido: un proceso estocástico $X_1,X_2,...$ que es "natural" pero para el que la propiedad de Markov no es evidente a primera vista. Por ejemplo, podría ser que la definición natural del proceso sea en términos de algún proceso $Y_1,Y_2,...$ que es markoviano y donde $X_i=f(Y_i)$ para alguna función $f$ .

Permítanme darles un ejemplo que es ligeramente sorprendente, pero no lo suficiente para mi gusto. Supongamos que tenemos $n$ contenedores que están inicialmente vacíos, y en cada paso de tiempo $t$ lanzamos una bola en uno de los recipientes seleccionados uniformemente al azar (e independientemente de los pasos de tiempo anteriores). Sea $X_t$ sea el número de recipientes vacíos en el momento $t$ . Entonces $X_1,X_2,...$ forman una cadena de Markov.

¿Hay buenos ejemplos más sorprendentes? Pido disculpas si esta pregunta es vaga.

Answer 1

Podría volver al propio Markov, que en 1913 aplicó el concepto de cadena de Markov a las secuencias de vocales y consonantes del poema de Alexander Pushkin Eugene Onegin. En buena aproximación, se encontró que la probabilidad de aparición de una vocal depende únicamente de la letra que la precede inmediatamente, con $p_{\text{vowel after consonant}}=0.663$ y $p_{\text{vowel after vowel}}=0.128$ . Estos números resultaron ser específicos para cada autor, lo que sugiere un método para identificar a los autores de textos desconocidos. (Aquí hay un Implementación de Mathematica. ) Brian Hayes escribió un artículo divertido revisando cómo "La probabilidad y la poesía fueron socios improbables en la creación de una herramienta computacional"

Las primeras 100 letras cirílicas de un total de 20.000 cartas recopiladas por Markov a partir del primer capítulo y medio del poema de Pushkin. Los números que rodean el bloque de letras se utilizaron para demostrar que la aparición de las vocales es una cadena de Markov. [ fuente de la cifra ]

Answer 2

Creo que si $(X_n)$ es un paseo aleatorio simple sesgado en $[-N,N]$ entonces $|X_n|$ es una cadena de Markov.

Answer 3

Considere la Algoritmo Metropolis-Hastings que es un MCMC es decir, un método de Monte Carlo de propósito general para producir muestras de una distribución de probabilidad dada. El método funciona generando una cadena de Markov a partir de una propuesta cadena de Markov de la siguiente manera. Una propuesta de movimiento se calcula según la cadena de Markov de la propuesta, y luego se acepta con una probabilidad que garantiza la Cadena metropolizada (la producida por el algoritmo Metropolis-Hastings) preserva la distribución de probabilidad dada.

Esta cadena metropolizada es un "ejemplo sorprendente de cadena de Markov" porque la probabilidad de aceptación en cada paso de la cadena depende de ambos el estado actual de la cadena y el estado propuesto. Sin embargo, la sorpresa desaparece un poco cuando uno se da cuenta de que el siguiente estado de la cadena metropolizada no coincide necesariamente con el movimiento propuesto, y que el siguiente estado de la cadena podría ser, de hecho, el estado actual de la cadena si se rechaza el movimiento propuesto.

Para una introducción expositiva a las cadenas metropolizadas, consulte La revolución MCMC por P. Diaconis, y véase también Una interpretación geométrica del algoritmo Metrópolis-Hasting por L. J. Billera y P. Diaconis. He aquí una cita de este último.

El algoritmo [Metropolis-Hastings] se utiliza ampliamente para simulaciones en física, química, biología y estadística. Aparece como la primera de una lista reciente de grandes algoritmos de la ciencia del siglo XX. científica del siglo XX. Sin embargo, para muchas personas (incluidos los autores actuales) el algoritmo de Metrópolis-Hastings parece un truco de magia. Es difícil de dónde viene o por qué funciona.

ADD

Otros ejemplos "sorprendentes" (y relacionados) son los siguientes MALA , Monte-Carlo hamiltoniano , Oportunidades adicionales Hamiltonian Monte-Carlo , Múltiple de Riemann Langevin y Monte Carlo Hamiltoniano , Metrópolis de varios intentos y Templado paralelo que son todos métodos MCMC. Al igual que el ejemplo anterior, estas cadenas son inesperadamente markovianas porque sus probabilidades de aceptación (las probabilidades que determinan la actualización real de la cadena) son funciones del estado actual de la cadena y del movimiento o movimientos propuestos.

Permítanme que me explaye un poco sobre el método de templado en paralelo y lo que lo convierte en un ejemplo sorprendente. El objetivo del método es tomar muestras de una distribución de probabilidad con un paisaje energético multimodal, que se puede considerar como una versión de alta dimensión:

La dificultad del muestreo de una distribución de probabilidad con un paisaje energético como éste no es sólo el hecho de que hay muchos modos, sino que las barreras energéticas entre estos modos pueden ser demasiado altas para que un simple método MCMC las supere. En pocas palabras, incluso el cálculo de la media y la varianza de esta distribución puede resultar poco práctico con métodos MCMC sencillos.

La idea básica del templado en paralelo es introducir un parámetro de temperatura ficticio que aplane la distribución de probabilidad deseada y, por tanto, facilite el muestreo mediante un método MCMC sencillo. Entonces se construye una secuencia de distribuciones desde una distribución suficientemente plana (a alta temperatura) hasta la distribución de probabilidad deseada (a baja temperatura). A continuación, se ejecuta una secuencia de cadenas para tomar muestras de esta secuencia de distribuciones.

Cada una de estas cadenas evoluciona a su propia temperatura, pero de vez en cuando se intercambian los estados entre estas cadenas para que la cadena que funciona a la temperatura más baja explore su paisaje de forma más eficiente. (Por desgracia, las muestras generadas a las temperaturas más altas no pueden utilizarse directamente para tomar muestras de la distribución deseada a la temperatura más baja de la secuencia).

Como ejemplo concreto, consideremos la aplicación del temple paralelo a una molécula de pentano de 15 grados de libertad. El objetivo es tomar una muestra de la distribución de equilibrio de esta molécula en el plano definido por sus dos ángulos diedros (que son ciertos grados de libertad internos de la molécula). Esta distribución tiene nueve modos (correspondientes a diferentes conformaciones moleculares). A continuación se muestra la secuencia de distribuciones de probabilidad en la que los puntos representan los estados de las cadenas MCMC a cuatro niveles de temperatura diferentes. (El parámetro $\beta$ es la temperatura inversa).

Es fácil calcular a ojo el plano a la temperatura más alta (la más baja $\beta$ ), ya que los puntos están más repartidos en ese plano. Volviendo al punto, no todos los intercambios son aceptados, y la probabilidad de intercambiar entre cadenas a diferentes temperaturas en el templado paralelo depende de ambos los estados actuales e intercambiados de la cadena. Además, al igual que en Metropolis-Hastings simple, la probabilidad de aceptar un movimiento propuesto para las cadenas a diferentes temperaturas también depende de ambos el estado actual y propuesto de la cadena. Esta dependencia es esencial para que la cadena conserve la distribución de probabilidad correcta en el espacio ampliado. Así, a primera vista, puede parecer que la cadena de templado paralelo no es Markov. Sin embargo, al igual que en Metropolis-Hastings, se puede demostrar explícitamente que la probabilidad de transición de la cadena de templado en paralelo sólo depende de su estado actual.

Answer 4

Un ejemplo que me gusta es que si añadir una lista de números los transportes forman una cadena de Markov

• Carros, barajas y una matriz sorprendente
• Carries, shuffling y funciones simétricas

Si $n$ enteros en base $b$ con dígitos elegidos uniformemente al azar, los transportes forman una cadena de Markov

1 12021 01111 11111 11111 11011 10111 01111 11111 21011 1112.

  43935 23749 58561 74916 62215 47448 33196 51990 19807 27075
  48537 53642 77448 32760 14421 72142 82116 37225 43300 51498
  33618 41327 41561 16257 43616 55134 82714 63369 87142 45607
-------------------------------------------------------------
1 26091 18719 77571 23934 20253 74725 98027 52585 50250 24180

---

Otro ejemplo importante es paseo aleatorio por el cubo [0,1] n y su proyección es la Urna Ehrenfest

• empezar en $\vec{v} = (0,\dots, 0) \in \{ 0,1\}^n$ y en cada paso de tiempo cambiar $0 \leftrightarrow 1$ para una de las coordenadas.
• Si tomamos el producto interior $\vec{v} \cdot (1,\dots, 1) = v_1 + \dots v_n \in \mathbb{N}$ esto también es una cadena de Markov.
• Podríamos tener manchas $0, 1, \dots, n$ y si $X_t = k$ podemos saltar a la izquierda con probabilidad $\frac{k}{n}$ y a la derecha con probabilidad $\frac{n-k}{n}$ y esto es una cadena de Markov.

Tuve que verificar que mi lógica era correcta está en Cadenas de Markov y tiempos de mezcla .

Answer 5

Dejemos que $S_n$ sea el paseo aleatorio unidimensional del vecino más cercano con $ 1-q=p=P[S_{n+1}=x+1\mid S_n=x]=1-P[S_{n+1}=x-1\mid S_n=x]$ , donde $p\neq q$ . Luego, hay un hecho (bastante sorprendente) que $Y_n=|S_n|$ sigue siendo una cadena de Markov. Véase, por ejemplo, la proposición 4.1.1 de [S.Ross, "Stochastic Processes"].