# Difference in markov chain persistense probability

I feel confused! Suppose that we are given a markov chain that has transition rates for each $q_{ij}$. So you can multiply the matrix $[p_1,p_2,\ldots,p_n] Q=0$ and solve the system. $p_1, p_2, \ldots$ in my notes are persistence state probabilties.

However in my notes if you know the transition probability $p_{ij}$ you can multiply again the matrix $P$ like that $[p_1,p_2,\ldots]=[p_1,p_2,\ldots]P$ and get $p_1,p_2$ etc...

That confuses me. Is the result referring to the same probabilities? What is the difference?

-
I think you need to make your question more precise. –  Ashok Feb 17 '12 at 5:28
Perhaps you are mixing up continuous-time Markov chains (which have transition rates) and discrete-time Markov chains (which have transition probabilities)? –  Nate Eldredge Feb 17 '12 at 17:24
@NateEldredge yes.. i thought that this was the difference but both probabilities seem the same –  Parhs Feb 17 '12 at 18:01
Rates are not probabilities! –  Nate Eldredge Feb 17 '12 at 18:26

## 1 Answer

Each continuous-time Markov chain is described by a family of nonnegative rates $r_{ij}$ indexed by $i\ne j$, and summarized by the unique matrix $Q=(q_{ij})$ such that $q_{ij}=r_{ij}$ for every $i\ne j$ and $q_{ii}=-\sum\limits_{j\ne i}r_{ij}=-\sum\limits_{j\ne i}q_{ij}$ for every $i$. Then $Q$ is called the transition rate matrix and stationary distributions $p$ solve the equation $pQ=0$.

Each discrete-time Markov chain is described bya family of nonnegative transition probabilities $p_{ij}$ indexed by $i$ and $j$, such that $\sum\limits_{j}p_{ij}=1$ for every $i$, and summarized by the matrix $P=(p_{ij})$. Then $P$ is called the transition probability matrix and stationary distributions $p$ solve $pP=p$.

Every transition rate matrix $Q$ gives rise to infinitely many transition probability matrices $P_t=\mathrm e^{tQ}$, for every nonnegative real number $t$. Recall that, by definition, $$\mathrm e^{tQ}=\sum\limits_{n=0}^{+\infty}\frac{t^n}{n!}Q^n=I+\sum\limits_{n=1}^{+\infty}\frac{t^n}{n!}Q^n,$$ and note that every $P_t$ is indeed a transition matrix. First, the sum of the coefficients of each line of $Q^n$ is zero for every $n\geqslant1$ and the sum of the coefficients of each line of $I$ is $1$ hence, summing up these contributions, one sees that the sum of the coefficients of each line of $\mathrm e^{tQ}$ is equal to $1$, as it should be. Second, choosing $a\geqslant -q_{ii}$ for every $i$, one gets a matrix $Q_a=aI+Q$ with nonnegative coefficients hence $$\mathrm e^{tQ}=\mathrm e^{-at}\mathrm e^{tQ_a}=\mathrm e^{-at}\sum\limits_{n=0}^{+\infty}\frac{t^n}{n!}(Q_a)^n,$$ which shows that indeed every coefficient of $\mathrm e^{tQ}$ is nonnegative, as it should.

Likewise, if $p$ is stationary for $Q$, then $pQ^n=0$ for every $n\geqslant1$ hence $pP_t=p$ for every nonnegative $t$, that is, $p$ is also stationary for every $P_t$. In the other direction, if $p$ is stationary for $P_t$ for every $t\geqslant0$, then $p$ is also stationary for $Q$ since $Q=\lim\limits_{t\to0}\frac1t(P_t-I)$ hence $pP_t=p$ for every $t$ implies $pQ=\lim\limits_{t\to0}\frac1t(pP_t-p)=\lim\limits_{t\to0}0=0$.

However, not every transition probability matrix $P$ can be written as $P=\mathrm e^{tQ}$ for some nonnegative $t$ and some transition rate matrix $Q$. When this is possible, one says $P$ is embeddable (in a Markov continuous-time semi-group). For example, $P=\begin{pmatrix}1-x & x\\ y & 1-y\end{pmatrix}$ with $x$ and $y$ in $[0,1]$ is embeddable if and only if $x+y\lt1$. There is no complete characterization of embeddability in every dimension but easy obstructions to embeddability are based on the following: if $P$ is embeddable then $P_{ii}\ne0$ for every state $i$; if $P$ is embeddable, $P_{ij}\ne0$ and $P_{jk}\ne0$ implies $P_{ik}\ne0$, for every states $i$, $j$ and $k$. There are other, less simple, necessary conditions for embeddability, based on the configuration of the eigenvalues of $P$.

-