# Markov property in a simple random walk

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.

$$S_n = \sum_{k=1}^n X_k=\sum_{k=1}^{n-1} X_k+X_n=S_{n-1}+X_n$$
$$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})$$
• 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. – Kelsey Middleton Dec 29 '16 at 16:50
• $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}$. – Canardini Dec 29 '16 at 17:04