Contra-exemplo específico para a não-markovianidade do passeio aleatório do elefante
Considere a caminhada aleatória do elefante $(S_n)_{n\in\mathbb{N}}$ definido por $S_n:=X_1+\ldots+ X_n, n\in\mathbb{N},$ cujos incrementos $X_k:=S_k-S_{k-1}$, $k\ge 1$, são recursivamente definidos da seguinte forma:
- A distribuição de $X_1$ É dado por $P(X_1=+1)=q\in(0,1)$ e $ P(X_1=-1)=1-q$.
- Em qualquer momento subsequente $n\ge 2$, desenha-se aleatoriamente um índice de tempo inteiro $k\in\{1,\ldots, n-1\}$ com probabilidade uniforme e vamos $X_n:=X_k$ com probabilidade $p$ e $X_n:=-X_k$ com probabilidade $1-p$.
O processo foi introduzido em https://arxiv.org/pdf/cond-mat/0406593.pdfe também foi referenciado em uma resposta a esta pergunta: Exemplo de um processo estocástico não Markoviano? .
Alguém tem um contra-exemplo específico de uma trajetória do processo mostrando a não Markovianidade do processo? Até agora eu tentei 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)$com as probabilidades condicionais das respectivas trajetórias completas possíveis e não foi possível encontrar nenhum contra-exemplo. Agradeço quaisquer outras ideias, especialmente porque não excluo a possibilidade de cometer erros de computação.
Respostas
Até onde eu posso dizer, embora o passeio aleatório do elefante tenha uma "descrição não-markoviana", é na verdade uma cadeia de Markov - embora não homogênea no tempo, e muitas pessoas falando sobre cadeias de Markov presumem homogeneidade. Isso é,$$ \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 trajetória possível $(s_1, s_2, \dots, s_n)$. No entanto, é possível que para$m \ne n$, $$\Pr[S_n = x \mid S_{n-1} = y] \ne \Pr[S_m = x \mid S_{m-1} = y].$$
Aqui está minha lógica. Se quisermos calcular$\Pr[S_{n+1} = s+1 \mid S_n = s]$ (e similarmente $\Pr[S_{n+1} = s-1 \mid S_n = s]$, tudo o que temos que fazer é perceber que, para chegar a $S_n = s$ dentro $n$ passos, $\frac{n+s}{2}$ das etapas deve ter sido $+1$ e $\frac{n-s}{2}$ das etapas deve ter sido $-1$. Isso significa que quando escolhemos um$k \in \{1,2,\dots,n\}$, nós temos uma $\frac{n+s}{2n}$ chance de escolher um $k$ com $X_k = 1$ e um $\frac{n-s}{2n}$ chance de escolher um $k$ com $X_k = -1$. No geral, há um$$p \cdot \frac{n+s}{2n} + (1-p) \cdot \frac{n-s}{2n}$$ chance de acabar escolhendo $X_{n+1}=1$e, portanto, obtendo $S_{n+1} = s+1$.
Condicionar em qualquer outra história da cadeia de Markov é irrelevante: pode nos dizer quais etapas foram$+1$ e quais eram $-1$, mas já sabemos quantos de cada há. Portanto, a propriedade de Markov sempre será válida.
No entanto, a fórmula acima depende de $n$, e não apenas em $s$. Se chegarmos a$s$ o mais cedo possível $n=|s|$, devemos ter dado passos que foram todos na mesma direção, então temos um $p$chance de continuar nessa direção. Se chegarmos a$s$ em um momento muito posterior, então $\frac{n+s}{2}$ e $\frac{n-s}{2}$ estarão próximos uns dos outros, e a probabilidade de ir em qualquer direção é próxima de $\frac12$.
Portanto, não há probabilidade fixa de ir de$s$ para $s+1$ (ou de $s$ para $s-1$), que é o que desejaríamos se a cadeia de Markov fosse homogênea no tempo.