First of all, I know nothing about Markov chains, and I'd like to prove the following without using the theory around them.
Let $(M_{n})_{n\geq 1}$ be a random walk over $\mathbb{Z}$, starting at $M_{0} = 0$, and defined by $M_{n} = \sum\limits_{i=1}^{n}Y_{i}$, where $(Yn)_{n\geq 1}$ are iid random variables with $P(Y_{i} = 1) = p$ and $P(Y_{i} = -1) = 1-p$.
Let $$S_{a, b} = \lbrace M_{i} \neq 0, a \leq i < b, \text{ and } M_{b} = 0 \rbrace$$ and $$S_{a, b}' = \lbrace M_{i}-M_{a-1} \neq 0, a \leq i < b, \text{ and } M_{b} - M_{a-1} = 0 \rbrace$$
The two things I want to prove are :
- $S_{a, b}$ and $S_{b+1, c}'$ are independent
- $P(S_{a+1, b}') = P(M_{i-a} \neq 0, a+1 \leq i <b, \text{ and } M_{b-a} = 0$)
But I'd like to do so by using simple arguments, such as counting the paths on the graph, etc...
1.
For $i\lt j,\; M_j-M_i$ is a function of $X_{i+1},\ldots,X_j$ only. So event $S_{b+1,c}^{'}$ involves r.v.'s $X_{b+1},\ldots,X_c$ only.
Also, $M_i$ is a function of $X_1,\ldots,X_i$ only. So event $S_{a,b}^{'}$ involves r.v.'s $X_1,\ldots,X_b$ only.
By independence of $X_1,X_2,\ldots,\;$ the events $S_{a,b}$ and $S_{b+1,c}^{'}$ are independent.
2.
Any path in $S_{a+1,b}^{'}$ is such that the sub-path between $a$ and $b$ (length $b-a$ steps) returns for the first time to its starting value, $M_a$, at $b$.
Any path in event $T := \{M_{i-a}\neq 0, a+1\leq i \lt b, M_{b-a}=0 \}$ (i.e. $\{M_1\neq 0, M_2\neq 0, \cdots, M_{b-a-1}\neq 0, M_{b-a}=0\}$) is such that the sub-path between $0$ and $b-a$ (length $b-a$ steps) returns for the first time to its starting value, $M_0=0$, at $b-a$.
Clearly, there is a $1-1$ correspondence between such sub-paths in $S_{a+1,b}^{'}$ and $T$. Hence, $P(S_{a+1,b}^{'}) = P(T)$.