Markov renewal process

A Markov renewal process is a random process that generalises the notion of Markovian jump processes. Other random processes like Markov chain, Poisson process, renewal process and Markov chain can be derived as a special case of an MRP (Markov renewal process).

Definition

Consider a state space S. Consider a set of random variables (X_n,T_n), where T_n are the jump times and X_n are the associated states in the Markov chain (see Figure). Let the inter-arrival time, τ_n = T_n − T_{n − 1}. Then the sequence (X_n, T_n) is called a Markov renewal process if

$\Pr(\tau_{n+1}\le t, X_{n+1}=j|(X_0, T_0), (X_1, T_1),\ldots, (X_n=i, T_n))=\Pr(\tau_{n+1}\le t, X_{n+1}=j|X_n=i)\, \forall n \ge1,t\ge0, i,j \in \mathrm{S}$

Relations to Standard Stochastic processes

1. If we define a new stochastic process Y_t = X_n in (T_n,T_n + 1), then the process Y_t is called a semi-Markov process. Note the main difference between an MRP and a semi-Markov process is that the former is defined as a two-tuple of states and times, whereas the latter is the actual random process that evolves over time. The entire process is not Markovian, i.e., memoryless, as happens in a CTMC. Instead the process is Markovian only at the specified jump instants. This is the rationale behind the name, Semi-Markov.
2. A semi-Markov process where all the holding times are exponentially distributed is called a continuous time Markov chain/process (CTMC). 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 CTMC.

   $\Pr(\tau_{n+1}\le t, X_{n+1}=j|(X_0, T_0), (X_1, T_1),\ldots, (X_n=i, T_n))=\Pr(\tau_{n+1}\le t, X_{n+1}=j|X_n=i)$

   $=\Pr(X_{n+1}=j|X_n=i)(1-e^{-\lambda t}), \forall n \ge1,t\ge0, i,j \in \mathrm{S}$

3. The sequence X_n in the MRP is a discrete-time Markov chain. In other words, if the time variables are ignored in the MRP equation, we end up with a DTMC.

   $\Pr(X_{n+1}=j|X_0, X_1, \ldots, X_n=i)=\Pr(X_{n+1}=j|X_n=i)\, \forall n \ge1, i,j \in \mathrm{S}$

4. If the sequence of τs are independent and identically distributed, and if their distribution does not depend on the state X_n, then the process is a renewal process. So, if the exact states are ignored and we have a chain of iid times, then we have a renewal process.

   $\Pr(\tau_{n+1}\le t|T_0, T_1, \ldots, T_n)=\Pr(\tau_{n+1}\le t)\, \forall n \ge1, \forall t\ge0$

See also

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

References and Further Reading

• Ross, S.M. (1995) Stochastic Processes. Wiley. ISBN 978-0471120629
• Jyotiprasad Medhi Stochastic Processes. New Age International. ISBN 978-0470270004
• Barbu, V.S, Limnios, N. (2008) Semi-Markov Chains and Hidden Semi-Markov Models toward Applications: Their Use in Reliability and DNA Analysis. ISBN 978-0387731711