Markov renewal process

An illustration of a Markov renewal process

In the context of a jump process that takes states in a state space ${\displaystyle \mathrm {S} }$, consider the set of random variables ${\displaystyle (X_{n},T_{n})}$, where ${\displaystyle T_{n}}$ represents the jump times and ${\displaystyle X_{n}}$ represents the associated states in the sequence of states (see Figure). Let the sequence of inter-arrival times ${\displaystyle \tau _{n}=T_{n}-T_{n-1}}$. In order for the sequence ${\displaystyle (X_{n},T_{n})}$ to be considered a Markov renewal process the following condition should hold:

${\displaystyle {\begin{aligned}&\Pr(\tau _{n+1}\leq t,X_{n+1}=j\mid (X_{0},T_{0}),(X_{1},T_{1}),\ldots ,(X_{n}=i,T_{n}))\\[5pt]={}&\Pr(\tau _{n+1}\leq t,X_{n+1}=j\mid X_{n}=i)\,\forall n\geq 1,t\geq 0,i,j\in \mathrm {S} \end{aligned}}}$

1. Let ${\displaystyle X_{n}}$ and ${\displaystyle T_{n}}$ be as defined in the previous statement. Defining a new stochastic process ${\displaystyle Y_{t}:=X_{n}}$ for ${\displaystyle t\in [T_{n},T_{n+1})}$, then the process ${\displaystyle Y_{t}}$ is called a semi-Markov process as it happens in a continuous-time Markov chain. The process is Markovian only at the specified jump instants, justifying the name semi-Markov.[1][2][3] (See also: hidden semi-Markov model.)
2. A semi-Markov process (defined in the above bullet point) in which all the holding times are exponentially distributed is called a continuous-time Markov chain. In other words, if the inter-arrival times are exponentially distributed and if the waiting time in a state and the next state reached are independent, we have a continuous-time Markov chain.

   ${\displaystyle {\begin{aligned}&\Pr(\tau _{n+1}\leq t,X_{n+1}=j\mid (X_{0},T_{0}),(X_{1},T_{1}),\ldots ,(X_{n}=i,T_{n}))\\[3pt]={}&\Pr(\tau _{n+1}\leq t,X_{n+1}=j\mid X_{n}=i)\\[3pt]={}&\Pr(X_{n+1}=j\mid X_{n}=i)(1-e^{-\lambda _{i}t}),{\text{ for all }}n\geq 1,t\geq 0,i,j\in \mathrm {S} ,i\neq j\end{aligned}}}$

3. The sequence ${\displaystyle X_{n}}$ in the Markov renewal process is a discrete-time Markov chain. In other words, if the time variables are ignored in the Markov renewal process equation, we end up with a discrete-time Markov chain.

   ${\displaystyle \Pr(X_{n+1}=j\mid X_{0},X_{1},\ldots ,X_{n}=i)=\Pr(X_{n+1}=j\mid X_{n}=i)\,\forall n\geq 1,i,j\in \mathrm {S} }$

4. If the sequence of ${\displaystyle \tau }$s is independent and identically distributed, and if their distribution does not depend on the state ${\displaystyle X_{n}}$, then the process is a renewal. So, if the states are ignored and we have a chain of iid times, then we have a renewal process.

   ${\displaystyle \Pr(\tau _{n+1}\leq t\mid T_{0},T_{1},\ldots ,T_{n})=\Pr(\tau _{n+1}\leq t)\,\forall n\geq 1,\forall t\geq 0}$

• Markov process
• Renewal theory
• Variable-order Markov model
• Hidden semi-Markov model