Independence of time intervals between visits of a state $x$ on a Markov chain

The question is like the following,

Let $X_0,X_1,...,X_n,...$ be an irreducible Markov chain with finite state space. Define $τ_{x,0}^+=0$, and $τ_{x,k}^+=\min\{t:t>τ_{x,k-1}^+,X_t=x\}$. In plain words, $τ_{x,k}^+$ is the $k$th time when $x$ is visited. Let $I_k=τ_{x,k}^+-τ_{x,k-1}^+$ for $k≥1$, then $I_k$ is the $k$-th time interval between $(k-1)$th visit and $k$th visit. Show that $I_1,I_2,…,I_n$ are independent RVs for any finite $n$.

This is a very intuitive statement which I find trouble proving. Hope someone can help. Thank you!

My attempt:

Let $i_1,…,i_n$ be any non-negative integers, and I want to show

$\Bbb P\{I_n=i_n |I_{n-1}=i_{n-1},…,I_i=i_1 \}=\Bbb P\{I_n=i_n \}$

Let $s_k=i_1+⋯+i_k$ for $k=1,2,…,n$, then by Markov property

$\Bbb P\{I_n=i_n |I_{n-1}=i_{n-1},…,I_i=i_1 \}=\Bbb P\{X_{s_n }=x,X_{s_{n-1}}≠x,…,X_{s_{n-1}+1}≠x│X_{s_{n-1} }=x\}=\Bbb P\{X_{i_n }=x,X_{i_n-1}≠x,X_1≠x,│X_0=x\}$

However I got stuck with the right-hand-side. If we can transform $\Bbb P\{I_n=i_n \}$ to $\Bbb P\{X_{i_n }=x,X_{i_n-1}≠x,X_1≠x,│X_0=x\}$, then the proof is done.

• How do you define $I_k$ if the process does not visit $x$, i.e., if $\tau^+_{x,k-1}=\tau^+_{x,k}=\infty?$ – user940 Feb 13 '16 at 20:03
• @ByronSchmuland Thanks for asking. I checked the textbook. There is a theorem saying that when the state space is finite, then $\tau_{x,k}^+$ is always finite for every finite $k$. – Tony Feb 13 '16 at 20:23
• That is not true actually. Did the textbook say that the chain is irreducible? If so, you might add that crucial information to your question. – user940 Feb 13 '16 at 22:19
• @ByronSchmuland Oh... sorry. That's my fault. Yes, the assumption is the chain is irreducible. Thank you for pointing this out! – Tony Feb 13 '16 at 22:28

It is clear that $\{I_n=i_n \}=\{τ_{x,n}^+=τ_{x,n-1}^++i_n\}$, then

\eqalign{ & {\Bbb P}\left\{ {{I_n} = {i_n}} \right\} = \mathop \sum \limits_{t \geqslant n} {\Bbb P}\left\{ {\tau _{x,n}^ + = t + {i_n},\tau _{x,n - 1}^ + = t} \right\} \cr & = \mathop \sum \limits_{t \geqslant n - 1} {\Bbb P}\left\{ {{X_{t + {i_n}}} = x,{X_{t + {i_n} - 1}} \ne x, \ldots ,{X_{t + 1}} \ne x,\tau _{x,n - 1}^ + = t} \right\} \cr & = \mathop \sum \limits_{t \geqslant n - 1} {\Bbb P}\left\{ {{X_{t + {i_n}}} = x,{X_{t + {i_n} - 1}} \ne x, \ldots ,{X_{t + 1}} \ne x|\tau _{x,n - 1}^ + = t} \right\}{\Bbb P}\left\{ {\tau _{x,n - 1}^ + = t} \right\} \cr & = \mathop \sum \limits_{t \geqslant n - 1} {\Bbb P}\left\{ {{X_{t + {i_n}}} = x,{X_{t + {i_n} - 1}} \ne x, \ldots ,{X_{t + 1}} \ne x|{X_t} = x} \right\}{\Bbb P}\left\{ {\tau _{x,n - 1}^ + = t} \right\} \cr & = \mathop \sum \limits_{t \geqslant n - 1} {\Bbb P}\left\{ {{X_{{i_n}}} = x,{X_{{i_n} - 1}} \ne x, \ldots ,{X_1} \ne x|{X_0} = x} \right\}{\Bbb P}\left\{ {\tau _{x,n - 1}^ + = t} \right\} \cr & = {\Bbb P}\left\{ {{X_{{i_n}}} = x,{X_{{i_n} - 1}} \ne x, \ldots ,{X_1} \ne x|{X_0} = x} \right\}\mathop \sum \limits_{t \geqslant n - 1} {\Bbb P}\left\{ {\tau _{x,n - 1}^ + = t} \right\} \cr & = {\Bbb P}\left\{ {{X_{{i_n}}} = x,{X_{{i_n} - 1}} \ne x, \ldots ,{X_1} \ne x|{X_0} = x} \right\} \cr & = {\Bbb P}\left\{ {{I_n} = {i_n}|{I_{n - 1}} = {i_{n - 1}}, \ldots ,{I_i} = {i_1}} \right\} \cr}

The following equality is due to strong Markov property, since $\tau_{x,n-1}^+$ is a stopping time.

${\Bbb P}\left\{ {{X_{t + {i_n}}} = x,{X_{t + {i_n} - 1}} \ne x, \ldots ,{X_{t + 1}} \ne x|\tau _{x,n - 1}^ + = t} \right\} = {\Bbb P}\left\{ {{X_{t + {i_n}}} = x,{X_{t + {i_n} - 1}} \ne x, \ldots ,{X_{t + 1}} \ne x|{X_t} = x} \right\}$

Also $\mathop \sum \limits_{t \geqslant n - 1} {\Bbb P}\left\{ {\tau _{x,n - 1}^ + = t} \right\} = 1$ since the summation exhausts all possibilities for $t$.

• You should change "$X_t=x$" to "$\tau^+_{x,n-1}=t$" everywhere in your argument. – user940 Feb 13 '16 at 22:43
• @ByronSchmuland I edited my argument. Thank you! – Sherry Feb 13 '16 at 23:34