1
$\begingroup$

Let $N_n:=\{1,2,\cdots,n\}$. Given two finite states Markov chains $\big(X^{(j)}_i\in N_n\}\big)_{i=0}^\infty$ for $j\in\{1,2\}$, both of which have two absorbing states at $1$ and $n$. $\text{Pr}\big(X^{(1)}_{i+1}=1|X^{(1)}_i=1\big)=\text{Pr}\big(X^{(1)}_{i+1}=n|X^{(1)}_i=n\big)=\text{Pr}\big(X^{(2)}_{i+1}=1|X^{(2)}_i=1\big)=\text{Pr}\big(X^{(2)}_{i+1}=n|X^{(2)}_i=n\big)=1, \,\forall a\in N_n$. $$\text{Pr}\big(X^{(1)}_{i+1}=b|X^{(1)}_i=a\big)>\text{Pr}\big(X^{(2)}_{i+1}=b|X^{(2)}_i=a\big)>0, \,\forall 1<a<b, a,b\in N_n.$$ $$0<\text{Pr}\big(X^{(1)}_{i+1}=b|X^{(1)}_i=a\big)< \text{Pr}\big(X^{(2)}_{i+1}=b|X^{(2)}_i=a\big), \,\forall n>a>b, a>1, a,b\in N_n,$$ $$\text{Pr}\big(X^{(1)}_{i+1}=a|X^{(1)}_i=a\big)= \text{Pr}\big(X^{(2)}_{i+1}=a|X^{(2)}_i=a\big), \,\forall n>a>1, a\in N_n.$$ Are the following inequalities true? $$\text{Pr}\big(X^{(1)}\text{ reaches } b|X^{(1)}_0=a\big)>\text{Pr}\big(X^{(2)}\text{ reaches }b|X^{(2)}_0=a\big), \,\forall 1<a<b,$$ and $$\text{Pr}(X^{(1)}\text{ reaches }b|X^{(1)}_0=a)<\text{Pr}(X^{(2)}\text{ reaches }b|X^{(2)}_0=a), \,\forall n>a>b.$$

This mathoverflow.net answer demonstrates a counterexample for a weaker condition.

Would a coupling argument help to prove the inequalities if they are true?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $P=(p_{ij})$ and $Q=(q_{ij})$ be the $n\times n$ transition matrices for the two respective Markov chains, where $n\ge2$. Your conditions imply the following:
\begin{gather}p_{nn}=q_{nn},\\ p_{nj}<q_{nj}\text{ if }1\le j\le n-1. \end{gather} Hence, $1=\sum_{j=1}^n p_{nj}<\sum_{j=1}^n q_{nj}=1$, which is a contradiction (which makes any conclusion whatsoever true).


Added: In a comment, the OP suggested that the conjecture be modified by now assuming $n$ to be an absorbing state as well, so that the conditions become \begin{gather}p_{11}=q_{11}=p_{nn}=q_{nn}=1,\\ p_{ii}=q_{ii}\text{ if }1\le i\le n, \\ p_{ij}q_{ij}>0\text{ if }1<i<n,\\ p_{ij}>q_{ij}\text{ if }1<i<j\le n,\\ p_{ij}<q_{ij}\text{ if }1\le j<i<n. \end{gather}

The conjecture then becomes that \begin{gather}f_{P;ij}>f_{Q;ij}\text{ if }1<i<j\le n,\\ f_{P;ij}<f_{Q;ij}\text{ if }1\le j<i<n, \end{gather} where $f_{P;ij}$ is the probability that the first chain ever reaches $j$ from $i$, and $f_{Q;ij}$ is defined similarly.

This conjecture, too, is false in general. E.g., suppose that $n=5$, $$P=\frac1{20} \left( \begin{array}{ccccc} 20 & 0 & 0 & 0 & 0 \\ 4 & 4 & 4 & 4 & 4 \\ 2 & 2 & 2 & 12 & 2 \\ 4 & 4 & 4 & 4 & 4 \\ 0 & 0 & 0 & 0 & 20 \\ \end{array} \right),\quad Q=\frac1{20}\left( \begin{array}{ccccc} 20 & 0 & 0 & 0 & 0 \\ 7 & 4 & 3 & 3 & 3 \\ 12 & 4 & 2 & 1 & 1 \\ 5 & 5 & 5 & 4 & 1 \\ 0 & 0 & 0 & 0 & 20 \\ \end{array} \right). $$ Then $$f_{P;32}=\frac13\not<\frac{69}{283}=f_{Q;32}.$$

Added more: This is in response to a request by the OP to provide details. Fix any $j\in[n]:=\{1,\dots,n\}$. Let $g$ denote the $j$th column of $P$ and let $R$ denote the matrix obtained from matrix $P$ by replacing the $j$th column in $P$ by the zero column. Then for the column matrix $f:=(f_{P;ij}\colon i\in[n])^T$ we have $$f=\sum_{n=0}^\infty (R^n g); $$ cf. e.g. the 5th display on page 85 and formula (2.6.3') on page 90 in Resnick. If all entries of the column matrix $g$ are nonzero, then the norm $\|R\|_{\infty,\infty}$ of the matrix $R$ considered as a linear operator from $\ell_n^\infty$ to $\ell_n^\infty$ will be $<1$, whence we will have $f=(\sum_{n=0}^\infty R^n)g=(I-R)^{-1}g$. However, in our case, because we have two absorbing states, every column of $P$ must have a zero entry. This difficulty is easy to circumvent, as follows. By the monotone convergence theorem, for $t\in(0,1)$ $$(I-tR)^{-1}g=\sum_{n=0}^\infty (tR)^n g\;\Big\uparrow\;\sum_{n=0}^\infty (R^n g)=f $$ as $t\uparrow1$. So, $$f=\lim_{t\uparrow1}(I-tR)^{-1}g. $$ Since $(I-tR)^{-1}g$ is rational in $t$, the latter limit is easy to compute.

In particular, for $n=5$ we get $$f_{P;32}=\frac {p_{34}p_{42}+p_{32}(1-p_{44})} {(1-p_{33}) (1-p_{44})-p_{34} p_{43}}, $$ with the corresponding expression for $f_{Q;32}$. We see that $f_{P;32}$ is increasing in $p_{34}$. Also, one of the OP's conditions is $p_{34}>q_{34}$. So, to get $f_{P;32}>f_{Q;32}$, we should try to make $p_{34}$ large and $q_{34}$ small. At the same time, we may choose $p_{42}$, $p_{32}$, and $p_{43}$ close enough to $q_{42}$, $q_{32}$, and $q_{43}$ (respectively), also keeping in mind the conditions $p_{33}=q_{33}$ and $p_{44}=q_{44}$. This should (and does) result in $f_{P;32}>f_{Q;32}$, which disproves the conjecture.

Added yet more: The matter becomes much more transparent if we ignore, at least for a moment, the strictness of the inequality restrictions on the $p_{ij}$'s and $q_{ij}$'s. Then we may assume that $p_{34}=q_{31}=p_{42}=q_{42}=1$. Then clearly $f_{P;32}=1\not\le0=f_{Q;32}$. If you still insist on the strictness of the inequality restrictions, then you can have it by the continuity of $f_{P;32}$ on the appropriate domain.

$\endgroup$
15
  • $\begingroup$ $p_{nn}=q_{nn}$ but they does not have to be $1$. Anyway, your objection is valid. How about making $p_{nn}=q_{nn}=1$ and $p_{nj}=q_{nj}=0, \,\forall 1\le j\le n-1$, so we have two absorbing states at both ends? $\endgroup$
    – Hans
    Commented Nov 7, 2019 at 9:24
  • $\begingroup$ @Hans : The modified conjecture is false, too. $\endgroup$ Commented Nov 7, 2019 at 13:53
  • $\begingroup$ I see. Do you see any way to salvage the conjecture? Could you please reveal the details of the process by which you find these counterexamples? $\endgroup$
    – Hans
    Commented Nov 7, 2019 at 17:51
  • $\begingroup$ @Hans : At this point I see no way to salvage the conjecture. However, I have provided the details you requested, which may help one find a good sufficient condition for your desired conclusion. $\endgroup$ Commented Nov 8, 2019 at 2:13
  • $\begingroup$ +1 Thank you very much, Iosif. Allow me to look through your answer. You understand my motivation for the conjecture that strong enough directional transitional flow should increase the hitting probability, right? $\endgroup$
    – Hans
    Commented Nov 8, 2019 at 9:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .