Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Markov Chain - Random Walk

  1. Sep 8, 2011 #1
    Suppose X is a random walk with probability
    [itex]P(X_k=+1)=p [/itex] and [itex]P(X_k=-1)=q=1-p [/itex]
    and [itex]S_n=X_1+X_2+...+X_n [/itex]

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

    The above comes from a book on random walk, I attached a link here (page 36),
  2. jcsd
  3. Sep 8, 2011 #2
    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.
  4. Sep 9, 2011 #3


    User Avatar
    Science Advisor

    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)
  5. Sep 9, 2011 #4
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook