1 Introduction

This article is a continuation of the very recent work [10], where subgeometric rates of convergence are established for continuous-time Markov processes under subordination in the sense of Bochner, and it aims to derive the analogous result when the time parameter is discrete. Readers are urged to refer to [7, Chapter 5] and [18, Chapters 13 and 15] for some background on the topic of convergence rates of Markov processes. For recent developments on subgeometric ergodicity, see, e.g., [6, 11,12,13,14, 22].

First, we recall the notion of discrete-time subordinator, which is a discrete-time counterpart of the classical continuous-time subordinator (i.e., nondecreasing Lévy process on \([0,\infty )\)) and was initialed in [5]; see also [1,2,3, 19, 20] for further developments on random walks under discrete-time subordination. A function \(\phi :(0,\infty )\rightarrow [0,\infty )\) is a Bernstein function if \(\phi \) is a \(C^\infty \)-function satisfying \((-1)^{n-1}\phi ^{(n)}\ge 0\) for all \(n\in \mathbb {N}\) (here \(\phi ^{(n)}\) denotes the nth derivative of \(\phi \)). It is well known, see, e.g., [23, Theorem 3.2], that every Bernstein function has a unique Lévy–Khintchine representation

$$\begin{aligned} \phi (x) =a+bx+\int _{(0,\infty )}\left( 1-e^{-xy} \right) \,\nu (\mathrm {d}y), \quad x>0, \end{aligned}$$

where \(a\ge 0\) is the killing term, \(b\ge 0\) is the drift term and \(\nu \) is a Radon measure on \((0,\infty )\) such that \(\int _{(0,\infty )}(1\wedge y)\,\nu (\mathrm {d}y)<\infty \). As usual, we make the convention that \(\phi (0):=\phi (0+)=a\). For our purpose, we will assume that \(\phi \) has no killing term (i.e., \(a=0\)); that is, \(\phi \) is of the form

$$\begin{aligned} \phi (x)=bx+\int _{(0,\infty )}\left( 1-e^{-xy} \right) \,\nu (\mathrm {d}y),\quad x\ge 0, \end{aligned}$$
(1.1)

where b and \(\nu \) are as above. Without loss of generality, we also assume that \(\phi (1)=1\); otherwise, we replace \(\phi \) by \(\phi /\phi (1)\).

For \(m\in \mathbb {N}\), we set

$$\begin{aligned} c(\phi ,m)=\frac{1}{m!}\int _{(0,\infty )} y^me^{-y}\,\nu (\mathrm {d}y)+ {\left\{ \begin{array}{ll} b,&{} \quad \text {if }\;m=1,\\ 0,&{}\quad \text {if }\;m\ge 2. \end{array}\right. } \end{aligned}$$

Since

$$\begin{aligned} \sum _{m=1}^\infty c(\phi ,m)= & {} b+\sum _{m=1}^\infty \frac{1}{m!}\int _{(0,\infty )} y^me^{-y}\,\nu (\mathrm {d}y)\\= & {} b+\int _{(0,\infty )}\left( 1-e^{-y}\right) \,\nu (\mathrm {d}y) =\phi (1)=1, \end{aligned}$$

we know that \(\{c(\phi ,m):m\in \mathbb {N}\}\) gives rise to a probability measure on \(\mathbb {N}\), and hence, we can define a random walk \(T=\{T_n:n\in \mathbb {N}\}\) on \(\mathbb {N}\) by \(T_n:=\sum _{k=1}^nR_k\), where \(\{R_k:k\in \mathbb {N}\}\) is a sequence of independent and identically distributed random variables with \(\mathbb {P}(R_k=m)=c(\phi ,m)\) for \(k,m\in \mathbb {N}\). As a strictly increasing process, the random walk T is called a discrete-time subordinator associated with the Bernstein function \(\phi \). Obviously, \(T_n\ge n\), and for \(m,n\in \mathbb {N}\) with \(m\ge n\),

$$\begin{aligned} \mathbb {P}(T_n=m)=\sum _{m_1+\dots +m_n=m} \prod _{i=1}^nc(m_i,\phi ). \end{aligned}$$

Let \(X=\{X_n:n\in \mathbb {N}\}\) be a Markov chain on a general measurable state space E, and denote by \(P^n(x,\mathrm {d}y)\) the n-step transition kernel. Throughout this paper, we always assume that X and T are independent and that X has an invariant measure \(\Pi \):

$$\begin{aligned} \int _EP^n(x,\cdot )\,\Pi (\mathrm {d}x)=\Pi \quad \text {for all }n\in \mathbb {N}. \end{aligned}$$

The subordinate process is given by the random time change \(X_n^\phi :=X_{T_n}\). The process \(X^\phi =\{X_n^\phi :n\in \mathbb {N}\}\) is again a Markov chain, and it follows easily from the independence of X and T that the n-step transition kernel of \(X^\phi \) is

$$\begin{aligned} P^n_\phi (x,\mathrm {d}y)=\sum _{m=n}^\infty P^m(x,\mathrm {d}y) \mathbb {P}(T_n=m). \end{aligned}$$
(1.2)

This implies that \(\Pi \) is also invariant for the time-changed chain \(X^\phi \).

For a (measurable) control function \(f:E\rightarrow [1,\infty )\), the f-norm (cf. [18, Chapter 14]) of a signed measure \(\mu \) on E is defined as \(\Vert \mu \Vert _f:=\sup _{|g|\le f}|\mu (g)|\), where the supremum ranges over all measurable functions \(g:E\rightarrow \mathbb {R}\) with \(|g|\le f\), and \(\mu (g)=\int _Eg\,\mathrm {d}\mu \). If \(f\equiv 1\), then the f-norm \(\Vert \cdot \Vert _f\) reduces to the total variation norm \(\Vert \cdot \Vert _{{\text {TV}}}\); since \(f\ge 1\), we always have \(\Vert \cdot \Vert _f\ge \Vert \cdot \Vert _{{\text {TV}}}\); if furthermore f is bounded, then these two norms are equivalent.

It is said that the process X has subgeometric convergence in the f-norm if

$$\begin{aligned} \left\| P^n(x,\cdot )-\Pi \right\| _f\le C(x)r(n), \quad x\in E,\,n\in \mathbb {N}, \end{aligned}$$
(1.3)

where C(x) is a positive constant depending on \(x\in E\) and \(r:\mathbb {N}\rightarrow (0,1]\) is a nonincreasing function with \(r(n)\downarrow 0\) and \(\log r(n)/n \uparrow 0\) as \(n\rightarrow \infty \). Here, r is called the subgeometric rate. In many specific models, the convergence rate r can be explicitly given and typical examples contain

$$\begin{aligned} r(n)=e^{-\theta n^\delta },\quad r(n)=n^{-\beta },\quad r(n)=\log ^{-\gamma }(2+n), \end{aligned}$$
(1.4)

where \(\theta >0\), \(\delta \in (0,1)\) and \(\beta ,\gamma >0\) are some constants. Let \(\mathbb {Z}_+=\mathbb {N}\cup \{0\}\) and \(\{p_k:k\in \mathbb {Z}_+\}\) be a sequence such that \(p_0=1\), \(p_k\in (0,1)\) for all \(k\in \mathbb {N}\), and \(\lim _{k\rightarrow \infty }\prod _{i=1}^kp_i=0\). Consider the backward recurrence time chain (cf. [18, Section 3.3.1]) on the countable state space \(\mathbb {Z}_+\) with one-step transition kernel P given by \(P(k,k+1)=1-P(k,0)=p_k\) for all \(k\in \mathbb {Z}_+\). Then this chain admits the convergence rates in (1.4) under some assumptions, see [12, Section 3.1] for details.

In recent years, there has been an increasing interest in the stability of properties of continuous-time Markov processes and their semigroups under Bochner’s subordination. See [16] for the dimension-free Harnack inequality for subordinate semigroups, [8] for shift Harnack inequality for subordinate semigroups, [9] for the quasi-invariance property of Brownian motion under random time change, and [10] for subgeometric rates of convergence for continuous-time Markov processes under continuous-time subordination. Subordinate functional inequalities can be found in [4, 15, 24].

It is a natural question whether subgeometric rates of convergence can be preserved under discrete-time subordination. If \(P^n\) is subgeometrically convergent to \(\Pi \) in the f-norm, is it possible to derive quantitative bounds on the convergence rates of the subordinate Markov chain \(X^\phi \)? What we are going to do is to find some function \(r_\phi :\mathbb {N}\rightarrow (0,1]\) such that \(\lim _{n\rightarrow \infty }r_\phi (n)=0\) and

$$\begin{aligned} \left\| P^n_\phi (x,\cdot )-\Pi \right\| _f\le C(x)r_\phi (n), \quad x\in E,\,n\in \mathbb {N}\end{aligned}$$
(1.5)

for some constant \(C(x)>0\) depending only on \(x\in E\). As in [10], it turns out that if the convergence rates of the original chain X are of the three typical forms in (1.4), then we are able to obtain convergence rates for the subordinate Markov chain \(X^\phi \) under some reasonable assumptions on the underlying Bernstein function.

The main result of this note is the following. As usual, denote by \(\phi ^{-1}\) the inverse function of the (strictly increasing) Bernstein function \(\phi \).

Theorem 1.1

Let X be a discrete-time Markov chain and T an independent discrete-time subordinator associated with Bernstein function \(\phi \) given by (1.1) such that \(\phi (1)=1\).

(a):

Assume that (1.3) holds with rate \(r(n)=e^{-\theta n^\delta }\) for some constants \(\theta >0\) and \(\delta \in (0,1]\). If

$$\begin{aligned} \nu (\mathrm {d}y)\ge cy^{-1-\alpha }\,\mathrm {d}y \end{aligned}$$
(1.6)

for some constants \(c>0\) and \(\alpha \in (0,1)\), then (1.5) holds with rate

$$\begin{aligned} r_\phi (n)=\exp \left[ -C\,n^{ \frac{\delta }{\alpha (1-\delta )+\delta } } \right] , \end{aligned}$$

where \(C=C(\theta ,\delta ,c,\alpha )>0\).

(b):

Assume that (1.3) holds with rate \(r(n)=n^{-\beta }\) for some constant \(\beta >0\). If

$$\begin{aligned} \liminf _{x\rightarrow \infty }\frac{\phi (x)}{\log x}>0 \quad \text {and}\quad \limsup _{x\downarrow 0}\frac{\phi (\lambda x)}{\phi (x)}>1 \quad \text {for some }\lambda >1, \end{aligned}$$
(1.7)

then (1.5) holds with rate

$$\begin{aligned} r_\phi (n)=\left[ \phi ^{-1}\left( \frac{1}{n}\right) \right] ^\beta . \end{aligned}$$
(c):

Assume that (1.3) holds with rate \(r(n)=\log ^{-\gamma }(2+n)\) for some constant \(\gamma >0\). Then (1.5) holds with rate

$$\begin{aligned} r_\phi (n)=\log ^{-\gamma }(2+n). \end{aligned}$$

Remark 1.2

(a) According to [10, Lemma 2.2 (ii)], the second condition in (1.7) is equivalent to

$$\begin{aligned} \limsup _{x\downarrow 0}\frac{\phi (\lambda x)}{\phi (x)}>1 \quad \text {for all }\lambda >1. \end{aligned}$$

(b) Let \(b=0\) and \(\nu (\mathrm {d}y)=\frac{\alpha }{\Gamma (1-\alpha )}\,y^{-1-\alpha }\,\mathrm {d}y\) with \(\alpha \in (0,1)\). In this case, it is clear that (1.6) holds, and by the formula [23, p. vii]

$$\begin{aligned} x^\alpha =\frac{\alpha }{\Gamma (1-\alpha )} \int _0^\infty \left( 1-e^{-xy}\right) y^{-1-\alpha }\,\mathrm {d}y,\quad x>0,\alpha \in (0,1), \end{aligned}$$

we know that the corresponding Bernstein function (1.1) is given by the fractional power function \(\phi (x)=x^\alpha \). One can construct more examples for (1.6) by choosing \(\nu (\mathrm {d}y)=cy^{-1-\alpha }\,\mathrm {d}y +\tilde{\nu }(\mathrm {d}y)\), where \(c>0\), \(\alpha \in (0,1)\), and \(\tilde{\nu }\) is another Lévy measure on \((0,\infty )\) such that

$$\begin{aligned} \phi (1)=b+c\alpha ^{-1}\Gamma (1-\alpha ) +\int _{(0,\infty )} \left( 1-e^{-y}\right) \, \tilde{\nu }(\mathrm {d}y)=1. \end{aligned}$$

(c) As pointed out in [10, Remark 1.1], typical examples for Bernstein function \(\phi \) satisfying (1.7) are

  • \(\phi (x)=\log (1+x)/\log 2\);

  • \(\phi (x)=x^\alpha \log ^\beta (1+x)/\log ^\beta 2\) with \(\alpha \in (0,1)\) and \(\beta \in [0,1-\alpha )\);

  • \(\phi (x)=x^\alpha \log ^{-\beta }(1+x)/\log ^{-\beta }2\) with \(0<\beta<\alpha <1\);

  • \(\phi (x)=2^\alpha x(1+x)^{-\alpha }\) with \(\alpha \in (0,1)\).

See [23, Chapter 16] for more examples of such Bernstein functions.

The rest of this paper is organized as follows: Section 2 is devoted to three types of moment estimates for discrete-time subordinators, which will be crucial for the proof of Theorem 1.1; we stress that this part is of some interest on its own. In Sect. 3, we present the proof of Theorem 1.1. Finally, we give in “Appendix” an elementary inequality, which is used in Sect. 2.

2 Moment Estimates for Discrete-Time Subordinators

Recall that a continuous-time subordinator \(S=\{S_t:t\ge 0\}\) associated with Bernstein function \(\phi \) is a nondecreasing Lévy process taking values in \([0,\infty )\) and with Laplace transform

$$\begin{aligned} \mathbb {E}\,e^{-uS_t}=e^{-t\phi (u)},\quad u,t\ge 0. \end{aligned}$$

The following result concerning moment estimates for continuous-time subordinators is taken from [10, Theorem 2.1].

Lemma 2.1

Let S be a continuous-time subordinator associated with Bernstein function \(\phi \) given by (1.1).

(a):

Let \(\theta >0\) and \(\delta \in (0,1]\). If (1.6) holds for some constants \(c>0\) and \(\alpha \in (0,1)\), then there exists a constant \(C=C(\theta ,\delta ,c,\alpha )>0\) such that

$$\begin{aligned} \mathbb {E}\,e^{-\theta S_t^\delta } \le \exp \left[ -C\,t^{ \frac{\delta }{\alpha (1-\delta )+\delta } } \right] \quad \mathrm{for\,all\, sufficiently\,large }\,t>1. \end{aligned}$$
(b):

Let \(\beta >0\). If the Bernstein function \(\phi \) satisfies (1.7), then there exists a constant \(C=C(\beta )>0\) such that

$$\begin{aligned} \mathbb {E}S_t^{-\beta }\le C\left[ \phi ^{-1}\left( \frac{1}{t}\right) \right] ^\beta \quad \mathrm{for\,all\, sufficiently\,large }\,t>1. \end{aligned}$$

Analogous to Lemma 2.1, we shall establish the corresponding results for discrete-time subordinators. For related moment estimates for general Lévy(-type) processes, we refer to [8, 17].

Our main contribution in this section is the following result.

Theorem 2.2

Let T be a discrete-time subordinator associated with Bernstein function \(\phi \) given by (1.1) such that \(\phi (1)=1\).

(a):

Let \(\theta >0\) and \(\delta \in (0,1]\). If (1.6) holds for some constants \(c>0\) and \(\alpha \in (0,1)\), then there exists a constant \(C=C(\theta ,\delta ,c,\alpha )>0\) such that

$$\begin{aligned} \mathbb {E}\,e^{-\theta T_n^\delta } \le \exp \left[ -C\,n^{ \frac{\delta }{\alpha (1-\delta )+\delta } } \right] \quad \mathrm{for\,all\, sufficiently\,large }\,n\in \mathbb {N}. \end{aligned}$$
(b):

Let \(\beta >0\). If the Bernstein function \(\phi \) satisfies (1.7), then there exists a constant \(C=C(\beta )>0\) such that

$$\begin{aligned} \mathbb {E}T_n^{-\beta }\le C\left[ \phi ^{-1}\left( \frac{1}{n}\right) \right] ^\beta \quad \mathrm{for\,all }\,n\in \mathbb {N}. \end{aligned}$$

In order to prove Theorem 2.2, we first present a general result to bound the completely monotone moment of a discrete-time subordinator by that of a continuous-time subordinator.

A function \(g:(0,\infty )\rightarrow \mathbb {R}\) is called a completely monotone function if g is of class \(C^\infty \) and \((-1)^ng^{(n)}\ge 0\) for all \(n=0,1,2,\dots \), see [23, Chapter 1]. By the celebrated theorem of Bernstein (cf. [23, Theorem 1.4]), every completely monotone function is the Laplace transform of a unique measure on \([0,\infty )\). More precisely, if g is a completely monotone function, then there exists a unique measure \(\mu \) on \([0,\infty )\) such that

$$\begin{aligned} g(x)=\int _{[0,\infty )}e^{-xt}\,\mu (\mathrm {d}t) \quad \text {for all } x>0. \end{aligned}$$
(2.1)

Since the function \(x\mapsto x^\delta \) (\(\delta \in (0,1]\)) is a (complete) Bernstein function, it follows easily from [23, Theorem 3.7] that the following functions

$$\begin{aligned} x\mapsto e^{-\theta x^\delta },\quad x\mapsto x^{-\beta } \end{aligned}$$
(2.2)

are completely monotone functions, where \(\theta >0\), \(\delta \in (0,1]\), and \(\beta >0\). Indeed, one has for \(\theta >0\) and \(\delta \in (0,1)\) (see [21]),

$$\begin{aligned} e^{-\theta x^\delta }=\int _0^\infty e^{-xt}\psi (\theta ,\delta ,t)\,\mathrm {d}t, \quad x>0, \end{aligned}$$

where

$$\begin{aligned} \psi (\theta ,\delta ,t)=\pi ^{-1}\theta ^{-1/\delta } \int _0^\infty e^{-\theta ^{-1/\delta }tu} e^{-u^\delta \cos \pi \delta } \sin \left( u^\delta \sin \pi \delta \right) \,\mathrm {d}u; \end{aligned}$$

moreover, for \(\beta >0\),

$$\begin{aligned} x^{-\beta }= \frac{1}{\Gamma (\beta )}\int _0^\infty e^{-xt}t^{\beta -1}\,\mathrm {d}t,\quad x>0. \end{aligned}$$

Lemma 2.3

Let T be a discrete-time subordinator with Bernstein function \(\phi \) given by (1.1) such that \(\phi (1)=1\). Let S be a continuous-time subordinator with the same Bernstein function \(\phi \). If \(g:(0,\infty )\rightarrow \mathbb {R}\) is a completely monotone function, then

$$\begin{aligned} \mathbb {E}\,g(T_n)\le \mathbb {E}\,g(S_n)\quad \text {for all }n\in \mathbb {N}. \end{aligned}$$

Proof

By the representation formula (2.1) and Tonelli’s theorem,

$$\begin{aligned} \mathbb {E}\,g(T_n)&=\mathbb {E}\left[ \int _{[0,\infty )}e^{-T_nt}\,\mu (\mathrm {d}t) \right] \\&=\int _{[0,\infty )}\mathbb {E}\,e^{-T_nt}\,\mu (\mathrm {d}t)\\&=\int _{[0,\infty )}\prod _{k=1}^n\mathbb {E}\,e^{-tR_k}\, \mu (\mathrm {d}t)\\&=\int _{[0,\infty )}\left( \mathbb {E}\,e^{-tR_1}\right) ^n\, \mu (\mathrm {d}t). \end{aligned}$$

Note that for \(t\ge 0\),

$$\begin{aligned} \mathbb {E}\,e^{-tR_1}&=\sum _{m=1}^\infty e^{-tm}c(\phi ,m)\\&=b e^{-t}+\sum _{m=1}^\infty e^{-tm}\frac{1}{m!}\int _{(0,\infty )} y^me^{-y}\,\nu (\mathrm {d}y)\\&=b e^{-t}+\int _{(0,\infty )} \left( e^{y e^{-t}} -1\right) e^{-y}\,\nu (\mathrm {d}y)\\&=\left[ b+\int _{(0,\infty )} \left( 1-e^{-y}\right) \nu (\mathrm {d}y) \right] \\&\quad -\left[ b\left( 1-e^{-t}\right) +\int _{(0,\infty )} \left( 1-e^{-( 1-e^{-t})y}\right) \nu (\mathrm {d}y) \right] \\&=\phi (1)-\phi \left( 1-e^{-t}\right) \\&=1-\phi \left( 1-e^{-t}\right) , \end{aligned}$$

which does not exceed \(e^{-\phi (t)}\) according to Lemma 4.1 in “Appendix”. Then, we have for all \(n\in \mathbb {N}\),

$$\begin{aligned} \mathbb {E}\,g(T_n)&\le \int _{[0,\infty )} e^{-n\phi (t)}\,\mu (\mathrm {d}t)\\&=\int _{[0,\infty )} \mathbb {E}\,e^{-tS_n}\,\mu (\mathrm {d}t)\\&=\mathbb {E}\left[ \int _{[0,\infty )}e^{-tS_n}\,\mu (\mathrm {d}t) \right] \\&=\mathbb {E}\,g(S_n), \end{aligned}$$

which was to be proved. \(\square \)

Proof of Theorem 2.2

Since the functions given in (2.2) are completely monotone functions, we only need to combine Lemma 2.3 with Lemma 2.1 to get the desired estimates.    \(\square \)

Since \(T_n\ge n\), the following lemma is clear.

Lemma 2.4

Let T be a discrete-time subordinator associated with Bernstein function \(\phi \) given by (1.1) such that \(\phi (1)=1\). For any \(\gamma >0\) and \(n\in \mathbb {N}\),

$$\begin{aligned} \mathbb {E}\log ^{-\gamma }(2+T_n)\le \log ^{-\gamma }(2+n). \end{aligned}$$

3 Proof of Theorem 1.1

Lemma 3.1

If (1.3) holds with some rate r(n), then so does (1.5) with rate \(r_\phi (n)=\mathbb {E}\,r(T_n)\).

Proof

It holds from (1.2) and (1.3) that

$$\begin{aligned} \left\| P^n_\phi (x,\cdot )-\Pi \right\| _f&=\left\| \sum _{m=n}^\infty \left[ P^m(x,\cdot )-\Pi \right] \mathbb {P}(T_n=m)\right\| _f\\&\le \sum _{m=n}^\infty \left\| P^m(x,\cdot )-\Pi \right\| _f \mathbb {P}(T_n=m)\\&\le C(x)\sum _{m=n}^\infty r(m)\mathbb {P}(T_n=m)\\&=C(x)\mathbb {E}\,r(T_n), \end{aligned}$$

and hence the claim follows.\(\square \)

Proof of Theorem 1.1

The assertion follows immediately by combining Lemma 3.1 with the moment estimates for discrete-time subordinators derived in Theorem 2.2 and Lemma 2.4.\(\square \)