2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ian Jun 24 '15 at 17:50
  • $\begingroup$ By the way, you might look up "transition path theory". $\endgroup$ – Ian Jun 24 '15 at 17:55
  • $\begingroup$ 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$. $\endgroup$ – Ian Jun 24 '15 at 18:05
  • $\begingroup$ @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. $\endgroup$ – Enredanrestos Jun 24 '15 at 19:41
  • $\begingroup$ 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. $\endgroup$ – Ian Jun 24 '15 at 20:01
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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