# Cover times in dynamical systems

Natalia Jurga  Mathematical Institute
University of St Andrews
North Haugh
St Andrews
KY16 9SS
Scotland<EMAIL_ADDRESS>https://nataliajurga.wordpress.com/ and  Mike
Todd  Mathematical Institute
University of St Andrews
North Haugh
St Andrews
KY16 9SS
Scotland<EMAIL_ADDRESS>http://www.mcs.st-and.ac.uk/ miket/

(Date: 27th August 2024)

###### Abstract.

We introduce the notion of cover time to dynamical systems. This quantifies
the rate at which orbits become dense in the state space and can be viewed as
a global, rather than the more standard local, notion of recurrence for a
system. Using transfer operator tools for systems with holes and inducing
techniques, we obtain an asymptotic formula for the expected cover time in
terms of the decay rate of the measure of the ball of minimum measure. We
apply this to a wide class of uniformly hyperbolic and non-uniformly
hyperbolic interval maps, including the Gauss map and Manneville-Pomeau maps.

###### Key words and phrases:

Cover time, Hitting time

###### 2020 Mathematics Subject Classification:

37A25, 37E05, 37C30, 37D25, 37D35

NJ was supported by an EPSRC Standard Grant (EP/R015104/1)

##  1\. Introduction and summary of results

Let $f:X\to X$ be a map of a metric space $(X,d)$ equipped with an ergodic
probability measure $\mu$.111Note that $X$ may be an invariant set of a larger
space. In this article we introduce and study the _cover time_ of the system
$(f,\mu)$ which, roughly speaking, quantifies the rate at which orbits become
dense in $X$. More precisely, given $\delta>0$ we define the $\delta$-covering
time $\tau_{\delta}:X\to{\mathbb{N}}\cup\\{\infty\\}$,

$\tau_{\delta}(x):=\inf\left\\{n\geqslant
1\;:\;\\{x,f(x),\ldots,f^{n}(x)\\}\;\textnormal{is $\delta$-dense in
$X$}\right\\}$ (1.1)

where we say that a subset $Z^{\prime}\subset Z$ is $\delta$-dense in $Z$ if
for all $x\in Z$ there exists $x^{\prime}\in Z^{\prime}$ such that
$d(x,x^{\prime})\leqslant\delta$. We will be interested in the asymptotic
behaviour of the expected cover time with respect to $\mu$,
$\mathbb{E}_{\mu}(\tau_{\delta})$ as $\delta\to 0$.

In probability, analogous notions to the cover time have a rich history of
study, such as in the setting of random walks on graphs [Al1, L, DLP] and
Markov chains [LP], as well as being extensively studied in stochastic
geometry [F, J, P, Al2]. Moreover, applications are numerous and include
wireless communications [BB] and genomics [ARS]. However the cover time,
despite being a very natural dynamical notion to study in connection with
other better understood notions of recurrence such as hitting and return
times, has not yet been addressed in the field of dynamical systems. We
briefly describe an application which illustrates the utility of obtaining
estimates on the cover time. Suppose $f:\Lambda\to\Lambda$ is an expanding
repeller. Then the expected cover time $N=\mathbb{E}_{\mu}(\tau_{\delta})$
describes how long one would should expect to wait for an orbit segment
$\\{x,f(x),\ldots,f^{N}(x)\\}$ to produce a $\delta$-approximation of the
repeller, which would be useful for an efficient computation of its image.

It is an interesting open programme to investigate what types of asymptotic
behaviour are feasible for the expected cover time and to characterise these
in terms of the basic properties of the dynamical system. We point to similar
lines of research in the setting of random walks on graphs, such as
investigation into general lower and upper bounds on the expected cover time
in terms of the number of vertices in the graph and a conjecture that the
smallest expected cover time should be attained by complete graphs [L]. In
this paper we make fundamental progress towards this general goal by obtaining
an asymptotic formula for the expected cover time for a wide class of
uniformly and non-uniformly hyperbolic systems.

Define

$M_{\mu}(\delta)=\min_{x\in\mathrm{supp}(\mu)}\mu(B(x,\delta))$ (1.2)

where $B(x,\delta)$ denotes an open ball, noting that the minimum exists by
compactness of $\mathrm{supp}(\mu)$ and lower semicontinuity of
$x\mapsto\mu(B(x,\delta))$. For a wide class of one-dimensional systems we
will show that $\mathbb{E}_{\mu}(\tau_{\delta})$ scales roughly like
$M_{\mu}(\delta)^{-1}$ as $\delta\to 0$. In particular, if we let
$\dim_{\textup{M}}\mu$ denote the Minkowski dimension of $\mu$

$\dim_{\textup{M}}\mu=\lim_{\delta\to 0}\frac{\log
M_{\delta}(\mu)}{\log\delta},$ (1.3)

which was introduced in [FFK]222This differs from the definition for the
Minkowski dimension which was given in [FFK], but the proof that (1.3) is an
equivalent characterisation can be found in [BJK, Lemma 1.1]. Note that the
limit in (1.3) will exist for the measures considered in this paper, however
this is not the general case. We also note that this definition does not agree
with the definition of the Minkowski dimension given by Pesin [P, §7] and that
some authors would refer to 1.3 as the $L^{-\infty}$ dimension (see e.g. [FFK,
Proposition 4.2]). then our main result says that if
$\dim_{\textup{M}}\mu<\infty$ then $\mathbb{E}_{\mu}(\tau_{\delta})$ scales
roughly like $\delta^{-\dim_{\textup{M}}\mu}$ as $\delta\to 0$. This is in
correspondence with the asymptotic behaviour of the expected hitting time
$\mathbb{E}_{\mu}(\tau_{B(x,\delta)})$ (see (1.4)) to a shrinking ball centred
at some $x\in X$ which grows like $O(\delta^{-D_{\mu}(x)})$ as $\delta\to 0$
where $D_{\mu}(x)$ denotes the local dimension of $\mu$ at $x$. In other
words, while hitting times are governed by _local_ scaling properties of the
measure $\mu$, cover times are governed by the scaling properties of the
(globally determined) ball of minimum measure. Our setup also gives rise to
natural examples of systems which cover the state space at a rate slower than
$\delta^{-\alpha}$ (for any $\alpha>0$), namely where the expected cover time
$\mathbb{E}_{\mu}(\tau_{\delta})$ has an exponential dependence on $1/\delta$,
see §7. We obtain more precise bounds on $\mathbb{E}_{\mu}(\tau_{\delta})$,
which can be found in Theorems 2.1 and 2.2 in the uniformly hyperbolic case
and in Theorems 6.1 and 6.2 in the non-uniformly hyperbolic case. We remark
that the subexponential terms in the asymptotic expression for the expected
cover time are interesting since they capture how nuanced information about
the system plays a role in the expected cover time, such as how many balls of
radius $\delta$ and measure $\approx M_{\mu}(\delta)$ there are.

In [JM, BJK] the cover time of the chaos game was studied, which is a random
algorithm that was introduced by Barnsley [Ba, Chapter 3] for constructing the
attractors of iterated function systems. Assuming the iterated function system
satisfies an appropriate separation condition, this is analogous to studying
$\mathbb{E}_{\mu}(\tau_{\delta})$ for a system $(f,\mu)$, where $f$ is
necessarily a full and finite branched uniformly expanding map (constructed
using the inverses of the contractions belonging to the iterated function
system) and $\mu$ is the stationary measure associated to the chaos game. In
the current paper we study the cover time from a dynamical viewpoint and in
particular we study systems which are well beyond the scope of [BJK] such as
systems which are non-uniformly hyperbolic (subexponentially mixing), are not
full branched, or have infinitely many branches. In particular, our results
give partial answers to [BJK, Questions 6.3 and 6.4].

The cover time $\tau_{\delta}$ is closely related to the hitting time
$\tau_{U}:X\to{\mathbb{N}}\cup\\{\infty\\}$

$\tau_{U}(x)=\inf\\{n\geqslant 1:f^{n}(x)\in U\\}$ (1.4)

for $U=B(x,\delta)$ where $x\in X$. For background on hitting time statistics
in dynamical systems see for example [Sau], [LFF+, Chapter 5]. In the
uniformly hyperbolic case, a key tool in this paper will be to adapt the tools
based on the spectral theory of transfer operators for dynamical systems with
a family of holes shrinking to a point [BDT], to instead give bounds on the
expected hitting time $\mathbb{E}_{\mu}(\tau_{U})$ over a family
${\mathcal{U}}_{\delta}$ of holes $U=B(x,\delta)$ centred at $x\in X$ and
which cover $X$. We have to do this in a uniform way, which is a significant
technical challenge, particularly when dealing with the ‘short returns’ which
requires a new symbolic argument given in §3, which restricts the geometry of
our setup (see (2.10) below). Following this, we will adapt an approach of
Matthews [M], based on randomising the order in which balls $U$ are visited,
which will allow us to express the expected cover time in terms of
$\max_{U}\mathbb{E}_{\mu}(\tau_{U})$, where the maximum is taken over balls
$U=B(x,\delta)$ with $x\in X$. Finally, given a non-uniformly hyperbolic
system $(f,\mu)$ we will consider a suitable first return map $F=f^{\tau_{Y}}$
which is uniformly hyperbolic, and show that the cover time for the original
system $(f,\mu)$ can be estimated in terms of the cover time of the induced
system $(F,\frac{1}{\mu(Y)}\mu|_{Y})$.

Notation. We say $x=O(y)$ if there exists $C>0$ such that $|x|\leqslant C|y|$.
We will also allow the constants $C,c>0$ to take different values throughout
the paper: they will indicate that the bounds are uniform in the context in
which they are used.

Organisation. In §2 we state the main theorems in the uniformly expanding case
(Theorems 2.1 and 2.2) and study the transfer operators which will be used to
obtain estimates on the expected hitting times in this setting. In §3 we
obtain estimates on expected return times, which are then used in §4 to obtain
estimates on expected hitting times. In §5 we prove Theorems 2.1 and 2.2 by
obtaining a dynamical generalisation of Matthews’ approach [M] to express the
expected cover time in terms of the expected hitting times. In §6 we state the
main theorems in the non-uniformly expanding case (Theorems 6.1 and 6.2) and
use an inducing argument to prove it. In § 7 we give applications of our
results, both in the uniformly hyperbolic and non-uniformly hyperbolic cases.
This includes applications to Gibbs-Markov maps, the Gauss map and Manneville-
Pomeau systems as well as examples of slowly covering systems. We postpone the
proofs of Propositions 2.3 and 2.4 to the appendix: these guarantee that for
all $\delta$ sufficiently small, we can find a family of balls of radius
roughly $\delta$, each of whose expected hitting time can be studied by our
transfer operator approach.

##  2\. Uniformly hyperbolic maps and transfer operators

In this section we introduce the class of uniformly expanding maps which will
be studied and state the main results in this setting. Furthermore we
introduce the transfer operators which will be used to estimate hitting times.
We establish the uniform spectral properties for these operators which will be
required to obtain uniform estimates on expected hitting times. From here on,
all of our dynamical systems will be interval maps, which we formalise next.

Let $I\subset{\mathbb{R}}$ be an interval and
$\mathcal{Z}=\\{Z_{i}\\}_{i\in\mathcal{I}}$ be a finite or countable
collection of subintervals of $I$ with disjoint interiors. Let
$f:\bigcup_{n\in\mathcal{I}}Z_{n}\to I$ be continuous and strictly monotonic
on each $Z_{n}$. We denote $f_{i}:=f|_{Z_{i}}$. We call an interval $H\subset
I$ on which $f$ is not defined a _hole_ 333These initially refer to the holes
present in the original dynamics, but later this idea will be also used when
we will investigate hitting times via an open dynamical systems perspective,
where an extra hole is introduced., for example when there is a gap between
$Z_{i}$s. Write $D=I\setminus\bigcup_{i}Z_{i}$. We denote

$\Lambda:=\left\\{x\in I:f^{k}(x)\in\bigcup_{n\in\mathcal{I}}Z_{n}\text{ for
all }k\geqslant 0\right\\}$

to be the repeller of $f$ and study the dynamical system
$f:\Lambda\to\Lambda$. In our notation we may sometimes suppress the fact that
we are restricting the dynamics to $\Lambda$, for instance by writing $f(U)$
for some $U$ which is not a subset of $\Lambda$ (for example $U$ may be an
interval, while $\Lambda$ may be a topological Cantor set); this is implicitly
understood as $f(U)=f(\Lambda\cap U)$. Note that in the case that
$I\setminus\bigcup_{n\in\mathcal{I}}\overline{Z_{n}}=\emptyset$ (i.e. there
are no holes) then we can take $\Lambda=I$. Let $\mathcal{Z}^{n}$ be the set
_$n$ -cylinders_, i.e., of maximal intervals $Z$ of $I$ such that
$f^{k}(Z)\subset Z_{i_{k}}$ for some $Z_{i_{k}}\in\mathcal{Z}$ for
$k=0,\ldots,n-1$.

We now outline our basic assumptions on our map $f$ and invariant measure
$\mu$.

###  2.1. Basic assumptions on $f$ and $\mu$

We assume there exists a nonatomic Borel probability measure $m$ such that
$m(D)=0$ and $m$ is conformal444From a thermodynamic formalism point of view,
our assumptions imply that the pressure of $\phi$ is zero. with respect to a
potential $\phi:\Lambda\to{\mathbb{R}}$, i.e. $\frac{dm}{d(m\circ
f)}=e^{\phi}$. We set $\phi|_{D}=-\infty$ and write
$S_{n}\phi=\sum_{i=0}^{n-1}\phi\circ f^{i}$. Let

${\mathcal{L}}\psi(x):=\sum_{y\in f^{-1}x}\psi(y)e^{\phi(y)}$ (2.1)

for $\psi\in L^{1}(\Lambda,m)$, (we will actually consider $\mathcal{L}$
acting on functions of bounded variation, see Section 2.6). We assume $\phi$
satisfies the following regularity properties as in [BDT, Section 2]:

  1. (a1)

$\exists C_{d}>0$ such that $|e^{S_{n}\phi(x)-S_{n}\phi(y)}-1|\leqslant
C_{d}|f^{n}(x)-f^{n}(y)|$ whenever $f^{i}(x),f^{i}(y)$ lie in the same element
of ${\mathcal{Z}}$ for each $i=0,1,\ldots,n-1$;

  2. (a2)

$\exists n_{0}\in{\mathbb{N}}$ such that
$\sup_{\Lambda}e^{S_{n_{0}}\phi}<\inf_{\Lambda\setminus
D}{\mathcal{L}}^{n_{0}}1$;

  3. (a3)

For each $x\in\Lambda$ and $\delta>0$ such that $J=B(x,\delta)$ has the
property that $J\cap D=\emptyset$, $\exists N=N(J)$ such that
$\inf_{\Lambda\setminus D}{\mathcal{L}}^{N}{\mathbbm{1}}_{J\cap\Lambda}>0$.

Note that (a3) implies $\mbox{\rm supp}(m)=\Lambda$. By conformality of $m$,
$\int\mathcal{L}^{n}1dm=\int 1dm=1$ so that $\inf_{\Lambda\setminus
D}\mathcal{L}^{n}1\leqslant 1$ for all $n\in{\mathbb{N}}$. Hence by (a2),
$\sup_{\Lambda}e^{S_{n_{0}}\phi}<1$. By this and conformality of $m$:

$\text{there exist }C>0,\omega>0\text{ such that any $n$-cylinder has measure
}\leqslant Ce^{-\omega n}.$ (2.2)

Since $\sup_{\Lambda}e^{S_{n_{0}}\phi}<1$ and since
$\sup_{\Lambda}e^{S_{n}\phi}$ is submultiplicative, we have that

$\sum_{n=1}^{\infty}\sup_{\Lambda}e^{S_{n}\phi}<\infty.$ (2.3)

By the same reasoning

$\exists n_{1}\in{\mathbb{N}}\;\textnormal{such
that}\;(2n_{1}+5)(C_{d}+1)\sup_{\Lambda}e^{S_{n_{1}}\phi}<1.$ (2.4)

We will also assume that

  1. (a4)

$\exists c_{m}>0$ such that
$\inf_{Z\in{\mathcal{Z}}^{n_{1}}}m(f^{n_{1}}(Z))\geqslant c_{m}$.

Along with the cylinder structure, this implies that for all $1\leqslant
i\leqslant n_{1}$,

$\inf_{Z\in{\mathcal{Z}}^{i}}m(f^{i}(Z))\geqslant\inf_{Z\in{\mathcal{Z}}^{n_{1}}}m(f^{n_{1}}(Z))\geqslant
c_{m}.$ (2.5)

By (a1), $\sup_{Z}e^{\phi}\leqslant(1+C_{d})m(Z)/m(f(Z))$ so applying (2.5)
with $i=1$ yields

$\sum_{Z\in{\mathcal{Z}}}\sup_{Z}e^{\phi}\leqslant(1+C_{d})\sum_{Z\in{\mathcal{Z}}}\frac{m(Z)}{m(f(Z))}\leqslant(1+C_{d})c_{m}^{-1}<\infty.$
(2.6)

Under (a1)-(a4), $\mathcal{L}$ admits a unique invariant measure $\mu$ which
is absolutely continuous with respect to $m$ and whose density $g$ is bounded
away from 0 and of bounded variation. By this and by conformality of $m$,
(2.3) implies

$K:=1+\sum_{n=1}^{\infty}\sup_{Z\in{\mathcal{Z}}^{n}}\mu(Z)<\infty.$ (2.7)

It will sometimes be more convenient to work with the symbolic coding of $f$.
Recall that the index set $\mathcal{I}$ labels the intervals of monotonicity
$\\{Z_{i}\\}_{i\in\mathcal{I}}$ for $f$. Let
$\Sigma\subset\mathcal{I}^{\mathbb{N}}$ be the subshift given by the set of
sequences $\mathbf{i}=(i_{0},i_{1},\ldots)\in\mathcal{I}^{{\mathbb{N}}_{0}}$
for which there exists an $x\in\Lambda$ such that $f^{n}(x)\in Z_{i_{n}}$ for
all $n\in{\mathbb{N}}_{0}$. Define the projection $\Pi:\Sigma\to I$ as

$\Pi(i_{0},i_{1},\cdots):=\lim_{n\to\infty}f_{i_{0}}^{-1}\circ\cdots\circ
f_{i_{n-1}}^{-1}(I),$

i.e. $\Pi(\mathbf{i})=x$. Then $f\circ\Pi=\Pi\circ\sigma$ where
$\sigma:\Sigma\to\Sigma$ is the left shift map. We let $\Sigma_{n}$ denote the
set of all words of length $n$ in $\Sigma$ and $\Sigma^{*}$ denote the set of
all finite words in $\Sigma$. Given $w\in\Sigma^{*}$ we write
$[w]:=\\{\mathbf{i}\in\Sigma:\mathbf{i}|n=w\\}$ where
$\mathbf{i}|n=(i_{0},\ldots,i_{n-1})$ if
$\mathbf{i}=(i_{n})_{n\in{\mathbb{N}}_{0}}$ (sometimes for brevity we will
write $w=i_{0}\ldots i_{n-1}$). We write $\tilde{\mu}$ to be the measure on
$\Sigma$ such that $\mu=\Pi_{*}\tilde{\mu}$.

We will require two additional assumptions on $\tilde{\mu}$:

  1. (a5)

$\tilde{\mu}$ is _quasi-Bernoulli_ ; i.e. there exists $C_{*}>1$ such that for
all finite words $\mathbf{i},\mathbf{j}\in\Sigma^{*}$,
$C_{*}^{-1}\tilde{\mu}([\mathbf{i}])\tilde{\mu}([\mathbf{j}])\leqslant\tilde{\mu}([\mathbf{i}\mathbf{j}])\leqslant
C_{*}\tilde{\mu}([\mathbf{i}])\tilde{\mu}([\mathbf{j}])$;

  2. (a6)

$\tilde{\mu}$ is _$\psi$ -mixing_, i.e.

$\left|\frac{\tilde{\mu}\left(\cup[x_{0},\ldots,x_{i-1},y_{0},\ldots,y_{j-1},z_{0},\ldots,z_{\ell-1}]\right)}{\tilde{\mu}\left([x_{0},\ldots,x_{i-1}]\right)\tilde{\mu}\left([z_{0},\ldots,z_{\ell-1}]\right)}-1\right|\leqslant\gamma(j)$

where the union is taken over all words $y_{0}\ldots y_{j-1}$ of length $j$
such that
$(x_{0},\ldots,x_{i-1},y_{0},\ldots,y_{j-1},z_{0},\ldots,z_{\ell-1})\in\Sigma_{i+j+\ell}$,
and $\gamma(j)\to 0$ as $j\to\infty$.

###  2.2. Gibbs-Markov maps

In the case where $f:\Lambda\to\Lambda$ is Markov, i.e. for each
$Z\in{\mathcal{Z}}$, $f(Z)$ is a union of elements of ${\mathcal{Z}}$, then
the class of maps satisfying (a1)-(a6) is precisely the class of Gibbs-Markov
maps with the big images and pre-images (BIP) property. These maps and their
properties are discussed in more detail in [BDT, Section 2.6.2], but we give a
brief account here.

We say that $f$ satisfies the _big images and pre-images (BIP) property_ if
there exists a finite set $\\{Z_{j}\\}_{j\in\mathcal{J}}\subset{\mathcal{Z}}$
such that $\forall Z\in{\mathcal{Z}}$, $\exists j,k\in\mathcal{J}$ such that
$f(Z_{j})\supseteq Z$ and $f(Z)\supseteq Z_{k}$. We also assume that
$|Df|\geqslant\gamma^{-1}>1$ on each $Z\in{\mathcal{Z}}$. We say that an
invariant measure $\mu$ (or $\tilde{\mu}$) is _Gibbs_ if there exists a
Lipschitz continuous potential $\phi$ (i.e., with some uniform Lipschitz
constants such that on each $Z\in{\mathcal{Z}}$, $\phi$ is Lipschitz) and
constants $K,P$ such that for all $i_{0},\ldots,i_{n-1}\in\Sigma_{n}$ and
$\mathbf{i}\in[i_{0},\ldots,i_{n-1}]$,

$K^{-1}\leqslant\frac{\tilde{\mu}([i_{0},\ldots,i_{n-1}])}{e^{S_{n}\phi(\Pi(\mathbf{i}))+nP}}\leqslant
K.$

We say that $(f,\mu)$ is Gibbs-Markov with BIP if $f$ is Markov and satisfies
BIP and $\mu$ is Gibbs. One can readily check that such maps satisfy
(a1)-(a6). Indeed, as in [BDT, Section 2.6.2], these maps satisfy (a1)-(a3).
Also (a4) follows from the big images property and Markov property; (a5)
follows because Gibbs measures $\tilde{\mu}$ are quasi-Bernoulli. Finally (a6)
holds since Gibbs measures $\tilde{\mu}$ are $\psi$-mixing [Br].

On the other hand, suppose $f$ is Markov and satisfies (a1)-(a4). Then $\mu$
is necessarily a Gibbs measure. Moreover by [S2], $f$ must satisfy BIP. In
other words, the class of Markov maps satisfying (a1)-(a6) coincides with the
class of Gibbs-Markov map with BIP. We call $f_{i}=f|_{Z_{i}}$ the _branch_ of
$f$ at $Z_{i}$; if $f(Z_{i})=I$ then we say that $f$ has a _full branch_ on
$Z_{i}$. The simplest BIP examples are when all branches of $f$ are full.

###  2.3. Other assumptions on $f$ and $m$.

Before we state our main theorems, we will need to introduce further
assumptions on the system.

Firstly, we assume that for some constant $C_{m}<\infty$ and $s>0$,

$m(U)\leqslant C_{m}\mbox{\rm diam}(U)^{s}\hskip 14.22636pt\textnormal{for all
intervals $U\subset I$}.$ (2.8)

We will also require the derivatives of iterates of $f$ to satisfy bounded
distortion: there exists a constant $C_{bd}>0$ such that for all
$x,y\in\Lambda$ for which $f^{i}(x),f^{i}(y)$ are in the same cylinder $Z$ for
each $0\leqslant i\leqslant n-1$ then

$C_{bd}^{-1}\leqslant\frac{|(f^{i})^{\prime}(x)|}{|(f^{i})^{\prime}(y)|}\leqslant
C_{bd}.$ (2.9)

Since we are in the uniformly hyperbolic setting, in the case that $f$ has
finitely many $C^{1+\alpha}$ branches, $f$ satisfies (2.9). Similarly, in the
case that $f$ has infinitely many $C^{1+\alpha}$ branches and there is a
uniform upper bound bound on the Hölder constants associated to the first
order derivative of each branch, $f$ also satisfies (2.9).

Next, in order that $f:I\to I$ can be sufficiently well approximated by the
symbolic representation of the system, we require adjacent cylinders to be
comparable. That is there is $C>0$ such that given
$Z,Z^{\prime}\in{\mathcal{Z}}^{n}$ where $Z,Z^{\prime}\subset
Z_{n-1}\in{\mathcal{Z}}^{n-1}$ which are _adjacent_ , meaning that there is an
interval $A\subset Z_{n-1}$ such that $Z$ and $Z^{\prime}$ are the only
elements of ${\mathcal{Z}}^{n}$ intersecting $A$,

$\frac{1}{C}\leqslant\frac{\mu(Z)}{\mu(Z^{\prime})}\leqslant C.$ (2.10)

Note that here we are assuming that given $Z_{n-1}\in{\mathcal{Z}}^{n-1}$,
each $Z\in{\mathcal{Z}}^{n}$ in $Z_{n-1}$ has an adjacent
$Z^{\prime}\in{\mathcal{Z}}^{n}$ in $Z_{n-1}$, which implies that if domains
of ${\mathcal{Z}}^{n}$ accumulate in $Z_{n-1}\in{\mathcal{Z}}^{n-1}$, then
this must occur at the boundary of $Z_{n-1}$. Observe that it is sufficient to
check this assumption for elements of ${\mathcal{Z}}^{1}$, where $I$ is the
corresponding element of ${\mathcal{Z}}^{0}$.

Finally, we will sometimes assume that $m$ is Ahlfors regular: namely that
there exists $c>0$ such that for any $x\in\Lambda$ and $r>0$,

$\frac{r^{s_{f}}}{c}\leqslant m(B(x,r))\leqslant cr^{s_{f}}$ (2.11)

where $s_{f}=\dim_{\textup{H}}\Lambda$. This holds if $m$ is Lebesgue, or more
generally if $m$ is conformal for a potential $-s_{f}\log|Df|$ and, for
example, $f$ is a finite branch Markov map555To see this, approximate the
measure $m(B(x,r))$ from above and below by the measure of appropriate
cylinders and apply conformality and (a1) (or alternatively using assumption
(2.9))., in which case this is referred to as the _Hausdorff measure_.

###  2.4. Results

We begin by stating our main theorem in the special case that $f$ is Markov
and $m$ satisfies (2.11).

######  Theorem 2.1.

Assume $(f,\mu)$ satisfies (a1)-(a6) and (2.8)–(2.11). There exist
$0<c<C<\infty$ such that for all $\delta>0$,

$c\delta^{-s_{f}}\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\delta^{-s_{f}}\log(1/\delta).$

Moreover, if the system is Gibbs-Markov and $f$ has at least 2 full branches
then we also have the sharp lower bound:

$c\delta^{-s_{f}}\log(1/\delta)\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\delta^{-s_{f}}\log(1/\delta).$

The assumption that $f$ has at least 2 full branches allows us to find, for
all $\delta>0$ sufficiently small, sufficiently many $\delta$-balls centred at
a point in $\Lambda$ which have measure close to $M_{\mu}(\delta)$ and are
‘far’ from each other in the sense that there is a good lower bound on the
time in between consecutive visits to these balls. This is enough to provide a
sharp lower bound, however we expect that there are weaker assumptions which
would yield the same conclusion.

We also consider more general measures $\mu$. Suppose
$\dim_{\textup{M}}\mu<\infty$. For each $\delta>0$ we denote

$\mathrm{Err}(\delta):=\left|\dim_{\textup{M}}\mu-\frac{\log\left(M_{\mu}(\delta))\right)}{\log\delta}\right|.$
(2.12)

Clearly $\dim_{\textup{M}}\mu<\infty$ implies $\lim_{\delta\to
0}\mathrm{Err}(\delta)=0$. Therefore in the case that
$\dim_{\textup{M}}\mu<\infty$, one can think of
$\delta^{-\dim_{\textup{M}}\mu\pm\mathrm{Err}(\delta)}$ as being upper and
lower bounds on the measure of the ball of minimum measure at scale $\delta$.

######  Theorem 2.2.

Assume $(f,\mu)$ and satisfies (a1)-(a6) and (2.8)–(2.10). There exist
$0<c<C<\infty$ and $\varepsilon>0$ such that such that for all $\delta>0$,

$\frac{c}{M_{\mu}(\delta/\varepsilon)}\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant\frac{C}{M_{\mu}(\varepsilon\delta)}\log(1/\delta).$
(2.13)

In particular if $\dim_{\textup{M}}\mu<\infty$ then

$c\delta^{-\dim_{\textup{M}}\mu+\mathrm{Err}(\delta/\varepsilon)}\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\delta^{-\dim_{\textup{M}}\mu-\mathrm{Err}(\varepsilon\delta)}\log(1/\delta).$
(2.14)

We note that if the measure $\mu$ is doubling (for example, if $f$ is a finite
branch Markov map and $\mu$ is Gibbs), then the dependence on $\varepsilon$
can be removed from the estimates. For example in (2.13) the denominators
appearing in the bounds could be replaced by $M_{\mu}(\delta)$ (the constants
coming from the doubling property would be absorbed in the constants $c$ and
$C$). The upper bound in Theorem (2.14) is analogous to the upper bound in
Theorem 2.1. The reason that $\mathrm{Err}(\delta)$ does not appear in Theorem
2.1 is because for a general measure $\mu$, the measure of the ball of minimum
measure at scale $\delta$ may take some time to resemble the asymptotic limit
$O(\delta^{\dim_{\textup{M}}\mu})$, whereas if (2.11) holds then this can
already be seen at large scales $\delta$.

In order to obtain a sharper lower bound in Theorem 2.2, roughly speaking we
would require an estimate on the number of balls of measure
$O(\delta^{\dim_{\textup{M}}\mu+\mathrm{Err}(\delta/\varepsilon)})$ seen at
scale $\delta$. This is straightforward in the case (2.11) holds, since all
balls of comparable diameter have comparable measure, which ensures a sharp
lower bound in Theorem 2.1. However we note that it is not always true that we
have exponentially many balls of measure
$O(\delta^{\dim_{\textup{M}}\mu+\mathrm{Err}(\delta/\varepsilon)})$ at scale
$\delta$ (meaning the system can cover faster than $\log(1/\delta)$ times the
reciprocal of the measure of the ball of minimum measure at scale $\delta$)
see for instance [JM, Theorem 1.1(2)]. In the other hand, in § 7 we provide
two examples of slowly covering systems: systems for which
$\dim_{\textup{M}}\mu=\infty$ and provide estimates on the asymptotic growth
of their expected cover times.

###  2.5. Uniformly large images for family of punctured maps

Suppose $(f,\mu)$ satisfies (a1)-(a4), in particular so that the constants
$n_{1}$ from (2.4) and $c_{m}$ from (a4) are well-defined. We say that the
system $(f,\mu)$ satisfies (U) if there exists $\delta_{0}>0$ such that for
each $0<\delta\leqslant\delta_{0}$ we can find a finite collection
${\mathcal{U}}_{\delta}$ of closed subintervals of $U\subset I$ which satisfy
the following assumptions:

  1. (U)(a)

There exists $0<t<1<T$ such that for all
$U\in{\mathcal{U}}(\delta_{0}):=\bigcup_{0<\delta\leqslant\delta_{0}}\bigcup\\{U:U\in{\mathcal{U}}_{\delta}\\}$,
there exists $x\in\Lambda$ such that $B(x,t\delta)\subseteq U\subseteq
B(x,T\delta)$;

  2. (U)(b)

for any $0<\delta\leqslant\delta_{0}$ the interiors of the intervals in
${\mathcal{U}}_{\delta}$ are pairwise disjoint;

  3. (U)(c)

for each $0<\delta\leqslant\delta_{0}$,
$\Lambda\subseteq\bigcup_{U\in{\mathcal{U}}_{\delta}}U$;

  4. (U)(d)

there exists $0<\tilde{\beta}<c_{m}$ such that for all $1\leqslant i\leqslant
n_{1}$, $Z\in{\mathcal{Z}}^{i}$ and $U\in{\mathcal{U}}(\delta_{0})$ either
$Z\subseteq U$ or $\frac{m(U\cap
Z)}{m(Z)}\leqslant\frac{\tilde{\beta}}{(n_{1}+1)(1+C_{d})^{2}}$, where $n_{1}$
comes from (2.4);

  5. (U)(e)

for any $U\in{\mathcal{U}}_{\delta}$,
$U\cap\Lambda=\Pi(\bigcup_{\mathbf{i}\in{\mathcal{P}}_{\delta}}[\mathbf{i}])$
where ${\mathcal{P}}_{\delta}\subset\Sigma^{*}$ is a finite or countable
collection of words $\mathbf{i}$ with the property that
$|\mathbf{i}|=O(\log(1/\delta))$ (where the implied constant is uniform over
all $0<\delta\leqslant\delta_{0}$).

Under the additional assumptions (2.8) and (2.9), $(f,\mu)$ satisfies 2.5.
Note that the only place where (2.8) and (2.9) will be required is in the
proofs of the following two propositions.

######  Proposition 2.3.

Suppose $(f,\mu)$ satisfies (a1)-(a4), (2.8) and (2.9). Then $(f,\mu)$
satisfies 2.5.

To obtain the sharp lower bound in Theorem 2.1 (in the case (2.11) holds) we
will also require the following proposition.

######  Proposition 2.4.

Suppose $(f,\mu)$ is Gibbs-Markov with at least two full branches, and
satisfies (2.8) and (2.9). There exists $\delta_{0}>0$ such that for each
$0<\delta\leqslant\delta_{0}$ we can find a finite collection

${\mathcal{V}}_{\delta}\subset\\{\Pi([wab^{n_{3}}])\;:\;w\in\\{a,b\\}^{*}\\}$

of pairwise disjoint subsets of $\Lambda$ where:

  1. (a)

$a,b\in\Sigma_{1}$, $a\neq b$ are such that $f_{a}$ and $f_{b}$ are full
branched and $n_{3}\in{\mathbb{N}}$ is chosen such that
$C_{*}^{3}\tilde{\mu}([ab^{n_{3}}])K<1$;

  2. (b)

for all $0\leqslant i\leqslant n_{3}$ and $U,V\in{\mathcal{V}}_{\delta}$,
$f^{i}(U)\cap V=\emptyset$;

  3. (c)

there exists $c,\varepsilon>0$ such that $\\#{\mathcal{V}}_{\delta}\geqslant
c\delta^{-\varepsilon}$;

  4. (d)

there exists $T>t>0$ such that for all $U\in{\mathcal{V}}_{\delta}$, there
exists $x\in\Lambda$ such that $B(x,t\delta)\cap\Lambda\subset U\subset
B(x,T\delta)$;

  5. (e)

there exists $0<\tilde{\beta}<c_{m}$ such that for all $1\leqslant i\leqslant
n_{1}$, $Z\in{\mathcal{Z}}^{i}$ and $U\in{\mathcal{U}}(\delta_{0})$ either
$Z\cap\Lambda\subseteq U$ or $\frac{m(U\cap
Z)}{m(Z)}\leqslant\frac{\tilde{\beta}}{(n_{1}+1)(1+C_{d})^{2}}$, where $n_{1}$
comes from (2.4);

  6. (f)

for any $U=\Pi([wab^{n_{3}}])\in{\mathcal{V}}_{\delta}$,
$|w|=O(\log(1/\delta))$ (where the implied constant is uniform over all
$0<\delta\leqslant\delta_{0}$);

  7. (g)

if $\Pi([w_{1}ab^{n_{3}}]),\Pi([w_{2}ab^{n_{3}}])\in{\mathcal{V}}_{\delta}$
are distinct, then $w_{1}ab^{n_{3}}$ is not a subword of $w_{2}ab^{n_{3}}$.

Proposition 2.4 essentially states that for sufficiently small $\delta$ we can
find sufficiently many balls of diameter roughly $\delta$ and measure roughly
$M_{\mu}(\delta)$ (this is (c) and (d)), which are dynamically far from each
other (namely there is a uniform lower bound on the time taken in between
visits of any orbit to any two balls in ${\mathcal{V}}_{\delta}$ \- this is
(b)). Proposition 2.4 will only be used in the proof of the lower bound in
Theorem 2.1.

The proof of Theorems 2.1 and 2.2 will require us to study a family of open
dynamical systems which have a hole at some $U\in{\mathcal{U}}(\delta_{0})$.
Namely, given $U\in{\mathcal{U}}(\delta_{0})$ we define the (open) map with a
hole at $U$ by $\mathring{f}_{U}=f|_{\Lambda\setminus U}$. Then its iterates
are given by $\mathring{f}_{U}^{n}=f|_{\mathring{U}^{n-1}}$ where
$\mathring{U}^{n-1}=\bigcap_{i=0}^{n}f^{-i}(\Lambda\setminus U)$ (so that
$\mathring{U}^{0}=\Lambda\setminus U$). We will require that the transfer
operators associated to these holes have a uniform spectral gap, and this will
follow from (U)(d) via the following lemma.

######  Lemma 2.5.

Assume $f$ and $\mu$ satisfy (a1)-(a4), (2.8) and (2.9). Then there exists
$c_{0}>0$ such that for all $U\in{\mathcal{U}}(\delta_{0})$,

$\inf_{U\in{\mathcal{U}}(\delta_{0})}\inf\\{m(\mathring{f}_{U}^{n_{1}}J):J\in{\mathcal{Z}}^{n_{1}}\;\textnormal{s.t.}\;J\cap\mathring{U}^{n_{1}}\neq\emptyset\\}\geqslant
c_{0}$

where $n_{1}$ comes from (2.4).

###### Proof.

Throughout the proof we’ll assume $\Lambda=I$, the more general case follows
similarly after taking intersections with $\Lambda$. Fix
$Z\in{\mathcal{Z}}^{n_{1}}$, $Z=\Pi([i_{0},\ldots,i_{n_{1}-1}])$ and
$U\in{\mathcal{U}}(\delta_{0})$ such that
$Z\cap\mathring{U}^{n_{1}}\neq\emptyset$. We want to show there exists $c_{0}$
which is independent of $U\in{\mathcal{U}}(\delta_{0})$ such that
$m(\mathring{f}_{U}^{n_{1}}(Z))\geqslant c_{0}$.

For each $0\leqslant j\leqslant n_{1}$ either $f^{-j}(U)\cap Z=\emptyset$ or
$U\cap\Pi([i_{j},\ldots,i_{n_{1}}])\neq\emptyset$ and $f^{-j}(U)\cap
Z=f_{i_{0}\ldots i_{j-1}}^{-1}(U\cap\Pi([i_{j},\ldots,i_{n_{1}-1}]))$, where
$f_{i_{0}\ldots i_{j-1}}^{-1}=f_{i_{0}}^{-1}\circ\cdots f_{i_{j-1}}^{-1}$
corresponds to the inverse branch of $f^{j}$ which maps $I$ homeomorphically
to $\Pi([i_{0}\ldots i_{j-1}])$ (in particular if $j=0$ we define
$f_{i_{0}\ldots i_{j-1}}^{-1}=\mathrm{Id}$). Note that this means that we
cannot have $\Pi([i_{j}\ldots i_{n_{1}-1}])\subset U$ as this would imply that
$f^{-j}(U)\cap Z=Z$ which is a contradiction since we’ve assumed
$Z\cap\mathring{U}^{n_{1}}\neq\emptyset$.

Hence

$\displaystyle\frac{m(f^{-j}(U)\cap Z)}{m(Z)}$
$\displaystyle\leqslant\frac{m(U\cap\Pi([i_{j}\ldots
i_{n_{1}-1}]))}{m([\Pi(i_{j}\ldots
i_{n_{1}-1}]))}\frac{\sup_{Z}e^{S_{j}\phi}}{\inf_{Z}e^{S_{j}\phi}}$
$\displaystyle\leqslant(1+C_{d})\frac{m(U\cap\Pi([i_{j}\ldots
i_{n_{1}-1}]))}{m(\Pi([i_{j}\ldots
i_{n_{1}-1}]))}\leqslant\frac{\tilde{\beta}}{(n_{1}+1)(1+C_{d})}$

where the first inequality follows by conformality, the second by (a1) and the
third by Proposition 2.3 and (U)(d). Thus

$\displaystyle\frac{m(Z\setminus\mathring{U}^{n_{1}})}{m(Z)}$
$\displaystyle=\frac{m(Z\cap\bigcup_{j=0}^{n_{1}}f^{-j}(U))}{m(Z)}\leqslant(n_{1}+1)\frac{\tilde{\beta}}{(n_{1}+1)(1+C_{d})}=\frac{\tilde{\beta}}{1+C_{d}}.$
(2.15)

In particular

$\displaystyle
m(\mathring{f}_{U}^{n_{1}}(Z))=m(f^{n_{1}}(Z))-m(f^{n_{1}}(Z\setminus\mathring{U}^{n_{1}}))$
$\displaystyle\geqslant
m(f^{n_{1}}(Z))-\frac{m(Z\setminus\mathring{U}^{n_{1}})}{m(Z)}\frac{\sup_{Z}e^{S_{n_{1}}\phi}}{\inf_{Z}e^{S_{n_{1}}\phi}}$
$\displaystyle\geqslant
m(f^{n_{1}}(Z))-\frac{m(Z\setminus\mathring{U}^{n_{1}})}{m(Z)}(1+C_{d})\geqslant
c_{m}-\tilde{\beta}>0$

where we have used conformality in the first inequality, (a1) in the second
inequality and (2.15) in the third inequality. The proof follows by setting
$c_{0}:=c_{m}-\tilde{\beta}$. ∎

###  2.6. Transfer operators for closed system.

We will study the action of the operator $\mathcal{L}$ on the Banach space
${\mathcal{B}}$ of functions $\psi:\Lambda\to{\mathbb{R}}$ with bounded
variation norm $\lVert\cdot\rVert=\lVert\cdot\rVert_{1}+|\cdot|_{BV}$, where
$\lVert\cdot\rVert_{1}$ denotes the $L^{1}$ norm with respect to $m$ and
$|\cdot|_{BV}:=|\cdot|_{BV,I}$ where for any interval $J\subseteq I$,

$|\psi|_{BV,J}:=\sup\left\\{\sum_{i=0}^{k-1}|\psi(x_{i+1})-\psi(x_{i})|\;:\;x_{0}<x_{1}<\cdots<x_{k},\;x_{i}\in
J\cap\Lambda,\;\forall i\leqslant k\right\\}$

where the supremum is taken over all finite sets $\\{x_{i}\\}_{i}\subset
J\cap\Lambda$.

Under (a1)-(a4) we have the following.

######  Lemma 2.6.

Assuming (a1)-(a4), for all $n\geqslant 0$,

  1. (a)

$\sum_{Z\in{\mathcal{Z}}^{n}}e^{S_{n}\phi}<\infty$;

  2. (b)

for each $Z\in{\mathcal{Z}}$, $|\phi|_{BV,Z}\leqslant C_{d}\sup_{Z}e^{\phi}$;

  3. (c)

$|e^{S_{n}\phi}|_{BV}<\infty$.

###### Proof.

(a) follows by induction on (2.6). (b) follows from (a) since
$|e^{\phi(x_{i+1})}-e^{\phi(x_{i})}|\leqslant C_{d}e^{\phi(x_{i})}$ for any
$\\{x_{i}\\}_{i=1}^{k}\subset Z$. For $n=0$, (c) follows from (b) and (2.6).
Setting $\phi|_{D}=-\infty$ only adds a term bounded by the series in (2.6) to
the variation. For $n\geqslant 1$ the claim follows by induction. ∎

Using Lemma 2.6 and (2.4), the operator $\mathcal{L}^{n_{1}}$ satisfies the
assumptions of [R, Theorem 1], thus $\mathcal{L}^{n_{1}}$ is quasi-compact on
${\mathcal{B}}$. By [R, Theorem 3] and (a3), $\mathcal{L}^{n_{1}}$ has a
simple eigenvalue at 1 and no other eigenvalues of modulus 1, in other words
$\mathcal{L}^{n_{1}}$ has spectral gap. By Lemma 2.6, since $\mathcal{L}$ is a
bounded operator on ${\mathcal{B}}$, it also has a spectral gap. We let
$g\in{\mathcal{B}}$ denote the normalised ($\int gdm=1$) eigenfunction of
$\mathcal{L}$ associated to the leading eigenvalue 1. $g$ is bounded away from
0. Write $d\mu=gdm$.

###  2.7. Transfer operators for open systems.

Here we use spectral properties of appropriate transfer operators which will
later give us information on hitting time statistics. This type of approach
has been used previously, for example in [D], [KL2] and [BDT], but we have to
make some adaptations, principally to Proposition 2.8 below in order to get
uniform estimates for our setting. Lemma 2.9 and Corollary 2.10 are then
essentially standard, but we include the short proofs for completeness.

######  Definition 2.7 (Transfer operators for open systems).

For any hole $U$ let
$\mathring{\mathcal{L}}_{U}:{\mathcal{B}}\to{\mathcal{B}}$ denote the transfer
operator with a hole at $U$, given by

$\mathring{\mathcal{L}}_{U}(\psi):=\sum_{y\in\mathring{f}_{U}^{-1}x}\psi(y)e^{\phi(y)}=\mathcal{L}({\mathbbm{1}}_{I\setminus
U}\psi).$

Note that the iterates of $\mathring{\mathcal{L}}_{U}$ are given by

$\mathring{\mathcal{L}}_{U}^{n}\psi(x)=\sum_{y\in\mathring{f}_{U}^{-n}x}\psi(y)e^{S_{n}\phi(y)}=\mathcal{L}^{n}(\psi{\mathbbm{1}}_{\mathring{U}^{n-1}}).$
(2.16)

By conformality of $m$,

$\int\mathring{\mathcal{L}}_{U}^{n}\psi
dm=\int\mathcal{L}^{n}(\psi{\mathbbm{1}}_{\mathring{U}^{n-1}})dm=\int_{\mathring{U}^{n-1}}\psi
dm.$ (2.17)

By (U) we have the following set of uniform Lasota-Yorke inequalities for the
family of operators
$\\{\mathring{\mathcal{L}}_{U}\\}_{U\in{\mathcal{U}}(\delta_{0})}$.

######  Proposition 2.8.

There exist $C_{0}>0$ and $0<\alpha<1$ such that for any
$\varphi\in{\mathcal{B}}$, $U\in{\mathcal{U}}(\delta_{0})$ and $n\geqslant 0$,

$\lVert\mathring{\mathcal{L}}_{U}^{n}\varphi\rVert\leqslant
C_{0}\alpha^{n}\lVert\varphi\rVert+C_{0}\int_{\mathring{U}^{n-1}}|\varphi|dm.$

The above is also true when $\mathring{\mathcal{L}}_{U}$ is replaced by
$\mathcal{L}$.

###### Proof.

Throughout the proof we’ll assume $\Lambda=I$, the proof in the more general
case is similar. For each $J\in{\mathcal{Z}}^{n}$ there is a unique choice of
disjoint intervals $\\{(x_{1},x_{2}),\ldots,(x_{k_{J}-1},x_{k_{J}})\\}$ such
that

$J\cap\mathring{U}^{n}=\bigcup_{i=1}^{k_{J}/2}(x_{2i-1},x_{2i}).$

In particular note that $x_{1}$ is the left hand end point of $J$ and
$x_{k_{J}}$ is the right hand end point of $J$.

Given $\psi\in{\mathcal{B}}$,

$|\mathring{\mathcal{L}}_{U}^{n}\psi|_{BV}\leqslant\sum_{J\in{\mathcal{Z}}^{n}}|\psi
e^{S_{n}\phi}|_{BV,J}+\psi(x_{1})e^{S_{n}\phi(x_{1})}+\cdots+\psi(x_{k_{J}})e^{S_{n}\phi(x_{k_{J}})}.$

Note that for all $x\in\\{x_{1},\ldots,x_{k_{J}}\\}$,

$\psi(x)e^{S_{n}\phi(x)}\leqslant\frac{1}{m(J\cap\mathring{U}^{n})}\int_{m(J\cap\mathring{U}^{n})}|\psi|e^{S_{n}\phi}dm+|\psi
e^{S_{n}\phi}|_{BV,J}$

yielding

$\displaystyle|\mathring{\mathcal{L}}_{U}^{n}\psi|_{BV}\leqslant\sum_{J\in{\mathcal{Z}}^{n}}(k_{J}+1)|\psi
e^{S_{n}\phi}|_{BV,J}+\frac{k_{J}}{m(J\cap\mathring{U}^{n})}\int_{J\cap\mathring{U}^{n}}|\psi|e^{S_{n}\phi}dm.$
(2.18)

Next, note that

$\displaystyle|\psi e^{S_{n}\phi}|_{BV,J}$
$\displaystyle\leqslant\sup_{J}\psi|e^{S_{n}\phi}|_{BV,J}+\sup_{J}e^{S_{n}\phi}|\psi|_{BV,J}$
$\displaystyle\leqslant\sup_{J}\psi
C_{d}\sup_{J}e^{S_{n}\phi}+\sup_{J}e^{S_{n}\phi}|\psi|_{BV,J}$ (2.19)
$\displaystyle\leqslant\sup_{J}e^{S_{n}\phi}\left(|\psi|_{BV,J}(C_{d}+1)+\frac{C_{d}}{m(J\cap\mathring{U}^{n})}\int_{J\cap\mathring{U}^{n}}|\psi|dm\right)$

where in the second line we have used Lemma 2.6(b) and in the last line we
have bounded
$\sup_{J}\psi\leqslant\frac{1}{m(J\cap\mathring{U}^{n})}\int_{J\cap\mathring{U}^{n}}|\psi|dm+|\psi|_{BV,J}.$

Combining with (2.18) we obtain

$\displaystyle|\mathring{\mathcal{L}}_{U}^{n}\psi|_{BV}$
$\displaystyle\leqslant\sum_{J\in{\mathcal{Z}}^{n}}(k_{J}+1)\sup_{J}e^{S_{n}\phi}|\psi|_{BV,J}(C_{d}+1)+((k_{J}+1)\sup_{J}e^{S_{n}\phi}C_{d}+k_{J})\frac{1}{m(J\cap\mathring{U}^{n})}\int_{J\cap\mathring{U}^{n}}|\psi|e^{S_{n}\phi}dm.$
(2.20)

By conformality and (a1), for all $x\in J\cap\mathring{U}^{n}$,

$e^{S_{n}\phi(x)}\frac{m(f^{n}(J\cap\mathring{U}^{n}))}{m(J\cap\mathring{U}^{n})}\leqslant
1+C_{d}.$ (2.21)

Also, note that $k_{J}\leqslant 2n+4$, since $J\cap\mathring{U}^{n}$ contains
at most $n+1$ holes corresponding to $U,\ldots,f^{-n}(U)$. Combining these
with (2.20) we obtain

$\displaystyle|\mathring{\mathcal{L}}_{U}^{n}\psi|_{BV}$
$\displaystyle\leqslant(2n+5)\sup_{I}e^{S_{n}\phi}(C_{d}+1)|\psi|_{BV}$
$\displaystyle\;\;\;+\sum_{J\in{\mathcal{Z}}^{n}}((2n+5)\sup_{I}e^{S_{n}\phi}C_{d}+2n+4)(1+C_{d})\frac{1}{m(f^{n}(J\cap\mathring{U}^{n}))}\int_{J\cap\mathring{U}^{n}}|\psi|dm$
(2.22)
$\displaystyle\leqslant(2n+5)\sup_{I}e^{S_{n}\phi}(C_{d}+1)|\psi|_{BV}+((2n+5)\sup_{I}e^{S_{n}\phi}C_{d}+2n+4)(1+C_{d})\frac{1}{c_{0}}\int_{\mathring{U}^{n}}|\psi|dm$
(2.23)

where we have used Lemma 2.5 in the final line.

Applying (2.23) with $n=n_{1}$ we see that for
$\tilde{\alpha}=(2n_{1}+5)\sup_{I}e^{S_{n_{1}}\phi}(C_{d}+1)|<1$ we have

$|\mathring{\mathcal{L}}_{U}^{n_{1}}\psi|_{BV}\leqslant\tilde{\alpha}|\psi|_{BV}+((2n_{1}+5)\sup_{I}e^{S_{n_{1}}\phi}C_{d}+2n_{1}+4)(1+C_{d})\frac{1}{c_{0}}\int_{\mathring{U}^{n_{1}}}|\psi|dm.$

We can then iterate this to complete the proof with
$\alpha=\tilde{\alpha}^{1/n_{1}}$. ∎

By Proposition 2.8, the compactness of the unit ball of ${\mathcal{B}}$ in
$L^{1}(m)$ and the conformality of $m$ that the spectral radius of
$\mathring{\mathcal{L}}_{U}$ acting on ${\mathcal{B}}$ is at most 1 and its
essential spectral radius is bounded by $\alpha<1$, for each
$U\in{\mathcal{U}}(\delta_{0})$ and the same is true for $\mathcal{L}$. Thus
$\mathcal{L}$ and each $\mathring{\mathcal{L}}_{U}$ are quasi-compact as
operators on ${\mathcal{B}}$. Define the following perturbative norm for
operators $P,Q$ acting on ${\mathcal{B}}$:

${|\kern-1.07639pt|\kern-1.07639pt|P-Q|\kern-1.07639pt|\kern-1.07639pt|}:=\sup\\{|P\varphi-Q\varphi|_{1}\;:\;\lVert\varphi\rVert\leqslant
1\\}.$

######  Lemma 2.9.

For any $U\subset I$,

${|\kern-1.07639pt|\kern-1.07639pt|\mathcal{L}-\mathring{\mathcal{L}}_{U}|\kern-1.07639pt|\kern-1.07639pt|}\leqslant
m(U)\leqslant C_{1}\mu(U)$

where $C_{1}=1/\operatorname*{ess\,inf}g.$

###### Proof.

If $\varphi\in{\mathcal{B}}$ with $\lVert\varphi\rVert\leqslant 1$ then

$\int|(\mathcal{L}-\mathring{\mathcal{L}}_{U})\varphi|dm=\int|\mathcal{L}(1_{U}\varphi)|dm\leqslant\sup_{\Lambda}|\varphi|m(U)\leqslant
m(U)$

by conformality. The fact that $\operatorname*{ess\,inf}g>0$ follows from
(a3). ∎

######  Corollary 2.10.

There exists $\delta_{1}\in(0,\delta_{0})$ such that for all
$U\in{\mathcal{U}}(\delta_{1})$, $\mathring{\mathcal{L}}_{U}$ and
$\mathcal{L}$ have uniform spectral gap. In particular, $\mathcal{L}$ and
$\mathring{\mathcal{L}}_{U}$ admits the following spectral decomposition

$\displaystyle\mathring{\mathcal{L}}$ $\displaystyle=\Pi+R$
$\displaystyle\mathring{\mathcal{L}}_{U}$
$\displaystyle=\lambda_{U}\Pi_{U}+R_{U}$

where

  1. (a)

$\lambda_{U}$ is the leading eigenvalue of $\mathring{\mathcal{L}}_{U}$ for
the normalised ($\int g_{U}dm=1$) eigenfunction $g_{U}$, i.e.
$\mathring{\mathcal{L}}_{U}g_{U}=\lambda_{U}g_{U}$ (analogously the leading
eigenvalue of $\mathcal{L}$ is 1, with normalised eigenfunction $g$);

  2. (b)

$\Pi_{U}$ is the projection onto the eigenspace spanned by $g_{U}$
(analogously $\Pi$ is the projection onto the eigenspace spanned by $g$),
moreover $\mathring{\mathcal{L}}_{U}^{*}m_{U}=\lambda_{U}m_{U}$ for the
eigenmeasure $m_{U}$;

  3. (c)

for $\alpha<\beta_{1}<\beta_{2}<1$ we have $\lambda_{U}>\beta_{2}$ and the
spectral radius $\sigma(R_{U})<\beta_{1}$ (also $\sigma(R)<\beta_{1}$);

  4. (d)

$\Pi_{U}^{2}=\Pi_{U}$ and $\Pi_{U}R_{U}=R_{U}\Pi_{U}=0$ (analogously
$\Pi^{2}=\Pi$ and $\Pi R=R\Pi=0$).

Moreover, there exist constants $K_{1},K_{2},K_{3},K_{4}>0$ and $\eta\in(0,1)$
such that for all $U\in{\mathcal{U}}(\delta_{1})$,

$\displaystyle{|\kern-1.07639pt|\kern-1.07639pt|\Pi_{U}-\Pi|\kern-1.07639pt|\kern-1.07639pt|}$
$\displaystyle\leqslant K_{1}m(U)^{\eta}$ (2.24) $\displaystyle\lVert
R_{U}^{n}\rVert$ $\displaystyle\leqslant K_{2}\beta_{1}^{n}$ (2.25)
$\displaystyle|1-\lambda_{U}|$ $\displaystyle\leqslant K_{3}\mu(U)$ (2.26)
$\displaystyle\lVert g_{U}\rVert$ $\displaystyle\leqslant K_{4}$ (2.27)

###### Proof.

As already discussed in the previous section, $\mathcal{L}$ has a spectral gap
by [R]. Using Proposition 2.8 and Lemma 2.9 and [KL1, Corollary 1] there
exists $\delta_{1}\in(0,\delta_{0})$ such that the family
$\\{\mathring{\mathcal{L}}_{U}\\}_{U\in{\mathcal{U}}(\delta_{1})}$ has a
uniform spectral gap and the stated eigendecomposition including properties
(a)-(d) (note that although [KL1] studies just one sequence of perturbed
operators, we can obtain analogues of the bounds in [KL1, Corollary 1] (and
thus the uniform spectral gap) over our whole family of operators
$\\{\mathring{\mathcal{L}}_{U}\\}_{U\in{\mathcal{U}}(\delta_{1})}$ due to the
uniformity of the constants in Proposition 2.8). (2.24) follows from [KL1,
Corollary 1(1)], (2.25) follows from [KL1, Corollary 2(2)] and (2.27) follows
from [KL1, Corollary 1(2)] (again the constants are uniform due to the
uniformity of the constants in Proposition 2.8.

To see (2.26) note that

$\displaystyle|1-\lambda_{U}|$ $\displaystyle=\left|\int
g_{U}dm-\lambda_{U}\int
g_{U}dm\right|=\left|\int\mathcal{L}g_{U}dm-\int\mathring{\mathcal{L}}_{U}g_{U}dm\right|$
$\displaystyle=\left|\int(\mathcal{L}-\mathring{\mathcal{L}}_{U})g_{U}dm\right|\leqslant\sup_{U\in{\mathcal{U}}(\delta_{1})}\lVert
g_{U}\rVert{|\kern-1.07639pt|\kern-1.07639pt|\mathcal{L}-\mathring{\mathcal{L}}_{U}|\kern-1.07639pt|\kern-1.07639pt|}\leqslant
C_{1}K_{4}\mu(U)$

where the last inequality follows by Lemma 2.9 and (2.27). ∎

##  3\. Return time estimates

We will estimate the expected hitting times to $U\in{\mathcal{U}}_{\delta}$ in
terms of the top eigenvalue $\lambda_{U}$. In order to then obtain Theorem 2.1
we will need to estimate $\lambda_{U}$ in terms of the measure of $U$ (which
will be done in Proposition 4.3). To this end, we will first require the
following estimates on return times to $U$, which is the main focus of this
section (note that the following proposition, and in particular in the lemma
following it, is the only place we use (2.10)).

######  Proposition 3.1.

Assume $(f,\mu)$ satisfies (a1)-(a6) and (2.8)–(2.11). Then there exist $c>0$
and $\delta_{2}\in(0,\delta_{1})$ such that for all
$U\in{\mathcal{U}}(\delta_{2})$ and $n\geqslant 1/\mu(U)$,

$\mu_{U}(\tau_{U}\geqslant n)\geqslant c\lambda_{U}^{n}.$

We will require the following lemma, which allows us to approximate intervals
by a pair of well-understood sets of cylinders. Let $d(Z)$ be the depth of a
cylinder $Z$. Note that given a cylinder $[x_{0},\ldots,x_{k}]$, for
$\ell\leqslant k$, its _$\ell$ -prefix_ is $(x_{0},\ldots,x_{\ell})$.

######  Lemma 3.2.

Assume (2.10).

  1. (1)

If $U_{I}\subset U\subset U_{O}$ and $n\in{\mathbb{N}}$ then

$\frac{\mu(U_{O})}{\mu(U)}\mu_{U_{O}}(\tau_{U_{O}}<n)\geqslant\mu_{U}(\tau_{U}<n)\geqslant\frac{\mu(U_{I})}{\mu(U)}\mu_{U_{I}}(\tau_{U_{I}}<n).$

  2. (2)

There exists $\kappa>0$ with the following property. For an interval $U$,
there are depths $d_{L},d_{R}$ such that there are $U_{I}\subset
U\cap\Lambda\subset U_{O}$ with $\mu(U_{I})\geqslant(1-\kappa)\mu(U)$ and
$\mu(U_{O})\leqslant(1+\kappa)\mu(U)$. Moreover, $U_{I}$ and $U_{O}$ are each
the $\Pi$ image of (at most) a union of $(d_{L}+1)$-cylinders
$\\{U_{L}^{i}\\}_{i}$ and $(d_{R}+1)$-cylinders $\\{U_{R}^{i}\\}_{i}$ where
all the $\\{U_{L}^{i}\\}_{i}$ have the same $d_{L}$-prefix and all the
$\\{U_{R}^{i}\\}_{i}$ have the same $d_{R}$-prefix.

###### Proof.

For the first part,

$\mu_{U}(\tau_{U}<n)=\frac{1}{\mu(U)}\mu\left(x\in
U:\tau_{U}(x)<n\right)\geqslant\frac{1}{\mu(U)}\mu\left(x\in
U_{I}:\tau_{U_{I}}(x)<n\right)=\frac{\mu(U_{I})}{\mu(U)}\mu_{U_{I}}\left(\tau_{U_{I}}<n\right),$

and similarly for the upper bound.

For the second part, for an interval $U$, let $U_{L}$ and $U_{R}$ be the
deepest cylinders such that $\Pi(U_{L})$ and $\Pi(U_{R})$ are adjacent to each
other, $\Pi(U_{L})$ to the left, so that $U\cap\Lambda\subset\Pi(U_{L}\cup
U_{R})$.

######  Claim.

There exists $B\in(0,1)$ such that for $\\{U_{L}^{i}\\}_{i}$ the depth
$d(U_{L})+1$ cylinders contained in $U_{L}\cap\Pi^{-1}(U)$ and
$\\{U_{R}^{i}\\}_{i}$ the depth $d(U_{R})+1$ cylinders contained in
$U_{R}\cap\Pi^{-1}(U)$,

$\mu\left(\left(\bigcup_{i}U_{L}^{i}\right)\cup\left(\bigcup_{i}U_{R}^{i}\right)\right)\geqslant
B\mu(U).$

Moreover adding in $U_{L}^{\ell}\subset U_{L}$ and $U_{R}^{r}\subset U_{R}$,
the depth $d(U_{L})+1$ and depth $d(U_{R})+1$ cylinders respectively so that
$\Pi^{-1}(U)\subset U_{L}^{\ell}\cup
U_{R}^{r}\cup\left(\bigcup_{i}U_{L}^{i}\right)\cup\left(\bigcup_{i}U_{R}^{i}\right)$,

$\mu\left(U_{L}^{\ell}\cup
U_{R}^{r}\cup\left(\bigcup_{i}U_{L}^{i}\right)\cup\left(\bigcup_{i}U_{R}^{i}\right)\right)\leqslant\frac{\mu(U)}{B}.$

###### Proof of Claim..

This claim follows from the cylinder structure. It is sufficient to show that

$\frac{\mu\left(U_{L}^{\ell}\cup\left(\bigcup_{i}U_{L}^{i}\right)\right)}{\mu\left(\left(\bigcup_{i}U_{L}^{i}\right)\right)}$

is uniformly bounded above (the case for the right-hand cylinder follows
similarly). First note that $\bigcup_{i}U_{L}^{i}\neq{\emptyset}$ since
otherwise $U_{L}$ is not the deepest cylinder we could have chosen. Then since
$U_{L}^{\ell}$ must be adjacent to some $U_{L}^{i}$, the bound follows
directly from (2.10). ∎

∎

###### Proof of Proposition 3.1..

The problems here are when there are multiple overlaps, so the worst case is
when the symbolic model is the full shift, so we will assume this here.
Moreover we will assume that $\Lambda=I$: the adaptation to the general case
goes through by intersecting intervals with $\Lambda$.

We first show what happens for the non-conditional measure case.

######  Claim.

There exist constants $0<c(U,n)<1<C(U,n)<\infty$ with the property that

$c(U,n)\lambda_{U}^{n}\leqslant\mu(\tau_{U}\geqslant n)\leqslant
C(U,n)\lambda_{U}^{n}$

where $c(U,n),C(U,n)\to 1$ as $\mu(U)\to 0$ and $n\to\infty$.

###### Proof.

$\displaystyle\mu(\tau_{U}\geqslant n)$
$\displaystyle=\int{\mathbbm{1}}_{\\{\tau_{U}\geqslant n\\}}\cdot
g\leavevmode\nobreak\
dm=\int\mathring{\mathcal{L}}_{U}^{n}(g)\leavevmode\nobreak\
dm=\lambda_{U}^{n}\left(\int\Pi_{U}(g)+\lambda_{U}^{-n}R_{U}^{n}(g)dm\right)$
$\displaystyle=\lambda_{U}^{n}\left(\int
cg_{U}+\lambda_{U}^{-n}R_{U}^{n}(g)dm\right)=\lambda_{U}^{n}\left(c+\lambda_{U}^{-n}\int
R_{U}^{n}(g)dm\right)$

for some constant $c$, by definition of $\Pi_{U}$. Then

$|c-1|=\left|\int cg_{U}\leavevmode\nobreak\ dm-\int g\leavevmode\nobreak\
dm\right|=\left|\int\Pi_{U}(g)\leavevmode\nobreak\
dm-\int\Pi(g)\leavevmode\nobreak\ dm\right|\leqslant
K_{1}\mu(U)^{\eta}\|g\|\leqslant K_{1}K_{4}\mu(U)^{\eta}$

by (2.24) and (2.27). Since also from (2.25),

$\left|\int R_{U}^{n}(g)\leavevmode\nobreak\
dm\right|\leqslant\|R_{U}^{n}(g)\|\leqslant K_{2}\beta_{1}^{n}\|g\|\leqslant
K_{2}K_{4}\beta_{1}^{n},$

we obtain

$\mu(\tau_{U}\geqslant
n)\geqslant\lambda_{U}^{n}\left(1-K_{1}K_{4}\mu(U)^{\eta}-K_{2}K_{4}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{n}\right),$

completing the proof of the lower bound, and the upper bound is similar. ∎

The idea is to ‘add buffers’ of length $m$ so that we lose some of the power
coming from $\lambda_{U}$, but gain better distortion estimates using
$\psi$-mixing (a6).

Single cylinder case

We start by assuming $\Pi^{-1}(U)$ is a cylinder, and generalise later on. To
simplify notation, we switch to using the symbolic measure $\tilde{\mu}$ and
assume $U$ itself is a cylinder.

Given $m\in{\mathbb{N}}$ and assuming $n\geqslant 2k+2m$, we write

$\displaystyle\tilde{\mu}_{U}(\tau_{U}\geqslant n)$
$\displaystyle=\tilde{\mu}_{U}\left(\underline{x}=(x_{0},x_{1},\ldots)\in
U:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=0}^{n-2}[x_{i+1},\ldots,x_{i+k}]\right)$
$\displaystyle=\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=k+m}^{n-2}[x_{i+1},\ldots,x_{i+k}]\right)$
$\displaystyle\quad-\tilde{\mu}_{U}\big{(}\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\in\cup_{i=0}^{k+m-1}[x_{i+1},\ldots,x_{i+k}]$
$\displaystyle\hskip 113.81102pt\text{ \&
}[u_{0},\ldots,u_{k-1}]\notin\cup_{i=k+m}^{n-2}[x_{i+1},\ldots,x_{i+k}]\big{)}.$

We refer to these terms as $(I)$ and $(II)$

For $(I)$, using $\psi$-mixing (a6),

$\displaystyle\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=k+m}^{n-2}[x_{i+1},\ldots,x_{i+k}]\right)$
$\displaystyle=\frac{1}{\tilde{\mu}(U)}\tilde{\mu}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=k+m}^{n-2}[x_{i+1},\ldots,x_{i+k}]\right)$
$\displaystyle\geqslant(1-\gamma(m))\tilde{\mu}\left(\underline{x}\in\Sigma:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=0}^{n-k-m-2}[x_{i+1},\ldots,x_{i+k}]\right)\sim\lambda_{U}^{n-k-m-2},$

where the final step follows from the claim since

$\displaystyle\mu\left(\underline{x}\in\Sigma:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=0}^{n-k-m-2}[x_{i+1},\ldots,x_{i+k}]\right)$
$\displaystyle=\mu\left(\underline{x}\in\Sigma:\tau_{U}(x)\geqslant
n-k-m-2\right).$

Then for $(II)$ we look at the larger value

$\displaystyle\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\in\cup_{i=0}^{k+m-1}[x_{i+1},\ldots,x_{i+k}]\text{ \&
}[u_{0},\ldots,u_{k-1}]\notin\cup_{i=2k+2m}^{n-2}[x_{i+1},\ldots,x_{i+k}]\right).$

There are three conditions here: being in $U$ as well as the two conditions on
the cylinders. By $\psi$-mixing (a6) these are almost independent. The
problematic part here, the _short returns_ , is dealt with by the following
claim. We note that the arguments here are similar to those in [AL], but here
we have more general systems (our measures need not be Bernoulli) and
ultimately have to deal with more than one cylinder.

######  Claim.

There is $\tilde{\theta}<1$ independent of $U$ such that

$\displaystyle\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\in\left\\{[x_{i+1},\ldots,x_{i+k}]\right\\}_{i=0}^{k+m-1}\right)\leqslant\tilde{\theta}.$

###### Proof of Claim.

We first estimate

$\displaystyle\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\in\left\\{[x_{i+1},\ldots,x_{i+k}]\right\\}_{i=0}^{k+m-1}\right)\leqslant\tilde{\theta},$

so we are interested in estimates of the form

$\tilde{\mu}_{U}\left([u_{0},u_{1},\ldots,u_{i},u_{0},\ldots,u_{k-1}]\right)=\frac{1}{\tilde{\mu}(U)}\tilde{\mu}\left([u_{0},\ldots,u_{k-1}]\cap[u_{0},u_{1},\ldots,u_{i},u_{0},\ldots,u_{k-1}]\right).$

We can deal with this case by case: if the intersection here is non-empty and
$i=0$ then $u_{j}=u_{0}$ for all $1\leqslant j<k$ and then

$\displaystyle\tilde{\mu}_{U}\left([u_{0},u_{0},\ldots,u_{k-1}]\right)$
$\displaystyle=\tilde{\mu}_{U}\left([u_{0},\ldots,u_{k-1},u_{k-1}]\right)=1-\frac{1}{\tilde{\mu}(U)}\tilde{\mu}\left(\cup_{u_{k-1}^{\prime}\neq
u_{k-1}}[u_{0},\ldots,u_{k-1},u_{k-1}^{\prime}]\right)$
$\displaystyle\leqslant
1-\frac{1}{C_{*}}\tilde{\mu}\left(\cup_{u_{k-1}^{\prime}\neq
u_{k-1}}[u_{k-1}^{\prime}]\right)=1-\frac{1}{C_{*}}\left(1-\tilde{\mu}([u_{k-1}])\right)<1$

by (a5). Crucially here we do not have to consider any further overlaps, since
in this case they are accounted for by the first one.

Similarly, if the relevant intersection is non-empty for $i=1$ with $u_{0}\neq
u_{1}$ but $u_{0}=u_{2}$, then in fact $u_{i}=u_{j}$ if and only if $i=j\mod
2$. So

$\displaystyle\tilde{\mu}_{U}\left([u_{0},u_{1},u_{0},\ldots,u_{k-1}]\right)$
$\displaystyle=\tilde{\mu}_{U}\left([u_{0},\ldots,u_{k-1},u_{k-2},u_{k-1}]\right)$
$\displaystyle=1-\frac{1}{\tilde{\mu}(U)}\tilde{\mu}\left(\cup_{(u_{k-2}^{\prime},u_{k-1}^{\prime})\neq(u_{k}-2,u_{k-1})}[u_{0},\ldots,u_{k-1},u_{k-2}^{\prime},u_{k-1}^{\prime}]\right)$
$\displaystyle\leqslant
1-\frac{1}{C_{*}}\tilde{\mu}\left(\cup_{(u_{k-2}^{\prime},u_{k-1}^{\prime})\neq(u_{k}-2,u_{k-1})}[u_{k-2}^{\prime},u_{k-1}^{\prime}]\right)=1-\frac{1}{C_{*}}\left(1-\tilde{\mu}\left([u_{k-2},u_{k-1}]\right)\right)<1.$

(Again, we only have to consider one overlap here.)

We can proceed in the same way to deal with all possible periods up to length
$\lfloor\frac{k-1}{2}\rfloor$ within $U$ since if there is a non-empty overlap
of
$[u_{0},\ldots,u_{k-1}]\cap[u_{0},u_{1},\ldots,u_{i},u_{0},\ldots,u_{k-1}]$,
but not for smaller $i$, then this argument says that the $j$th coordinate of
$U$ determines the $(i+j+1)$st coordinate of $U$ for any $i$. But this
uniquely determines all possible overlaps if
$i\leqslant\lfloor\frac{k-1}{2}\rfloor$, and indeed all subsequent overlaps
are accounted for by the first one. On the other hand, if there an overlap for
some $i>\lfloor\frac{k-1}{2}\rfloor$, but not before this, there may also be
multiple overlaps for subsequent $\ell>i$ which are not already accounted for
at time $i$. However, in this case we can use the quasi-Bernoulli property
(a5) to give

$\displaystyle\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\in\left\\{[x_{i+1},\ldots,x_{i+k}]\right\\}_{i=\lfloor\frac{k-1}{2}\rfloor}^{k-1}\right)$
$\displaystyle\leqslant
C_{*}\left(\tilde{\mu}[u_{0},\ldots,u_{\lfloor\frac{k-1}{2}\rfloor}]+\cdots+\tilde{\mu}[u_{0},\ldots,u_{k-2}]\right)\leqslant\frac{C_{*}e^{-\left(\lfloor\frac{k-1}{2}\rfloor\right)}}{1-e^{-\alpha}}.$

Since for $k$ large, this estimate is very small, we see that the the worst
estimate is essentially for the first case we dealt with here, from which we
would derive our new $\tilde{\theta}<1$.

However, we also need to deal with the cases

$\displaystyle\tilde{\mu}_{U}\left(\underline{x}\in
U:[u_{0},\ldots,u_{k-1}]\in\left\\{[x_{i+1},\ldots,x_{i+k}]\right\\}_{i=k-1}^{k+m-1}\right).$

But since these cases consist of estimates of the form

$\tilde{\mu}_{U}\left(\cup_{b_{0},\ldots,b_{\ell-1}\in\mathcal{I}}[u_{0},\ldots,u_{k-1},b_{0},\ldots,b_{\ell-1},u_{0},\ldots,u_{k-1}]\right)\leqslant
C_{*}\tilde{\mu}(U)$

for $0\leqslant\ell\leqslant m-1$, which sum to $C_{*}m\tilde{\mu}(U)$. So for
$U$ small, this doesn’t affect $\tilde{\theta}$ very much, so we abuse
notation and keep this the same. ∎

Putting together the estimates for $(II)$ we obtain
$\lambda_{U}^{n-2-2k-2m}(1+\gamma(m))^{2}\tilde{\theta}$. Here we have used
that

$\left(\underline{x}\in\Sigma:[u_{0},\ldots,u_{k-1}]\notin\cup_{i=2k+2m}^{n-2}[x_{i+1},\ldots,x_{i+k}]\right)$

is just a preimage of the set $\\{\underline{x}\in\Sigma:\tau_{U}(x)\geqslant
n-2-2k-2m\\}$. Therefore the overall asymptotic estimate is

$\lambda_{U}^{n-2-2k-2m}\left(\lambda_{U}^{m+k}(1-\gamma(m))-(1+\gamma(m))^{2}\tilde{\theta}\right).$

Since $\lambda_{U}^{n-2-2k-2m}\geqslant\lambda_{U}^{n}$, it is sufficient to
prove
$\left(\lambda_{U}^{m+k}(1-\gamma(m))-(1+\gamma(m))^{2}\tilde{\theta}\right)>0$.
This follows since we can fix some large enough $m$ so that $\gamma(m)$ is
sufficiently small, and then use (2.26) which, since also
$\tilde{\mu}(U)\leqslant Ce^{-\omega k}$, implies $\lambda_{U}\geqslant
1-K_{3}\tilde{\mu}(U)$, so $\lambda_{U}^{m+k}\to 1$ as $\tilde{\mu}(U)\to 0$.

Approximating intervals by cylinders

Now in the case that $U$ is not a cylinder, but $\Pi(U)$ is an interval, Lemma
3.2 implies that it is enough to prove for certain unions of cylinders. We
will simplify the situation by just looking at a union of two cylinders, but
notice that since the lemma tells us that we only have two families of
cylinders, of depths $d_{L}+1$ and $d_{R}+1$ respectively, where the
$d_{L}$-th (or $d_{R}$-th) prefix is the same for all members of the family,
the proofs will go through for these unions too.

Suppose that $U$ and $V$ are cylinders of depth $k_{U}$ and $k_{V}$
respectively, so $U=[u_{0},\ldots,u_{k_{U}-1}]$ and
$V=[v_{0},\ldots,u_{k_{V}-1}]$. Assume $k_{U}\geqslant k_{V}$. To make similar
estimates to the single cylinder case, we will replace $k$ with $k_{U}$ in
$(I)$ and $(II)$. The estimate for $(I)$ follows as in the single cylinder
case, so we focus on $(II)$. To estimate the short returns we will be dealing
with estimates of the form

  1. (i)

$\mu_{U\cup V}\left([u_{0},\ldots,u_{i},u_{0},\ldots,u_{k_{U}-1}]\right)$ for
$i\leqslant k_{U}-1$;

  2. (ii)

$\mu_{U\cup V}\left([u_{0},\ldots,u_{i},v_{0},\ldots,v_{k_{V}-1}]\right)$ for
$i\leqslant k_{U}-1$;

  3. (iii)

$\mu_{U\cup V}\left([v_{0},\ldots,v_{i},u_{0},\ldots,u_{k_{U}-1}]\right)$ for
$i\leqslant k_{V}-1$;

  4. (iv)

$\mu_{U\cup V}\left([v_{0},\ldots,v_{i},v_{0},\ldots,v_{k_{V}-1}]\right)$ for
$i\leqslant k_{V}-1$;

  5. (v)

$\mu_{U\cup
V}\left(\cup_{b_{p}\in{\mathcal{A}}}[v_{0},\ldots,v_{k_{V}-1},b_{0},\ldots,b_{j-1},u_{0},\ldots,u_{k_{U}-1}]\right)$
and $k_{V}\leqslant i\leqslant k_{U}-1$;

  6. (vi)

$\mu_{U\cup
V}\left(\cup_{b_{p}\in{\mathcal{A}}}[v_{0},\ldots,v_{k_{V}-1},b_{0},\ldots,b_{j-1},v_{0},\ldots,v_{k_{V}-1}]\right)$
and $k_{V}\leqslant i\leqslant k_{U}-1$.

As in the single cylinder case, for $i$ small we have to make careful
estimates, but for $i$ large a rough estimate suffices (in particular, the
idea for dealing with $i$ around $k+m-1$ is the same as in the single cylinder
case, so we will not deal with that here). Indeed the estimates (v) and (vi)
the estimates are
$\leqslant\frac{CC_{*}\mu(U)\mu(V)e^{-j\omega}}{\mu(U)+\mu(V)}$, which is very
small, and sum nicely. Estimates for (i) and (iv) follow as in the simple
cylinder case. It remains to consider (ii) and (iii).

As in the single cylinder case, the naive estimate takes over for $i$ large,
so let us assume:

$i\leqslant\frac{k_{V}}{2}\leqslant\frac{k_{U}}{2}$ (3.1)

We give some details for Case (iii). The first $i$ with non-empty overlap is
$[v_{0},\ldots,v_{i},u_{0},\ldots,u_{k_{U}-1}]\subset U\cup V$ with
$i\leqslant k_{V}-1$.

  * •

First assume $[v_{0},\ldots,v_{i},u_{0},\ldots,u_{k_{U}-1}]\subset V$.
Then
$u_{0}=v_{i+1},u_{1}=v_{i+2},\ldots,u_{j}=v_{i+j+1},\ldots,u_{k_{V}-i-2}=v_{k_{V}-1}$.

Now suppose
$[v_{0},\ldots,v_{i},v_{i+1},u_{0},\ldots,u_{k_{U}-1}]\neq{\emptyset}$. Then
if this set is in $V$ then
$u_{0}=v_{i+2}=u_{1}=v_{i+1},\ldots,u_{j}=v_{i+2+j}=u_{j+1}=v_{i+j+1}$ for
$j\leqslant\min\\{k_{U}-1,k_{V}-2-i\\}$, i.e.,
$v_{i+1}=\cdots=v_{i+j+1}=u_{0}$. Hence any relevant non-empty intersection
will already be contained in $[v_{0},\ldots,v_{i},u_{0},\ldots,u_{j}]$ for
$j=\min\\{k_{U}-1,k_{V}-2-i\\}\geqslant\frac{k_{V}}{2}-2$.

If instead we consider
${\emptyset}\neq[v_{0},\ldots,v_{i},v_{i+1},u_{0},\ldots,u_{k_{U}-1}]\subset
U$ then this also forces $u_{j+i+1}=u_{j}=u_{j+i+1}$ for $j\leqslant
k_{U}-i-2$, i.e., $u_{0}=u_{1}=\cdots=u_{k_{U}-i-2}$. Hence any relevant non-
empty intersection will be contained in
$[v_{0},\ldots,v_{i},u_{0},\ldots,u_{k_{U}-i-2}]$.

We can proceed as before to cover intersections
$[v_{0},\ldots,v_{i},v_{i+1},\ldots,v_{i+j},u_{0},\ldots,u_{k_{U}-1}]$ for
$i+j\leqslant\frac{k_{V}}{2}$: we can always cover all the resulting
intersections with $[v_{0},\ldots,v_{i},u_{0},\ldots,u_{\ell}]$ for
$\ell\geqslant\frac{k_{V}}{2}$.

  * •

Now, instead, start by assuming
$[v_{0},\ldots,v_{i},u_{0},\ldots,u_{k_{U}-1}]\subset U$, then
$u_{0}=u_{i+1},\ldots,u_{k_{U}-i-2}=u_{k_{U}-1}$.

If also
${\emptyset}\neq[v_{0},\ldots,v_{i},v_{i+1},u_{0},\ldots,u_{k_{U}-1}]\subset
U$ then as above all further relevant non-empty intersections will already be
contained in $[v_{0},\ldots,v_{i},u_{0},\ldots,u_{k_{U}-i-3}]$

If instead we assume
${\emptyset}\neq[v_{0},\ldots,v_{i},v_{i+1},u_{0},\ldots,u_{k_{U}-1}]\subset
V$ then we can deduce that $u_{i+j}=v_{i+j}$ for $0\leqslant j\leqslant
k_{V}-1-i$ (we already had $u_{j}=v_{j}$ for $0\leqslant j\leqslant k_{U}-1$).
This again puts us in the single cylinder case for the first
$\frac{k_{V}}{2}-1$ intersections.

Again we can proceed as before to cover all other intersections
$[v_{0},\ldots,v_{i},v_{i+1},\ldots,v_{i+j},u_{0},\ldots,u_{k_{U}-1}]$ for
$i+j\leqslant\frac{k_{V}}{2}$.

Case (ii) follows similarly. ∎

##  4\. Hitting times estimates

In this section, we obtain the following estimates on the expected hitting
times.

######  Theorem 4.1.

Assume $(f,\mu)$ satisfies (a1)-(a5), (2.8) and (2.9), so that by Proposition
2.3 we can choose ${\mathcal{U}}(\delta_{3})$ which satisfies (U). There exist
$0<c<C<\infty$, $\delta_{3}^{*}\in(0,\delta_{3})$ such that for all
$U\in{\mathcal{U}}(\delta_{3}^{*})$,

$\frac{c}{\mu(U)}\leqslant\mathbb{E}(\tau_{U})\leqslant\frac{C}{\mu(U)}.$

In order to obtain uniform estimates on $\mathbb{E}(\tau_{U})$ we write
$\mathbb{E}(\tau_{U})=\sum_{n\geqslant 1}\mu(\tau_{U}\geqslant n)$ and observe
that

$\mu(\tau_{U}\geqslant n)=\int{\mathbbm{1}}_{\\{\tau_{U}\geqslant n\\}}\cdot
g\leavevmode\nobreak\
dm=\int\mathring{\mathcal{L}}_{U}^{n}(g)\leavevmode\nobreak\ dm$

and so it will be sufficient to obtain uniform estimates on
$\int\mathring{\mathcal{L}}_{U}^{n}(g)\leavevmode\nobreak\ dm$.

######  Lemma 4.2.

There exist constants $0<c<C<\infty$, $0<\delta_{2}^{*}\leqslant\delta_{1}$
and $N\in{\mathbb{N}}$ such that for all $U\in{\mathcal{U}}(\delta_{2}^{*})$,

$\displaystyle
0\leqslant\int\mathring{\mathcal{L}}_{U}^{n}(g)\leavevmode\nobreak\
dm\leqslant C\lambda_{U}^{n}$ $\displaystyle\;\;\;(\forall n<N)$
$\displaystyle
c\lambda_{U}^{n}\leqslant\int\mathring{\mathcal{L}}_{U}^{n}(g)\leavevmode\nobreak\
dm\leqslant C\lambda_{U}^{n}$ $\displaystyle\;\;\;(\forall n\geqslant N).$

###### Proof.

By Corollary 2.10, for all $U\in{\mathcal{U}}(\delta_{1})$.

$\displaystyle\int\mathring{\mathcal{L}}_{U}^{n}(g)dm$
$\displaystyle=\lambda_{U}^{n}\left(\int\Pi_{U}(g)+\lambda_{U}^{-n}R_{U}^{n}(g)dm\right)=\lambda_{U}^{n}\left(\int
c_{U}g_{U}+\lambda_{U}^{-n}R_{U}^{n}(g)dm\right)$
$\displaystyle=\lambda_{U}^{n}\left(c_{U}+\lambda_{U}^{-n}\int
R_{U}^{n}(g)dm\right)$

where we have used that $\int g_{U}dm=1$. By (2.25),

$\left|\int R_{U}^{n}(g)dm\right|\leqslant\lVert R_{U}^{n}(g)\rVert\leqslant
K_{2}\beta_{1}^{n}\lVert g\rVert.$

By (2.24),

$|1-c_{U}|=\left|\int\Pi(g)dm-\int\Pi_{U}(g)dm\right|\leqslant
K_{1}m(U)^{\eta}\lVert g\rVert.$

Now, we can choose $N\in{\mathbb{N}}$ so that $K_{2}\lVert
g\rVert(\beta_{1}/\beta_{2})^{N}<1$. Now chooses
$\delta_{2}^{*}\leqslant\delta_{1}$ such that
$M:=\sup_{U\in{\mathcal{U}}(\delta_{2}^{*})}K_{1}\lVert g\rVert
m(U)^{\eta}<1-K_{2}\lVert g\rVert(\beta_{1}/\beta_{2})^{N}$. Then for all
$n\in{\mathbb{N}}$ and $U\in{\mathcal{U}}(\delta_{2}^{*})$,

$\displaystyle\int\mathring{\mathcal{L}}_{U}^{n}(g)dm$
$\displaystyle\leqslant\lambda_{U}^{n}\left(1+M+K_{2}(\beta_{1}/\beta_{2})^{n}\lVert
g\rVert\right)$ $\displaystyle\leqslant\lambda_{U}^{n}\left(1+M+K_{2}\lVert
g\rVert\right).$

Moreover, for all $n\geqslant N$ and $U\in{\mathcal{U}}(\delta_{2}^{*})$

$\displaystyle\int\mathring{\mathcal{L}}_{U}^{n}(g)dm$
$\displaystyle\geqslant\lambda_{U}^{n}(1-M-K_{2}\lVert
g\rVert(\beta_{1}/\beta_{2})^{N}\lVert g\rVert)$

where the term in the bracket is positive by definition of $M$. ∎

Therefore, to complete the proof of Theorem 4.1, we require estimates on
$\lambda_{U}$. This is provided by the following result.

######  Proposition 4.3.

There exist constants $0<c<C<\infty$ and $\delta_{3}\in(0,\delta_{2})$ such
that for all $U\in{\mathcal{U}}(\delta_{3})$,

$c\mu(U)\leqslant 1-\lambda_{U}\leqslant C\mu(U).$

###### Proof.

The upper bound follows from (2.26). For the lower bound we adapt some
arguments from [KL2]. In [KL2] and [BDT] the limit $\lim_{\delta\to
0}\frac{1-\lambda_{U_{\delta}}}{\mu(U_{\delta})}$ is computed for
$\bigcap_{\delta>0}U_{\delta}=\\{z\\}$. We require something less precise
(only a lower bound on the ratio
$\frac{1-\lambda_{U_{\delta}}}{\mu(U_{\delta})}$), but it needs to be uniform
over $U\in{\mathcal{U}}(\delta_{3})$ for some $\delta_{3}>0$.

We begin by verifying that uniform versions of (A1)-(A6) from [KL2] hold over
our family of operators
$\\{\mathring{\mathcal{L}}_{U}\\}_{U\in{\mathcal{U}}(\delta_{1})}$. (A1)-(A2)
is precisely the spectral decomposition from Corollary 2.10. (A3) requires
that

$\sum_{n=0}^{\infty}\sup_{U\in{\mathcal{U}}(\delta_{1})}\frac{\lVert
R_{U}^{n}\rVert}{\lambda_{U}^{n}}<\infty$

which holds by (2.25). (A4) requires that $\int g_{U}dm=1$, which we have, and
that

$\sup_{U\in{\mathcal{U}}(\delta_{1})}\lVert g_{U}\rVert<\infty$

which follows from (2.27). (A5) requires that
$\sup_{U\in{\mathcal{U}}(r)}\eta_{U}\to 0$ where

$\eta_{U}:=\sup_{\lVert\psi\rVert=1}\left|\int(\mathcal{L}\psi-\mathring{\mathcal{L}}_{U}\psi)dm\right|,$
(4.1)

which holds by Lemma 2.9 since $\eta_{U}\leqslant m(U)$. Finally (A6) requires
that

$\eta_{U}\lVert(\mathcal{L}-\mathring{\mathcal{L}}_{U})(g)\rVert\leqslant
C^{\prime}\mu(U)$

for some constant $C^{\prime}$ which doesn’t depend on
$U\in{\mathcal{U}}(\delta_{1})$. Since

$\lVert(\mathcal{L}-\mathring{\mathcal{L}}_{U})(g)\rVert=\lVert\mathcal{L}({\mathbbm{1}}_{U}g)\rVert\leqslant\lVert\mathcal{L}\rVert\lVert{\mathbbm{1}}_{U}g\rVert\leqslant\lVert\mathcal{L}\rVert\lVert
g\rVert$

we indeed have

$\eta_{U}\lVert(\mathcal{L}-\mathring{\mathcal{L}}_{U})(g)\rVert\leqslant
m(U)\lVert\mathcal{L}\rVert\lVert g\rVert\leqslant
C_{1}\lVert\mathcal{L}\rVert\lVert g\rVert\mu(U)$

as desired.

The above implies that [KL2, Lemma 6.1] holds for a uniform constant $C$. In
particular, defining for each $n\in{\mathbb{N}}$

$\kappa_{n}:=K_{2}\sum_{k=n}^{\infty}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{n},$
(4.2)

there exists $C>0$ such that for all $U\in{\mathcal{U}}(\delta_{1})$,

  1. (a)

$|1-\int gdm_{U}|\leqslant Cm(U)$ where $m_{U}$ is given by Corollary 2.10(a),

  2. (b)

$\frac{\lVert R_{U}^{n}g\rVert}{\lambda_{U}^{n}}\leqslant
C\kappa_{n}(\lVert(\mathcal{L}-\mathring{\mathcal{L}}_{U})(g)\rVert+|1-\lambda_{U}|)$.

Following the proof of Theorem 2.1 in [KL2] now yields that for any
$n\in{\mathbb{N}}$,

$\frac{1-\lambda_{U}}{\mu(U)}=\frac{\left(1-\sum_{k=0}^{n-1}\lambda_{U}^{-k}q_{k,U}\right)+\kappa_{n}^{\prime}}{(1+O(\eta_{U}))(1+nO(\eta_{U}))}$
(4.3)

where $\kappa_{n}^{\prime}=O(\kappa_{n})$ and

$q_{k,U}=\frac{m((\mathcal{L}-\mathring{\mathcal{L}}_{U})\mathring{\mathcal{L}}_{U}^{k}(\mathcal{L}-\mathring{\mathcal{L}}_{U})g)}{m((\mathcal{L}-\mathring{\mathcal{L}}_{U})g)}=\frac{\mu(E_{U}^{k})}{\mu(U)}$

for

$E_{U}^{k}:=\\{x\in U:f^{i}(x)\notin U,\;i=1,\ldots,k,\;f^{k+1}(x)\in U\\},$

see [BDT].

Recall that by $\kappa_{n}^{\prime}=O(\kappa_{n})$ we mean that for some
constant $C^{\prime\prime}>0$ which is independent of $n$ (and $U$),
$|\kappa_{n}^{\prime}|\leqslant C^{\prime\prime}|\kappa_{n}|$. Let $C$ be any
constant such that

$|\kappa_{n}^{\prime}|\leqslant C(\beta_{1}/\beta_{2})^{n}$

for all $n\in{\mathbb{N}}$. Choose $\delta_{2}^{\prime}\in(0,\delta_{2}]$ such
that

$\rho:=\frac{\beta_{1}}{\beta_{2}\inf_{U\in{\mathcal{U}}(\delta_{2}^{\prime})}\lambda_{U}}<1,$

which is possible by (2.26), and such that
$\inf_{U\in{\mathcal{U}}(\delta_{2}^{\prime})}\lambda_{U}\geqslant\beta_{2}$.
Let $c$ be given by Proposition 3.1. Let $N$ be sufficiently large that
$C\rho^{N}<c\beta_{2}$. We claim that there exists $c^{\prime}>0$ and
$0<\delta_{2}^{\prime}\leqslant\delta_{2}$ such that for all
$U\in{\mathcal{U}}(\delta_{2}^{\prime})$ with $N_{U}:=1/\mu(U)>N$,

$1-\sum_{k=0}^{N_{U}-1}\frac{\mu(E_{U}^{k})}{\mu(U)}+\kappa_{N_{U}}^{\prime}\geqslant
c^{\prime}.$ (4.4)

To see this note that the left hand side of (4.4) equals

$\displaystyle
1-\sum_{k=0}^{N_{U}-1}\frac{\mu(E_{U}^{k})}{\mu(U)}+\kappa_{N_{U}}^{\prime}$
$\displaystyle=1-\frac{\mu(x\in U:\tau_{U}(x)\leqslant
N_{U})}{\mu(U)}+\kappa_{N_{U}}^{\prime}=1-\mu_{U}(\tau_{U}\leqslant
N_{U})+\kappa_{N_{U}}^{\prime}$ $\displaystyle=\mu_{U}(\tau_{U}\geqslant
N_{U}+1)+\kappa_{N_{U}}^{\prime}.$

By Proposition 3.1, $\mu_{U}(\tau_{U}\geqslant N_{U}+1)\geqslant
c\lambda_{U}^{N_{U}+1}$ therefore

$\mu_{U}(\tau_{U}\geqslant N_{U}+1)+\kappa_{N_{U}}^{\prime}\geqslant
c\lambda_{U}^{N_{U}+1}+\kappa_{N_{U}}^{\prime}\geqslant\lambda_{U}^{N_{U}}(c\lambda_{U}-C\left(\beta_{1}/\beta_{2}\lambda_{U}\right)^{N_{U}}).$

All of this implies that for all $U\in{\mathcal{U}}(\delta_{2}^{\prime})$,

$1-\sum_{k=0}^{N_{U}-1}q_{k,U}+\kappa_{N_{U}}^{\prime}\geqslant\lambda_{U}^{N_{U}}(c\beta_{2}-C\rho^{N_{U}})>0,$

proving (4.4). Finally, we choose $0<\delta_{3}\leqslant\delta_{2}^{\prime}$
sufficiently small that the denominator in (4.3),

$\inf_{U\in{\mathcal{U}}(\delta_{3})}(1+O(\eta_{U}))(1+N_{U}O(\eta_{U}))>0$

(possible since $\eta_{U}\leqslant 1/m(U)$ and noting that it is clearly
uniformly bounded above too) and such that the numerator

$\inf_{U\in{\mathcal{U}}(\delta_{3})}\left(1-\sum_{k=0}^{N_{U}-1}\lambda_{U}^{-k}q_{k,U}\right)+\kappa_{N_{U}}^{\prime}>0$

which is possible by (4.4) and (2.26). By (4.3) this completes the proof of
the proposition. ∎

###### Proof of Theorem 4.1.

Since

$\mathbb{E}(\tau_{U})=\sum_{n\geqslant 1}\mu(\tau_{U}\geqslant
n)=\sum_{n\geqslant
1}\int\mathring{\mathcal{L}}_{U}^{n}(g)\leavevmode\nobreak\ dm,$

it follows from Lemma 4.2 that for all $r\in(0,\delta_{2}]$ and
$U\in{\mathcal{U}}(\delta_{2}^{*})$,

$\frac{c}{1-\lambda_{U}}\leqslant\mathbb{E}(\tau_{U})\leqslant\frac{C}{1-\lambda_{U}}$

for some uniform constants $0<c<C$. Take
$\delta_{3}^{*}=\min\\{\delta_{2}^{*},\delta_{3}\\}$ where $\delta_{3}$ is
given by Proposition 4.3. The proof now follows from Proposition 4.3. ∎

##  5\. Expected cover time: uniformly hyperbolic case

In this section we prove Theorems 2.1 and 2.2. This will be done by
generalising the ‘Matthews method’ for Markov chains (see [M] or [LP, Chapter
11]) which will establish a relationship between the expected cover time and
the expected hitting times, at which point we can apply our estimates from §4.
Recall from §2 that there exists a subshift $\sigma:\Sigma\to\Sigma$ and a
projection $\Pi:\Sigma\to I$ such that $f\circ\Pi=\Pi\circ\sigma$. Further
recall that there exists a quasi-Bernoulli measure $\tilde{\mu}$ on $\Sigma$
such that $\Pi_{*}\tilde{\mu}=\mu$. In this section we will primarily work
with symbolic versions of cover and hitting times, which we describe below.

Let $\mathcal{P}$ be a finite set of subsets of $\Sigma$ where (a) for each
$P\in\mathcal{P}$, there exists a finite or countable set of words
$P^{*}\subset\Sigma^{*}$ such that $P=\bigcup_{\mathbf{i}\in
P^{*}}[\mathbf{i}]$, and (b) for distinct $P,Q\in\mathcal{P}$, $P\cap
Q=\emptyset$.666Note that here we only require disjointness as subsets of
$\Sigma$, rather than disjointness of their $\Pi$-projections to
${\mathbb{R}}$. Note that $\mathcal{P}$ is not necessarily a partition of
$\Sigma$ since there is no requirement that
$\bigcup_{P\in\mathcal{P}}P=\Sigma$. We will call $\mathcal{P}$ a subpartition
of $\Sigma$ if it satisfies (a) and (b). For $\mathbf{i}\in\Sigma$ we let
$\tau_{\mathcal{P}}(\mathbf{i})$ denote the first time $n$ that
$\\{\mathbf{i},\sigma(\mathbf{i}),\ldots,\sigma^{n}(\mathbf{i})\\}$ has
visited every element in $\mathcal{P}$. For $P\in\mathcal{P}$ we let
$\tau_{P}:\Sigma\to{\mathbb{N}}_{0}\cup\\{\infty\\}$ be defined as

$\tau_{P}(\mathbf{i})=\inf\\{n\geq 0:\sigma^{n}(\mathbf{i})\in P\\}$

i.e. the first $n\geq 0$ such that $\sigma^{n}(\mathbf{i})$ begins with a word
in $P^{*}$.

######  Remark 5.1.

Since $\tau_{P}$ may take the value 0, strictly speaking $\tau_{P}$ is not a
hitting time in the same sense as (1.4). Let us briefly write
$\tilde{\tau}_{P}(\mathbf{i})=\inf\\{n\geq 1:\sigma^{n}(\mathbf{i})\in P\\}$.
Then

$\\{\mathbf{i}\in\Sigma:\tilde{\tau}_{P}(\mathbf{i})=n\\}=\sigma^{-1}(\\{\mathbf{i}\in\Sigma:\tau_{P}(\mathbf{i})=n-1\\}),$

implying in particular that
$\mathbb{E}_{\tilde{\mu}}(\tau_{P})=\mathbb{E}_{\tilde{\mu}}(\tilde{\tau}_{P})$.
Hence, slightly abusing notation, we will still refer to $\tau_{P}$ as the
hitting time throughout this section. The fact that the expectations coincide
along with the fact that $\Pi_{*}\tilde{\mu}=\mu$, $\Pi\circ\sigma=f\circ\Pi$
and non-uniquely coded points have zero measure, we have
$\mathbb{E}_{\tilde{\mu}}(\tau_{P})=\mathbb{E}_{\mu}(\tau_{\Pi(P)})$.

We need to set up some notation and obtain some preliminary results. Let
$\mathcal{P}=\\{P_{1},\ldots,P_{N}\\}$ be a subpartition of $\Sigma$ and given
a permutation $s$ of $\\{1,\ldots,N\\}$ and $2\leqslant k\leqslant N$, let
$A_{s,k}\subset\Sigma$ be the set of points which visit $P_{s(k)}$ for the
first time after $P_{s(1)},\ldots,P_{s(k-1)}$ have all been visited. That is,
denoting $\tau_{s(k)}\equiv\tau_{P_{s(k)}}$ and $\tau_{s(1)}^{s(k-1)}$ to be
the first time $n\in{\mathbb{N}}_{0}$ that $P_{s(1)},\ldots,P_{s(k-1)}$ have
all been visited by
$\\{\mathbf{i},\sigma(\mathbf{i}),\ldots,\sigma^{n}(\mathbf{i})\\}$, we have

$\tau_{s(k)}(\mathbf{i})>\tau_{s(1)}^{s(k-1)}(\mathbf{i})$

for $\mathbf{i}\in A_{s,k}$.

Let $\mathbb{P}$ be the uniform measure on the set of all permutations $s\in
S_{N}$ of $\\{1,\ldots,N\\}$.

######  Lemma 5.2.

Let $\mathcal{P}$ be a subpartition of $\Sigma$ and $A_{s,k}$ and $\mathbb{P}$
be as above. Then

$\int\tilde{\mu}(A_{s,k})d\mathbb{P}=\frac{1}{k}.$ (5.1)

###### Proof.

Fix $2\leqslant k\leqslant N$. For each $s\in S_{N}$ consider the unordered
set $\\{s(1),\ldots,s(k)\\}$. Note that there are
$\frac{N(N-1)\cdots(N-(k-1))}{k!}$ possible values. For each possible value
$\\{i_{1},\ldots,i_{k}\\}\subset\\{1,\ldots,N\\}$ that this set can take, let
$S_{N}(\\{i_{1},\ldots,i_{k}\\})$ denote the set of all $s$ for which
$\\{s(1),\ldots,s(k)\\}=\\{i_{1},\ldots,i_{k}\\}$, thinking of these as
unordered sets.

Next, we can further separate each $S_{N}(\\{i_{1},\ldots,i_{k}\\})$ into $k$
subsets $S_{N}^{i_{j}}(\\{i_{1},\ldots,i_{k}\\})$, $(1\leqslant j\leqslant
k)$, which determines the set of all $s\in S_{N}(\\{i_{1},\ldots,i_{k}\\})$
for which $s(k)=i_{j}$. Note that each
$S_{N}^{i_{j}}(\\{i_{1},\ldots,i_{k}\\})$ contains $(N-k)!(k-1)!$
permutations, corresponding to $(N-k)!$ ways to order the last $N-k$ terms and
and $(k-1)!$ ways to arrange the first $k-1$ terms. Over each $s\in
S_{N}^{i_{j}}(\\{i_{1},\ldots,i_{k}\\})$, the set $A_{s,k}$ is constant. If
for each $1\leqslant j\leqslant k$ we choose a representative $s_{j}\in
S_{N}^{i_{j}}(\\{i_{1},\ldots,i_{k}\\})$ then since the sets in
${\mathcal{P}}$ are pairwise disjoint, it follows that
$\\{A_{s_{j},k}\\}_{j=1}^{k}$ are pairwise disjoint and
$\bigcup_{j=1}^{k}A_{s_{j},k}=\Sigma$.

Hence for any choice of $\\{i_{1},\ldots,i_{k}\\}\subset\\{1,\ldots,N\\}$,

$\displaystyle\int_{S_{N}(\\{i_{1},\ldots,i_{k}\\})}\tilde{\mu}(A_{s,k})d\mathbb{P}=\sum_{n=1}^{k}\frac{(k-1)!(N-k)!}{N!}\tilde{\mu}(A_{s_{j},k}),$
(5.2)

where the factor $\frac{1}{N!}$ comes from the fact that $\mathbb{P}$ is
uniformly distributed. Now, since $\bigcup_{j=1}^{k}A_{s_{j},k}=\Sigma$ and
$\\{A_{s_{j},k}\\}_{j=1}^{k}$ are pairwise disjoint we have

$\tilde{\mu}(A_{s_{k},k})=1-\sum_{j=1}^{k-1}\tilde{\mu}(A_{s_{j},k})$

and substituting this into (5.2) we obtain

$\displaystyle\int_{S_{N}(\\{i_{1},\ldots,i_{k}\\})}\\!\\!\tilde{\mu}(A_{s,k})d\mathbb{P}$
$\displaystyle=\sum_{j=1}^{k-1}\frac{(k-1)!(N-k)!}{N!}\tilde{\mu}(A_{s_{j},k})+\frac{(k-1)!(N-k)!}{N!}\Big{(}1-\sum_{j=1}^{k-1}\tilde{\mu}(A_{s_{j},k})\Big{)}$
$\displaystyle=\frac{(k-1)!(N-k)!}{N!}.$

Therefore,

$\int_{S_{N}}\tilde{\mu}(A_{s,k})d\mathbb{P}=\frac{N(N-1)\cdots(N-(k-1))}{k!}\cdot\frac{(k-1)!(N-k)!}{N!}=\frac{1}{k}.$

∎

We are now ready to prove Theorems 2.1 and 2.2. Note that the upper bound in
Theorem 2.1 is just a special case of the upper bounds in Theorem 2.2 (by
using (2.11) and that $g=d\mu/dm$ is strictly positive on $\Lambda$), hence it
suffices to prove the upper bound in Theorem 2.2.

###### Proof of upper bound in Theorem 2.2.

For each $\delta>0$ consider the set of closed intervals
${\mathcal{U}}_{\delta}$ given by (U). Recall that for any
$U\in{\mathcal{U}}_{\delta}$, there exists $x\in\Lambda$ such that
$B(x,t\delta)\subseteq U\subseteq B(x,T\delta)$ for some uniform constants $t$
and $T$. Let $\mathcal{P}_{\delta}$ be the subpartition

$\mathcal{P}_{\delta}=\left\\{\mathrm{int}(\Pi^{-1}(U))\;:\;U\in{\mathcal{U}}_{\delta}\right\\}$
(5.3)

where $\mathrm{int}$ is taking the interior inside $\Sigma$. This ensures
$\mathcal{P}_{\delta}$ is a subpartition (by ensuring a set in
$\mathcal{P}_{\delta}$ cannot contain any isolated points in the cylinder sets
topology and guarantees pairwise disjointness of sets in
$\mathcal{P}_{\delta}$).

By (U)(a) and (U)(c), if
$\\{\mathbf{i},\sigma(\mathbf{i}),\ldots,\sigma^{n}(\mathbf{i})\\}$ has
visited each element in ${\mathcal{P}}_{\delta/2T}$ then
$\\{x,f(x),\ldots,f^{n}(x)\\}$ is $\delta$-dense, hence

$\mathbb{E}_{\mu}(\tau_{\delta})\leqslant\mathbb{E}_{\tilde{\mu}}(\tau_{\mathcal{P}_{\delta/2T}}).$
(5.4)

Now, fix $\delta$ and fix ${\mathcal{P}}=\mathcal{P}_{\delta/2T}$. Let
$L=\max_{\mathbf{i}\in{\mathcal{P}}}|\mathbf{i}|$, so that
$L=O(\log(1/\delta))$ by (U)(e). We order
${\mathcal{P}}=\\{P_{1},\ldots,P_{N}\\}$ and let $\mathbb{P}$ be the uniform
measure on the set of permutations $S_{N}$. We have

$\displaystyle\int\tau_{\mathcal{P}}d\tilde{\mu}$ $\displaystyle=$
$\displaystyle\int\int\tau_{s(1)}^{s(N)}d\tilde{\mu}d\mathbb{P}=\int\int\tau_{s(1)}d\tilde{\mu}d\mathbb{P}+\sum_{k=2}^{N}\int\int\tau_{s(1)}^{s(k)}-\tau_{s(1)}^{s(k-1)}d\tilde{\mu}d\mathbb{P}$
(5.5) $\displaystyle=$
$\displaystyle\int\int\tau_{s(1)}d\tilde{\mu}d\mathbb{P}+\sum_{k=2}^{N}\int\int_{A_{s,k}}\tau_{s(k)}-\tau_{s(1)}^{s(k-1)}d\tilde{\mu}d\mathbb{P}.$

Fix $s\in S_{N}$. Let $A_{s,k}^{*}$ denote the set of all finite words
$\mathbf{i}=i_{0}\ldots i_{n}\in\Sigma^{*}$ for which (a) for all $1\leqslant
j\leqslant k-1$, $\mathbf{i}$ contains at least one word from $P_{s(j)}$, and
we let $0\leqslant n_{j}\leqslant n-L$ denote the index at which the first
word from $P_{s(j)}$ begins (so that $i_{n_{j}}$ is the first digit of this
word) (b) for $\ell\leqslant\max_{1\leqslant j\leqslant k-1}n_{j}$,
$\mathbf{i}$ does not contain any word from $P_{s(k)}$ beginning at $i_{\ell}$
and (c) $|\mathbf{i}|=L+\max_{1\leqslant j\leqslant k-1}n_{j}$. Note that
$A_{s,k}=\bigcup_{\mathbf{i}\in A_{s,k}^{*}}[\mathbf{i}]$. For $\mathbf{i}\in
A_{s,k}^{*}$ let $B_{\mathbf{i},s,k}$ denote the set of all finite words
$\mathbf{j}\in\Sigma^{*}$ for which $\mathbf{i}\mathbf{j}\in\Sigma^{*}$ and
$\mathbf{j}$ ends in the first occurrence of a word from $P_{s(k)}$. Given
$\mathbf{j}\in B_{\mathbf{i},s,k}$ let $\mathbf{j}_{s(k)}\in P_{s(k)}$ denote
the word that $\mathbf{j}$ ends in. Also, let $B_{s,k}$ denote the set of all
finite words $\mathbf{j}\in\Sigma^{*}$ which end in the first occurrence of a
word from $P_{s(k)}$. Then

$\int_{A_{s,k}}\tau_{s(k)}-\tau_{s(1)}^{s(k-1)}d\tilde{\mu}\leqslant\sum_{\mathbf{i}\in
A_{s,k}^{*}}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{i}\mathbf{j}])(|\mathbf{j}|+L-|\mathbf{j}_{s(k)}|).$

Then by the quasi-Bernoulli property (a6) we have

$\displaystyle\sum_{\mathbf{i}\in A_{s,k}^{*}}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{i}\mathbf{j}])(|\mathbf{j}|+L-|\mathbf{j}_{s(k)}|)$
$\displaystyle\leqslant$ $\displaystyle C_{*}\sum_{\mathbf{i}\in
A_{s,k}^{*}}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{i}])\tilde{\mu}([\mathbf{j}])(|\mathbf{j}|+L-|\mathbf{j}_{s(k)}|)$
$\displaystyle\leqslant$ $\displaystyle
C_{*}\tilde{\mu}(A_{s,k})\sum_{\mathbf{j}\in
B_{s,k}}\tilde{\mu}([\mathbf{j}])(|\mathbf{j}|+L-|\mathbf{j}_{s(k)}|)$
$\displaystyle\leqslant$ $\displaystyle
C\tilde{\mu}(A_{s,k})(\mathbb{E}_{\tilde{\mu}}(\tau_{s(k)}+2L)).$

To see the final inequality, we use that
$|\tau_{s(k)}^{\prime\prime}-\tau_{s(k)}|\leqslant L$ where, denoting
$\tau_{s(k)}^{\prime}(\mathbf{i})$ to be the first time $n\in{\mathbb{N}}$
that $\mathbf{i}|_{n}$ ends in a word from $P_{s(k)}$,
$\tau_{s(k)}^{\prime\prime}(\mathbf{i})$ denotes the time $n^{\prime}\leqslant
n$ that this word from $P_{s(k)}$ begins. Putting back into (5.5) and using
$L=O(\log(1/\delta))$ we get

$\displaystyle\int\tau_{\mathcal{P}}d\tilde{\mu}$ $\displaystyle\leqslant
C(\log(1/\delta)+\max_{1\leqslant m\leqslant
N}\mathbb{E}_{\tilde{\mu}}(\tau_{m}))\left(1+\sum_{k=2}^{N}\int\tilde{\mu}(A_{s,k})d\mathbb{P}\right)$
$\displaystyle=C\left(\log(1/\delta)+\max_{1\leqslant m\leqslant
N}\mathbb{E}_{\mu}(\tau_{\Pi(P_{m})})\right)(1+1/2+\cdots+1/N)$

by Lemma 5.2 and Remark 5.1. Note that $N\leqslant C/\delta$. Using this, we
obtain that

$\displaystyle\mathbb{E}_{\mu}(\tau_{\delta})$ $\displaystyle\leqslant
C\left(\max_{U\in{\mathcal{U}}_{\delta/2T}}\frac{1}{\mu(U)}\log\left(1/\delta\right)+(\log(1/\delta))^{2}\right)$
$\displaystyle\leqslant
C\left(\frac{1}{\min_{x\in\Lambda}\mu(B(x,t\delta/2T))}\log\left(1/\delta\right)+(\log(1/\delta))^{2}\right)\leqslant\frac{C}{M_{\mu}(t\delta/2T)}\log\left(1/\delta\right)$

where in the first inequality we have used (5.4), Theorem 4.1 and the fact
that $\mu$ is non-atomic, and in the second we have used (U)(a). In the
specific setting that (2.11) holds, similarly

$\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\left(\max_{U\in{\mathcal{U}}_{t\delta/2T}}\frac{1}{\mu(U)}\log\left(1/\delta\right)+(\log(1/\delta))^{2}\right)\leqslant\frac{C}{\delta^{s_{f}}}\log\left(1/\delta\right)$

where again we have used (U)(a) to conclude that
$\max_{U\in{\mathcal{U}}_{\delta/2T}}\frac{1}{\mu(U)}\leqslant\max_{x\in\Lambda}\frac{1}{\mu(B(x,t\delta/2T))}$
and (2.11) for the second inequality. ∎

Now we prove the lower bounds in Theorems 2.1 and 2.2. The lower bound in the
first displayed equation in Theorem 2.1 is a special case of the lower bound
in Theorem 2.2. Therefore, we will first prove the lower bound from Theorem
2.2 and then proceed to prove the lower bound from the second displayed
equation in Theorem 2.1.

###### Proof of lower bounds in Theorem 2.1 and 2.2.

We begin by proving the lower bound from Theorem 2.2. Define $P_{\delta}$ as
in (5.3). Note that if $\\{x,f(x),\ldots,f^{n}(x)\\}$ is $\delta$-dense then
it necessarily visits every ball centred at a point in $\Lambda$ of radius
greater than or equal to $\delta$ hence
$\\{\mathbf{i},\sigma(\mathbf{i}),\ldots,\sigma^{n}(\mathbf{i})\\}$ has
visited each element in $\mathcal{P}_{2\delta/t}$ by (U)(a) and (U)(b). Hence

$\mathbb{E}_{\mu}(\tau_{\delta})\geqslant\mathbb{E}_{\tilde{\mu}}(\tau_{\mathcal{P}_{2\delta/t}}).$

Moreover, for each $P\in\mathcal{P}_{2\delta/t}$,

$\mathbb{E}_{\tilde{\mu}}(\tau_{\mathcal{P}_{2\delta/t}})\geqslant\mathbb{E}_{\tilde{\mu}}(\tau_{P})=\mathbb{E}_{\mu}(\tau_{\Pi(P)})\geqslant\frac{c}{\mu(\Pi(P))}$

where we have used Remark 5.1 to justify the equality of expectations. Since
some $U=\Pi(P)\in{\mathcal{U}}_{2\delta/t}$ must belong to the ball of minimum
measure at scale $2T\delta/t$ we have

$\mathbb{E}_{\mu}(\tau_{\delta})\geqslant\frac{c}{\min_{x\in\Lambda}\mu(B(x,2T\delta/t))}=\frac{c}{M_{\mu}(2T\delta/t)}$

proving the lower bound from Theorem 2.2.

Next, we prove the lower bound which appears in the second displayed equation
in Theorem 2.1. In particular, we are now additionally assuming (2.11) holds,
$f$ is Markov and $f$ has at least 2 full branches, moreover Proposition 2.4
is applicable. Since $f$ is Markov, it is useful to keep in mind that for
$\mathbf{i},\mathbf{j}\in\Sigma^{*}$ the legality of concatenations
$\mathbf{i}\mathbf{j}$ will be equivalent to the legality of concatenating the
last digit of $\mathbf{i}$ with the first digit of $\mathbf{j}$. For each
$\delta$ sufficiently small consider the set $\mathcal{V}_{\delta}$ given by
Proposition 2.4. Define

$\mathcal{Q}_{\delta}=\left\\{[wab^{n_{3}}]\;:\Pi([wab^{n_{3}}])\in\mathcal{V}_{\delta}\right\\}\subset\\{[wab^{n_{3}}]:w\in\\{a,b\\}^{*}\\}$

noting that $\mathcal{Q}_{\delta}$ is a subpartition since sets in
${\mathcal{V}}_{\delta}$ are pairwise disjoint. Note that if
$\\{x,f(x),\ldots,f^{n}(x)\\}$ is $\delta$-dense then it necessarily visits
every ball centred at a point in $\Lambda$ of radius greater than or equal to
$\delta$ hence by (U)(a) and (U)(c)
$\\{\mathbf{i},\sigma(\mathbf{i}),\ldots,\sigma^{n}(\mathbf{i})\\}$ has
visited each element in ${\mathcal{Q}}_{2\delta/t}$. Hence

$\mathbb{E}_{\mu}(\tau_{\delta})\geqslant\mathbb{E}_{\tilde{\mu}}(\tau_{\mathcal{Q}_{2\delta/t}}).$
(5.6)

Now, fix $\delta$ and fix ${\mathcal{Q}}=\mathcal{Q}_{2\delta/t}$. Write
${\mathcal{Q}}=\\{[\mathbf{i}_{1}],\ldots,[\mathbf{i}_{M}]\\}$ and let
$\mathbb{P}$ be the uniform measure on the set of permutations $S_{M}$. Let
$A_{s,k}\subset\Sigma$ be the set of points which visit $[\mathbf{i}_{s(k)}]$
for the first time after $[\mathbf{i}_{s(1)}],\ldots,[\mathbf{i}_{s(k-1)}]$
have all been visited. For brevity we write
$\tau_{s(k)}\equiv\tau_{[\mathbf{i}_{s(k)}]}$ and $\tau_{s(1)}^{s(k-1)}$ to be
the first time that $[\mathbf{i}_{s(1)}],\ldots,[\mathbf{i}_{s(k-1)}]$ have
all been visited. Then

$\displaystyle\int\tau_{\mathcal{Q}}d\tilde{\mu}$ $\displaystyle=$
$\displaystyle\int\int\tau_{s(1)}^{s(M)}d\tilde{\mu}d\mathbb{P}\int\int\tau_{s(1)}d\tilde{\mu}d\mathbb{P}+\sum_{k=2}^{M}\int\int\tau_{s(1)}^{s(k)}-\tau_{s(1)}^{s(k-1)}d\tilde{\mu}d\mathbb{P}$
(5.7) $\displaystyle=$
$\displaystyle\int\int\tau_{s(1)}d\tilde{\mu}d\mathbb{P}+\sum_{k=2}^{M}\int\int_{A_{s,k}}\tau_{s(k)}-\tau_{s(1)}^{s(k-1)}d\tilde{\mu}d\mathbb{P}.$

Fix $s\in S_{M}$. Let $A_{s,k}^{*}$ denote the set of all finite words
$\mathbf{i}\in\Sigma^{*}$ for which (a) $\mathbf{i}$ contains every word in
$\\{\mathbf{i}_{s(1)},\ldots,\mathbf{i}_{s(k-1)}\\}$ (b) $\mathbf{i}$ does not
contain the word $\mathbf{i}_{s(k)}$ and (c) for some $1\leqslant i\leqslant
k-1$, $\mathbf{i}$ ends in the first occurrence of the word
$\mathbf{i}_{s(i)}$. In particular, $A_{s,k}=\bigcup_{\mathbf{i}\in
A_{s,k}^{*}}[\mathbf{i}]$ by Proposition 2.4(g).

Let $B_{\mathbf{i},s,k}$ denote the set of all finite words
$\mathbf{j}\in\Sigma^{*}$ for which $\mathbf{i}\mathbf{j}$ ends in the first
occurrence of the word $\mathbf{i}_{s(k)}$. Note that since $\mathbf{i}$ ends
with a digit in $\\{a,b\\}$ and the system is Markov, necessarily
$\mathbf{i}\mathbf{j}\in\Sigma^{*}$. Then by the (lower) quasi-Bernoulli
property (a6),

$\displaystyle\int_{A_{s,k}}\tau_{s(k)}-\tau_{s(1)}^{s(k-1)}d\tilde{\mu}$
$\displaystyle=$ $\displaystyle\sum_{\mathbf{i}\in
A_{s,k}^{*}}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{i}\mathbf{j}])(|\mathbf{i}_{s(i)}|+|\mathbf{j}|-|\mathbf{i}_{s(k)}|)$
(5.8) $\displaystyle\geqslant$ $\displaystyle 1/C_{*}\sum_{\mathbf{i}\in
A_{s,k}^{*}}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{i}])\tilde{\mu}([\mathbf{j}])(|\mathbf{i}_{s(i)}|+|\mathbf{j}|-|\mathbf{i}_{s(k)}|)$
$\displaystyle\geqslant$
$\displaystyle\tilde{\mu}(A_{s,k})/C_{*}\inf_{\mathbf{i}\in
A_{s,k}^{*}}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{j}])(|\mathbf{i}_{s(i)}|+|\mathbf{j}|-|\mathbf{i}_{s(k)}|).$

Note that

$\mathbb{E}_{\mathbf{i}_{s(i)}}(\tau_{s(k)})=\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\frac{\tilde{\mu}([\mathbf{i}_{s(i)}\mathbf{j}])}{\tilde{\mu}([\mathbf{i}_{s(i)}])}(|\mathbf{i}_{s(i)}|+|\mathbf{j}|-|\mathbf{i}_{s(k)}|)\leqslant
C_{*}\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{j}])(|\mathbf{i}_{s(i)}|+|\mathbf{j}|-|\mathbf{i}_{s(k)}|),$
(5.9)

where we are using $\mathbb{E}_{\mathbf{i}_{s(i)}}$ to denote the expectation
(with respect to $\tilde{\mu}$) conditioned to $[\mathbf{i}_{s(i)}]$.

Let $L=\max_{\mathbf{i}\in{\mathcal{Q}}}|\mathbf{i}|$, noting that
$L=O(\log(1/\delta))$ by Proposition 2.4(f). Consider the function

$w_{s(k),n}(x):=\inf\\{m\geqslant n:\sigma^{m}(x)\in[\mathbf{i}_{s(k)}]\\}.$

Denote $w_{s(k),s(i)}=w_{s(k),|\mathbf{i}_{s(i)}|}$. Observe that on
$[\mathbf{i}_{s(i)}]$,

$w_{s(k),s(i)}\leqslant\tau_{s(k)}+\sum_{\ell=1}^{L}\mathbf{1}_{\\{\tau_{s(k)}=|\mathbf{i}_{s(i)}|+\ell-|\mathbf{i}_{s(k)}|\\}}(w_{s(k),|\mathbf{i}_{s(i)}|+\ell}+\ell),$

therefore

$\mathbb{E}_{\mathbf{i}_{s(i)}}(w_{s(k),s(i)})\leqslant\mathbb{E}_{\mathbf{i}_{s(i)}}(\tau_{s(k)})+\sum_{\ell=1}^{L}\mathbb{E}_{\mathbf{i}_{s(i)}}(\mathbf{1}_{\\{\tau_{s(k)}=|\mathbf{i}_{s(i)}|+\ell-|\mathbf{i}_{s(k)}|\\}}(w_{s(k),|\mathbf{i}_{s(i)}|+\ell}+\ell)).$
(5.10)

Let $C_{s(i),s(k),\ell}\subset\Sigma_{\ell}$ be the set of words $\mathbf{k}$
such that $\mathbf{i}_{s(i)}\mathbf{k}$ ends with the first occurence of the
word $\mathbf{i}_{s(k)}$ (note that necessarily
$\mathbf{i}_{s(i)}\mathbf{k}\in\Sigma^{*}$ since
$\mathbf{i}_{s(i)}\in\\{a,b\\}^{*}$) and let
$C_{s(i),s(k)}=\bigcup_{\ell=1}^{L}C_{s(i),s(k),\ell}$. Let let $D_{s(k)}$
denote the set of words $\mathbf{j}$ such that $\mathbf{j}$ ends with the
first occurrence of the word $\mathbf{i}_{s(k)}$. Define

$P_{s(i),s(k)}=\sum_{\mathbf{\mathbf{k}}\in
C_{s(i),s(k)}}\tilde{\mu}([\mathbf{k}])\;\;\textnormal{and}\;\;P_{s(i),s(k),\ell}=\sum_{\mathbf{\mathbf{k}}\in
C_{s(i),s(k),\ell}}\tilde{\mu}([\mathbf{k}])$

Note that for any choice of permutation $s$, $P_{s(i),s(k)}\leqslant
C_{*}\tilde{\mu}[ab^{n_{3}}]K$. To see this, write
$\mathbf{i}_{s(k)}=u_{1}\ldots u_{n}ab^{n_{3}}$, thus

$\displaystyle P_{s(i),s(k)}$
$\displaystyle\leqslant\tilde{\mu}[ab^{n_{3}}]+\tilde{\mu}[u_{n}ab^{n_{3}}]+\cdots+\tilde{\mu}[u_{1}\ldots
u_{n}ab^{n_{3}}]\leqslant C_{*}\tilde{\mu}[ab^{n_{3}}]K.$

In particular $r:=C_{*}^{3}P_{s(i),s(k)}<1$ by Proposition 2.4(a).

$\displaystyle\mathbb{E}_{\mathbf{i}_{s(i)}}\left(\mathbf{1}_{\\{\tau_{s(k)}=|\mathbf{i}_{s(i)}|+\ell-|\mathbf{i}_{s(k)}|\\}}(w_{s(k),|\mathbf{i}_{s(i)}|+\ell}+\ell)\right)$
$\displaystyle=\sum_{\mathbf{k}\in C_{s(i),s(k),\ell}}\sum_{\mathbf{j}\in
D_{s(k)}}\frac{\tilde{\mu}([\mathbf{i}_{s(i)}\mathbf{k}\mathbf{j}])}{\tilde{\mu}([\mathbf{i}_{s(i)}])}(\ell+|\mathbf{j}|-|\mathbf{i}_{s(k)}|)$
$\displaystyle\leqslant C_{*}^{3}\sum_{\mathbf{k}\in
C_{s(i),s(k),\ell}}\tilde{\mu}([\mathbf{k}])\sum_{\mathbf{j}\in
D_{s(k)}}\frac{\tilde{\mu}([\mathbf{i}_{s(i)}\mathbf{j}])}{\tilde{\mu}([\mathbf{i}_{s(i)}])}(\ell+|\mathbf{j}|-|\mathbf{i}_{s(k)}|)$
$\displaystyle\leqslant
C_{*}^{3}P_{s(i),s(k),\ell}\mathbb{E}_{\mathbf{i}_{s(i)}}(w_{s(k),s(i)}+L).$

So by (5.10)

$\mathbb{E}_{\mathbf{i}_{s(i)}}(\tau_{s(k)})\geqslant\mathbb{E}_{\mathbf{i}_{s(i)}}(w_{s(k),s(i)})(1-C_{*}^{3}P_{s(i),s(k)})-C_{*}^{3}P_{s(i),s(k)}L.$
(5.11)

Moreover

$\displaystyle\mathbb{E}_{\mathbf{i}_{s(i)}}(w_{s(k),s(i)})$
$\displaystyle=\sum_{\mathbf{j}\in
D_{s(k)}}\frac{\tilde{\mu}([\mathbf{i}_{s(i)}\mathbf{j}])}{\tilde{\mu}([\mathbf{i}_{s(i)}])}(|\mathbf{j}|-|\mathbf{i}_{s(k)}|)$
$\displaystyle\geqslant\frac{1}{C_{*}}\sum_{\mathbf{j}\in
D_{s(k)}}\tilde{\mu}([\mathbf{j}])(|\mathbf{j}|-|\mathbf{i}_{s(k)}|)=\frac{1}{C_{*}}\mathbb{E}_{\tilde{\mu}}(\tau_{s(k)}).$
(5.12)

So by (5.9), (5.11) and (5.12),

$\displaystyle\sum_{\mathbf{j}\in
B_{\mathbf{i},s,k}}\tilde{\mu}([\mathbf{j}])(|\mathbf{i}_{s(i)}|+|\mathbf{j}|-|\mathbf{i}_{s(k)}|)$
$\displaystyle\geqslant\frac{1}{C_{*}}\mathbb{E}_{\mathbf{i}_{s(i)}}(\tau_{s(k)})$
$\displaystyle\geqslant\frac{1}{C_{*}}\mathbb{E}_{\mathbf{i}_{s(i)}}(w_{s(k),s(i)})(1-C_{*}^{3}P_{s(i),s(k)})-C_{*}^{2}P_{s(i),s(k)}L$
$\displaystyle\geqslant\frac{1}{C_{*}^{2}}\mathbb{E}_{\tilde{\mu}}(\tau_{s(k)})(1-C_{*}^{3}P_{s(i),s(k)})-C_{*}^{2}P_{s(i),s(k)}L\geqslant\frac{1-r}{C_{*}^{2}}\mathbb{E}_{\tilde{\mu}}(\tau_{s(k)})-rL.$

Finally, substituting this into (5.8) and applying (5.7),

$\displaystyle\mathbb{E}_{\mu}(\tau_{\delta})$
$\displaystyle\geqslant\left(\frac{1-r}{C_{*}^{2}}\min_{1\leqslant m\leqslant
M}\mathbb{E}_{\tilde{\mu}}(\tau_{m})-rL\right)(1+1/2+\cdots+1/M)$
$\displaystyle\geqslant
c\min_{U\in{\mathcal{V}}_{2\delta/t}}\frac{1}{\mu(U)}\log(1/\delta)=\frac{c}{\delta^{s_{f}}}\log(1/\delta)$

where in the first line we have used (5.6) and Lemma 5.2 and in the second we
have used Remark 5.1, the fact that $L=O(\log(1/\delta))$, Proposition 2.4(c)
to bound $M\geqslant c\delta^{-\varepsilon}$ as well as Theorem 4.1, (2.11),
Proposition 2.4(d) and the fact that $g=d\mu/dm<\infty$ on $\Lambda$.

∎

##  6\. Expected cover time: non-uniformly hyperbolic case

In this section we consider some cases where the system $f:I\to I$ does not
satisfy our standard assumptions (a1)-(a6),(2.8)-(2.10). By considering a
first return map (to a subset of $I$) which satisfies (a1)-(a6),
,(2.8)-(2.10), we will be able to recover results on the expected cover time
for the original system.

Let $f:I\to I$ with a conformal measure $m$ and invariant probability measure
$\mu$ which is absolutely continuous with respect to $m$. Given an interval
$Y\subset I$ with $\mu(Y)>0$ we define $F=f^{\tau_{Y}}:Y\to Y$ be the first
return map to $Y$ and define $\mu_{Y}=\frac{1}{\mu(Y)}\mu|_{Y}$.

For $x\in Y$ let $R_{n}(x)=\sum_{i=0}^{n-1}\tau_{Y}\circ F^{i}(x)$ denote the
$n$th return time of $x$ to $Y$. By Kac theorem, for $\mu_{Y}$ almost every
$x\in Y$,

$\frac{R_{n}(x)}{n}=\frac{1}{n}\sum_{k=0}^{n-1}\tau_{Y}(F^{k}x)\xrightarrow{n\to\infty}\int_{Y}\tau_{Y}d\mu_{Y}=1/\mu(Y).$

We will require the following property: there exists $N_{1}\in{\mathbb{N}}$
such that

$I\setminus Y\cap\left(\bigcup_{n=1}^{N_{1}}f^{n}(Y)\right)=I\setminus Y.$
(6.1)

As in §2 we begin by stating our result in the special case that (2.11) holds.

######  Theorem 6.1.

Let $f,m$, $\mu$ be as above, in particular we assume (2.11). Suppose there
exists $Y\subset I$ such that $f$ satisfies (6.1). Moreover assume that the
first return map $F:Y\to Y$ equipped with the measure $\mu_{Y}$ satisfies
(a1)-(a6), (2.8)-(2.11). Additionally assume that
$\mu_{Y}(\tau_{Y}>n)=O(n^{-\gamma})$ for some $\gamma>2$. There exist
$0<c<C<\infty$ such that for all $\delta>0$,

$c\delta^{-s_{f}}\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\delta^{-s_{f}}\log(1/\delta).$

Moreover, if $F$ has at least 2 full branches, we have a sharp lower bound

$c\delta^{-s_{f}}\log(1/\delta)\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\delta^{-s_{f}}\log(1/\delta).$

Next we state our result for general measures.

######  Theorem 6.2.

Let $f,m$, $\mu$ be as above. Suppose there exists $Y\subset I$ such that $f$
satisfies (6.1). Moreover assume that the first return map $F:Y\to Y$ equipped
with the measure $\mu_{Y}$ satisfies satisfies (a1)-(a6),,(2.8)-(2.10).
Additionally, assume that $\mu_{Y}(\tau_{Y}>n)=O(n^{-\gamma})$ for some
$\gamma>2$. There exist $0<c<C<\infty$ such that for all $\delta>0$,

$\frac{c}{M_{\mu}(\delta)}\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant\frac{C}{M_{\mu}(\delta)}\log(1/\delta).$

In particular if $\dim_{\textup{M}}\mu<\infty$ then there exists
$\varepsilon<0$ such that

$c\delta^{-\dim_{\textup{M}}\mu+\mathrm{Err}(\delta/\varepsilon)}\leqslant\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\delta^{-\dim_{\textup{M}}\mu-\mathrm{Err}(\varepsilon\delta)}\log(1/\delta).$

and $\varepsilon>0$

We denote

$\tau^{Y}_{\delta}(x):=\inf\\{n\geqslant
1\;:\;\\{x,f(x),\ldots,f^{n}(x)\\}\;\textnormal{is $\delta$-dense in $Y$}\\}$
(6.2)

and

${\mathcal{T}}_{\delta}(x):=\inf\\{n\geqslant
1\;:\;\\{x,F(x),\ldots,F^{n}(x)\\}\;\textnormal{is $\delta$-dense in $Y$}\\}.$
(6.3)

Fix $\varepsilon>0$ and consider the sets of large deviations

$A_{u}=A_{u,\varepsilon}:=\\{x\in Y:\exists n\geqslant
u,|R_{n}(x)/n-1/\mu(Y)|>\varepsilon\\}.$

######  Lemma 6.3.

Under (a6), $\mu_{Y}(\tau_{Y}>n)=O(n^{-\gamma})$ implies
$\sum_{u=1}^{\infty}\mu_{Y}(A_{u})<\infty$.

###### Proof.

By [G1, Theorem 2.2], see also [G2, Theorem 4], $\psi$-mixing and
$\mu_{Y}(\tau_{Y}>n)=O(n^{-\gamma})$ implies $\mu(A_{u})=O(n^{1-\gamma})$. ∎

Using Lemma 6.3 we will show that under the assumption that
$\mu_{Y}(\tau_{Y}>n)=O(n^{-\gamma})$ for some $\gamma>2$, it follows that
$\mathbb{E}_{\mu}(\tau_{\delta})$ is proportional to
$\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})$, and the proof of Theorems 6.1
and 6.2 will follow by applying Theorem 2.1.

The following lemma allows us to estimate $\tau_{\delta}$ from above in terms
of $\tau_{\delta}^{Y}$, whose expectation can be easier related to
$\mathbb{E}({\mathcal{T}}_{\delta})$.

######  Lemma 6.4.

There exists $\kappa>0$ such that for all sufficiently small $\delta>0$ and
all $x\in Y$, $\tau_{\delta}(x)\leqslant\tau_{\kappa\delta}^{Y}(x)$.

###### Proof.

Let $C=C(N_{1})$ satisfy that $\inf_{x}|(f^{N_{1}})^{\prime}(x)|\leqslant C$
and set $\kappa:=1/(2CN_{1}(N_{1}+1))$. Let $P$ be a partition of $Y$ into
sets of length at most $\frac{\delta}{CN_{1}(N_{1}+1)}$ and at least
$\frac{\delta}{2CN_{1}(N_{1}+1)}$ with the property that each set in $P$ is
contained inside a unique element of ${\mathcal{Z}}^{N_{1}}$.

Denote

$A:=\\{f^{n}(J)\;:\;J\in P,\,1\leqslant n\leqslant
N_{1},\,f^{n}(J)\cap(I\setminus Y)\neq\emptyset\\}$

and note that for each $f^{n}(J)\in A$, $\mbox{\rm diam}(f^{n}(J))\leqslant
C\mbox{\rm diam}(J)=\frac{\delta}{N_{1}(N_{1}+1)}\leqslant\frac{\delta}{2}$.
Moreover, by definition of $N_{1}$,

$\bigcup_{U\in A}U=I$ (6.4)

Fix $x\in Y$ and let $k=\tau_{\kappa\delta}^{Y}(x)$. Note that since each set
$J\in P$ has diameter at least $\frac{\delta}{2CN_{1}(N_{1}+1)}=\kappa\delta$,
this implies that each set in $P$ is visited by the orbit segment
$\\{x,f(x),\ldots,f^{k}(x)\\}$. Let $\mathcal{J}\subseteq\\{1,\ldots,k\\}$ be
the set of indices $i$ for which $f^{i}(x)\in Y$. For each $i\in\mathcal{J}$
let $J_{i}\in P$ denote the partition element that $f^{i}(x)$ belongs to. Note
that each $f^{n}(J)\in A$ must be visited by the orbit segment
$\\{x,\ldots,f^{k}(x)\\}$ except possibly the following sets:

$B:=\\{f^{j}(J_{i})\;:\;i\in\mathcal{J},\;1\leqslant j\leqslant
N_{1}\;\mathnormal{s.t.}\;i+j>k\\}.$

(This is because any set in $B$ might only be visited after time $k$). There
are at most $1+2+\ldots+N_{1}=N_{1}(N_{1}+1)/2$ distinct sets in $B$. By
continuity of $f^{N_{1}}$ on ${\mathcal{Z}}^{N_{1}}$, each set in $B$ is
necessarily an interval of length at most $\delta/N_{1}(N_{1}+1)$. Therefore,
the largest interval contained in $\bigcup_{J^{\prime}\in B}J^{\prime}$ has
length at most $\delta/2$. In particular by (6.4) $\\{x,\ldots,f^{k}(x)\\}$
must be $\delta$ dense in $I\setminus Y$. ∎

We are almost ready to estimate $\mathbb{E}_{\mu_{Y}}(\tau_{\delta})$ in terms
of $\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})$. We will require the
following simple but useful lemma.

######  Lemma 6.5.

Suppose $x\in A_{u}^{c}$. Then

$\tau_{\delta}(x)>\frac{u}{\mu(Y)}\Rightarrow{\mathcal{T}}_{\delta}(x)>\frac{u}{1+\varepsilon\mu(Y)}$

and

${\mathcal{T}}_{\delta}(x)>\frac{u}{1-\varepsilon\mu(Y)}\Rightarrow\tau_{\delta}(x)>\frac{u}{\mu(Y)}.$

###### Proof.

Note that for any $x\in Y$,
$R_{{\mathcal{T}}_{\delta}(x)}(x)=\tau_{\delta}^{Y}(x)$.

For the first part, note that $\tau^{Y}_{\delta}(x)>\frac{u}{\mu(Y)}$ implies
${\mathcal{T}}_{\delta}(x)>\frac{u}{\mu(Y)}>u$. Hence

$\frac{R_{{\mathcal{T}}_{\delta}(x)}(x)}{{\mathcal{T}}_{\delta}(x)}=\frac{\tau^{Y}_{\delta}(x)}{{\mathcal{T}}_{\delta}(x)}=\frac{1}{\mu(Y)}+s$

where $|s|<\varepsilon$ since $x\in A_{u}^{c}$. Therefore

${\mathcal{T}}_{\delta}(x)=\frac{\tau^{Y}_{\delta}(x)}{1/\mu(Y)+s}>\frac{u/\mu(Y)}{1/\mu(Y)+\varepsilon}=\frac{u}{1+\varepsilon\mu(Y)}.$

For the second part, note that
${\mathcal{T}}_{\delta}(x)>\frac{u}{1-\varepsilon\mu(Y)}>u$, therefore

$\frac{R_{{\mathcal{T}}_{\delta}(x)}(x)}{{\mathcal{T}}_{\delta}(x)}=\frac{\tau^{Y}_{\delta}(x)}{{\mathcal{T}}_{\delta}(x)}=\frac{1}{\mu(Y)}+s$

where $|s|<\varepsilon$ since $x\in A_{u}^{c}$. Hence

$\tau^{Y}_{\delta}(x)=\frac{{\mathcal{T}}_{\delta}(x)}{\mu(Y)}+s{\mathcal{T}}_{\delta}(x)>\frac{u}{1-\varepsilon\mu(Y)}(1/\mu(Y)-\varepsilon)=\frac{u}{\mu(Y)}.$

∎

The following proposition allows us to estimate
$\mathbb{E}_{\mu_{Y}}(\tau_{\delta})$ in terms of
$\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})$.

######  Proposition 6.6.

Assume that $\sum_{u=1}^{\infty}\mu_{Y}(A_{u})<\infty$. There exist constants
$c<1<C$ such that for all $\delta>0$,

$c\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})\leqslant\mathbb{E}_{\mu_{Y}}(\tau_{\delta})\leqslant
C\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\kappa\delta}).$

###### Proof.

Since $\mu_{Y}$ is supported on $Y$, by Lemma 6.4

$\mathbb{E}_{\mu_{Y}}(\tau_{\delta}^{Y})\leqslant\mathbb{E}_{\mu_{Y}}(\tau_{\delta})\leqslant\mathbb{E}_{\mu_{Y}}(\tau_{\kappa\delta}^{Y})$

so it is enough to obtain lower and upper bounds on
$\mathbb{E}_{\mu_{Y}}(\tau_{\delta}^{Y})$ in terms of
$\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})$. To this end

$\displaystyle\mathbb{E}_{\mu_{Y}}(\tau_{\delta}^{Y})$
$\displaystyle=\sum_{n\in{\mathbb{N}}}\mu_{Y}(\tau_{\delta}^{Y}\geqslant
n)=\sum_{n\in{\mathbb{N}}}\left(\mu_{Y}(\tau_{\delta}^{Y}\geqslant n\wedge
A_{n\mu(Y)}^{c})+\mu_{Y}(\tau_{\delta}^{Y}\geqslant n\wedge
A_{n\mu(Y)}\right)$
$\displaystyle\leqslant\sum_{n\in{\mathbb{N}}}\mu_{Y}\left({\mathcal{T}}_{\delta}\geqslant\frac{n\mu(Y)}{1+\varepsilon\mu(Y)}\right)+\sum_{n\in{\mathbb{N}}}\mu(A_{n\mu(Y)})$
$\displaystyle=\sum_{n\in{\mathbb{N}}}\mu_{Y}\left(\frac{{\mathcal{T}}_{\delta}(1+\varepsilon\mu(Y))}{\mu(Y)}\geqslant
n\right)+\sum_{n\in{\mathbb{N}}}\mu(A_{n\mu(Y)})$
$\displaystyle=\mathbb{E}_{\mu_{Y}}\left(\frac{{\mathcal{T}}_{\delta}(1+\varepsilon\mu(Y))}{\mu(Y)}\right)+\sum_{n\in{\mathbb{N}}}\mu_{Y}(A_{n\mu(Y)})$
$\displaystyle=\frac{1+\varepsilon\mu(Y)}{\mu(Y)}\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})+\sum_{n\in{\mathbb{N}}}\mu_{Y}(A_{n\mu(Y)})$

where to get the inequality we have used Lemma 6.5. Note that since
$\sum_{n\in{\mathbb{N}}}\mu_{Y}(A_{n\mu(Y)})<\infty$, it is just a constant
which is independent of $\delta$, therefore we have the upper bound.

Similarly for the lower bound,

$\displaystyle\mathbb{E}_{\mu_{Y}}(\tau_{\delta}^{Y})$
$\displaystyle\geqslant\sum_{n\in{\mathbb{N}}}\mu_{Y}(\tau_{\delta}^{Y}\geqslant
n\wedge
A_{n\mu(Y)}^{c})\geqslant\sum_{n\in{\mathbb{N}}}\mu_{Y}\left({\mathcal{T}}_{\delta}\geqslant\frac{n\mu(Y)}{1-\varepsilon\mu(Y)}\right)$
$\displaystyle=\mathbb{E}_{\mu_{Y}}\left(\frac{{\mathcal{T}}_{\delta}(1-\varepsilon\mu(Y))}{\mu(Y)}\right)=\left(\frac{1-\varepsilon\mu(Y)}{\mu(Y)}\right)\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})$

where again we have used Lemma 6.5. ∎

Proposition 6.6 will allow us to obtain a lower bound on
$\mathbb{E}_{\mu}(\tau_{\delta})$ since
$\mathbb{E}_{\mu}(\tau_{\delta})\geqslant\mu(Y)\mathbb{E}_{\mu_{Y}}(\tau_{\delta})$.
Next we will obtain an upper bound on $\mathbb{E}_{\mu}(\tau_{\delta})$ in
terms of $\mathbb{E}_{\mu_{Y}}(\tau_{\delta}^{Y})$.

For this we will view the system as a Young Tower
$(\Delta,f_{\Delta},\mu_{\Delta})$. We call the base, which corresponds to
$Y$, $\Delta_{0}$, and we’ll use notation $\Delta_{i,j}$ for domains in
$\Delta$, where $\Delta_{i,0}\subset\Delta_{0}$ and
$f_{\Delta}^{j}(\Delta_{i,0})=\Delta_{i,j}$ for $j\leqslant r_{i}-1$ ($r$
being the roof function) and $f_{\Delta}^{r_{i}}(\Delta_{i,0})=\Delta_{0}$.
Points in $\Delta_{i,j}$ are denoted $(x,j)$ for $x\in Y$. Then
$f_{\Delta}^{r}$ on $\Delta_{0}$ corresponds to $F$ on $Y$. We let
$\pi:\Delta\to I$ be the natural projection $\pi(x,j)=f^{j}(x)$. Note that
$\pi|_{\pi^{-1}(\Delta_{0})}$ is injective. We define $\mu_{\Delta}$ to be the
measure
$\mu_{\Delta}(\Delta_{i,j})=\mu_{\Delta}(\Delta_{i,0})=\mu(Y)\mu_{Y}(\Delta_{i,0})$.
Then $\pi_{*}\mu_{\Delta}=\mu$ and $f\circ\pi=\pi\circ f_{\Delta}$. Let
$\mu_{\Delta_{0}}=\mu_{\Delta}|_{\Delta_{0}}$ \- we will similarly restrict
$\mu_{\Delta}$ to $\Delta_{i,j}$ to get $\mu_{\Delta_{i,j}}$. We will also
consider the symbolic coding for $F$ as in §2; in this setup $\Sigma$ can be
taken to be the set of all $\mathbf{i}=(i_{0},i_{1}\ldots)$ such that for some
$x\in Y$, $x\in\Delta_{i_{0},0}$, $F(x)\in\Delta_{i_{1},0}$ and so on.
Moreover, in this case $\Pi(\mathbf{i})=x$. Let $\tilde{\mu}_{Y}$ be the
measure on $\Sigma$ such that $\Pi_{*}\tilde{\mu}_{Y}=\mu_{Y}$, which by our
assumptions is quasi-Bernoulli. The relationship between $\tilde{\mu}_{Y}$ and
$\mu_{\Delta_{0}}$ is the following:
$\mu_{\Delta_{0}}=\mu(Y)\Pi_{*}\tilde{\mu}_{Y}$.

We can also extend the cover time function to $\Delta_{0}$ in the natural way:

$\tau_{\delta}^{\Delta_{0}}(x,j):=\inf\\{n\in{\mathbb{N}}:\\{\pi(x,j),\ldots,\pi(f_{\Delta}^{n}(x,j)\\}\;\textnormal{is
$\delta$ dense in $\Delta_{0}$}\\},$

where the metric on $\Delta_{0}$ is the one induced from $Y$. Since
$f\circ\pi=\pi\circ f_{\Delta}$ and by definition of $\mu_{\Delta}$, we have
$\mathbb{E}_{\mu}(\tau^{Y}_{\kappa\delta})=\mathbb{E}_{\mu_{\Delta}}(\tau_{\kappa\delta}^{\Delta_{0}}).$

######  Proposition 6.7.

Suppose $F$ and $\mu_{Y}$ satisfies (a1)-(a4), (a6), (2.8) and (2.9) and that
$\mu_{Y}(\tau>n)=O(n^{-\gamma})$ where $\gamma>2$. Then for some
$\varepsilon>0$, and $C>0$

$\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\mathbb{E}_{\mu_{Y}}(\tau_{\varepsilon\delta}^{Y}).$

###### Proof.

By Lemma 6.4 we have

$\mathbb{E}_{\mu}(\tau_{\delta})\leqslant\mathbb{E}_{\mu}(\tau^{Y}_{\kappa\delta})=\mathbb{E}_{\mu_{\Delta}}(\tau_{\kappa\delta}^{\Delta_{0}}).$

For any $x\in\Delta_{i,0}$,

$\tau^{\Delta_{0}}_{\kappa\delta}((x,j))\leqslant\tau^{\Delta_{0}}_{\kappa\delta}(F(x),0)+r_{i}-j.$

Hence

$\mathbb{E}_{\mu_{\Delta_{i,j}}}\left(\tau_{\kappa\delta}^{\Delta_{0}}\right)\leqslant\mathbb{E}_{\mu_{\Delta_{i,0}}}\left(\tau_{\kappa\delta}^{\Delta_{0}}\circ
F+r_{i}-j\right).$

Summing over the column (i.e. summing over $j$) we obtain

$\sum_{j=0}^{r_{i}-1}\mathbb{E}_{\mu_{\Delta_{i,j}}}\left(\tau_{\kappa\delta}^{\Delta_{0}}\right)\leqslant
r_{i}\mathbb{E}_{\mu_{\Delta_{i,0}}}\left(\tau_{\kappa\delta}^{\Delta_{0}}\circ
F\right)+\mu_{\Delta}(\Delta_{i,0})\sum_{j=0}^{r_{i}-1}(r_{i}-j).$

Now summing over $i$ we obtain

$\mathbb{E}_{\mu_{\Delta}}(\tau^{\Delta_{0}}_{\kappa\delta})=\sum_{i}\sum_{j=0}^{r_{i}-1}\mathbb{E}_{\mu_{\Delta_{i,j}}}(\tau^{\Delta_{0}}_{\kappa\delta})\leqslant\sum_{i}r_{i}\mathbb{E}_{\mu_{\Delta_{i,0}}}(\tau^{\Delta_{0}}_{\kappa\delta}\circ
F)+R$ (6.5)

where
$R:=\sum_{i}\mu_{\Delta}(\Delta_{i,0})\sum_{j=0}^{r_{i}-1}j=\sum_{n}n\mu_{Y}(\tau_{Y}>n)<\infty$
since we have assumed $\mu_{Y}(\tau>n)=O(n^{-\gamma})$ for some $\gamma>2$.

Now, let $\mathcal{P}_{\delta}$ be defined as in (5.3) for the system $F:Y\to
Y$ (which is possible by our assumptions on $F$ and $\mu_{Y}$). Put
$\mathcal{P}=\mathcal{P}_{\kappa\delta/T}$. By definition of
$\mu_{\Delta_{i,0}}$,

$\displaystyle\mathbb{E}_{\mu_{\Delta_{i,0}}}(\tau^{\Delta_{0}}_{\kappa\delta}\circ
F)$
$\displaystyle=\mu(Y)\mathbb{E}_{\mu_{Y}|\Pi([i])}(\tau_{\kappa\delta}^{Y}\circ
F)\leqslant\mu(Y)\mathbb{E}_{\tilde{\mu}_{Y}|[i]}(\tau_{\mathcal{P}}\circ
F)=\mu(Y)\sum_{\mathbf{j}\in{\mathcal{P}}}\tilde{\mu}_{Y}([i\mathbf{j}])\left(\sum_{k}r_{j_{k}}\right)$
$\displaystyle\leqslant
C_{*}\mu(Y)\tilde{\mu}_{Y}([i])\sum_{\mathbf{j}\in{\mathcal{P}}}\tilde{\mu}_{Y}([\mathbf{j}])\left(\sum_{k}r_{j_{k}}\right)=C_{*}\mu_{\Delta_{0}}(\Delta_{i,0})\mathbb{E}_{\tilde{\mu}_{Y}}(\tau_{{\mathcal{P}}})$
$\displaystyle\leqslant
C_{*}\mu_{\Delta_{0}}(\Delta_{i,0})\mathbb{E}_{\mu_{Y}}(\tau_{t\kappa\delta/3T}^{Y})=\frac{C_{*}}{\mu(Y)}\mu_{\Delta_{0}}(\Delta_{i,0})\mathbb{E}_{\mu_{\Delta_{0}}}(\tau_{t\kappa\delta/3T}^{\Delta_{0}})$

where the first inequality follows by (5.4), the second inequality by the
quasi-Bernoulli property (a5) of $\mu_{Y}$ and the final inequality follows by
(5.6).

Now putting back into (6.5) and using that
$\sum_{i}r_{i}\mu_{\Delta_{0}}(\Delta_{i,0})=1$ we obtain

$\displaystyle\mathbb{E}_{\mu}(\tau_{\delta})\leqslant\mathbb{E}_{\mu_{\Delta}}(\tau_{\kappa\delta}^{\Delta_{0}})$
$\displaystyle\leqslant\frac{C_{*}}{\mu(Y)}\sum_{i}r_{i}\mu_{\Delta_{0}}(\Delta_{i,0})\mathbb{E}_{\mu_{\Delta_{0}}}(\tau_{t\kappa\delta/3T}^{\Delta_{0}})+R$
$\displaystyle=\frac{C_{*}}{\mu(Y)}\mathbb{E}_{\mu_{\Delta_{0}}}(\tau_{t\delta/12T}^{\Delta_{0}})+K=C_{*}\mathbb{E}_{\mu_{Y}}(\tau_{t\kappa\delta/3T}^{Y})+R$

which completes the proof. ∎

###### Proof of Theorems 6.1 and 6.2.

By our assumption, there exists $Y\subset I$ such that the first return map
$F:Y\to Y$ equipped with the induced measure $\mu_{Y}$ satisfies the
assumptions of Theorem 2.1. Since Lemma 6.3 implies
$\sum_{u=1}^{\infty}\mu_{Y}(A_{u})<\infty$,

$\displaystyle\mathbb{E}_{\mu}(\tau_{\delta})\geqslant\mu(Y)\mathbb{E}_{\mu_{Y}}(\tau_{\delta})\geqslant
c\mu(Y)\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})$

where in the second inequality we have used Proposition 6.6. Now, in the
setting for general $\mu$ (ie. proof of Theorem 6.2) the lower bound is
obtained by applying Theorem 2.1 to deduce that
$\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})\geqslant\frac{c}{M_{\mu}(\delta/\varepsilon)}$.
In the setting where (2.11) holds (ie. proof of Theorem 6.1) observe that
(2.11) holds on $Y$, thus we can again apply Theorem 2.1 to deduce that
$\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\delta})\geqslant
c\delta^{-s_{f}}\log(1/\delta)$.

For the upper bound we have

$\displaystyle\mathbb{E}_{\mu}(\tau_{\delta})\leqslant
C\mathbb{E}_{\mu_{Y}}(\tau_{\delta}^{Y})\leqslant
C\mathbb{E}_{\mu_{Y}}(\tau_{\delta})\leqslant
C\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\kappa\delta})$

where in the first inequality we have used Proposition 6.7, in the third we
have used Proposition 6.6. In the case for general $\mu$ (ie. proof of Theorem
6.2) we obtain the upper bound by applying Theorem 2.1 to get
$\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\kappa\delta})\leqslant\frac{C}{M_{\mu}(\varepsilon\kappa\delta)}\log(1/\delta)$.
In the setting where (2.11) holds we can again apply Theorem 2.1 to deduce
that $\mathbb{E}_{\mu_{Y}}({\mathcal{T}}_{\kappa\delta})\leqslant
C\delta^{-s}\log(1/\delta)$. ∎

##  7\. Examples

###  7.1. Full branched interval maps with acip

Let $f$ be a full branched map of an interval $I$ (i.e. $\Lambda=I$) and
assume each of the branches $f|_{Z}$ is $C^{1+Lip}$, such that there is a
uniform bound on the Lipschitz constants of the derivatives. Assume
$|Df|\geqslant\gamma^{-1}>1$ on each $Z\in{\mathcal{Z}}$ and
$\frac{|Z|}{|Z^{\prime}|}$ is uniformly bounded for adjacent intervals
$Z,Z^{\prime}\in{\mathcal{Z}}$. The potential $\phi=-\log|Df|$ gives rise to
an acip $\mu$ for $f$.

Since $f$ is full-branched, it is Markov and satisfies BIP. The potential
$\phi$ is Lipschitz with uniform Lipschitz constants, hence satisfies (2.9).
Moreover $\mu$ is necessarily Gibbs for the potential $\phi=-\log|Df|$, so by
the discussion in §2.2 the system $(f,\mu)$ satisfies (a1)-(a6). In this case
the conformal measure $m$ is Lebesgue measure, hence (2.8) is satisfied for
$s=1$. For (2.10), this follows from the uniform bounds on the density and the
bound on $\frac{|Z|}{|Z^{\prime}|}$. In particular Theorem 2.1 applies.

We note that if there is $\alpha>0$ such that each of the branches $f|_{Z}$ is
$C^{1+\alpha}$, with uniform $\alpha$-Hölder constants then Theorem 2.1 is
also applicable to this system, by making some small adjustments to the proof,
similar to what is described in the following section.

###  7.2. Gauss map

The Gauss map $f:(0,1]\to(0,1]$ is defined by $f(x)=\frac{1}{x}\mod 1$, so
defining our partition ${\mathcal{Z}}$ as
$\\{Z_{n}\\}_{n}=\\{(\frac{1}{n+1},\frac{1}{n})\\}_{n}$, $f$ is continuously
differentiable on each element of ${\mathcal{Z}}$. We set $\phi=-\log|Df|$ and
$m$ be Lebesgue measure on $(0,1]$. Then we have an invariant density is
$g(x)=\frac{1}{\log 2}\frac{1}{1+x}$ defining an acip $\mu$: call
$((0,1],f,\phi,\mu)$ the _Gauss system_.

(a1) fails for this system, however this system is well-known to satisfy
Rychlik’s conditions since the potential is monotonic on each branch, and
moreoever the potential satisfies the following weaker Hölder distortion
control on the cylinder sets:

######  Lemma 7.1.

There exists $C_{d}>0$ such that $|e^{S_{n}\phi(x)-S_{n}\phi(y)}-1|\leqslant
C_{d}|f^{n}x-f^{n}y|^{1/2}$ whenever $f^{i}(x)$ and $f^{i}(y)$ lie in the same
element of ${\mathcal{Z}}$ for each $i=0,\ldots,n-1$.

###### Proof.

See [BDT, Lemma 2.9]. ∎

We’ll show that Lemma 7.1 suffices to prove Proposition 2.3 and Proposition
2.8, so that Theorem 2.1 holds for the Gauss system.

First we verify that the remainder of our assumptions hold for the Gauss
system. For (a2) notice that $|e^{\phi}|_{\infty}\leqslant 1$ while
$|e^{S_{2}\phi}|_{\infty}<1$ thus $|e^{S_{n}\phi}|_{\infty}$ converges to 0
exponentially fast in $n$, while $\mathcal{L}^{n}1$ converges to $g$ which is
bounded away from 0 on $[0,1]$. (a3) holds since $f$ is full branched and the
potential satisfies Lemma 7.1. (a4) holds since $f$ is full branched. (a5) and
(a6) hold since $\mu$ is Gibbs. (2.8) and (2.11) hold for $s=s_{f}=1$ since
$m$ is Lebesgue measure. (2.9) follows from Lemma 7.1. (2.10) holds since
$1\leqslant\frac{\mu(Z_{n-1})}{\mu(Z_{n})}\leqslant\frac{n+1}{n-1}$ for all
$n\geqslant 2$. Instead of (2.4) we choose $n_{1}$ such that
$\frac{2n_{1}+5}{2}\sup_{I}e^{S_{n_{1}}\phi}|\phi|_{BV}<1$ (the reason for
this will be made clear later).

We note that Proposition 2.3 still holds for the Gauss system since the only
time (a1) is used in the proof is in (8.1), where (2.9) can be used instead,
to obtain the same conclusion.

We also verify that Lemma 2.6 holds: (a) holds by induction on (2.6), (b)
holds with $C_{d}=1$ since $e^{\phi}$ is monotonic on each $Z\in{\mathcal{Z}}$
so $|\phi|_{BV,Z}\leqslant\sup_{Z}e^{\phi}$ and (c) holds by induction on (b),
using (a).

Finally, we are ready to demonstrate that the uniform Lasota-Yorke
inequalities hold in Proposition 2.8. (a1) is used in two places in the proof:
in (2.19) and (2.21). (2.19) holds with $C_{d}=1$ by Lemma 2.6(b). (2.21)
holds using (2.9). Hence the contracting term in (2.23) becomes
$\frac{2n+5}{2}\sup_{I}e^{S_{n_{1}}\phi}|\phi|_{BV}$, which is the same
expression, just with $C_{d}=1$, hence since $n_{1}$ was chosen such that
$\frac{2n_{1}+5}{2}\sup_{I}e^{S_{n_{1}}\phi}|\phi|_{BV}<1$, the proof of
Proposition 2.8 is complete. Hence we have shown that Theorem 2.1 holds for
the Gauss system.

###  7.3. Manneville-Pomeau maps

For $\alpha\in(0,1)$, we will study the class of Manneville-Pomeau maps
defined by

$f=f_{\alpha}:x\mapsto\begin{cases}x(1+2^{\alpha}x^{\alpha})&\text{ if
}x\in[0,1/2),\\\ 2x-1&\text{ if }x\in[1/2,1].\end{cases}$

(This is the simpler form given by Liverani, Saussol and Vaienti, often
referred to as LSV maps). These maps all have an acip $\mu=\mu_{\alpha}$,
which is an equilibrium state for the potential $\phi=-\log Df$. Our first
returns will be taken to the set $Y=[1/2,1]$. The induced system
$(Y,F=f^{\tau_{Y}})$ is a full-branched Gibbs-Markov map with respect to the
induced potential $-\log DF$. The full-branched property implies 6.1 holds: in
fact since $f([3/4,1])=Y$, it holds with $N_{1}=1$. Adjacent intervals,
$Y_{n}$ and $Y_{n-1}$ can be shown (see for example [S1, Corollary 1]) to have
$\frac{\mu_{Y}(Y_{n-1})}{\mu_{Y}(Y_{n})}\sim\left(\frac{n}{n-1}\right)^{\frac{1}{\alpha}+1}$,
so (2.10) holds. Moreover, the induced system is $\psi$-mixing, which we used
in the proof of Proposition 3.1 (though in fact we only require $\phi$-mixing,
which is a weaker condition). Thus to apply Theorem 6.1, it is sufficient that
$\mu(\tau_{Y}>n)=O(n^{-\gamma})$ for some $\gamma>2$. It is well known that
for $f_{\alpha}$, $\mu(\tau_{Y}>n)=O(n^{-1/\alpha})$ (again, see for example
[S1, Corollary 1]), so our results apply to the case $\alpha\in(0,1/2)$.

######  Remark 7.2.

Hitting Time statistics results hold for all $\alpha\in(0,1)$ at all points,
see [FFTV], so it is a natural question to ask if the results here should also
hold in that generality. However, in this setting we are required to take
expectations, which means summing over more quantities, so it is not clear if
the restriction to $(0,1/2)$, which is used twice in our argument, is an
artefact of our proof method or is intrinsic for this problem. It may be
relevant to note that the range $\alpha\in(0,1/2)$ is the range of parameters
for which the Central Limit Theorem holds: for $\alpha\in(1/2,1)$ it fails
(this is also seen in the i.i.d. case with observables outside $L^{2}$).

###  7.4. Systems with slow covering

In previous related studies of the cover time [JM, BJK], the leading term for
the expected cover time $\mathbb{E}_{\mu}(\tau_{\delta})$ always obeyed a
power law in $1/\delta$, that is, $\dim_{\textup{M}}\mu<\infty$ and
$\mathbb{E}_{\mu}(\tau_{\delta})\approx\left(1/\delta\right)^{\dim_{\textup{M}}\mu}$.
However, our setup presents natural examples of systems in which average
orbits become dense in the state space at a much slower rate. In these
examples $\dim_{\textup{M}}\mu=\infty$, therefore the formula for the expected
cover time can no longer expressed as a power law in $1/\delta$.

######  Example 7.3.

Let $f:[0,1]\to[0,1]$ be the Manneville-Pomeau map

$\displaystyle f(x)=\begin{cases}f_{1}(x)=x(1+2^{\alpha}x^{\alpha}),\hskip
42.67912ptx\in[0,1/2)\\\ f_{2}(x)=2x-1,\hskip
68.28644ptx\in[1/2,1]\end{cases}$

although this time we equip it with the measure $\mu$ which is given as the
pushforward of the $(1/2,1/2)$ Bernoulli measure on $\\{1,2\\}^{\mathbb{N}}$
through the coding map $\Pi:\\{1,2\\}^{\mathbb{N}}\to[0,1]$,

$\Pi(i_{0}\ldots
i_{n-1}\ldots)=\lim_{n\to\infty}f_{i_{0}}^{-1}\circ\cdots\circ
f_{i_{n-1}}^{-1}([0,1)).$

Similarly to §7.3 we see that this system satisfies Theorem 6.2. (2.10)
clearly holds with $C=2$.

Then for each $n\in{\mathbb{N}}$, $\mu(\Pi([1^{n}]))=1/2^{n}$ whereas
$\mbox{\rm diam}(\Pi([1^{n}]))\sim\frac{1}{2}(\alpha n)^{-1/\alpha}$. In
particular $M_{\mu}(\delta)\leqslant(2^{1/\delta^{\alpha}})^{-1/(\alpha
2^{\alpha})}$ so by Theorem 6.2,
$\mathbb{E}_{\mu}(\tau_{\delta})\geqslant(2^{1/\delta^{\alpha}})^{1/(\alpha
2^{\alpha})}$. The key point here is that it is very difficult for this system
to cover a neighbourhood of 0, which drives the expected cover time up.

######  Example 7.4.

Let $a_{0}=0$ and for $n\geqslant 1$, let
$a_{n}=\sum_{k=1}^{n}\frac{1}{cn^{2}}$ where $c=\frac{\pi^{2}}{6}$. Then let
$f:[0,1)\to[0,1)$ be the map

$f(x)=cn^{2}(x-a_{n-1})\text{ for }x\in[a_{n-1},a_{n})$

equipped with the measure $\mu$ which is given as the pushforward of the
Bernoulli measure $\mathbb{P}$ on ${\mathbb{N}}^{\mathbb{N}}$ which fixes
$\mathbb{P}([n])=\frac{1}{2^{n}}$ through the coding map
$\Pi:{\mathbb{N}}^{{\mathbb{N}}_{0}}\to[0,1)$,

$\Pi(i_{0}\ldots
i_{n-1}\ldots)=\lim_{n\to\infty}f_{i_{0}}^{-1}\circ\cdots\circ
f_{i_{n-1}}^{-1}([0,1)).$

This is a Gibbs-Markov system so Theorem 2.2 applies. Then for each
$n\in{\mathbb{N}}$, $\mu(\Pi([n]))=\frac{1}{2^{n}}$ whereas $\mbox{\rm
diam}(\Pi([n]))=\frac{1}{cn^{2}}$. In particular for
$\delta=\frac{1}{cn^{2}}$,
$M_{\mu}(\delta)\leqslant\frac{1}{2^{\sqrt{1/c\delta}}}$ so by Theorem 2.2,
$\mathbb{E}_{\mu}(\tau_{\delta})\gtrsim 2^{\sqrt{1/c\delta}}$. In this
example, it is very difficult for the system to cover a neighbourhood of 1,
which drives the expected cover time up.

##  8\. Appendix: Proof of Propositions 2.3 and 2.4

In this section we prove Propositions 2.3 and 2.4, and we begin with the
former. We start with the simpler case where $\Lambda=I$. Following this, we
will describe how the proof can be adapted to hold for more general $\Lambda$.

###  8.1. Proof of Proposition 2.3 for interval maps

The proof in the case that $f$ has finitely many branches is trivial,
therefore we focus our attention on the case where $f$ has infinitely many
branches.

Throughout the proof, given an interval $J$ we’ll denote its diameter by
$|J|$. The rough idea is the following. For each small $r$ we will partition
$I$ into intervals of diameter roughly $r$ in an iterative way. If a union of
neighbouring 1-cylinders can be taken of the correct length then this union
forms a ball in ${\mathcal{U}}_{\delta}$. For all 1-cylinders which are too
large, we split it into 2-cylinders and consider unions of these which have
both the correct diameter and whose diameter comprises a small proportion of
the diameter of the 1-cylinder. On the other hand, for all 2-cylinders which
are too large we iterate the process by splitting them into 3-cylinders. This
is continued until we reach $n_{1}$-cylinders, at which point any
$n_{1}$-cylinder which is too large is split into arbitrary intervals (not
necessarily unions of $(n_{1}+1)$-cylinders) which have the correct diameter
and whose diameter comprises a small proportion of the $n_{1}$-cylinder.

For any interval $J$ let $\ell(J)$ and $r(J)$ denote the left and right end
points of $J$ respectively. Beginning from $\ell(I)$ we can uniquely choose a
(possibly infinite) union of 1-cylinders $\cup_{J_{1}\in\alpha_{1}}J_{1}$
which forms an interval such that
$\ell(\cup_{J_{1}\in\alpha_{1}}J_{1})=\ell(I)$,
$|\cup_{J_{1}\in\alpha_{1}}J_{1}|\geqslant\delta/2$ and such that for any
subcollection $\alpha_{1}^{\prime}\subset\alpha_{1}$ for which
$\cup_{J_{1}\in\alpha_{1}^{\prime}}J_{1}$ is an interval starting at
$\ell(I)$, we have $|\cup_{J_{1}\in\alpha_{1}^{\prime}}J_{1}|<\delta/2$. If
$|\cup_{J_{1}\in\alpha_{1}}J_{1}|<3\delta/2$ then we add
$\cup_{J_{1}\in\alpha_{1}}J_{1}$ to $U_{1}$. Otherwise, there exists
$J_{1}^{*}\in\alpha_{1}$ such that
$r(J_{1}^{*})=r(\cup_{J_{1}\in\alpha_{1}}J_{1})$ and
$|\cup_{J_{1}\in\alpha_{1}}J_{1}|-|J_{1}^{*}|<\delta/2$, in particular
$|J_{1}^{*}|\geqslant\delta$. In this case we add
$\cup_{J_{1}\in\alpha_{1}}J_{1}$ to $V_{1}$.

We then repeat the above, replacing $\ell(I)$ by
$r(\cup_{J_{1}\in\alpha_{1}}J_{1})$, and continue the process until either
$U_{1}\cup V_{1}$ cover $I$ or we are left with one interval with right hand
end point $r(I)$ and diameter less than $\delta/2$. In this case we add this
interval to $R_{1}$.

Recall that $c_{m}$ is given by (a4) and $C_{m}$ is given by (2.8). Now, let
$0<\tilde{\beta}<c_{m}$ and put

$\beta=\frac{\tilde{\beta}c_{m}}{C_{m}C_{bd}^{s}(n_{1}+1)(1+C_{d})^{3}}.$

Next, for each $A\in V_{1}$ we take the final 1-cylinder $J_{1}^{*}$ contained
in $A$ and beginning from $\ell(J_{1}^{*})$ we can uniquely choose a union of
2-cylinders $\cup_{J_{2}\in\alpha_{2}}J_{2}$ which forms an interval such that
$\ell(\cup_{J_{2}\in\alpha_{2}}J_{2})=\ell(J_{1}^{*})$,
$|\cup_{J_{2}\in\alpha_{2}}J_{2}|\geqslant\beta\delta/4$ and such that for any
subcollection $\alpha_{2}^{\prime}\subset\alpha_{2}$ for which
$\cup_{J_{2}\in\alpha_{2}^{\prime}}J_{2}$ is an interval starting at
$\ell(J_{1}^{*})$, we have
$|\cup_{J_{2}\in\alpha_{2}^{\prime}}J_{2}|<\beta\delta/4$. If
$|\cup_{J_{2}\in\alpha_{2}}J_{2}|<\beta\delta/2$ then we add
$\cup_{J_{2}\in\alpha_{2}}J_{2}$ to $U_{2}$. Otherwise, there exists
$J_{2}^{*}\in\alpha_{2}$ such that
$r(J_{2}^{*})=r(\cup_{J_{2}\in\alpha_{2}}J_{2})$ and
$|\cup_{J_{2}\in\alpha_{2}}J_{2}|-|J_{2}^{*}|<\beta\delta/4$, in particular
$|J_{2}^{*}|\geqslant\beta\delta/4$. In this case we add
$\cup_{J_{2}\in\alpha_{2}}J_{2}$ to $V_{2}$. We then repeat the above,
replacing $\ell(J_{1}^{*})$ by $r(\cup_{J_{2}\in\alpha_{2}}J_{2})$, and
continue the process until either $U_{1}\cup U_{2}\cup V_{2}\cup R_{1}$ cover
$I$ or we are left with a finite number of intervals (all of which appear on
the left or right hand sides of intervals in $V_{1}$). The ones on the left
will have length at most $\delta/2$ and will be made up of a union of
1-cylinders, and we put these into $L_{1}$. The ones on the right will have
length at most $\beta\delta/4$ and these will be put into $R_{2}$.

We can continue the above process inductively for each $2\leqslant n\leqslant
n_{1}-1$. For each $A\in V_{n}$ we take the final $n$-cylinder $J_{n}^{*}$
contained in $A$ and beginning from $\ell(J_{n}^{*})$ we can uniquely choose a
union of $n+1$-cylinders $\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1}$ which forms an
interval such that
$\ell(\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1})=\ell(J_{n}^{*})$,
$|\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1}|\geqslant\delta(\beta/4)^{n}$ and such
that for any subcollection $\alpha_{n+1}^{\prime}\subset\alpha_{n+1}$ for
which $\cup_{J_{n+1}\in\alpha_{n+1}^{\prime}}J_{n+1}$ is an interval starting
at $\ell(J_{n}^{*})$, we have
$|\cup_{J_{n+1}\in\alpha_{n+1}^{\prime}}J_{n+1}|<\delta(\beta/4)^{n}$. If
$|\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1}|<\delta(\beta/2)(\beta/4)^{n-1}$ then
we add $\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1}$ to $U_{n+1}$. Otherwise, there
exists $J_{n+1}^{*}\in\alpha_{n+1}$ such that
$\delta(J_{n+1}^{*})=r(\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1})$ and
$|\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1}|-|J_{n+1}^{*}|<\delta(\beta/4)^{n}$, in
particular $|J_{n+1}^{*}|\geqslant\delta(\beta/4)^{n}$. In this case we add
$\cup_{J_{n+1}\in\alpha_{n+1}}J_{n+1}$ to $V_{n+1}$. We then repeat the above,