Consider the Elephant Random Walk $(S_n)_{n\in\mathbb{N}}$ defined by
$S_n:=X_1+\ldots+ X_n, n\in\mathbb{N},$
whose increments $X_k:=S_k-S_{k-1}$, $k\ge 1$, are recursively defined as follows:
- The distribution of $X_1$ is given by $P(X_1=+1)=q\in(0,1)$ and $ P(X_1=-1)=1-q$.
- At any subsequent time $n\ge 2$, one draws randomly an integer time index $k\in\{1,\ldots, n-1\}$ with uniform probability and lets $X_n:=X_k$ with probability $p$ and $X_n:=-X_k$ with probability $1-p$.
The process was introduced in https://arxiv.org/pdf/cond-mat/0406593.pdf and was also referenced in an answer to this question: Example of a stochastic non Markov process?.
Does anyone have a specific counterexample of a trajectory of the process showing the non-Markovianness of the process? So far I've tried comparing $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)$ with the conditional probabilities of the respective possible complete trajectories and couldn't find any counterexample. I am grateful for any further ideas, especially since I don't exclude the possibility of making computation mistakes.
Best Answer
As far as I can tell, though the elephant random walk has a very "non-Markovian description", it is actually a Markov chain - though not a time-homogeneous one, and many people talking about Markov chains do assume homogeneity. That is, $$ \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}] $$ for every possible trajectory $(s_1, s_2, \dots, s_n)$. However, it's possible that for $m \ne n$, $$\Pr[S_n = x \mid S_{n-1} = y] \ne \Pr[S_m = x \mid S_{m-1} = y].$$
Here's my logic. If we want to compute $\Pr[S_{n+1} = s+1 \mid S_n = s]$ (and similarly $\Pr[S_{n+1} = s-1 \mid S_n = s]$, all we have to do is realize that in order to get to $S_n = s$ in $n$ steps, $\frac{n+s}{2}$ of the steps must have been $+1$ and $\frac{n-s}{2}$ of the steps must have been $-1$. That means when we choose a random $k \in \{1,2,\dots,n\}$, we have a $\frac{n+s}{2n}$ chance of picking a $k$ with $X_k = 1$ and a $\frac{n-s}{2n}$ chance of picking a $k$ with $X_k = -1$. Overall, there is a $$p \cdot \frac{n+s}{2n} + (1-p) \cdot \frac{n-s}{2n}$$ chance of ending up choosing $X_{n+1}=1$, and therefore getting $S_{n+1} = s+1$.
Conditioning on any other history of the Markov chain is irrelevant: it can tell us which steps were $+1$ and which were $-1$, but we already know how many of each there are. So the Markov property will in fact always hold.
However, the formula above depends on $n$, and not only on $s$. If we get to $s$ at the earliest possible time $n=|s|$, we must have taken steps that all went in the same direction, and so we have a $p$ chance of continuing in that direction. If we get to $s$ at a much later time, then $\frac{n+s}{2}$ and $\frac{n-s}{2}$ will be close to each other, and the probability of going in either direction is close to $\frac12$.
So there is no fixed probability of going from $s$ to $s+1$ (or from $s$ to $s-1$), which is what we'd want if the Markov chain were time-homogeneous.