Semi-Markov Process

In probability and statistics, a Markov renewal process (MRP) is a random process that generalizes the notion of Markov jump processes. Other random processes like Markov chains, Poisson processes and renewal processes can be derived as special cases of MRP's.

Definition

Consider a state space $\mathrm.$ 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, $\tau_n=T_n-T_$. Then the sequence $(X_n,T_n)$ is called a Markov renewal process if

:
\begin
& \Pr(\tau_\le t, X_=j\mid(X_0, T_0), (X_1, T_1),\ldots, (X_n=i, T_n)) \\ pt= & \Pr(\tau_\le t, X_=j\mid X_n=i)\, \forall n \ge1,t\ge0, i,j \in \mathrm
\end

Relation to other stochastic processes

# If we define a new stochastic process $Y_t:=X_n$ for t \in _n,T_),_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_and_any_realisation_of_the_process_has_a_defined_state_for_''any''_given_time._The_entire_process_is_not_Markovian,_i.e.,_memoryless,_as_happens_in_a_Continuous-time_Markov_process.html" ;"title="tuple.html" ;"title="_n,T_), 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">_n,T_), 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 and any realisation of the process has a defined state for ''any'' given time. The entire process is not Markovian, i.e., memoryless, as happens in a Continuous-time Markov process">continuous time Markov chain/process (CTMC). Instead the process is Markovian only at the specified jump instants. This is the rationale behind the name, ''Semi''-Markov. (See also: hidden semi-Markov model.)
# A semi-Markov process (defined in the above bullet point) where all the holding times are exponential distribution, exponentially distributed is called a 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.
#: \begin
& \Pr(\tau_\le t, X_=j\mid(X_0, T_0), (X_1, T_1),\ldots, (X_n=i, T_n)) \\ pt= & \Pr(\tau_\le t, X_=j\mid X_n=i) \\ pt= & \Pr(X_=j\mid X_n=i)(1-e^), \text n \ge1,t\ge0, i,j \in \mathrm, i \ne j
\end

# 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_=j\mid X_0, X_1, \ldots, X_n=i)=\Pr(X_=j\mid X_n=i)\, \forall n \ge1, i,j \in \mathrm$
# If the sequence of $\tau$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 states are ignored and we have a chain of iid times, then we have a renewal process.
#:$\Pr(\tau_\le t\mid T_0, T_1, \ldots, T_n)=\Pr(\tau_\le t)\, \forall n \ge1, \forall t\ge0$

See also

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

References

{{Reflist

Markov processes