Skip to main content
added 2 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

Let $P=(p_{ij})$ and $Q=(q_{ij})$ be the $n\times n$ transition matrices for the two respective Markov chains, such that $$p_{11}=q_{11},\quad p_{ij}q_{ij}>0\text{ if }i>1,\quad p_{ij}>q_{ij}\text{ if }1<i<j,\quad\text{ and }p_{ij}\le q_{ij}\text{ if }i>1\text{ and }1\le j\le i. $$\begin{gather}p_{11}=q_{11}=1,\\ p_{ij}q_{ij}>0\text{ if }i>1,\\ p_{ij}>q_{ij}\text{ if }1<i<j,\\ p_{ij}\le q_{ij}\text{ if }i>1\text{ and }1\le j\le i. \end{gather} The conjecture was that then $$f_{P;ij}>f_{Q;ij}\text{ if }1<i<j,\quad\text{ and }f_{P;ij}\le f_{Q;ij}\text{ if }i>1\text{ and }1\le j\le i, $$\begin{gather}f_{P;ij}>f_{Q;ij}\text{ if }1<i<j,\\ f_{P;ij}\le f_{Q;ij}\text{ if }i>1\text{ and }1\le j\le i, \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 is false in general. E.g., suppose that $n=3$, $$P=\frac1{16} \left( \begin{array}{ccc} 16 & 0 & 0 \\ 1 & 3 & 12 \\ 4 & 4 & 8 \\ \end{array} \right),\quad Q=\frac1{16}\left( \begin{array}{ccc} 16 & 0 & 0 \\ 4 & 4 & 8 \\ 4 & 4 & 8 \\ \end{array} \right). $$ Then $$f_{P;22}=\frac9{16}\not\le\frac8{16}=f_{Q;22}.$$

Let $P=(p_{ij})$ and $Q=(q_{ij})$ be the $n\times n$ transition matrices for the two respective Markov chains, such that $$p_{11}=q_{11},\quad p_{ij}q_{ij}>0\text{ if }i>1,\quad p_{ij}>q_{ij}\text{ if }1<i<j,\quad\text{ and }p_{ij}\le q_{ij}\text{ if }i>1\text{ and }1\le j\le i. $$ The conjecture was that then $$f_{P;ij}>f_{Q;ij}\text{ if }1<i<j,\quad\text{ and }f_{P;ij}\le f_{Q;ij}\text{ if }i>1\text{ and }1\le j\le i, $$ where $f_{P;ij}$ is the probability that the first chain reaches $j$ from $i$, and $f_{Q;ij}$ is defined similarly.

This conjecture is false in general. E.g., suppose that $n=3$, $$P=\frac1{16} \left( \begin{array}{ccc} 16 & 0 & 0 \\ 1 & 3 & 12 \\ 4 & 4 & 8 \\ \end{array} \right),\quad Q=\frac1{16}\left( \begin{array}{ccc} 16 & 0 & 0 \\ 4 & 4 & 8 \\ 4 & 4 & 8 \\ \end{array} \right). $$ Then $$f_{P;22}=\frac9{16}\not\le\frac8{16}=f_{Q;22}.$$

Let $P=(p_{ij})$ and $Q=(q_{ij})$ be the $n\times n$ transition matrices for the two respective Markov chains, such that \begin{gather}p_{11}=q_{11}=1,\\ p_{ij}q_{ij}>0\text{ if }i>1,\\ p_{ij}>q_{ij}\text{ if }1<i<j,\\ p_{ij}\le q_{ij}\text{ if }i>1\text{ and }1\le j\le i. \end{gather} The conjecture was that then \begin{gather}f_{P;ij}>f_{Q;ij}\text{ if }1<i<j,\\ f_{P;ij}\le f_{Q;ij}\text{ if }i>1\text{ and }1\le j\le i, \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 is false in general. E.g., suppose that $n=3$, $$P=\frac1{16} \left( \begin{array}{ccc} 16 & 0 & 0 \\ 1 & 3 & 12 \\ 4 & 4 & 8 \\ \end{array} \right),\quad Q=\frac1{16}\left( \begin{array}{ccc} 16 & 0 & 0 \\ 4 & 4 & 8 \\ 4 & 4 & 8 \\ \end{array} \right). $$ Then $$f_{P;22}=\frac9{16}\not\le\frac8{16}=f_{Q;22}.$$

Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

Let $P=(p_{ij})$ and $Q=(q_{ij})$ be the $n\times n$ transition matrices for the two respective Markov chains, such that $$p_{11}=q_{11},\quad p_{ij}q_{ij}>0\text{ if }i>1,\quad p_{ij}>q_{ij}\text{ if }1<i<j,\quad\text{ and }p_{ij}\le q_{ij}\text{ if }i>1\text{ and }1\le j\le i. $$ The conjecture was that then $$f_{P;ij}>f_{Q;ij}\text{ if }1<i<j,\quad\text{ and }f_{P;ij}\le f_{Q;ij}\text{ if }i>1\text{ and }1\le j\le i, $$ where $f_{P;ij}$ is the probability that the first chain reaches $j$ from $i$, and $f_{Q;ij}$ is defined similarly.

This conjecture is false in general. E.g., suppose that $n=3$, $$P=\frac1{16} \left( \begin{array}{ccc} 16 & 0 & 0 \\ 1 & 3 & 12 \\ 4 & 4 & 8 \\ \end{array} \right),\quad Q=\frac1{16}\left( \begin{array}{ccc} 16 & 0 & 0 \\ 4 & 4 & 8 \\ 4 & 4 & 8 \\ \end{array} \right). $$ Then $$f_{P;22}=\frac9{16}\not\le\frac8{16}=f_{Q;22}.$$