Notations
Let $\{X_n\}_{n\in\mathbb{N}}$ and $\{Y_n\}_{n\in\mathbb{N}}$ be two simple random walks on the integers $\mathbb{Z}$. So the process $\{(X_n,Y_n)\}_{n\in\mathbb{N}}$ is a random walk on $\mathbb{Z}^2$, where each step the "increment" of the couple of random variables could be $(+1,+1),(+1,-1),(-1,+1),(-1,-1)$ with uniform probability ($\frac{1}{4}$ each). $(X_0,Y_0) = (0,0)$, so we start our random walk from the origin.
Solved question
In Nicolas Privault's "Understanding Markov Chains" , the exercise 4.5 wants me to prove or disprove that the stochastic process $Z_n = X_n^2+Y_n^2$ is a Markov chain. I manage to prove with a counterexample that the Markovian property is not always satisfied. For example:
$$ P(Z_n = 122|Z_{n-1} = 100, Z_{n-2} = 98) = 0 $$ while $$ P(Z_n = 122|Z_{n-1} = 100, Z_{n-2} = 82) > 0 $$ so the "future" of the process depends on the "present" and also on the "past".
Real question, which generalizes the first one
How many of these counterexamples exist? Can you find any others? Are there infinitely many of them?
I'll try to write a code to brute force them and I also will try to find some "criteria" in order to eliminate some cases.
Solution of the first part
The identities above are true since:
$Z_n = 122$ has solutions $(X_n,Y_n) = (\pm 11,\pm 1)$, $(X_n,Y_n) = (\pm 1,\pm 11)$;
$Z_{n-1} = 100$ has solutions $(X_{n-1},Y_{n-1}) = (\pm 10,0)$, $(X_{n-1},Y_{n-1}) = (0,\pm 10)$, $(X_{n-1},Y_{n-1}) = (\pm 8,\pm 6)$, $(X_{n-1},Y_{n-1}) = (\pm 6,\pm 8)$;
$Z_{n-2} = 98$ has solutions $(X_{n-2},Y_{n-2}) = (\pm 7, \pm 7)$;
$Z_{n-2} = 82$ has solutions $(X_{n-2},Y_{n-2}) = (\pm 9, \pm 1)$, $(X_{n-2},Y_{n-2}) = (\pm 1, \pm 9)$.
So in the first case we know that $Z_{n-2} = 98$ and $Z_{n-1} = 100$, but this implies that $(X_{n-1},Y_{n-1}) = (\pm 8,\pm 6)$ or $(X_{n-1},Y_{n-1}) = (\pm 6,\pm 8)$, but it's impossible for example that $(X_{n-1},Y_{n-1}) = (\pm 10,0)$, because of the previous value of $Z_{n-2} = 100$ and the fact that $|X_{n+1}-X_n| = |Y_{n+1}-Y_n| = 1$, $\forall n\in\mathbb{N}$.
But since we have proved that $(X_{n-1},Y_{n-1}) = (\pm 8,\pm 6)$ or $(X_{n-1},Y_{n-1}) = (\pm 6,\pm 8)$, then it's impossible for $Z_n$ to be $122$, just looking at the integer solutions of $X_n^2+Y_n^2 = 122$. So the first probability is equal to 0.
For the second one, we can just prove that it's strictly positive, for example exhibiting a possible path for the process which links the two states:
$(X_{n-2},Y_{n-2}) = (9,1) \implies Z_{n-2} = 82$;
$(X_{n-1},Y_{n-1}) = (10,0) \implies Z_{n-1} = 100$;
$(X_{n},Y_{n}) = (11,1) \implies Z_{n} = 122$;
Claim
If $Z_{n-1} = 4c^2$ where $z$ is the biggest entry in a Pythagorean triple $(a,b,c)$, then there exist $Z_n$,$Z_{n-2}'$,$Z_{n-2}''$ which forms a valid counterexample.
In the example above, $(3,4,5)$ is the Pythagorean triple and $Z_{n-1} = 4\cdot5^2 = 100$.
Proof
Let $(a,b,c)$ be a Pythagorean triple. Let $Z_{n-1} = 4c^2$. Then $Z_{n-1} = (2c)^2+0^2 = (2a)^2+(2b)^2$. Let $Z_n = (2c+1)^2+1^2$, $Z_{n-2}' = (2c-1)^2+1^2$, $Z_{n-2}'' = (2a-1)^2+(2b-1)^2$. Then: $$ P(Z_n|Z_{n-1}, Z_{n-2}') > 0 $$ $$ P(Z_n|Z_{n-1}, Z_{n-2}'') = 0 $$
Then the second probability is equal to 0 because:
$(X_{n-2},Y_{n-2}) = (2a-1,2b-1)$ -> $(X_{n-1},Y_{n-1}) = (2a,2b)$ -> $(X_n,Y_n) = (2c+1,1)$, but the last arrow is impossible since $b\not = -1,0,1$, or in other words $2b$->$1$ in one step of length 1 is impossible.
The other probability is strictly bigger than 0 because of the existence of the following path:
$(X_{n-2},Y_{n-2}) = (2c-1,1)$ -> $(X_{n-1},Y_{n-1}) = (2c,0)$ -> $(X_n,Y_n) = (2c+1,1)$