= Transition-completion time in a Markov chain
For a <Markov chain> with <transition matrix> $P$, fix a <transition probability>[directed transition] $(u,v)$ with $P_{uv}>0$. Its transition-completion time is
$$
T_{uv}=\inf\{n\geq1:(X_{n-1},X_n)=(u,v)\}.
$$
It counts the successful final step. Merely visiting $v$ by another route does not complete this <event>. In a finite <irreducible Markov chain>[irreducible] chain its <mean> $g_i=\mathbb E_iT_{uv}$ is finite and <first-step analysis> gives
$$
g_i=1+\sum_jP_{ij}g_j-\mathbf1_{\{i=u\}}P_{uv}g_v.
$$
The subtracted continuation term removes exactly the case where the designated transition has just succeeded. An equivalent construction sends that transition to a new absorbing success state and computes its <Expected hitting time>.
For the two-state chain $P_{01}=p$, $P_{10}=q$, with $0<p,q\leq1$, the waiting time for $0\to1$ has <means> $g_0=1/p$ and $g_1=1/q+1/p$. Starting at one, the <hitting time> of state one is zero, whereas the transition-completion time must first wait for $1\to0$ and then $0\to1$. This example makes the difference between an <edge> <event> and a state <event> explicit.
Back to article page