Why Do Lines 3 and 4 Equate in Random Walk Probability Calculations?

[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 X_i'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 X_i'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 don't 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 don't 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.

 

[blue_raver22]

for your question! I can explain why lines 3 and 4 are equal in this context. First, let's review the definition of a random walk. A random walk is a mathematical model that describes the movement of a "walker" on a number line. At each step, the walker moves either to the left or right with a certain probability. In this case, the walker has a probability of p to move to the right and a probability of q (1-p) to move to the left.

Now, let's look at the expression in line 3: P(S_k-S_0≠0 ,S_k-S_1≠0 ,…,S_k-S_{k-1}≠0). This is the probability that the walker is not at the starting point (S_0) and has not passed through any of the previous points (S_1, S_2, ..., S_{k-1}) up to the kth step. This can also be written as P(X_k+X_{k-1}+⋯+X_1≠0 ,X_k+X_{k-1}+⋯+X_2≠0 ,…,X_k≠0) because S_n=X_1+X_2+...+X_n.

Now, let's look at the expression in line 4: P(X_1≠0 ,X_2+X_1≠0 ,…,X_k+X_{k-1}+⋯+X_1≠0). This is the probability that the walker's first step (X_1) is not at the starting point (S_0), the second step (X_2) is not at the first point (S_1), and so on up to the kth step (X_k) not being at any of the previous points (S_1, S_2, ..., S_{k-1}). This is equivalent to the previous expression because the walker is still not at any of the previous points and has not returned to the starting point.

In summary, lines 3 and 4 are equal because they both represent the probability that the walker has not passed through any of the previous points up to the kth step. This is a fundamental property of random walks and is why the expressions are interchangeable. I hope this helps to clarify the