Inequality on time to reach absorption for Markov chain

Question

Take any Markov chain on the state set $\{0,1,...,n\}$ with the condition that the transition probability $P_ij$ to go from state $i$ to state $j$ is zero whenever $j>i$.

Define the random variable $T_n$ to be the number of steps before the process reaches the state $0$, if the process is started at state $n$.

Is it always true that $\displaystyle \mathbb{E}[T_n]\leq \sum_{i=1}^n \frac{1}{\sum_{j=0}^i P_{ij}(i-j)}$?

---

Example 1: Let $n=1$, $P_{1,1}=p$ and $P_{1,0}=1-p$. Then $\displaystyle\sum_{i=1}^n \frac{1}{\sum_{j=0}^i P_{ij}(i-j)}=\frac{1}{1-p}$.

We have $\mathbb{P}(T_1=k)=(1-p)p^{k-1}$ for $k\geq 1$ and so $\displaystyle \mathbb{E}(T_1)=\sum_{k=1}^{\infty}k\mathbb{P}(T_1=k)=(1-p)\frac{\mathrm{d}}{dp}\left(\frac{p}{1-p}\right)=\frac{1}{1-p}$

---

Example 2: Let $n=2$, $P_{2,0}=\frac{2}3$, $P_{2,1}=\frac{1}3$, $P_{2,2}=0$ and $P_{1,1}=P_{1,0}=\frac{1}2$. Then $\mathbb{P}(T_2=1)=\frac{2}3$ and $\mathbb{P}(T_2=k)=\frac{1}{3.2^{k-1}}$ if $k>1$.

In this case, $\displaystyle\sum_{i=1}^n \frac{1}{\sum_{j=0}^i P_{ij}(i-j)}=\frac{13}5$ and $\mathbb{E}(T_n)=\frac{5}3$

---

A few observations that may or may not help:

1. There is a recurrence relation $\mathbb{E}(T_n)=\sum_{k=0}^nP_{nk}\mathbb{E}[T_{k}+1]$.
2. Remove the zeroeth row and zeroeth column from the transition matrix. Then you get a matrix $Q$ with $Q_{ij}=P_{ij}$ for $i,j\ne 0$. Define the fundamental matrix $N=(1-Q)^{-1}$. $\mathbb{E}(T_n)$ is the $n$th element of $N\bf{1}$. $N$ is an upper triangular matrix.
3. My question appears to be related to this question.
4. The process looks similar to a renewal processes.

Answer 1

If I understand the problem correctly, the inequality need not always hold.

Let $P=\begin{pmatrix}1&1/2&1/20\\0&1/2&0\\0&0&19/20\end{pmatrix}$, $Q:=\begin{pmatrix}1/2&0\\0&19/20\end{pmatrix}$, and $r:=(1/2,1/20)$.

Then the probability of taking exactly $n$ steps to reach the $0$th state, starting from the $n$th state, is $rQ^{n-1}e_n$. So the mean of the number of steps is $$\mathbb{E}(T_n)=\sum_nnrQ^{n-1}e_n=r(I-Q)^{-2}e_n=20$$

The rhs of the inequality is $$\sum_{i=1}^2\frac{1}{\sum_{j=0}^iP_{ij}(i-j)}=\frac{1}{1/2}+\frac{1}{2/20}=12$$