Contraejemplo específico de la no-Markovianness del paseo aleatorio del elefante
Considere la caminata aleatoria de elefantes $(S_n)_{n\in\mathbb{N}}$ definido por $S_n:=X_1+\ldots+ X_n, n\in\mathbb{N},$ cuyos incrementos $X_k:=S_k-S_{k-1}$, $k\ge 1$, se definen recursivamente como sigue:
- La distribución de $X_1$ es dado por $P(X_1=+1)=q\in(0,1)$ y $ P(X_1=-1)=1-q$.
- En cualquier momento posterior $n\ge 2$, se extrae aleatoriamente un índice de tiempo entero $k\in\{1,\ldots, n-1\}$ con probabilidad uniforme y permite $X_n:=X_k$ con probabilidad $p$ y $X_n:=-X_k$ con probabilidad $1-p$.
El proceso se introdujo en https://arxiv.org/pdf/cond-mat/0406593.pdfy también se hizo referencia en una respuesta a esta pregunta: ¿ Ejemplo de un proceso estocástico no de Markov? .
¿Alguien tiene un contraejemplo específico de una trayectoria del proceso que muestre el carácter no markoviano del proceso? Hasta ahora he intentado comparar$P(S_3=1|S_2=0)$, $P(S_4=2|S_3=1)$, $P(S_4=0|S_3=1)$, $P(S_4=0|S_3=-1)$con las probabilidades condicionales de las respectivas trayectorias completas posibles y no pudo encontrar ningún contraejemplo. Estoy agradecido por cualquier otra idea, especialmente porque no excluyo la posibilidad de cometer errores de cálculo.
Respuestas
Por lo que puedo decir, aunque el paseo aleatorio del elefante tiene una "descripción no markoviana", en realidad es una cadena de Markov, aunque no homogénea en el tiempo, y muchas personas que hablan de cadenas de Markov asumen homogeneidad. Es decir,$$ \Pr[S_n = s_n \mid S_{n-1} = s_{n-1}, S_{n-2} = s_{n-2}, \dots, S_1 = s_1] = \Pr[S_n = s_n \mid S_{n-1} = s_{n-1}] $$ para cada trayectoria posible $(s_1, s_2, \dots, s_n)$. Sin embargo, es posible que para$m \ne n$, $$\Pr[S_n = x \mid S_{n-1} = y] \ne \Pr[S_m = x \mid S_{m-1} = y].$$
Esta es mi lógica. Si queremos calcular$\Pr[S_{n+1} = s+1 \mid S_n = s]$ (y de manera similar $\Pr[S_{n+1} = s-1 \mid S_n = s]$, todo lo que tenemos que hacer es darnos cuenta de que para llegar a $S_n = s$ en $n$ pasos, $\frac{n+s}{2}$ de los pasos debe haber sido $+1$ y $\frac{n-s}{2}$ de los pasos debe haber sido $-1$. Eso significa que cuando elegimos un azar$k \in \{1,2,\dots,n\}$, tenemos una $\frac{n+s}{2n}$ posibilidad de elegir un $k$ con $X_k = 1$ y un $\frac{n-s}{2n}$ posibilidad de elegir un $k$ con $X_k = -1$. En general, hay una$$p \cdot \frac{n+s}{2n} + (1-p) \cdot \frac{n-s}{2n}$$ posibilidad de terminar eligiendo $X_{n+1}=1$, y por lo tanto obteniendo $S_{n+1} = s+1$.
El condicionamiento de cualquier otra historia de la cadena de Markov es irrelevante: puede decirnos qué pasos fueron$+1$ y cuales fueron $-1$, pero ya sabemos cuántos de cada uno hay. Por tanto, la propiedad de Markov se mantendrá siempre.
Sin embargo, la fórmula anterior depende de $n$, y no solo en $s$. Si llegamos a$s$ a la mayor brevedad posible $n=|s|$, debemos haber tomado medidas que iban en la misma dirección, por lo que tenemos una $p$posibilidad de continuar en esa dirección. Si llegamos a$s$ mucho más tarde, entonces $\frac{n+s}{2}$ y $\frac{n-s}{2}$ estarán cerca uno del otro, y la probabilidad de ir en cualquier dirección es cercana a $\frac12$.
Entonces no hay una probabilidad fija de pasar de$s$ a $s+1$ (o de $s$ a $s-1$), que es lo que querríamos si la cadena de Markov fuera homogénea en el tiempo.