2. Main results

For a non-negative matrix $M=(M_{i,j})$ , let $(M)_{i,+}$ denote the ith row sum of M, i.e. $(M)_{i,+}=\sum_j M_{i,j}$ . Before presenting the main results Theorems 1 and 2, we state Lemma 1 below, which is needed for the proofs of Theorems 1 and 2. All the proofs are given in Section 4.

Theorem 1 has a discrete-time analogue concerning a Markov chain $\{Y_n\}$ with state space $\{0,1,\ldots\} \cup \{e\}$ in discrete time $n=0,1,\ldots.$ Specifically, $\{Y_n\}$ has transition probabilities satisfying

(1) \begin{align}\sum_{j=\max\{0, i-1\}}^{i+1} \mathbb{P}(Y_{n+1}=j \mid Y_n=i) +\mathbb{P}(Y_{n+1}=e \mid Y_n=i)=1,\quad i=0,1,\ldots,\end{align}

and $\mathbb{P}(Y_{n+1}=e \mid Y_n=e)=1$ . (Note that $\mathbb{P}(Y_{n+1}=i \mid Y_n=i)>0$ is allowed.) We refer to $\{Y_n\}$ as a discrete-time birth–death process with killing (or DBDK for short). Let $T_e^d\,:\!=\,\inf\{n\ge 0\colon Y_n=e\}$ , which is the discrete-time counterpart of $T_e$ . (By convention, $\inf \emptyset\,:\!=\,\infty$ .)

3. Numerical examples

In this section we illustrate Theorems 1 and 2 with numerical examples. We first consider a DBDK $\{Y_n\}$ with transition probabilities given by

\begin{align*}\mathbb{P}(Y_{n+1}=e \mid Y_n=i)&=0.01,\quad i=0,1,2,\\[3pt] \mathbb{P}(Y_{n+1}=e \mid Y_n=i)&=0.02,\quad i\geq 3,\\[3pt] \mathbb{P}(Y_{n+1}=1 \mid Y_n=0)&=0.99=1- \mathbb{P}(Y_{n+1}=e \mid Y_n=0),\\[3pt] \mathbb{P}(Y_{n+1}=i+1 \mid Y_n=i)&=0.5,\quad i\geq 1,\\[3pt] \mathbb{P}(Y_{n+1}=i-1 \mid Y_n=i)&=0.5-\mathbb{P}(Y_{n+1}=e \mid Y_n=i),\quad i\geq 1.\end{align*}

Figure 1 plots the survival probabilities

\begin{equation*}\mathbb{P}(T_e^d > n \mid Y_0= i)=(M^n)_{i,+}=\sum_{j=0}^\infty M^n_{i,j} \quad \text{for $0\leq n \leq 160$ and $i=0,1,2,3$,}\end{equation*}

where the matrix $M=(M_{i,j})$ is given by $M_{i,j}=\mathbb{P}(Y_1=j \mid Y_0=i)$ for $i,j=0,1,\ldots.$ It shows that $\mathbb{P}(T_e^d > n \mid Y_0= i)$ decreases as i increases, as expected in view of Theorem 2(iii).

Figure 1: The survival probabilities $\mathbb{P}(T_e^d > n \mid Y_0= i)$ , $i=0,1,2,3$ .

For a linear CBDK $\{X_t\}$ with $\mu_i=ai$ , $\lambda_i=bi+\theta$ , and $\gamma_i=ci$ , where a,b,c and $\theta$ are positive constants, Karlin and Tavaré [Reference Karlin and Tavaré11] derived the explicit formula

\begin{equation*}\mathbb{P}(T_e>t \mid X_0=i)={\mathrm{e}}^{-\theta (1-v_0)t}\biggl[\dfrac{v_0(v_1-1)+v_1 \sigma_t (1-v_0)}{v_1-1+\sigma_t (1-v_0)}\biggr]^i \biggl[\dfrac{v_1-1+\sigma_t(1-v_0)}{v_1-v_0}\biggr]^{-\theta/b},\end{equation*}

where $0<v_0<1<v_1$ are the two roots of the equation $bx^2 -(a+b+c)x + a=0$ and $\sigma_t={\mathrm{e}}^{-b(v_1-v_0)t}$ . Since $\gamma_i$ is increasing in i, $\mathbb{P}(T_e>t \mid X_0=i)$ should be decreasing in i by Theorem 1(iii). Noting that $v_0(v_1-1)+v_1 \sigma_t (1-v_0)<v_1-1+\sigma_t (1-v_0)$ (since $0<\sigma_t<1$ ), we see that $\mathbb{P}(T_e>t \mid X_0=i)$ decays geometrically in i. Figure 2 plots $\mathbb{P}(T_e>t \mid X_0=i)$ for $0<t<5$ and $i=0,2,4,6,8$ with $a=b=c=\theta=1$ .

Figure 2: The survival probabilities $\mathbb{P}(T_e > t \mid X_0= i)$ , $i=0,2,4,6, 8$ .

While no explicit formula for $\mathbb{P}(T_e>t \mid X_0=i)$ is available for general CBDKs, we may use the technique of uniformization (see [14, Section 5.10] and [15, Section 6.7]) to compute $\mathbb{P}(T_e>t \mid X_0=i)$ if $\{X_t\}$ is uniformizable (i.e. $\sup_i (\lambda_i+\mu_i+\gamma_i)\leq C<\infty$ for some constant $C>0$ ). Specifically, with $\mu_0\,:\!=\,0$ , let $\{Z_n\}$ be a DBDK with transition probabilities satisfying $\mathbb{P}(Z_{n+1}=e \mid Z_n=e)=1$ , and for $i\geq 0$

\begin{align*}&\mathbb{P}(Z_{n+1}=i-1 \mid Z_n=i)=\dfrac{\mu_i}{C},\quad \mathbb{P}(Z_{n+1}=i+1 \mid Z_n=i)=\dfrac{\lambda_i}{C},\\[3pt] &\mathbb{P}(Z_{n+1}=e \mid Z_n=i)=\dfrac{\gamma_i}{C},\quad \mathbb{P}(Z_{n+1}=i \mid Z_n=i)=1-\dfrac{\mu_i+\lambda_i+\gamma_i}{C}.\end{align*}

Let $\{N(t)\}$ be a Poisson process of constant rate C, independent of $\{Z_n\}$ . Then we have the following result:

(2) \begin{align} \text{Given $ X_0=Z_0$, the two processes $\{X_t\}$ and $ \{Z_{N(t)}\}$ have the same distribution.} \end{align}

In other words, the CBDK $\{X_t\}$ may be constructed by placing the transitions of the DBDK $\{Z_n\}$ at Poisson arrival epochs. It follows from (2) that

\begin{align}\mathbb{P}(T_e>t \mid X_0=i)&= \mathbb{P}(X_t \neq e \mid X_0=i) \notag\\[3pt] &=\mathbb{P}(Z_{N(t)}\neq e \mid Z_0=i) \notag\\[3pt] &=\sum_{n=0}^\infty \mathbb{P}(Z_n \neq e, N(t)=n \mid Z_0=i) \notag\\[3pt] &=\sum_{n=0}^\infty \mathbb{P}(N(t)=n)\, \mathbb{P}(Z_n \neq e \mid Z_0=i) \notag\\[3pt] &=\sum_{n=0}^\infty \dfrac{{\mathrm{e}}^{-Ct}(Ct)^n}{n!} (M^{*n})_{i,+}, \notag\end{align}

where the matrix $M^*=(M^*_{i,j})$ is given by $M^*_{i,j}=\mathbb{P}(Z_1=j \mid Z_0=i)$ . So $\mathbb{P}(T_e>t \mid X_0=i)$ may be approximated by

\begin{equation*}\sum_{n=0}^{L(t)} \dfrac{{\mathrm{e}}^{-Ct}(Ct)^n}{n!} (M^{*n})_{i,+}\end{equation*}

for sufficiently large integer L(t) (depending on t). The distributional equivalence of $\{X_t\}$ and $\{Z_{N(t)}\}$ in (2) will be called for in the proof of Theorem 1 in the next section.

4. Proofs of Theorems 1 and 2 and Lemma 1

To prove Theorem 2, let $M=(M_{i,j})_{i,j\in \{0,1,\ldots\}}$ be the transition matrix of $\{Y_n\}$ restricted to the states $0,1,\ldots.$ That is,

\begin{equation*}M_{i,j}=\mathbb{P}(Y_{n+1}=j \mid Y_{n}=i), \quad i,j=0,1,\ldots.\end{equation*}

By (1), we see that $M_{i,j}=0$ for $|i-j|>1$ and that

(3) \begin{align} (M)_{i,+}=\sum_{j=\max\{0,i-1\}}^{i+1} M_{i,j}=1- \mathbb{P}(Y_{n+1}=e \mid Y_n=i)=1-p_{i,e}. \end{align}

Moreover,

(4) \begin{align}\mathbb{P}(T_e^d>n \mid Y_0=i)=\sum_{j=0}^\infty \mathbb{P}(Y_n =j \mid Y_0=i)=(M^n)_{i,+}.\end{align}

In view of (3) and (4), Theorem 2 follows immediately from Lemma 1. To prove Theorem 1, one may approximate the CBDK $\{X_t\}$ by a sequence of DBDKs via time-discretization and argue that $T_e$ is the limit of the corresponding $T^d_e$ . Instead of taking this approach, we first consider uniformizable $\{X_t\}$ (i.e. $\sup_i\; (\lambda_i+\mu_i+\gamma_i)<\infty$ ) for which the associated (embedded) discrete-time Markov chain is a DBDK, so that the desired results follow from Theorem 2. The general CBDK $\{X_t\}$ is then approximated by a sequence of uniformizable CBDKs. The details are given in the proof below.

Proof of Theorem 1. We first prove part (i) under the additional assumption that $\{X_t\}$ is uniformizable, i.e. $\sup_i\; (\lambda_i+\mu_i+\gamma_i)\leq C<\infty$ for some $C>0$ . Let $\{Z_n\}$ and $\{N(t)\}$ be, respectively, the DBDK and (independent) Poisson process of constant rate C as described in the last paragraph of Section 3. Letting

\begin{equation*}p^{(Z)}_{i,e}\,:\!=\,\mathbb{P}(Z_{n+1}=e \mid Z_n=i)=\gamma_i/C\quad \text{and}\quad T_e^{d(Z)}\,:\!=\,\inf\{n\geq 0\colon Z_n=e\},\end{equation*}

we see that $\{Z_n\}$ is a DBDK with $p^{(Z)}_{i,e} \leq p^{(Z)}_{j,e}$ for $i\leq i^*$ and $j>i^*$ , so that by Theorem 2(i),

(5) \begin{align} \mathbb{P}(Z_n \neq e \mid Z_0=i^*)&=\mathbb{P}(T_e^{d(Z)}>n \mid Z_0=i^*)\notag\\[3pt] &\geq \mathbb{P}(T_e^{d(Z)} >n \mid Z_0=i^*+1) \notag \\[3pt] &=\mathbb{P}(Z_n \neq e \mid Z_0=i^*+1). \end{align}

Consequently, for $t>0$ ,

\begin{align*} \mathbb{P}(T_e>t \mid X_0=i^*)&=\mathbb{P}(Z_{N(t)}\neq e \mid Z_0=i^*)\quad (\text{by} ({2}))\\[3pt] &=\sum_{n=0}^\infty \mathbb{P}(N(t)=n)\, \mathbb{P}(Z_n \neq e \mid Z_0=i^*)\\[3pt] &\geq \sum_{n=0}^\infty \mathbb{P}(N(t)=n)\, \mathbb{P}(Z_n \neq e \mid Z_0=i^*+1)\quad (\text{by} ({5}))\\[3pt] &=\mathbb{P}(Z_{N(t)}\neq e \mid Z_0=i^*+1)\\[3pt] &=\mathbb{P}(T_e>t \mid X_0=i^*+1).\end{align*}

This proves part (i) for uniformizable $\{X_t\}$ .

For general (non-explosive) $\{X_t\}$ , to prove

\begin{equation*}\mathbb{P}(T_e>t_0 \mid X_0=i^*) \geq \mathbb{P}(T_e>t_0 \mid X_0=i^*+1)\end{equation*}

for any (fixed) $t_0>0$ , let

(6) \begin{align}a_k\,:\!=\,\mathbb{P}(T_k\leq t_0 \mid X_0=i^*)\quad \text{and}\quad b_k\,:\!=\,\mathbb{P}(T_k\leq t_0 \mid X_0=i^*+1),\end{align}

where $T_k\,:\!=\,\inf\{t\geq 0\colon X_t=k\}$ . For $X_t$ to reach a (large) state k starting from $i^*$ or $i^*+1$ , at least $k-i^*-1$ transitions are required. Since $\{X_t\}$ is non-explosive, we have

(7) \begin{align}\lim_{k \to \infty} a_k=0\quad\text{and}\quad \lim_{k \to \infty}b_k=0.\end{align}

For each $k>i^*$ , let $\{X_t^{(k)}\}$ be a CBDK whose birth, death, and killing rates in state i are given by $\lambda_i^{(k)}\,:\!=\,\lambda_{i\wedge k}$ , $\mu_i^{(k)}\,:\!=\,\mu_{i\wedge k}$ , and $\gamma_i^{(k)}\,:\!=\,\gamma_{i\wedge k}$ , where $i \wedge k\,:\!=\,\min\{i,k\}$ . Clearly $\{X_t^{(k)}\}$ is uniformizable with the killing rates satisfying $\gamma_i^{(k)}\leq \gamma_j^{(k)}$ for $i\leq i^*$ and $j>i^*$ . Let $\mathcal{L}_i(T_k)$ ( $\mathcal{L}_i(T_e \wedge T_k)$ , respectively) denote the distribution of $T_k$ ( $T_e \wedge T_k$ , respectively) given $X_0=i$ . Similarly, let $\mathcal{L}_i(T_k^{(k)})$ ( $\mathcal{L}_i(T_e^{(k)}\wedge T_k^{(k)})$ , respectively) denote the distribution of $T_k^{(k)}$ ( $T_e^{(k)}\wedge T_k^{(k)}$ , respectively) given $X_0^{(k)}=i$ , where $T_r^{(k)}\,:\!=\,\inf\{t \geq 0\colon X_t^{(k)}=r\}$ for $r=k,e$ .

For $k>i^*$ , given $X_0=i^*$ or $i^*+1$ , the distributions of $T_k$ and $T_e \wedge T_k$ depend only on the values of $\lambda_i, \mu_i, \gamma_i$ for $i< k$ . Similarly, given $X_0^{(k)}=i^*$ or $i^*+1$ , the distributions of $T_k^{(k)}$ and $T_e^{(k)} \wedge T_k^{(k)}$ depend only on the values of $\lambda_i^{(k)}, \mu_i^{(k)}, \gamma_i^{(k)}$ for $i< k$ . Since $\lambda_i=\lambda_i^{(k)}$ , $\mu_i=\mu_i^{(k)}$ , and $\gamma_i=\gamma_i^{(k)}$ for $i\leq k$ , we find that

\begin{align*}\mathcal{L}_i(T_k)=\mathcal{L}_i(T_k^{(k)})\quad \text{and}\quad\mathcal{L}_i(T_e \wedge T_k)=\mathcal{L}_i(T_e^{(k)} \wedge T_k^{(k)})\quad \text{for $i=i^*$, $i^*+1$ and $ k>i^*$,}\end{align*}

implying that for $k>i^*$ ,

(8) \begin{align}\mathbb{P}(T_k>t_0 \mid X_0=i)&=\mathbb{P}(T_k^{(k)}>t_0 \mid X_0^{(k)}=i),\quad i=i^*,\, i^*+1\end{align}

(9) \begin{align}*\mathbb{P}(T_e \wedge T_k >t_0 \mid X_0=i)&=\mathbb{P}(T_e^{(k)} \wedge T_k^{(k)} >t_0 \mid X_0^{(k)}=i),\quad i=i^*, \, i^*+1.\end{align}

Since $\{X_t^{(k)}\}$ is uniformizable with $\gamma^{(k)}_i \leq \gamma^{(k)}_j$ for $i \leq i^*$ and $j>i^*$ , we have shown that

(10) \begin{align}\mathbb{P}(T_e^{(k)} > t_0 \mid X_0^{(k)}=i^*) \geq \mathbb{P}(T_e^{(k)}>t_0 \mid X_0^{(k)}=i^*+1)\quad\text{for $k>i^*$.}\end{align}

Also for $k>i^*$ and $i=i^*$ , $i^*+1$ ,

\begin{align*}\mathbb{P}(T_e>t_0 \mid X_0=i)&\geq \mathbb{P}(T_e \wedge T_k>t_0 \mid X_0=i)\\[3pt] &=\mathbb{P}(T_e^{(k)} \wedge T_k^{(k)}>t_0 \mid X_0^{(k)}=i)\quad (\text{by} ({9})),\end{align*}

and

\begin{align*}\mathbb{P}(T_e>t_0 \mid X_0=i)&\leq \mathbb{P}(T_e \wedge T_k>t_0 \mid X_0=i)+ \mathbb{P}(T_k\leq t_0 \mid X_0=i)\\[3pt] &=\mathbb{P}(T_e^{(k)} \wedge T_k^{(k)}>t_0 \mid X_0^{(k)}=i)+\mathbb{P}(T_k\leq t_0 \mid X_0=i) \quad (\text{by} ({9}))\\[3pt] &\leq \mathbb{P}(T_e^{(k)} \wedge T_k^{(k)}>t_0 \mid X_0^{(k)}=i)+ a_k \vee b_k,\end{align*}

where $a_k$ and $b_k$ are as defined in (6) and $a_k \vee b_k\,:\!=\,\max\{a_k,b_k\}$ . Consequently, for $k>i^*$ ,

(11) \begin{align}0\leq \mathbb{P}(T_e>t_0 \mid X_0=i)-\mathbb{P}(T_e^{(k)} \wedge T_k^{(k)}>t_0 \mid X_0^{(k)}=i) \leq a_k \vee b_k,\quad i=i^*,\, i^*+1.\end{align}

Furthermore, for $k>i^*$ and $i=i^*$ , $i^*+1$ ,

\begin{align*}0&\leq \mathbb{P}(T_e^{(k)}>t_0 \mid X_0^{(k)}=i)-\mathbb{P}(T_e^{(k)} \wedge T_k^{(k)}>t_0 \mid X_0^{(k)}=i)\\[3pt] &\leq \mathbb{P}(T_k^{(k)} \leq t_0 \mid X_0^{(k)}=i)\\[3pt] &=\mathbb{P}(T_k \leq t_0 \mid X_0=i)\quad (\text{by} ({8}))\\[3pt] &\leq a_k \vee b_k,\end{align*}

which together with (11) implies that for $k>i^*$ and $i=i^*$ , $i^*+1$ ,

(12) \begin{align}|\mathbb{P}(T_e>t_0 \mid X_0=i) -\mathbb{P}(T_e^{(k)}>t_0 \mid X_0^{(k)}=i)| \leq a_k \vee b_k.\end{align}

It follows from (7), (10), and (12) that

\begin{equation*}\mathbb{P}(T_e > t_0 \mid X_0=i^*) \geq \mathbb{P}(T_e>t_0 \mid X_0=i^*+1),\end{equation*}

completing the proof of part (i).

Part (ii) can be proved by using a similar argument and invoking Theorem 2(ii). Parts (iii) and (iv) follow immediately from parts (i) and (ii), respectively. □

Proof of Lemma 1. Note that part (ii) follows from part (i) by reversing the ordering of the rows and that of the columns, and that part (iii) is a consequence of parts (i) and (ii). It remains to prove part (i). It suffices to deal only with the case $\mathbb{S}=\mathbb{Z}$ , since the cases $\mathbb{S}=\{0,1,\ldots, I\}$ and $\mathbb{S}=\{0,1,\ldots\}$ can be treated as special cases of $\mathbb{S}=\mathbb{Z}$ . More precisely, for $M=(M_{i,j})_{i,j \in \{0,1,\ldots,I\}}$ satisfying $(M)_{i,+}\le (M)_{j,+}$ for $i \le i^*<j$ , define $\widetilde{M}=(\widetilde{M}_{i,j})_{i,j \in \mathbb{Z}}$ by

\begin{align*}\widetilde{M}_{i,j}=M_{i,j} \textbf{1}_{\{0\le i,j \le I\}}+ (M)_{i^*,+} \;\;\delta_{i,j} \textbf{1}_{\{i <0\}} +(M)_{i^*+1,+}\;\; \delta_{i,j} \textbf{1}_{\{i >I\}},\end{align*}

where $\textbf{1}_A$ denotes the indicator function of a set A and $\delta_{i,j}=1$ if $i=j$ and $\delta_{i,j}=0$ otherwise. We have $(\widetilde{M})_{i,+}\le (\widetilde{M})_{j,+}$ for $i\le i^*<j$ . Moreover, $(\widetilde{M}^n)_{i,+}=(M^n)_{i,+}$ for $i=0,1,\ldots,I$ .

We now prove part (i) for $\mathbb{S}=\mathbb{Z}$ . Without loss of generality, we assume $i^*=0$ , so that the tri-diagonal matrix M satisfies $M_{i,j}\ge 0$ for $i,j \in \mathbb{Z}$ , $M_{i,j}=0$ if $|i-j|>1$ , and $(M)_{i,+}\le (M)_{j,+}$ for $i \le 0<j$ . To show that $(M^{n})_{0,+} \leq (M^{n})_{1,+}$ for any (fixed) $n\geq 2$ , note that $(M^{n})_{0,+}$ and $(M^{n})_{1,+}$ do not depend on the values of $M_{i,i-1}$ , $M_{i,i}$ , and $M_{i,i+1}$ for $i\leq -n$ or $i\geq n+1$ . Thus $(M^{n})_{0,+}=(\overline{M}^{n})_{0,+}$ and $(M^{n})_{1,+} = (\overline{M}^{n})_{1,+}$ , where $\overline{M}=(\overline{M}_{i,j})$ is defined by

\begin{align*}\overline{M}_{i,j} = M_{i,j} \textbf{1}_{\{-n<i\leq n\}}+ (M)_{0,+}\;\;\delta_{i,j} \textbf{1}_{\{i\leq -n\}}+ (M)_{1,+}\;\;\delta_{i,j} \textbf{1}_{\{i>n\}}.\end{align*}

Note that $\overline{M}$ has bounded row sums and satisfies $(\overline{M})_{i,+}\le (\overline{M})_{j,+}$ for $i\leq 0<j$ . If we can show part (i) of the theorem for non-negative tri-diagonal matrices with bounded row sums, then we have

\begin{equation*}(M^n)_{0,+}=(\overline{M}^n)_{0,+}\le (\overline{M}^n)_{1,+}= (M^n)_{1,+}.\end{equation*}

So it suffices to establish part (i) with M having bounded row sums. We may further assume that the row sums of M are bounded by 1.

To show that $(M^{n})_{0,+} \leq (M^{n})_{1,+}$ for $n\geq 2$ , we introduce a Markov chain $\{X_{n}\colon n=0,1,\ldots \}$ with state space $\mathbb{Z}\cup \{e\}$ and transition probabilities given by

\begin{align*}\mathbb{P}(X_{n+1}&=j \mid X_{n}=i) = M_{i,j} ,\quad i,j\in \mathbb{Z} ,\\[3pt] \mathbb{P}(X_{n+1}&=e \mid X_{n}=i) = 1-(M)_{i,+} ,\quad i\in \mathbb{Z} ,\\[3pt] \mathbb{P}(X_{n+1}&=e \mid X_{n}=e) = 1 .\end{align*}

Note that the state e is absorbing. Let $T_{1}=\inf \{n\geq 0\colon X_{n}=1\}$ and $T_{e}=\inf \{n\geq 0\colon X_{n}=e\}$ . (In Theorem 1, $T_e$ is defined with respect to the continuous-time process $\{X_t\}$ . Here the same notation $T_e$ is used with respect to the discrete-time process $\{X_n\}$ . This proof does not involve the continuous-time process $\{X_t\}$ .)

We write $\mathbb{P}_{i}( \cdot )=\mathbb{P}( \cdot\mid X_{0}=i)$ , and claim that for $n=1,2,\ldots,$ and $j=1,2,\ldots,$

(13) \begin{align}\mathbb{P}_{0}(T_{1}\geq n,\, T_{e}>n) + \sum^{n-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j}(T_{e}>n-\ell) \leq \mathbb{P}_{j}(T_{e}>n). \end{align}

Note that for $1 \leq \ell < n$ ,

(14) \begin{align}\mathbb{P}_0(T_{1}=\ell,\, T_{e}>n) &=\mathbb{P}(T_{1}=\ell,\, T_{e}>n\mid X_{0}=0)\notag \\[3pt] &=\mathbb{P}(T_{1}=\ell \mid X_{0}=0)\, \mathbb{P}(T_{e}>n\mid T_{1}=\ell,\, X_{0}=0)\notag \\[3pt] &=\mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}(T_{e}>n\mid X_{\ell}=1)\notag\\[3pt] &=\mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}(T_{e}>n-\ell \mid X_{0}=1)\notag\\[3pt] &=\mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}_{1}(T_{e}>n-\ell)\,. \end{align}

By (14), the left-hand side of (13) with $j=1$ equals

\begin{align*}& \mathbb{P}_{0}(T_{1}\geq n,\, T_{e}>n) + \sum^{n-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}_{1}(T_{e}>n-\ell)\\[3pt] &\quad =\mathbb{P}_{0}(T_{1}\geq n,\, T_{e}>n) + \sum^{n-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell,\, T_{e}>n)\\[3pt] &\quad =\mathbb{P}_{0}(T_{e}>n) .\end{align*}

Thus the inequality (13) with $j=1$ is equivalent to

(15) \begin{align}\mathbb{P}_{0}(T_{e}>n) \leq \mathbb{P}_{1}(T_{e}>n). \end{align}

Since $\mathbb{P}_{i}(T_{e}>n) =\mathbb{P}(X_{n}\in \mathbb{Z} \mid X_{0}=i) = (M^{n})_{i,+}$ , (15) is equivalent to $(M^{n})_{0,+} \leq (M^{n})_{1,+}$ .

We now prove (13) by induction on n. For $n=1$ , the left-hand side of (13) equals

\begin{align*}\mathbb{P}_{0}(T_{1}\geq 1,\, T_{e}>1)= \mathbb{P}_{0}(T_{e}>1)=(M)_{0,+},\end{align*}

while the right-hand side equals $\mathbb{P}_{j}(T_{e}>1)=(M)_{j,+}$ . Thus the inequality (13) with $n=1$ follows from the assumption that $(M)_{0,+}\leq (M)_{j,+}$ for $j>0$ .

For $m \geq 1$ , suppose (13) holds for $n=1,\ldots,m$ and $j=1,2,\ldots.$ In particular, the induction hypothesis (see (15)) implies that

(16) \begin{align}\mathbb{P}_{0}(T_{e}>\ell) \leq \mathbb{P}_{1}(T_{e}>\ell) ,\quad \ell=1,\ldots,m . \end{align}

We need to show that for $j=1,2,\ldots,$

(17) \begin{align}\mathbb{P}_{0}(T_{1} \geq m+1,\, T_{e} > m+1) + \sum^{m}_{\ell =1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j}(T_{e}>m+1-\ell) \leq \mathbb{P}_{j}(T_{e}>m+1) . \end{align}

Note that for $j=1,2,\ldots,$

(18) \begin{align}\mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m)\ &+ \sum^{m-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j-1}(T_{e}>m-\ell) \leq \mathbb{P}_{j-1}(T_{e}>m) , \end{align}

(19) \begin{align}\mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m)\ &+ \sum^{m-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j}(T_{e}>m-\ell) \leq \mathbb{P}_{j}(T_{e}>m) , \end{align}

(20) \begin{align}\mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m)\ &+ \sum^{m-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j+1}(T_{e}>m-\ell) \leq \mathbb{P}_{j+1}(T_{e}>m) . \end{align}

Except for $j=1$ in (18), (18)–(20) follow immediately from the induction hypothesis. By (16), $\mathbb{P}_{0}(T_{e}>m-\ell) \leq \mathbb{P}_{1}(T_{e}>m-\ell) $ for $\ell=1,\ldots,m-1$ , so the left-hand side of (18) with $j=1$ equals

\begin{align*}& \mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m) + \sum^{m-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}_{0}(T_{e}>m-\ell) \\[3pt] & \quad \leq \mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m) + \sum^{m-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}_{1}(T_{e}>m-\ell) \\[3pt] & \quad = \mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m) + \sum^{m-1}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell,\, T_{e}>m) \quad (\text{by} ({14})) \\[3pt] & \quad = \mathbb{P}_{0}(T_{e}>m) ,\end{align*}

establishing (18) for $j=1$ .

Note that for $\ell=m$ ,

\begin{align*}& \mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) +\mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}_{j-1}(T_{e}>m-\ell) \\[3pt] & \quad =\mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) +\mathbb{P}_{0}(T_{1}=m)\ \mathbb{P}_{j-1} (T_{e}>0) \\[3pt] & \quad =\mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) +\mathbb{P}_{0}(T_{1}=m) \\[3pt] & \quad =\mathbb{P}_{0}(T_{1}\geq m,\, T_{e}>m) ,\end{align*}

so (18) is equivalent to

(21) \begin{align}& \mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) + \sum^{m}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j-1}(T_{e}>m-\ell) \leq \mathbb{P}_{j-1}(T_{e}>m) . \end{align}

Similarly, (19) and (20), respectively, are equivalent to

(22) \begin{align}& \mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) + \sum^{m}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j}(T_{e}>m-\ell) \leq \mathbb{P}_{j}(T_{e}>m) , \end{align}

(23) \begin{align} & \mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) + \sum^{m}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\ \mathbb{P}_{j+1}(T_{e}>m-\ell) \leq \mathbb{P}_{j+1}(T_{e}>m) . \end{align}

Letting $a_j=M_{j,j-1}$ , $ b_j=M_{j,j}$ , and $c_j=M_{j,j+1}$ , we have

(24) \begin{align}\mathbb{P}_{j}(T_{e} > m+1) & =\mathbb{P}(T_{e}>m+1 \mid X_{0}=j) \notag \\[3pt] & =\mathbb{P}(X_{1}\neq e,\, T_{e}>m+1\mid X_{0}=j) \notag \\[3pt] & = \sum^{j+1}_{r=j-1} \mathbb{P}(X_{1}=r,\, T_{e}>m+1\mid X_{0}=j) \notag \\[3pt] & = a_{j} \mathbb{P}(T_{e}>m+1\mid X_{1}=j-1) + b_{j} \mathbb{P}(T_{e}>m+1\mid X_{1}=j) \notag \\[3pt] &\quad+ c_{j} \mathbb{P}(T_{e}>m+1\mid X_{1}=j+1) \notag \\[3pt] & = a_{j} \mathbb{P}_{j-1}(T_{e}>m) + b_{j} \mathbb{P}_{j}(T_{e}>m) + c_{j} \mathbb{P}_{j+1}(T_{e}>m) . \end{align}

Similarly, for $1 \leq \ell \leq m$ ,

(25) \begin{align}\mathbb{P}_{j}(T_{e}>m+1-\ell)=a_{j} \mathbb{P}_{j-1}(T_{e}> m-\ell)+b_{j} \mathbb{P}_{j}(T_{e} > m-\ell)+ c_{j} \mathbb{P}_{j+1}(T_{e} > m-\ell) . \end{align}

In view of (24) and (25), it follows from (21)–(23) that

(26) \begin{align}(a_{j}+b_{j}+c_{j})\, \mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1) &+ \sum^{m}_{\ell=1} \mathbb{P}_{0}(T_{1}=\ell)\, \mathbb{P}_{j}(T_{e}>m+1-\ell) \leq\mathbb{P}_{j}(T_{e}>m+1). \end{align}

Note that, given $X_0=0$ ,

\begin{equation*}\{T_1 \ge m+1,\, T_e > m+1\}=\{X_1<1,\ldots, X_m<1,\, X_{m+1}\ne e\},\end{equation*}

and

\begin{equation*}\{X_1<1,\ldots,X_m<1\}=\{X_{\ell} \in\{0,-1,-2,\ldots\},\,\ell=1,\ldots,m\}=\{T_1\wedge T_e \ge m+1\}.\end{equation*}

We have

(27) \begin{align}&\mathbb{P}_{0}(T_{1} \geq m+1,\, T_{e}>m+1) \notag \\[3pt] &\quad = \mathbb{P}(X_{1}<1,\ldots,X_{m}<1,\, X_{m+1}\neq e\mid X_{0}=0) \notag \\[3pt] &\quad =\mathbb{P}(X_{1}<1,\ldots,X_{m}<1\mid X_{0}=0)\, \mathbb{P}(X_{m+1}\neq e\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1) \notag \\[3pt] &\quad =\mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1)\, \mathbb{P}(X_{m+1}\neq e\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1) \notag \\[3pt] &\quad \leq\mathbb{P}_{0}(T_{1} \wedge T_{e} \geq m+1)\ (a_{j}+b_{j}+c_{j}). \end{align}

The above inequality follows since

\begin{align*}& \mathbb{P}(X_{m+1} \neq e\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1) \\[3pt] & \quad = \sum_{i \leq 0} \mathbb{P}(X_{m}=i,\, X_{m+1} \neq e\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1) \\[3pt] & \quad = \sum_{i \leq 0} \mathbb{P}(X_{m}=i\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1)\, \mathbb{P}(X_{m+1} \neq e\mid X_{m}=i) \\[3pt] & \quad = \sum_{i \leq 0} \mathbb{P}(X_{m}=i\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1)\ (a_{i}+b_{i}+c_{i}) \\[3pt] & \quad \leq \sum_{i \leq 0} \mathbb{P}(X_{m}=i\mid X_{0}=0,\, X_{1}<1,\ldots,X_{m}<1)\ (a_{j}+b_{j}+c_{j}) \\[3pt] & \quad = a_{j}+b_{j}+c_{j} ,\end{align*}

where the inequality is due to the assumption that $a_{i}+b_{i}+c_{i} \leq a_{j}+b_{j}+c_{j}$ for $i \leq 0 < j$ .

Finally (17) follows from (26) and (27). The proof is complete. □