Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.