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$$
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})$$