Markov renewal process

A Markov renewal process (MRP) is a random process in probability and statistics, which generalizes the concept of Markov jump processes. Other random processes, such as Markov chains, Poisson, and renewal processes, can be derived as special cases of Markov renewal processes (MRPs).

Definition

An illustration of a Markov renewal process

In the context of a jump process that takes states in a state space, We consider the set of random variables, which represents the jump times and ${\displaystyle \mathrm {S} .}$ We 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 inter-arrival time ${\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}}}$

Relation to other stochastic processes

1. Let ${\displaystyle X_{n}}$ and ${\displaystyle T_{n}}$ be as defined in the previous statement. Define 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/process (CTMC). 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 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}$

See also

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

References

1. Medhi, J. (1982). Stochastic processes. New York: Wiley & Sons. ISBN   978-0-470-27000-4.
2. Ross, Sheldon M. (1999). Stochastic processes (2nd ed.). New York [u.a.]: Routledge. ISBN   978-0-471-12062-9.
3. Barbu, Vlad Stefan; Limnios, Nikolaos (2008). Semi-Markov chains and hidden semi-Markov models toward applications: their use in reliability and DNA analysis. New York: Springer. ISBN   978-0-387-73171-1.