11institutetext: TU Delft
11email<EMAIL_ADDRESS>
# Do the Findings of Document and Passage Retrieval Generalize to the
Retrieval of Responses for Dialogues?

Gustavo Penha  Claudia Hauff

###### Abstract

A number of learned sparse and dense retrieval approaches have recently been
proposed and proven effective in tasks such as passage retrieval and document
retrieval. In this paper we analyze with a replicability study if the lessons
learned generalize to the retrieval of responses for dialogues, an important
task for the increasingly popular field of conversational search. Unlike
passage and document retrieval where documents are usually longer than
queries, in response ranking for dialogues the queries (dialogue contexts) are
often longer than the documents (responses). Additionally, dialogues have a
particular structure, i.e. multiple utterances by different users. With these
differences in mind, we here evaluate how generalizable the following major
findings from previous works are: (F1) query expansion outperforms a no-
expansion baseline; (F2) document expansion outperforms a no-expansion
baseline; (F3) zero-shot dense retrieval underperforms sparse baselines; (F4)
dense retrieval outperforms sparse baselines; (F5) hard negative sampling is
better than random sampling for training dense models. Our
experiments111https://github.com/Guzpenha/transformer_rankers/tree/full_rank_retrieval_dialogues.—based
on three different information-seeking dialogue datasets—reveal that four out
of five findings (F2–F5) generalize to our domain.

##  1 Introduction

_Conversational search_ is concerned with creating agents that satisfy an
information need by means of a _mixed-initiative_ conversation through natural
language interaction, rather than through the traditional search engine
results page. A popular approach to conversational search is retrieval-based
[3]: given an ongoing conversation and a large corpus of historic
conversations, retrieve the response that is best suited from the corpus [45,
48, 28, 47, 11]. Due to the effectiveness of heavily pre-trained transformer-
based language models such as BERT [4], they have become the predominant
approach for conversation response re-ranking [28, 43, 53, 8, 42].

The most common evaluation procedure for conversation response re-ranking
consists of re-ranking a limited set of $n$ candidate responses (including the
ground-truth response(s)), followed by measuring the number of relevant
responses found in the first $K$ positions—$Recall_{n}@K$ [52]. Since the
entire collection of available responses is typically way bigger222While for
most benchmarks [52] we have only 10–100 candidates, a working system with the
Reddit data from PolyAI https://github.com/PolyAI-LDN/conversational-datasets
would need to retrieve from 3.7 billion responses. than such a set of
candidates, this setup is in fact a selection problem, where we have to choose
the correct response out of a few options. This evaluation overlooks the
first-stage retrieval step, which retrieves a set of $n$ responses to be re-
ranked. If the first-stage model, e.g. BM25, fails to retrieve relevant
responses, the entire pipeline fails.

Motivated by a lack of research on the first-stage retrieval step, we are
interested in answering in our replicability study whether the considerable
knowledge obtained on document and passage retrieval tasks generalizes to the
dialogue domain. Unlike document and passage retrieval where the documents are
generally longer than the queries, in response retrieval for dialogues the
queries (dialogue contexts) tend to be longer than the documents (responses).
A second important difference is the structure induced by the dialogue as seen
in Table 1.

Table 1: Comparison between passage retrieval and response retrieval for dialogues. In §3 we define the task of _First-stage Retrieval for Dialogues_. Colors symbolize the information-seeker and information-provider. $p^{+}/r^{+}$ are the relevant passage/response. |  Passage Retrieval |  |  First-stage Retrieval for Dialogues
---|---|---|---
Input |  Query $q$ |  |  Dialogue context $\mathcal{U}=\\{u^{1},u^{2},...,u^{\tau}\\}$
Example |  $q$: what is theraderm used for |  |  $u^{1}$: I want a firewall that will protect me but more of that to monitor any connection in or out of my mac […] $u^{2}$:  {url} allows you to map joypad buttons to keyboard keys and […] $u^{3}$:  Do the diagonals for the analog stick work correctly for you? […]
Output |  Ranked list of passages |  |  Ranked list of responses
Example |  $p^{+}$: Thera-Derm Lotion is used as a moisturizer to treat or prevent dry, rough, scaly, […] |  |  $r^{+}$:  In the ”Others” tab, try […]

Given the differences between the domains, we verify empirically across three
information-seeking datasets and 1.7M queries, the generalizability of five
findings (F1 to F5) from the passage and document retrieval literature related
to state-of-the-art sparse and dense retrieval models. We are motivated in our
selection of these five findings by their impact in prior works (cf. §2). Our
results show that four out of five previous findings do indeed generalize to
our domain:

  * F1

✗333✗ indicates that the finding does not hold in our domain whereas ✓
indicates that it holds in our domain followed by the necessary condition or
exception. Dialogue context (i.e. query) expansion outperforms a no-expansion
baseline [1, 18, 49, 21].

  * F2

✓ Response (i.e. document) expansion outperforms a no-expansion baseline [25,
21, 19] if the expansion model is trained to generate the most recent context
(last utterance444For example in Table 1 the last utterance is $u^{3}$. of the
dialogue) instead of older context (all utterances).

  * F3

✓ Dense retrieval in the zero-shot555A zero-shot is a model that does not have
access to target data, cf. Table 2. setting underperforms sparse baselines
[34, 41] except when it goes through intermediate training on large amounts of
out-of-domain data.

  * F4

✓ Dense retrieval with access to target data666Target data is data from the
same distribution, i.e. dataset, of the evaluation dataset. outperforms sparse
baselines [7, 15, 34] if an intermediate training step on out-of-domain data
is performed before the fine-tuning on target data.

  * F5

✓ Harder negative sampling techniques lead to effectiveness gains [46, 51] if
a denoising technique is used to reduce the number of false negative samples.

Our results indicate that most findings translate to the domain of retrieval
of responses for dialogues. A promising future direction is thus to start with
successful models from other domains—for which there are more datasets and
previous research—and study how to adapt and improve them for retrieval-based
conversational search.

##  2 Related Work

In this section we first discuss current research in retrieval-based systems
for conversational search, followed by reviewing the major findings of
(un)supervised sparse and dense retrieval in the domains of passage and
document retrieval.

###  2.1 Ranking and Retrieval of Responses for Dialogues

Early neural models for response re-ranking were based on matching the
representations of the concatenated dialogue context and the representation of
a response in a single-turn manner with architectures such as CNN and LSTM
[23, 14]. More complex neural architectures matching each utterance with the
response were also explored [54, 9, 22]. Heavily pre-trained language models
such as BERT were first shown to be effective by Nogueira and Cho [24] for re-
ranking. Such models quickly became a predominant approach for re-ranking in
IR [21] and were later shown to be effective for re-ranking responses in
conversations [42, 28].

In contrast, the first-stage retrieval of responses for a dialogue received
relatively little attention [29]. Lan et al. [17] and Tao et al. [38] showed
that BERT-based dense retrieval models outperform BM25 for first-stage
retrieval of responses for dialogues. A limitation of their work is that
strong sparse retrieval baselines that have shown to be effective in other
retrieval tasks, e.g. BM25 with dialogue context expansion [25] or BM25 with
response expansion [49], were not employed for dense retrieval. We do such
comparisons here and test a total of five major findings that have been not
been evaluated before by previous literature on the first-stage retrieval of
responses for dialogues.

###  2.2 Dense and Sparse Models for Passage and Document Retrieval

####  2.2.1 Context for F1

Retrieval models can be categorized into two dimensions: supervised vs.
unsupervised and dense vs. sparse representations [19]. An _unsupervised_
sparse representation model such as BM25 [35] represents each document and
query with a sparse vector with the dimension of the collection’s vocabulary,
having many zero weights due to non-occurring terms. Since the weights of each
term are entirely based on term statistics they are considered unsupervised
methods. Such approaches are prone to the vocabulary mismatch problem [6], as
semantic matches are not considered. A way to address such a problem is by
using query expansion methods. RM3 [1] is a competitive [49] query expansion
technique that uses pseudo-relevance feedback to add new terms to the queries
followed by another final retrieval step using the modified query.

####  2.2.2 Context for F2

A _supervised_ sparse retrieval model can take advantage of the effectiveness
of transformer-based language models by changing the terms’ weights from
collection statistics to something that is learned. Document expansion with a
learned model can be considered a learned sparse retrieval approach [19]. The
core idea is to create pseudo documents that have expanded terms and use them
instead when doing retrieval. Doc2query [25] is a strong supervised sparse
retrieval baseline that uses a language model to predict queries that might be
issued to find a document. The predictions of this model are used to create
the augmented pseudo documents.

####  2.2.3 Context for F3 and F4

Supervised dense retrieval models777A distinction can also be made of cross-
encoders and bi-encoders, where the first encode the query and document
jointly as opposed to separately [40]. Cross-encoders are applied in a re-
ranking step due to their inefficiency and thus are not our focus., such as
ANCE [46] and coCodenser [7], represent query and documents in a small fixed-
length space, for example of 768 dimensions. Dense retrieval models without
access to target data for training—known as the _zero-shot scenario_ —have
underperformed sparse methods (F3). For example, the BEIR benchmark [41]
showed that BM25 was superior to dense retrieval from 9–18 (depending on the
model) out of the 18 datasets in the zero-shot scenario. In contrast, when
having access to enough supervision from target data, dense retrieval models
have shown to consistently outperform strong sparse baselines [7, 15, 34]
(F4).

####  2.2.4 Context for F5

In order to train neural ranking models, a small set of negative (i.e. non-
relevant) candidates are necessary as it is prohibitively expensive to use
every other document in the collection as negative sample for a query. A
limitation of randomly selecting negative samples is that they might be too
easy for the ranking model to discriminate from relevant ones, while for
negative documents that are harder the model might still struggle. For this
reason hard negative sampling has been shown to perform better than random
sampling for passage and document retrieval [46, 36, 51].

##  3 First-stage Retrieval for Dialogues

In this section we first describe the problem of first-stage retrieval of
responses, followed by the findings we want to replicate from sparse and dense
approaches.

####  3.0.1 Problem Definition

The task of first-stage retrieval of responses for dialogues, concerns
retrieving the best response out of the entire collection given the dialogue
context. Formally, let
$\mathcal{D}=\\{(\mathcal{U}_{i},\mathcal{R}_{i},\mathcal{Y}_{i})\\}_{i=1}^{M}$
be a data set consisting of $M$ triplets: dialogue context, response
candidates and response relevance labels. The dialogue context
$\mathcal{U}_{i}$ is composed of the previous utterances
$\\{u^{1},u^{2},...,u^{\tau}\\}$ at the turn $\tau$ of the dialogue. The
candidate responses $\mathcal{R}_{i}=\\{r^{1},r^{2},...,r^{n}\\}$ are either
ground-truth responses $r^{+}$ or negative sampled candidates $r^{-}$,
indicated by the relevance labels
$\mathcal{Y}_{i}=\\{y^{1},y^{2},...,y^{n}\\}$. In previous work, the number of
candidates is limited, typically $n=10$ [29]. The findings we replicate here
come from passage and document retrieval tasks where there is no limit to the
number of documents or passages that have to be retrieved. Thus, in all of our
first-stage retrieval task experiments $n$ is set to the size of the entire
collection of responses in the corpus. The number of ground-truth responses is
one, the observed response in the conversational data. The task is then to
learn a ranking function $f(.)$ that is able to generate a ranked list from
the entire corpus of responses $\mathcal{R}_{i}$ based on their predicted
relevance scores $f(\mathcal{U},r)$.

####  3.0.2 F1: Unsupervised Sparse Retrieval

We rely on classic retrieval methods, for which the most commonly used
baseline is BM25. One of the limitations of sparse retrieval is the vocabulary
mismatch problem. Expansion techniques are able to overcome this problem by
appending new words to the dialogue contexts and responses. For this reason,
we here translate a query expansion technique to the dialogue domain and
perform _dialogue context expansion_ with RM3 [1], a competitive unsupervised
method that assumes that the top-ranked responses by the sparse retrieval
model are relevant. From these pseudo-relevant responses, words are selected
and an expanded dialogue context is created and subsequently employed by the
sparse retrieval method to rank the final list of responses. The effectiveness
of RM3 in the domain of dialogues is the first finding that we validate.

####  3.0.3 F2: Learned Sparse Retrieval

Alternatively, we can expand the responses in the collection with a learned
method. To do so we “translate” doc2query [25] into our domain, yielding
resp2ctxt. Formally, we fine-tune a generative transformer model $G$ for the
task of generating the dialogue context $\mathcal{U}_{i}$ from the ground-
truth response $r^{+}_{i}$. This model is then used to generate expansions for
all responses in the collection, $r^{i}=concat(r^{i},G(r^{i}))$. These
expansions are appended to the responses and the collection is indexed
again—the sparse retrieval method itself is not modified, i.e. we continue
using BM25. This approach (which we coin resp2ctxt) leads to two improvements:
term re-weighting (adding terms that already exist in the document) and
dealing with the vocabulary mismatch problem (adding new terms). The
effectiveness of doc2query in the domain of dialogues is the second finding
that we validate.

Unlike passage and document retrieval where the queries are smaller than the
documents, for the retrieval of responses for dialogues the queries are longer
than the documents888For example, while the TREC-DL-2020 passage and document
retrieval tasks the queries have between 5–6 terms on average and the passages
and documents have over 50 and 1000 terms respectively, for the information-
seeking dialogue datasets used here the dialogue contexts (queries) have
between 70 and 474 terms on average depending on the dataset while the
responses (documents) have between 11 and 71.. This is a challenge for the
generative model, since generating larger pieces of text is a more difficult
problem than smaller ones as there is more room for errors. Motivated by this,
we also explored a modified version of resp2ctxt that aims to generate only
the last utterance of the dialogue context: resp2ctxtlu. This model is trained
to generate $u^{\tau}$ from $r^{+}_{i}$, instead of trying to generate the
whole utterance $\mathcal{U}_{i}=\\{u^{1},u^{2},...,u^{\tau}\\}$. The
underlying premise is that the most important utterance from the dialogue is
the last one, and if it is correctly generated by resp2ctxtlu, the sparse
retrieval method will be able to find the correct response from the
collection.

####  3.0.4 F3: Zero-shot Dense Retrieval

We rely on methods that learn to represent the dialogue context and the
responses separately in a dense embedding space. Responses are then ranked by
their similarity to the dialogue context. We rely here on pre-trained language
transformer models, such as BERT [4] and MPNet [37], to obtain such
representations of the dialogue context and response. This approach is
generally referred to as a _bi-encoder_ model [21] and is an effective family
of models999See for example the top models in terms of effectiveness from the
MSMarco benchmark leaderboards https://microsoft.github.io/msmarco/.. A zero-
shot model is one that is not trained on the target data. Target data is data
from the same distribution, i.e. dataset, of the evaluation dataset.

One way of improving the representations of a heavily pre-trained language
model for the zero-shot setting is to fine-tune it with intermediate data
[33]. Such intermediate data contains triplets of query, relevant document,
and negative document and can include multiple datasets. The advantage of
adding this step before employing the representations of the language model is
to reduce the gap between the pre-training and the downstream task at hand
[31, 26, 30]. In Table 2 we clarify the relationship between pre-training,
intermediate training and fine-tuning.

Table 2: The different training stages and data, their purposes, examples of datasets, and the type of dense model obtained after each stage. |  Pre-training data |  Intermediate data |  Target data
---|---|---|---
Purpose |  Learn general representations |  Learn sentence representations for ranking |  Learn representations for target distribution
Model is |  Zero-shot |  Zero-shot |  Fine-tuned
Example |  Wikipedia |  MSMarco |  MANtIS

The intermediate training step learns to represent pieces of text (query and
documents) by applying a mean pooling function over the transformer’s final
layer, which is then used to calculate the dot-product similarity. The loss
function employs multiple negative texts from the same batch to learn the
representations in a constrastive manner, also known as in-batch negative
sampling. Such a procedure learns better text representations than a naive
approach that uses the $[CLS]$ token representation of BERT [33, 2].

The function $f(\mathcal{U},r)$ is then
$dot(\eta(concat(\mathcal{U})),\eta(r))$, where $\eta$ is the representation
obtained by applying the mean pooling function over the last layer of the
transformer model, and
$concat(\mathcal{U})=u^{1}\;|\;[U]\;|\;u^{2}\;|\;[T]\;|\;...\;|\;u^{\tau}\;$,
where $|$ indicates the concatenation operation. The utterances from the
context $\mathcal{U}$ are concatenated with special separator tokens $[U]$ and
$[T]$ indicating end of utterances and turns101010The special tokens $[U]$ and
$[T]$ will not have any meaningful representation in the zero-shot setting,
but they can be learned on the fine-tuning step.. The effectiveness of a zero-
shot bi-encoder model in the domain of dialogues is the third finding we
validate.

####  3.0.5 F4: Fine-tuned Dense Retrieval

The standard procedure is to fine-tune dense models with target data that
comes from the same dataset that the model will be evaluated. Since we do not
have labeled negative responses, all the remaining responses in the dataset
can be thought of as non-relevant to the dialogue context. Computing the
probability of the correct response over all other responses in the dataset
would give us
$P(r\mid\mathcal{U})=\frac{P(\mathcal{U},r)}{\sum_{k}P\left(\mathcal{U},r_{k}\right)}$.
This computation is prohibitively expensive, and the standard procedure is to
approximate it using a few negative samples. The _negative sampling_ task is
then as follows: given the dialogue context $\mathcal{U}$ find challenging
responses $r^{-}$ that are non-relevant for $\mathcal{U}$. Negative sampling
can be seen as a retrieval task, where one can use a model to retrieve
negatives by applying a retrieval function to the collection of responses
using $\mathcal{U}$ as the query.

With such a dataset at hand, we continue the training—after the intermediate
step—in the same manner as done by the intermediate training step, with the
following cross-entropy loss function111111We refer to this loss as
MultipleNegativesRankingLoss. for a batch with size $B$:

$\mathcal{J}(\mathbf{\mathcal{U}},\mathbf{r},\theta)=-\frac{1}{B}\sum_{i=1}^{B}\left[f\left(\mathcal{U}_{i},r_{i}\right)-\log\sum_{j=1,j!=i}^{B}e^{f\left(\mathcal{U}_{i},r_{j}\right)}\right],$

where $f(\mathcal{U},r)$ is the dot-product of the mean pooling of the last
layer of the transformer model. The effectiveness of a fine-tuned bi-encoder
model in the domain of dialogues is the fourth finding we validate here.

####  3.0.6 F5: Hard Negative Sampling

A limitation of random samples is that they might be too easy for the ranking
model to discriminate from relevant ones, while for negative documents that
are hard the model might still struggle. For this reason, another popular
approach is to use a ranking model to retrieve negative documents using the
given query with a classic retrieval technique such as BM25. This leads to
finding negative documents that are closer to the query in the sparse
representation space, and thus they are _harder negatives_. Since dense
retrieval models have been outperforming sparse retrieval in a number of cases
with available training data, more complex negative sampling techniques making
use of dense retrieval have also been proposed [46, 12]. The effectiveness of
hard negative sampling for a bi-encoder model in the domain of dialogues is
the fifth finding we validate here.

##  4 Experimental Setup

In order to compare the different sparse and dense approaches we consider
three large-scale information-seeking conversation datasets121212MSDialog is
available at https://ciir.cs.umass.edu/downloads/msdialog/; MANtIS is
available at https://guzpenha.github.io/MANtIS/; UDCDSTC8 is available at
https://github.com/dstc8-track2/NOESIS-II.: MSDialog [32] contains 246K
context-response pairs, built from 35.5K information seeking conversations
from the Microsoft Answer community, a QA forum for several Microsoft
products; MANtIS [27] contains 1.3 million context-response pairs built from
conversations of 14 Stack Exchange sites, such as askubuntu and travel;
UDCDSTC8 [16] contains 184k context-response pairs of disentangled Ubuntu IRC
dialogues.

####  4.0.1 Implementation Details

For BM25 and BM25+RM3131313We perform hyperparameter tuning using grid search
on the number of expansion terms, number of expansion documents, and weight.
we rely on the pyserini implementations [20]. In order to train resp2ctxt
expansion methods we rely on the Huggingface transformers library [44], using
the t5-base model. We fine-tune the T5 model for 2 epochs, with a learning
rate of 2e-5, weight decay of 0.01, and batch size of 5. When augmenting the
responses with resp2ctxt we follow docT5query [25] and append three different
context predictions, using sampling and keeping the top-10 highest probability
vocabulary tokens.

For the zero-shot dense models, we rely on the SentenceTransformers [33] model
releases. The library uses Hugginface’s transformers for the pre-trained
models such as BERT [4] and MPNet [37]. For the bi-encoder models, we use the
pre-trained all-mpnet-base-v2 weights which were the most effective in our
initial experiments, compared with other pre-trained models141414The
alternative models we considered are those listed in the model overview
section at https://www.sbert.net/docs/pretrained_models.html.. When fine-
tuning the dense retrieval models, we rely on the
MultipleNegativesRankingLoss, which accepts a number of hard negatives, and
also uses the remaining in-batch random negatives to train the model. We use a
total of 10 negative samples for dialogue context. We fine-tune the dense
models for a total of 10k steps, and every 100 steps we evaluate the models on
a re-ranking task that selects the relevant response out of 10 responses. We
use the re-ranking validation MAP to select the best model from the whole
training to use in evaluation. We use a batch size of 5, with 10% of the
training steps as warmup steps. The learning rate is 2e-5 and the weight decay
is 0.01. We use FAISS [13] to perform the similarity search.

####  4.0.2 Evaluation

To evaluate the effectiveness of the retrieval systems we use $R@K$. We thus
evaluate the models’ capacity of finding the correct response out of the whole
possible set of responses151515The standard evaluation metric in conversation
response ranking [50, 8, 39] is recall at position $K$ with $n$ candidates
$R_{n}@K$. Since we are focused on the first-stage retrieval we set $n$ to be
the entire collection of answers. We perform Students t-tests at the 0.95
confidence level with Bonferroni correction to compare statistical
significance of methods. Comparisons are performed across the results for each
dialogue context.

##  5 Results

In this section, we discuss our empirical results along with the five major
findings from previous work (Section 1) in turn. Table 3 contains the main
results regarding F1 to F4. Table 5 contains the results for F5.

Table 3: Results for the generalizability of F1–F4. Bold values indicate the highest recall for each type of approach. Superscripts indicate statistically significant improvements using Students t-test with Bonferroni correction. $\dagger$=other methods from the same group$1$=best from unsupervised sparse retrieval ; $2$=best from supervised sparse retrieval; $3$=best from zero-shot dense retrieval. For example, in F3 † indicates that row (3d) improves over rows (3a–c), 1 indicates that it improves over row (1a) and 2 indicates it improves over row (2b). |  | MANtIS | MSDialog | UDCDSTC8
---|---|---|---|---
|  | R@1 | R@10 | R@1 | R@10 | R@1 | R@10
(0) | Random | 0.000 | 0.000 | 0.000 | 0.001 | 0.000 | 0.001
Unsupervised sparse | F1
(1a) | BM25 | 0.133† | 0.299† | 0.064† | 0.177† | 0.027† | 0.070†
(1b) | BM25 + RM3 | 0.073 | 0.206 | 0.035 | 0.127 | 0.011 | 0.049
Supervised sparse | F2
(2a) | BM25 + resp2ctxt | 0.135 | 0.309 | 0.074 | 0.208 | 0.028 | 0.067
(2b) | BM25 + resp2ctxtlu | 0.147†1 | 0.325†1 | 0.0751 | 0.2021 | 0.029 | 0.076
Zero-shot dense (ModelIntermediateData) | F3
(3a) | ANCE600K-MSMarco | 0.048 | 0.111 | 0.050 | 0.124 | 0.010 | 0.028
(3b) | TAS-B400K-MSMarco | 0.062 | 0.143 | 0.060 | 0.157 | 0.019 | 0.050
(3c) | Bi-encoder215M-mul | 0.138 | 0.297 | 0.108 | 0.277 | 0.023 | 0.076
(3d) | Bi-encoder1.17B-mul | 0.155†1 | 0.341†12 | 0.147†12 | 0.339†12 | 0.041† | 0.097†12
Fine-tuned dense (ModelNegativeSampler) | F4
(4a) | Bi-encoderRandom(0) | 0.130 | 0.307 | 0.168123 | 0.387123 | 0.05012 | 0.128123

####  F1 ✗ Query expansion via RM3 leads to improvements over not using query
expansion [1, 18, 49, 21].

BM25+RM3 (row 1b) does not improve over BM25 (1a) on any of the three
conversational datasets analyzed. We performed thorough hyperparameter fine-
tuning and no combination of the RM3 hyperparameters outperformed BM25. This
indicates that F1 does not hold for the task of response retrieval for
dialogues.

A manual analysis of the new terms appended to a sample of 60 dialogue
contexts by one of the paper’s authors revealed that only 18% of them have at
least one relevant term added based on our best judgment. Unlike web search
where the query is often incomplete, under-specified, and ambiguous, in the
information-seeking datasets employed here the dialogue context (query) is
quite detailed and has more terms than the responses (documents). We
hypothesize that because the dialogue contexts are already quite descriptive,
the task of expansion is trickier in this domain and thus we observe many
dialogues for which the added terms are noisy.

####  F2 ✓ Document expansion via resp2ctxt leads to improvements over no
expansion [25, 21, 19].

We find that a naive approach to response expansion improves marginally in two
of the three datasets with BM25+resp2ctxt (2a) outperforming BM25 (1a).
However, the proposed modification of predicting only the last utterance of
the dialogue (resp2ctxtlu) performs better than predicting the whole
utterance, as shown by BM25+resp2ctxtlu’s (2b) higher recall values. In the
MANtIS dataset the R@10 goes from 0.309 when using the model trained to
predict the dialogue context to 0.325 when using the one trained to predict
only the last utterance of the dialogue context. We thus find that F2
generalizes to response retrieval for dialogues, especially when predicting
only the last utterance of the context161616As future work, more sophisticated
techniques can be used to determine which parts of the dialogue context should
be predicted..

Table 4: Statistics of the augmentations for resp2ctxt and resp2ctxtlu. New words are the ones that did not exist in the document before. | MANtIS | MSDialog | UDCDSTC8
---|---|---|---
Context avg length | 474.12 | 426.08 | 76.95
Response avg length | 42.58 | 71.38 | 11.06
Aug. avg length - resp2ctxt | 494.23 | 596.99 | 202.3
Aug. avg length - resp2ctxtlu | 138.5 | 135.29 | 72.57
% new words - resp2ctxt | 71% | 69% | 71%
% new words - resp2ctxtlu | 59% | 37% | 63%

In order to understand what the response expansion methods are doing most—term
re-weighting or adding novel terms—we present the percentage of novel terms
added by both methods in Table 4. The table shows that resp2ctxtlu does more
term re-weighting than adding new words when compared to resp2ctxt (53% and
70% on average are new words respectively and thus 47% vs 30% are changing the
weights by adding existing words), generating overall smaller augmentations
(115.45 vs 431.17 on average respectively).

####  F3 ✓ Sparse retrieval outperforms zero-shot dense retrieval [34, 41].

Sparse retrieval models are more effective than the majority of zero-shot
dense models, as shown by the comparison of rows (1a–b), and (2a–b) with rows
(3a–c). However, a dense retrieval model that has gone through intermediate
training on large and diverse datasets including dialogues is more effective
than a strong sparse retrieval model, as we see by comparing row (3d) with row
(2b) in Table 3.

For example, while the zero-shot dense retrieval models based only on the
MSMarco dataset (3a–b) perform on average 35% worse than the strong sparse
baseline (2b) in terms of R@10 for the MSDialog dataset, the zero-shot model
trained with 1.17B instances on diverse data (3d) is 68% better than the
sparse baseline (2b). When using a bigger amount of intermediate training
data171717For the full description of the intermediate data see
https://huggingface.co/sentence-transformers/all-mpnet-base-v2., we see that
the zero-shot dense retrieval model (3d) is able to outperform the sparse
retrieval baseline by margins of 33% of R@10 on average across datasets.

We thus show that F3 only generalizes to response retrieval for dialogues if
we do not employ a large set of diverse intermediate data. As expected, the
closer the intermediate training data distribution is to the evaluation data,
the better the dense retrieval model performs. The results indicate that a
good zero-shot retrieval model needs to go through intermediate training on a
large set of training data coming from multiple datasets to generalize well to
different domains and outperform strong sparse retrieval baselines.

####  F4 ✓ Dense models with access to target training data outperform sparse
models [7, 15, 34].

First, we see that fine-tuning the dense retrieval model, which has gone
through intermediate training already, with random sampling—row (4a) in Table
3—achieves the best overall effectiveness in two of the three datasets. This
result shows that F4 generalizes to the task of response retrieval for
dialogues when employing intermediate training181818Our experiments show that
when we do not employ the intermediate training step the fine-tuned dense
model does not generalize well, with row (3d) performance dropping to 0.172,
0.308 and 0.063 R@10 for MANtIS, MSDialog and UDCDSTC8 respectively.. Having
access to the target data as opposed to only the intermediate training data
means that the representations learned by the model are closer to the true
distribution of the data.

We hypothesize that fine-tuning the bi-encoder for MANtIS (4a) is harmful
because the intermediate data contains Stack Exchange responses. In this way,
the set of dialogues of Stack Exchange that MANtIS encompasses might be
serving only to overfit the intermediate representations. As evidence for this
hypothesis, we found that (I) the learning curves flatten quickly (as opposed
to other datasets) and (II) fine-tuning another language model that does not
have Stack Exchange data (MSMarco) in their fine-tuning, bi-encoderbert-base
(3c), improves the effectiveness with statistical significance from 0.092 R@10
to 0.205 R@10.

####  F5 ✓ Hard negative sampling is better than random sampling for training
dense retrieval models [46, 51].

Surprisingly we find that naively using more effective models to select
negative candidates is detrimental to the effectiveness of the dense retrieval
model (see Hard negative sampling in Table 5). We observe this phenomenon when
using different language models, when switching intermediate training on or
off for all datasets, and when using an alternative contrastive loss [10] that
does not employ in-batch negative sampling191919The results are not shown here
due to space limitations.

After testing for a number of hypotheses that might explain why harder
negatives do not improve the effectiveness of the dense retrieval model, we
found that false negative samples increase significantly when using better
negative sampling methods. False negatives are responses that are potentially
valid for the context. Such relevant responses lead to unlearning relevant
matches between context and responses as they receive negative labels. See
below an example of a false negative sample retrieved by the bi-encoder model
(row 3d of Table 3):

Dialogue context ($\mathcal{U}$):  hey… how long until dapper comes out? $[U]$
14 days […] $[U]$ i thought it was coming out tonight Correct response
($r^{+}$): just kidding couple hours False negative sample ($r^{-}$): there is
a possibility dapper will be delayed […] meanwhile, dapper discussions should
occur in ubuntu+1

Denoising techniques try to solve this problem by reducing the number of false
negatives. We employ a simple approach that instead of using the top-ranked
responses as negative responses, we use the bottom responses of the top-ranked
responses as negatives202020For example, if we retrieve $k=100$ responses,
instead of using responses from top positions 1–10, we use responses 91–100
from the bottom of the list.. This decreases the chances of obtaining false
positives and if $k<<|\mathcal{D}|$ we will not obtain random samples. Our
experiments in Table 5 reveal that this denoising technique, row (3b),
increases the effectiveness for harder negative samples, beating all models
from Table 3 for two of the three datasets. The results indicate that F5
generalizes to the task of response retrieval for dialogues only when
employing a denoising technique.

Table 5: Results for the generalizability of F5—with and without a denoising strategy for hard negative sampling. Superscripts indicate statistically significant improvements using Students t-test with Bonferroni correction . †=significance against the random sampling baseline, ‡=significance against hard negative sampling without denoising. | MANtIS | MSDialog | UDCDSTC8
---|---|---|---
|  | R@10 |  | R@10 |  | R@10
Baseline |  |  |  |  |  |
(1) Bi-encoderRandom |  | 0.307 |  | 0.387 |  | 0.128
Hard negative sampling |  |  |  |  |  |
(2a) Bi-encoderBM25 |  | 0.271 |  | 0.316 |  | 0.087
(2b) Bi-encoderBi-encoder |  | 0.146 |  | 0.306 |  | 0.051
Denoised hard negative sampling |  |  |  |  |  |
(3a) Bi-encoderBM25 |  | 0.257 |  | 0.358‡ |  | 0.121‡
(3b) Bi-encoderBi-encoder |  | 0.316†‡ |  | 0.397†‡ |  | 0.107‡

##  6 Conclusion

In this work, we tested if the knowledge obtained in dense and sparse
retrieval from experiments on the tasks of passage and document retrieval
generalizes to the first-stage retrieval of responses for dialogues. Our
replicability study reveals that while most findings do generalize to our
domain, a simple translation of the models is not always successful. A careful
analysis of the domain in question might reveal better ways to adapt
techniques.

As future work, we believe an important direction is to evaluate learned
sparse methods that do weighting and expansion for both the queries and
documents [5]—while resp2ctxt is able to both change the weights of the terms
in the response (by repeating existing terms) and expand terms (by adding
novel terms), it is not able to do weighting and expansion for the dialogue
contexts.

#### Acknowledgements

This research has been supported by NWO projects SearchX (639.022.722) and NWO
Aspasia (015.013.027).

## References

  * [1] Abdul-Jaleel, N., Allan, J., Croft, W.B., Diaz, F., Larkey, L., Li, X., Smucker, M.D., Wade, C.: Umass at trec 2004: Novelty and hard. Computer Science Department Faculty Publication Series p. 189 (2004)
  * [2] Aghajanyan, A., Gupta, A., Shrivastava, A., Chen, X., Zettlemoyer, L., Gupta, S.: Muppet: Massive multi-task representations with pre-finetuning. arXiv preprint arXiv:2101.11038 (2021)
  * [3] Anand, A., Cavedon, L., Joho, H., Sanderson, M., Stein, B.: Conversational search (dagstuhl seminar 19461). In: Dagstuhl Reports. vol. 9. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020)
  * [4] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)
  * [5] Formal, T., Lassance, C., Piwowarski, B., Clinchant, S.: Splade v2: Sparse lexical and expansion model for information retrieval. arXiv preprint arXiv:2109.10086 (2021)
  * [6] Furnas, G.W., Landauer, T.K., Gomez, L.M., Dumais, S.T.: The vocabulary problem in human-system communication. Communications of the ACM 30(11), 964–971 (1987)
  * [7] Gao, L., Callan, J.: Unsupervised corpus aware language model pre-training for dense passage retrieval. arXiv preprint arXiv:2108.05540 (2021)
  * [8] Gu, J.C., Li, T., Liu, Q., Ling, Z.H., Su, Z., Wei, S., Zhu, X.: Speaker-aware bert for multi-turn response selection in retrieval-based chatbots. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management. pp. 2041–2044 (2020)
  * [9] Gu, J.C., Ling, Z.H., Liu, Q.: Interactive matching network for multi-turn response selection in retrieval-based chatbots. In: proceedings of the 28th ACM international conference on information and knowledge management. pp. 2321–2324 (2019)
  * [10] Hadsell, R., Chopra, S., LeCun, Y.: Dimensionality reduction by learning an invariant mapping. In: 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06). vol. 2, pp. 1735–1742. IEEE (2006)
  * [11] Han, J., Hong, T., Kim, B., Ko, Y., Seo, J.: Fine-grained post-training for improving retrieval-based dialogue systems. In: Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1549–1558. Association for Computational Linguistics, Online (Jun 2021). https://doi.org/10.18653/v1/2021.naacl-main.122, https://aclanthology.org/2021.naacl-main.122
  * [12] Hofstätter, S., Lin, S.C., Yang, J.H., Lin, J., Hanbury, A.: Efficiently teaching an effective dense retriever with balanced topic aware sampling. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 113–122 (2021)
  * [13] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7(3), 535–547 (2019)
  * [14] Kadlec, R., Schmid, M., Kleindienst, J.: Improved deep learning baselines for ubuntu corpus dialogs. arXiv preprint arXiv:1510.03753 (2015)
  * [15] Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., Yih, W.t.: Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04906 (2020)
  * [16] Kummerfeld, J.K., Gouravajhala, S.R., Peper, J.J., Athreya, V., Gunasekara, C., Ganhotra, J., Patel, S.S., Polymenakos, L.C., Lasecki, W.: A large-scale corpus for conversation disentanglement. Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (2019). https://doi.org/10.18653/v1/p19-1374, http://dx.doi.org/10.18653/v1/P19-1374
  * [17] Lan, T., Cai, D., Wang, Y., Su, Y., Mao, X.L., Huang, H.: Exploring dense retrieval for dialogue response selection. arXiv preprint arXiv:2110.06612 (2021)
  * [18] Lin, J.: The simplest thing that can possibly work: pseudo-relevance feedback using text classification. arXiv preprint arXiv:1904.08861 (2019)
  * [19] Lin, J.: A proposed conceptual framework for a representational approach to information retrieval. arXiv preprint arXiv:2110.01529 (2021)
  * [20] Lin, J., Ma, X., Lin, S.C., Yang, J.H., Pradeep, R., Nogueira, R.: Pyserini: A Python toolkit for reproducible information retrieval research with sparse and dense representations. In: Proceedings of the 44th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2021). pp. 2356–2362 (2021)
  * [21] Lin, J., Nogueira, R., Yates, A.: Pretrained transformers for text ranking: Bert and beyond. Synthesis Lectures on Human Language Technologies 14(4), 1–325 (2021)
  * [22] Lin, Z., Cai, D., Wang, Y., Liu, X., Zheng, H.T., Shi, S.: The world is not binary: Learning to rank with grayscale data for dialogue response selection. arXiv preprint arXiv:2004.02421 (2020)
  * [23] Lowe, R., Pow, N., Serban, I., Pineau, J.: The ubuntu dialogue corpus: A large dataset for research in unstructured multi-turn dialogue systems. arXiv preprint arXiv:1506.08909 (2015)
  * [24] Nogueira, R., Cho, K.: Passage re-ranking with bert. arXiv preprint arXiv:1901.04085 (2019)
  * [25] Nogueira, R., Lin, J., Epistemic, A.: From doc2query to doctttttquery. Online preprint 6 (2019)
  * [26] Peeters, R., Bizer, C., Glavaš, G.: Intermediate training of bert for product matching. small 745(722), 2–112 (2020)
  * [27] Penha, G., Balan, A., Hauff, C.: Introducing mantis: a novel multi-domain information seeking dialogues dataset. arXiv preprint arXiv:1912.04639 (2019)
  * [28] Penha, G., Hauff, C.: Curriculum learning strategies for ir: An empirical study on conversation response ranking. arXiv preprint arXiv:1912.08555 (2019)
  * [29] Penha, G., Hauff, C.: Challenges in the evaluation of conversational search systems. In: Converse@ KDD (2020)
  * [30] Poth, C., Pfeiffer, J., Rücklé, A., Gurevych, I.: What to pre-train on? efficient intermediate task selection. arXiv preprint arXiv:2104.08247 (2021)
  * [31] Pruksachatkun, Y., Phang, J., Liu, H., Htut, P.M., Zhang, X., Pang, R.Y., Vania, C., Kann, K., Bowman, S.R.: Intermediate-task transfer learning with pretrained models for natural language understanding: When and why does it work? arXiv preprint arXiv:2005.00628 (2020)
  * [32] Qu, C., Yang, L., Croft, W.B., Trippas, J.R., Zhang, Y., Qiu, M.: Analyzing and characterizing user intent in information-seeking conversations. In: The 41st international acm sigir conference on research & development in information retrieval. pp. 989–992 (2018)
  * [33] Reimers, N., Gurevych, I.: Sentence-bert: Sentence embeddings using siamese bert-networks. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics (11 2019), https://arxiv.org/abs/1908.10084
  * [34] Ren, R., Qu, Y., Liu, J., Zhao, W.X., Wu, Q., Ding, Y., Wu, H., Wang, H., Wen, J.R.: A thorough examination on zero-shot dense retrieval. arXiv preprint arXiv:2204.12755 (2022)
  * [35] Robertson, S.E., Walker, S.: Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In: SIGIR’94. pp. 232–241. Springer (1994)
  * [36] Robinson, J., Chuang, C.Y., Sra, S., Jegelka, S.: Contrastive learning with hard negative samples. arXiv preprint arXiv:2010.04592 (2020)
  * [37] Song, K., Tan, X., Qin, T., Lu, J., Liu, T.Y.: Mpnet: Masked and permuted pre-training for language understanding. Advances in Neural Information Processing Systems 33, 16857–16867 (2020)
  * [38] Tao, C., Feng, J., Liu, C., Li, J., Geng, X., Jiang, D.: Building an efficient and effective retrieval-based dialogue system via mutual learning. arXiv preprint arXiv:2110.00159 (2021)
  * [39] Tao, C., Wu, W., Xu, C., Hu, W., Zhao, D., Yan, R.: Multi-representation fusion network for multi-turn response selection in retrieval-based chatbots. In: WSDM. pp. 267–275 (2019)
  * [40] Thakur, N., Reimers, N., Daxenberger, J., Gurevych, I.: Augmented sbert: Data augmentation method for improving bi-encoders for pairwise sentence scoring tasks. arXiv preprint arXiv:2010.08240 (2020)
  * [41] Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., Gurevych, I.: Beir: A heterogenous benchmark for zero-shot evaluation of information retrieval models. arXiv preprint arXiv:2104.08663 (2021)
  * [42] Whang, T., Lee, D., Lee, C., Yang, K., Oh, D., Lim, H.: An effective domain adaptive post-training method for bert in response selection. arXiv preprint arXiv:1908.04812 (2019)
  * [43] Whang, T., Lee, D., Oh, D., Lee, C., Han, K., Lee, D.h., Lee, S.: Do response selection models really know what’s next? utterance manipulation strategies for multi-turn response selection. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35, pp. 14041–14049 (2021)
  * [44] Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., et al.: Huggingface’s transformers: State-of-the-art natural language processing. arXiv preprint arXiv:1910.03771 (2019)
  * [45] Wu, Y., Wu, W., Xing, C., Zhou, M., Li, Z.: Sequential matching network: A new architecture for multi-turn response selection in retrieval-based chatbots. In: ACL. pp. 496–505 (2017)
  * [46] Xiong, L., Xiong, C., Li, Y., Tang, K.F., Liu, J., Bennett, P., Ahmed, J., Overwijk, A.: Approximate nearest neighbor negative contrastive learning for dense text retrieval. arXiv preprint arXiv:2007.00808 (2020)
  * [47] Yang, L., Qiu, M., Qu, C., Chen, C., Guo, J., Zhang, Y., Croft, W.B., Chen, H.: Iart: Intent-aware response ranking with transformers in information-seeking conversation systems. arXiv preprint arXiv:2002.00571 (2020)
  * [48] Yang, L., Qiu, M., Qu, C., Guo, J., Zhang, Y., Croft, W.B., Huang, J., Chen, H.: Response ranking with deep matching networks and external knowledge in information-seeking conversation systems. In: SIGIR. pp. 245–254 (2018)
  * [49] Yang, W., Lu, K., Yang, P., Lin, J.: Critically examining the” neural hype” weak baselines and the additivity of effectiveness gains from neural ranking models. In: Proceedings of the 42nd international ACM SIGIR conference on research and development in information retrieval. pp. 1129–1132 (2019)
  * [50] Yuan, C., Zhou, W., Li, M., Lv, S., Zhu, F., Han, J., Hu, S.: Multi-hop selector network for multi-turn response selection in retrieval-based chatbots. In: EMNLP. pp. 111–120 (2019)
  * [51] Zhan, J., Mao, J., Liu, Y., Guo, J., Zhang, M., Ma, S.: Optimizing dense retrieval model training with hard negatives. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1503–1512 (2021)
  * [52] Zhang, Z., Zhao, H.: Advances in multi-turn dialogue comprehension: A survey. arXiv preprint arXiv:2110.04984 (2021)
  * [53] Zhang, Z., Zhao, H.: Structural pre-training for dialogue comprehension. arXiv preprint arXiv:2105.10956 (2021)
  * [54] Zhou, X., Li, L., Dong, D., Liu, Y., Chen, Y., Zhao, W.X., Yu, D., Wu, H.: Multi-turn response selection for chatbots with deep attention matching network. In: Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1118–1127 (2018)


# Effective estimates of ergodic quantities illustrated on the Bolyai-Rényi
map

Mark Pollicott and Julia Slipantschuk111The authors were partly supported by
ERC-Advanced Grant 833802-Resonances.

###### Abstract

We present a practical and effective method for rigorously estimating
quantities associated to top eigenvalues of transfer operators to very high
precision. The method combines explicit error bounds of the Lagrange-Chebyshev
approximation with an established min-max method. We illustrate its
applicability by significantly improving rigorous estimates on various ergodic
quantities associated to the Bolyai-Rényi map.

##  1 Introduction

In a classic 1957 paper, A. Rényi described a general class of $f$-expansions.
This included, as special cases, base $d$-expansions and $\beta$-expansions;
continued fraction expansions; and (as Example 3 in [16]) the iterated radical
expansions, which first appeared in Bolyai’s 1832 book [3]. This last example
gives an expansion for almost every $0<x<1$ in the form of an iterated square
root:

$x=-1+\sqrt{a_{1}+\sqrt{a_{2}+\sqrt{a_{3}+\cdots}}},$ (1.1)

where $a_{1},a_{2},a_{3},\ldots\in\\{1,2,3\\}$. Related infinite radical
expansions appear in the notebooks of Ramanujan [1].

Statistical properties of the expansions in (1.1) are given by ergodic
properties of the associated Bolyai-Rényi transformation
$T\colon[0,1)\to[0,1)$ \- a piecewise analytic expanding Markov map (see
Section 2) with a unique $T$-invariant probablity measure $\mu$. Bosma, Dajani
and Kraaikamp [5] conjectured that the metric entropy is $h(T,\mu)\approx
1.0545$, accurate to two decimal places. In [7] a rigorous estimate of
$1.056313074$ was given using a periodic point method. One of the aims of this
note is to use estimation of this and other quantities to illustrate an
alternative approach leading to significantly improved estimates.

In this and similar systems, estimating quantities of interest such as
entropy, or digit frequencies, requires approximation of the pressure function
arising from the maximal positive eigenvalue of an appropriately chosen
(positive) transfer operator $\mathcal{L}$. This eigenvalue satisfies the so-
called min-max principle, allowing to bound the pressure function in terms of
bounds on $(\mathcal{L}f)/f$ for suitable positive functions $f$, see [12,
Theorems 7.25-7.26] and [15].

Two crucial ingredients are needed to make these bounds rigorous and
sufficiently tight: the first consists in choosing a suitable $f$, the second
in obtaining rigorous and tight lower and upper bounds on $(\mathcal{L}f)/f$.
For the first step, in order to obtain effective bounds on the pressure
function, the function $f$ should be chosen close to the leading eigenfunction
of $\mathcal{L}$. This can be achieved by approximating $\mathcal{L}$ by a
suitable finite-rank operator $\mathcal{L}_{n}$ and using its leading
eigenfunction as a candidate for $f$. In [15, 14] this was accomplished using
the classical Lagrange-Chebyshev interpolation scheme, for which results in
[2] guarantee exponential convergence (in rank $n$) of eigenfunctions of
$\mathcal{L}_{n}$ to those of $\mathcal{L}$ for analytic expanding maps $T$.
For the second step, rigorous lower and upper bounds on $(\mathcal{L}f)/f$
were obtained using ball arithmetic, involving the use of higher-order
derivatives for increased precision.

In this note we provide a refinement of this method, critically also using the
Lagrange-Chebyshev interpolation method for enhancing the second step. In
particular, the exponential convergence properties of this scheme allow us to
rigorously bound $(\mathcal{L}f)/f$ to much greater precision, while being
more efficient and using a single derivative of the quotient function.
Overall, leveraging the strong convergence properties of Lagrange-Chebyshev
interpolation for efficiently achieving accurate approximation, and ball
arithmetic for rigorous bounding, this “Lagrange-Chebyshev min-max algorithm”
provides a method for rigorous high-accuracy estimation of ergodic quantities
for analytic expanding maps, at comparatively small computational cost.

This note is organized as follows. We introduce the Bolyai-Rényi map and state
our approximation results for several of its ergodic quantities in §2, and
summarize the well-known properties of the associated transfer operator and
its leading eigenvalue in §3. In §4 we describe our min-max method: we derive
the key estimate Theorem 4 in §4.1, describe the choice of approximate
eigenfunctions $f$ in §4.2 and the enhanced method for bounding
$(\mathcal{L}f)/f$ in §4.3, and provide pseudo-code for the method’s
implementation in §4.4. Proofs of the results from §2 based on this method are
given in §5. Finally, in §6 we compare our algorithm with other available
methods, and finish off with some generalizing remarks in §7.

##  2 Bolyai-Rényi transformation and results

Associated to (1.1) is the Bolyai-Rényi transformation $T\colon[0,1)\to[0,1)$
of the form

$T(x)=\begin{cases}x^{2}+2x&\hbox{ if }0\leq x<\sqrt{2}-1\cr x^{2}+2x-1&\hbox{
if }\sqrt{2}-1\leq x<\sqrt{3}-1\cr x^{2}+2x-2&\hbox{ if }\sqrt{3}-1\leq x\leq
1.\cr\end{cases}$

We can then write digits in the radical expansion (1.1) as

$a_{n}=\begin{cases}1&\hbox{ if }0\leq T^{n-1}(x)<\sqrt{2}-1\cr 2&\hbox{ if
}\sqrt{2}-1\leq T^{n-1}(x)<\sqrt{3}-1\cr 3&\hbox{ if }\sqrt{3}-1\leq
T^{n-1}(x)\leq 1.\cr\end{cases}$

Formally, it is often convenient to consider $T$ as a piecewise expanding
Markov map acting on three closed intervals. Since $T$ is expanding (with
$\inf_{x}T^{\prime}(x)\geq 2$) there is a (unique) $T$-invariant probability
measure $\mu$ which is absolutely continuous (even equivalent) to Lebesgue
measure by, for example, the classical Lasota-Yorke theorem [10]. We denote
the metric entropy of $\mu$ by $h(\mu)=h(T,\mu)$, and by the classical Rokhlin
formula it is also conveniently given as the Lyapunov exponent, i.e.,

$h(\mu)=\int\log T^{\prime}(x)d\mu(x),$ (2.1)

which, as usual, quantifies the sensitive dependence on initial conditions for
typical orbits.

######  Theorem 1.

The metric entropy of $T$ can be rigorously estimated to be

$h(\mu)=1.0563130740\,7297055209\,9568877064\,0651679335\,4262184005\ldots,$

accurate to the number of decimal places presented.

The min-max method we use to obtain this new estimate is relatively
undemanding on computer resources and so with more patience it would be
relatively easy to get more decimal places.

######  Example 2.1.

As an application we have a variant on Lochs’ theorem, which originally
compared base $10$ expansions with continued fraction expansions of typical
digits. For a.e. ($\mu$) point $x\in(0,1)$ and $n\geq 1$ we can write

$\displaystyle x$
$\displaystyle=-1+\sqrt{a_{1}+\sqrt{a_{2}+\sqrt{a_{3}+\cdots}}}$ where
$\displaystyle a_{1},a_{2},a_{3},\ldots\in\\{1,2,3\\}$
$\displaystyle=\frac{b_{1}}{3}+\frac{b_{2}}{3^{2}}+\frac{b_{3}}{3^{3}}+\cdots$
where $\displaystyle b_{1},b_{2},b_{3},\ldots\in\\{0,1,2\\}$

and for each $n\geq 1$ we denote by $N_{n}(x)$ the minimal number of digits
($b_{1},b_{2},\ldots,b_{N_{n}(x)}$) in base $3$ expansion which are needed to
specify the first $n$ digits ($a_{1},a_{2},\ldots,a_{n}$) in the radical
expansion. The following is a simple consequence of Theorem 1.

######  Corollary 2.2.

The quantity $\lim_{n\to+\infty}(N_{n}/n)$ evaluates to

$1.0400442024\,5603917587\,6064437681\,7446547515\,185552379\ldots,$

accurate to the number of decimal places presented.

###### Proof.

The proof of Lochs’ theorem is based on the Shannon-McMillan-Breman theorem
[11], generalized to the present example to give that the limit exists and is
equal to the ratio of the entropies of the two maps, that is,
$\log(3)/h(\mu)$, which corresponds to the value stated. ∎

In the following two subsections we will provide further applications of our
method, presenting estimates for several other quantities related to the
Bolyai-Rényi map.

###  2.1 Frequency of digits

We consider the frequency of digits that occur in typical expansions. In
particular, we can define

$f_{i}(x):=\lim_{n\to+\infty}\frac{1}{n}\\#\\{1\leq k\leq
n:a_{k}(x)=i\\}\quad\text{ for }i=1,2,3$

whenever the limit exists. By ergodicity of $T$ the limit exists and is
constant for a.e. ($\mu$) $x\in[0,1)$ and we simply denote it $f_{i}$.

######  Theorem 2.

The digit frequencies are

$\displaystyle f_{1}$
$\displaystyle=0.4640796294\,4716719166\,0214542662\,4296264246\,0872990983\ldots,$
$\displaystyle f_{2}$
$\displaystyle=0.3044190449\,4046044774\,3959549801\,4270582974\,2520632111\ldots,$
$\displaystyle f_{3}$
$\displaystyle=0.2315013256\,1237236059\,5825907536\,1433152779\,6606376905\ldots,$

accurate to the number of decimal places presented.

These are an improvement on the accuracy of previous estimates in [7, Theorem
2], which were computed up to approximately $\pm 10^{-7}$.

###  2.2 Deleted digits

Another interesting problem is to consider the Cantor set whose radical
expansions use only the digits $1$ and $3$, i.e., the “deleted digit” Cantor
set

$\mathcal{E}=\left\\{x=-1+\sqrt{a_{1}+\sqrt{a_{2}+\sqrt{a_{3}+\cdots}}}:a_{1},a_{2},a_{3},\ldots\in\\{1,3\\}\right\\}.$

######  Theorem 3.

The Hausdorff dimension of $\mathcal{E}$ is

$\displaystyle\dim_{H}(\mathcal{E})=0.6439131204\,7072945768\,7895134656\,7617073899\,0093573261\ldots,$

accurate to the number of decimal places presented.

Similar problems have attracted interest in the context of continued fractions
[6, 15] and this result might be considered as an analogy.

##  3 The transfer operators $\mathcal{L}_{t}$

We associate to $T$ the three inverse branches
$T_{1},T_{2},T_{3}\colon[0,1]\to[0,1]$ given by

$T_{i}(x)=\sqrt{i+x}-1\quad\text{ for }i=1,2,3$

(i.e., $T\circ T_{i}(x)=x$ for all $x\in[0,1)$ and $i=1,2,3$) and observe by
direct computation that

$T_{i}^{\prime}(x)=\frac{1}{2(T_{i}(x)+1)}\quad\text{ for }i=1,2,3.$

Let $C([0,1])$ denote the Banach space of continuous functions
$f\colon[0,1]\to\mathbb{R}$ with the supremum norm
$\|f\|_{\infty}=\sup_{x\in[0,1]}|f(x)|$. We recall the following well-known
result.

######  Lemma 3.1 (Lasota-Yorke [10]).

The absolutely continuous $T$-invariant measure $\mu$ on $[0,1]$ satisfies
$h(x):=\frac{d\mu}{dx}\in C([0,1])$, where $h$ is the eigenvector associated
to the maximal eigenvalue $1$ for the linear operator $\mathcal{L}_{0}\colon
C([0,1])\to C([0,1])$ given by

$\mathcal{L}_{0}f(x)=\sum_{i=1}^{3}|T_{i}^{\prime}(x)|f(T_{i}x),\quad\forall
f\in C([0,1]),x\in[0,1].$

More generally, we can consider the following parameterized family of bounded
linear operators.

######  Definition 3.2.

For each $t\in\mathbb{R}$ we let $\mathcal{L}_{t}\colon C([0,1])\to C([0,1])$
denote the bounded linear operator given by

$\mathcal{L}_{t}f(x)=\sum_{i=1}^{3}|T_{i}^{\prime}(x)|^{1+t}f(T_{i}x),\quad\forall
f\in C([0,1]),x\in[0,1].$

We can denote the spectral radius of $\mathcal{L}_{t}$ by $e^{P(t)}$. The
following formulation follows from the spectral radius theorem.

######  Definition 3.3.

We can associate the _pressure function_ $P\colon\mathbb{R}\to\mathbb{R}$
defined by

$P(t)=\lim_{n\to+\infty}\frac{1}{n}\log\|\mathcal{L}_{t}^{n}1\|_{\infty},$

where $1(x)=1$ is the constant function.

As will be seen from the next lemma, the limit exists, and the pressure
function defined this way has certain properties following from the
transformation $T$ being expanding and differentiable. We note that there are
alternative definitions of pressure, e.g. via the variational principle
applied to the function $-t\log|T^{\prime}|$, see [20].

######  Lemma 3.4.

The function $P\colon\mathbb{R}\to\mathbb{R}$ has the following properties:

  1. 1.

$P(0)=0$.

  2. 2.

$P$ is $C^{1}$ (even real analytic), monotone decreasing and convex.

  3. 3.

$\frac{d}{dt}P(t)|_{t=0}=-h(\mu)$.

###### Proof.

The first part follows from bounds on $\|\mathcal{L}_{0}^{n}1\|_{\infty}$, for
$n\geq 0$.

For the second part, the value $e^{P(t)}$ for the spectral radius of
$\mathcal{L}_{t}$ occurs as a maximal simple eigenvalue for the transfer
operator $\mathcal{L}_{t}\colon C^{1}([0,1])\to C^{1}([0,1])$ acting on the
Banach space of $C^{1}$ functions $f\colon[0,1]\to\mathbb{R}$ with the norm
$\|f\|:=\|f\|_{\infty}+\|f^{\prime}\|_{\infty}$ (Ruelle Operator Theorem, see
[13]). The analyticity of $P(t)$ then follows by perturbation theory applied
to the maximal eigenvalue of $\mathcal{L}_{t}$, see [13, 17]. The monotone
decreasing property follows from the negative derivative in the next part.
Convexity follows from the observation that for each $n\geq 1$ the function
$t\mapsto\|\mathcal{L}_{t}^{n}1\|_{\infty}$ is convex.

For the third part, let $h_{t}\in C^{1}([0,1])$ be an eigenfunction
corresponding to the maximal eigenvalue of $\mathcal{L}_{t}$ for
$t\in\mathbb{R}$, and write $h^{\prime}_{t}(x)=\frac{d}{dt}h_{t}(x)$. By
analytic perturbation theory [9], we can differentiate the eigenvalue equation
$\mathcal{L}_{t}h_{t}=e^{P(t)}h_{t}$ at $t=0$ to write

$\mathcal{L}_{0}h_{0}^{\prime}-\mathcal{L}_{0}(\log|T^{\prime}|h_{0})=e^{P(0)}h_{0}^{\prime}+P^{\prime}(0)h_{0}.$

We can then integrate with respect to the measure
$\nu_{0}=\mathcal{L}_{0}^{*}\nu_{0}$ to write

$\displaystyle
P^{\prime}(0)=-\nu_{0}(\log|T^{\prime}|h_{0})=-\mu(\log|T^{\prime}|).$ (3.1)

Finally, the Rokhlin identity gives $h(\mu)=\mu(\log|T^{\prime}|)$. ∎

We will make use of part 3 of Lemma 3.4, despite the unpromising formulation,
to bound the entropy $h(\mu)$ by deriving inequalities on the derivative of
$P(t)$ at $t=0$. In particular, using elementary calculus, we can estimate
$\frac{d}{dt}P(t)|_{t=0}=-h(\mu)$ from estimates of the two values of pressure
$P(\epsilon)$ and $P(-\epsilon)$ for a fixed $\epsilon>0$.

$P(-\epsilon)$$|P(\epsilon)|$$\epsilon$$\epsilon$$0$$P(t)$$t$slope $-h(\mu)$
Figure 1: The pressure function $P(t)$ and the inequalities in Corollary 3.5.

By convexity we can (rigorously) bound the entropy (cf. Figure 1):

######  Corollary 3.5.

For any $\epsilon>0$ we have the bounds

$\frac{P(-\epsilon)}{\epsilon}\geq h(\mu)\geq\frac{|P(\epsilon)|}{\epsilon}.$
(3.2)

######  Remark 3.6.

To make the bounds in (3.2) effective, we need to choose $\epsilon>0$
appropriately small. On the other hand, for large values of $\epsilon$ we
observe that the bounds become the asymptotic derivatives $P^{\prime}(t)$ of
the pressure $P(t)$ as $t\to\pm\infty$. Interestingly these become

$\inf_{\nu}\nu(\log|T^{\prime}|)\leq
h(\mu)\leq\sup_{\nu}\nu(\log|T^{\prime}|),$

where the supremum and infimum range over all $T$-invariant probability
measures, although these are clearly not useful for practical estimates.

##  4 Algorithm for estimating properties of $P(\pm\epsilon)$

The bounds in (3.2) may at first sight seem unpromising since we need to
choose $\epsilon>0$ appropriately small. Therefore it is important to find an
efficient and accurate method to estimate $P(\pm\epsilon)$, or equivalently
the leading eigenvalue of $\mathcal{L}_{\pm\epsilon}$. We shall now describe a
simple min-max method to give an upper bound on this eigenvalue.

###  4.1 Min-max method to bound the top eigenvalue of
$\mathcal{L}_{\pm\epsilon}$

We will use a “min-max” estimate which is based on the following lemma.

######  Lemma 4.1.

Let $t,\alpha\in\mathbb{R}$, and assume there exists a positive continuous
function $g\colon[0,1]\to\mathbb{R}^{+}$ such that
$\sup_{x}\frac{\mathcal{L}_{t}g(x)}{g(x)}\leq e^{\alpha}$. Then
$P(t)\leq\alpha$.

###### Proof.

Since the transfer operator $\mathcal{L}_{t}$ is positive, applying it
multiple times to the inequality in the hypothesis yields

$0<\mathcal{L}_{t}^{n}g(x)\leq e^{\alpha}\mathcal{L}_{t}^{n-1}g(x)\leq
e^{2\alpha}\mathcal{L}_{t}^{n-2}g(x)\leq\cdots\leq e^{n\alpha}g(x)$

for all $x\in[0,1]$. In particular, since $g$ is positive we have

$e^{P(t)}=\lim_{n\to+\infty}\|\mathcal{L}_{t}^{n}g\|_{\infty}^{1/n}\leq
e^{\alpha},$

using our definition of $P(t)$. The claim follows. ∎

Using the fact that $P(t)$ is positive for $t<0$ and negative for $t>0$, the
lemma yields the following implications for any $\epsilon,\alpha,\beta>0$ and
any positive continuous functions $f,g$ (cf. Figure 2):

$\displaystyle\sup_{x}\frac{\mathcal{L}_{\epsilon}g(x)}{g(x)}\leq e^{-\alpha}$
$\displaystyle\implies|P(\epsilon)|\geq\alpha,$ (4.1)
$\displaystyle\sup_{x}\frac{\mathcal{L}_{-\epsilon}f(x)}{f(x)}\leq e^{\beta}$
$\displaystyle\implies P(-\epsilon)\leq\beta.$ (4.2)

Combining with the inequalities in (3.2), we have the following useful bound.

$0$$0$$1$$\mathcal{L}_{\epsilon}g$$e^{-\alpha}g$ $0$$0$$1$$e^{\beta}$
f$\mathcal{L}_{-\epsilon}f$

Figure 2: Illustrations of the hypotheses of (4.1) (left) and (4.2) (right).

######  Theorem 4 (Bounds on the entropy $h(\mu)$).

Let $\epsilon>0$, and assume there are positive continuous functions
$g,f\colon[0,1]\to\mathbb{R}^{+}$ and $\alpha,\beta>0$ satisfying the
hypotheses of (4.1) and (4.2), respectively, then

$\frac{\beta}{\epsilon}\geq h(\mu)\geq\frac{\alpha}{\epsilon}.$ (4.3)

In practice, dividing by a small value $\epsilon$ needs to be more than
compensated for by the efficiency of the approach in estimating $P(-\epsilon)$
and $P(\epsilon)$, to allow $\alpha$ and $\beta$ to be chosen very close
(compared to $\epsilon>0$). There are two crucial ingredients to make the
bounds (4.3) effective, rigorous and computationally efficient. The first
consists in choosing $g,f$ in (4.1), (4.2) as close as possible to the leading
eigenfunctions of $\mathcal{L}_{\pm\epsilon}$, the second in efficiently
computing tight rigorous bounds on $(\mathcal{L}g)/g$ and $(\mathcal{L}f)/f$.
We now describe effective schemes for both, based on Lagrange-Chebyshev
interpolation.

###  4.2 Choosing the functions $f$ and $g$ via interpolation

Given $\epsilon>0$, our aim is to choose suitable functions
$f,g\colon[0,1]\to\mathbb{R}^{+}$ for which we can associate values
$\alpha,\beta>0$ satisfying (4.1) and (4.2) and then apply the bounds in
(4.3). Although there is plenty of scope in how they are actually arrived at,
the most promising way is to choose $f,g$ as close as possible to the leading
eigenfunctions of $\mathcal{L}_{-\epsilon}$ and $\mathcal{L}_{\epsilon}$,
respectively. As these eigenfunctions are not known explicitly, we approximate
them by approximating the respective transfer operators by finite-rank
operators.

More precisely, denoting by $L\colon B\to B$ any bounded operator on a Banach
space $B$, we can approximate it by a finite-rank operator $P_{m}LP_{m}$ where
$P_{m}\colon B\to B$ is a bounded projection operator of finite rank given by

$P_{m}f=\sum_{l=0}^{m-1}e_{l}^{*}(f)e_{l},$

with $e_{l}\in B$ and $e_{l}^{*}\in B^{*}$ for $l=0,\ldots,m-1$. The operator
$P_{m}LP_{m}$ is represented by an $m\times m$ matrix $M$, whose $(k,l)$-entry
is given by

$M_{kl}=e_{k}^{*}(Le_{l}).$

######  Definition 4.2.

For $B=C([-1,1])$, the Lagrange-Chebyshev interpolation scheme consists in
using $P_{m}$ as defined above with

  1. 1.

$e_{l}$ ($0\leq l\leq m-1$) the Chebyshev polynomial of the first kind and
degree $l$; and

  2. 2.

$e_{k}^{*}$ ($0\leq k\leq m-1$) the linear functional given by

$e_{k}^{*}(f)=\frac{2-\delta_{0,k}}{m}\sum_{j=0}^{m-1}f(x_{j})e_{k}(x_{j}),$

with $x_{0},\ldots,x_{m-1}$ the Chebyshev nodes of order $m$,
$x_{j}=\cos((2j+1)\pi/(2m))$.

For an arbitrary interval $I=[c-r,c+r]=\gamma([-1,1])$, with
$\gamma(x)=\gamma_{r,c}(x)=rx+c$ for some $c\in\mathbb{R}$, $r>0$, we denote
$P_{m,\gamma}$ the corresponding Lagrange-Chebyshev interpolation operator on
$B=C(I)$, defined as above with $e_{l}$ and $x_{j}$ replaced with
$\hat{e}_{l}=e_{l}\circ\gamma^{-1}$ and $\hat{x}_{j}=\gamma(x_{j})$,
respectively.

We apply the above scheme to our transfer operator
$L=\mathcal{L}_{\epsilon}\colon C([0,1])\to C([0,1])$, using the change of
coordinates $\gamma=\gamma_{r,c}\colon[-1,1]\to[0,1]$ with $r=c=1/2$. We
obtain an $m\times m$ matrix $M$, whose right eigenvector
$v=(v_{0},\ldots,v_{m-1})^{T}$ corresponding to the largest eigenvalue of $M$
yields a candidate function $g:=g^{(m)}=\sum_{l=0}^{m-1}v_{l}\hat{e}_{l}$ to
use in (4.1). A priori it may not be obvious why $g$ is positive and a good
candidate function, however we observe that $\mathcal{L}_{\epsilon}$ is not an
arbitrary bounded operator. The contractions $T_{i}$ involved in the
definition of $\mathcal{L}_{\epsilon}$ are analytic on $[0,1]$, hence extend
holomorphically to a complex neighbourhood, in particular to a suitable
ellipse $E_{\gamma,R}=\gamma(E_{R})\supset[0,1]$, where $E_{R}\supset[-1,1]$
is a standard Bernstein ellipse222A Bernstein ellipse is an ellipse
$E_{R}\subset\mathbb{C}$ with foci $-1$ and $1$ and lengths of major and minor
semi-axes given by $a=\cosh(\log R)$ and $b=\sinh(\log R)$, respectively. for
some $R>0$. Now, Theorem 3.3 and Corollary 3 of [2] guarantee that the
(generalized) eigenfunctions of
$P_{m,\gamma}\mathcal{L}_{\epsilon}P_{m,\gamma}$ converge (in supremum norm)
exponentially fast in $m$ to those of $\mathcal{L_{\epsilon}}$. In particular,
for large enough $m$, the function $g=g^{(m)}$ is positive on $[0,1]$ and
approximates the eigenfunction for the maximal positive eigenvalue
$e^{P(\epsilon)}$ of $\mathcal{L}_{\epsilon}$.

###  4.3 Rigorous bounds on the supremum/infimum

The main step in establishing the left-hand sides of (4.1) and (4.2) comes
down to rigorously estimating $\sup_{x\in I}h(x)$ for
$h(x)=\mathcal{(L_{\epsilon}}f)(x)/f(x)$ and $I=[0,1]=[c-r,c+r]$ with
$c=r=1/2$. By the mean value theorem we have

$\sup_{x\in I}h(x)\leq h(c)+\sup_{x\in I}|h^{\prime}(x)|\cdot r,$ (4.4)

and using the quotient rule we can write $h^{\prime}=\psi/f^{2}$ with

$\psi=(\mathcal{L}_{\epsilon}f)^{\prime}\cdot
f-f^{\prime}\cdot(\mathcal{L}_{\epsilon}f),$

which we use to rewrite (4.4) as

$\sup_{x\in I}h(x)\leq h(c)+\frac{r}{\inf_{x\in I}f(x)^{2}}\cdot\sup_{x\in
I}|\psi(x)|.$ (4.5)

To obtain a tight bound on $\sup_{x\in I}|\psi(x)|$, we can approximate $\psi$
using the Langrange-Chebyshev interpolation projector $P_{n,\gamma}$,
$n\in\mathbb{N}$, introduced in the previous section, and use the fact that

$\sup_{x\in I}|\psi(x)|\leq\sup_{x\in I}|(\psi-
P_{n,\gamma}\psi)(x)|+\sup_{x\in I}|(P_{n,\gamma}\psi)(x)|.$ (4.6)

We note that the function $\psi$ is holomorphic on
$E_{\gamma,R}=\gamma(E_{R})$ for a suitable $R>1$, whenever $f$ is a
polynomial (or more generally, any entire function). Based on results in [2],
the following lemma shows that the error incurred by this approximation decays
exponentially in $n$, and provides all relevant constants explicitly, allowing
for a rigorous implementation.

######  Lemma 4.3.

Let $R>1$, and let $\psi$ be a holomorphic function on a scaled Bernstein
ellipse $E_{\gamma,R}$. Then for any $\rho\in(1,R)$ and $n\in\mathbb{N}$, the
approximation error under Lagrange-Chebyshev interpolation obeys

$\sup_{x\in I}|(\psi-P_{n,\gamma}\psi)(x)|\leq
c_{\rho,R}\cdot\frac{\cosh(n\log\rho)}{\sinh(n\log R)}\cdot\sup_{x\in
I}|(\psi\circ\gamma\circ\sigma)(Re^{2\pi ix})|,$

where $c_{\rho,R}=\frac{\sinh(\log R)}{\cosh(\log R)-\cosh(\log\rho)}$ and
$\sigma(z)=(z+z^{-1})/2$.

###### Proof.

Writing $\tilde{\psi}=\psi\circ\gamma$, we have

$\sup_{x\in I}|(\psi-
P_{n,\gamma}\psi)(x)|=\sup_{x\in[-1,1]}|(\tilde{\psi}-P_{n}\tilde{\psi})(x)\leq\sup_{z\in
E_{\rho}}|(\tilde{\psi}-P_{n,\gamma}\tilde{\psi})(z)|,$

for any $\rho\in(1,R)$. Using [2, Lemma 2.6], we obtain the bound

$\sup_{z\in E_{\rho}}|(\tilde{\psi}-P_{n,\gamma}\tilde{\psi})(z)|\leq
c_{\rho,R}\cdot\frac{\cosh(n\log\rho)}{\sinh(n\log R)}\cdot\sup_{z\in
E_{R}}|\tilde{\psi}(z)|,$

with the constant $c_{\rho,R}=\sinh(\log R)/(\cosh(\log R)-\cosh(\log\rho))$.
The assertion follows by application of the maximum modulus principle, and
observing that $\sigma$ maps a circle of radius $R$ to the boundary of
$E_{R}$:

$\sup_{z\in E_{R}}|\tilde{\psi}(z)|\leq\sup_{z\in\partial
E_{R}}|\tilde{\psi}(z)|=\sup_{x\in I}|(\tilde{\psi}\circ\sigma)(Re^{2\pi
ix})|.\qed$

######  Remark 4.4.

Expressing a quantity as the extremum of a function over an interval (as done
in the previous lemma) allows for rigorous computational bounding by using
ball arithmetic, as, for example, implemented in the Arb library [8]. In
practice, in order to obtain rigorous bounds on a function $f$ over the
interval $I=[0,1]$, say, we can evaluate $f$ on $k\in\mathbb{N}$ equal-sized
subintervals $I_{l}=[c_{l}-r,c_{l}+r]$, $r=|I|/k,c_{l}=(l-1/2)\cdot r$,
$l=1,\ldots,k$. The image intervals
$J_{l}=[c^{\prime}_{l}-r^{\prime}_{l},c^{\prime}_{l}+r^{\prime}_{l}]$ output
by the ball arithmetic calculation are then guaranteed to satisfy
$f(I_{l})\subseteq J_{l}$, yielding effective lower and upper bounds on $f$.

Combining (4.5), (4.6) and Lemma 4.3 yields the inequality

$\sup_{x\in
I}\frac{\mathcal{L}_{\epsilon}f(x)}{f(x)}\leq\frac{\mathcal{L}_{\epsilon}f(c)}{f(c)}+\frac{r}{\inf_{x\in
I}f(x)^{2}}\left(\delta_{n,\rho,R}(\psi)+\sup_{x\in
I}|(P_{n,\gamma}\psi)(x)|\right),$

where $\delta_{n,\rho,R}(\psi)$ denotes the upper bound from Lemma 4.3 which
decays exponentially with $n$. We note that, as in Remark 4.4, all suprema and
infima on the right-hand side of this inequality can be rigorously bounded via
ball arithmetic.

######  Remark 4.5.

We note that with the same method as above, a rigorous _lower_ bound on the
_infimum_ of $(\mathcal{L}_{\epsilon}f)/f$ can be obtained, yielding

$\inf_{x\in
I}\frac{\mathcal{L}_{\epsilon}f(x)}{f(x)}\geq\frac{\mathcal{L}_{\epsilon}f(c)}{f(c)}-\frac{r}{\inf_{x\in
I}f(x)^{2}}\left(\delta_{n,\rho,R}(\psi)+\sup_{x\in
I}|(P_{n,\gamma}\psi)(x)|\right).$

###  4.4 Algorithmic implementation of rigorous bounds

With the results of the previous sections, we are now ready to describe our
algorithm for computing rigorous and tight estimates on $(\mathcal{L}f)/f$ for
a given transfer operator $\mathcal{L}=\mathcal{L}_{\epsilon}$, which will
form the key ingredient in the proofs of Theorems 1-3; see Algorithm 1.

Algorithm 1 Rigorous lower/upper bounds on $(\mathcal{L}f)/f$

function compute_bounds($\mathcal{L}\colon
g\mapsto\mathcal{L}g,d\mathcal{L}\colon(g,g^{\prime})\mapsto(\mathcal{L}g)^{\prime},m,n,c,r$)

$\\{e_{l}\\},\\{e^{\prime}_{l}\\}\leftarrow$ cheb_basis($m,c,r$)
$\triangleright$ basis functions and their derivatives

$M\leftarrow$ compute_matrix($\mathcal{L},\\{e_{l}\\}$)

$v\leftarrow$ power_method($M$) $\triangleright$ e.vec. corresponding to
leading e.val.

$f\leftarrow\sum_{l}v_{l}\cdot
e_{l}~{};~{}f^{\prime}\leftarrow\sum_{l}v_{l}\cdot e^{\prime}_{l}$

$f_{min}\leftarrow$ inf_ball($f$)

assert($f_{min}>0$) $\triangleright$ abort if eigenfunction non-positive

$\mathcal{L}f\leftarrow\mathcal{L}(f)~{};~{}(\mathcal{L}f)^{\prime}\leftarrow
d\mathcal{L}(f,f^{\prime})$

$\psi\leftarrow(\mathcal{L}f)^{\prime}\cdot f-\mathcal{L}f\cdot f^{\prime}$

$P_{n,\gamma}(\psi),error(P_{n,\gamma},\psi)\leftarrow$
pn_approximate($\psi,n$)

$S\leftarrow$sup_ball($|P_{n,\gamma}(\psi)|$) $+error(P_{n,\gamma},\psi)$

return $\mathcal{L}f(c)/f(c)\mp S\cdot r/f_{min}^{2}$

The algorithm requires access to mappings which, for a given differentiable
function $g$ and its derivative $g^{\prime}$, produce $\mathcal{L}g$ and
$(\mathcal{L}g)^{\prime}$. Following Section 4.2, it begins by computing a
matrix representation $M$ in the Chebyshev basis for a finite-rank
approximation of $\mathcal{L}$ (compute_matrix) and obtaining the eigenvector
$v$ corresponding to its leading eigenvalue via the power method
(power_method).

The corresponding eigenfunction $f$ and its derivative are then used to define
$\psi=(\mathcal{L}f)^{\prime}\cdot f-\mathcal{L}\cdot f^{\prime}$. The
algorithm proceeds by computing $P_{n,\gamma}(\psi)$ and the upper bound on
the approximation error $error(P_{n,\gamma},\psi)=\sup|\psi-
P_{n,\gamma}(\psi)|$ described in Lemma 4.3 (pn_approximate). Finally, it
returns the (rigorous) lower and upper bounds, following the respective
formulas derived in Section 4.3.

We note that all calculations are performed using ball arithmetic to account
for potential accumulation of errors. In particular, as in Remark 4.5, all
$\sup$ (sup_ball) and $\inf$ (inf_ball) computations are performed by function
evaluation on $k$ equal-sized subintervals of $[c-r,c+r]$.

##  5 Proofs of results

###  5.1 Proof of Theorem 1

In order to complete the proof of Theorem 1 we combine the rigorous
computational estimation presented in Sections 4.2-4.4 with Theorem 4.

Algorithm 2 Rigorous lower/upper bounds on $P^{\prime}(0)=-h(\mu)$

function compute_pressure_derivative($\epsilon,m,n,c,r$)

$\mathcal{L}_{\epsilon},d\mathcal{L}_{\epsilon}\leftarrow$
operators($\epsilon$);
$\mathcal{L}_{-\epsilon},d\mathcal{L}_{-\epsilon}\leftarrow$
operators($-\epsilon$)

$b_{min},b_{max}\leftarrow$
compute_bounds($\mathcal{L}_{-\epsilon},d\mathcal{L}_{-\epsilon},m,n,c,r$)

$a_{min},a_{max}\leftarrow$
compute_bounds($\mathcal{L}_{\epsilon},d\mathcal{L}_{\epsilon},m,n,c,r$)

$\beta\leftarrow\log(b_{max})~{};~{}\alpha\leftarrow-\log(a_{max})$

return $\alpha/\epsilon,\beta/\epsilon$

The computational step is summarized in Algorithm 2. Making use of
compute_bounds (see Algorithm 1) to compute rigorous upper bounds

$\frac{\mathcal{L}_{\epsilon}g(x)}{g(x)}\leq e^{-\alpha}\qquad\text{ and
}\qquad\frac{\mathcal{L}_{-\epsilon}f(x)}{f(x)}\leq e^{\beta},$

bounds on $h(\mu)$ are obtained via Theorem 4 as $\alpha/\epsilon\leq
h(\mu)\leq\beta/\epsilon$. In order to obtain the given precision, we make the
following set of parameter choices in executing the algorithm:

  1. (a)

We take the value $\epsilon=10^{-50}$.

  2. (b)

We choose $m=160$ for the rank of the approximation of
$\mathcal{L}_{\epsilon}$.

  3. (c)

We choose $n=200$ for the rank of the Lagrange-Chebyshev approximation of the
function $\psi$ in Section 4.3.

  4. (d)

For estimating suprema and infima with ball arithmetic as described in Section
4.3, we use $k=250$ intervals.

  5. (e)

We use the value333We note that $\psi$ is holomorphic on $E_{\gamma,R}$ for
any $1<R<\exp(\operatorname{arccosh}(3))\approx 5.8$. $R=5.5$ and $\rho=1.001$
for computing the bound on the approximation error in Lemma 4.3.

The resulting values are

$\displaystyle\alpha/\epsilon=1.0563130740\,7297055209\,9568877064\,0651679335\,4262184005\,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>$\displaystyle\beta/\epsilon=1.0563130740\,7297055209\,9568877064\,0651679335\,4262184005\,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
yielding the asserted value for $h(\mu)$.

######  Remark 5.1.

We note that in (4.6), the approximation error incurred by $P_{n,\gamma}$ is
negligible compared to the actual size of the approximated supremum. With our
choices of parameters (in particular, approximation rank $n=200$), the error
is $\sup_{x\in I}|(\psi-P_{n,\gamma}\psi)(x)|<2\cdot 10^{-142}$, whereas
$\sup_{x\in I}|\psi(x)|\approx\sup_{x\in I}|(P_{n,\gamma}\psi)(x)|\approx
10^{-112}$.

###  5.2 Proof of Theorem 2

By a simple application of the Birkhoff ergodic theorem, the frequency $f_{i}$
($i=1,2,3$) of each of the three digits can be expressed in terms of the
$T$-invariant measure $\mu$ as $f_{i}=\mu(I_{i})$, with

$I_{1}=\left[0,\sqrt{2}-1\right),~{}I_{2}=\left[\sqrt{2}-1,\sqrt{3}-1\right),~{}I_{3}=\left[\sqrt{3}-1,1\right).$

Thus we need to estimate the respective measure for each of these digits. To
this end we want to replace the family of operators $\mathcal{L}_{t}$ by the
following.

######  Definition 5.2.

Given $t\in\mathbb{R}$, we define operators $\mathcal{N}_{i,t}\colon
C([0,1])\to C([0,1])$ for $i=1,2,3$ by

$\mathcal{N}_{i,t}f(x)=\mathcal{L}_{t}f(x)+(e^{t}-1)|T_{i}^{\prime}(x)|f(T_{i}).$

We can denote by $e^{R_{i}(t)}$ the spectral radius of the operator
$\mathcal{N}_{i,t}$.

######  Definition 5.3.

For $i=1,2,3$ we define $R_{i}\colon\mathbb{R}\to\mathbb{R}$ as

$R_{i}(t)=\limsup_{n\to+\infty}\frac{1}{n}\log\|\mathcal{N}_{i,t}^{n}1\|_{\infty},$

where $1(x)=1$ is the constant function and
$\|f\|_{\infty}=\sup_{x\in[0,1]}|f(x)|$.

The following results are analogues of Lemma 3.4 and Corollary 3.5.

######  Lemma 5.4.

For $i=1,2,3$ the function $R_{i}\colon\mathbb{R}\to\mathbb{R}$ has the
following properties:

  1. 1.

$R_{i}(0)=0$.

  2. 2.

$R_{i}$ is $C^{\infty}$ (even real analytic), monotone decreasing and convex.

  3. 3.

$\frac{d}{dt}R_{i}(t)|_{t=0}=-f_{i}$.

######  Corollary 5.5.

For $\epsilon>0$ and $i=1,2,3$ we can bound

$\frac{R_{i}(-\epsilon)}{\epsilon}\geq\mu(I_{i})\geq\frac{|R_{i}(\epsilon)|}{\epsilon}.$

In order to convert these bounds into practical estimates we need the analogue
of Lemma 4.1, now for the operators $\mathcal{N}_{i,t}$ ($i=1,2,3$).

######  Lemma 5.6.

Let $t,\alpha\in\mathbb{R}$, $i=1,2,3$. If there exists a positive continuous
function $g\colon[0,1]\to\mathbb{R}^{+}$ such that
$\sup_{x}\frac{\mathcal{N}_{i,t}g(x)}{g(x)}\leq e^{\alpha}$, then
$R_{i}(t)\leq\alpha$.

The remainder of the proof of the theorem is completely analogous to that of
Theorem 1, where for the computational step we also use the exact same
parameter values.

###  5.3 Proof of Theorem 3

We can adapt the method of the proof of Theorem 1 to prove Theorem 3. To begin
we need to replace the operators $\mathcal{L}_{t}$ by the following operators.

######  Definition 5.7.

For any $t\in\mathbb{R}$, let $\mathcal{M}_{t}\colon C([0,1])\to C([0,1])$ be
the bounded linear operator defined by

$\mathcal{M}_{t}f(x)=|T_{0}^{\prime}(x)|^{t}f(T_{0}x)+|T_{2}^{\prime}(x)|^{t}f(T_{2}x)\quad\forall
f\in C([0,1]),x\in[0,1].$

Denoting the spectral radius of $\mathcal{M}_{t}$ by $e^{Q(t)}$, the following
re-formulation follows from the spectral radius theorem.

######  Definition 5.8.

We can write $Q\colon\mathbb{R}\to\mathbb{R}$ as

$Q(t)=\lim_{n\to+\infty}\frac{1}{n}\log\|\mathcal{M}_{t}^{n}{\mathbf{1}}\|_{\infty},$

where ${\mathbf{1}}(x)=1$ is the constant function.

The following result is the analogue of Lemma 3.4.

######  Lemma 5.9.

The function $Q\colon\mathbb{R}\to\mathbb{R}$ is $C^{\infty}$ (even real
analytic), monotone decreasing and convex.

The following lemma can be proved analogously to Lemma 4.1.

######  Lemma 5.10.

Let $t>0,\alpha\in\mathbb{R}$, and let $g\colon[0,1]\to\mathbb{R}^{+}$ be a
positive continous function. Then the following implications hold:

$\displaystyle\inf_{x\in[0,1]}\frac{\mathcal{M}_{t}g(x)}{g(x)}\geq e^{\alpha}$
$\displaystyle\implies Q(t)\geq\alpha,$ (5.1)
$\displaystyle\sup_{x\in[0,1]}\frac{\mathcal{M}_{t}g(x)}{g(x)}\leq e^{\alpha}$
$\displaystyle\implies Q(t)\leq\alpha.$ (5.2)

The connection between $\dim(\mathcal{E})$ and the function $Q$ is the
following classical result [4, 18].

######  Lemma 5.11 (Bowen’s Theorem).

The Hausdorff dimension of $\mathcal{E}$ corresponds to the solution
$t=\dim_{H}(\mathcal{E})$ to $Q(t)=0$.

$t_{0}$$t_{1}$$Q(t_{0})$$|Q(t_{1})|$$\dim_{H}(\mathcal{E})$$Q(t)$$t$ Figure 3:
$t_{0}\leq\dim_{H}(\mathcal{E})\leq t_{1}$

Lemmas 5.10 and 5.11 and the monotonicity of $Q(t)$ immediately yield the
following corollary (see Figure 3).

######  Corollary 5.12.

Let $t_{1}>t_{0}>0$ and assume there are positive continuous functions
$f,g\colon[0,1]\to\mathbb{R}^{+}$ and $\alpha,\beta>0$ such that

$\inf_{x}\frac{\mathcal{M}_{t_{0}}g(x)}{g(x)}\geq e^{\beta}\quad\text{ and
}\quad\sup_{x}\frac{\mathcal{M}_{t_{1}}f(x)}{f(x)}\leq e^{-\alpha}.$

Then $t_{0}<\dim_{H}(\mathcal{E})<t_{1}$.

######  Remark 5.13.

It is worth noting that in the proofs of Theorems 1 and 2 our goal was to
estimate the _derivative_ of the pressure function, which required obtaining
two upper bounds on expressions of the form $(\mathcal{L}f)/f$. Here, on the
other hand, we are aiming to accurately estimate the _zero_ of such function,
which is achieved by computing a pair of lower and upper bounds.

Corollary 5.12 provides us with a criterion that we can easily rigorously
verify with the computational method described in Section 4, in particular
using Algorithm 1.

Algorithm 3 Rigorous lower/upper bounds on zero of $Q$

function compute_pressure_zero($t_{0},t_{1},m,n,c,r,\delta$)

while $t_{1}-t_{0}>\delta$ do $\triangleright$ iterate to desired precision
$\delta$

$t\leftarrow(t_{0}+t_{1})/2$

$\mathcal{M}_{t},d\mathcal{M}_{t}\leftarrow$ operators($t$)

$\alpha_{min},\alpha_{max}\leftarrow$
compute_bounds($\mathcal{M}_{t},d\mathcal{M}_{t},m,n,c,r$)

if $\alpha_{min}>0$ then

$t_{0}\leftarrow t$

else if $\alpha_{max}<0$ then

$t_{1}\leftarrow t$

else$\triangleright$ also invoke this case if compute_bounds fails
($f_{min}\leq 0$)

$m\leftarrow m+1$

return $t_{0},t_{1}$

The entire procedure is described in Algorithm 3. It is based on a binary
search principle: beginning with a small initial approximation rank $m$ and an
interval $[t_{0},t_{1}]$ guaranteed to contain $\dim_{H}(\mathcal{E})$, we
compute rigorous bounds on $\inf$ and $\sup$ of $\mathcal{M}_{t}f/f$ for $t$
the mid-point of $[t_{0},t_{1}]$ (compute_bounds). If
$\inf(\mathcal{M}_{t}f)/f>1$, then $\dim_{H}(\mathcal{E})>t$ and the search
continues on the sub-interval $[t,t_{1}]$; if $\sup(\mathcal{M}_{t}f)/f<1$,
then $\dim_{H}(\mathcal{E})\leq t$ and the search continues on $[t_{0},t]$. If
neither of the conditions hold, or if the approximate eigenfunction $f$
computed in compute_bounds fails to be positive (both of which can occur due
to insufficiently accurate finite-rank approximation of the operator), then we
increment the approximation rank $m$ and repeat the procedure on
$[t_{0},t_{1}]$. This iteration proceeds until the required accuracy
$\delta>0$ is reached, that is, until $t_{1}-t_{0}<\delta$.

We perform this computation with the initial values $t_{0}=0.5$, $t_{1}=0.8$
and $m=10$, and the parameters $n=100$, $k=250$, $\rho=1.001$ and $R=5.5$,
which yields the asserted value and accuracy for $\dim_{H}(\mathcal{E})$,
proving Theorem 3. We note that in practice the algorithm reaches this
accuracy after incrementing the approximation rank for $\mathcal{M}_{t}$ to
$m=75$.

##  6 Comparison with other approaches

In this section we compare the estimate in Theorem 1 with the results obtained
using other methods.

###  6.1 The finite section method

There is a more classical approach to estimating the entropy of the Bolyai-
Rényi map directly. We have seen that the metric entropy $h(\mu)$ (or
equivalently the Lyapunov exponent) can be described using the maximal
eigenvalue and the associated eigenfunction (and eigenmeasure) of a transfer
operator, see (3.1). We write

$h(\mu)=\mu(\log|T^{\prime}|)=\ell^{*}(\eta\cdot\rho),$

where $\rho,\ell^{*}$ are the eigenfunction and eigenfunctional of
$\mathcal{L}_{0}$ corresponding to the leading eigenvalue $1$, normalized so
that $\ell^{*}(f)=1$, and $\eta(x)=\log(|T^{\prime}(x)|)$ for $x\in I=[0,1]$.

Using the Lagrange-Chebyshev interpolation method (Definition 4.2), we
approximate $\mathcal{L}_{0}$ by a rank $m$ operator (for some
$m\in\mathbb{N}$), represented by an $m\times m$ matrix $M$. The right and
left eigenvectors $v,w\in\mathbb{R}^{m}$ corresponding to the leading
eigenvalue of $M$ give rise to the corresponding eigenfunction $\rho_{m}$ and
the eigenfunctionals $\ell_{m}$ of the approximating rank $m$ operator via

$\rho_{m}(x)=\sum_{l=0}^{m-1}v_{l}e_{l}(x)\quad\text{ and
}\quad\ell_{m}(f)=\sum_{l=0}^{m-1}w_{l}e_{l}^{*}(f),$

where $e_{m}$ and $e^{*}_{m}$ are as in Definition 4.2, up to an (affine)
change of coordinates, taking into account the (non-standard) interval
$I=[0,1]$. Writing $b_{l}=e_{l}^{*}(\eta\cdot\rho_{m})$, the approximation to
the entropy can now be computed as

$h_{m}=\frac{\ell_{m}(\eta\cdot\rho_{m})}{\ell_{m}(\rho_{m})}=\frac{\sum_{l=0}^{m-1}b_{l}w_{l}}{\sum_{l=0}^{m-1}v_{l}w_{l}}.$

The denominator in this expression is needed for normalization.

######  Example 6.1.

If we let $m=100$ and carry out the above calculation we have the following
heuristic estimate for the entropy

$\displaystyle h_{100}=1.$ $\displaystyle
0563130740\,7297055209\,9568877064\,0651679335\,4262184005\,$ $\displaystyle
7092244740\,0283696700\,9505655203\,1501166170\,438688675\ldots$

This agrees with the value in Theorem 1. Theorem 3.3 and Corollary 3 of [2]
guarantee exponential convergence (in $m$) of $h_{m}$ to $h(\mu)$, where the
convergence rate can be bounded using the complex contraction ratios of the
inverse branches of $T$ on suitable Bernstein ellipses. However the implied
constant depends on the resolvent of the operator, making rigorous error
estimates more difficult to obtain in this case.

###  6.2 The periodic point method

The approach in [7] was based on using the data $(T^{n})^{\prime}(x)$ for
fixed points $T^{n}x=x$ for $T^{n}\colon[0,1]\to[0,1]$ ($n\geq 1$). More
precisely, one considers a determinant function of two variables formally
defined by

$d(z,s)=\exp\left(-\sum_{n=1}^{\infty}\frac{z^{n}}{n}\sum_{T^{n}x=x}\frac{|(T^{n})^{\prime}(x)|^{-s}}{1-1/(T^{n})^{\prime}(x)}\right),$

which converges for any $z\in\mathbb{C}$ and $\operatorname{Re}(s)$
sufficiently large, and has an analytic extension to $\mathbb{C}^{2}$. The
entropy can then be written in the form

$h(\mu)=\frac{\partial d(z,s)}{ds}\big{/}\frac{\partial
d(z,s)}{dz}\big{|}_{s=0,z=1}.$

In order to convert this into a useful algorithm we truncate the Taylor series
for $d(z,s)$ in $z$. In particular, for any $\frac{1}{3-\sqrt{3}}<\theta<1$
and $M\geq 1$, we have

$d(z,s)=1+\sum_{n=1}^{M}a_{n}(s)z^{n}+O(\theta^{M^{2}}),$

where $a_{n}(s)$ depends only on the weights associated to periodic points of
period at most $n$.

######  Example 6.2.

With the choice $M=12$ the entropy was rigorously estimated to be444Here the
notation $x=A\pm 10^{-\kappa}$ signifies that $A-10^{-\kappa}\leq x\leq
A+10^{-\kappa}$ holds rigorously. $h(\mu)=1.05631307402\pm 4.1\times 10^{-6}$
(see [7, §5]) and heuristically estimated to $9$ decimal places as
$1.056313074$. This required computing the $3^{M}=531441$ periodic points
$T^{n}x=x$ and their weights $(T^{n})^{\prime}(x)$ for $1\leq n\leq 12$.

Although the error terms can be bounded with comparative ease, an issue for
this method is the exponential growth in data that needs to be managed as $M$
increases.

##  7 Final remarks

In this last section, we briefly comment on some directions in which our
method and results generalize, as well as on some of their limitations.

######  Remark 7.1.

In the interest of clarity, we have chosen to define the operators
$\mathcal{L}_{t}$, $\mathcal{M}_{t}$ and $\mathcal{N}_{j,t}$ separately.
Instead, we could have introduced a single more general class of operators of
the form

$\widehat{\mathcal{L}}_{t}f(x)=\sum_{i=0}^{2}|T_{i}^{\prime}(x)|e^{g(T_{i}x)}f(T_{i}x),$

with different choices of $g\in C^{1}([0,1])$ giving rise to the three
operators of interest.

######  Remark 7.2.

Our method readily applies to generalizations of the Bolyai-Rényi
transformation [19]. As an example, for $m\in\mathbb{N}\setminus\\{1\\}$ we
consider $\tilde{T}_{m}\colon[0,1)\to[0,1)$ given by

$\tilde{T}_{m}(x)=(x+1)^{m}-1,$

noting that for $m=2$ this reduces to the classical Bolyai-Rényi map
$T=\tilde{T}_{2}$. For each $m$, the map $\tilde{T}_{m}$ has exactly $2^{m}-1$
contractive inverse branches given by $x\mapsto(x+i)^{1/m}-1$,
$i=1,2,\ldots,2^{m}-1$. Completely analogously to Theorem 1, we can rigorously
estimate the entropy $h(\tilde{T}_{m},\mu_{m})$ (where $\mu_{m}$ denotes the
respective $\tilde{T}_{m}$-invariant probability measure absolutely continuous
to Lebesgue measure). For $m=3,4,\ldots,10$ we obtain the following values,
each accurate to the number of decimal places presented:

m | $h(\tilde{T}_{m},\mu_{m})$
---|---
3 | 1.83495 44938 47482…
4 | 2.50156 90070 03226…
5 | 3.10685 89449 66953…
6 | 3.67309 55489 06997…
7 | 4.21213 20147 18818…
8 | 4.73108 63064 39220…
9 | 5.23459 49760 98698…
10 | 5.72585 67503 35337…

######  Remark 7.3.

We have presented our results in the specific setting of expansions by
iterated radicals. This is in part to illustrate the method, and as a paradigm
of a more general method, which originated in [15], while also giving better
results on the map $T$, interesting in its own right. The important properties
that we need (and which are easy to check for $T$) are the following:

  1. 1.

$T$ is conformal (which is automatic since it is one dimensional);

  2. 2.

$T$ is $C^{1}$;

  3. 3.

$T$ has a finite number of inverse branches;

  4. 4.

$T$ is expanding, i.e., there exists $\kappa>1$ such that
$\inf_{x}|T^{\prime}(x)|\geq\kappa$;

  5. 5.

$T$ is Markov (even Bernoulli, in this case).

This fits naturally in the setting of $f$-expansions [16]. These properties
allow us to make of use Theorem 4, Corollaries 5.5 and 5.12. In order to bound
the relevant quantities rigorously to a very high precision using the
algorithm presented, we crucially used the fact that $T$ is analytic, ensuring
exponential convergence of the Lagrange-Chebyshev interpolation scheme [2].

######  Remark 7.4.

While as above our method generalizes beyond the exact setting of this paper,
we should also acknowledge its limitations. In particular, the application of
our method presented here is specifically tailored for estimating quantities
relating to the top eigenvalue of a transfer operator. It is not directly
applicable to estimating quantities such as the rate of mixing of a
transformation, which is determined by the transfer operator’s spectral gap
and has been previously estimated with the periodic point method [7].

######  Remark 7.5.

A real number is called _computable_ if there is an algorithm (corresponding
to a Turing machine) computing a value abitrarily close to that number. The
set of computable numbers is countable. It is a consequence of the algorithm
presented that the entropy $h(\mu)$ is a computable number.

######  Remark 7.6.

Our algorithm can be used to obtain any specified accuracy on the estimated
quantities (given sufficient computational resources). It is natural to ask
how its time complexity grows with an increase in desired accuracy. This boils
down to the time complexity of compute_bounds (Algorithm 1), which is driven
by computing the top eigenvalue and corresponding eigenvector of an $m\times
m$ matrix, and evaluating the approximation $P_{n}\psi$ on $k$ intervals. The
first of these has a complexity of $O(p\cdot m^{2})$, with $p$ the number of
steps of the power method (both $p$ and $m$ can be expected to be
$O(\log(1/\delta))$ for a desired eigenvector accuracy of $\delta$), the
second has a complexity of $O(k\cdot n)$.

## References

  * [1] B.C. Berndt, Ramanujan’s Notebooks, Part II, Springer, Berlin, 1989.
  * [2] O.F. Bandtlow and J. Slipantschuk, Lagrange approximation of transfer operators associated with holomorphic data, (2020) arXiv:2004.03534.
  * [3] W. Bolyai, Tentamen iuventutem stúdiósam in elementa matheseos purae elementáris ac sublimioris methodo intuitiva evidentiaque huic propria introducendi, ed. sec. (Budapest, 1897), Vol. 1.
  * [4] R. Bowen, Hausdorff dimension of quasi-circles, Publ. Math. I.H.E.S. 50 (1979) 11–25.
  * [5] W. Bosma, K. Dajani and C. Kraaikamp, Entropy quotients and correct digits in number-theoretic expansions, in Dynamics & stochastics, 176–188, IMS Lecture Notes Monogr. Ser., 48, Inst. Math. Statist., Beachwood, OH, 2006.
  * [6] I. J. Good, The fractional dimension theory of continued fractions Proc. Camb. Phil. Soc. 37 (1941) 199–228.
  * [7] O. Jenkinson and M. Pollicott, Ergodic properties of the Bolyai-Rényi expansion, Indag. Math. 11 (2000) 399–418.
  * [8] F. Johansson, Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput. 66 (2017) 1281–1292.
  * [9] T. Kato, Perturbation Theory for Linear Operators, Springer, Berlin, 2013.
  * [10] A. Lasota and J. Yorke, On the existence of invariant measures for piecewise monotonic transformations, Trans. Amer. Math. Soc. 186 (1973) 481–488.
  * [11] G. Lochs, Vergleich der Genauigkeit von Dezimalbruch und Kettenbruch, Abh. Math. Semin. Univ. Hambg. 27 (1964), 142–144.
  * [12] D. H. Mayer, Continued fractions and related transformations, Lectures at the Topical Meeting on Hyperbolic Geometry and Ergodic Theory, ICTP-Trieste, Italy (1989).
  * [13] W. Parry and M. Pollicott, Zeta functions and the periodic orbit structure of hyperbolic dynamics, Astérisque, 187-188 (1990) 1–268.
  * [14] M. Pollicott and J. Slipantschuk, Sierpiński fractals and the dimension of their Laplacian spectrum, Math. Comput. Appl. 28(3) (2023) 70.
  * [15] M. Pollicott and P. Vytnova, Hausdorff dimension estimates applied to Lagrange and Markov spectra, Zaremba theory, and limit sets of Fuchsian groups, Trans. Amer. Math. Soc. Ser. B 9 (2022).
  * [16] A. Rényi, Representations for real numbers and their ergodic properties. Acta Mathematica Academiae Scientiarum Hungaricae 8 (1957) 477–493.
  * [17] D. Ruelle, Thermodynamic Formalism, Addison-Wesley, New York, 1978.
  * [18] D. Ruelle, Repellers for real analytic maps, Ergodic Theory Dynam. Systems, 2 (1982) 99–107.
  * [19] F. Schweiger, Invariant measures of piecewise fractional linear maps and piecewise quadratic maps, Int. J. Number Theory 14 (2018) 1559–1572.
  * [20] P. Walters, Ergodic Theory, Springer, Berlin, 1982.

M. Pollicott, Department of Mathematics, University of Warwick, Coventry, CV4
7AL, UK.

E-mail<EMAIL_ADDRESS>
J. Slipantschuk, Department of Mathematics, University of Warwick, Coventry,
CV4 7AL, UK.

E-mail<EMAIL_ADDRESS>