Spezifisches Gegenbeispiel für die Nicht-Markovianness des Elefanten-Random-Walks
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
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.