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

155 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.