I want to know is there any literature on markov chains who's state transition probability matrix evolves over time?

For instance, I have 2 states, 1 and 2. With

$$P = \begin{bmatrix} p_{11} & p_{12} \\ p_{21} & p_{22} \end{bmatrix} = \begin{bmatrix} 0.9 & 0.1 \\ 0.8 & 0.2 \end{bmatrix}$$

Where $p_{ij}$ indicates the change that you jump from state $i$ to $j$.

Now at time $k$ I jump from 1 to 2, which has a 0.1 probability. The next instance $k+1$ I have a probability of 0.2 of staying in state 2. Now if I stay at $k+1$ in state 2 then the probability of staying in state 2 would increase and the probability of jumping from state 2 to 1 would decrease. Meaning that $P_{k+2}$ would, for instance have evolved to

$$P_{k+2} = \begin{bmatrix} 0.9 & 0.1 \\ 0.5 & 0.5 \end{bmatrix}$$

If I again stay in state 2 it increases further...

$$P_{k+3} = \begin{bmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \end{bmatrix}$$

If I then jump from state 2 to 1 it decreases...

$$P_{k+4} = \begin{bmatrix} 0.9 & 0.1 \\ 0.6 & 0.4 \end{bmatrix}$$

Now I want to know if there is any literature regarding this?


I believe my question is very much related to https://mathoverflow.net/questions/168398/time-inhomogeneous-markov-chains


2 Answers 2


This corresponds to any bivariate renewal process where one is given some positive integer valued independent $(U_i)$ i.i.d. and $(V_i)$ i.i.d. and one is at state $1$ at time $n$ if there exists some $k$ such that$$\sum_{i=1}^k(U_i+V_i)\leqslant n\lt U_{k+1}+\sum_{i=1}^k(U_i+V_i),$$ and one is at state $2$ otherwise.

The distributions of every $U_i$ and every $V_i$ are as follows: for every $n$, $P(U_i\geqslant n+1\mid U_i\geqslant n)$ is the probability to stay at state $1$ one more step when one is at state $1$ for $n$ steps, likewise, $P(V_i\geqslant n+1\mid V_i\geqslant n)$ is the probability to stay at state $2$ one more step when one is at state $2$ for $n$ steps.

In the example given in the post, this means that $$P(V=1)=0.8,\quad P(V=2)=0.2\times0.5,\quad P(V=3)=0.2\times0.5\times0.2.$$

  • $\begingroup$ So $P(V = 1)$ is the probability that one is in state 2 for 1 step? Should that not be $p_{k,12} = 0.1$ then? The probability of jumping from state 1 to 2? Assuming that interpretation of $P(V = 1)$ is correct. Then $P(V = 2) = p_{k,12} * p_{k+1,22}$ and $P(V = 3) = p_{k,12} * p_{k+1,22} * p_{k+2,22}$? $p_{k,ij}$ denotes the element $p_{ij}$ of the $P_k$th matrix. Sorry I am a bit confused. Also maybe see my added link in my post. $\endgroup$
    – WG-
    Sep 28, 2014 at 14:52
  • 1
    $\begingroup$ One stays in state 2 for 1 step when one leaves state 2 as soon as possible, thus, with probability $(P)_{2,1}=.8$. Likewise, $(V=2)$ corresponds first to a decision to stay at 2 (probability $(P)_{2,2}=.2$) and second to a decision, one time later, to leave state 2 (probability $(P_2)_{2,1}=.5$). $\endgroup$
    – Did
    Sep 28, 2014 at 15:49
  • $\begingroup$ Your setting is quite different from the one in the MO page since transitions in your model depend on the duration of the stay at the present state, that is, transitions at time $n$ are given by a matrix $P_{n-L_n}$, where $L_n$ is the time of arrival at present state, not $P_n$ as on the MO page. $\endgroup$
    – Did
    Sep 28, 2014 at 15:55
  • $\begingroup$ is it okay for you if I extend my question? I have a subsequent question namely which requires me to add more info. $\endgroup$
    – WG-
    Sep 28, 2014 at 16:07
  • $\begingroup$ Well, IF new problem, THEN new question on new page, no? $\endgroup$
    – Did
    Sep 28, 2014 at 16:10

Yes, this is a so-called "inhomogenous Markov chain". Some authors use the term "non-homogenous".

Please note that you are interested in Markov chains with discrete time which are different from models with continuous time.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .