1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SSepehr Apr 21 '16 at 21:15
  • $\begingroup$ @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. $\endgroup$ – joriki Apr 21 '16 at 21:16
  • $\begingroup$ @SSepehr: And the other half of the argument also doesn't work in that case: You can't tell which one you're at by looking at the past. $\endgroup$ – joriki Apr 21 '16 at 21:20
  • 1
    $\begingroup$ @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)$. $\endgroup$ – joriki Apr 21 '16 at 21:23
  • 1
    $\begingroup$ Thanks, you're right. This was actually the second part of a question, and I didn't expect it to be wrong. $\endgroup$ – SSepehr Apr 21 '16 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.