In this paper, we consider two time-inhomogeneous Markov chains Xt(l), l∈{1,2}, with discrete time on a general state space. We assume the existence of some renewal set C and investigate the time of simultaneous renewal, that is, the first positive time when the chains hit the set C simultaneously. The initial distributions for both chains may be arbitrary. Under the condition of stochastic domination and nonlattice condition for both renewal processes, we derive an upper bound for the expectation of the simultaneous renewal time. Such a bound was calculated for two time-inhomogeneous birth–death Markov chains.
Simultaneous renewal is an important topic for a practical application of Markov chains. Although it has its own value, for example, in queuing theory, we are interested in its investigation because it plays an essential role in coupling construction, which can be used to derive stability estimates of the n-step transition probabilities and other results like the law of large numbers and limit theorems.
For example, in [5, 6], we can find how a stability estimate can be calculated using the coupling method for two time-inhomogeneous Markov chains with discrete time on the general state space. Good examples of applications of the coupling method (for both homogeneous and inhomogeneous Markov chains) are given in [2, 3].
It worth mentioning that the coupling construction for time-inhomogeneous chains is slightly different from its classical setup (see, e.g., [16, 17]). Such a time-inhomogeneous coupling for general state space can be found in [5]. Its modification, called the maximal coupling, can be used for a discrete space. More information about maximal coupling and its application to stability in the time-homogeneous case can be found in [14, 15].
For maximal coupling and its application to stability in the time-inhomogeneous case, see [10–12].
The crucial problem in the application of the results in the listed papers was calculation of the expectation for the coupling moment deriving from the simultaneous renewal. But there were no good estimates for the expectation of a simultaneous renewal for the time-inhomogeneous case.
For the time-homogeneous case, the paper [13] proposes such an estimate based on the Daley inequality (see [1]).
In [9], we derived conditions (see Thm. 3.1) that guarantee that the expectation for the simultaneous renewal time is finite. But there were no practical estimates for the expectation.
In [8], we derived an analogue of the Daley inequality that is used in this paper. The key condition for this inequality is a finiteness of the second moment for the stochastic dominant of the original renewal process. Thats why it is a crucial condition for the estimate construction.
Definitions and notation
We consider two independent time-inhomogeneous Markov chains with discrete time and general state space (E,E). We assume that both chains are defined on the same probability space (Ω,F,P). Denote these chains as (Xn(1)), (Xn(2)), n≥0. We use the following notation for the one-step transition probabilities:
Plt(x,A)=P{Xt+1(l)∈A|Xt(l)=x},
where x∈E is an arbitrary element, l∈{1,2}, and A∈E is an arbitrary set.
We continue to use the definitions and notation from [9]. We consider some set C∈E, and our goal is to find an upper bound for the expectation of the first time of visiting the set C by both chains.
Define the renewal intervals
θ0(l)=inf{t≥0,Xt(l)∈C},θn(l)=inf{t≥θn−1(l),Xt(l)∈C},
where l∈{1,2}, n≥1, and renewal times
τn(l)=∑k=0nθk(l),l∈{1,2},n≥1.
Then we can define the renewal probabilities
gn(t,l)=P{θk(l)=n|τk−1(l)=t},l∈{1,2},n≥1.
It is worth mentioning that, in general, gn(t,l) also depends on the value x of Xt(l) which can hit different states inside C. However, we will omit x for simplicity. We refer the reader to [9] for more details about definition (4).
Let us define the renewal sequence recursively:
u0(t,l)=1,un(t,l)=∑k=0n−1uk(t,l)gn−k(t+k,l).
The time of simultaneous hitting the set C is defined as
T=inf{t>0:∃m,n,t=τm(1)=τn(2)}.0:\hspace{2.5pt}\exists m,n,\hspace{2.5pt}t={\tau _{m}^{(1)}}={\tau _{n}^{(2)}}\big\}.\]]]>
The notion of the overshoot or excess is defined as follows:
Rn(l)=inf{t>n:Xt(l)∈C},l∈{1,2}.n:\hspace{2.5pt}{X_{t}^{(l)}}\in C\big\},\hspace{1em}l\in \{1,2\}.\]]]>
It is, in fact, the next time after n when the chain X(l) hits the set C.
Estimate for the expectation of the simultaneous hitting time
First, we need put the condition on un(t,l) that guarantees its separation from 0. In the time-homogeneous case, this follows from the renewal theorem, but for the time-inhomogeneous case, there is no such theorem. Therefore, we need the following condition.
Condition A. There are a constant γ>00$]]> and a number n0≥0 such that, for all t, l and n≥n0,
un(t,l)≥γ.
It is important that this condition also guarantees certain “regularity” of a chain in terms of periodicity. The periodic chains obviously do not satisfy it.
There are various theorems that allow us to check Condition A in practice. See, for example, [7], Theorems 4.1, 4.2, 4.3. We will later use some of them.
We need a condition of the stochastic domination in order to apply Theorem 3.1 from [8].
Condition B. Distributions (gn(t,l)) are stochastically dominated by some sequence (gˆn), gˆn≥0, which means that
Gn(t,l)=∑k>ngk(t,l)≤Gˆn=∑k>ngˆkn}{g_{k}^{(t,l)}}\le \hat{G}_{n}=\sum \limits_{k>n}\hat{g}_{k}\]]]>
and that the stochastic dominant (gˆn) has finite first and second moments
μˆ1=∑k≥1kgˆk=∑k≥0Gˆk<∞,μˆ2=∑k≥1k2gˆk<∞.
The sequence Gˆn is nonincreasing because gˆn≥0.
It is worth mentioning that we do not require (gˆn) to be a probability distribution, that is, the total mass ∑k≥1gˆk not necessarily equals 1.
Assume that conditions (A) and (B) hold for the chains(Xn(l)),l∈{1,2}, defined before and that the renewal sequences are generated by them. Then the expectation of the simultaneous hitting time for the set C satisfies the inequalityE[T]≤E[θ0(1)]+E[θ0(2)]+Mγ,whereM=μˆ2+μˆ1(γ−1+n0).
Let us recall the notation from [9]:
ν0:=min{j≥1:τj1>n0},n_{0}\big\},\]]]>B0:=τν01,ν1:=min{j≥ν0:τj2−τν01>n0,orτj2−τν01=0},n_{0},\hspace{2.5pt}\text{or}\hspace{2.5pt}{\tau _{j}^{2}}-{\tau _{\nu _{0}}^{1}}=0\big\},\]]]>B1:=τν12−τν01,
and further on
ν2m:=min{j≥ν2m−1:τj1−τν2m−12>n0,orτj1−τν2m−12=0},n_{0}\hspace{0.1667em},\hspace{2.5pt}\text{or}\hspace{2.5pt}{\tau _{j}^{1}}-{\tau _{\nu _{2m-1}}^{2}}=0\big\},\]]]>B2m:=τν2m1−τν2m−12,ν2m+1:=min{j≥ν2m:τj2−τν2m1>n0,orτj2−τν2m1=0},n_{0}\hspace{0.1667em},\hspace{2.5pt}\text{or}\hspace{2.5pt}{\tau _{j}^{2}}-{\tau _{\nu _{2m}}^{1}}=0\big\},\]]]>B2m+1:=τν2m+12−τν2m1.
The moments νk are called coupling trials. Let us define τ=min{n≥1:Bn=0} and the sequence of sigma-fields Bn, n≥0, by
Bn=σ[Bk,νk,τjl,k≤n,j≤νn].
We will use the same idea as in the Theorem 5.1 from [9].
First, we assume that θ0(2)=0, which means that the second chain starts from the set C.
The next representation of time T is following directly from the definitions:
T≤θ0(1)+∑n=0τBn=θ0(1)+∑n≥0Bn1τ>n.n}.\]]]>
Using Lemma 1 and the fact that {τ>n−1}∈Bn−1n-1\}\in \mathfrak{B}_{n-1}$]]>, we can derive the following inequality:
E[Bn1τ>n|Bn−1]=E[Bn1τ≥n|Bn−1]+E[01τ=n|Bn−1]=1τ≥nE[Bn|Bn−1]≤1τ≥nM.n}|\mathfrak{B}_{n-1}]& \displaystyle =E[B_{n}\mathbb{1}_{\tau \ge n}|\mathfrak{B}_{n-1}]+E[\mathbb{01}_{\tau =n}|\mathfrak{B}_{n-1}]\\{} & \displaystyle =\mathbb{1}_{\tau \ge n}E[B_{n}|\mathfrak{B}_{n-1}]\le \mathbb{1}_{\tau \ge n}M.\end{array}\]]]>
Lemma 8.5 from [9] implies
P{τ>n}≤(1−γ)n.n\}\le {(1-\gamma )}^{n}.\]]]>
Taking the unconditional expectation of the both parts in (14) gives us
E[Bn1τ>n]≤MP{τ>n}≤M(1−γ)n.n}]\le M\mathbb{P}\{\tau >n\}\le M{(1-\gamma )}^{n}.\]]]>
Applying this inequality to (13), we have
E[T]≤E[θ0]+E[∑n=0τBn]=E[θ0]+∑n≥0E[Bn1τ>n]≤E[θ0]+∑n≥0M(1−γ)n=E[θ0]+Mγ.n}]\\{} & \displaystyle \le \mathbb{E}[\theta _{0}]+\sum \limits_{n\ge 0}M{(1-\gamma )}^{n}=\mathbb{E}[\theta _{0}]+\frac{M}{\gamma }.\end{array}\]]]>
Now, we have to get rid of the assumption θ0(2)=0. The same calculations as in [9] after formula (20) give us
E[T]≤E[max(θ0(1),θ0(2))]+Mγ≤E[θ0(1)]+E[θ0(2))]+Mγ.
□
Application to the birth–death processes
Consider two time-inhomogeneous processes X(1) and X(2) with the following transition probabilities on the tth step:
Pt=αt01−αt0000…0αt101−αt10…00αt201−αt2……
and
Qt=βt01−βt0000…0βt101−βt10…00βt201−βt2…….
We would like to estimate the expectation applying Theorem 1. So we have to check the regularity condition A and the domination condition B.
We will need the second moment of the dominating distribution, which is difficult to derive for chains X(1) and X(2). So the idea is to construct a domination sequence based on some simple homogeneous Markov chain whose renewal sequence is well studied and whose second moment can be calculated easily. The closest chain similar to the birth–death chains we consider here is a random walk on the half-line.
The domination sequence based on such a random walk is constructed in Lemma 2, and Lemma 3 gives its first and second moments that we need for Theorem 1.
Next, we will check regularity condition A. First, we assume that, for every t>00$]]>, g1(l)=αt0>00$]]>, and
γ0=inft{αt0,βt0}>0.0.\]]]>
We will use Corollary to Theorem 4.2 from [7] in order to check Condition A. It says that if g1(t)>00$]]> and a domination sequence exists, then Condition A holds. Moreover, its proof (see [7, p. 12], inequality for F(G)) contains an estimate for γ:
γ=exp(μˆln(γ0)/γ0).
Finally, we can state the following result.
Assume that for chains with transition probabilitiesPt,Qtdefined before, condition (20) holds and that there exists p that satisfies condition (28) for both chainsX(1)andX(2). If both chains start from the zero state, then the expectation of their simultaneous renewal satisfies the inequalityE[T]≤μˆ2/γ+μˆ1/γ2,whereμˆ1,μˆ2are defined in Lemma3, and γ is defined in (21).
The statement of the theorem follows from Theorem 1, applied to chains X(1) and X(2) with domination sequence constructed in Lemma 2, the constant γ defined before, and the variables μˆ1 and μˆ2 calculated in Lemma 3. □
Auxiliary results
We have the inequalityE[Bn|Bn−1]≤M,forn≥1, where M is defined in (12).
From Lemma 8.3 of [9] we can derive:
E[B2n+1|B2n]=∑tE[Rt+n0(2)]1τν2n(1)=t,E[B2n|B2n−1]=∑tE[Rt+n0(1)]1τν2n−1(2)=t.
At the same time, Theorem 3.1 from [8] gives us the inequality
E[Rm(l)]≤M,m≥0,l∈{0,1},
taking into account the domination condition B.
Putting (25) into formulas (24) yields the required result (23). □
Consider the following time-inhomogeneous birth–death Markov chainZtwith the transition probabilities on the t-th stepPt=αt01−αt0000…0αt101−αt10…00αt201−αt2……,and the time-homogeneous random walkZˆtwith the transition probability matrixPˆ=01000…p01−p00…0p01−p0……,.LetC={0},and letgn(t)be a distribution of the first after t returning into 0 for the chain Z, which is in the zero state at the moment t.
Assume that there exists some p such that, for all t, i, s, j, the following inequations hold:p>1/2,p(1−p)≥(1−αti)αsj,∀t,s,i,j.1/2,\\{} p(1-p)\ge (1-\alpha _{ti})\alpha _{sj},\hspace{1em}\forall t,s,i,j.\end{array}\]]]>Denote byfnthe renewal probability for the chainZˆt(fnis the probability of the first returning to 0 for the chainZˆstarted at 0):fn=Pˆ{Zˆ0=0,Zˆ1≠0,…,Zˆn−1≠0,Zˆn=0},and letgˆn=fn/p,n>11$]]>, andgˆ1=1.
Then the sequence(gˆn)n≥1stochastically dominatesgn(t), or, in other words,Gk(t)≤Gˆk,whereGn(t)=∑k>ngk(t)n}{g_{k}^{(t)}}$]]>,Gˆn=∑k>ngˆkn}\hat{g}_{k}$]]>, andP,EandPˆ,Eˆare the probabilities and expectations on the canonical probability space for the chains Z andZˆ, respectively.
First of all, notice that (gˆn) is not a probability distribution. But this is not a big problem since the domination sequence in our construction does not have to be a distribution.
We will show that
gˆn≥gn(t),
for all t,n.
Let us start with n=1:
g1(t)=αt0<1=gˆ1.
For n>11$]]>, consider the event
A(2n)t={Zt=0,Zt+1≠0,…,Zt+2n−1≠0,Zt+2n=0}.
It can be interpreted as a set of trajectories ω=(ω1,…,ω2n), ωi∈{+1,−1}, where ωi=+1 if Zt+i goes up and ωi=−1 otherwise. It is clear that, in order to return back to 0 at time 2n, there should be exactly n steps up (the first one must be step up) and n steps down. It is worth mentioning that not every trajectory of length 2n that has n steps up and n down belongs to A(2n)t because some of them might visit 0 before 2n+t, which is not acceptable for A(2n)t. The exact number of such trajectories in A(2n)t is unknown and not important for this proof. What is important, is that each ω∈A(2n)t corresponds to the same trajectory for the chain Zˆ. This means that summing Pˆ{ω} for all ω∈A(2n)t gives the probability f2n. Strictly speaking, the chains Z and Zˆ are defined on different probability spaces, but there is an obvious correspondence between the trajectories, and the difference is only in the probabilities. So we can use the same symbol ω for both.
Since ω has exactly n steps up and n steps down, its probability is a product of n different (1−αtini) and n different αtj,ni+1, for i,j=1,n‾. Notice that some of ni can be the same.
This means that, after reordering, the probability of such ω can be presented as
P{ω}=∏((1−αtini)αtjni+1),
for some ti,ni,tj. We emphasize again that the terms in that product may repeat, but this is not important for this proof.
At the same time, it follows from condition (28) that for any indexes, αtn(1−αsm)<p(1−p) and
P{ω}≤(p(1−p))n−1=Pˆ{ω}/p.
Summing over all such ω, we obtain (31) for n>11$]]>. □
The sequence(gˆn)defined in Lemma2has the finite first and second momentsμˆ1=2/(2p−1)+1,μˆ2=(2p−1)−1(2+8(1−p)1−4p)+2/(2p−1)+1.
First we note that since gˆn=fn/p, n>11$]]>, and gˆ1=1=1+f1, we have μˆ1=μ1/p+1 and μˆ2=μ2/p+1, where μ1 and μ2 are the expectation and the second moment for the probability distribution fn,n≥1.
The generating function F(z) for the distribution fn equals (see, e.g., [4, Ch. XIII])
F(z)=1−1−4p(1−p)s22(1−p).
So, μ1=F′(1) and μ2=F″(1)+μ1. □
ReferencesDaley, D.: Tight bounds for the renewal function of a random walk. Ann. Probab.8, 615–621 (1980). MR0573298Douc, R., Moulines, E., Soulier, P.: Practical drift conditions for subgeometric rates of convergence. Ann. Appl. Probab.14, 1353–1377 (2004). MR2071426. doi:10.1214/105051604000000323Douc, R., Moulines, E., Soulier, P.: Quantitative bounds on convergence of time-inhomogeneous Markov chains. Ann. Appl. Probab.14, 1643–1665 (2004). MR2099647. doi:10.1214/105051604000000620Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. John Wiley and Sons (1957). MR0088081Golomoziy, V.: A subgeometric estimate of the stability for time-homogeneous Markov chains. Theory Probab. Math. Stat.81, 35–50 (2010). MR2667308. doi:10.1090/S0094-9000-2010-00808-8Golomoziy, V.: An estimate of the stability for nonhomogeneous Markov chains under classical minorization condition. Theory Probab. Math. Stat.88, 35–49 (2014). MR3112633. doi:10.1090/S0094-9000-2014-00917-5Golomoziy, V.: An inequality for the coupling moment in the case of two inhomogeneous Markov chains. Theory Probab. Math. Stat.90, 43–56 (2015)Golomoziy, V.: An estimate for an expectation of the excess of the renewal sequence generated by the non-homogeneous Markov chain under a condition of existence square-integrable stochastic dominant. Theory Probab. Math. Stat.94, 50–59 (2016) (in Ukrainian)Golomoziy, V., Kartashov, M.: On the integrability of the coupling moment for time-inhomogeneous Markov chains. Theory Probab. Math. Stat.89, 1–12 (2014)Golomoziy, V., Kartashov, M.: Maximal coupling and stability of discrete non-homogeneous Markov chains. Theory Probab. Math. Stat.91, 17–27 (2015). MR3364120Golomoziy, V., Kartashov, M.: Maximal coupling and v-stability of discrete inhomogeneous Markov chains. Theory Probab. Math. Stat.93, 22–33 (2015) (in Ukrainian)Golomoziy, V., Kartashov, M., Kartashov, Y.: Impact of the stress factor on the price of widow’s pensions. Proofs. Theory Probab. Math. Stat.92, 17–22 (2016)Kartashov, M., Golomoziy, V.: The mean coupling time for independent discrete renewal processes. Theory Probab. Math. Stat.84, 79–86 (2012). MR2857418. doi:10.1090/S0094-9000-2012-00855-7Kartashov, M., Golomoziy, V.: Maximal coupling procedure and stability of discrete Markov chains. I. Theory Probab. Math. Stat.86, 93–104 (2013). MR2986452. doi:10.1090/S0094-9000-2013-00891-6Kartashov, M., Golomoziy, V.: Maximal coupling procedure and stability of discrete Markov chains. II. Theory Probab. Math. Stat.87, 65–78 (2013). MR3241447. doi:10.1090/S0094-9000-2014-00905-9Lindvall, T.: Lectures on Coupling Method. John Wiley and Sons (1991). MR1180522Thorisson, H.: Coupling, Stationarity, and Regeneration. Springer, New York (2000). MR1741181. doi:10.1007/978-1-4612-1236-2