¿Ejemplo de proceso estocástico no Markov?

Question

Un proceso de Markov se define como: $$P(X_t| X_{1:t-1}) = P(X_t|X_{t-1})$$

¿Existe un proceso no Markov que pueda ser generado por un ordenador y que no pueda ser convertido en un proceso Markov cambiando la variable?

Quiero decir que si $X_t$ depende de todos los valores anteriores, el proceso no puede ser generado por un ordenador ya que puede depender de un número infinitamente grande de valores cuando t es grande.

Además, si por ejemplo $X_t$ sólo depende de los 2 valores anteriores, podemos definir una nueva variable $Y_t = (X_t, X_{t-1})$ que es Markov.

Answer 1

Consideremos un paseo aleatorio sobre una línea que va a la izquierda o a la derecha con probabilidad $q$ y $1-q$ respectivamente para el primer movimiento. Para su $n-th$ movimiento, el caminante mira su anterior $n-1$ pasos (cada paso es a la izquierda o a la derecha) y uniformemente al azar escoge uno de ellos. Ahora en su $n-th$ paso, repite el paso elegido al azar de su memoria con probabilidad $p$ o hace lo contrario con probabilidad $1-p$ .

Este proceso se denomina Paseo Aleatorio del Elefante y es uno de los pocos procesos no markovianos exactamente resolubles. Es grande $t$ se conoce el comportamiento tanto analítico como numérico.

Referencia: https://arxiv.org/abs/cond-mat/0406593

Answer 2

Uno de estos procesos podría ser una secuencia $X_0, X_1,\dots,$ de bits en los que $X_n$ se distribuye como Bernoulli( $0.75$ ) si $X_0+X_1+\cdots+X_{n-1} = 0$ (en ${\mathbb F}_2$ ) y se distribuye como Bernoulli( $0.25$ ) en caso contrario. (Y la única dependencia es ésta.) Claramente no es Markov ya que la distribución de $X_n$ depende de toda la historia del proceso. Por otro lado, es posible implementarlo en un ordenador, ya que sólo hay que mantener un bit de información: el total en curso de la $X_i$ .