Rates of memory loss for null recurrent Markov chains Ilya Chevyrev, Alexey Korepanov Abstract Orey (1962) proved that for an irreducible, aperiodic, and recurrent Markov chain with transition operator P P , the sequence P n ​ ( μ − ν ) P^{n}(\mu-\nu) converges to zero in total variation for any two probability measures μ \mu and ν \nu . In other words, all such Markov chains exhibit memory loss . While the rates of memory loss have been extensively studied for positive recurrent chains, there is a surprising lack of results for null recurrent chains. In this work, we prove the first estimates of memory loss rates in the null recurrent case. 1 Introduction Consider a Markov chain X_{0},X_{1},\ldots taking values in a measurable space \Omega with transition operator P\colon{\mathcal{P}}(\Omega)\to{\mathcal{P}}(\Omega) , where {\mathcal{P}}(\Omega) is the space of probability measures on \Omega . That is, if X_{n}\sim\mu with \mu\in{\mathcal{P}}(\Omega) , then X_{n+1}\sim P\mu . A question of fundamental interest is whether the chain is mixing , and if so, what is the mixing rate . A well studied notion of mixing is memory loss: the convergence \|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}}\to 0 as n\to\infty for \mu,\nu\in{\mathcal{P}}(\Omega) that act as initial distributions for X , where \|\cdot\|_{\mathrm{TV}} is the total variation norm. A celebrated result of Orey [ Ore59 , Ore62 ] (see also [ JO67 , Ore71 ] ) states that if X is recurrent, irreducible and aperiodic, then \lim_{n\to\infty}\|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}}=0 for all \mu,\nu\in{\mathcal{P}}(\Omega) . This result is remarkable in its scope, but of course, at this level of generality, comes with no rate of convergence. In the case that X is positive recurrent , and thus admits an invariant probability measure, there are well-known results that quantify memory loss, e.g. for so-called regular measures, one has \sum_{n=1}^{\infty}\|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}}<\infty , so in particular \|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}}\lesssim n^{-1} , see [ Num84 , Theorem 6.11] . There is an abundance of criteria for polynomial and geometric rates of convergence, e.g. based on estimates of first return times to nice sets, or the existence of Lyapunov functions, see [ NT78 , NT82 , NT83 ] for early works as well as the books [ Lin02 , Num84 , BH22 , MT09 ] and the references therein. For results in the case of subgeometric mixing rates, see for example [ TT94 , Ver97 , JR02 , DFMS04 , Bax05 , Hai21 , CnM23 ] and the book [ DMPS18 ] . To our knowledge, all of these conditions are restricted to the positive recurrent case. The purpose of this paper is to provide the first rates in convergence \|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}}\to 0 for null recurrent Markov chains. We present three results which use different strategies and work under different assumptions, and which are applicable to general Harris chains. To illustrate the results, consider an aperiodic and recurrent Markov chain X_{n} on \Omega=\{0,1,2,\ldots\} with connection graph \displaystyle\resizebox{}{}{{\hbox{\hskip 0.0pt\raise-10.00002pt\hbox{{ \hbox to232.36pt{\vbox to57.85pt{\pgfpicture\makeatletter\hbox{\hskip 22.35716pt\lower-47.64499pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 13.84 0 C 13.84 7.64 7.64 13.84 0 13.84 C -7.64 13.84 -13.84 7.64 -13.84 0 C -13.84 -7.64 -7.64 -13.84 0 -13.84 C 7.64 -13.84 13.84 -7.64 13.84 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -3.46 -4.46)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} {{{{}}}}{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 83.02 0 C 83.02 7.64 76.83 13.84 69.19 13.84 C 61.54 13.84 55.35 7.64 55.35 0 C 55.35 -7.64 61.54 -13.84 69.19 -13.84 C 76.83 -13.84 83.02 -7.64 83.02 0 Z M 69.19 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{47.50008pt}{-3.22221pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 65.73 -4.46)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} {{{{}}}}{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 152.21 0 C 152.21 7.64 146.01 13.84 138.37 13.84 C 130.73 13.84 124.53 7.64 124.53 0 C 124.53 -7.64 130.73 -13.84 138.37 -13.84 C 146.01 -13.84 152.21 -7.64 152.21 0 Z M 138.37 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{97.50015pt}{-3.22221pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 134.91 -4.46)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} {{{{}}}}{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 221.39 0 C 221.39 7.64 215.2 13.84 207.56 13.84 C 199.91 13.84 193.72 7.64 193.72 0 C 193.72 -7.64 199.91 -13.84 207.56 -13.84 C 215.2 -13.84 221.39 -7.64 221.39 0 Z M 207.56 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{147.50023pt}{-3.22221pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 204.1 -4.46)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} {{{{}}}}{{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{196.2503pt}{-2.5pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 271.55 -3.46)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} {{}}{}{{}}{}{{}}{}{ {}{}{}}{}{{}}{}{{}}{}{{}}{}{{}}{}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.8pt} \lx@inpgf@ignorespaces\lx@inpgf@ignorespaces\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}{{ {\lxSVG@setdash{0.0pt}\lx@inpgf@ignorespaces\lxSVG@roundjoin\lx@inpgf@ignorespaces{} {}{}{} {}{}{} {}{}{} \lxSVG@fillstroke}} }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 53.08 0 L 14.11 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{38.36009pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 53.08 0)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 122.26 0 L 83.3 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{88.36017pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 122.26 0)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 191.45 0 L 152.48 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{138.36024pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 191.45 0)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} { {}{}{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{ {}{}}{}{}{{}{}}}}}{{}}{}{}{}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 260.63 0 L 221.67 0}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{188.36032pt}{0.0pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 260.63 0)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{} {\lx@inpgf@ignorespaces{}{}{{}}{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{}{}\lx@inpgf@ignorespaces}{{}} {\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M -13.95 -8.05 C -30.38 -17.54 0 -35.08 0 -14.11}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{0.86603}{0.5}{-0.5}{0.86603}{-10.08054pt}{-5.81999pt}\lxSVG@begingroup@{transform=matrix(0.86603 0.5 -0.5 0.86603 -13.95 -8.05)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-13.99261pt}{-24.2126pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -19.36 -33.5)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{} {\lx@inpgf@ignorespaces{}{}{{}}{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{}{}\lx@inpgf@ignorespaces}{{}} {\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 15.32 -4.98 C 29.42 -9.56 41.15 -13.07 56.39 -5.96}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{-0.95107}{0.30902}{-0.30902}{-0.95107}{11.07037pt}{-3.59698pt}\lxSVG@begingroup@{transform=matrix(-0.95107 0.30902 -0.30902 -0.95107 15.32 -4.98)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{34.46663pt}{-13.0632pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 47.69 -18.08)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{} {\lx@inpgf@ignorespaces{}{}{{}}{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{}{}\lx@inpgf@ignorespaces}{{}} {\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 13.03 -9.47 C 47.82 -34.75 89.95 -33.91 126.81 -8.1}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{-0.80902}{0.58778}{-0.58778}{-0.80902}{9.41698pt}{-6.84178pt}\lxSVG@begingroup@{transform=matrix(-0.80902 0.58778 -0.58778 -0.80902 13.03 -9.47)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{82.96655pt}{-17.59355pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 114.8 -24.34)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope }}}\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}}{} {\lx@inpgf@ignorespaces{}{}{{}}{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{}{}\lx@inpgf@ignorespaces}{{}} {\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{\lx@inpgf@ignorespaces{}{}{{}}{}}{{{}}{{}}}{{}}{}{{}}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{{{{{{}}{}{}{}{}{{}}}}}{}{}{}{}}{}{}{}{}{{}}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 9.47 -13.03 C 47.5 -65.37 150.42 -57.14 197.58 -9.98}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{-0.58778}{0.80902}{-0.80902}{-0.58778}{6.84178pt}{-9.41698pt}\lxSVG@begingroup@{transform=matrix(-0.58778 0.80902 -0.80902 -0.58778 9.47 -13.03)} \lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke-dasharray=none,stroke-dashoffset=0.0pt} \lxSVG@begingroup@{stroke-linejoin=round} \lxSVG@drawpath@unclipped{M 1.44 0 C -0.36 0.36 -2.16 1.08 -4.32 2.34 C -2.16 0.72 -2.16 -0.72 -4.32 -2.34 C -2.16 -1.08 -0.36 -0.36 1.44 0 Z}{} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{132.7292pt}{-21.19235pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 183.66 -29.32)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}} }}}}} (1.1) and transition probabilities \P(X_{1}=0\mid X_{0}=n)=q_{n} , \P(X_{1}=n+1\mid X_{0}=n)=1-q_{n} . Consider initial distributions \mu=\delta_{0} and \nu=P^{\ell}\delta_{0} , where \delta_{n} gives probability 1 to the state \mathrm{n} . Remark 1.1 . The Markov chain ( 1.1 ) and our choice of initial distributions are far more than a convenient illustration. As we show in Section 3 , estimates on \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} for ( 1.1 ) lead directly to memory loss rates for Markov chains on a general state space with relaxed recurrence properties, specifically for Harris chains. For n\geq 1 let \displaystyle p_{n}=\P(\inf\{k\geq 1\,:\,X_{k}=0\}=n\mid X_{0}=0)=(1-q_{0})\cdots(1-q_{n-2})q_{n-1}\;. Suppose that \sum_{k>n}p_{k}\leq Cn^{-\alpha} with some C,\alpha>0 . If \alpha>1 , then X_{n} is positive recurrent, and it is generally null recurrent otherwise. A standard result (see Appendix A ) for positive recurrent Markov chain is that for \alpha>1 , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\frac{\ell}{n^{\alpha}}\;, (1.2) where \lesssim means a bound up to a multiplicative constant that does not depend on n or \ell . In general, this bound is sharp for \ell\leq n , e.g. when \sum_{k>n}p_{k}=(n+1)^{-\alpha} , see Corollary 2.4 . In the null recurrent case \alpha\leq 1 , we are not aware of any prior results which give a convergence rate. Our main results in this situation can be summarised as follows. (a) If \alpha\in(0,3/2) , then \displaystyle\|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\frac{\ell^{2/3}}{n^{\alpha/3}} for \ell sufficiently small, for example for \ell\leq n^{3/2-\alpha}(\log(1+n))^{-3/2} . See Theorem 2.6 . (b) If p_{n} satisfies the decreasing failure rate (DFR), i.e. the sequence p_{n}/(p_{n}+p_{n+1}+\cdots) is non-increasing, then \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} is given by an explicit expression, regardless of the assumption on the tails \sum_{k>n}p_{k} . In particular, \|P^{n+1}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}=2\sum_{k>n+1}p_{k} . See Theorem 2.8 and Lemma 2.9 . (c) Assume a corresponding lower bound \sum_{k>n}p_{k}\geq C^{-1}n^{-\alpha} . Then, for \alpha\in(1/2,1) , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\frac{\ell^{2\alpha-1}}{n^{2\alpha-1}}\;. Assume furthermore an upper bound on increments \sum_{k>n}|p_{k}-p_{k+1}|\lesssim n^{-\alpha-1} . Then, for \alpha\in(0,1) , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\frac{\ell^{\alpha}}{n^{\alpha}}\;. (1.3) See Theorem 2.10 . Remark 1.2 . If n\mapsto\sum_{k>n}p_{k} is regularly varying, then ( 1.3 ) is sharp in the sense that \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\gtrsim\ell^{\alpha}n^{-\alpha} , see Corollary 2.4 . Furthermore, in this case, the obvious upper bound \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim 1 is sharp for \ell>n . Remark 1.3 . The bound ( 1.2 ) for \alpha>1 follows from the case \ell=1 and the triangle inequality. This is not the case for the results in (a) - (c) . Remark 1.4 . As mentioned in Remark 1.1 , bounds on \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} translate directly to memory loss rates for general Harris chains. As a simple example, consider a Markov chain X on a measurable space \Omega with a recurrent point x\in\Omega . Define \tau=\inf\{k\geq 1\,:\,X_{k}=x\} and p_{k}=\P(\tau=k\mid X_{0}=x) . Suppose that \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\ell^{\beta}n^{-\alpha} for some \beta\geq\alpha\geq 0 uniformly in \ell,n\geq 1 , where P is the transition operator for the Markov chain ( 1.1 ) built with these p_{k} . For \mu\neq\nu\in{\mathcal{P}}(\Omega) , define \|\mu-\nu\|_{\beta}=\E_{X_{0}\sim\lambda}\tau^{\beta} where \lambda=|\mu-\nu|(\Omega)^{-1}|\mu-\nu|\in{\mathcal{P}}(\Omega) . Then \|Q^{n}\mu-Q^{n}\nu\|_{\mathrm{TV}}\lesssim n^{-\alpha}\|\mu-\nu\|_{\beta} where Q is the transition operator of X . See Proposition 3.8 for details. Our proofs of (a) - (c) are self-contained and independent of each other. Moreover, the proofs are elementary yet at times delicate, using only basic facts about regularly varying functions, Hoeffding’s inequality, etc. We make the following additional remarks. (a) is based on the famous and elegant coupling of Ornstein [ Orn69a , Orn69b ] , where memory loss is drawn from the times when a symmetric random walk on {\mathbb{Z}} reaches 0 . The proof is short, the assumptions are very general, yet the rate is weaker than in (b) or (c) , and than in ( 1.2 ) for \alpha>1 . (b) has an even shorter, essentially algebraic proof, although the assumption is very restrictive. The decreasing failure rate is used to verify that the renewal sequence u_{n}=\P(X_{n}=0\mid X_{0}=0) is monotone, which in turn allows completely bypassing otherwise substantial difficulties. Such monotonicity conditions were considered in [ Isa88 , HF91 ] . We highlight, however, that we give a simple and possibly new proof of the fact that a decreasing failure rate implies monotonicity of u_{n} (see Lemma 2.9 ). (c) is, we believe, the main contribution of this paper. The rate ( 1.3 ) is sharp (see Remark 1.2 ) while the assumptions are still practical to verify. Our proof of (c) is the longest part of the paper and is based on analysing the renewal sequence u_{n} using Tauberian arguments, inspired by but not relying on [ GL63 ] . Some key differences are that we bound the increments |u_{n}-u_{n+\ell}| rather than u_{n} itself, and that we require only upper/lower bounds on the tails \sum_{k>n}p_{k} instead of assuming that the tails are regularly varying. (Regular variation of \sum_{k>n}p_{k} is a standard assumption in renewal theory with infinite mean, see e.g. [ GL63 , Teu68 , Eri70 , Fre82 , Don97 , CD19 , Ber19 ] , and we are not aware of any results that do not use this assumption.) See Remark 2.11 for possible generalisations of (c) . We conclude the introduction by outlining the motivation for our study. Mixing rates are a fundamental property of Markov chains, as evidenced by the body of results in the positive recurrent case, thus we believe our findings carry intrinsic interest. Our motivation originates in smooth ergodic theory, where so-called non-uniformly expanding and non-uniformly hyperbolic dynamical systems have an intimate relation to Markov chains similar to ( 1.1 ). Various statistical properties have been proved by representing these systems as Young towers , topological Markov chains with some nice structure [ You98 , You99 ] . Further, connections with renewal-type Markov chains have been established via Lipschitz continuous and measure preserving semi-conjugacies [ Kor18 , CDKM24 ] . The landscape is much like in the probabilistic literature. Memory loss is known to occur in very general conditions [ Lin71 ] , see [ Aar97 , Theorem 1.3.3] . In the positive recurrent case, sharp rates of memory loss have been obtained using coupling [ You98 , You99 , KL21 ] (c.f. [ Pit74 , Lin79 ] ) and renewal theory [ Sar02 , Gou04 ] . In the null recurrent case, renewal sequences have been accurately estimated [ MT12 , Ter16 ] . However, no results currently address rates of memory loss in the null recurrent case. Extension of our results to ergodic theory will be a subject of a future study. In particular, the ‘practical’ assumptions in (c) have been chosen with such applications in mind. Organization of the paper In Section 2 we state our main results for the Markov chain ( 1.1 ). In Section 3 we relate memory loss rates of ( 1.1 ) to those of Markov chains with a recurrent atom and, more generally, Harris chains. In Sections 4 - 6 we prove the results from Section 2 , and in Appendix A we justify ( 1.2 ). 2 Model chain In this section we work with Markov chain X_{n} from ( 1.1 ) and initial measures \delta_{0} and P^{\ell}\delta_{0} with some \ell\geq 1 . Informally, we are trying to understand how quickly the Markov chain ( 1.1 ) forgets a time shift. 2.1 Notation and preliminaries Recall that we suppose that X_{n} is aperiodic and recurrent. That is, \sum_{n\geq 1}p_{n}=1 and there exist c_{\#}>0 and N_{\#}\geq 1 so that \gcd\{1\leq k\leq N_{\#}\,:\,p_{k}\geq c_{\#}\}=1\;. (2.1) If \sum_{n\geq 1}np_{n}<\infty , then X_{n} is positive recurrent, and X_{n} is null recurrent otherwise. Let u_{n} , n\geq 0 , denote the renewal probabilities u_{n}=\P(X_{n}=0\mid X_{0}=0)\;. Equivalently, we can define u_{n} by u_{0}=1 and the renewal equation u_{n}=\sum_{k=1}^{n}p_{k}u_{n-k}\;,\quad n\geq 1\;. (2.2) For n\geq 0 let z_{n}=\sum_{k>n}p_{k}\;. Remark 2.1 . It is a direct verification that z_{n}=z_{n-1}(1-q_{n-1})=(1-q_{0})\cdots(1-q_{n-1}) for n\geq 1 . In particular z_{n}q_{n}=p_{n+1} for n\geq 0 and \sum_{n\geq 0}z_{n}q_{n}=1=z_{0} . That is, z_{n} are the weights of the unique (up to scaling) stationary measure on \Omega . Our notation allows a convenient expression P^{n}\delta_{0}=\sum_{m=0}^{n}u_{n-m}z_{m}\delta_{m}\;. Subsequently, P^{n+\ell}\delta_{0}-P^{n}\delta_{0}=\sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}\delta_{m}+\sum_{m=0}^{n}(u_{n+\ell-m}-u_{n-m})z_{m}\delta_{m}\;. (2.3) The problem of bounding \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} is therefore closely tied to the asymptotics of the increments of the renewal sequence u_{n} . We use X\lesssim Y to denote X\leq CY for a constant C>0 that does not depend on X,Y . We write X\asymp Y if X\lesssim Y and Y\lesssim X . We also write Y\gg X whenever Y\geq CX for some C sufficiently large. For x\in{\mathbb{R}} , we let \lfloor x\rfloor\in{\mathbb{Z}} denote the floor of x . For probability measures \mu,\nu on a general measurable space (\Omega,\Sigma) , recall the identity \|\mu-\nu\|_{\mathrm{TV}}=2\sup_{A\in\Sigma}|\mu(A)-\nu(A)|\;. (2.4) 2.1.1 Regularly varying functions Recall that a function \rho\colon[a,\infty)\to(0,\infty) is called regularly varying (RV) with index \alpha\in{\mathbb{R}} if \lim_{x\to\infty}\rho(\lambda x)/\rho(x)=\lambda^{\alpha} for all \lambda>0 . A RV function with index 0 is called slowly varying. For more details on RV functions, we refer to [ BGT89 ] . We will use the following basic facts without explicit mention. Suppose \rho is RV with index \alpha . • One has \rho(x)=x^{\alpha}L(x) where L is slowly varying. • For any compact I\subset(0,\infty) , the limit \lim_{x\to\infty}\rho(\lambda x)/\rho(x)=\lambda^{\alpha} is uniform over \lambda\in I . In particular, for x,y sufficiently large, \rho(x)\asymp\rho(y) whenever x\asymp y . • Karamata’s theorem [ BGT89 , Section 1.5.6] . Suppose \rho is locally bounded. If \alpha>-1 , then \lim_{x\to\infty}x\rho(x)/\int_{a}^{x}\rho(y)\,dy=\alpha+1 . If \alpha<-1 , then \lim_{x\to\infty}x\rho(x)/\int_{x}^{\infty}\rho(y)\,dy=-\alpha-1 . If \alpha=-1 , then \int_{a}^{x}\rho(y)\,dy is slowly varying. We will often use these facts in the following form: if \alpha>-1 , then \int_{a}^{x}\rho(y)\,dy\asymp x\rho(x) and \int_{0}^{\delta}\rho(x^{-1})^{-1}\,dx\asymp\delta\rho(1/\delta) uniformly in x sufficiently large and \delta sufficiently small. Likewise, if \alpha<-1 , then \int_{x}^{\infty}\rho(y)\,dy\asymp x\rho(x) and \int_{\delta}^{1/a}\rho(x^{-1})^{-1}\,dx\asymp\delta\rho(1/\delta) . If \rho is defined on \{k,k+1,\ldots\} , we say that \rho is RV if x\mapsto\rho(\lfloor x\rfloor) is RV. 2.2 Lower bounds We begin with an easy lower bound on the memory loss for the Markov chain ( 1.1 ). Lemma 2.2 . For all n,\ell\geq 0 \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\geq 2\sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}\;. (2.5) Proof. The result follows from ( 2.3 ) and ( 2.4 ) by taking A=\{n+1,\ldots,n+\ell\} in the latter. ∎ Corollary 2.3 . \|P^{n+1}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\geq 2z_{n+1} . Corollary 2.4 . Suppose n\mapsto z_{n} is RV with index -\alpha . If \alpha>1 , then for n\geq 0 and \ell\geq 1 , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\gtrsim\sum_{m=n+1}^{n+\ell}z_{n}\;. (2.6) so in particular, \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\gtrsim\ell z_{n} for \ell\leq n . If \alpha\in(0,1) , then for n\geq 0 and \ell\geq 1 , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\gtrsim 1\wedge\frac{z_{n}}{z_{\ell}}\;. If \alpha=1 , then for \ell\leq n , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\gtrsim z_{n}\sum_{k=1}^{\ell-1}m(k)^{-1}\;,\qquad\text{where}\qquad m(n)=\sum_{k=0}^{n-1}z_{k}\;. Proof. If \alpha>1 then u_{n}\gtrsim 1 for sufficiently large n . Hence ( 2.6 ) follows from ( 2.5 ) and \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\gtrsim\ell z_{n} for \ell\leq n follows since z is RV. Suppose \alpha\in(0,1) . Then by [ GL63 , Theorem 1.1] , \liminf_{n\to\infty}nz_{n}u_{n}>0 . Let r>0 such that u_{n}\gtrsim n^{-1}z_{n}^{-1} for all n\geq r . It suffices to consider rn , \displaystyle\|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} \displaystyle\geq\sum_{m=n+1}^{n+\ell-r}u_{n+\ell-m}z_{m}\gtrsim 1\;, where we used u_{n+\ell-m}\gtrsim\ell^{-1}z_{\ell}^{-1} and z_{m}\gtrsim z_{\ell} . Suppose \alpha=1 . By [ Eri70 , Theorem 1] , \lim_{n\to\infty}m(n)u_{n}=1 . Then there is r>0 so that u_{n}\geq\frac{1}{2}m(n)^{-1} for all n\geq r and, repeating the calculation for \alpha\in(0,1) , for r<\ell\leq n , \displaystyle\|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} \displaystyle\gtrsim z_{n}\sum_{k=0}^{\ell-1}u_{k}\gtrsim z_{n}\sum_{k=r}^{\ell-1}m(k)^{-1}\;.\qed Remark 2.5 . Suppose that \sum_{k>n}p_{k}\lesssim n^{-\alpha} with \alpha>0 . For \alpha>1 (when X_{n} is positive recurrent), \|P^{n+1}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim n^{-\alpha} by ( 1.2 ). By Corollary 2.4 , this is sharp. A question of special interest and the initial motivation for this work was to investigate whether the bound \|P^{n+1}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim n^{-\alpha} can be extended to \alpha\leq 1 . 2.3 Upper bounds Under very relaxed assumptions, using only an upper bound on the tails \sum_{k>n}p_{k} , we obtain: Theorem 2.6 . Suppose that \sum_{k>n}p_{k}\leq\rho(n) , where \rho is RV with index -\alpha\in(-3/2,0) . Then \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\ell^{2/3}\rho(n)^{1/3} (2.7) uniformly in n\geq 1 and \ell\geq 1 restricted by: • \ell\leq\rho(n)n^{3/2}M(n)^{-3/2} with M(n)=1+\int_{1}^{n}\rho(t)\,dt if \alpha=1 , • \ell\leq\rho(n)n^{3/2} if \alpha\in(1,\frac{3}{2}) . In all cases, the proportionality constant depends only on the constants in ( 2.1 ) and on \rho . We prove Theorem 2.6 in Section 4 . The proof is based on quantifying an elegant coupling of Ornstein [ Orn69a , Orn69b ] . Remark 2.7 . For \rho(n)=Cn^{-\alpha} with \alpha>1 , the upper bound ( 2.7 ) is significantly weaker than ( 1.2 ) that works under the same assumptions, and this is an inherent limitation of the proof. Moreover, for \alpha\leq 1 , the upper bound ( 2.7 ) is far from the lower bound ( 2.5 ). However, this is the only rate we obtain that works under the minimal assumption \sum_{k>n}p_{k}\leq\rho(n) . It remains an open question if ( 2.7 ) can be improved without making extra assumptions. Under a very restrictive assumption we show that the lower the bound ( 2.5 ) is precise: Theorem 2.8 . Assume that u_{n} is non-increasing with n . Then \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}=2\sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}\;. We prove Theorem 2.8 in Section 5 . The following lemma provides a simple way to verify the monotonicity condition of Theorem 2.8 . Lemma 2.9 . Assume decreasing failure rate (DFR), i.e. that the sequence p_{n}/(p_{n}+p_{n+1}+\cdots) is non-increasing with n . Then u_{n} is non-increasing in n . Proof. The lemma appears in [ HF91 ] but we provide a different, simple proof in Section 5.1 . ∎ Finally, we show that the optimal rates are achievable for null recurrent chains under practical assumptions: Theorem 2.10 . Suppose that c\rho(n)\leq z_{n}\leq\rho(n) (2.8) for all n\geq 1 , where c\in(0,1] and \rho is regularly varying with index -\alpha\in(-1,0) . If \alpha\in(\frac{1}{2},1) , then uniformly in n\geq\ell\geq 1 , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\frac{n\rho(n)^{2}}{\ell\rho(\ell)^{2}}\;. (2.9) If \alpha\in(0,1) and, in addition to ( 2.8 ), we assume \sum_{k>n}|p_{k}-p_{k+1}|\leq c^{-1}n^{-1}\rho(n)\;, (2.10) then, uniformly in n\geq\ell\geq 1 , \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}}\lesssim\frac{\rho(n)}{\rho(\ell)}\;. (2.11) All the proportionality constants depend only on the constants in ( 2.1 ) and on c,\rho . We prove Theorem 2.10 in Section 6 . Remark that ( 2.11 ) is generally sharp by Corollary 2.4 . Remark 2.11 . The only place where we use the lower bound on z_{n} is Lemma 6.9 . It is possible to assume a bound of the form C_{1}n^{-\beta}\leq z_{n}\leq C_{2}n^{-\alpha} with possibly different exponents \beta\geq\alpha , but then the bound on \|P^{n+\ell}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} becomes more complicated to state. In the same spirit, one can generalise the condition ( 2.10 ) to \sum_{k\geq n}|p_{k}+p_{k+1}|\lesssim\hat{\rho}(n) for another RV function \hat{\rho} , but again with a more complicated final result. Remark 2.12 . Condition ( 2.10 ) implies p_{n}=\sum_{m\geq n}(p_{m}-p_{m+1})\lesssim n^{-1}\rho(n) , which, by Karamata’s theorem, implies \sum_{m>n}p_{m}\lesssim\rho(n) . Hence ( 2.10 ) implies the upper bound in ( 2.8 ) (up to a multiplicative constant), and so ( 2.10 ) is the most ‘optimistic’ bound that is consistent with the upper bound in ( 2.8 ), i.e. if n^{-1}\rho(n) is replaced by \bar{\rho}(n) for RV \bar{\rho} with \bar{\rho}(n)\lesssim n^{-1}\rho(n) then we would have \sum_{m\geq n}p_{m}\lesssim n\bar{\rho}(n) , which is stronger than the upper bound from ( 2.8 ). 3 General Markov chains In this section we estimate memory loss on Harris chains, using the bounds of \|P^{n}(\delta_{0}-P^{\ell}\delta_{0})\|_{\mathrm{TV}} for the model chain ( 1.1 ). This is our principle motivation for studying the chain ( 1.1 ) and for the results of Section 2 . First we treat Markov chains with a recurrent atom in Section 3.1 and then general Harris chains in Section 3.2 . We discuss examples in Section 3.3 . Given p_{n}\geq 0 with \sum_{n\geq 1}p_{n}=1 we denote b_{\ell}(n)=\|P^{n}(\delta_{0}-P^{\ell}\delta_{0})\|_{\mathrm{TV}}\;, (3.1) where P is the transition operator on the Markov chain ( 1.1 ) defined by p_{n} . Throughout this section, let (\Omega,\Sigma) be a measurable space and X_{n} , n\geq 0 , a Markov chain with state space \Omega and transition operator Q\colon{\mathcal{P}}(\Omega)\to{\mathcal{P}}(\Omega) . 3.1 Markov chains with a recurrent atom Suppose that X_{n} has a recurrent atom S\in\Sigma . That is, there exists a probability measure \beta on \Omega such that (a) \P(X_{n}\in S\text{ infinitely often}\mid X_{0}=x)=1 for each x\in\Omega , and (b) \P(X_{n+1}\in A\mid X_{n}=x)=\beta(A) for all A\in\Sigma and x\in S . Define \tau=\inf\{k\geq 1\,:\,X_{k-1}\in S\}\qquad\text{and}\qquad p_{n}=\P(\tau=n\mid X_{0}\sim\beta)\;. (3.2) Since X_{n} is recurrent, \sum_{n\geq 1}p_{n}=1 . Let \beta_{m} , m\geq 0 , be probability measures on \Omega given by \displaystyle\beta_{m}(A) \displaystyle=\P(X_{m+1}\in A\mid X_{0}\in S\text{ while }X_{1},\ldots,X_{m}\notin S) \displaystyle=\P(X_{m}\in A\mid X_{0}\sim\beta\text{ and }\tau\geq m+1)\;. For a measure \zeta on \{0,1,\ldots\} , let \pi\zeta be its projection on \Omega obtained by \pi\zeta=\sum_{m\geq 0}\zeta(m)\beta_{m}\;. The following lemma links Q^{n}\mu , for \mu\in{\mathcal{P}}(\Omega) , with the evolution of P^{n}\delta_{0} on ( 1.1 ) for which the p_{n} are given by ( 3.2 ), up to a small remainder. Lemma 3.1 . Let X_{0}\sim\mu\in{\mathcal{P}}(\Omega) and A\in\Sigma . Then \P(X_{n}\in A)=Q^{n}\mu(A)=\pi\Bigl[\sum_{t=1}^{n}\P(\tau=t)P^{n-t}\delta_{0}\Bigr](A)+\P(X_{n}\in A\,,\tau>n)\;. Proof. Let Z_{n}=\begin{cases}-1&\text{if }n=0\text{ or }X_{0},\ldots X_{n-1}\notin S\;,\\ \min\{k\geq 0\,:\,X_{n-1-k}\in S\}&\text{otherwise}\;.\end{cases} Then (X_{n},Z_{n}) is a Markov chain on \Omega\times\{-1,0,\ldots\} , and, for m\geq 0 , \beta_{m}(A)=\P(X_{n}\in A\mid Z_{n}=m)\;,\qquad\tau=\inf\{k\geq 1\,:\,Z_{k}=0\}\;. Observe that Z_{\tau},Z_{\tau+1},\ldots behaves as the Markov chain ( 1.1 ) defined by p_{n} in ( 3.2 ), with the initial condition Z_{\tau}=0 . Consequently, \sum_{m=0}^{n}\P(Z_{t+n}=m\mid Z_{t}=0)\beta_{m}=\pi P^{n}\delta_{0}\;. Suppose that X_{0}\sim\mu . For A\in\Sigma , n\geq t\geq 1 , 0\leq mn,X_{n}\in A) \displaystyle=\sum_{t=1}^{n}\P(\tau=t)\pi[P^{n-t}\delta_{0}](A)+\P(\tau>n,X_{n}\in A)\;.\qed Lemma 3.1 can be used to estimate memory loss, for example: Corollary 3.2 . Let \mu,\mu^{\prime}\in{\mathcal{P}}(\Omega) . Then \|Q^{n}(\mu-\mu^{\prime})\|_{\mathrm{TV}}\leq\sum_{t=1}^{n}\bigl|\mu(\tau=t)-\mu^{\prime}(\tau=t)\bigr|\,b_{t-1}(n-t)+2\mu(\tau>n)+2\mu^{\prime}(\tau>n)\;, where b_{\ell}(n) are as in ( 3.1 ) and \mu(\tau=k) is a shorthand for \P(\tau=k\mid X_{0}\sim\mu) . Proof. Let X_{0}\in\mu and let X^{\prime}_{n} be a copy of X_{n} with X^{\prime}_{0}\sim\mu^{\prime} . Let \tau^{\prime} denote the copy of \tau . By Lemma 3.1 , \begin{split}Q^{n}\mu(A)-Q^{n}\mu^{\prime}(A)&=\pi\Bigl[\sum_{t=1}^{n}\bigl(\P(\tau=t)-\P(\tau^{\prime}=t)\bigr)P^{n-t}\delta_{0}\Bigr](A)\\ &\qquad+\P(X_{n}\in A\,,\tau>n)-\P(X^{\prime}_{n}\in A\,,\tau^{\prime}>n)\;.\end{split} Furthermore \sum_{t=1}^{\infty}\bigl(\P(\tau=t)-\P(\tau^{\prime}=t)\bigr)P^{n-1}\delta_{0}=0 and thus \displaystyle\sum_{t=1}^{n}\bigl(\P(\tau=t)-\P(\tau^{\prime}=t)\bigr)P^{n-t}\delta_{0} \displaystyle=\sum_{t=1}^{n}\bigl(\P(\tau=t)-\P(\tau^{\prime}=t)\bigr)(P^{n-t}\delta_{0}-P^{n-1}\delta_{0}) \displaystyle-(\P(\tau>n)-\P(\tau^{\prime}>n))P^{n-1}\delta_{0}\;. The result follows readily. ∎ Corollary 3.2 can be strengthened when \mu and \mu^{\prime} overlap, i.e. when |\mu-\mu^{\prime}|(\Omega)<2 . For \mu,\mu^{\prime}\in{\mathcal{P}}(\Omega) let |\mu-\mu^{\prime}|(\tau=n)=|\mu-\mu^{\prime}|(\Omega)\,\P(\tau=n\mid X_{0}\sim\lambda)\;, (3.3) where \lambda is the normalized to probability difference |\mu-\mu^{\prime}| , namely \lambda=\frac{|\mu-\mu^{\prime}|}{|\mu-\mu^{\prime}|(\Omega)} , if \mu\neq\mu^{\prime} , and an arbitrary measure otherwise. Corollary 3.3 . Let \mu,\mu^{\prime}\in{\mathcal{P}}(\Omega) . Then \|Q^{n}(\mu-\mu^{\prime})\|_{\mathrm{TV}}\leq\sum_{t=1}^{n}|(\mu-\mu^{\prime})(\tau=t)|\,b_{t-1}(n-t)+2|\mu-\mu^{\prime}|(\tau>n)\;, where b_{\ell}(n) are as in ( 3.1 ) and |\mu-\mu^{\prime}|(\tau=k) is as in ( 3.3 ). Proof. Write \mu-\mu^{\prime}=\frac{1}{2}|\mu-\mu^{\prime}|(\Omega)\,(\kappa-\kappa^{\prime}) , where \kappa and \kappa^{\prime} are mutually singular probability measures. Then \lambda=\frac{1}{2}|\kappa-\kappa^{\prime}|=\frac{1}{2}(\kappa+\kappa^{\prime}) and \P(\tau=n\mid X_{0}\sim\lambda)=\frac{1}{2}(\kappa(\tau=n)+\kappa^{\prime}(\tau=n)) . The result follows from Corollary 3.2 applied to \kappa,\kappa^{\prime} . ∎ 3.2 Harris chains Suppose now that X_{n} is a Harris chain [ Lin02 , Dur19 ] , i.e. there exists S\in\Sigma , \varepsilon>0 and a probability measure \beta on \Omega such that (a) \P(X_{n}\in S\text{ infinitely often}\mid X_{0}=x)=1 for each x\in\Omega , and (b) \P(X_{n+1}\in A\mid X_{n}=x)\geq\varepsilon\beta(A) for all A\in\Sigma and x\in S . Remark 3.4 . If \varepsilon=1 , then S is an atom and we can work with X_{n} as in Section 3.1 . For \varepsilon<1 the situation is not too different: using Nummelin’s splitting technique [ Num78 ] we can extend X_{n} to a Markov chain with an atom. Remark 3.5 . There are different definitions of Harris (recurrent) chains in the literature, see e.g. [ Num84 , MT09 , BH22 ] . We work with a definition that is simple for our purposes. See e.g. [ NT82 ] that relates our definition to others. Let \xi_{n} , n\geq 0 , be a sequence of independent (also from the Markov chain X_{n} ) Bernoulli random variables with \P(\xi_{n}=1)=\varepsilon and \P(\xi_{n}=0)=1-\varepsilon . Denote \tau=\inf\{k\geq 1\,:\,X_{k-1}\in S\text{ and }\xi_{k-1}=1\}\qquad\text{and}\qquad p_{n}=\P(\tau=n\mid X_{0}\sim\beta)\;. (3.4) This way, p_{n} and \tau are geometrically compounded versions of ( 3.2 ). Again, \sum_{n\geq 1}p_{n}=1 . Let \beta_{m} , m\geq 0 , be probability measures on \Omega given by \beta_{m}(A)=\P(X_{m}\in A\mid X_{0}\sim\beta\text{ and }\tau\geq m+1)\;. For a measure \zeta on \{0,1,\ldots\} , let \pi\zeta be the measure on \Omega obtained by \pi\zeta=\sum_{m\geq 0}\zeta(m)\beta_{m}\;. The exact copy of Lemma 3.1 holds: Lemma 3.6 . Let X_{0}\sim\mu\in{\mathcal{P}}(\Omega) and A\in\Sigma . Then \P(X_{n}\in A)=Q^{n}\mu(A)=\pi\Bigl[\sum_{t=1}^{n}\P(\tau=t)P^{n-t}\delta_{0}\Bigr](A)+\P(X_{n}\in A,\,\tau>n)\;. Proof. The strategy, following [ Num78 ] , is to extend X_{n} to a Markov chain with an atom and then apply Lemma 3.1 . To this end, let H(x,A)=\P(X_{n+1}\in A\mid X_{n}=x) denote the kernel of X_{n} . Define H_{0}(x,A) by H(x,A)=\begin{cases}\varepsilon\beta(A)+(1-\varepsilon)H_{0}(x,A)&\text{if }x\in S\;,\\ H_{0}(x,A)&\text{otherwise}\;,\end{cases} where, if \varepsilon=1 , we set H_{0}(x,\cdot) arbitrarily for x\in S . Let {\widehat{X}}_{n} be the Markov chain on {\widehat{\Omega}}=\Omega\times\{0,1\} with kernel {\widehat{H}}((x,0),(A,t))=\begin{cases}(1-\varepsilon)H_{0}(x,A\cap S)+H_{0}(x,A\setminus S)&\text{if }t=0\;,\\ \varepsilon H_{0}(x,A\cap S)&\text{if }t=1\;,\end{cases} {\widehat{H}}((x,1),(A,t))={\hat{\beta}}(A,t):=\begin{cases}(1-\varepsilon)\beta(A\cap S)+\beta(A\setminus S)&\text{if }t=0\;,\\ \varepsilon\beta(A\cap S)&\text{if }t=1\;.\end{cases} (3.5) Recall that X_{0}\sim\mu and let {\widehat{X}}_{0}\sim{\hat{\mu}} where {\hat{\mu}}(A\times\{0\})=\mu(A\setminus S)+(1-\varepsilon)\mu(A\cap S)\quad\text{and}\quad{\hat{\mu}}(A\times\{1\})=\varepsilon\mu(A\cap S)\;. Observe that \P({\widehat{X}}_{n}=(x,1)\mid{\widehat{X}}_{n}\in\{x\}\times\{0,1\})=\varepsilon\mathbf{1}_{x\in S} . It is then a direct verification that \P\bigl({\widehat{X}}_{n+1}\in A\times\{0,1\}\mid{\widehat{X}}_{n}\in\{x\}\times\{0,1\}\bigr)=\P(X_{n+1}\in A\mid X_{n}=x)\;. That is, the first component marginal process of {\widehat{X}}_{n} has the same law as X_{n} . Moreover {\widehat{S}}=S\times\{1\} is an atom for {\widehat{X}}_{n} , which thus falls within the framework of Section 3.1 with {\hat{\tau}}=\inf\{k\geq 1\,:\,{\widehat{X}}_{k-1}\in{\widehat{S}}\} , {\hat{\beta}}\in{\mathcal{P}}({\widehat{\Omega}}) as in ( 3.5 ), and the corresponding projection {\hat{\pi}} . Moreover, \P(\tau=n\mid X_{0}\sim\beta)=\P({\hat{\tau}}=n\mid{\widehat{X}}_{0}\sim{\hat{\beta}}) , so the distributions p_{n} for X_{n} and {\widehat{X}}_{n} coincide. Thus, by Lemma 3.1 , writing {\widehat{A}}=A\times\{0,1\} , \P({\widehat{X}}_{n}\in{\widehat{A}})={\hat{\pi}}\Bigl[\sum_{t=1}^{n}\P({\hat{\tau}}=t)P^{n-t}\delta_{0}\Bigr]({\widehat{A}})+\P({\widehat{X}}_{n}\in{\widehat{A}},\,{\hat{\tau}}>n)\;. The hats can be removed, yielding the desired result. ∎ With the same proof as Corollary 3.3 , we obtain the following. Corollary 3.7 . Let \mu,\mu^{\prime}\in{\mathcal{P}}(\Omega) . Then \|Q^{n}(\mu-\mu^{\prime})\|_{\mathrm{TV}}\leq\sum_{t=1}^{n}|(\mu-\mu^{\prime})(\tau=t)|\,b_{t-1}(n-t)+2|\mu-\mu^{\prime}|(\tau>n)\;, where b_{\ell}(n) are as in ( 3.1 ) and |\mu-\mu^{\prime}|(\tau=k) is as in ( 3.3 ). 3.3 An example Suppose we are in the setting of Section 3.2 . In particular, X is a Harris chain. Recall ( 3.3 ) where \tau is from ( 3.4 ). Corollary 3.7 provides a convenient way to estimate memory loss: Proposition 3.8 . Suppose that b_{\ell}(n)=\|P^{n}\delta_{0}-P^{n+\ell}\delta_{0}\|_{\mathrm{TV}}\lesssim\rho(n)g(\ell) uniformly in n\geq\ell\geq 1 , where \rho,g are RV with g increasing. Denote \|\mu-\mu^{\prime}\|_{g}=\sum_{\ell\geq 0}g(\ell)|\mu-\mu^{\prime}|(\tau=\ell)=|\mu-\mu^{\prime}|(\Omega)\,\E_{X_{0}\sim\lambda}g(\tau)\;, (3.6) where \lambda=\frac{|\mu-\mu^{\prime}|}{|\mu-\mu^{\prime}|(\Omega)} . Then \|Q^{n}\mu-Q^{n}\mu^{\prime}\|_{\mathrm{TV}}\lesssim\{\rho(n)+1/g(n)\}\|\mu-\mu^{\prime}\|_{g}\;. (3.7) Proof. Denote \mu_{\ell}=\mu(\tau=\ell),\mu^{\prime}_{\ell}=\mu^{\prime}(\tau=\ell) . Remark that |\mu_{\ell}-\mu^{\prime}_{\ell}|=\Bigl|\int_{\Omega}\P(\tau=\ell\mid X_{0}=x)(\mu-\mu^{\prime})(dx)\Bigr|\leq|\mu-\mu^{\prime}|(\tau=\ell)\;. By Corollary 3.7 , \|Q^{n}(\mu-\mu^{\prime})\|_{\mathrm{TV}}\leq\sum_{\ell=1}^{n}\bigl|\mu_{\ell}-\mu^{\prime}_{\ell}\bigr|\,b_{\ell-1}(n-\ell)+2|\mu-\mu^{\prime}|(\tau>n)\;. Then, using b_{\ell}(n)\lesssim 1\wedge g(\ell)\rho(n) , \displaystyle\sum_{\ell=1}^{n}|\mu_{\ell}-\mu^{\prime}_{\ell}|b_{\ell-1}(n-\ell) \displaystyle\lesssim\sum_{n/2<\ell\leq n}|\mu_{\ell}-\mu^{\prime}_{\ell}|+\sum_{1\leq\ell\leq n/2}|\mu_{\ell}-\mu^{\prime}_{\ell}|g(\ell)\rho(n-\ell) \displaystyle\lesssim(g(n)^{-1}+\rho(n))\|\mu-\mu^{\prime}\|_{g}\;, where we used \sum_{n/2<\ell\leq n}|\mu_{\ell}-\mu^{\prime}_{\ell}|\lesssim g(n)^{-1}\|\mu-\mu^{\prime}\|_{g} . Finally, since g is increasing, we clearly have |\mu-\mu^{\prime}|(\tau>n)\leq g(n)^{-1}\|\mu-\mu^{\prime}\|_{g} . ∎ Remark 3.9 . Proposition 3.8 can be seen as a version of classical results for positive recurrent Markov chains, like [ Lin02 , Theorem 4.2, p27] . However, Proposition 3.8 does not yield sharp rates in some simple situations. For example, consider the Markov chain ( 1.1 ) with S=\{\hbox to12.74pt{\vbox to12.74pt{\pgfpicture\makeatletter\hbox{\hskip 6.36772pt\lower-6.36772pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} { {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin=1} {{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 8.53 0 C 8.53 4.71 4.71 8.53 0 8.53 C -4.71 8.53 -8.53 4.71 -8.53 0 C -8.53 -4.71 -4.71 -8.53 0 -8.53 C 4.71 -8.53 8.53 -4.71 8.53 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin=1} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\lxSVG@begingroup@{transform=matrix(1.0 0.0 0.0 1.0 -3.46 -4.46)} \pgfsys@hbox{59}\lxSVG@closescope }}} \lxSVG@closescope }}} } \lxSVG@closescope {{{}}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\} and p_{k}=Ck^{-\alpha-1} , \alpha\in(0,1) , so that \sum_{k>n}p_{k}=\rho(n) with \rho(n)=C^{\prime}n^{-\alpha} . Then by Theorem 2.10 , b_{\ell}(n)\lesssim\rho(n)g(\ell) with g(\ell)=\ell^{\alpha} , and this is sharp by Corollary 2.4 . Let \mu=\delta_{0} and \mu^{\prime}=\delta_{1} . Then, attempting to apply Proposition 3.8 , we estimate \P(\tau=n\mid X_{0}\sim\lambda)\asymp p_{n}=Cn^{-\alpha-1} , and hence \E_{X_{0}\sim\lambda}g(\tau)\asymp\sum_{n\geq 1}n^{-1} , which is infinite, and thus so is the right-hand side of ( 3.7 ). This is not surprising because ( 3.6 ) is a strong moment while we otherwise work with weak moments. To apply Proposition 3.8 to this example, we could instead use the bound b_{\ell}(n)\lesssim\ell^{\beta}n^{-\beta} for \beta<\alpha . Then \E_{X_{0}\sim\lambda}\tau^{\beta}\asymp\sum_{n\geq 1}n^{\beta-\alpha-1}<\infty , which yields \|Q^{n}\mu-Q^{n}\mu^{\prime}\|_{\mathrm{TV}}\lesssim n^{-\beta} but which is not sharp. It is possible to use Lemmas 3.1 or 3.6 directly to recover the sharp rate, or, of course, \|P^{n}(\delta_{0}-\delta_{1})\|_{\mathrm{TV}}=(1-p_{1})^{-1}\|P^{n}(\delta_{0}-P\delta_{0})\|_{\mathrm{TV}}=(1-p_{1})^{-1}b_{1}(n)\lesssim n^{-\alpha}\;. 4 Ornstein’s coupling In this section we prove Theorem 2.6 , adapting Ornstein’s proof [ Orn69a , Orn69b ] of Orey’s theorem. The proof is based on reduction to a symmetric random walk on integers and coupling when the random walk reaches 0 . 4.1 Meeting times and coupling inequality Consider probability distributions \mu,\nu on a state space \Omega and a transition operator P\colon{\mathcal{P}}(\Omega)\to{\mathcal{P}}(\Omega) . We recall how to bound \|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}} by coupling. Consider \Omega -valued Markov chains X,Y , defined on the same probability space, with initial distributions X_{0}\sim\mu,Y_{0}\sim\nu . Suppose that exists a random time T>0 such that X_{n}=Y_{n} for all n\geq T . Then \P(X_{n}\neq Y_{n})\leq\P(T>n) which in particular implies that, for any measurable A\subset\Omega , \displaystyle\P(X_{n}\in A) \displaystyle=\P(X_{n}\in A,\,T\leq n)+\P(X_{n}\in A,\,T>n)\leq\P(Y_{n}\in A,\,T\leq n)+\P(T>n) \displaystyle\leq\P(Y_{n}\in A)+\P(T>n)\;. By symmetry, \P(Y_{n}\in A)\leq\P(X_{n}\in A)+\P(T>n) . We thus obtain the coupling inequality, a simple yet very useful tool for estimating total variation (see e.g. [ Lin02 , Chapter I] ): \|P^{n}\mu-P^{n}\nu\|_{\mathrm{TV}}=2\sup_{A}|\P(X_{n}\in A)-\P(Y_{n}\in A)|\leq 2\P(T>n)\;. (4.1) 4.2 Proof of Theorem 2.6 By the aperiodicity condition ( 2.1 ), there exists A\geq 1 such that p_{A},p_{A+1}>0 . Let X be the Markov chain ( 1.1 ) with X_{0}=0 . Let a_{0}=\inf\{j\geq\ell\,:\,X_{j}=0\} and a_{k+1}=\inf\{j>a_{k}:X_{j}=0\} index visits of X to 0 after time \ell . Let \Delta denote backward increments, so \Delta a_{k}=a_{k}-a_{k-1} and \P(\Delta a_{k}=n)=p_{n} for all k\geq 1 . On the same (possibly enriched) probability space as X , we now construct another Markov chain Y with the same transition probabilities but with initial state Y_{0}=X_{\ell}\sim P^{\ell}\delta_{0} . To define Y , it suffices to specify the times b_{0}=\inf\{j\geq 0\,:\,Y_{j}=0\} and b_{k+1}=\inf\{j>b_{k}\,:\,Y_{j}=0\} that index the visits of Y to 0 . First, let b_{0}=a_{0}-\ell so that Y_{0}=X_{\ell},Y_{1}=X_{\ell+1},\ldots,Y_{b_{0}}=X_{a_{0}} . Then we define b_{k} for k\geq 1 by \Delta b_{k}=\begin{cases}\Delta a_{k}&\text{if }a_{k-1}=b_{k-1}\text{ or }\Delta a_{k}\notin\{p_{A},p_{A+1}\}\;,\\ s_{k}&\text{otherwise,}\end{cases} where s_{k} is a sequence of independent (also from X ) and identically distributed random variables with \P(s_{k}=A)=p_{A}/(p_{A}+p_{A+1}) and \P(s_{k}=A+1)=p_{A+1}/(p_{A}+p_{A+1}) . This completes the construction of Y . Remark that, for k\geq 1 , \Delta b_{k} has the same distribution as \Delta a_{k} , thus Y indeed has the same transition operator as X . Denote d_{k}=a_{k}-b_{k} . Let k_{0}=0 and let k_{i} , i\geq 1 , index when d_{k} can change, namely k_{i+1}=\inf\{j>k_{i}\,:\,\Delta a_{j}\in\{p_{A},p_{A+1}\}\} . Observe that \Delta a_{k_{i}}=a_{k_{i}}-a_{k_{i-1}} are i.i.d. with \P(\Delta a_{k_{i}}\geq j)\leq\rho(j) . Furthermore, d_{k_{0}},d_{k_{1}},\ldots is a symmetric random walk on integers starting at d_{k_{0}}=d_{0}=\ell\geq 1 and stopping when it reaches 0 , with \Delta d_{k_{i}}=d_{k_{i}}-d_{k_{i-1}}\in\{-1,0,1\} and \P(\Delta d_{k_{i}}=\pm 1\mid d_{k_{i-1}}\neq 0)=p_{A}p_{A+1}/(p_{A}+p_{A+1})^{2}\;. Let \sigma=\inf\{j>0\,:\,d_{k_{j}}=0\} . Consider a walk Z_{i} with the same transition probabilities as d_{k_{i}} but without stopping, such that Z_{i}=\ell-d_{k_{i}} for i\leq\sigma . Note that \sigma=\{j>0\,:\,Z_{j}=\ell\} . By the reflection principle, \P(\sigma\leq n)=\P(\max_{i\leq n}Z_{i}\geq\ell)=\P(Z_{n}=\ell)+2\P(Z_{n}>\ell)=\P(Z_{n}=\ell)+\P(|Z_{n}|>\ell) and thus, uniformly in n,\ell , \P(\sigma>n)\leq\P(|Z_{n}|\leq\ell)\lesssim\ell n^{-1/2} . Now let m,n\geq 0 . Using ( 4.1 ) and that X_{n}=Y_{n} for all n\geq a_{k_{\sigma}} , we obtain \begin{split}\|P^{n}\delta_{0}-P^{n+\ell}\delta_{0}\|_{\mathrm{TV}}&\leq 2\P(a_{k_{\sigma}}>n)\leq 2\P(a_{k_{m}}\geq n)+2\P(\sigma\geq m)\\ &\lesssim\P(a_{k_{m}}\geq n)+\ell m^{-1/2}\;.\end{split} (4.2) It remains to bound \P(a_{k_{m}}\geq n) and choose a suitable m . Let c_{i}=\Delta a_{k_{i}}\mathbf{1}\{\Delta a_{k_{i}}\leq B\} with 00 . Thus \displaystyle\P\Bigl(\sum_{i=1}^{m}c_{i}\geq n\Bigr) \displaystyle\leq\exp\Bigl[-\frac{n}{2B}\gamma\log\Bigl(\frac{nB}{2m\mathrm{Var}(c_{1})}\Bigr)\Bigr]=\Bigl(\frac{2m\mathrm{Var}(c_{1})}{nB}\Bigr)^{\frac{\gamma n}{2B}} \displaystyle\leq K^{\gamma n/B}\Bigl(\frac{mB\rho(B)}{n}\Bigr)^{\frac{\gamma n}{2B}}\;, where K is uniform in n,m and where we used that, if \frac{2m\mathrm{Var}(c_{1})}{nB}\geq 1 , then the first bound trivially holds. Taking B=\frac{n}{2p} for p\geq 1 , we obtain \P\Bigl(\sum_{i=1}^{m}c_{i}\geq n\Bigr)\lesssim(m\rho(n))^{\gamma p} and therefore, by ( 4.2 ), ( 4.3 ), and ( 4.4 ), for fixed p\geq\gamma^{-1} and uniformly in m,n such that m\E c_{1}\leq n/2 , \begin{split}\|P^{n}\delta_{0}-P^{n+\ell}\delta_{0}\|_{\mathrm{TV}}&\lesssim\ell m^{-1/2}+m\rho(n)+(m\rho(n))^{\gamma p}\\ &\lesssim\ell m^{-1/2}+m\rho(n)\;.\end{split} (4.5) Now we treat the cases \alpha<1 , \alpha=1 and \alpha\in(1,\frac{3}{2}) separately. First suppose that \alpha<1 . The result is trivial if \ell^{2/3}\rho(n)^{1/3}>1 , so we assume that \ell^{2/3}\rho(n)^{1/3}\leq 1 . To optimise, we take m=1+\lfloor\ell^{2/3}\rho(n)^{-2/3}\rfloor , which implies \ell m^{-1/2}\asymp m\rho(n)\asymp\ell^{2/3}\rho(n)^{1/3} . Note that m\E c_{1}\lesssim mB\rho(B)\ll mn\rho(n)\asymp\ell^{2/3}\rho(n)^{1/3}n\leq n\;, where the asymptotic ratio can be made arbitrarily large by taking p large. Hence with a suitably large p we achieve m\E c_{1}\leq n/2 for all sufficiently large n . Therefore ( 4.5 ) holds and we conclude \|P^{n}\delta_{0}-P^{n+\ell}\delta_{0}\|_{\mathrm{TV}}\lesssim\ell^{2/3}\rho(n)^{1/3} . Suppose now that \alpha=1 . Then \E c_{1}\lesssim M(B)=1+\int_{1}^{B}\rho(t)\,dt , which is slowly varying in B and increasing. We take m=1+\lfloor\delta\ell^{2/3}\rho(n)^{-2/3}\rfloor for some small \delta>0 . Now the constraint m\E c_{1}\leq n/2 is satisfied for sufficiently large n if \ell\ll\rho(n)M(n)^{-3/2}n^{3/2} , and the proof proceeds as for \alpha<1 . The case \ell\leq\rho(n)M(n)^{-3/2}n^{3/2} as in the statement of the theorem follows from a bounded number of applications of the triangle inequality. Suppose now that \alpha\in(1,\frac{3}{2}) . Then \E c_{1}\lesssim 1 . To optimise, we take m as a small multiple of 1+\lfloor\ell^{2/3}\rho(n)^{-2/3}\rfloor , so that \ell m^{-1/2}\asymp m\rho(n)\asymp\ell^{2/3}\rho(n)^{1/3} . Then, for n sufficiently large, m\E c_{1}\leq\ell^{2/3}\rho(n)^{-2/3}\leq n/2 by the assumption that \ell\leq\rho(n)n^{3/2} . Once again ( 4.5 ) holds and we conclude \|P^{n}\delta_{0}-P^{n+\ell}\delta_{0}\|_{\mathrm{TV}}\lesssim\ell^{2/3}\rho(n)^{1/3} . The proof of Theorem 2.6 is complete. 5 Monotonicity In this section we prove Theorem 2.8 . Recall the definition of u_{n} and z_{n} in Section 2.1 . Proof of Theorem 2.8 . Let \mu_{n}=P^{n}\delta_{0} . By ( 2.3 ), \|\mu_{n}-\mu_{n+\ell}\|_{\mathrm{TV}}=\sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}+\sum_{m=0}^{n}(u_{n-m}-u_{n+\ell-m})z_{m}\;. At the same time, (\mu_{n}-\mu_{n+\ell})(\{0,\ldots,n+\ell\})=0 , so again by ( 2.3 ), \sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}=\sum_{m=0}^{n}(u_{n-m}-u_{n+\ell-m})z_{m}\;. Hence \|\mu_{n}-\mu_{n+\ell}\|_{\mathrm{TV}}=2\sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}\;.\qed 5.1 Proof of Lemma 2.9 Recall that z_{0}=1 and z_{n}=z_{n+1}+p_{n+1} . Assume the DFR in this subsection. Excluding the trivial case p_{1}=1 and p_{n}=0 for n\geq 2 , assume that p_{n}>0 for all n\geq 1 , so that \frac{p_{n}}{z_{n-1}}\geq\frac{p_{n+1}}{z_{n}}\quad\text{for}\quad n\geq 1\;. Lemma 5.1 . Suppose that b_{k} , k\geq 0 , is a non-negative sequence with \frac{b_{k+1}}{b_{k}}\leq\frac{z_{k+1}}{z_{k}} for all k . Let c_{k}=b_{k+1}+p_{k+1}b_{0} for k\geq 0 . Then \frac{c_{k+1}}{c_{k}}\leq\frac{z_{k+1}}{z_{k}} for all k . Proof. Fix k\geq 0 and write \frac{c_{k+1}}{c_{k}}=\frac{b_{k+2}+p_{k+2}b_{0}}{b_{k+1}+p_{k+1}b_{0}}=\lambda\frac{b_{k+2}}{b_{k+1}}+(1-\lambda)\frac{p_{k+2}}{p_{k+1}}\;, where \lambda=\frac{b_{k+1}}{b_{k+1}+p_{k+1}b_{0}}\in(0,1] . Since \frac{p_{k+2}}{p_{k+1}}\leq\frac{z_{k+1}}{z_{k}} , it suffices to consider the case \frac{b_{k+2}}{b_{k+1}}>\frac{z_{k+1}}{z_{k}} . Then, since \lambda is monotone decreasing function of b_{0} (with all other variables fixed), so is \frac{c_{k+1}}{c_{k}} . In turn, from \frac{b_{k+1}}{b_{0}}\leq\frac{z_{k+1}}{z_{0}} we obtain b_{0}\geq\frac{b_{k+1}}{z_{k+1}} and \frac{c_{k+1}}{c_{k}}\leq\frac{b_{k+2}+p_{k+2}\frac{b_{k+1}}{z_{k+1}}}{b_{k+1}+p_{k+1}\frac{b_{k+1}}{z_{k+1}}}=\frac{\frac{b_{k+2}}{b_{k+1}}+\frac{p_{k+2}}{z_{k+1}}}{1+\frac{p_{k+1}}{z_{k+1}}}\leq\frac{\frac{z_{k+2}}{z_{k+1}}+\frac{p_{k+2}}{z_{k+1}}}{1+\frac{p_{k+1}}{z_{k+1}}}=\frac{z_{k+1}}{z_{k}}\;.\qed Corollary 5.2 . u_{n}\geq u_{n+1} for all n\geq 0 . Proof. Consider a Markov chain Y_{n} on non-negative integers with the connection graph ( 1.1 ) but all arrows reversed, starting at Y_{0}=0 with transition probabilities \P(Y_{n+1}=k\mid Y_{n}=k+1)=1\quad\text{and}\quad\P(Y_{n+1}=k\mid Y_{n}=0)=p_{k+1}\quad\text{for}\quad k\geq 0\;. Set b_{k}^{n}=\P(Y_{n}=k) . Note that b_{k}^{n+1}=b_{k+1}^{n}+p_{k+1}b_{0}^{n} . Observe that the renewal probabilities \P(Y_{n}=0\mid Y_{n}=0) coincide with those for the Markov chain ( 1.1 ), hence u_{n}=b_{0}^{n} . By Lemma 5.1 applied inductively, \frac{b_{k+1}^{n}}{b_{k}^{n}}\leq\frac{z_{k+1}}{z_{k}} for all n,k , and in particular \frac{b_{1}^{n}}{b_{0}^{n}}\leq\frac{z_{1}}{z_{0}} . Then \frac{u_{n+1}}{u_{n}}=\frac{b_{1}^{n}+p_{1}b_{0}^{n}}{b_{0}^{n}}=\frac{b_{1}^{n}}{b_{0}^{n}}+p_{1}\leq\frac{z_{1}^{n}}{z_{0}^{n}}+p_{1}=1\;.\qed 6 Practical rates In this section we prove Theorem 2.10 . Without loss of generality we assume that \rho\colon[0,\infty)\to(0,\infty) is monotone and continuous, with \rho(0)=\rho(1)=1 . Let us write \rho(z)=z^{-\alpha}L(z) for z\geq 1 with a slowly varying function L . Define K(z)=1+\int_{1}^{z}t^{-1}L(t)^{-2}\,dt\;,\quad z\geq 1\;. Remark 6.1 . K(z) is strictly increasing in z and K\geq 1 and K(z)\gtrsim L(z)^{-2}\;. (6.1) Moreover, by Karamata’s theorem from Section 2.1.1 , K(z) is slowly varying. Denote \mu_{n}=P^{n}\delta_{0}\;. Throughout this section we assume that ( 2.8 ) holds. Recall u_{n} from Section 2.1 . 6.1 Proof of ( 2.9 ) We admit for a moment the following lemma, postponing the proof: Lemma 6.2 . Suppose ( 2.8 ) holds. Then, uniformly in n\geq 1 , u_{n}\lesssim\begin{cases}\rho(n)\quad&\text{if }\alpha\in(0,\frac{1}{2})\;,\\ \rho(n)K(n)\quad&\text{if }\alpha=\frac{1}{2}\;,\\ n^{-1}\rho(n)^{-1}\quad&\text{if }\alpha\in(\frac{1}{2},1)\;.\end{cases} (6.2) Furthermore, uniformly in \ell\geq 1 and n\geq 2\ell , |u_{n}-u_{n-\ell}|\lesssim\rho(n)\times\begin{cases}1\quad&\text{if }\alpha\in(0,\frac{1}{2})\;,\\ K(\ell)\quad&\text{if }\alpha=\frac{1}{2}\;,\\ \ell^{-1}\rho(\ell)^{-2}\quad&\text{if }\alpha\in(\frac{1}{2},1)\;.\end{cases} (6.3) Remark 6.3 . The key result of [ GL63 ] is that, if \alpha>1/2 and z_{n}=\rho(n) , then \lim_{n\to\infty}n\rho(n)u_{n}=\frac{\sin\pi\alpha}{\pi} . This is consistent with ( 6.2 ). Lemma 6.4 . Suppose that u_{n}\leq g(n) where g is RV with index in (-1,0) . Then, uniformly in n\geq 0 , \ell\geq 1 , \|\mu_{n+\ell}-\mu_{n}\|_{\mathrm{TV}}\lesssim\ell g(\ell)\rho(n)+\sum_{r=\ell}^{n+\ell}\rho(n+\ell-r)|u_{r}-u_{r-\ell}|\;. Proof. If n\leq 4\ell , then \rho(n)\gtrsim\rho(\ell) , so the desired bound follows simply from \|\mu_{n}\|_{\mathrm{TV}}=1 . We thus consider n>4\ell . By ( 2.3 ), \|\mu_{n+\ell}-\mu_{n}\|_{\mathrm{TV}}=\sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}+\sum_{m=0}^{n}|u_{n+\ell-m}-u_{n-m}|z_{m}\;. (6.4) By the assumption u_{n}\leq g(n) and the upper bound in ( 2.8 ), \sum_{m=n+1}^{n+\ell}u_{n+\ell-m}z_{m}\lesssim\sum_{m=n+1}^{n+\ell}g(n+\ell-m)\rho(m)\asymp\ell g(\ell)\rho(n)\;, where we used 4\ell\frac{1}{2} . We assume that n\gg\ell as otherwise the right-hand side of ( 2.9 ) is order 1 . By ( 6.2 ) and Lemma 6.4 , it suffices to bound \sum_{r=\ell}^{n+\ell}\rho(n+\ell-r)|u_{r}-u_{r-\ell}|\;. By Lemma 6.2 , we can use the following bounds: • |u_{r}-u_{r-\ell}|\leq u_{r}+u_{r-\ell}\lesssim(r-\ell+1)^{-1}\rho(r-\ell)^{-1} for \ell\leq r<2\ell , • |u_{r}-u_{r-\ell}|\lesssim\rho(r)\ell^{-1}\rho(\ell)^{-2} for 2\ell\leq r . The first case contributes, recalling that n\gg\ell , \sum_{\ell\leq r<2\ell}\frac{\rho(n+\ell-r)}{(r-\ell+1)\rho(r-\ell)}\asymp\frac{\rho(n)}{\rho(\ell)}\;. Note that \frac{\rho(n)}{\rho(\ell)}\lesssim\frac{n\rho(n)^{2}}{\ell\rho(\ell)^{2}} since n\gg\ell . The second case contributes, \sum_{2\ell\leq r\leq n+\ell}\frac{\rho(n+\ell-r)\rho(r)}{\ell\rho(\ell)}\lesssim\frac{n\rho(n)^{2}}{\ell\rho(\ell)^{2}}\;. The conclusion follows. ∎ Remark 6.5 . Repeating this proof with \alpha\in(0,1/2) does not yield anything useful: we get \|\mu_{n+\ell}-\mu_{n}\|_{\mathrm{TV}}\lesssim n\rho(n)^{2} which grows with n . However, for \alpha=1/2 we obtain \|\mu_{n+\ell}-\mu_{n}\|_{\mathrm{TV}}\lesssim K(\ell)L(n)^{2} , which, depending on L , may be small for small \ell and large n . To finish the proof of ( 2.9 ), it remains to prove Lemma 6.2 , for which we require several definitions and lemmas. Define P(x)=\sum_{n=1}^{\infty}p_{n}e_{n}(x) , where e_{n}(x)=e^{\mathbf{i}nx} and \mathbf{i}=\sqrt{-1} . Since P is periodic with period 2\pi , we will treat it as a function on [-\pi,\pi) . Lemma 6.6 . |P|\leq 1 with P(x)=1 if and only if x=0 . Proof. Since \sum_{k}p_{k}=1 and p_{k}\geq 0 for all k\geq 1 , we have |P|\leq 1 , so it remains to show that P(x)=1 if and only if x=0 . Let z=x/2\pi\in[-\frac{1}{2},\frac{1}{2}) . Observe that P(x)=1 if and only if e^{\mathbf{i}mx}=1 , or mz\in{\mathbb{Z}} , for each m with p_{m}>0 . By the aperiodicity assumption ( 2.1 ), there exist m_{1},\ldots,m_{k} such that \gcd(m_{1},\ldots,m_{k})=1 and p_{m_{i}}>0 . Suppose there exists z\in[-\frac{1}{2},\frac{1}{2})\setminus\{0\} such that m_{i}z\in{\mathbb{Z}} for all i=1,\ldots,k . Writing z=a/b with a,b coprime we obtain z=a/b=c_{i}/m_{i} for some c_{i}\in{\mathbb{Z}} , i.e. am_{i}=bc_{i} . However, if a,b are coprime then b must divide m_{i} for all i=1,\ldots,k , therefore b=1 and z is an integer. This is a contradiction. ∎ For a function h\colon(0,\infty)\to(0,\infty) and f\colon I\to{\mathbb{C}} , where I\subset{\mathbb{R}} , define |f|_{\mathcal{C}^{h}(I)}=\sup_{x\neq y\in I}\frac{|f(x)-f(y)|}{h(|x-y|^{-1})}\;. We will drop I from the subscript whenever I=[-\pi,\pi) and f is 2\pi -periodic. Lemma 6.7 . Suppose B=\sum_{m\in{\mathbb{Z}}}b_{m}e_{m} with \sum_{|m|\geq n}|b_{n}|\leq h(n) where h is non-increasing and regularly varying with index \beta\in(-1,0] . Then |B|_{\mathcal{C}^{h}}\leq C_{h} , where C_{h}<\infty depends only on h . Proof. Fix \delta\in(0,1) and decompose B=\hat{B}+\tilde{B} where \tilde{B}=\sum_{|k|\geq\delta^{-1}}b_{k}e_{k} . Then |\tilde{B}|_{\infty}\leq\sum_{|k|\geq\delta^{-1}}|b_{k}|\leq h(\delta^{-1}) . On the other hand, |\hat{B}^{\prime}|_{\infty}\leq\sum_{|k|\leq\delta^{-1}}|kb_{k}| . Since \sum_{2^{n}\leq|k|\leq 2^{n+1}}|b_{k}|\leq h(2^{n}) , we obtain, uniformly in \delta\in(0,1) , |\hat{B}^{\prime}|_{\infty}\leq\sum_{\begin{subarray}{c}0\leq n\leq|\log_{2}\delta|\\ 2^{n}\leq|k|\leq 2^{n+1}\end{subarray}}|kb_{k}|\leq 2\sum_{0\leq n\leq|\log_{2}\delta|}2^{n}h(2^{n})\lesssim\delta^{-1}h(\delta^{-1})\;, where we used that nh(n) is regularly varying with index 1+\beta>0 . Consequently, for |x-y|=\delta , |B(x)-B(y)|\leq\delta|\hat{B}^{\prime}|_{\infty}+2|\tilde{B}|_{\infty}\lesssim h(\delta^{-1})\;.\qed Lemma 6.8 . |P|_{\mathcal{C}^{\rho}}<\infty . Proof. Follows from Lemma 6.7 and the upper bound in ( 2.8 ). ∎ Lemma 6.9 . |1-P(x)|\geq\operatorname{Re}(1-P(x))\gtrsim\rho(1/|x|) uniformly in x\in[-\pi,\pi) . Proof. By Lemma 6.6 , \operatorname{Re}(1-P(x))>0 if x\neq 0 , and it remains to consider the behaviour with x close to 0 . Since p_{k}\geq 0 and 1-\cos(mx)\gtrsim|mx|^{2} for all mx\leq\pi , we obtain \operatorname{Re}(1-P(x))=\sum_{m=1}^{\infty}p_{m}(1-\cos(mx))\gtrsim\sum_{m<\pi|x|^{-1}}p_{m}m^{2}|x|^{2}\;. By our assumptions on \rho , there exists \varepsilon>0 such that 2\rho(n)\leq c\rho(\varepsilon n) for all n sufficiently large so that \rho(n)\leq\frac{c}{4} . Then, by the two-sided bound ( 2.8 ), \sum_{\varepsilon n\leq m1 , note that \int_{-\pi}^{\pi}f(x+\pi/|n|)e^{\mathbf{i}nx}\,dx=-\int_{-\pi}^{\pi}f(x)e^{\mathbf{i}nx}\,dx , and thus \Big|\int_{-\pi}^{\pi}f(x)e^{\mathbf{i}nx}\,dx\Big|=\frac{1}{2}\Big|\int_{-\pi}^{\pi}\{f(x)-f(x+\pi/|n|)\}e^{\mathbf{i}nx}\,dx\Big|\;. (6.5) For \delta>0 , define the L^{1} modulus of continuity by \omega_{\delta}(f)=\int_{-\pi}^{\pi}|f(x+\delta)-f(x)|\,dx . Lemma 6.10 . |\int_{-\pi}^{\pi}f(x)e^{\mathbf{i}nx}\,dx|\leq\frac{1}{2}\omega_{\pi/|n|}(f) for all |n|\geq 1 . Proof. Follows immediately from ( 6.5 ). ∎ Lemma 6.11 . Let n\in{\mathbb{Z}}\setminus\{0\} and \delta=\frac{2\pi}{|n|} . Let I be an interval of length |I|>\delta . Then, for h\colon(0,\infty)\to(0,\infty) non-increasing, \Big|\int_{I}f(x)e^{\mathbf{i}nx}\,dx\Big|\leq 2\delta|f|_{\infty;I}+h(\delta^{-1})\int_{I}|f|_{\mathcal{C}^{h}[x-\delta,x+\delta]}\,dx\;. Proof. We subdivide [-\pi,\pi) into intervals I_{k}=[k\delta,(k+1)\delta) . If I does not contain any I_{k} , then clearly |I|\leq 2\delta and |\int_{I}f(x)e^{\mathbf{i}nx}\,dx|\leq 2\delta|f|_{\infty;I} . Suppose now that I contains I_{k},\ldots,I_{m} . The integral of |f(x)| over I\setminus I_{k}\cup\ldots\cup I_{m} is also bounded by 2\delta|f|_{\infty;I} , so it suffices to bound \sum_{j=k}^{m}|\int_{I_{j}}f(x)e^{\mathbf{i}nx}\,dx| . Note that \int_{I_{j}}e^{\mathbf{i}nx}\,dx=0 . Therefore, since h is non-increasing, |\int_{I_{j}}f(x)e^{\mathbf{i}nx}\,dx|\leq\delta h(\delta^{-1})|f|_{\mathcal{C}^{h}[y_{j}-\delta,y_{j}+\delta]} for any point y_{j}\in I_{j} . There exist y_{j}\in I_{j} such that \delta|f|_{\mathcal{C}^{h}[y_{j}-\delta,y_{j}+\delta]}\leq\int_{I_{j}}|f|_{\mathcal{C}^{h}[x-\delta,x+\delta]}\,dx and therefore \sum_{j=k}^{m}|\int_{I_{j}}f(x)e^{\mathbf{i}nx}\,dx|\leq h(\delta^{-1})\sum_{j=k}^{m}\int_{I_{j}}|f|_{\mathcal{C}^{h}[x-\delta,x+\delta]}\,dx\leq h(\delta^{-1})\int_{I}|f|_{\mathcal{C}^{h}[x-\delta,x+\delta]}\,dx . ∎ Proof of Lemma 6.2 . Denote U=1/(1-P) , so that, by ( 2.2 ), we have U=\sum_{n=0}^{\infty}u_{n}e_{n} and u_{n}=\frac{1}{2\pi}\int_{-\pi}^{\pi}U(x)e^{-\mathbf{i}nx}\,dx . We first prove ( 6.2 ). By Lemma 6.10 it suffices to prove that, uniformly in \delta\in(0,1) , \omega_{\delta}(U)\lesssim\rho(1/\delta)\times\begin{cases}1\quad&\text{if }\alpha\in(0,\frac{1}{2})\;,\\ K(1/\delta)\quad&\text{if }\alpha=1/2\;,\\ \delta\rho(1/\delta)^{-2}\quad&\text{if }\alpha\in(\frac{1}{2},1)\;.\end{cases} (6.6) To this end, by Lemma 6.9 , |U(x)|=|1-P(x)|^{-1}\lesssim\rho(1/|x|)^{-1}\;, (6.7) and thus, since \alpha<1 , \int_{-2\delta}^{2\delta}|U(x+\delta)-U(x)|\,dx\lesssim\delta\rho(1/\delta)^{-1}\;, (6.8) which is smaller than the right-hand side of ( 6.6 ) by ( 6.1 ). For non-zero x\in[-\pi,\pi) , we claim that |U|_{\mathcal{C}^{\rho}([\frac{1}{2}x,\frac{3}{2}x])}\lesssim\rho(1/|x|)^{-2}\;. (6.9) Indeed, note that |f\circ g|_{\mathcal{C}^{\rho}}\leq|f^{\prime}|_{\infty}|g|_{\mathcal{C}^{\rho}} . We apply this with g\colon[\frac{1}{2}x,\frac{3}{2}x]\to{\mathbb{C}} defined by g=(1-P)\restriction_{[\frac{1}{2}x,\frac{3}{2}x]} and f(x)=1/x , for which f\circ g=U\restriction_{[\frac{1}{2}x,\frac{3}{2}x]} . Note that |g|\gtrsim\rho(1/|x|) by Lemma 6.9 and so |f^{\prime}|_{\infty;g[\frac{1}{2}x,\frac{3}{2}x]}\lesssim\rho(1/|x|)^{-2} . We thus obtain ( 6.9 ) since g\in\mathcal{C}^{\rho} by Lemma 6.8 . It follows that, for |x|>2\delta , |U(x)-U(x+\delta)|\lesssim\rho(1/\delta)\rho(1/|x|)^{-2}\;. (6.10) Therefore \int_{|x|>2\delta}|U(x+\delta)-U(x)|\,dx\lesssim\rho(1/\delta)\int_{2\delta}^{\pi}\rho(1/|x|)^{-2}\,dx\;, which, by Karamata’s theorem, is bounded from above by the right-hand side of ( 6.6 ). This completes the proof of ( 6.6 ) and thus of ( 6.2 ). We now prove ( 6.3 ). Let \ell\geq 1 . For 2\ell\leq n\lesssim\ell , ( 6.3 ) follows simply from ( 6.2 ) and the triangle inequality. Suppose henceforth that n\gg\ell and denote \delta=\pi/(n-\ell)\asymp n^{-1} . Denote F=1-e_{-\ell} and H=FU . Observe also that |F^{\prime}|\leq\ell , F(0)=0 and |F|\leq 2 . Furthermore, for all n\geq\ell , using ( 6.5 ), |u_{n-\ell}-u_{n}|=\frac{1}{2\pi}\Big|\int_{-\pi}^{\pi}He_{-n+\ell}\Big|=\frac{1}{4\pi}\Big|\int_{-\pi}^{\pi}\{H(x)-H(x+\delta)\}e^{-\mathbf{i}(n-\ell)x}\,dx\Big|\;. By ( 6.7 ), |U(x)|\lesssim\rho(1/|x|)^{-1} , hence H(x)\lesssim\ell|x|\rho(1/|x|)^{-1} , and thus by triangle inequality \int_{-2\delta}^{2\delta}|H(x+\delta)-H(x)|\,dx\lesssim\int_{0}^{2\delta}\ell x\rho(1/x)^{-1}\,dx\lesssim\frac{\ell\delta^{2}}{\rho(1/\delta)}\;. Remark that \frac{\ell\delta^{2}}{\rho(1/\delta)} is bounded by a multiple of the right-hand side of ( 6.3 ) (for the case \alpha=\frac{1}{2} , this uses L^{-2}\lesssim K ). We now consider |x|>2\delta and write H(x+\delta)-H(x)=\bigl(F(x+\delta)-F(x)\bigr)U(x)+F(x+\delta)\bigl(U(x+\delta)-U(x)\bigr)\;. (6.11) Using ( 6.10 ), the absolute value of the second term in ( 6.11 ) is bounded by a multiple of (\ell|x|\wedge 1)\rho(1/\delta)\rho(1/|x|)^{-2} , which, integrating over |x|>2\delta , contributes \int_{2\delta}^{1/\ell}\ell x\rho(1/\delta)\rho(1/x)^{-2}\,dx\leq\ell\rho(1/\delta)\int_{0}^{1/\ell}x\rho(1/x)^{-2}\,dx\lesssim\frac{\rho(1/\delta)}{\ell\rho(\ell)^{2}} plus \int_{1/\ell}^{\pi}\rho(1/\delta)\rho(1/x)^{-2}\,dx\lesssim\rho(1/\delta)\times\begin{cases}1\quad&\text{if }\alpha\in(0,\frac{1}{2})\;,\\ K(\ell)\quad&\text{if }\alpha=1/2\;,\\ \ell^{-1}\rho(\ell)^{-2}\quad&\text{if }\alpha\in(\frac{1}{2},1)\;.\end{cases} (6.12) Remark that \frac{\rho(1/\delta)}{\ell\rho(\ell)^{2}} is bounded by a multiple of the right-hand of ( 6.3 ), while ( 6.12 ) is precisely of this order. For the first term in ( 6.11 ), we divide the integration domain into |x|\in[2\delta,z] and |x|\in[z,\pi] for some z\geq 2\delta to be determined. For the first domain, we take absolute values and obtain, by ( 6.7 ), \int_{|x|\in[2\delta,z]}\bigl|\bigl(F(x+\delta)-F(x)\bigr)U(x)\bigr|\,dx\lesssim\int_{2\delta}^{z}\frac{\ell\delta}{\rho(x^{-1})}\,dx\lesssim\frac{\ell\delta z}{\rho(z^{-1})}\;. (6.13) For the second domain, we use instead \begin{split}\Big|\int_{|x|>z}\bigl(F(x+\delta)&-F(x)\bigr)U(x)e^{-\mathbf{i}(n-\ell)x}\,dx\Big|=\Big|\int_{|x|>z}e_{-\ell}(x)\bigl(e_{-\ell}(\delta)-1\bigr)U(x)e^{-\mathbf{i}(n-\ell)x}\,dx\Big|\\ &\leq 2\Big|\int_{|x|>z}U(x)e^{-\mathbf{i}nx}\,dx\Big|\lesssim\frac{\delta}{\rho(z^{-1})}+\int_{z}^{\pi}\frac{\rho(\delta^{-1})}{\rho(x^{-1})^{2}}\,dx\\ &\lesssim\rho(\delta^{-1})\times\begin{cases}1\quad&\text{if }\alpha\in(0,\frac{1}{2})\;,\\ K(1/z)\quad&\text{if }\alpha=1/2\;,\\ z\rho(z^{-1})^{-2}\quad&\text{if }\alpha\in(\frac{1}{2},1)\;.\end{cases}\end{split} (6.14) In the 2nd line above we used Lemma 6.11 and the fact that |U(x)|\lesssim\rho(z^{-1})^{-1} for |x|>z and |U|_{\mathcal{C}^{\rho}[x-\delta,x+\delta]}\lesssim\rho(|x|^{-1})^{-2} by ( 6.9 ). In the 3rd line we used that z\geq 2\delta , that 1/\rho^{2} is RV with index 2\alpha , and, for the case \alpha=\frac{1}{2} , the bound ( 6.1 ). For \alpha<\frac{1}{2} we take z=2\delta (so there is no first domain) and obtain a bound of order \rho(\delta^{-1}) . Alternatively, for \alpha<\frac{1}{2} the bound in ( 6.3 ) follows directly from ( 6.2 ). For \alpha=\frac{1}{2} we choose z^{-1}=\ell , so the second domain contributes \rho(\delta^{-1})K(\ell) and the first contributes \delta/\rho(\ell)\lesssim\rho(\delta^{-1})K(\ell) , where the final bound is due to ( 6.1 ) and \delta^{-1}\gg\ell . For \alpha>\frac{1}{2} we also choose z^{-1}=\ell . From \delta^{-1}\asymp n\gtrsim\ell we have \delta^{-1}\rho(\delta^{-1})\gtrsim\ell\rho(\ell) and thus the first domain contributes \frac{\ell\delta z}{\rho(z^{-1})}=\frac{\delta}{\rho(\ell)}\lesssim\frac{\rho(\delta^{-1})}{\ell\rho(\ell)^{2}}\;. The second domain contributes \frac{\rho(\delta^{-1})}{z^{-1}\rho(z^{-1})^{2}}=\frac{\rho(\delta^{-1})}{\ell\rho(\ell)^{2}}\;, as required. ∎ 6.2 Proof of ( 2.11 ) In addition to ( 2.8 ) and ( 2.1 ), we now assume the regularity bound ( 2.10 ). We first strengthen the bounds in Lemma 6.2 under these assumptions. Lemma 6.12 . Uniformly in n\geq 1 , u_{n}\lesssim\frac{1}{n\rho(n)}\;. (6.15) Furthermore, uniformly in \ell\geq 1 and n\geq 2\ell , |u_{n}-u_{n-\ell}|\lesssim\begin{cases}n^{-1}\rho(n)\rho(\ell)^{-2}&\alpha<1/2\;,\\ n^{-1}\rho(n)\ell\{K(n)-K(\ell)\}&\alpha=1/2\;,\\ n^{-2}\rho(n)^{-1}\ell&\alpha>1/2\;.\end{cases} (6.16) Remark 6.13 . If \alpha>\frac{1}{2} , then ( 6.16 ) for \ell\geq 1 follows from the case \ell=1 , i.e. |u_{n}-u_{n-1}|\lesssim n^{-2}\rho(n)^{-1} , and the triangle inequality. Note also that |u_{n}-u_{n-1}|\lesssim n^{-2}\rho(n)^{-1} and u_{n}\to 0 imply the bound ( 6.15 ). None of such implications hold in Lemma 6.2 or for the cases \alpha\leq\frac{1}{2} . Remark 6.14 . For n\geq 2\ell , K(n)-K(\ell)\gtrsim\int_{\ell}^{2\ell}\frac{1}{tL(t)^{2}}\,dt+\int_{n/2}^{n}\frac{1}{tL(t)^{2}}\,dt\gtrsim L(\ell)^{-2}+L(n)^{-2}\;. (6.17) Therefore, if \alpha=\frac{1}{2} , then n^{-1}\rho(n)\rho(\ell)^{-2}+n^{-2}\rho(n)^{-1}\ell\lesssim n^{-1}\rho(n)\ell\{K(n)-K(\ell)\} . That is, the bound in ( 6.16 ) is compatible with those for \alpha\neq\frac{1}{2} , and is possibly weaker. Using Lemma 6.12 , whose proof we postpone, we can complete the proof of Theorem 2.10 . Proof of Theorem 2.10 . We already proved ( 2.9 ). For n\lesssim\ell , the bound trivially follows from \|\mu_{k}\|_{\mathrm{TV}}\leq 1 , so we suppose henceforth that n\gg\ell . By ( 6.15 ) and Lemma 6.4 , we have \|\mu_{n+\ell}-\mu_{n}\|_{\mathrm{TV}}\lesssim\rho(\ell)^{-1}\rho(n)+\sum_{r=\ell}^{n+\ell}\rho(n+\ell-r)|u_{r}-u_{r-\ell}|\;. Since \rho(\ell)^{-1}\rho(n) is already the desired bound, it remains to bound the sum over r . Suppose first that \alpha>\frac{1}{2} . By Lemma 6.12 , we use the following bounds: • |u_{r}-u_{r-\ell}|\lesssim(r-\ell+1)^{-1}\rho(r-\ell)^{-1} for \ell\leq r<2\ell , • |u_{r}-u_{r-\ell}|\lesssim r^{-2}\rho(r)^{-1}\ell for 2\ell\leq r . The first case contributes, since n\gg\ell , \sum_{\ell\leq r<2\ell}\frac{\rho(n+\ell-r)}{(r-\ell+1)\rho(r-\ell)}\asymp\frac{\rho(n)}{\rho(\ell)} where we used that y^{-1}\rho(y)^{-1} is RV with index -1+\alpha>-1 . The second case contributes \sum_{2\ell\leq r\leq n+\ell}\frac{\ell\rho(n+\ell-r)}{r^{2}\rho(r)}\asymp\frac{\ell}{n}+\frac{\rho(n)}{\rho(\ell)}\asymp\frac{\rho(n)}{\rho(\ell)} where the first part of the middle term is due to n/2\leq r\leq n+\ell and the second is due to \ell\leq ry_{0} and x\in[y,Cy] . Since n\gg\ell , we restrict to n>C\ell . We also restrict to \ell>y_{0} , because \sum_{r=1}^{n}\frac{\rho(n-r)\rho(r)K(r)}{r}\lesssim\rho(n) . Then, for t\in[C^{i}\ell,C^{i+1}\ell] , we have \frac{L(\ell)}{L(t)}=\frac{L(\ell)}{L(C\ell)}\cdots\frac{L(C^{i}\ell)}{L(t)}\in[2^{-i-1},2^{i+1}] and therefore \int_{C^{i}\ell}^{C^{i+1}\ell}t^{-1}L(t)^{-2}\,dt\leq 4^{i+1}L(\ell)^{-2}\int_{C^{i}\ell}^{C^{i+1}\ell}t^{-1}\,dt=4^{i+1}L(\ell)^{-2}\log C\;. Then for C^{j}\ell\leq r0 , that a_{m}=\sum_{k=m}^{\infty}a_{k}-a_{k+1}=O(h(m)) , and similarly for m<0 . In general, the two limits \lim_{m\to\infty}a_{m} and \lim_{m\to-\infty}a_{m} exist but can be distinct. Define the distribution A=\sum_{m\in{\mathbb{Z}}}a_{m}e_{m} where we recall e_{m}(x)=e^{\mathbf{i}mx} for x\in{\mathbb{R}} . Lemma 6.16 . The function A\colon[-\pi,\pi)\setminus\{0\}\to{\mathbb{C}} satisfies |A(x)|\lesssim|x|^{-1}h(|x|^{-1}) for all x\in[-\pi,\pi)\setminus\{0\} and |A|_{\mathcal{C}^{h}(I)}\lesssim|x|^{-1} where I=(x/2,3x/2) . Proof. For x\in[-\pi,\pi)\setminus\{0\} , consider a smooth function \psi\colon{\mathbb{R}}\to{\mathbb{R}} which is 2\pi -periodic and equal to 1/(1-e_{-1}) on I . Note that |\psi(x)|\lesssim|x|^{-1} since |1-e_{-1}(x)|\gtrsim|x| . Let B=A(1-e_{-1}) . Then, as distributions on I , A=B\psi\;, where the product is well-defined since 1-e_{-1} and \psi are smooth, and B=\sum_{m\in{\mathbb{Z}}}(a_{m}-a_{m+1})e_{m} . It follows from ( 6.20 ) and Lemma 6.7 that |B|_{\mathcal{C}^{h}}<\infty . Furthermore, B(0)=\sum_{m\in{\mathbb{Z}}}a_{m}-a_{m+1}=0\;, where the series is absolutely convergent due to ( 6.20 ). Therefore |B(x)|\lesssim h(|x|^{-1}) and thus |A(x)|=|B(x)\psi(x)|\lesssim|x|^{-1}h(|x|^{-1})\;. To obtain an upper bound on |A|_{\mathcal{C}^{h}(I)} , remark that |\psi|_{C^{1}(I)}\lesssim|x|^{-2} . Therefore, for all y,z\in I , |\psi(y)-\psi(z)|\lesssim|y-z||x|^{-2}\lesssim\frac{h(|y-z|^{-1})|x|^{-1}}{h(|x|^{-1})} where in the final bound we used |y-z|^{-1}\gtrsim|x|^{-1} and that h(n)n is RV with index \beta+1>0 . Therefore A(z)-A(y)=B(z)(\psi(z)-\psi(y))+(B(z)-B(y))\psi(y)=O(h(|y-z|^{-1})|x|^{-1})\;.\qed Coming back to the proof of Lemma 6.12 , consider as in Section 6.1 the function P=\sum_{m=1}^{\infty}p_{m}e_{m} . Since ( 2.10 ) is equivalent to \sum_{m=n}^{2n-1}|p_{m}-p_{m+1}|\lesssim n^{-1}\rho(n) , \sum_{m\geq n}m|p_{m}-p_{m+1}|\lesssim\rho(n)\;. Combining with the upper bound in ( 2.8 ), it follows that a_{m}:=\mathbf{i}mp_{m} satisfies ( 6.20 ) with h=\rho . Therefore, since P^{\prime}=\sum_{m}a_{m}e_{m} , we obtain for x\in[-\pi,\pi)\setminus\{0\} by Lemma 6.16 \displaystyle|P^{\prime}(x)| \displaystyle\lesssim|x|^{-1}\rho(|x|^{-1})\;, (6.21) \displaystyle|P^{\prime}|_{\mathcal{C}^{\rho}([\frac{1}{2}x,\frac{3}{2}x])} \displaystyle\lesssim|x|^{-1}\;. (6.22) Remark 6.17 . If \rho(n)=n^{-\alpha} , then Lemmas 6.8 - 6.9 and the bounds ( 6.21 )-( 6.22 ) imply that 1-P behaves like |x|^{\alpha} in terms of regularity of its derivatives of order up to 1 . Proof of Lemma 6.12 . We first prove ( 6.15 ). As in the proof of Lemma 6.2 , define U=1/(1-P) , so that U=\sum_{n=0}^{\infty}u_{n}e_{n} . By Lemma 6.10 it suffices to prove that, uniformly in \delta\in(0,1) , \omega_{\delta}(U)\lesssim\frac{\delta}{\rho(\delta^{-1})}\;. (6.23) Recall ( 6.8 ): \int_{-2\delta}^{2\delta}|U(x+\delta)-U(x)|\,dx\lesssim\delta/\rho(\delta^{-1}) . By Lemma 6.9 and ( 6.21 ), |U^{\prime}(x)|\leq|P^{\prime}(x)|\,|1-P(x)|^{-2}\lesssim\frac{|x|^{-1}}{\rho(|x|^{-1})}\;. (6.24) The final expression, as a function of |x|^{-1} , is RV with index 1+\alpha>1 . Therefore, by Karamata’s theorem, \int_{|x|>2\delta}|U(x+\delta)-U(x)|\,dx\lesssim\frac{\delta}{\rho(\delta^{-1})}\;, which completes the proof of ( 6.23 ) and thus of ( 6.15 ). We now prove ( 6.16 ). Let \ell\geq 1 . If 2\ell\leq n\lesssim\ell , then ( 6.16 ) follows simply from ( 6.15 ), the triangle inequality, and the fact that K(n)-K(\ell)\asymp L(n)^{-2} in this case. Suppose henceforth that n\gg\ell . Following notation from the proof of Lemma 6.2 , denote F=1-e_{-\ell} , U=1/(1-P) and H=FU . Define \delta=\pi/(n-\ell)\asymp n^{-1} . Then, by ( 6.5 ), (n-\ell)|u_{n-\ell}-u_{n}|=\frac{1}{2\pi}\Big|\int_{-\pi}^{\pi}H^{\prime}e_{-n+\ell}\Big|=\frac{1}{4\pi}\Big|\int_{-\pi}^{\pi}\{H^{\prime}(x)-H^{\prime}(x+\delta)\}e^{-\mathbf{i}(n-\ell)x}\,dx\Big|\;. (6.25) To estimate the final integral, we write H^{\prime}(x)=\frac{-\mathbf{i}\ell e^{-\mathbf{i}\ell x}}{(1-P)(x)}+\frac{(1-e^{-\mathbf{i}\ell x})}{(1-P)^{2}(x)}P^{\prime}(x)=-\mathbf{i}A(x)+B(x)P^{\prime}(x)\;. (6.26) Note that, by Lemma 6.9 , |A(x)|\lesssim\frac{\ell}{\rho(|x|^{-1})}\;, |B(x)|\lesssim\frac{\ell|x|\wedge 1}{\rho(|x|^{-1})^{2}}\;. (6.27) Therefore, using ( 6.21 ), |H^{\prime}(x)|\lesssim\frac{\ell}{\rho(|x|^{-1})}+\frac{\ell|x|\wedge 1}{|x|\rho(|x|^{-1})}\lesssim\frac{\ell}{\rho(|x|^{-1})} and thus, since \rho is RV with index -\alpha>-1 , \int_{-2\delta}^{2\delta}|H^{\prime}(x+\delta)-H^{\prime}(x)|\,dx\lesssim\int_{-2\delta}^{2\delta}\frac{\ell}{\rho(|x|^{-1})}\,dx\lesssim\frac{\ell\delta}{\rho(\delta^{-1})}\;. Suppose now that |x|>2\delta . To handle the second term in ( 6.26 ), by ( 6.21 ) and Lemma 6.9 , |B^{\prime}(x)|\lesssim\frac{\ell}{\rho(|x|^{-1})^{2}}+\frac{\ell|x|\wedge 1}{|x|\rho(|x|^{-1})^{2}}\lesssim\frac{\ell}{\rho(|x|^{-1})^{2}}\;. Therefore, by ( 6.21 )-( 6.22 ) and ( 6.27 ), |B(x+\delta)P^{\prime}(x+\delta)-B(x)P^{\prime}(x)|\lesssim\frac{\delta\ell}{|x|\rho(|x|^{-1})}+\frac{(\ell|x|\wedge 1)\rho(\delta^{-1})}{|x|\rho(|x|^{-1})^{2}}\;. The integral of the first term over |x|>2\delta is \ell\delta/\rho(\delta^{-1}) as earlier, while the integral of the second term over |x|>2\delta is \int_{1/\ell}^{\pi}\frac{\rho(\delta^{-1})}{|x|\rho(|x|^{-1})^{2}}\,dx+\int_{2\delta}^{1/\ell}\frac{\ell\rho(\delta^{-1})}{\rho(|x|^{-1})^{2}}\,dx\;. The first integral is proportional to \rho(\delta^{-1})/\rho(\ell)^{2} . The second integral, recalling that \rho(z)=z^{-\alpha}L(z) and \delta<\frac{1}{4\ell} , is equal to \ell\rho(\delta^{-1})\int_{\ell}^{\frac{1}{2\delta}}\rho(y)^{-2}y^{-2}\,dy\asymp\begin{cases}\rho(\delta^{-1})\rho(\ell)^{-2}&\alpha<1/2\;,\\ \ell\rho(\delta^{-1})\{K(\delta^{-1})-K(\ell)\}&\alpha=1/2\;,\\ \ell\delta\rho(\delta^{-1})^{-1}&\alpha>1/2\;.\end{cases} (6.28) To handle the first term in ( 6.26 ), we write \displaystyle A(x+\delta)-A(x) \displaystyle=\ell e_{-\ell}(x+\delta)\bigl(U(x+\delta)-U(x)\bigr)+\ell\bigl(e_{-\ell}(x+\delta)-e_{-\ell}(x)\bigr)U(x) \displaystyle=A_{1}(x,\delta)+A_{2}(x,\delta)\;. By ( 6.24 ), |U^{\prime}(x)|\lesssim|x|^{-1}\rho(|x|^{-1})^{-1} , hence |U(x+\delta)-U(x)|\lesssim\delta|x|^{-1}\rho(|x|^{-1})^{-1} , and thus \int_{|x|>2\delta}|A_{1}(x,\delta)|\,dx\lesssim\frac{\ell\delta}{\rho(\delta^{-1})}\;. To handle A_{2}(x,\delta)=\ell\bigl(F(x)-F(x+\delta)\bigr)U(x) , note that, for z\in[2\delta,\pi] , by ( 6.13 ), \int_{|x|\in[2\delta,z]}|A_{2}(x,\delta)|\,dx\lesssim\frac{\ell^{2}\delta z}{\rho(z^{-1})}\;. (6.29) Furthermore, similar to ( 6.14 ), \begin{split}\Big|\int_{|x|>z}A_{2}(x,\delta)e^{-\mathbf{i}(n-\ell)x}\,dx\Big|&\leq 2\ell\Big|\int_{|x|>z}U(x)e^{-\mathbf{i}(n-\ell)x}\,dx\Big|\\ &\lesssim\frac{\ell\delta}{\rho(z^{-1})}+\int_{z}^{\pi}\frac{\ell\delta}{x\rho(x^{-1})}\,dx\lesssim\frac{\ell\delta}{\rho(z^{-1})}\;,\end{split} (6.30) where in the 2nd bound we used Lemma 6.11 with h(y)=y^{-1} and ( 6.24 ). Taking z=\ell^{-1}\geq 2\delta , both ( 6.29 ) and ( 6.30 ) yield a contribution of order \ell\delta\rho(\ell)^{-1}\lesssim\ell\delta\rho(\delta^{-1})^{-1} . Finally, note that \ell\delta/\rho(\delta^{-1}) and \rho(\delta^{-1})/\rho(\ell)^{2} , for any \alpha\in(0,1) , are bounded by a multiple of ( 6.28 ) (for \alpha=\frac{1}{2} we use K(\delta^{-1})-K(\ell)\gtrsim L(\delta^{-1})^{-2}+L(\ell)^{-2} since \delta^{-1}\gg\ell , as in ( 6.17 )). Therefore ( 6.25 ) is bounded by the right-hand side of ( 6.28 ), concluding the proof. ∎ Appendix A Memory loss for positive recurrent Markov chains Here we justify ( 1.2 ). We use notation from Section 2.1 , in particular the sequences u_{n}=\P(X_{n}=0\mid X_{0}=0) and z_{n}=\sum_{k>n}p_{k} . We start by recalling the following special case of [ MO14 , Theorem 2.2] : Theorem A.1 . Suppose that \alpha>1 . If z_{n}\lesssim n^{-\alpha} , then |u_{n}-u_{n+1}|\lesssim n^{-\alpha} . To prove ( 1.2 ), consider \alpha>1 . It suffices to consider \ell=1 and apply the triangle inequality. By ( 2.3 ) and Theorem A.1 , \displaystyle\|P^{n+1}\delta_{0}-P^{n}\delta_{0}\|_{\mathrm{TV}} \displaystyle=z_{n+1}+\sum_{m=0}^{n}|u_{n+1-m}-u_{n-m}|z_{m}\ \displaystyle\lesssim n^{-\alpha}+\sum_{m=0}^{n}(n-m+1)^{-\alpha}(m+1)^{-\alpha}\lesssim n^{-\alpha}\;, as desired. Remark A.2 . The above proof of ( 1.2 ) relies on Theorem A.1 , the proof of which in [ MO14 ] is based on a generalised Wiener lemma. There are other ways to prove ( 1.2 ), for example we were able to adapt [ Lin02 , Theorem 4.2, p27] , which essentially contains ( 1.2 ) under the strong moment assumption \sum_{n\geq 1}n^{-\alpha}p_{n}<\infty .