# Expression for the quotient between two stationary states in a Markov process

I've been thinking about this problem and I would appreciate some help. Consider a finite number of states ($n$) Markov process with transition matrix $Q_{n\times n}$ with the usual properties and definitions: $$\frac{q_{ij}}{\sum_{k=1, k\ne i}^{n} q_{ik}}= \frac{q_{ij}}{q_i}:=p_{ij}\quad\text{for }i\neq j;~~q_{ii}=-q_i\quad;~~p_{ii}=0~~.$$ Therefore the sum of the rows of $Q$ is zero and $p_{ij}$ are the transition probabilities of the embedded (or jump) chain. Lets assume that the process is irreducible and all transitions are possible. Let $\pi$ be the normalized stationary distribution, that is, $\sum\pi_i=1$ and $\pi^{\rm T}\cdot Q=0$. Given any two states ($i=1,2$, say) we need to prove (or disprove) that $$\pi_1 q_1 \mathbb{P(1\rightarrow2)}=\pi_2 q_2 \mathbb{P(2\rightarrow1)}~~,\quad(1)$$ where $\mathbb{P(1\rightarrow2)}$ is the probability (given that the start state is $1$) of all the jump chains that start in $1$ and end up in $2$ and do not get into states $1$ or $2$ any other time. Putting in another way (considering that each state will be visited an infinite number of times with probability 1) , it is the probability that the process will reach state $2$ before returning to $1$, given that it started in $1$. From this equation we can derive an expression for the quotient $\pi_1/\pi_2$ that, formally, depends on the $q_{ij}$.

The cases n=2,3, and 4

Here I show the first three cases for n. The result is trivial for $n=2$. For $n=3$ the paths that enter the calculation of $\mathbb{P}(1\rightarrow 2)$ are $12$ and $132$, therefore, equation (1) says $$\pi_1 q_1 (p_{12}+p_{13}p_{32})=\pi_2 q_2 (p_{21}+p_{23}p_{31})~~,\tag{2}$$ which is true. The $n=4$ case is more interesting. The paths this time are infinite, given by $12$, $132$, $142$, $1342$, $13432$, etc.... The probabilities are given by $$\sum_{k\ge0}p_{13}(p_{34}p_{43})^kp_{32}=\frac{p_{13}p_{32}}{1-p_{34}p_{43}}\text{for the 13...32 paths}~~,\tag{4}$$ $$\sum_{k\ge0}p_{13}(p_{34}p_{43})^kp_{34}p_{42}=\frac{p_{13}p_{34}p_{42}}{1-p_{34}p_{43}}\text{for the 13...42 paths}~~,\tag{5}$$ $$\sum_{k\ge0}p_{14}(p_{43}p_{34})^kp_{42}=\frac{p_{14}p_{42}}{1-p_{34}p_{43}}\text{for the 14...42 paths}~~,\text{ and}\tag{6}$$ $$\sum_{k\ge0}p_{14}(p_{43}p_{34})^kp_{43}p_{32}=\frac{p_{14}p_{43}p_{32}}{1-p_{34}p_{43}}\text{for the 14...32 paths}~~.\tag{7}$$ Therefore, Equation (1) says: \begin{multline} \pi_1 q_1 \left(p_{12}+p_{13}\frac{p_{32}+p_{34}p_{42}}{1-p_{34}p_{43}}+p_{14}\frac{p_{42}+p_{43}p_{32}}{1-p_{34}p_{43}}\right)=\\ \pi_2 q_2 \left(p_{21}+p_{23}\frac{p_{31}+p_{34}p_{41}}{1-p_{34}p_{43}}+p_{24}\frac{p_{41}+p_{43}p_{31}}{1-p_{34}p_{43}}\right)~~, \tag{8}\end{multline} which is also true, giving me confidence that the general result might be true as well, but I can not see the demonstration. I have a few heuristic ideas that justify this, but they do not fully convince me.

• I think your equation is a different way of writing the detailed balance condition $\pi_i q_{ij}=\pi_j q_{ji}$. If I'm right, then this is probably best framed as $Q$ being self-adjoint with respect to the inner product $(x,y)=\sum_{i=1}^n x_i \pi_i y_i$. This condition is not guaranteed for $n>2$, and is actually rather special. For example it implies that $Q$ is diagonalizable over $\mathbb{R}$. I'm not sure if it is implied by the assumption that all $p_{ij}$ are positive, though. – Ian Jun 24 '15 at 17:50
• By the way, you might look up "transition path theory". – Ian Jun 24 '15 at 17:55
• Ah, I have a counterexample (at least to the way that I read the question, which might be wrong). The idea is to take a purely periodic chain and perturb it slightly, so that the condition that all $p_{ij}$ are positive is still satisfied. So I consider $Q=\begin{bmatrix} -1 & 1-\varepsilon & \varepsilon \\ \varepsilon & -1 & 1-\varepsilon \\ 1-\varepsilon & \varepsilon & -1 \end{bmatrix}$ with $0<\varepsilon \ll 1$. So this is "almost" the deterministic oscillator $1 \to 2 \to 3 \to 1 \to 2 \dots$. It has complex eigenvalues, as I checked numerically with $\varepsilon=0.01$. – Ian Jun 24 '15 at 18:05
• @Ian. Thanks for your comments. I will revise the transition path theory, I have not heard of it. So, given your counterexample, you do not agree with Eq. (2)? In any case, I am preparing a demonstration. I am going to post it today. Check it out if it convinces you. – Enredanrestos Jun 24 '15 at 19:41
• My example fundamentally requires 3 states; all 2 state systems are in detailed balance. But again I am not sure whether your condition is equivalent to detailed balance, I would need to play with it. – Ian Jun 24 '15 at 20:01

Lets define the transition matrix of the embedded chain $\Pi$, and a subset of this matrix, $\Pi_{3}$ in the following way: $$\Pi=\left(\begin{array}{cc|ccc} 0 & p_{12} & &p_{1\bullet}&\\ p_{21} & 0 & & p_{2\bullet}& \\\hline & & & &\\ p_{\bullet1} & p_{\bullet2} & & \Pi_3&\\ & & & &\\ \end{array}\right)~~.\tag{1}$$ The sizes of the matrices defined are: $\Pi_{n\times n}$, $(\Pi_3)_{(n-2)\times(n-2)}$, $(p_{\bullet1})_{1\times (n-2)}$,$(p_{1\bullet})_{(n-2)\times 1}$, etc. The $p_{12}$ and $p_{21}$ are just positive probabilities. We are assuming that ${\rm diag}(\Pi)=0$.

First, we need to give a more explicit definition of the probability described by the notation $\mathbb{P}(1\rightarrow2)$. For that, we note that the probability that, starting from the state $1$, reach state $2$ in $k>0$ steps without entering $\{1,2\}$ any other time is given by $$\begin{cases} p_{1\bullet}\Pi_3^{k-2}p_{\bullet 2} &\text{if }k>1\\ p_{12} &\text{if }k=1\\ \end{cases}~~,\tag{2}$$ that is, all possible paths from $1$ to $\{3,\ldots,n\}$, and then $k-2$ paths inside this last set of states, and then a last path to state $2$. If $k=1$, then the probability is given simply by $p_{12}$. Throughout this post I will assume that the zero matrix to the power of zero is the identity matrix.

Therefore, the probability of a path that start in $1$ and ends in $2$ without returning to ${1,2}$ in between, of any length, is $$p_{12}+p_{1\bullet}\left(\sum_{k\ge0}\Pi_3^{k-2}\right)p_{\bullet 2}= p_{12}+p_{1\bullet}(I-\Pi_3)^{-1}p_{\bullet 2}~~,\tag{3}$$ where $I$ is the identity matrix of order $n-2$. $(I-\Pi_3)$ is invertible because it is diagonally dominant. From here I was able to make several numerical tests confirming the result.

Note that from expressions given in ${\rm(2)}$ we can easily deduce similar expression to calculate $\mathbb{P}(1\rightarrow1)$, $\mathbb{P}(2\rightarrow1)$, or $\mathbb{P}(2\rightarrow1)$.

Lets denote the stationary probability (horizontal) vector of the jump chain as $r$, that is, $r=r\Pi$. Note also that what we want to prove is equivalent to $$r_1\mathbb{P}(1\rightarrow2)=r_2\mathbb{P}(2\rightarrow1)~~\tag{4}$$ because $r_j=\pi_jq_j/(\sum_{i=1}^nq_i\pi_i)$.

## Proposition 1

Lets define $$A_{kl}=p_{k\bullet}(I_{(n-2)\times(n-2)}-\Pi_3)^{-1}p_{\bullet l}\quad\text{for k,l=1,2}~~.\tag{5}$$ Then, we will prove that $$p_{12}+A_{11}+A_{12}=1~~. \tag{6}$$ The justification relies on the process being irreducible, with all transition connected and recurrent. Lets denote the n-th passage time through the set of states $S$ by $T_S^{(n)}$. Recurrence and irreductibility means that $\mathbb{P}(T_S^{(n)}<\infty)=1$ for each nonempty $S$ and $n>0$. Proposition 1 is derived from noting that the left side of $(6)$ is another way to calculate $\mathbb{P}_1(T_{\{1,2\}}^{(2)}<\infty)$. Indeed, $A_{11}$ denotes the probability of all the paths that start in $1$ and return to $1$ without passing through $1$ or $2$ before. $A_{12}=\mathbb{P}(1\rightarrow2)$ is analogous, and the only path left is $1$ directly to $2$, corresponding to $T_{\{1,2\}}^{(2)}=1$.

## The result

By the definition of stationarity, $r\Pi=r$, therefore $$\begin{pmatrix} r1 & r2 & r_\bullet \end{pmatrix} \Pi=r~~,\tag{7}$$ therefore, \begin{align} r_2p_{21}+r_\bullet p_{\bullet 1}&=r_1~~,\tag{8}\\ r_1p_{12}+r_\bullet p_{\bullet 2}&=r_1~~,\tag{9}\\ r_1p_{1\bullet}+r_2 p_{2\bullet}+r_\bullet\Pi_3&=r_\bullet~~.\tag{10} \end{align} From Eq. (10), we have $$r_\bullet=r_1p_{1\bullet}(I-\Pi_3)^{-1}+r_2p_{2\bullet}(I-\Pi_3)^{-1}~~,\tag{11}$$ and (post)multiplying by $p_{\bullet 1}$ and $p_{\bullet 2}$ we derive \begin{align} r_1(1-A_{11})=r_2(p_{21}+A_{21})~~,\tag{11}\\ r_2(1-A_{22})=r_1(p_{12}+A_{12})~~.\tag{12} \end{align} Therefore, since $1-A_{11}=p_{12}+A_{12}$ by Proposition 1 and using the rest of the definitions (Eq. (3)), we conclude Eq. (4) and the result.