I am reading an article in which they discuss a specific Markov chain in an example, and it turns out I need to sharpen up my Markov knowledge.
First the setup.
I have a continuous time Markov chain $(Y(t))_{t\geq 0}$ with discrete state space $S$. I have some subset $B\subset S$, and I have a point $x_0\not\in B$, such that the chain $Y$ starts at $x_0$.
Let $0\leq T_1\leq T_2\leq\cdots$ be the jump times of this Markov chain, and let $T_0=0$. Define the discrete skeleton Markov chain $(X_j)_{j\in\mathbb{N}}$ by $X_j=Y(T_j)$, and define then the stopping time $\tau_B$ by $$\tau_B = \inf\{j>0\ |\ X_j\in B\},$$ so that $\tau_B$ is the first index of $X$ for which $X$ enters the set $B$. Define also the time $\widetilde{\tau}_B$ until we reach the set $B$ as $$\widetilde{\tau}_B = \sum_{j=0}^{\tau_B-1}(T_{j+1}-T_j) = T_{\tau_B}.$$ Now, let $\Delta_j = \mathbb{E}[T_{j+1}-T_j|X_j]$, so that $\Delta_j$ is the expected time in state $X_j$. Notice that this is a random variable.
My first question is the following. The article notes that $\Delta_j$ is the inverse of the jump rate out of the state $X_j$, but I don't know what this means. Perhaps if $T_{j+1}-T_j|X_j=x$ has an exponential distribution with distribution function $F(t) = 1-\exp{(-\lambda_x)}$, I get something that has mean value equal to $\frac{1}{\lambda_x}$, and if $\lambda_x$ qualifies as the "jump rate", I guess I am done. But what is really the jump rate of a Markov chain, and why (if true) is the difference $T_{j+1}-T_j$ exponentially distributed given $X_j$? Do I need extra assumptions on the chain for this to be true?
Furthermore, the article gives the following expression for the mean value until first reaching $B$: $$\mathbb{E}[\widetilde{\tau}_B]=\mathbb{E}\left[\sum_{j=0}^{\tau_B-1}\Delta_j\right].$$ My second question is, how did this equality occur? My thoughts so far are: $$\mathbb{E}[\widetilde{\tau}_B] = \mathbb{E}\left[\sum_{j=0}^{\tau_B-1}T_{j+1}-T_j\right]=\mathbb{E}\left[\mathbb{E}\left[\sum_{j=0}^{\tau_B-1}T_{j+1}-T_j\ |\ X_0,X_1,\ldots,X_{\tau_B}\right]\right].$$
Since $\tau_B$ is determined by the chain up until time $\tau_B$, I can move the sum outside of the inner expectation, so that $$\mathbb{E}\left[\mathbb{E}\left[\sum_{j=0}^{\tau_B-1}T_{j+1}-T_j\ |\ X_0,X_1,\ldots,X_{\tau_B}\right]\right]=\mathbb{E}\left[\sum_{j=0}^{\tau_B-1}\mathbb{E}\left[T_{j+1}-T_j\ |\ X_0,X_1,\ldots,X_{\tau_B}\right]\right].$$ Now, if I could remove every step of the chain except for the $j$th one in this last expression, I would be done. Can I do this, and why? I can probably remove the past steps $X_0,X_1,\ldots,X_{j-1}$ (why? this is not precisely the Markov condition), but can I also remove the future steps $X_{j+1},\ldots$?
EDIT: It is example 1 on page 3 of this article: http://www.irisa.fr/armor/Rare/Publis/split.pdf
Best regards.
1) Yes, you are correctly interpreting the "jump rate out."
If we are in state 1 and there are two arrows pointing out to states 2 and 3, they are labeled with "transition rates" $q_{12}$ and $q_{13}$. This means there are two independent racing exponential random variables $Z_{12}$ and $Z_{13}$ with rates $q_{12}$, $q_{13}$, respectively. We transition according to which one "wins" (meaning which one comes first). The winning time is $\min[Z_{12},Z_{13}]$, which is again exponentially distributed with rate $q_{12} + q_{13}$ and mean $1/(q_{12} + q_{13})$.
So, if we are in state $j$, we can define $v_j$ as the sum of transition rates out:
$$ v_j = \sum_{k\neq j} q_{jk} $$
and the time to transition out is exponential with rate $v_j$ and mean $1/v_j$ (recall that an exponential random variable with rate $\lambda$ has mean $1/\lambda$).
You can prove that the minimum of independent exponential random variables $Z_1, \ldots, Z_n$ with rates $\mu_1, \ldots, \mu_n$ is again exponential with rate $\mu_1+\ldots+\mu_n$ by:
\begin{align} Pr[\min[Z_1,\ldots, Z_n]>z] &=Pr[Z_1>z,Z_2>z, \ldots, Z_n>z] \\ &= Pr[Z_1>z]Pr[Z_2>z]\ldots Pr[Z_n>z] \\ &= e^{-\mu_1 z} e^{-\mu_2 z} \ldots e^{-\mu_n z} \\ &= e^{-(\mu_1+\ldots+\mu_n)z} \end{align}
2) The sum of already-conditioned random variables was more tricky than I first thought and the basic law of iterated expectations I gave in my comments is true but doesn't seem to help. I like your derivation as is. You can indeed say:
$$ E[T_{j+1}-T_j|X_0, \ldots, X_{\tau_B}] = E[T_{j+1}-T_j|X_j, \ldots, X_{\tau_B}] $$
by the standard Markov properties. You can also say:
$$ E[T_{j+1}-T_j|X_j, \ldots, X_{\tau_B}] = E[T_{j+1}-T_j|X_j,X_{j+1}] $$
since future events after we transition to $j+1$ are independent of the transition time from $X_j$ to $X_{j+1}$. To remove the $X_{j+1}$ conditioning, you need another fact of continuous time Markov chains that the transition time is in fact independent of the state that we visit next (the "winning time" is independent of the state that wins).
I could not easily find online links anywhere, so here is one way to prove that the winning time is independent of who wins: Let $X$ and $Y$ be independent exponential random variables with rates $\lambda$ and $\mu$, respectively. Define $T=\min[X,Y]$. Recall that $T$ is exponential with rate $\lambda + \mu$.
Claim: For all $t>0$:
$$ Pr[X<Y|T=t] = Pr[X<Y] = \frac{\lambda}{\lambda+ \mu} $$
Proof: Fix $\delta>0$. Then for small $\delta$:
\begin{align} Pr[X<Y|T=t] &\approx Pr[X<Y | T \in [t, t+\delta]] \\ &= \frac{Pr[X<Y, T \in [t, t+\delta]]}{Pr[T \in [t, t+\delta]]} \\ & = \frac{Pr[X<Y, X \in [t, t+\delta]]}{Pr[T \in [t, t+\delta]]} \\ &= \frac{\int_{x=t}^{t+\delta} f_X(x)e^{-\mu x}dx}{\int_{x=t}^{t+\delta} f_T(x)dx} \end{align}
Taking a limit as $\delta \rightarrow 0$ and using L'Hopital's rule for $0/0$ gives:
\begin{align} \lim_{\delta\rightarrow 0} \frac{\int_{x=t}^{t+\delta} f_X(x)e^{-\mu x}dx}{\int_{x=t}^{t+\delta} f_T(x)dx} &= \lim_{\delta\rightarrow 0} \frac{f_X(t+\delta)e^{-\mu(t+\delta)}}{f_T(t+\delta)} \\ &=\lim_{\delta\rightarrow 0} \frac{\lambda e^{-\lambda (t+\delta)}e^{-\mu(t+\delta)}}{(\lambda + \mu)e^{-(\lambda + \mu)(t+\delta)}}\\ &=\frac{\lambda}{\lambda + \mu} \end{align}