Spezifisches Gegenbeispiel für die Nicht-Markovianness des Elefanten-Random-Walks

Nov 26 2020

Betrachten Sie den Elephant Random Walk $(S_n)_{n\in\mathbb{N}}$ definiert von $S_n:=X_1+\ldots+ X_n, n\in\mathbb{N},$ deren Inkremente $X_k:=S_k-S_{k-1}$, $k\ge 1$sind rekursiv wie folgt definiert:

  • Die Verteilung von $X_1$ ist gegeben durch $P(X_1=+1)=q\in(0,1)$ und $ P(X_1=-1)=1-q$.
  • Zu jedem späteren Zeitpunkt $n\ge 2$zeichnet man zufällig einen ganzzahligen Zeitindex $k\in\{1,\ldots, n-1\}$ mit einheitlicher Wahrscheinlichkeit und lässt $X_n:=X_k$ mit Wahrscheinlichkeit $p$ und $X_n:=-X_k$ mit Wahrscheinlichkeit $1-p$.

Der Prozess wurde in eingeführt https://arxiv.org/pdf/cond-mat/0406593.pdfund wurde auch in einer Antwort auf diese Frage erwähnt: Beispiel eines stochastischen Nicht-Markov-Prozesses? .

Hat jemand ein spezifisches Gegenbeispiel für eine Flugbahn des Prozesses, die die Nicht-Markovianität des Prozesses zeigt? Bisher habe ich versucht zu vergleichen$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)$mit den bedingten Wahrscheinlichkeiten der jeweils möglichen vollständigen Trajektorien und konnte kein Gegenbeispiel finden. Ich bin dankbar für weitere Ideen, zumal ich die Möglichkeit von Rechenfehlern nicht ausschließe.

Antworten

1 MishaLavrov Nov 26 2020 at 07:04

Soweit ich das beurteilen kann, handelt es sich beim Elefanten-Random-Walk zwar um eine sehr "nicht-markovianische Beschreibung", aber tatsächlich um eine Markov-Kette - wenn auch nicht um eine zeithomogene, und viele Leute, die über Markov-Ketten sprechen, gehen von Homogenität aus. Das ist,$$ \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}] $$ für jede mögliche Flugbahn $(s_1, s_2, \dots, s_n)$. Es ist jedoch möglich, dass für$m \ne n$, $$\Pr[S_n = x \mid S_{n-1} = y] \ne \Pr[S_m = x \mid S_{m-1} = y].$$


Hier ist meine Logik. Wenn wir rechnen wollen$\Pr[S_{n+1} = s+1 \mid S_n = s]$ (und ähnlich $\Pr[S_{n+1} = s-1 \mid S_n = s]$Alles, was wir tun müssen, ist zu erkennen, um dorthin zu gelangen $S_n = s$ im $n$ Schritte, $\frac{n+s}{2}$ der Schritte muss gewesen sein $+1$ und $\frac{n-s}{2}$ der Schritte muss gewesen sein $-1$. Das heißt, wenn wir einen Zufall wählen$k \in \{1,2,\dots,n\}$, wir haben ein $\frac{n+s}{2n}$ Chance auf eine $k$ mit $X_k = 1$ und ein $\frac{n-s}{2n}$ Chance auf eine $k$ mit $X_k = -1$. Insgesamt gibt es eine$$p \cdot \frac{n+s}{2n} + (1-p) \cdot \frac{n-s}{2n}$$ Chance, am Ende zu wählen $X_{n+1}=1$und deshalb bekommen $S_{n+1} = s+1$.

Die Konditionierung auf eine andere Geschichte der Markov-Kette ist irrelevant: Sie kann uns sagen, welche Schritte waren$+1$ und welche waren $-1$, aber wir wissen bereits, wie viele von jedem es gibt. Die Markov-Eigenschaft wird also tatsächlich immer gültig sein.

Die obige Formel hängt jedoch davon ab $n$und nicht nur auf $s$. Wenn wir dazu kommen$s$ zum frühestmöglichen Zeitpunkt $n=|s|$Wir müssen Schritte unternommen haben, die alle in die gleiche Richtung gingen, und so haben wir eine $p$Chance, in diese Richtung weiterzumachen. Wenn wir dazu kommen$s$ zu einem viel späteren Zeitpunkt dann $\frac{n+s}{2}$ und $\frac{n-s}{2}$ wird nahe beieinander sein, und die Wahrscheinlichkeit, in beide Richtungen zu gehen, ist nahe beieinander $\frac12$.

Es gibt also keine feste Wahrscheinlichkeit, von zu gehen$s$ zu $s+1$ (oder von $s$ zu $s-1$), was wir uns wünschen würden, wenn die Markov-Kette zeithomogen wäre.