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$ do you have a reference for how the "it can be shown" is done? $\endgroup$
    – wdc
    Nov 20, 2019 at 6:28

1 Answer 1

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$
6
  • $\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$
    – Emax
    Apr 21, 2016 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, 2016 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, 2016 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, 2016 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$
    – Emax
    Apr 21, 2016 at 21:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .