# Maximal escape rate for shifts

Claudio Bonanno  Dipartimento di Matematica, Università di Pisa, Largo Bruno
Pontecorvo 5, 56127 Pisa, Italy<EMAIL_ADDRESS>,  Giampaolo
Cristadoro  Dipartimento di Matematica e Applicazioni, Università di Milano -
Bicocca, Via Roberto Cozzi 55, 20125 Milano, Italy
<EMAIL_ADDRESS>and  Marco Lenci  Dipartimento di Matematica,
Università di Bologna, Piazza di Porta San Donato 5, 40126 Bologna, Italy, and
Istituto Nazionale di Fisica Nucleare, Sezione di Bologna, Via Irnerio 46,
40126 Bologna, Italy<EMAIL_ADDRESS>
###### Abstract.

We consider the shift transformation on the space of infinite sequences over a
finite alphabet endowed with the invariant product measure, and examine the
presence of a _hole_ on the space. The holes we study are specified by the
sequences that do not contain a given finite word as initial sub-string. The
measure of the set of sequences that do not fall into the hole in the first
$n$ iterates of the shift is known to decay exponentially with $n$, and its
exponential rate is called _escape rate_. In this paper we provide a complete
characterization of the holes with maximal escape rate. In particular we show
that, contrary to the case of equiprobable symbols, ordering the holes by
their escape rate corresponds to neither the order by their measure nor by the
length of the shortest periodic orbit they contain. Finally, we adapt our
technique to the case of shifts endowed with Markov measures, where
preliminary results show that a more intricate situation is to be expected.

###### Key words and phrases:

Open dynamical systems, symbolic dynamics, Markov holes, maximal escape rate,
piecewise linear maps

###### 2020 Mathematics Subject Classification:

37B10, 37A05, 37E05

The authors are partially supported by the PRIN Grant 2017S35EHN “Regular and
stochastic behaviour in dynamical systems” of the Italian Ministry of
University and Research (MUR), Italy. This research is part of the authors’
activity within the UMI Group “DinAmicI” (www.dinamici.org) and the Gruppo
Nazionale di Fisica Matematica, INdAM, Italy.

##  1\. Introduction

Given a measure-preserving transformation $T$ of a probability space
$(X,\mu)$, a _hole_ of the associated dynamical system $(X,\mu,T)$ is a
measurable set $H\subset X$ with $\mu(H)>0$ such that when $T^{k}(x)\in H$ the
orbit of $x$ escapes from $X$. The presence of a hole is often realized by
modifying $T$ so that it is not defined on $H$ (another option is to define
the maps as the identity inside the hole). The investigation of properties of
open systems is more than forty years old; the first attempts can be traced
back to the late ’70s. See [20, 12] and references therein for the first
approaches to the problem. This kind of system has often been used to model
different situations of interest for the physics community. A recent review
dealing with such applications can be found in [1].

Let us introduce the basic properties of the open systems we consider. When
the probability measure $\mu$ is ergodic, almost every orbit enters $H$ at
some finite time, hence almost every orbit escapes. Let

$S_{n}:=\left\\{x\in X\,:\,T^{i}(x)\not\in
H\,,\,\forall\,i=0,\dots,n\right\\}$

be the set of points which do not escape up to time $n$, and define the
_survival probability at time $n$_ as $p_{n}:=\mu(S_{n})$. The sequence
$p_{n}$ is decreasing and vanishing as $n\to\infty$, and we consider its
exponential rate of convergence.

######  Definition 1.1.

The _escape rates_ $\gamma_{H}^{\pm}$ of the set $H$ are the exponential rates
of convergence to 0 of the survival probability, namely

$\gamma_{H}^{-}:=\liminf_{n\to\infty}\,\frac{-\log
p_{n}}{n}\,\quad\text{and}\quad\gamma_{H}^{+}:=\limsup_{n\to\infty}\,\frac{-\log
p_{n}}{n}.$

We consider only $\gamma_{H}:=\gamma_{H}^{-}$, since it can be studied by the
classical method of generating functions, and we refer to it as the _escape
rate of $H$_.

When $T$ has exponential decay of correlations, a finite non-zero escape rate
is to be expected for generic holes (see [11, 10] for precise conditions on
$T$ and a more extensive discussion on this topic). A variety of systems
satisfy this property: paradigmatic examples are expanding maps, Anosov
diffeomorphisms, and dispersing billiards [5, 21, 18, 9] (but many more cases
are studied in the literature). Other aspects that have been investigated are
the relations with other statistical properties of dynamical systems and
thermodynamic methods (see [7, 3]). Finally, there has been some recent
interest also in open systems exhibiting sub-exponential rates of escape [14,
19, 2, 8].

Among the different properties of open systems, much effort has been devoted
to the study of the escape rate as a function of certain parameters, such as
the size and the position of the hole. In this context, a recurrent question
in the literature concerns the identification of the hole with maximal escape
rate among holes in a given family (e.g., in the set of holes with the same
measure). It turns out that a peculiar role is played by the structure of the
periodic orbits of the system: as an example, it has been shown that in
certain systems the different escape rates for holes with the same measure can
be ordered according to the shortest period of the periodic points contained
in the hole [4]. Moreover, using a perturbative approach, it has been shown in
[17] that the escape rate for holes shrinking to a periodic point has a non-
trivial dependence on the stability of the limiting orbit. While these results
provide an answer to the question of where to place a hole to achieve maximal
escape for some specific situations, such as the small-hole limit, a complete
understanding of the generic case is not yet available, to our knowledge. This
work provides a complete answer to this question for full shifts on infinite
sequences over a finite number of symbols. It is well known that such a
symbolic dynamical system is isomorphic to an appropriate piecewise linear map
on the interval $[0,1]$ with full branches. There are many other examples of
systems isomorphic to a full shift, e.g., the logistic map $T(x)=4x(1-x)$ on
$[0,1]$. Thus our results apply to these isomorphic systems as well.

More in detail, in Theorem 3.4, we show that in order to find the maximal
escape rate for a fixed length of the forbidden word, it is enough to consider
two specific holes. This characterization is more precise in the case of full
shifts over two symbols, where, based on the probability of the most probable
symbol, we are able to determine which of the two holes achieves maximal
escape rate (Theorem 3.5) and to estimate this rate from below and from above
(Corollary 3.9).

##  2\. The setting

Consider the symbolic dynamical system $(\mathcal{A}^{\mathbb{N}},\mu,\sigma)$
defined by the left shift transformation $\sigma$ acting on the space
$\mathcal{A}^{\mathbb{N}}$ of semi-infinite words with symbols from a finite
alphabet $\mathcal{A}=\\{a_{1},a_{2},\dots,a_{A}\\}$, endowed with a product
probability measure $\mu$. The measure $\mu$ is determined by a probability
vector $\\{p_{a_{1}},\dots,p_{a_{A}}\\}$ such that $p_{a_{j}}>0$ for all $j$.

Since $\sigma$ preserves $\mu$ and is ergodic, we can study the escape rates
for holes in $\mathcal{A}^{\mathbb{N}}$. In this context, cylinders are the
natural and often studied choice for holes. This corresponds to fixing a
finite word $w=(w_{0}\,w_{1}\dots w_{r-1})\in\mathcal{A}^{r}$ and letting the
hole $H$ be the set of all infinite words in $\mathcal{A}^{\mathbb{N}}$
containing $w$ as the initial sub-word. Throughout, we denote a hole of this
kind by the finite word specifying it. Also, the _length of a hole_ denotes
the length of the corresponding word.

By the previous construction we are led to use combinatorial arguments in our
approach to the escape rate. We first recall some basic notions from [13],
starting with the definition of _weighted autocorrelation polynomial_ of a
word.

######  Definition 2.1.

Let $w\in\mathcal{A}^{*}:=\cup_{n=1}^{\infty}\mathcal{A}^{n}$ be a finite word
and denote by $|w|$ its length. For any letter $a$ in the alphabet
$\mathcal{A}$ we define the _number of occurrences of $a$ in a sub-word of
$w$_ as

$N_{w}(a,k,n):=\left\\{\begin{array}[]{ll}\\#\left\\{i\in[k,n-1]\,:\,w_{i}=a\right\\}\,,&\text{for
}\,0\leq k<n\leq|w|\,;\\\\[5.69046pt] 0\,,&\text{for
}\,k=n\,.\end{array}\right.$

For simplicity we use the notation $N_{w}(a):=N_{w}(a,0,|w|)$.

######  Definition 2.2.

Let $\mathcal{A}=\\{a_{1},\dots,a_{A}\\}$ and $w\in\mathcal{A}^{n}$. The
_autocorrelation vector_ $c=(c_{0},\dots,c_{n-1})$ of $w$ is defined by
setting

$c_{i}=\left\\{\begin{array}[]{ll}1\,,&\text{if
}(w_{i}\,w_{i+1}\,\dots\,w_{n-1})=(w_{0}\,w_{1}\,\dots\,w_{n-1-i})\,;\\\\[5.69046pt]
0\,,&\text{otherwise.}\end{array}\right.$

The _weighted autocorrelation polynomial_ of $w$ is a polynomial in $A+1$
variables, $x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}}$ and $z$, given by

$c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z):=\sum_{j=0}^{n-1}\,c_{j}\,\Big{(}\prod_{a_{i}\in\mathcal{A}}\,(x_{a_{i}})^{N_{w}(a_{i},n-j,n)}\Big{)}\,z^{j}.$

By definition, the weighted autocorrelation polynomial has non-negative
coefficients and in particular $c_{0}=1$.

######  Definition 2.3.

A hole $w$ of finite length is called _prime_ if its autocorrelation vector is
$c=(1,0,\ldots,0)$, whence $c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)=1$.

We now show that the escape rate of a hole $w$ is the logarithm of a root of a
polynomial depending on the measure of the set $\mu(w)$ and on the weighted
autocorrelation polynomial of $w$. A similar result can be found in [15, 16].
The proof of the proposition is in Appendix A and is based on the notion of
the generating function of the survival probability of the hole.

######  Proposition 2.4.

The escape rate $\gamma_{w}$ of a hole $w$ of length $r$ is given by

$\gamma_{w}=\log\,z_{0},$

where $z_{0}$ is the smallest positive root of the polynomial

(2.1)
$\tau_{w}(z):=\mu(w)\,z^{r}+(1-z)\,c_{w}(p_{a_{1}},p_{a_{2}},\dots,p_{a_{A}},z),$

$\mu(w)=\prod_{a_{j}\in\mathcal{A}}\,(p_{a_{j}})^{N_{w}(a_{j})}$ is the
measure of the hole $w$, and $c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)$ is
the weighted autocorrelation polynomial of $w$.

Note that, for all $r\geq 1$ and all $w\in\mathcal{A}^{r}$ we have
$\tau_{w}(z)>0$ for all $z\in[0,1]$, and in particular $z_{0}>1$, so that
$\gamma_{w}>0$.

Among the different polynomials $\tau_{w}$ for the different possible words
$w$, two families stand out as particularly relevant for what follows: the
polynomials for prime words and the polynomials for words that are repetitions
of a single symbol, as for example $w=(aaa\dots a)$.

For a prime hole $w$ of length $r$ and measure $\mu$, it follows immediately
from (2.1) that

(2.2) $\tau_{w}(z)=\mu z^{r}-z+1.$

For a hole of the form $w=(aaa\dots a)$ of length $r$, we start computing
explicitly the weighted autocorrelation polynomial

$c_{w}(x_{a},x_{a_{2}},\dots,x_{a_{A}},z)=\sum_{j=0}^{r-1}\,x_{a}^{j}\,z^{j}=\frac{x_{a}^{r}\,z^{r}-1}{x_{a}\,z-1},$

where we are using the notation of Definition 2.2 with the convention
$a=a_{1}$ for simplicity. Then

(2.3) $\displaystyle\tau_{w}(z)$ $\displaystyle=$ $\displaystyle
p_{a}^{r}\,z^{r}+(1-z)\,\frac{p_{a}^{r}\,z^{r}-1}{p_{a}\,z-1}$
$\displaystyle=$
$\displaystyle\frac{p_{a}^{r}(1-p_{a})\,z^{r+1}-z+1}{1-p_{a}z}.$

Note that the numerator in (2.3) is a polynomial belonging to the previous
family (2.2); more precisely, it is the polynomial of a prime hole of length
$r+1$ (this connection was already found in [6]). Moreover, both the numerator
and the denominator of (2.3) vanish at $\frac{1}{p_{a}}$ (this will be useful
below).

In the next lemma, we show some elementary properties of the family of
polynomials in (2.2) that will be useful in the derivation of our main results
in next section.

######  Lemma 2.5.

Let us consider the family of polynomials

$f_{m}(z)=m\,z^{r}-z+1$

for a fixed $r\geq 2$ and $m\in\mathbb{R}^{+}$. Then:

  1. (i)

$f_{m}(z)$ is convex for all $m\in\mathbb{R}^{+}$ in the set $(0,+\infty)$.

  2. (ii)

Letting $m^{*}_{r}:=\frac{1}{r}(1-\frac{1}{r})^{r-1}$ and
$z^{*}_{r}(m):=(r\,m)^{-\frac{1}{r-1}}$, one has

$f_{m}(z^{*}_{r}(m))\left\\{\begin{array}[]{ll}<0\,,&\text{if
}m<m^{*}_{r};\\\\[5.69046pt] =0\,,&\text{if }m=m^{*}_{r};\\\\[5.69046pt]
>0\,,&\text{if }m>m^{*}_{r};\end{array}\right.$

and $z^{*}_{r}(m^{*}_{r})=\frac{r}{r-1}$.

  3. (iii)

The polynomial $f_{m}(z)$ has two positive roots for $m\in(0,m^{*}_{r})$, one
positive root for $m=m^{*}_{r}$, no positive roots for $m>m^{*}_{r}$.

###### Proof.

(i). Obvious.
(ii) and (iii). Notice that $f_{m}^{\prime}(z)=0$ if and only if
$z=z^{*}_{r}(m)$, hence $z^{*}_{r}(m)$ is a point of local minimum. The sign
of $f_{m}(z^{*}_{r}(m))$ is a computation. ∎

##  3\. The hole with maximal escape rate

In this section we show how to determine the hole with maximal escape rate.
That is, we study how the escape rate varies among the holes of length $r$ and
we determine which one has the maximal escape rate. We start this section by
discussing one of the simplest examples in our setting, that is, the full
shift over two symbols only: this example suffices to show the difficulties
that arise when trying to order all holes of fixed length $r$ by their escape
rate. Indeed, the first discussion of this problem in the context of dynamical
systems can be found in [4]: Bunimovich and Yurchenko showed that if the
symbols of $\mathcal{A}$ are equiprobable, that is, $p_{a_{j}}=\frac{1}{A}$
for all $j=1,\dots,A$, all the holes can be ordered according to their escape
rate just by looking at the length of the shortest periodic pattern they
contain. In the following example we show that, contrary to the above simpler
case, if the symbols have different probabilities, looking only at the
periodic patterns in a hole is not enough to determine the hole with maximal
escape rate. Our main result proves that the measure of a hole, its weighted
autocorrelation polynomial and the probability of the most probable symbol are
the essential ingredients to identify the maximal escape rate for all possible
shifts.

######  Example 3.1.

Let $\mathcal{A}=\left\\{a,b\right\\}$ and $p=p_{a}$, $q=p_{b}$, with $p+q=1$.
We restrict to $p\geq q$ (that is $p\in[\frac{1}{2},1]$) as the other cases
can be recovered by interchanging the symbols of the alphabet. We use
Proposition 2.4 to compute explicitly the escape rates of all holes with
length $r\leq 4$: for these short lengths, the maximal escape rate can be
identified by an explicit computation.

Figure 1. The escape rates $\gamma_{w}$ for $p\in[\frac{1}{2},1]$, for all
holes of length $r=4$.

  * $\bullet\,(r=1)$

It is an elementary computation to show that the word $w=(a)$ has the maximal
escape rate as $\gamma_{a}=-\log(1-p)=-\log q$, and $\gamma_{b}=-\log p$.

  * $\bullet\,(r=2)$

We have two families:

    * (i)

$w\in\\{(aa),(bb)\\}$. Let us start from the case $w=(aa)$. The
autocorrelation vector is $c=(1,1)$, and $N_{aa}(a,1,2)=1$, $N_{aa}(b,1,2)=0$,
hence the weighted autocorrelation polynomial is

$c_{aa}(x,y,z)=1+xz.$

Moreover $N_{aa}(a)=2$ and $N_{aa}(b)=0$, hence

$\tau_{aa}(z)=p^{2}z^{2}+(1-z)\,c_{aa}(p,q,z)=1-qz-pqz^{2},$

from which $z_{0}=\frac{-q+\sqrt{q^{2}+4pq}}{2pq}$ and
$\gamma_{aa}=\log(\frac{-q+\sqrt{q^{2}+4pq}}{2pq})$.

The case $w=(bb)$ works as the previous one, we simply need to interchange the
roles of $p$ and $q$. Hence
$\gamma_{bb}=\log(\frac{-p+\sqrt{p^{2}+4pq}}{2pq})$.

    * (ii)

$w\in\\{(ab),(ba)\\}$ Let us start from the case $w=(ab)$. The autocorrelation
vector is $c=(1,0)$, hence the weighted autocorrelation polynomial is

$c_{ab}(x,y,z)=1.$

Moreover $N_{ab}(a)=1$ and $N_{ab}(b)=1$, hence

$\tau_{ab}(z)=pqz^{2}+(1-z)\,c_{ab}(p,q,z)=(1-pz)(1-qz),$

from which $z_{0}=\frac{1}{p}$ since $p\geq q$. Hence $\gamma_{ab}=-\log p$.

For $w=(ba)$ it turns out that $\tau_{ba}(z)=\tau_{ab}(z)$, hence
$\gamma_{ba}=\gamma_{ab}$.

Note that for $\frac{1}{2}\leq p<\frac{2}{3}$, the holes with maximal escape
rate are $(ab)$ and $(ba)$, whereas for $p>\frac{2}{3}$, the hole with maximal
escape rate is $(aa)$ . At the same time, for all values of
$p\in(\frac{1}{2},1]$, the hole $(aa)$ has measure $\mu(aa)=p^{2}$, greater
than the measure $\mu(ab)=\mu(ba)=pq$.

  * $\bullet\,(r=3)$

This case is similar to the case $r=4$ discussed below. Some further details
can be found in [6].

  * $\bullet\,(r=4)$

Instead of giving explicit formulas (no more difficulties arise in their
derivation than in the case $r=2$, but the formulas are longer and not very
informative), it is more illustrative to plot the different escape rates (see
Fig. 1) and discuss some important features. Firstly, note that for
$p=\frac{1}{2}$ all holes have the same measure and their escape rates can be
ordered by looking at the length of the shortest periodic pattern they
contain, just as discussed in [4]. On the other hand, it is apparent by Fig. 1
that this ordering is destroyed as soon as the two symbols are not
equiprobable. Nevertheless some new patterns can be derived.

In the figure we have used the following notation: curves with the same color
correspond to holes with the same measure; solid curves correspond to prime
holes and dashed curves to non-prime ones (the dashed blue and purple curves
have different styles as they correspond to holes for which there is no prime
hole with the same measure). First, it is apparent that in the family of holes
with the same measure, prime holes (if they exist) are the leakiest (see Lemma
3.2-(i)). For example, the red curves are the plot of the escape rates of the
holes of measure $p^{3}(1-p)$. Among them, the two prime holes $(aaab)$ and
$(baaa)$ have (the same) maximal escape rate (look at the solid red curve). On
the other hand, the escape rates of prime holes with different measures are
ordered, for a fixed $p$, by their measure (see Lemma 3.2-(ii)). One is then
tempted to say that the maximal escape rate among all the holes of fixed
length should be achieved by the prime hole with maximal measure (red solid
curve). But this is not true for all values of $p$, as is apparent by looking
at Fig. 1: for $p>1-\frac{1}{r+1}=\frac{4}{5}$ (see Theorem 3.5) the maximal
escape rate is given by the hole $(aaaa)$, i.e., the hole with the repetition
of the most probable symbol. Finally, the escape rate of the hole $(aaaa)$ is
always greater than that of the similar hole $(bbbb)$ (see Lemma 3.2-(iii)).

The formal derivation of the hole with maximal escape rate is our most
important result. We give it in the next section.

###  3.1. Main results

Let the alphabet $\mathcal{A}$ with $A\geq 2$ symbols be fixed and denote by
$a$ the most probable symbol and by $b$ the second most probable one. Hence we
rename by $\\{a,b,a_{3},\dots,a_{A}\\}$ the symbols in $\mathcal{A}$, with
$p=p_{a}$, $q=p_{b}$; $q+p\leq 1$ and $p_{a_{k}}\leq q\leq p$ for all $k\geq
3$.

As anticipated, an important role is played by prime holes and by holes which
have maximal measure for a fixed length. Using the expression of the
polynomial $\tau_{w}$ in (2.1), we obtain a few basic inequalities which arise
when comparing their escape rates:

######  Lemma 3.2.

Let us consider a fixed $r\geq 2$. Then:

  1. (i)

Let $w_{1}$ and $w_{2}$ be holes of the same length and measure. If $w_{1}$ is
prime then $\gamma_{w_{1}}\geq\gamma_{w_{2}}$, and equality holds only if
$w_{2}$ is also prime.

  2. (ii)

Let $w_{1}$ and $w_{2}$ be prime holes of the same length. If
$\mu(w_{1})>\mu(w_{2})$ then $\gamma_{w_{1}}>\gamma_{w_{2}}$.

  3. (iii)

Let $w_{1}=(a_{i}a_{i}\dots a_{i})$ and $w_{2}=(a_{j}a_{j}\dots a_{j})$ be
holes of the same length given by repetitions of different symbols. If
$p_{a_{i}}\geq p_{a_{j}}$ then $\gamma_{w_{1}}\geq\gamma_{w_{2}}$.

###### Proof.

(i) If $w_{1}$ is prime and $w_{2}$ is not prime, then
$c_{w_{1}}(p_{a},p_{b},\dots,p_{a_{A}},z)=1<c_{w_{2}}(p_{a},p_{b},\dots,p_{a_{A}},z)$
for all $z>0$. Hence by (2.1), for $z>1$ we have
$\tau_{w_{1}}(z)>\tau_{w_{2}}(z)$ and therefore
$\gamma_{w_{1}}>\gamma_{w_{2}}$. If both are prime then
$\tau_{w_{1}}(z)=\tau_{w_{2}}(z)$.
(ii) Note that for a prime hole $w$ we have
$c_{w}(p_{a},p_{b},\dots,p_{a_{A}},z)=1$ and, as shown in (2.2), the
polynomial $\tau_{w}(z)$ belongs to the family studied in Lemma 2.5. Hence, if
$w_{1}$ and $w_{2}$ are prime holes of the same length, it follows that
$\tau_{w_{1}}(z)=f_{m_{1}}(z)$ with $m_{1}=\mu(w_{1})$, and
$\tau_{w_{2}}(z)=f_{m_{2}}(z)$ with $m_{2}=\mu(w_{2})$. Hence if
$\mu(w_{1})>\mu(w_{2})$ then $\tau_{w_{1}}(z)>\tau_{w_{2}}(z)$ for all $z>0$
and $\gamma_{w_{1}}>\gamma_{w_{2}}$.
(iii) Let us assume for simplicity that $a_{i}=a_{1}=a$ and $a_{j}=a_{2}=b$,
so that $p=p_{a_{i}}$ and $q=p_{a_{j}}$, and note that the proof in no way
depends on these being the most probable symbols. Use (2.3) to write

$\tau_{w_{1}}(z)=\frac{p^{r}(1-p)\,z^{r+1}-z+1}{1-pz},\quad\tau_{w_{2}}(z)=\frac{q^{r}(1-q)\,z^{r+1}-z+1}{1-qz}.$

As remarked before, both the numerator and the denominator of
$\tau_{w_{1}}(z)$ vanish at $z=p^{-1}$, and the same is true for
$\tau_{w_{2}}(z)$ at $z=q^{-1}$. In addition, by Lemma 2.5-(iii), the
numerator of $\tau_{w_{1}}(z)$ has two distinct positive roots for
$p\not=1-\frac{1}{r+1}$, and one double positive root for $p=1-\frac{1}{r+1}$
. This follows by using the function $[0,1]\ni x\mapsto g(x):=x^{r}(1-x)$,
which has a strict maximum at $1-\frac{1}{r+1}$. Then

$g(p)=p^{r}(1-p)\leq
g\left(1-\frac{1}{r+1}\right)=\frac{1}{r+1}\left(1-\frac{1}{r+1}\right)^{r}=m_{r+1}^{*}\,,\quad\forall\,p\in[0,1],$

and $p^{r}(1-p)=m_{r+1}^{*}$ if and only if $p=1-\frac{1}{r+1}$. The analogous
result holds for the numerator of $\tau_{w_{2}}(z)$. Hence $\tau_{w_{1}}(z)$
and $\tau_{w_{2}}(z)$ have at most one positive root each, which we denote,
respectively, $z_{0}(\tau_{w_{1}})$ and $z_{0}(\tau_{w_{2}})$.

We now claim that $p^{r}(1-p)\geq q^{r}(1-q)$. The function $g(x)=x^{r}(1-x)$
is increasing in $[0,\frac{r}{r+1}]$ and decreasing in $[\frac{r}{r+1},1]$.
Since $p\geq q$ and $p+q\leq 1$, if $p\leq\frac{r}{r+1}$ then $g(p)\geq g(q)$
and the claim follows. If $p\geq\frac{r}{r+1}$ then $p>\frac{1}{2}$, so that
$(1-p)<p$ and $q\leq(1-p)<\frac{1}{2}<\frac{r}{r+1}$. Then $g(q)\leq g(1-p)$,
hence $q^{r}(1-q)\leq(1-p)^{r}p\leq p^{r}(1-p)$, since $(1-p)^{r-1}\leq
p^{r-1}$. The claim is proved.

Finally, the claim implies that the numerator of $\tau_{w_{1}}(z)$ is greater
or equal than that of $\tau_{w_{2}}(z)$ for all $z\geq 0$, hence
$z_{0}(\tau_{w_{1}})\geq z_{0}(\tau_{w_{2}})$, and thus
$\gamma_{w_{1}}\geq\gamma_{w_{2}}$. ∎

We now use Lemma 3.2 to compare all the different holes with the same length
and conclude that the hole with maximal escape rate is either a prime hole or
a hole with maximal measure. To this end, it is helpful to define the
following families of holes:

(3.1) $\displaystyle P^{r}:=\left\\{w\in\mathcal{A}^{r}:\text{$w$ is a prime
hole, $\mu(w)\geq\mu(\tilde{w})$ for all prime holes
$\tilde{w}\in\mathcal{A}^{r}$}\right\\},$ (3.2) $\displaystyle
M^{r}:=\left\\{w\in\mathcal{A}^{r}:\text{$\mu(w)\geq\mu(\tilde{w})$ for all
$\tilde{w}\in\mathcal{A}^{r}$}\right\\}.$

In words, $P^{r}$ is the set of words of length $r$ for which the
corresponding hole is prime and has maximal measure among all the prime holes;
$M^{r}$ consists of the holes of maximal measure. In what follows, with an
oversimplification of notation, when we write $w_{{}_{P}}$ and $w_{{}_{M}}$ we
will implicitly intend that $w_{{}_{P}}\in P^{r}$ and $w_{{}_{M}}\in M^{r}$.

Using the definition of the symbols $a$ and $b$, one immediately verifies that

$\left\\{(aaa\dots ab)\,,\,(ba\dots aaa)\right\\}\subseteq P^{r},$

thus $\mu(w_{{}_{P}})=p^{r-1}q$ for all $w_{{}_{P}}\in P^{r}$. On the other
hand, since $a$ is the most probable symbol, we have $(aaa\dots a)\in M^{r}$
and $\mu(w_{{}_{M}})=p^{r}$. Notice that the hole $(aaa\dots a)$ is not prime.

######  Remark 3.3.

For what follows it is useful to know when the two sets $P^{r}$ and $M^{r}$
are disjoint or not.

Let $q<p$. In this case $M^{r}=\\{(aaa\dots a)\\}$, so that $M^{r}\cap
P^{r}=\emptyset$. Moreover, for all prime holes $w$, $\mu(w)<\mu(aaa\dots a)$.
On the contrary, for many $w\not=(aaa\dots a)$ there exists a prime hole
$\tilde{w}$ such that $\mu(w)=\mu(\tilde{w})$. In fact, whenever a word
contains at least two different symbols, there exists a prime hole with its
same measure: it is indeed easy to produce a prime hole which contains any
symbol of $\mathcal{A}$ any number of times, for example

$w=(a_{1}\dots a_{1}a_{2}\dots a_{2}\dots a_{A}\dots a_{A}).$

Observe however that this argument does not work for a word given by $r$
repetitions of a single symbol with probability different from those of all
other symbols.

If $q=p$ then $P^{r}\cap M^{r}\neq\emptyset$ as the words $(aaa\dots ab)$ and
$(ba\dots aaa)$ are in the intersection of the two sets.

We can now state our first main result:

######  Theorem 3.4.

Let $r\geq 2$ be a fixed word length. The escape rate $\gamma_{w_{{}_{P}}}$ is
the same for all $w_{{}_{P}}\in P^{r}$, cf. (3.1), and the escape rate
$\gamma_{w_{{}_{M}}}$ is the same for all $w_{{}_{M}}\in M^{r}$, cf. (3.2).
Moreover

$\gamma_{max}^{r}:=\max\left\\{\gamma_{w}\,:\,w\text{ has length
}r\right\\}=\max\\{\gamma_{w_{{}_{P}}}\,,\,\gamma_{w_{{}_{M}}}\\}.$

###### Proof.

The first assertion comes from Proposition 2.4 and (2.2)-(2.3). For a fixed
length $r\geq 2$, we can first group the holes $w$ according to their
measures. Then by Lemma 3.2-(i), for fixed length and measure, the hole with
maximal escape rate is prime, whenever a prime hole with that given measure
exists. By Remark 3.3, if $q<p$ there is no prime hole of measure $p^{r}$
since $P^{r}\cap M^{r}=\emptyset$, and there is no prime hole of measure
$p_{k}^{r}$, if $p_{k}$ is the probability of a symbol in $\mathcal{A}$ and no
other symbol has the same probability. If $q=p$ instead, there is a prime hole
of measure $p^{r}$.

From the above arguments, it remains only to consider the set of prime holes
and the set of holes which have measure different from that of all the prime
holes. As explained in Remark 3.3, these last cases correspond to holes of the
form $(a_{i}a_{i}\dots a_{i})$, words with one single symbol repeated $r$
times. Applying now Lemma 3.2-(ii), the hole with the maximal escape rate
among the prime holes is $w_{{}_{P}}$, and applying Lemma 3.2-(iii), the hole
with the maximal escape rate among the holes with one single symbol repeated
is $w_{{}_{M}}$.

Finally, to obtain the maximal escape rate it is sufficient to compare
$\gamma_{w_{{}_{P}}}$ and $\gamma_{w_{{}_{M}}}$. ∎

####  3.1.1. Explicit expression for the maximal escape in the case of two
symbols

We now show that if $A=2$ we can explicitly identify, for all $r\geq 2$, a
hole with maximal escape rate.

######  Theorem 3.5.

Let $\mathcal{A}=\\{a,b\\}$ with $p=p_{a}\geq q=p_{b}$ satisfying $p+q=1$. For
holes $w$ of fixed length $r\geq 2$,

$\gamma_{max}^{r}=\left\\{\begin{array}[]{ll}\gamma_{w_{{}_{P}}}\,,&\text{if
}p\in\left[\frac{1}{2}\,,\,1-\frac{1}{r+1}\right];\\\\[8.5359pt]
\gamma_{w_{{}_{M}}}\,,&\text{if
}p\in\left[1-\frac{1}{r+1}\,,\,1\right);\end{array}\right.$

where $w_{{}_{P}}$ denotes a word in $P^{r}$, cf. (3.1), and $w_{{}_{M}}$
denotes a word in $M^{r}$, cf. (3.2). In addition, for
$p\in[1-\frac{1}{r}\,,\,1-\frac{1}{r+1}]$ we can explicitly compute that
$\gamma_{w_{{}_{P}}}=\log\frac{1}{p}$ and thus obtain that in this range
$\gamma_{max}^{r}=\log\frac{1}{p}$.

###### Proof.

It is enough to show that it is possible to determine which of the escape
rates of the holes $w_{{}_{P}}$ and $w_{{}_{M}}$ is maximal, and apply Theorem
3.4.

The case $r=2$ is studied in details in Example 3.1. Let us consider a fixed
length $r\geq 3$ and start with the case $p>q$, hence $p>\frac{1}{2}$. We
first deal with the hole $w_{{}_{P}}$, which is a prime hole with maximal
measure among the prime holes. An example is the hole $(aaa\dots ab)$. We have
$\mu(w_{{}_{P}})=p^{r-1}q$ and $\tau_{w_{{}_{P}}}(z)$ is a polynomial of the
family studied in Lemma 2.5 given by

$\tau_{w_{{}_{P}}}(z)=p^{r-1}q\,z^{r}-z+1.$

Applying Lemma 2.5 to $\tau_{w_{{}_{P}}}(z)$ with $m=p^{r-1}q=p^{r-1}(1-p)$,
it follows that $\tau_{w_{{}_{P}}}(z)$ has two distinct positive roots for
$p\not=1-\frac{1}{r}$ and one double positive root for $p=1-\frac{1}{r}$. To
show this it is enough to repeat the argument in the proof of Lemma 3.2-(iii),
using now the function $[0,1]\ni x\mapsto g(x):=x^{r-1}(1-x)$. Let us denote
by $z_{0}(w_{{}_{P}})$ and by $z_{1}(w_{{}_{P}})$ the smallest and the biggest
positive roots of $\tau_{w_{{}_{P}}}(z)$ respectively. Since
$z_{r}^{*}(p^{r-1}q)$ is the point of minimum for the polynomial
$\tau_{w_{{}_{P}}}$ we have

$z_{0}(w_{{}_{P}})\leq
z_{r}^{*}(p^{r-1}q)=\frac{1}{p}\,(r\,q)^{-\frac{1}{r-1}}\leq
z_{1}(w_{{}_{P}}).$

Since $\tau_{w_{{}_{P}}}(\frac{1}{p})=0$ for all $p$, either
$z_{0}(w_{{}_{P}})$ or $z_{1}(w_{{}_{P}})$ is $\frac{1}{p}$. It is clear from
the previous estimate that if $(r\,q)^{-\frac{1}{r-1}}<1$ then
$z_{1}(w_{{}_{P}})=\frac{1}{p}$, and if $(r\,q)^{-\frac{1}{r-1}}\geq 1$ then
$z_{0}(w_{{}_{P}})=\frac{1}{p}$. Thus, using $q=1-p$, we have proved that

(3.3)
$\gamma_{w_{{}_{P}}}\left\\{\begin{array}[]{ll}=\log\frac{1}{p}\,,&\text{if
}p\in\left[1-\frac{1}{r}\,,\,1\right);\\\\[8.5359pt] <\log
z_{r}^{*}(p^{r-1}q)\,,&\text{if
}p\in\left[\frac{1}{2}\,,\,1-\frac{1}{r}\right).\end{array}\right.$

Let us now consider the hole $w_{{}_{M}}$, which is a hole with maximal
measure among all the holes of length $r$. An example is the hole
$w_{{}_{M}}=(aaa\dots a)$, and this is the only example for $p>q$, that is,
for $p>\frac{1}{2}$. Using (2.3), we have

$\tau_{w_{{}_{M}}}(z)=\frac{p^{r}(1-p)\,z^{r+1}-z+1}{1-pz}.$

In particular we know that the numerator has two distinct positive roots for
$p\not=1-\frac{1}{r+1}$ and one of the positive roots is always $\frac{1}{p}$.
Since $\frac{1}{p}$ is also the unique root of the denominator, it follows
that $\tau_{w_{{}_{M}}}(z)$ has only one positive root $z_{0}(w_{{}_{M}})$,
which is the positive root of the numerator not equal to $\frac{1}{p}$. Hence

$\gamma_{w_{{}_{M}}}=\log z_{0}(w_{{}_{M}}).$

From the previous argument on prime holes, we also know that
$z_{0}(w_{{}_{M}})>\frac{1}{p}$ if and only if $p\geq 1-\frac{1}{r+1}$, hence
using (3.3) we conclude that $\gamma_{max}^{r}=\gamma_{w_{{}_{M}}}$ for $p\geq
1-\frac{1}{r+1}$, and $\gamma_{max}^{r}=\gamma_{w_{{}_{P}}}=\log\frac{1}{p}$
for $p\in[1-\frac{1}{r}\,,\,1-\frac{1}{r+1}]$.

To conclude the argument, we need to consider the case
$p\in(\frac{1}{2},1-\frac{1}{r}]$, for which both $z_{0}(w_{{}_{P}})$ and
$z_{0}(w_{{}_{M}})$ are smaller than $\frac{1}{p}$. To compare these two
values, we introduce the following notation. Let

(3.4) $\bar{\tau}_{r,p}(z):=p^{r-1}(1-p)\,z^{r}-z+1,$

then

$\tau_{w_{{}_{P}}}(z)=\bar{\tau}_{r,p}(z)\quad\text{and}\quad\tau_{w_{{}_{M}}}(z)=\frac{\bar{\tau}_{r+1,p}(z)}{1-pz}.$

By the previous arguments, the polynomial $\bar{\tau}_{r,p}(z)$ has two
positive roots, one is $\frac{1}{p}$ and let us denote the other by
$\bar{z}_{r}(p)$. Recall that $\bar{z}_{r}(p)=\frac{1}{p}$ if and only if
$p=1-\frac{1}{r}$. In addition, we have shown that for
$p\in(\frac{1}{2},1-\frac{1}{r}]$, one has
$z_{0}(w_{{}_{M}})=\bar{z}_{r+1}(p)<\frac{1}{p}$ and
$z_{0}(w_{{}_{P}})=\bar{z}_{r}(p)<\frac{1}{p}$. Since
$\bar{\tau}_{r,p}(z)\geq\bar{\tau}_{r+1,p}(z)$ for $z\in[1,\frac{1}{p}]$ and
for all $r$, it follows that $\bar{z}_{r}(p)\geq\bar{z}_{r+1}(p)$ for
$p\in(\frac{1}{2},1-\frac{1}{r}]$. Hence
$\gamma_{max}^{r}=\gamma_{w_{{}_{P}}}=\log\bar{z}_{r}(p)$ for
$p\in(\frac{1}{2}\,,\,1-\frac{1}{r}]$.

Finally, if $r\geq 3$ and $p=q=\frac{1}{2}$, we know that $(aa\dots ab)$ is an
example of a word in $P^{r}\cap M^{r}$, and by Theorem 3.4, it follows
$\gamma_{max}^{r}=\gamma_{w_{{}_{P}}}=\gamma_{w_{{}_{M}}}$.

We have thus finished the proof of the theorem, and can collect all the
information on the maximal escape rate by saying that

$\gamma_{max}^{r}=\left\\{\begin{array}[]{ll}\gamma_{w_{{}_{P}}}=\log\bar{z}_{r}(p)\,,&\text{if
}p\in\left[\frac{1}{2}\,,\,1-\frac{1}{r}\right];\\\\[8.5359pt]
\gamma_{w_{{}_{P}}}=\log\frac{1}{p}\,,&\text{if
}p\in\left[1-\frac{1}{r}\,,\,1-\frac{1}{r+1}\right];\\\\[8.5359pt]
\gamma_{w_{{}_{M}}}=\log\bar{z}_{r+1}(p)\,,&\text{if
}p\in\left[1-\frac{1}{r+1}\,,\,1\right).\end{array}\right.$

∎

####  3.1.2. Maximal escape in the case of more than two symbols

The situation is more intricate in the case with more than two symbols, that
is $A>2$, as elucidated by the following:

######  Proposition 3.6.

With the notation of Theorem 3.4, let the alphabet $\mathcal{A}$ have $A>2$
elements, and let $a$ and $b$ be the two most probable symbols with
probabilities given by $p$ and $q$ respectively. Let $r\geq 2$ be a fixed
length, then $\gamma_{max}^{r}=\gamma_{w_{{}_{M}}}$ for $p\geq
1-\frac{1}{r+1}$. In addition, if $q<p(1-p)$ then
$\gamma_{max}^{r}=\gamma_{w_{{}_{M}}}$ for
$p\in[\frac{1}{2},1-\frac{1}{r+1}]$. On the other hand, there exist values of
$q$ sufficiently close to $1-p$ and of $p\in(\frac{1}{2},1-\frac{1}{r+1})$,
such that $\gamma_{max}^{r}=\gamma_{w_{{}_{P}}}$.

###### Proof.

Let us first consider the hole $w_{{}_{M}}=(aaa\dots a)$. As in the proof of
Theorem 3.5 we can write

$\tau_{w_{{}_{M}}}(z)=\frac{\bar{\tau}_{r+1,p}(z)}{1-pz}$

where $\bar{\tau}_{r+1,p}(z)$ is as in (3.4), and
$\gamma_{w_{{}_{M}}}=\log\bar{z}_{r+1}(p)$, whence
$\gamma_{w_{{}_{M}}}\geq\log\frac{1}{p}$ for $p\geq 1-\frac{1}{r+1}$.

On the other hand, a prime hole $w_{{}_{P}}$ of length $r$ has measure
$p^{r-1}q$ and polynomial

$\tau_{w_{{}_{P}}}(z)=p^{r-1}q\,z^{r}-z+1\leq\bar{\tau}_{r,p}(z),\quad\forall\,z>0\,,$

because $q\leq 1-p$. Hence by the proof of Theorem 3.5, $\gamma_{w_{{}_{P}}}$
is smaller than $\log\frac{1}{p}$ for $p\geq 1-\frac{1}{r}$.

We have thus proved, using Theorem 3.4, that
$\gamma_{max}^{r}=\gamma_{w_{{}_{M}}}$ for $p\geq 1-\frac{1}{r+1}$.

Let us now assume that $q<p(1-p)$. Then
$\tau_{w_{{}_{P}}}(z)<\bar{\tau}_{r+1,p}(z)$ for all $z>1$, and since
$z_{0}(w_{{}_{P}})>1$ it follows that $z_{0}(w_{{}_{P}})<\bar{z}_{r+1}(p)$ for
all $p$. Then $\gamma_{w_{{}_{P}}}\leq\gamma_{w_{{}_{M}}}$ for all
$p\in[\frac{1}{2},1]$.

Note that the previous result is different from that for shifts on two
symbols. However, all the quantities that we are using have continuous
dependence on the probabilities of the symbols. Hence, if $q$ is sufficiently
close to $1-p$, that is if we are sufficiently close to the case of shifts on
two symbols, we expect to find the same kind of results obtained in Theorem
3.5. Therefore there exist values of $p<1-\frac{1}{r+1}$ for which the maximal
escape rate is achieved by a prime hole $w_{{}_{P}}$. ∎

######  Remark 3.7.

In the case of two equiprobable symbols, $A=2$ with $p=1-p=\frac{1}{2}$, in
[4] the authors prove that prime holes have the maximal escape rate among the
holes with the same measure and length, but also show that it is possible to
order same-measure holes according to their escape rate by using the minimal
period of periodic points in the hole. In this paper we have proved that prime
holes have maximal escape rate among the holes with the same measure and same
length, also in the case of non-equiprobable symbols, that is $A=2$ and
$p\not=\frac{1}{2}$. One may wonder whether also the ordering found in [4] for
non-prime holes is preserved when the symbols are not equiprobable. We show
that this is not the case. We find same-length words $w$ and $\tilde{w}$ such
that the corresponding holes are not prime and have the same measure, and such
that there exists $p^{*}\in(\frac{1}{2},1)$ with
$\gamma_{w}>\gamma_{\tilde{w}}$, for $p\in(\frac{1}{2},p^{*})$, and
$\gamma_{w}<\gamma_{\tilde{w}}$ for $p\in(p^{*},1)$. Hence the ordering of the
holes does not only depend on the length of the periodic orbits in the hole.
One can check that this phenomenon occurs for example for $w=(aabbaa)$ and
$\tilde{w}=(baaaab)$, with $p^{*}\approx\frac{\sqrt{2}}{2}$: the hole $w$
contains a periodic orbit with period four, whereas the minimal period of the
periodic orbits contained in the hole $\tilde{w}$ is five. For holes shrinking
to a periodic point the escape rate behaves as the instability factor of the
orbit. In this case we remark that the two factors for $w$ and $\tilde{w}$ are
the same for $p=\frac{\sqrt{5}-1}{2}<p^{*}$, hence this does not seem to be
the reason for the order switching found above.

####  3.1.3. Estimates

By Theorem 3.4, the maximal escape rate may be obtained simply by comparing
the roots of the polynomials $\tau_{w_{P}}$ and $\tau_{w_{M}}$. While for
small $r$ such roots can be computed exactly, for large $r$ one should rely on
numerical approximations, that in principle provide a value with arbitrary
precision. On the other hand, if a numerical approximation is not at hand, it
could be relevant to have rigorous estimates of the maximal escape rate, in
particular for given $p$ and large length $r$. In this section we show that,
with elementary arguments, one can obtain explicit estimates of the maximal
escape rate in the case of a two-symbol alphabet (see Fig. 2 for examples).

We start by giving an estimate on the escape rate for prime holes which holds
for all finite alphabets, $A\geq 2$.

######  Lemma 3.8.

Let us consider a fixed $r\geq 2$. If $w$ is a prime hole of length $r$ we
have

$\log\left(\frac{1+r(r-2)\mu(w)-\sqrt{1-r\mu(w)(2+(r-2)\mu(w))}}{r(r-1)\mu(w)}\right)\leq\gamma_{w}\leq\frac{1}{r-1}\log\frac{1}{r\mu(w)}.$

###### Proof.

For a prime hole $w$ we have $\mu(w)\leq\mu(w_{{}_{P}})=p^{r-1}q\leq
p^{r-1}(1-p)$ where $p$ and $q$ are the probabilities of the most probable and
of the second most probable symbols. As in the proof of Lemma 3.2-(iii), using
the function $g(x):=x^{r-1}(1-x)$ on $[0,1]$, one has

$p^{r-1}(1-p)\leq
m_{r}^{*}=\frac{1}{r}\left(1-\frac{1}{r}\right)^{r-1},\quad\forall\,p\in[0,1],$

and $p^{r-1}(1-p)=m_{r}^{*}$ if and only if $p=1-\frac{1}{r}$. Hence
$\mu(w)\leq m_{r}^{*}$ for all prime holes $w$, and $\mu(w)=m_{r}^{*}$ if and
only if $\mu(w)=p^{r-1}(1-p)$ for $p=1-\frac{1}{r}$. Since we can apply Lemma
2.5 to $\tau_{w}(z)$, we obtain that $\tau_{w}(z)$ has at least one root
$z_{0}>1$, and if $z_{0}$ is the smallest positive root then

$z_{0}\leq
z^{*}_{r}(\mu(w))=\left(\frac{1}{r\,\mu(w)}\right)^{\frac{1}{r-1}}.$

To prove the bound from below, recall that by Lemma 2.5 the polynomial
$\tau_{w}(z)$ is convex in $(0,+\infty)$, and for the derivatives we have
$\tau^{(j)}_{w}(1)>0$ for all $j\geq 2$. Hence $z_{0}$, the smallest positive
root of $\tau_{w}(z)$, is greater than 1, and we can bound $\tau_{w}(z)$ from
below by its osculating parabola at $z=1$, that is

$\tau_{w}(z)\geq\frac{1}{2}\,\tau^{\prime\prime}_{w}(1)(z-1)^{2}+\tau^{\prime}_{w}(1)\,(z-1)+\tau_{w}(1),\quad\forall\,z\geq
1.$

Since $\tau_{w}(1)=\mu(w)>0$ and $\tau^{\prime}_{w}(1)=r\mu(w)-1<0$, the roots
of the osculating parabola are both greater than 1. It follows that the
smallest positive root $z_{0}$ of $\tau_{w}(z)$ is greater than the smallest
root of the osculating parabola. ∎

When the alphabet has two symbols, by Theorem 3.5 we know which hole has the
maximal escape rate, and it is simpler to estimate the smallest positive root
of the associated polynomial also thanks to Lemma 3.8.

######  Corollary 3.9.

Let $\mathcal{A}=\\{a,b\\}$ with $a$ the symbol with largest probability
$p\in[\frac{1}{2},1]$. For holes $w$ of fixed length $r\geq 2$ the maximal
escape rate satisfies:

  * (i)

If $p\in\left[\frac{1}{2},1-\frac{1}{r}\right)$ then

$\gamma_{max}^{r}\in\left[\log\bar{\gamma}(p,r)\,,\,\frac{1}{r-1}\,\log\frac{1}{rp^{r-1}(1-p)}\right]$

where

$\bar{\gamma}(p,r)=\frac{1+r(r-2)\mu(w_{P})-\sqrt{1-r\mu(w_{P})(2+(r-2)\mu(w_{P}))}}{r(r-1)\mu(w_{P})}$

with $\mu(w_{P})=p^{r-1}(1-p)$.

  * (ii)

If $p\in\left[1-\frac{1}{r},1-\frac{1}{r+1}\right]$ then

$\gamma_{max}^{r}=\log\frac{1}{p}.$

  * (iii)

If $p\in\left(1-\frac{1}{r+1},1\right)$ then

$\gamma_{max}^{r}\in\left[\log\frac{1}{p}+\frac{1}{r}\,\log\frac{1}{(r+1)(1-p)}\,,\,\log\left(\frac{-1+p+\sqrt{(1-p)^{2}+4p(1-p)}}{2p(1-p)}\right)\right].$

###### Proof.

For $p\leq 1-\frac{1}{r+1}$ we apply Theorem 3.5 and Lemma 3.8 to the hole
$w_{P}$ for which $\mu(w_{P})=p^{r-1}(1-p)$.

For $p>1-\frac{1}{r+1}$, we use that $\gamma_{max}^{r}=\gamma_{w_{M}}$ and
that

$\tau_{w_{{}_{M}}}(z)=\frac{\bar{\tau}_{r+1,p}(z)}{1-pz}$

with $\bar{\tau}_{r+1,p}$ defined in (3.4). It follows that
$\gamma_{w_{M}}=\log z_{0}(w_{M})$, where $z_{0}(w_{M})>\frac{1}{p}$ is one of
the two positive roots of the polynomial $\bar{\tau}_{r+1,p}$ defined in
(3.4), the other being $\frac{1}{p}$. By Lemma 2.5, it follows that
$z_{0}(w_{M})$ is the largest root of $\bar{\tau}_{r+1,p}$, and then with
$q=1-p$,

$z_{0}(w_{M})\geq
z_{r+1}^{*}(p^{r}q)=\frac{1}{p}\,\Big{(}q(r+1)\Big{)}^{-\frac{1}{r}}.$

This gives the lower bound for $\gamma_{max}^{r}$ for $p>1-\frac{1}{r+1}$. To
obtain the upper bound, we use (2.3) to write

$\tau_{w_{{}_{M}}}(z)=p^{r}z^{r}+(1-z)\,\sum_{j=0}^{r-1}\,p^{j}z^{j}=1-(1-p)\sum_{j=1}^{r}\,p^{j-1}\,z^{j}.$

It follows that $\tau_{w_{{}_{M}}}(z)$ is less than any truncated sum of its
terms for all $z\geq 0$. In particular, truncating the sum at $k=2$ one gets

$\tau_{w_{{}_{M}}}(z)\leq 1-(1-p)z-p(1-p)z^{2}=\tau_{aa}(z)$

for all $z\geq 0$, where $\tau_{aa}(z)$ is the polynomial associated to the
hole $(aa)$ in Example 3.1. In particular the unique positive root of
$\tau_{w_{{}_{M}}}(z)$ is less or equal than the unique positive root of
$\tau_{aa}(z)$. ∎

Finally, we remark that the lower bounds turn out to be quite precise: the
relative error between the exact value and the estimates decays to zero
exponentially fast with the length $r$ (see Fig. 2).

Figure 2. The relative error between a very precise numerical approximation of
$\gamma^{r}_{max}$ and the lower bound $l_{b}$ in Corollary 3.9, defined by
$RE(r):=(\gamma^{r}_{max}-l_{b})/\gamma^{r}_{max}$ and displayed as a function
of the length $r$ of the hole in log-linear scale. The decay towards zero
shows that the accuracy of the estimate improves exponentially with the length
of the hole. Different curves correspond to different values of $p$ (from
bottom to top: $p=0.85$, $p=0.9$, $p=0.95$).

##  4\. The case of Markov measures

In the previous sections we have considered the dynamical system
$(\mathcal{A}^{\mathbb{N}},\sigma)$ endowed with a product probability
measure. In this section we discuss the extension of some of our results to
the case of _Markov measures_ limiting ourselves to the alphabet
$\mathcal{A}=\\{a,b\\}$ with two symbols. Given a stochastic matrix

$\Pi=\begin{pmatrix}\pi_{aa}&\pi_{ab}\\\ \pi_{ba}&\pi_{bb}\end{pmatrix}$

with $\pi_{ij}\geq 0$ for all $i,j\in\mathcal{A}$ and
$\pi_{aa}+\pi_{ab}=\pi_{ba}+\pi_{bb}=1$, we consider the set

$\mathcal{A}^{\mathbb{N}}_{{}_{\Pi}}:=\left\\{\omega\in\mathcal{A}^{\mathbb{N}}\,:\,\pi_{\omega_{i}\omega_{i+1}}>0\,\text{
for all $i\geq 0$}\right\\}$

and the action of the shift transformation $\sigma$ on
$\mathcal{A}^{\mathbb{N}}_{{}_{\Pi}}$. One can define analogously the set of
allowed finite words $\mathcal{A}^{*}_{{}_{\Pi}}$. It is well known that if
the matrix $\Pi$ is irreducible and aperiodic, that is, there exists $N>0$
such that all the entries of $\Pi^{n}$ are positive for $n\geq N$, then there
is a unique vector $p=(p_{a},p_{b})$ such that $p_{a},p_{b}>0$,
$p_{a}+p_{b}=1$ and $p\Pi=p$. In this situation the shift $\sigma$ preserves
the probability measure $m_{{}_{\Pi}}$, called the _Markov measure_ , defined
on finite words $s=(s_{0}s_{1}\dots s_{k-1})\in\mathcal{A}^{k}$ to be

$m_{{}_{\Pi}}(s)=p_{s_{0}}\,\prod_{j=0}^{k-2}\,\pi_{s_{j}\,s_{j+1}}.$

In this section we are interested to the symbolic dynamical system
$(\mathcal{A}^{\mathbb{N}}_{{}_{\Pi}},m_{{}_{\Pi}},\sigma)$, which is well
known to be ergodic. We can then study the escape rates for holes in
$\mathcal{A}^{\mathbb{N}}_{{}_{\Pi}}$ given by finite words.

The following parameter $\chi_{{}_{\Pi}}\in(-1,1)$ will play an important
role:

(4.1) $\chi_{{}_{\Pi}}:=\pi_{aa}+\pi_{bb}-1.$

Note that for $\chi_{{}_{\Pi}}=0$ we have $\pi_{aa}=\pi_{ba}$, hence the rows
of $\Pi$ are equal and the Markov measure becomes a product measure. Thus the
case $\chi_{{}_{\Pi}}=0$ corresponds to those studied in the previous
sections.

Special examples of the system
$(\mathcal{A}^{\mathbb{N}}_{{}_{\Pi}},m_{{}_{\Pi}},\sigma)$ are _subshifts of
finite type_ , which correspond to stochastic matrices $\Pi$ with at least one
vanishing entry. In addition, shifts with a Markov measure are isomorphic to
piecewise linear Markov maps of the interval and to Markov chains, hence our
results hold for these classes of systems too. We also mention that, while
interesting in their own right, Markov systems are often used as first-order
approximations of more general nonlinear systems.

We start by introducing the autocorrelation polynomial of a finite word
adapted to the Markov case:

######  Definition 4.1.

Let $s\in\\{a,b\\}^{n}$, and let $c=(c_{0},\dots,c_{n-1})$ denote its
autocorrelation vector given in Definition 2.2. Then the _Markovian weighted
autocorrelation polynomial_ of $s$ is a polynomial in 5 variables given by

$c_{s,M}(y_{aa},y_{ab},y_{ba},y_{bb},z):=\sum_{j=0}^{n-1}\,c_{j}\,\Big{(}\prod_{i=1}^{j}\,y_{s_{n-i-1}\,s_{n-i}}\Big{)}\,z^{j}$

with the convention $\prod_{i=1}^{0}\,y_{s_{n-i-1}\,s_{n-i}}=1$.

In Appendix B we prove the following result.

######  Proposition 4.2.

The escape rate $\gamma_{w}$ of a hole $w$ of length $r$ is given by

$\gamma_{w}=\log\,z_{0}\,,$

where $z_{0}$ is the smallest positive zero of the polynomial

(4.2) $\displaystyle\tau_{w,\Pi}(z):=$
$\displaystyle\mu_{{}_{\Pi}}(w)\,z^{r}\Big{(}\pi_{w_{r-1}w_{0}}-\chi_{{}_{\Pi}}\,z\,\delta_{w_{0}w_{r-1}}\Big{)}$
$\displaystyle+(1-z)\,(1-\chi_{{}_{\Pi}}\,z)\,c_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z).$

Here $\mu_{{}_{\Pi}}(w):=\prod_{j=0}^{r-2}\,\pi_{w_{j}w_{j+1}}$ is the
$m_{{}_{\Pi}}$-measure of the hole $w$ divided by the probability $p_{w_{0}}$
of the first symbols of $w$, the symbol $\delta_{\cdot,\cdot}$ denotes the
classical Kronecker delta, and $c_{w,M}(y_{aa},y_{ab},y_{ba},y_{bb},z)$ is the
Markovian weighted autocorrelation polynomial of $w$.

Note that the polynomial $\tau_{w,\Pi}(z)$ is of degree $r$. In fact the
Markovian weighted autocorrelation polynomial can be written as

$c_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)=\delta_{w_{0},w_{r-1}}\,\mu_{{}_{\Pi}}(w)\,z^{r-1}+\tilde{c}_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)\,,$

where
$\tilde{c}_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z):=\sum_{j=0}^{r-2}\,c_{j}\,\Big{(}\prod_{i=1}^{j}\,\pi_{w_{r-i-1}\,w_{r-i}}\Big{)}\,z^{j}$.
Hence the terms of degree $r+1$ in (4.2) cancel out. Moreover, we can write

(4.3) $\displaystyle\tau_{w,\Pi}(z)=$
$\displaystyle\tilde{\mu}_{{}_{\Pi}}(w)\,z^{r}+(1-z)\,(1-\chi_{{}_{\Pi}}\,z)\,\tilde{c}_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)$
$\displaystyle+\delta_{w_{0}w_{r-1}}\mu_{{}_{\Pi}}(w)(1-(1+\chi_{{}_{\Pi}})\,z)\,z^{r-1},$

where
$\tilde{\mu}_{{}_{\Pi}}(w):=\mu_{{}_{\Pi}}(w)\,\pi_{w_{r-1}w_{0}}=\prod_{j=0}^{r-1}\,\pi_{w_{j}w_{j+1}}$
with $w_{r}:=w_{0}$.

######  Example 4.3.

Consider the case of holes of length $r=2$.

  * $w\in\\{(aa),(bb)\\}$.

Let us start with the case $w=(aa)$. The autocorrelation vector is $c=(1,1)$,
and the Markovian weighted autocorrelation polynomial is

$\tilde{c}_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)=1\,,\qquad\delta_{w_{0},w_{r-1}}\,\mu_{{}_{\Pi}}(w)\,z^{r-1}=\pi_{aa}\,z.$

Hence with $\tilde{\mu}_{{}_{\Pi}}(w)=\pi^{2}_{aa}$ we obtain

$\tau_{w,\Pi}(z)=-(1-\pi_{aa})(1-\pi_{bb})\,z^{2}-\pi_{bb}\,z+1$

and the smallest positive zero is given by

$z_{0}=\left\\{\begin{array}[]{ll}\frac{-\pi_{bb}+\sqrt{\pi^{2}_{bb}+4(1-\pi_{aa})(1-\pi_{bb})}}{2(1-\pi_{aa})(1-\pi_{bb})}\,,&\text{if
}\,(1-\pi_{aa})(1-\pi_{bb})\not=0;\\\\[5.69046pt]
\frac{1}{\pi_{bb}}\,,&\text{if
}\,(1-\pi_{aa})(1-\pi_{bb})=0.\end{array}\right.$

The case $w=(bb)$ works analogously, interchanging the role of $\pi_{aa}$ and
$\pi_{bb}$. Hence the smallest positive zero of $\tau_{w,\Pi}$ is given by

$z_{0}=\left\\{\begin{array}[]{ll}\frac{-\pi_{aa}+\sqrt{\pi^{2}_{aa}+4(1-\pi_{aa})(1-\pi_{bb})}}{2(1-\pi_{aa})(1-\pi_{bb})}\,,&\text{if
}\,(1-\pi_{aa})(1-\pi_{bb})\not=0;\\\\[5.69046pt]
\frac{1}{\pi_{aa}}\,,&\text{if
}\,(1-\pi_{aa})(1-\pi_{bb})=0.\end{array}\right.$

  * $w\in\\{(ab),(ba)\\}$.

For both holes, the autocorrelation vector is $c=(1,0)$, and the Markovian
weighted autocorrelation polynomial is

$c_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)=\tilde{c}_{w,M}(\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)=1.$

Hence with
$\tilde{\mu}_{{}_{\Pi}}(w)=\pi_{ab}\pi_{ba}=(1-\pi_{aa})(1-\pi_{bb})$ we
obtain

$\tau_{w,\Pi}(z)=\pi_{aa}\pi_{bb}\,z^{2}-(\pi_{aa}+\pi_{bb})\,z+1$

and the smallest positive zero is given by

$z_{0}=\frac{1}{\max\\{\pi_{aa},\pi_{bb}\\}}.$

The previous example shows that the identification of the hole with maximal
escape rate for shifts with a Markov measure is a much more difficult problem
than the system with a product measure. When trying to extend the results in
Section 3 to this case, one immediately finds differences and subtleties; here
we made a first step in this direction. The investigation of the Markov case
in its generality is outside the scope of the present work and will be the
subject of future study.

We start with the analogue of Lemma 3.2. As we will see, in this case it is
useful to compare holes with the same length and quantity
$\tilde{\mu}_{{}_{\Pi}}$ introduced in (4.3), which replaces the measure of a
hole.

######  Proposition 4.4.

Let $w_{1}$ and $w_{2}$ be two holes of the same length with
$\tilde{\mu}_{{}_{\Pi}}(w_{1})=\tilde{\mu}_{{}_{\Pi}}(w_{2})$, and let $w_{1}$
be prime. If $w_{2}$ is prime then $\gamma_{w_{1}}=\gamma_{w_{2}}$. If $w_{2}$
is not prime, then:

  1. (i)

If $\chi_{{}_{\Pi}}>0$ we have $\gamma_{w_{1}}>\gamma_{w_{2}}$.

  2. (ii)

If $\chi_{{}_{\Pi}}<0$ and $w_{2}$ is such that
$(w_{2})_{0}\not=(w_{2})_{r-1}$, then $\gamma_{w_{1}}>\gamma_{w_{2}}$.

###### Proof.

Let $w_{1}$ be a prime hole of length $r$. We have $c_{w_{1},M}(z)=1$ and

$\tau_{w_{1},\Pi}(z)=\tilde{\mu}_{{}_{\Pi}}(w_{1})\,z^{r}+(1-z)(1-\chi_{{}_{\Pi}}z).$

It is clear that if $w_{2}$ is prime and
$\tilde{\mu}_{{}_{\Pi}}(w_{2})=\tilde{\mu}_{{}_{\Pi}}(w_{1})$, then
$c_{w_{2},M}(z)=1$ and $\tau_{w_{2},\Pi}=\tau_{w_{1},\Pi}$. Let’s assume that
$w_{2}$ is not prime.

(i) Let $\chi_{{}_{\Pi}}>0$. Since $\frac{1}{\chi_{{}_{\Pi}}}>1$, all the
positive roots of $\tau_{w_{1},\Pi}(z)$ are contained in the interval
$(1,\frac{1}{\chi_{{}_{\Pi}}})$. Since $w_{2}$ is not prime, at least one
condition between $\tilde{c}_{w_{2},M}(z)>1$ and
$\delta_{(w_{2})_{0}(w_{2})_{r-1}}=1$ holds. Then using (4.3)

$\tau_{w_{2},\Pi}(z)<\tilde{\mu}_{{}_{\Pi}}(w_{2})\,z^{r}+(1-z)(1-\chi_{{}_{\Pi}}z)=\tau_{w_{1},\Pi}(z),\quad\forall\,z\in\left(1,\frac{1}{\chi_{{}_{\Pi}}}\right),$

because $(1-z)(1-\chi_{{}_{\Pi}}z)<0$ and $(1-(1+\chi_{\Pi})z)<0$ in the
interval $(1,\frac{1}{\chi_{{}_{\Pi}}})$. Since $\tau_{w_{1},\Pi}(z)$ has a
root in $(1,\frac{1}{\chi_{{}_{\Pi}}})$ it follows that the smallest positive
root of $\tau_{w_{2},\Pi}$ is smaller than that of $\tau_{w_{1},\Pi}$, hence
$\gamma_{w_{1}}>\gamma_{w_{2}}$.

(ii) Let $\chi_{{}_{\Pi}}<0$. In this case the term $(1-\chi_{{}_{\Pi}}z)$ is
positive for $z>0$, and we only know that the positive roots of
$\tau_{w_{1},\Pi}(z)$ are greater than 1. Since $w_{2}$ is not prime, if
$(w_{2})_{0}\not=(w_{2})_{r-1}$ then $\tilde{c}_{w_{2},M}(z)>1$ and using
(4.3)

$\tau_{w_{2},\Pi}(z)<\tilde{\mu}_{{}_{\Pi}}(w_{2})\,z^{r}+(1-z)(1-\chi_{{}_{\Pi}}z)=\tau_{w_{1},\Pi}(z),\quad\forall\,z>1.$

Hence the smallest positive root of $\tau_{w_{2},\Pi}$ is smaller than that of
$\tau_{w_{1},\Pi}$, and $\gamma_{w_{1}}>\gamma_{w_{2}}$. ∎

When the parameter $\chi_{{}_{\Pi}}$ is negative, it is possible to find
conditions for a stochastic matrix to have non-prime holes with a larger
escape rate than the prime holes with the same $\tilde{\mu}_{{}_{\Pi}}$.

If $w_{1}=(aabb\dots b)$ and $w_{2}=(abb\dots ba)$ are two words of length
$r\geq 3$ with two symbols $a$ and $r-2$ symbols $b$, then

$\tilde{\mu}_{{}_{\Pi}}(w_{1})=\tilde{\mu}_{{}_{\Pi}}(w_{2})=\pi_{aa}\,\pi_{ab}\,\pi_{ba}\,\pi_{bb}^{r-3}.$

The hole $w_{1}$ is prime whereas $w_{2}$ is not prime, and

$\displaystyle\tau_{w_{1},\Pi}(z)=\tilde{\mu}_{{}_{\Pi}}(w_{1})\,z^{r}+(1-z)(1-\chi_{{}_{\Pi}}z),$
$\displaystyle\tau_{w_{2},\Pi}(z)=\tau_{w_{1},\Pi}(z)+\pi_{ab}\,\pi_{ba}\,\pi_{bb}^{r-3}(1-(1+\chi_{{}_{\Pi}})z)\,z^{r-1}.$

Therefore $\tau_{w_{2},\Pi}(z)>\tau_{w_{1},\Pi}(z)$ for
$z\in(1,\frac{1}{1+\chi_{{}_{\Pi}}})$, and
$\tau_{w_{2},\Pi}(z)<\tau_{w_{1},\Pi}(z)$ for $z>\frac{1}{1+\chi_{{}_{\Pi}}}$.
Hence $\gamma_{w_{2}}>\gamma_{w_{1}}$ if and only if the smallest positive
root of $\tau_{w_{1},\Pi}$ is smaller than $\frac{1}{1+\chi_{{}_{\Pi}}}$.

In Fig. 3 we show the behaviour of the escape rates for the holes of length
$r=3$ as functions of $\pi_{aa}$ and $\pi_{bb}$. The figure clearly shows that
for $\chi_{{}_{\Pi}}$ negative there are values of $\pi_{aa}$ and $\pi_{bb}$
for which the maximal escape rate is realized by the holes $(aba)$ and $(bab)$
(green surface), which are neither prime nor a repetition of a single symbol.

Figure 3. The escape rates for the system of Section 4, as functions of
$\pi_{aa},\pi_{bb}\in(0,1)$: the blue graph is for the holes $w=(aaa)$ and
$w=(bbb)$; the red graph is for the holes $w=(aab)$, $w=(bba)$, $w=(baa)$ and
$w=(abb)$; the green graph is for the holes $w=(aba)$ and $w=(bab)$.

######  Remark 4.5.

We briefly compare the results of this section with those of [16]. The
theorems of [16] hold for subshifts of finite type also with more than two
symbols (some of the results actually require the number of symbols in the
alphabet to be larger than a certain bound) and with respect to the _Parry
measure_ , the Markov measure of maximal entropy. In the cases covered by both
papers, one can easily check that the results obtained by our Proposition 4.2
coincide with those in [16, Thm 2.1] (see also [15, Thm 3.1]) in the
elementary case of holes of length $r=2$, by following the computations in
Example 4.3 in the case $\pi_{aa}=0$ or $\pi_{bb}=0$ (these are the only cases
of a $2\times 2$ irreducible and aperiodic stochastic matrix $\Pi$ with one
vanishing entry). For holes of length $r\geq 3$ the escape rates have
cumbersome or implicit expressions, therefore the only convenient way to
compare escape rate is by numerical approximation.

##  Appendix A Proof of Proposition 2.4

Given a hole $w$ of length $r$, we have

$S_{n}=\left\\{\omega\in\mathcal{A}^{\mathbb{N}}\,:\,\omega^{n+r}\,\text{ does
not contain $w$ as a sub-word}\right\\},\quad\forall\,n\geq 0$

where $\omega^{k}\in\mathcal{A}^{k}$ denotes the finite sub-word of $\omega$
given by the first $k$ symbols. Let us introduce the sets

(A.1)
$\Sigma_{\ell}:=\Sigma_{\ell}^{(w)}:=\left\\{s\in\mathcal{A}^{\ell}\,:\,s\text{
does not contain $w$ as a sub-word}\right\\},$

then clearly $\Sigma_{\ell}=\mathcal{A}^{\ell}$ for $\ell<r$, and we can write

(A.2)
$S_{n}=\left\\{\omega\in\mathcal{A}^{\mathbb{N}}\,:\,\omega^{n+r}\,\in\Sigma_{n+r}\right\\},\quad\forall\,n\geq
0.$

Let us recall that a word $s\in\mathcal{A}^{\ell}$ defines a cylinder
$C_{s}\subset\mathcal{A}^{\mathbb{N}}$, the set of all words in
$\mathcal{A}^{\mathbb{N}}$ beginning with $s$, and that, by definition of the
product probability measure $\mu$,

$\mu(C_{s})=\prod_{j=0}^{\ell-1}\,p_{s_{j}}.$

Hence for the survival probability $p_{n}$ we have

$p_{n}=\mu(S_{n})=\sum_{s\in\Sigma_{n+r}}\,\mu(C_{s})=\sum_{s\in\Sigma_{n+r}}\,\prod_{j=0}^{n+r-1}\,p_{s_{j}},$

which becomes

(A.3)
$p_{n}=\mu(S_{n})=\sum_{s\in\Sigma_{n+r}}\,\prod_{a\in\mathcal{A}}\,(p_{a})^{N_{s}(a)}$

if we use the counting function of Definition 2.1.

A classical method to study the exponential behaviour of a sequence is to use
its generating function. Let $P(z)$ be the generating function of
$\\{p_{n}\\}$, that is

$P(z):=\sum_{n=0}^{\infty}\,p_{n}\,z^{n},$

and $\rho$ be the radius of convergence of $P(z)$. Then
$\rho=e^{\gamma_{w}^{-}}\leq e^{\gamma_{w}^{+}}$, thus
$\gamma_{w}:=\gamma_{w}^{-}$ is given by the logarithm of the modulus of the
smallest pole of $P(z)$.

We now use (A.3) to find an explicit expression for the generating function
$P(z)$. For the sets $\Sigma_{\ell}$ defined in (A.1), let

(A.4)
$\alpha_{k_{1},\dots,k_{A},\ell}:=\\#\left\\{s\in\Sigma_{\ell}\,:\,N_{s}(a_{i})=k_{i}\,,\
i=1,\dots,A\right\\}.$

The power series

(A.5)
$\Sigma(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z):=\sum_{\ell=0}^{\infty}\,\Big{(}\sum_{k_{1}+\dots+k_{A}=\ell}\,\alpha_{k_{1},\dots,k_{A},\ell}\,(x_{a_{1}})^{k_{1}}\dots(x_{a_{A}})^{k_{A}}\Big{)}\,z^{\ell},$

where all $k_{i}$ are assumed to be non-negative integers, is called the
generating function of the sets $\Sigma_{\ell}$. We recall that

$\sum_{k_{1}+\dots+k_{A}=\ell}\,\alpha_{k_{1},\dots,k_{A},\ell}\,(x_{a_{1}})^{k_{1}}\dots(x_{a_{A}})^{k_{A}}=(x_{a_{1}}+x_{a_{2}}+\dots+x_{a_{A}})^{\ell}$

for all $\ell=0,\dots,r-1$.

Following [13, Proposition I.4], we prove the following result.

######  Lemma A.1.

Let $c_{w}=c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)$ be the weighted
autocorrelation polynomial of the word $w$ of length $r$. Then

$\displaystyle\Sigma(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)$
$\displaystyle=\frac{c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)}{\Big{(}\prod_{i=1}^{A}\,(x_{a_{i}})^{N_{w}(a_{i})}\Big{)}\,z^{r}+\Big{[}1-\Big{(}\sum_{i=1}^{A}\,x_{a_{i}}\Big{)}\,z\Big{]}\,c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)}\,.$

###### Proof.

For $\ell\geq r$, set

(A.6)
$W_{\ell}:=\left\\{s\in\mathcal{A}^{\ell}\,:\begin{array}[]{l}\text{$s_{\ell-r}\,s_{\ell-r+1}\dots
s_{\ell-1}=w$ and $s$ does not}\\\ \text{contain $w$ in other
positions}\end{array}\right\\}$

and denote by $W(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)$ be the generating
function of the sets $W_{\ell}$, defined as in (A.4)-(A.5) with $W_{\ell}$ in
lieu of $\Sigma_{\ell}$.

Let $s\in\Sigma:=\cup_{\ell\geq 0}\Sigma_{\ell}$. By appending a letter to
$s$, we obtain a non-empty word either in $\Sigma$ or in $W:=\cup_{\ell\geq
r}W_{\ell}$. Hence the corresponding generating functions satisfy the equation

(A.7) $\displaystyle
1+\Big{(}\sum_{i=1}^{A}\,x_{a_{i}}\Big{)}\,z\,\Sigma(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)$
$\displaystyle=\Sigma(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)+W(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z).$

Next, appending the word $w$ to a word $s\in\Sigma$, we obtain either a word
in $W$ or a word with two appearances of $w$ in the last $2r-1$ symbols. The
latter case occurs if one of the symbols $c_{1},\dots,c_{r-1}$ of the
autocorrelation vector of $w$ is equal to 1. If $c_{i}=1$ for some $i\geq 1$
then $(w_{i}\,w_{i+1}\dots w_{r-1})=(w_{0}\,w_{1}\dots w_{r-i-1})$, thus,
appending $w$ to a word in $\Sigma$ whose last symbols are $(w_{0}\,w_{1}\dots
w_{i-1})$, we get a word which can be written as a word in $W$ with
$(w_{r-i}\,w_{r-i+1}\dots w_{r-1})$ appended at the end. Therefore we obtain a
word with two appearances of $w$.

Hence we have the equation

(A.8)
$\displaystyle\Big{(}\prod_{i=1}^{A}\,(x_{a_{i}})^{N_{w}(a_{i})}\Big{)}\,z^{r}\,\Sigma(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)$
$\displaystyle=W(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z)\,c_{w}(x_{a_{1}},x_{a_{2}},\dots,x_{a_{A}},z).$

The result follows by solving (A.7) and (A.8). ∎

From (A.3) it follows that

$\displaystyle P(z)=$
$\displaystyle\sum_{n=0}^{\infty}\,\Big{(}\sum_{s\in\Sigma_{n+r}}\,\prod_{i=1}^{A}\,(p_{a_{i}})^{N_{s}(a_{i})}\Big{)}\,z^{n}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\,\Big{(}\sum_{k_{1}+\dots+k_{A}=n+r}\,\alpha_{k_{1},\dots,k_{A},n+r}\,(p_{a_{1}})^{k_{1}}\dots(p_{a_{A}})^{k_{A}}\Big{)}\,z^{n}$
$\displaystyle=$ $\displaystyle
z^{-r}\,\sum_{\ell=r}^{\infty}\,\Big{(}\sum_{k_{1}+\dots+k_{A}=\ell}\,\alpha_{k_{1},\dots,k_{A},\ell}\,(p_{a_{1}})^{k_{1}}\dots(p_{a_{A}})^{k_{A}}\Big{)}\,z^{\ell},$

hence finally

(A.9)
$P(z)=z^{-r}\,\Big{(}\Sigma(p_{a_{1}},p_{a_{2}},\dots,p_{a_{A}},z)-\sum_{\ell=0}^{r-1}\,z^{\ell}\Big{)}.$

Using Lemma A.1, it follows that $P(z)$ is a rational function, with smallest
positive pole given by the smallest positive zero of the denominator of
$\Sigma(p_{a_{1}},p_{a_{2}},\dots,p_{a_{A}},z)$. Hence the proof of
Proposition 2.4 is finished.

##  Appendix B Proof of Proposition 4.2

We argue as in Appendix A. Given a hole $w\in\mathcal{A}^{*}_{{}_{\Pi}}$ of
length $r$ we have by (A.1) and (A.2)

$p_{n}=m_{{}_{\Pi}}(S_{n})=m_{{}_{\Pi}}\Big{(}\left\\{\omega\in\mathcal{A}^{\mathbb{N}}_{{}_{\Pi}}\,:\,\omega^{n+r}\,\in\Sigma_{n+r}\right\\}\Big{)}$

for the survival probability. Since, for a given
$s=(s_{0}\,\dots\,s_{\ell-1})\in\\{a,b\\}^{\ell}$,

$m_{{}_{\Pi}}(C_{s})=p_{s_{0}}\,\prod_{j=0}^{\ell-2}\,\pi_{s_{j}\,s_{j+1}}$

where $p=(p_{a},p_{b})$ is the vector defined in Section 4, we find

$p_{n}=\sum_{s\in\Sigma_{n+r}}\,m_{{}_{\Pi}}(C_{s})=\sum_{s\in\Sigma_{n+r}}\,p_{s_{0}}\,\prod_{j=0}^{n+r-2}\,\pi_{s_{j}\,s_{j+1}}.$

Using the notation $\mathbf{k}=(k_{1},k_{2},k_{3},k_{4})$ and
$|\mathbf{k}|:=k_{1}+k_{2}+k_{3}+k_{4}$, we can then write

(B.1)
$p_{n}=\sum_{|\mathbf{k}|=n+r-1}\,\Big{(}\alpha^{a}_{\mathbf{k}}\,p_{a}\,\pi_{aa}^{k_{1}}\,\pi_{ab}^{k_{2}}\,\pi_{ba}^{k_{3}}\,\pi_{bb}^{k_{4}}+\alpha^{b}_{\mathbf{k}}\,p_{b}\,\pi_{aa}^{k_{1}}\,\pi_{ab}^{k_{2}}\,\pi_{ba}^{k_{3}}\,\pi_{bb}^{k_{4}}\Big{)}$

where $\alpha^{a}_{\mathbf{k}}$ and $\alpha^{b}_{\mathbf{k}}$ denote the
number of words $s\in\Sigma_{n+r}$ which begin with $a$ and $b$, respectively,
and for which $\mathbf{k}$ is the vector of the number of appearances of
$\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb}$, respectively, in the measure of the
cylinder $C_{s}$.

In order to obtain a connection with the survival probabilities as expressed
in (B.1), we need to write the generating function of the sets $\Sigma_{\ell}$
taking into account the number of transitions from a letter to another, and
the first letter of a word. We write

(B.2) $\displaystyle\Sigma(x_{a},x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$
$\displaystyle:=1+\Sigma^{a}(x_{a},y_{aa},y_{ab},y_{ba},y_{bb},z)+\Sigma^{b}(x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$

where

$\displaystyle\Sigma^{a}(x_{a},x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$
$\displaystyle:=\sum_{\ell=1}^{\infty}\,\Big{[}\sum_{|\mathbf{k}|=\ell-1}\,\Big{(}\alpha^{a,a}_{\mathbf{k}}\,x_{a}\,y_{aa}^{k_{1}}\,y_{ab}^{k_{2}}\,y_{ba}^{k_{3}}\,y_{bb}^{k_{4}}+\alpha^{b,a}_{\mathbf{k}}\,x_{b}\,y_{aa}^{k_{1}}\,y_{ab}^{k_{2}}\,y_{ba}^{k_{3}}\,y_{bb}^{k_{4}}\Big{)}\Big{]}\,z^{\ell}$

is the generating function of words of length at least 2 and with last letter
equal to $a$. Here $\alpha^{a,a}_{\mathbf{k}}$ and $\alpha^{b,a}_{\mathbf{k}}$
denote the number of words of length $|\mathbf{k}|+1$ not containing $w$ as a
pattern, which begin with $a$ and $b$, respectively, which end with $a$, and
for which $\mathbf{k}$ is the vector of the number of appearances of the
patterns $aa,ab,ba,bb$.

A similar formulation holds for
$\Sigma^{b}(x_{a},x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$, the generating
function of words of length at least 2 and with last letter equal to $b$. With
the above notations we have

$\alpha^{a,a}_{\mathbf{k}}+\alpha^{a,b}_{\mathbf{k}}=\alpha^{a}_{\mathbf{k}}\,,\qquad\alpha^{b,a}_{\mathbf{k}}+\alpha^{b,b}_{\mathbf{k}}=\alpha^{b}_{\mathbf{k}}.$

The analog of (A.9) then follows for the generating function of $\\{p_{n}\\}$

(B.3) $P(z)=\sum_{n\geq
0}\,p_{n}\,z^{n}=z^{-r}\,\Big{(}\Sigma(p_{a},p_{b},\pi_{aa},\pi_{ab},\pi_{ba},\pi_{bb},z)-q(z)\Big{)}$

where $q(z)$ is a polynomial of degree $r-1$ in $z$. As in Appendix A, the
proof of Proposition 4.2 ends by showing that
$\Sigma(x_{a},x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$ is a rational function and
finding its denominator.

We repeat the proof of Lemma A.1 to prove

######  Lemma B.1.

Let $c_{w,M}(y_{aa},y_{ab},y_{ba},y_{bb},z)$ be the Markovian weighted
autocorrelation polynomial of a word $w$ of length $r$. Then the generating
function (B.2) is a rational function with denominator given by

$\displaystyle y_{w_{0}w_{1}}\dots
y_{w_{r-2}w_{r-1}}\,z^{r}\,(y_{w_{r-1}w_{0}}-\chi\,z\,\delta_{w_{0},w_{r-1}})$
$\displaystyle+\Big{(}1-(y_{aa}+y_{bb})\,z+\chi\,z^{2}\Big{)}\,c_{w,M}(y_{aa},y_{ab},y_{ba},y_{bb},z),$

where $\chi:=y_{aa}y_{bb}-y_{ab}y_{ba}$.

###### Proof.

For $\ell\geq r$, let $W_{\ell}$ as in (A.6), and $W:=\cup_{\ell\geq
r}W_{\ell}$. Also we use the notation
$W(x_{a},x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$ for the generating function of
the sets $W_{\ell}$.

Let $s\in\Sigma=\cup_{\ell\geq 0}\,\Sigma_{\ell}$. By appending a letter to
$s$, we obtain a non-empty word in $\Sigma$ or in $W$, but now we need to
distinguish between the cases where we append the letter $a$ or $b$. We find
the following equations for the generating functions defined in (B.2) (we drop
the dependence on most of the variables for reasons of readability). If we
append the letter $a$, we might find a word in $W$ only if $w_{r-1}=a$, and we
do not find it ending with $b$, hence

(B.4)
$x_{a}\,z+\Sigma^{a}(z)\,y_{aa}\,z+\Sigma^{b}(z)\,y_{ba}\,z=\Sigma^{a}(z)+W(z)\,\delta_{a,w_{r-1}}.$

Analogously,

(B.5)
$x_{b}\,z+\Sigma^{a}(z)\,y_{ab}\,z+\Sigma^{b}(z)\,y_{bb}\,z=\Sigma^{b}(z)+W(z)\,\delta_{b,w_{r-1}}.$

Next, appending the word $w$ to a word $s\in\Sigma$, we obtain either a word
in $W$ or a word with two appearances of $w$ in the last $2r-1$ symbols, and
again this is regulated by the Markovian weighted autocorrelation polynomial
of $w$. We find the equation

(B.6) $\displaystyle x_{w_{0}}\,y_{w_{0}w_{1}}\dots
y_{w_{r-2}w_{r-1}}+\Big{(}\Sigma^{a}(z)\,z^{r}\,y_{aw_{0}}+\Sigma^{b}(z)\,z^{r}\,y_{bw_{0}}\Big{)}\,y_{w_{0}w_{1}}\dots
y_{w_{r-2}w_{r-1}}$ $\displaystyle=W(z)\,c_{w,M}(z).$

Solving the system given by (B.4),(B.5),(B.6) for $\Sigma^{a}$, $\Sigma^{b}$
and $W$ in the four possible cases for $w_{0}$ and $w_{r-1}$, we find that the
solution of the systems is such that
$\Sigma(x_{a},x_{b},y_{aa},y_{ab},y_{ba},y_{bb},z)$ is a rational function
with denominator given by

$\displaystyle y_{w_{0}w_{1}}\dots
y_{w_{r-2}w_{r-1}}\,z^{r}\,\Big{(}y_{w_{r-1}w_{0}}-(y_{aa}y_{bb}-y_{ab}y_{ba})\,z\,\delta_{w_{0},w_{r-1}}\Big{)}$
$\displaystyle+\Big{(}1-(y_{aa}+y_{bb})\,z+(y_{aa}y_{bb}-y_{ab}y_{ba})\,z^{2}\Big{)}\,c_{w,M}(z).$

The proposition is proved. ∎

Using now (B.3), with the relations $\pi_{aa}+\pi_{ab}=\pi_{ba}+\pi_{bb}=1$,
we find that the denominator of $P(z)$ is given by the polynomial
$\tau_{w,\Pi}$ in (4.2).

## References

  * [1] E.G. Altmann, J.S.E. Portela, T. Tél, _Leaking chaotic systems_ , Rev. Modern Phys. 85 (2013), 869–918.
  * [2] C. Bonanno, I. Chouari, _Escape rates for the Farey map with approximated holes_ , Internat. J. Bifur. Chaos Appl. Sci. Engrg. 26 (2016), no. 10, 1650169.
  * [3] H. Bruin, M.F. Demers, M. Todd, _Hitting and escaping statistics: mixing, targets and holes_ , Adv. Math. 328 (2018), 1263–1298.
  * [4] L. Bunimovich, A. Yurchenko, _Where to place a hole to achieve a maximal escape rate_ , Israel J. Math. 182 (2011), 229–252.
  * [5] N. Chernov, R. Markarian, S. Troubetzkoy, _Conditionally invariant measures for Anosov maps with small holes_ , Ergodic Theory Dynam. Systems 18 (1998), no. 5, 1049–1073.
  * [6] G. Cristadoro, G. Knight, M. Degli Esposti, _Follow the fugitive: an application of the method of images to open systems_ , J. Phys. A 46 (2013), no. 27, 272001.
  * [7] M.F. Demers, M. Todd, _Equilibrium states, pressure and escape for multimodal maps with holes_ , Israel J. Math. 221 (2017), no. 1, 367–424.
  * [8] M.F. Demers, M. Todd, _Slow and fast escape for open intermittent maps_ , Comm. Math. Phys. 351 (2017), no. 2, 775–835.
  * [9] M.F. Demers, P. Wright, L.-S. Young, _Escape rates and physically relevant measures for billiards with small holes_ , Comm. Math. Phys. 294 (2010), no. 2, 353–388.
  * [10] M.F. Demers, P. Wright, L.-S. Young, _Entropy, Lyapunov exponents and escape rates in open systems_ , Ergodic Theory Dynam. Systems 32 (2012), no. 4, 1270–1301.
  * [11] M.F. Demers, L.-S. Young, _Escape rates and conditionally invariant measures_ , Nonlinearity 19 (2006), no. 2, 377–397.
  * [12] P.A. Ferrari, H. Kesten, S. Martinez, P. Picco, _Existence of quasi-stationary distributions. A renewal dynamical approach_ , Ann. Probab. 23 (1995), no. 2, 501–521.
  * [13] P. Flajolet, R. Sedgewick, “Analytic Combinatorics”, Cambridge University Press, Cambridge, 2009.
  * [14] G. Froyland, R. Murray, O. Stancevic, _Spectral degeneracy and escape dynamics for intermittent maps with a hole_ , Nonlinearity 24 (2011), no. 9, 2435–2463.
  * [15] C. Haritha, N. Agarwal, _Product of expansive Markov maps with hole_ , Discrete Contin. Dyn. Syst. 39 (2019), no. 10, 5743–5774.
  * [16] C. Haritha, N. Agarwal, _Subshifts of finite type with a hole_ , _J. Aust. Math. Soc._ , to appear. Available from: https://doi.org/10.1017/S1446788722000052.
  * [17] G. Keller, C. Liverani, _Rare events, escape rates and quasistationarity: some exact formulae_ , J. Stat. Phys. 135 (2009), no. 3, 519–534.
  * [18] C. Liverani, V. Maume-Deschamps, _Lasota-Yorke maps with holes: conditionally invariant probability measures and invariant probability measures on the survivor set_ , Ann. Inst. H. Poincaré Probab. Statist. 39 (2003), no. 3, 385–412.
  * [19] S. Munday, G. Knight, _Escape rate scaling in infinite measure preserving systems_ , J. Phys. A 49 (2016), no. 8, 085101.
  * [20] G. Pianigiani, J.A. Yorke, _Expanding maps on sets which are almost invariant. Decay and chaos_ , Trans. Amer. Math. Soc. 252 (1979), 351–366.
  * [21] H. van den Bedem, N. Chernov, _Expanding maps of an interval with holes_ , Ergodic Theory Dynam. Systems 22 (2002), no. 3, 637–654.