Independence of random variables derived from a Random walk

Question

Let $w=(w_x)_{x \in \mathbb Z}$ be i.i.d random variables taking values in $(0,1)$. Let $(X_n)_{n \in \mathbb{N}_0} (\mathbb{N} \cup {0})$ be a Markov chain (more specifically a simple random walk starting at $0$ i.e $X_0 =0$) on $\mathbb Z$. Define the transition probabilities for each $w$, $$P_w(X_{n+1}=y| X_n=x)=\begin{cases} w_x& \text{if}\,\,y=x+1\\ 1-w_x& \text{if}\,\, y=x-1\\ 0 &\text{otherwise}\end{cases}$$. Define $a_k = \inf\{n\geq 0: X_n=k\}$, where $k \in \mathbb N_0$. Now define $b_k = a_k-a_{k-1}$. So $(b_k)_{k \in \mathbb N_0}$ is another sequence of random variables. I am not able to figure out why is $(b_k)$ independent but not identical random variables.

Answer 1

For this to be a Markov chain, the probability specification must be so that $$ P_w(X_{n+1}=y| X_n=x)=\begin{cases} w_x& \text{if}\,\,y=x+1\\ 1-w_x& \text{if}\,\, y=x-1\\ 0 &\text{otherwise}\end{cases} $$ independent of all earlier steps. So we can write that $$ X_{n+1} = X_n + Z_n $$ where $Z_n$ is plus or minus 1 with probabilities given by $w_{X_n}$ where we can assume that all $w_i$ are drawn before the walk starts. All the $Z_n$ are independent. Now, $a_k$ is an increasing sequence, so $b_k$ cannot be negative. Without knowledge of the distribution of $w_i$, we cannot prove that all the $b$'s are defined, the random walk is not guaranteed to eventually converge to $+\infty$! In the following we will ignore this problem.

Suppose $a_{k-1}=m_1, a_k=m_2$ so that $b_k=m_2 - m_1$, then we have $x_{m_1}=k-1, X_{m_2}=k$ so that $$ X_{m_1+1} = k-1+Z_{m_1}, \\ X_{m_1+2}= k-1 +Z_{m_1} + Z_{m_1 +1}, \\ \dots \\ X_{m_1 +(m_2-m_1)}=k-1+Z_{m_1}+Z_{m_1+1}+\dots +Z_{m_2-1} \\ = k $$ so that $Z_{m_1}+Z_{m_1+1}+\dots +Z_{m_2-1}=1$ and is $\le 0$ for all lesser last indices (than $m_2-1$). This implies that, given $a_{k-1}=m_1$, $b_k$ is a function of $Z_{m_1}, Z_{m_1+1}, \dots, Z_{m_2-1}$ so each new $b_k$ depends on disjoints blocks of $Z$'s, which suffices to prove independence.