Markov Chain - Random Walk

1. Sep 8, 2011

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),
Thanks

2. Sep 8, 2011

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.

3. Sep 9, 2011

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)

4. Sep 9, 2011

tanzl

Thanks for the replies.
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.
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.