1 Introduction
1.1 Overview
In this paper, we are focused on studying a simultaneous renewal time for two time-inhomogeneous, discrete-time Markov chains on a general state space. By simultaneous renewal we mean visiting some set C by both chains at the same time.
While general renewal theory is well developed, properties of the renewal sequences generated by time-inhomogeneous Markov chains are not studied so seriously. The literature available for this topic is scant. Some generalizations of the general homogeneous theory could be found, for example, in [21] or [23]. At the same time, the problem under consideration is important from both theoretical and practical perspectives. Some of the existing results can be found in the paper [8], dedicated to investigating continuous-time renewal processes generated by a sequence of independent but not necessary identically distributed random variables. The paper shows that a general renewal equation is solvable using numerical methods and demonstrates an application of this result in actuarial science. Another paper related to the renewal theory (of geometrically ergodic time-homogeneous Markov chains) is [2].
Simultaneous renewal plays an essential role in investigation of the stability of Markov chains, particularly in the time-inhomogeneous case. In the papers [9, 10] a particular coupling construction has been introduced to derive a stability estimate. A key point of the whole stability research is to construct a stochastic dominating sequence for a series of coupling times and estimate the coupling time expectation using that sequence. Later, the stability estimates obtained in [17] were applied to the widow pension actuarial model which allows calculating variables related to this actuarial schema, such as net-premiums and others. In the papers [15, 16, 19, 20] stability estimates are obtained for discrete-space Markov chains in both time-homogeneous and time-inhomogeneous case using the so-called Maximal Coupling technique.
Estimates for the expectation of a simultaneous renewal time obtained in this paper and stability estimates derived from them have many practical applications. In particular, we may point out applications in the actuarial mathematics similar to the widow pension mentioned above. Other examples could be: obtaining premium in actuarial models that are represented by a perturbed Markov chain, such as seasonal factors. Another area of application is the queuing theory. Markov chains stability results enable us to study non-homogeneous qeuing models or models affected by some small non-homogeneous perturbation.
There are many works related to stability estimates which use coupling methods. For example stability estimates for different versions of the same time-homogeneous chain started with different initial distributions, using standard coupling technique could be found in the papers [4, 5]. In [10] we have extended results from [4] and [5] to the stability of two different (but close in some sense) time-inhomogeneous Markov chains by introducing a modified coupling technique which allows chains to couple and de-couple. Such construction leads us to the necessity of investigating properties of the renewal proceses generated by time-inhomogeneous Markov chains. Many works of other authors are using similar coupling techniques to obtain stability estimates or convergence rates, see for example [1, 7] where subgeometrical Markov chains are studied.
Simultaneous renewal has been studied in other works as well. In the article [18] an estimate for a coupling moment (what we call simultaneous renewal in the present article) for time-homogeneous processes was obtained under the existence condition of the second moment of the renewal sequence. The critical feature of the proof there was the Daley inequality (see [3]) which gives an estimate for average time of the excess of a renewal process in the homogeneous case. Later, in the paper [13] the Daley inequality was extended to the time-inhomogeneous case which allows obtaining an estimate for simultaneous renewal in the case of a square-integrable dominating sequence for a time-inhomogeneous process (see [12]). This estimate involves the second moment of the domination sequence, and in the present paper, we relax that condition and only require the existence of the first moment. We will compare the results of the present paper and [12].
In the paper [14] there is a theorem that shows finiteness of the expectation of the simultaneous renewal time but a computable estimate is not available. There are also examples of how to check the non-lattice regularity condition for a renewal sequence which is involved in all the results related to the time-inhomogeneous case.
We also ask the reader to pay attention to the classical books [22, 24], devoted to the coupling method.
This paper consists of 4 sections. Section 1 contains introduction and main definitions.
The main result is stated in Section 2. It also includes a detailed explanation of the conditions of the main theorem.
An example of an application of the main result concerning a birth-death process can be found in Section 3.
Section 4 is just the conclusion.
1.2 Definitions and notations
The main object of the study is a pair of time-inhomogeneous, independent, discrete time Markov chains defined on the probability space $(\varOmega ,\mathfrak{F},\mathbb{P})$, with the values in the general state space $(E,ℰ)$. We will denote these chains as ${X_{n}^{(1)}}$ and ${X_{n}^{(2)}}$, $n\ge 0$, respectively.
We will use the following notation for the one-step transition probabilities
for any $x\in E$, $l\in \{1,2\}$, and any $A\in ℰ$.
Our primary goal is to obtain an upper bound for the expectation of simultaneous hitting a given set C by both chains. An application usually dictates Applications usually dictate the choice of the set C. For a discrete state space consisting of integers the very typical choice is $C=\{0\}$, although this is not a single possible choice. Moreover, we do not assume that the set C consists of a single element. We will also allow arbitrary initial conditions for the chains, and assume that each chain has a finite expectation for a first time hitting the set C for a given initial state.
Define the renewal intervals
where $l\in \{1,2\}$, $n\ge 1$, and renewal times
(2)
\[ \begin{array}{c}{\theta _{0}^{(l)}}=\inf \big\{t\ge 0,{X_{t}^{(l)}}\in C\big\},\\ {} {\theta _{n}^{(l)}}=\inf \big\{t>{\theta _{n-1}^{(l)}},{X_{t}^{(l)}}\in C\big\}-{\theta _{n-1}^{(l)}},\end{array}\]Then, for each $x\in C$, we can define the renewal probabilities
and the sequence
We will also need a notation for sums of ${g_{n}^{(t,l)}}$:
${G_{n}^{(t,l)}}$ can be interpreted as an estimate for the probability that renewal has not happened up to the time n.
2 Main result
First, we introduce a condition that guarantees finiteness of the expectation of the renewal times for both chains. In this paper, we use a dominating sequence for this purpose.
Condition A
There is a non-increasing sequence ${G_{n}},\hspace{2.5pt}n\ge 0$, such that:
To make the further reasoning simpler, we allow the index n in ${G_{n}}$ to be negative. In this case we assume: ${G_{n}}={G_{0}}$, $n<0$.
We do not require this dominating sequence to be probabilistic and allow ${G_{0}}\ge 1$. Condition A will enable us to ascertain that both chains ${X^{(1)}},{X^{(2)}}$ will have a finite expectation of the renewal time, which is a necessary condition for having a finite expectation of simultaneous renewal.
Opposing the paper [12] we do not require the existence of the second moment for a dominating sequence.
Next, we need some regularity condition on ${u_{n}^{(t,l)}}$ which guarantees its separation from 0.
Condition B
There is a constant $\gamma >0$ and a number ${n_{0}}\ge 0$, such that for all $t\ge 0$, $l\in \{1,2\}$, and $n\ge {n_{0}}$
It is essential that such condition also guarantees certain “regularity” and non-periodicity of a chain. The periodic chains do not satisfy it.
There are various results which allow checking the condition (A) practically. See, for example [11], Theorems 4.1, 4.2, 4.3. We will use some of them later.
Before we state the main theorem, we should introduce some definitions, which are used in the proof, and the auxiliary lemma.
The notations below are the same as in [12]:
\[\begin{array}{l}\displaystyle {\nu _{0}}:=\min \big\{j\ge 1:{\tau _{j}^{1}}>{n_{0}}\big\},\\ {} \displaystyle {B_{0}}:={\tau _{{\nu _{0}}}^{1}},\\ {} \displaystyle {\nu _{1}}:=\min \big\{j\ge {\nu _{0}}:{\tau _{j}^{2}}-{\tau _{{\nu _{0}}}^{1}}>{n_{0}},\hspace{2.5pt}\text{or}\hspace{2.5pt}{\tau _{j}^{2}}-{\tau _{{\nu _{0}}}^{1}}=0\big\},\\ {} \displaystyle {B_{1}}:={\tau _{{\nu _{1}}}^{2}}-{\tau _{{\nu _{0}}}^{1}},\end{array}\]
and further on,
\[\begin{array}{l}\displaystyle {\nu _{2m}}:=\min \big\{j\ge {\nu _{2m-1}}:\hspace{2.5pt}{\tau _{j}^{1}}-{\tau _{{\nu _{2m-1}}}^{2}}>{n_{0}},\hspace{2.5pt}\text{or}\hspace{2.5pt}{\tau _{j}^{1}}-{\tau _{{\nu _{2m-1}}}^{2}}=0\big\},\\ {} \displaystyle {B_{2m}}:={\tau _{{\nu _{2m}}}^{1}}-{\tau _{{\nu _{2m-1}}}^{2}},\\ {} \displaystyle {\nu _{2m+1}}:=\min \{j\ge {\nu _{2m}}:\hspace{2.5pt}{\tau _{j}^{2}}-{\tau _{{\nu _{2m}}}^{1}}>{n_{0}}\hspace{0.1667em},\hspace{2.5pt}\text{or}\hspace{2.5pt}{\tau _{j}^{2}}-{\tau _{{\nu _{2m}}=0}^{1}},\\ {} \displaystyle {B_{2m+1}}:={\tau _{{\nu _{2m+1}}}^{2}}-{\tau _{{\nu _{2m}}}^{1}}.\end{array}\]
We will call ${\nu _{k}}$ renewal trials. Let’s define $\tau =\min \{n\ge 1:{B_{n}}=0\}$ and put ${B_{t}}=0$, if $t\ge \tau $.
For ease of use, we will introduce the variable
Note, that ${S_{2n}}={\tau _{{\nu _{2n}}}^{1}}$, ${S_{2n+1}}={\tau _{{\nu _{2n+1}}}^{2}}$, however, the use of the variable ${S_{n}}$ makes the text much more readable.
Theorem 1.
Assume that chains $({X_{n}^{(l)}})$, $l\in \{1,2\}$, start with some initial distributions ${\lambda _{1}}$ and ${\lambda _{2}}$ and that expectations of the first time each process hits the set C are finite. Denote them as ${m_{1}}({\lambda _{1}})$ and ${m_{2}}({\lambda _{2}})$ respectively. Assume also, that conditions (A) and (B) introduced above hold true. In this case, there exists a dominating sequence ${\hat{S}_{n}}$ for the simultaneous renewal time T:
such that
Proof.
First, we assume that ${\theta _{0}^{(2)}}=0$, which means that the second chain starts from the set C.
Next, the upper bound for T was introduced in [12] (it trivially follows from definitions):
We introduce the variable
Then ${\theta _{0}^{(1)}}+{T^{\prime }}$ is pointwise bigger than T, and so it stochastically dominates T.
So we will focus on building a dominating sequence for ${T^{\prime }}$ and estimating its expectation.
Let us consider
\[ \mathbb{P}\big\{{T^{\prime }}>n\big\}={\sum \limits_{k=0}^{n}}\mathbb{P}\{{S_{k}}\le n<{S_{k+1}}\}={\sum \limits_{k=0}^{n}}{\sum \limits_{j=k}^{n}}\mathbb{P}\{{S_{k}}=j,{B_{k+1}}>n-j\}.\]
Note that some terms are equal to 0 in the latter sum because each renewal trial takes at least ${n_{0}}$ steps, but this fact does not affect our reasoning.Lemma 1 gives us the inequality
which allows us to build the upper bound for $\mathbb{P}\{{T^{\prime }}>n\}$:
\[\begin{aligned}{}& \mathbb{P}\big\{{T^{\prime }}>n\big\}\le {\sum \limits_{k=0}^{n}}{\sum \limits_{j=k}^{n}}\mathbb{P}\{{S_{k}}=j,\tau \ge k\}{G_{n-j-{n_{0}}}}\\ {} & \hspace{1em}={\sum \limits_{j=0}^{n}}{G_{n-j-{n_{0}}}}{\sum \limits_{k=0}^{j}}P({S_{k}}=j,\tau \ge k).\end{aligned}\]
So we can put
\[ {\hat{S}^{\prime }_{n}}={\sum \limits_{j=0}^{n}}{G_{n-j-{n_{0}}}}{\sum \limits_{k=0}^{j}}P({S_{k}}=j,\tau \ge k),\]
and so the dominating sequence for $\mathbb{P}\{{T^{\prime }}>n\}$ is built.Let’s now estimate its expectation:
\[\begin{aligned}{}\mathbb{E}\big[{T^{\prime }}\big]& =\sum \limits_{n\ge 0}\mathbb{P}\big\{{T^{\prime }}>n\big\}\le \sum \limits_{n\ge 0}{\hat{S}^{\prime }_{n}}\\ {} & =\sum \limits_{n\ge 0}\Bigg({\sum \limits_{j=0}^{n}}{G_{n-j-{n_{0}}}}{\sum \limits_{k=0}^{j}}P({S_{k}}=j,\tau \ge k)\Bigg)\\ {} & =\bigg(\sum \limits_{n\ge 0}{G_{n-{n_{0}}}}\bigg)\times \bigg(\sum \limits_{n\ge 0}\sum \limits_{k\ge n}\mathbb{P}\{{S_{n}}=k,\tau \ge n\}\bigg)\\ {} & =({n_{0}}{G_{0}}+m)\sum \limits_{n\ge 0}\mathbb{P}\{\tau \ge n\}.\end{aligned}\]
Lemma 8.5 from [12] gives us the inequality
which yields
Proof.
We start with the assumption that k is even. We can write then:
where $u<j$, and $v\ge u$ is a value of η. Note that
\[ \mathbb{P}\{{S_{k}}=j,{B_{k+1}}>t\}=\mathbb{P}\big\{{S_{k}}=j,{X_{n}^{(2)}}\notin C,n\in \{j,j+{n_{0}},\dots ,j+t\}\big\}.\]
Let’s denote as η the last renewal of the chain ${X^{(2)}}$ before the time $j+{n_{0}}$. By the construction of the sequence ${B_{k}}$,
Indeed, if $k>0$, this means that ${S_{k-1}}={S_{k}}-{B_{k}}>0$ is a renewal time for the chain ${X^{(2)}}$. If $k=0$, then we should put ${S_{-1}}={S_{0}}-{B_{0}}=0$, but the chain ${X^{(2)}}$ has started in C, so $\eta >0$ by the condition of the lemma. So by construction, we have:
Let us denote the sets
and inspect the sample path of the chain ${X^{(2)}}$ after the moment η:
(12)
\[\begin{aligned}{}\mathbb{P}\{{S_{k}}=j,{B_{k+1}}>t\}& =\mathbb{P}\big\{{S_{k}}=j,{X_{j}^{(2)}}\notin C,{A_{2}}(j+{n_{0}},j+t)\big\}\\ {} & =\sum \limits_{u,v}\mathbb{P}\big\{{S_{k-1}}=u,\tau \ge k,{A_{1}}(u+{n_{0}},j-1),\\ {} & \hspace{2em}\hspace{2em}{X_{j}^{(1)}}\in C,{X_{v}^{(2)}}\in C,{A_{2}}(v+1,j+t)\big\},\end{aligned}\]
\[ \big\{{S_{k-1}}=u,{X_{u}^{(1)}}\notin C\big\}=\{{S_{k-1}}=u,\tau >k-1\}=\{{S_{k-1}}=u,\tau \ge k\}.\]
Let us recall that the chains ${X^{(1)}}$ and ${X^{(2)}}$ are independent and so we can split the probability in the formula (12) into the product:
\[\begin{aligned}{}& \mathbb{P}\big\{{S_{k-1}}=u,\tau \ge k,{A_{1}}(u+{n_{0}},j-1),{X_{j}^{(1)}}\in C,{X_{v}^{(2)}}\in C,\hspace{2.5pt}{A_{2}}(v+1,j+t)\big\}\\ {} & \hspace{1em}={\int _{E\times C}}\mathbb{P}\big\{{S_{k-1}}=u,{A_{1}}(u+{n_{0}},v),\big({X_{v}^{(1)}},{X_{v}^{(2)}}\big)=(dx,dy)\big\}\\ {} & \hspace{2em}\times \mathbb{P}\big\{{A_{1}}(v+1,j-1),{X_{j}^{(1)}}\in C,{A_{2}}(v+1,j+t)|\big({X_{v}^{(1)}},{X_{v}^{(2)}}\big)=(x,y)\big\}\\ {} & \hspace{1em}={\int _{E\times C}}\mathbb{P}\big\{{S_{k-1}}=u,\tau \ge k,{A_{1}}(u+{n_{0}},v),\big({X_{v}^{(1)}},{X_{v}^{(2)}}\big)=(dx,dy)\big\}\\ {} & \hspace{2em}\times \mathbb{P}\big\{{A_{1}}(v+1,j-1),{X_{j}^{(1)}}\in C|{X_{v}^{(1)}}=x\big\}\mathbb{P}\big\{{A_{2}}(v+1,j+t)|{X_{v}^{(2)}}=y\big\}.\end{aligned}\]
But $\mathbb{P}\{{A_{2}}(v+1,j+t)|{X_{v}^{(2)}}=y\}$, $y\in C$, is just the probability that the next renewal after v will not happen until the moment $j+t$. So we have
where the latest inequality follows from the Condition A.The above reasoning is valid in the case $\eta <j$, however, the case $\eta \in \{j+1,j+{n_{0}}-1\}$ yields the same result. The maximal possible value of v is $j+{n_{0}}$, so, using the fact that sequence ${G_{n}}$ is non-increasing, it follows from (13) that
which gives the estimate that does not depend on v. Taking into account the inequality (14) we can derive
(14)
\[ \underset{y\in C}{\sup }\mathbb{P}\big\{{A_{2}}(v+1,j+t)|{X_{v}^{(2)}}=y\big\}\le {G_{j+t-v}}\le {G_{t-{n_{0}}}},\](15)
\[\begin{aligned}{}& \mathbb{P}\{{S_{k}}=j,{B_{k+1}}>t\}\\ {} & \hspace{1em}\le \sum \limits_{u,v}{\int _{E\times C}}\mathbb{P}\big\{{S_{k-1}}=u,\tau \ge k,{A_{1}}(u+{n_{0}},v),({X_{v}^{(1)}},{X_{v}^{(2)}})=(dx,dy)\big\}\\ {} & \hspace{2em}\times \mathbb{P}\big\{{A_{1}}(v+1,j-1),{X_{j}^{(1)}}\in C|{X_{v}^{(1)}}=x\big\}{G_{t-{n_{0}}}}\le \mathbb{P}\{{S_{k}}=j,\tau \ge k\}{G_{t-{n_{0}}}}.\end{aligned}\]To complete the proof, we should consider the case when k is odd. In this case, $k>0$ which means $k-1\ge 0$ and we don’t have a problem with $k=0$ like in the even case. So, similar reasoning will yield the same inequality for odd k. □
3 Application to the birth-death processes
In the paper [12] we had derived an estimate for a simultaneous renewal of two time-inhomogeneous birth-death processes ${X^{(1)}}$ and ${X^{(2)}}$ with the following transition probabilities on the t-th step:
and
(16)
\[ {P_{t}}=\left(\begin{array}{c@{\hskip10.0pt}c@{\hskip10.0pt}c@{\hskip10.0pt}c@{\hskip10.0pt}c@{\hskip10.0pt}c}{\alpha _{t0}}& 1-{\alpha _{t0}}& 0& 0& 0& \dots \\ {} 0& {\alpha _{t1}}& 0& 1-{\alpha _{t1}}& 0& \dots \\ {} 0& 0& {\alpha _{t2}}& 0& 1-{\alpha _{t2}}& \dots \\ {} \dots \end{array}\right)\](17)
\[ {Q_{t}}=\left(\begin{array}{c@{\hskip10.0pt}c@{\hskip10.0pt}c@{\hskip10.0pt}c@{\hskip10.0pt}c@{\hskip10.0pt}c}{\beta _{t0}}& 1-{\beta _{t0}}& 0& 0& 0& \dots \\ {} 0& {\beta _{t1}}& 0& 1-{\beta _{t1}}& 0& \dots \\ {} 0& 0& {\beta _{t2}}& 0& 1-{\beta _{t2}}& \dots \\ {} \dots \end{array}\right)\]An estimate from [12] involves the second moment of the dominating sequence. Let us compare an estimate from [12] with the one that follows from Theorem 1.
We will start with building γ. As in [12] we notice that for every $t>0$, ${g_{1}^{(l)}}={\alpha _{t0}}>0$, and assume
As it has been shown in the [12] γ can be chosen in the following way:
with the ${n_{0}}=0$.
(19)
\[ \gamma =\exp \big(\hat{\mu }ln({\gamma _{0}})/{\gamma _{0}}\big)={\gamma _{0}^{\hat{\mu }/{\gamma _{0}}}}\]We will use the same dominating sequence as in [12]. To do this, we consider a standard random walk with a parameter $p>1/2$ and a probability ${f_{n}}$ of a first return to 0 in n steps. It has been shown in [6], Chapter XIII, that the generating function $F(z)$ for ${f_{n}}$ looks like
We have shown in the [12] that ${G_{n}}=\textstyle\sum \limits_{k>n}{f_{n}}/p$ is a dominating sequence (non-probabilistic) for renewal sequences generated by ${X^{(1)}}$ and ${X^{(2)}}$, if
The estimate for the expectation of the simultaneous renewal time in case of both chains started at C looks like
where
In our case the estimate looks like
So, we can see that
for all $\gamma \in (0,\frac{\sqrt{5}-1}{2})$, $\gamma (1+\gamma )<1$ which means that ${E_{2}}$ is a better estimate than ${E_{1}}$. In the same time, ${\gamma _{0}}$ is typically a small number, which makes γ to be a very small number. So, the improvement in estimate can be significant for practical applications.
4 Conclusions
In this article, we obtained an estimate for the expectation of the simultaneous renewal time for two time-inhomogeneous, discrete-time Markov chains on a general state space. By the simultaneous renewal of two Markov chains X and ${X^{\prime }}$ we understand the first moment of hitting a specific set C by both chains.
We have shown that under conditions (A) and (B) an estimate has the form
We have shown how the parameters $\gamma ,{n_{0}},{G_{0}},{m_{1}}({\lambda _{1}}),{m_{2}}({\lambda _{2}})$, and the sequence ${\hat{S}_{n}}$ included in the estimate can be calculated.
This result allows us to refine the stability estimate for two time-inhomogeneous Markov chains, which is a subject of a further investigation.
