2
$\begingroup$

How can I prove that a random walk satisfies the Markov property?

I have the simple random walk defined as $S_n = \sum_{k=1}^n X_k$ where $X_i$'s are independent and identically distributed random variables, that can be +1 or -1.

It is clear that $P(S_n=a_n | S_{n-1}=a_{n-1},...,S_1=a_1) = P(S_n=a_n|S_{n-1}=a_{n-1})$ but I do not know how to prove the latter formally.

$\endgroup$
2
$\begingroup$

$$S_n = \sum_{k=1}^n X_k=\sum_{k=1}^{n-1} X_k+X_n=S_{n-1}+X_n$$

Therefore,

$$P(S_n=a_n | S_{n-1}=a_{n-1},...,S_1=a_1)=P(X_n=a_n-a_{n-1} | S_{n-1}=a_{n-1},...,S_1=a_1)$$

By definition , $X_n$ is independent of the $S_k$, with $k\in {1,...,n-1}$, we can conclude that

$$P(S_n=a_n | S_{n-1}=a_{n-1},...,S_1=a_1)=P(S_{n-1}+X_n=a_n | S_{n-1}=a_{n-1})=P(X_n=a_n-a_{n-1})$$

$\endgroup$
  • $\begingroup$ Is it not more correct to write the equality this way: $P(S_n=a_n | S_{n-1}=a_{n-1},...,S_1=a_1)=P(X_n=a_n-a_{n-1} | S_{n-2}=a_{n-2},...,S_1=a_1)$? My problem is I am not sure when can I substitute the condition in the probability. $\endgroup$ – Kelsey Middleton Dec 29 '16 at 16:50
  • $\begingroup$ $S_n=S_{n-1}+X_n$, therefore two entities ,$S_{n-1}$ and $X_n$, entirely define $S_n$. Choosing $S_{n-1}$ will fix the first entity, we dont need to know the preceding values :$S_{n-2}$.. to fix it ( trivial). How about the second entity? Do the preceding values of $S$ matters ? The answer is no, because $X_n$ is independent of $S_{n-1}, S_{n-2}...$. Overall, we just need to know $S_{n-1}$. $\endgroup$ – Canardini Dec 29 '16 at 17:04

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.