Understanding the Difference Between Different Types of Markov Chains?

Question

I have been trying to learn more about different types of Markov Chains. So far, here is my basic understanding of them:

Discrete Time Markov Chain: Characterized by a constant transition probability matrix "P"

Continuous Time Markov Chain: Characterized by a time dependent transition probability matrix "P(t)" and a constant infinitesimal generator matrix "Q". The Continuous Time Markov Chain is based on the Exponential Distribution (i.e. sojourn times/holding times must be Exponentially Distributed) and thereby must obey the Memoryless Property.

Non Homogenous Continuous Time Markov Chain: Characterized by a time dependent transition probability matrix "P(t)" and a time dependent infinitesimal generator matrix "Q(t)". Non Homogenous Continuous Time Markov Chains are not necessarily based on the Exponential Distribution and thereby do not need to obey the Memoryless Property.

This brings me to my question - given the above information, I am having difficulty understanding the difference between these Markov Chains and a Semi-Markov Process.

Based on some readings that I have done, it seems like a Semi Markov Process is characterized by its "Sojourn Time" - that is, the amount of time that is spent in some state. Since the probability distribution of this "Sojourn Time" does not necessarily need to be Exponentially Distributed, a Semi Markov Process does not need to obey the Memoryless Property. If this is the case, then how exactly is the Semi-Markov Process different from a Non Homogenous Continuous Time Markov Chain?

Can someone please help me understand this? Perhaps some example could illustrate in which conditions it might be more advantageous to use a Semi-Markov Process compared to a Continuous Markov Process and vice versa?

Note: I am currently reading this reference : https://math.stackexchange.com/questions/2960929/difference-between-non-homogeneous-markov-and-semi-markov

• Note 1: I understand that as the name suggests, "Semi-Markov" does not need to obey the "Markov Property". That is, in Semi-Markov, the future states that the process can go to does not only depend on the current state, and can also depend on the history of the process. This is in contrast to a Continuous Markov Process in which the Markov Property must be obeyed, and the future state of a Continuous Markov Process can only depend on the current state.

• Note 2: I am told that one of the differences between Semi-Markov and Markov is how the notion of time is recorded. In a Continuous Markov Process, time is recorded in the "clock forward" format - this means that all time transitions are recorded from some initial time. In a Semi Markov Process, time is recorded in the "clock reset" format - this means that the clock is restarted every time a transition is recorded. Supposedly, "clock forward" is not able to take into consideration the history of the Markov Process - whereas "clock reset" is able to take into consideration the history of the Markov Process. However, I do not understand this point - I am not sure as to why recording time using different formats "magically" allows the Markov Process to consider the history or not to consider the history of the process.

• Note 3: It seems to me like a Semi Markov Process is closer to a "Discrete Markov Chain" : If my understanding is correct, a Semi Markov Process does not have a P(t) matrix or any type of Q matrix - a Semi Markov Process only has a time independent P matrix. Is this correct?

• Note 4: Again, if my understanding is correct, it seems as though a Semi Markov Process might not be as useful for modelling real world phenomena compared to a Continuous Markov Process (i.e. when modelling a person transitioning between medical condition, it will likely be useful to know the history of how long he has been healthy or sick) - with this being said, in what kinds of situations is it useful to use Semi Markov Processes?

Answer 1

I think i can provide you with a good illustrative example of what user350942 described in your link.

Consider $X_t$ the stochastic process containing the state of a patient in the ICU. $t = 0$ is ICU admission and the possible sates are just intubated, non intubated and as absorbing states you get dismissed and dead. In this example nobody ever comes back to the ICU after being dismissed.

Now we get 4 doctors with different ideas about what kind of process $X_t$ is, asking the only questions that matter according to their opinion:

1st: Doctor Time Homogeneous Markov Chain asks only one question "What state is the patient in?", the nurse replies: "They are intubated". The doctor thinks that's bad but not terrible.

2nd: Doctor Time Inhomogeneous Markov Chain asks only two questions "What state is the patient in and how long has he been in the ICU?", the nurse replies: "They are intubated and they've been in the ICU for 30 days". The doctor thinks that's terrible. This doctor doesn't care what happened in the 30 days, beyond the patient now being intubated, so his believes about $X_t$ are still Markov even if he includes $t$, because there was always going to be a state of the patient at that point in time.

3rd: Doctor Time Homogeneous Semi Markov Chain asks only two questions "What state is the patient in and how long has he been in that state?", the nurse replies: "They are intubated and they've been intubated 2 days ago". The doctor thinks that's not all that bad. Now this doctor believes, that the patient not being intubated slightly more than 2 days ago changes the probabilities of their future development. Therefore he does not believe that $X_t$ is strictly Markov.

4th: Doctor Time Inhomogeneous Semi Markov Chain is a workaholic and asks three questions "What state is the patient in, how long has he been in that state and how long has he been in the ICU?", the nurse replies: "They are intubated, they've been intubated 2 days ago and ICU admittance was 30 days ago". The doctor thinks that, when put together, this is bad but not terrible.

In principle the 4th doctor is probably right but of course more complex models require more data and, if the time effects aren't huge, the time homogeneous Markov Chain might very well be the only model with reasonable estimates.

Whether time is continuous or discrete isn't relevant for the distinction between these four different types. With discrete time, like only looking at patient development in full days, you have actual probabilities for each individual day, while with continuous time you are looking at all possible moments and the probability of something happening in an individual, infinitely short moment is of course 0. Instead you just have some abstract background risk, which expresses itself through mathematical machinery.

Answer 2

Let's rewind the definitions.

Definition $1.$ Let $E$ be a Polish space. Consider $\langle X_t\rangle_{t\in\mathcal I\subset \mathbb R}$ an $E$-valued stochastic process. It follows the Markov property if $$\mathbf P[X_t\in A\mid \mathcal F_s] = \mathbf P[X_t\in A\mid X_s,]~~~~\forall A\in \mathfrak B(E),~\forall s,t\in \mathcal I\wedge (s\leq t) \tag 1\label 1.$$

Any process following $\eqref 1$ is a Markov Process. With $E$ being countable and $\mathcal I = \mathbb N_0,$ the process becomes discrete Markov chain.

$\bullet$ Does the specification of homogeneous and non-homogeneous change the defining property of the Markov process, viz. $\eqref 1?$

Defintion $2.$ $\langle X_n, T_n \rangle_{n\in \mathbb N}$ is a Markov renewal process if $$\mathbf P[ X_{n+1}=j, ~T_{n+1}- T_n\leq t\mid X_0,\ldots, X_n; T_0, \ldots,T_n] = \mathbf P[X_{n+1}=j,~ T_{n+1}- T_n\leq t\mid X_n]\tag 2\label 2.$$

It is assumed that $\langle \mathbf X, T\rangle$ is time-homogeneous i that $$\mathbf P[X_{n+1}=j,~ T_{n+1}- T_n\leq t\mid X_n] := Q(i, j, t)\tag 3$$ being independent of $n.$

Definition $3.$ Define $Y_t := X_n\cdot\mathbb I_{[T_n,~T_{n+1})}(t).$ Then $\langle Y_t\rangle$ is the semi-Markov process associated with $\langle X, T\rangle.$

$\bullet$ Markov property holds for $Y_t$ only at epochs $T_n.$

$\bullet$ The distribution of the sojourn time $T_{ij}$ can be anything.

$\bullet$ If $Q(i,j, t) = p_{ij}[1-e^{-\lambda(i)t}],$ then only the semi-Markov process becomes a time-homogeneous Markov process. $\langle Y_t\rangle$ is a Markov process.

Therefore, a Markov process has the Markov property at all times. A semi-Markov process has the Markov property only at epochs.

Addition of non-homogeneity doesn't make a drastic distinction. As aptly remarked here:

In effect a semi Markov process can have whatever transition probability dependence on time you like, whereas in a non-homogeneous Markov chain you will still always have the probability of a transition from $i$ to $j$ in $[t,t+h]$ being $q_{ij}(t)h+o(h). $

At the end of the day, it is always the case of whether the Markov property $\eqref 1$ has been followed throughout or only at some instances.

---

References:

$\rm [I]$ Introduction to Stochastic Processes, Erhan Çinlar, Dover Publications, $2013,$ chapter $10,$ p. $314.$

$\rm [II]$ Stochastic Processes, J. Medhi, New Academic Science Limited, $2012,$ chapter $7,$ p. $299.$