Markov Chain - Random Walk

[tanzl]

Suppose X is a random walk with probability
P(X_k=+1)=p and P(X_k=-1)=q=1-p
and S_n=X_1+X_2+...+X_n

Can anyone explain why does line 3 equal to line 4?
P(S_k-S_0≠0 ,S_k-S_1≠0 ,…,S_k-S_{k-1}≠0)
=P(X_k+X_{k-1}+⋯+X_1≠0 ,X_k+X_{k-1}+⋯+X_2≠0 ,…,X_k≠0)
=P( X_k≠0 ,X_k+X_{k-1}≠0 ,…,X_k+X_{k-1}+⋯+X_1≠0 )...............Line 3
=P( X_1≠0 ,X_2+X_1≠0 ,…,X_k+X_{k-1}+⋯+X_1≠0 )..................Line 4
=P( X_1≠0 ,X_1+X_2≠0 ,…,X_1+X_2+⋯+X_k≠0 )

The above comes from a book on random walk, I attached a link here (page 36),
http://books.google.com/books?id=7suiLOKqeYQC&printsec=frontcover#v=onepage&q&f=false
Thanks

[alexfloo]

It's because your Xi's are all i.i.d.. That means you can always interchange them however you like, since they each have the same distribution.

[chiro]

Hey tanzl.

It looks like they are just substituting k = 1 into line 4, based on the premise that the relationship holds for k >= 1.

As for an explanation, it looks like a simple random walk with independent increments, but from the page you cited, it appears that they are not necessarily independent which is a more general assumption than the simple random walk models.

(When each incremental random variable is independent, this simplifies things somewhat)

[tanzl]

Thanks for the replies.
It's because your Xi's are all i.i.d.. That means you can always interchange them however you like, since they each have the same distribution.

Hi Alexfloo, in what way do you mean X can interchange? I do know that X are iid, but I dont see how this property can help when line 3 is adding more terms in reverse time order and line 4 is adding more terms in increasing time order.
Hey tanzl.

It looks like they are just substituting k = 1 into line 4, based on the premise that the relationship holds for k >= 1.

As for an explanation, it looks like a simple random walk with independent increments, but from the page you cited, it appears that they are not necessarily independent which is a more general assumption than the simple random walk models.

(When each incremental random variable is independent, this simplifies things somewhat)

Hi Chiro, I dont think it is just simply substituting k=1 into line 3, it does not hold for k>1.
From my understanding, X is independent incremental random variable, I am not sure about S. But S has Markovian property.

BTW, I have read in a research paper on this problem. The proof in the paper only stated that it uses symmetry and independence property without further clarification. I am not really sure what does symmetry property refer to.