# distance from the origin in a simple random walk on $\mathbb Z^2$

let $S_{n}= \sum_{i=1}^{n}X_i$ be a simple random walk on $\mathbb{Z}$, with $S_0 = 0$.

$X_i = 1$ with probability $p$ and $X_i = -1$ with probability $1-p$.

It can be shown that $$\mathbb{P}(S_n=i\mid|S_n|=i, |S_{n-1}|=i_{n-1}, ..., |S_1|=i_1)= \frac{p^i}{p^i+(1-p)^i},$$

which means that having only $|S_n|=i$, one can calculate the probability of being in state $S_n=i$ (and therefore $S_n=-i$). From here, it is easy to show that $|S_n|$ is a markov chain.

I'm trying to show that the same is true for a (not necessarily symmetric) simple random walk on $\mathbb{Z^2}$ starting from the origin. In other words, I want to show that distance from the origin at each step is a markov chain.

The argument above does not seem to be extendable here, since there may be $k>1$ points with integer coordinates for a given distance from the origin and $k$ depends on the distance.

• do you have a reference for how the "it can be shown" is done?
– wdc
Nov 20, 2019 at 6:28

This is not true. For instance, you have different options for the future whether you're at $(3,4)$ or $(5,0)$, and you can tell which one you're at by looking at the past, so the process is not memoryless.
• I don't understand your answer. you also have different options whether you're at $-5$ of $5$ in the 1-D case, but this does not mean that $|S_n|$ is not a markov process.
• @SSepehr: No, in that case you don't have different options. You have exactly the same options of moving to $|S_{n+1}|=4$ or to $|S_{n+1}|=6$ in both cases. Apr 21, 2016 at 21:16
• @SSepehr: More formally, $0=\textsf P(|S_{n+1}|=6\mid|S_n|=5\land |S_{n-1}|=4\sqrt2)\ne\textsf P(|S_{n+1}|=6\mid|S_n|=5\land |S_{n-1}|=4)$. Apr 21, 2016 at 21:23