Markov renewal process

Markov renewal processes are a class of random processes in probability and statistics that generalize the class of Markov jump processes. Other classes of random processes, such as Markov chains and Poisson processes, can be derived as special cases among the class of Markov renewal processes, while Markov renewal processes are special cases among the more general class of renewal processes.

Definition

File:Marked point process.png

An illustration of a Markov renewal process

In the context of a jump process that takes states in a state space $S$ , consider the set of random variables $(X_{n}, T_{n})$ , where $T_{n}$ represents the jump times and $X_{n}$ represents the associated states in the sequence of states (see Figure). Let the sequence of inter-arrival times $τ_{n} = T_{n} - T_{n - 1}$ . In order for the sequence $(X_{n}, T_{n})$ to be considered a Markov renewal process the following condition should hold: $\begin{aligned} \Pr (τ_{n + 1} \leq t, X_{n + 1} = j ∣ (X_{0}, T_{0}), (X_{1}, T_{1}), \dots, (X_{n} = i, T_{n})) \\ = & \Pr (τ_{n + 1} \leq t, X_{n + 1} = j ∣ X_{n} = i) \forall n \geq 1, t \geq 0, i, j \in S \end{aligned}$

Relation to other stochastic processes

Let $X_{n}$ and $T_{n}$ be as defined in the previous statement. Defining a new stochastic process $Y_{t} : = X_{n}$ for $t \in [T_{n}, T_{n + 1})$ , then the process $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.)
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.
$\begin{aligned} \Pr (τ_{n + 1} \leq t, X_{n + 1} = j ∣ (X_{0}, T_{0}), (X_{1}, T_{1}), \dots, (X_{n} = i, T_{n})) \\ = & \Pr (τ_{n + 1} \leq t, X_{n + 1} = j ∣ X_{n} = i) \\ = & \Pr (X_{n + 1} = j ∣ X_{n} = i) (1 - e^{- λ_{i} t}), for all n \geq 1, t \geq 0, i, j \in S, i \neq j \end{aligned}$
The sequence $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.
$\Pr (X_{n + 1} = j ∣ X_{0}, X_{1}, \dots, X_{n} = i) = \Pr (X_{n + 1} = j ∣ X_{n} = i) \forall n \geq 1, i, j \in S$
If the sequence of $τ$ s is independent and identically distributed, and if their distribution does not depend on the state $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.
$\Pr (τ_{n + 1} \leq t ∣ T_{0}, T_{1}, \dots, T_{n}) = \Pr (τ_{n + 1} \leq t) \forall n \geq 1, \forall t \geq 0$

References

↑ Medhi, J. (1982). Stochastic processes. New York: Wiley & Sons. ISBN 978-0-470-27000-4.
↑ Ross, Sheldon M. (1999). Stochastic processes (2nd ed.). New York [u.a.]: Routledge. ISBN 978-0-471-12062-9.
↑ 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.

[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.

[1]

[2]

[3]

Markov renewal process

Contents

Definition

Relation to other stochastic processes

See also

References

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools

In other projects

In other languages