Abstract
In this paper, we are concerned with the subgeometric rate of convergence of a Markov chain with discrete-time parameter to its invariant measure in the f-norm. We clarify how three typical subgeometric rates of convergence are inherited under a discrete-time version of Bochner’s subordination. The crucial point is to establish the corresponding moment estimates for discrete-time subordinators under some reasonable conditions on the underlying Bernstein function.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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
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
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
Since
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\),
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 \):
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
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
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
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
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
(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]
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
(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
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
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
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]),
where
moreover, for \(\beta >0\),
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
Proof
By the representation formula (2.1) and Tonelli’s theorem,
Note that for \(t\ge 0\),
which does not exceed \(e^{-\phi (t)}\) according to Lemma 4.1 in “Appendix”. Then, we have for all \(n\in \mathbb {N}\),
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}\),
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
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 \)
References
Bendikov, A., Cygan, W.: Alpha-stable random walk has massive thorns. Colloq. Math. 138, 105–129 (2015)
Bendikov, A., Cygan, W.: On massive sets for subordinated random walks. Math. Nachr. 288, 841–853 (2015)
Bendikov, A., Cygan, W., Trojan, B.: Limit theorems for random walks. Stoch. Proc. Appl. 127, 3268–3290 (2017)
Bendikov, A., Maheux, P.: Nash-type inequalities for fractional powers of non-negative self-adjoint operators. Trans. Am. Math. Soc. 359, 3085–3097 (2007)
Bendikov, A., Saloff-Coste, L.: Random walks on groups and discrete subordination. Math. Nachr. 285, 580–605 (2012)
Butkovsky, O.: Subgeometric rates of convergence of Markov processes in the Wasserstein metric. Ann. Appl. Probab. 24, 526–552 (2014)
Chen, M.-F.: Eigenvalues. Inequalities and Ergodicity. Springer, Singapore (2005)
Deng, C.-S., Schilling, R.L.: On shift Harnack inequalities for subordinate semigroups and moment estimates for Lévy processes. Stoch. Proc. Appl. 125, 3851–3878 (2015)
Deng, C.-S., Schilling, R.L.: On a Cameron–Martin type quasi-invariance theorem and applications to subordinate Brownian motion. Stoch. Anal. Appl. 33, 975–993 (2015)
Deng, C.-S., Schilling, R.L., Song, Y.-H.: Subgeometric rates of convergence for Markov processes under subordination. Adv. Appl. Probab. 49, 162–181 (2017)
Douc, R., Fort, G., Guillin, A.: Subgeometric rates of convergence of \(f\)-ergodic strong Markov processes. Stoch. Proc. Appl. 119, 897–923 (2009)
Douc, R., Fort, G., Moulines, E., Soulier, P.: Practical drift conditions for subgeometric rates of convergence. Ann. Appl. Probab. 14, 1353–1377 (2004)
Douc, R., Moulines, E., Soulier, P.: Computable convergence rates for sub-geometric ergodic Markov chains. Bernoulli 13, 831–848 (2007)
Fort, G., Roberts, G.O.: Subgeometric ergodicity of strong Markov processes. Ann. Appl. Probab. 15, 1565–1589 (2005)
Gentil, I., Maheux, P.: Super-Poincaré and Nash-type inequalities for subordinated semigroups. Semigroup Forum 90, 660–693 (2015)
Gordina, M., Röckner, M., Wang, F.-Y.: Dimension-independent Harnack inequalities for subordinated semigroups. Potential Anal. 34, 293–307 (2011)
Kühn, F.: Existence and estimates of moments for Lévy-type processes. Stoch. Proc. Appl. 127, 1018–1041 (2017)
Meyn, S.P., Tweedie, R.L.: Markov Chains and Stochastic Stability, 2nd edn. Cambridge University Press, Cambridge (2009)
Mimica, A.: On subordinate random walks. Forum Math. 29, 653–664 (2017)
Mimica, A., Šebek, S.: Harnack inequality for subordinate random walks. J. Theor. Probab. (2018). https://doi.org/10.1007/s10959-018-0821-5
Pollard, H.: The representation of \(\text{ e }^{-x^\lambda }\) as a Laplace integral. Bull. Am. Math. Soc. 52, 908–910 (1946)
Röckner, M., Wang, F.-Y.: Weak Poincaré inequalities and \(L^2\)-convengence rates of Markov semigroups. J. Funct. Anal. 185, 564–603 (2001)
Schilling, R. L., Song, R., Vondraček, Z.: Bernstein Functions. Theory and Applications. Studies in Mathematics, vol. 37, 2nd edn. De Gruyter, Berlin (2012)
Schilling, R.L., Wang, J.: Functional inequalities and subordination: stability of Nash and Poincaré inequalities. Math. Z. 272, 921–936 (2012)
Acknowledgements
The author would like to thank an anonymous referee for careful reading and useful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Financial support through the National Natural Science Foundation of China (11401442, 11831015) is gratefully acknowledged.
Appendix
Appendix
If \(\phi :[0,\infty )\rightarrow [0,\infty )\) is a concave function, then it is easy to see that
Lemma 4.1
Let \(\phi :[0,\infty )\rightarrow [0,\infty )\) be a concave function such that \(\phi (1)=1\) and \(\phi \) is differentiable on (0, 1) with \(\phi '|_{(0,1)}\ge 0\). Then
In particular, the above inequality holds if \(\phi \) is a Bernstein function (not necessarily with \(\phi (0)=0\)).
Proof
Let
It follows from (4.1) that for \(x\ge 1\),
whence
Now we obtain from (4.1) and (4.2) that for \(x\ge 1\),
It remains to consider the case that \(x\in [0,1)\). Since \(\phi \) is concave and differentiable on (0, 1), we know that \(\phi '\) is nonincreasing on (0, 1). For \(x\in (0,1)\), by the elementary inequality that \(1-e^{-x}<x\), we obtain
Moreover, by (4.1) one has for \(x\in (0,1)\),
which yields that
Combining this with (4.3), we find for \(x\in (0,1)\),
This implies that \(\Phi \) is nondecreasing on (0, 1) and thus for all \(x\in [0,1)\),
which completes the proof. \(\square \)
Rights and permissions
About this article
Cite this article
Deng, CS. Subgeometric Rates of Convergence for Discrete-Time Markov Chains Under Discrete-Time Subordination. J Theor Probab 33, 522–532 (2020). https://doi.org/10.1007/s10959-019-00879-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10959-019-00879-z