# Fundamental limits for learning hidden Markov model parameters

Kweku Abraham  Elisabeth Gassiat and Zacharie Naulet
Université Paris-Saclay  CNRS  Laboratoire de Mathématiques d’Orsay
91405 Orsay  France

###### Abstract

We study the frontier between learnable and unlearnable hidden Markov models
(HMMs). HMMs are flexible tools for clustering dependent data coming from
unknown populations. The model parameters are known to be fully identifiable
(up to label-switching) without any modeling assumption on the distributions
of the populations as soon as the clusters are distinct and the hidden chain
is ergodic with a full rank transition matrix. In the limit as any one of
these conditions fails, it becomes impossible in general to identify
parameters. For a chain with two hidden states we prove nonasymptotic minimax
upper and lower bounds, matching up to constants, which exhibit thresholds at
which the parameters become learnable. We also provide an upper bound on the
relative entropy rate for parameters in a neighbourhood of the unlearnable
region which may have interest in itself.

##  1 Introduction

###  1.1 Context and motivation

Finite state space hidden Markov models (HMMs) are widely used in applications
to model observations coming from different populations. HMMs can be viewed as
particular mixture models. In the latter, given a latent sequence of cluster
labels $(X_{n})_{n\in\mathbb{N}}$ taking values in a finite set, the observed
data $(Y_{n})_{n\in\mathbb{N}}$ is a sequence of independent random variables
with for each $n$ the distribution of $Y_{n}$ depending only on $X_{n}$. When
the $X_{n}$ are independent, a mixture model is not identifiable: various
convex combinations of population probability distributions can lead to the
same distribution for the observations. This is true even for observations
taking values in a finite alphabet: one cannot recover two different
multinomial distributions from a convex combination of them.

For a HMM, one adds the extra structure that $(X_{n})_{n\in\mathbb{N}}$ forms
a Markov chain. In sharp contrast to the independent setting, with hidden
Markov structure one can recover the distribution of data for each population
absent virtually any constraint on these distributions (known in this context
as the emission distributions). This fact had been observed in applied papers,
and a theoretical proof that parameters can be identified with minimal
assumptions is recent, given for HMMs taking values in a finite set in [5, 24,
6] and extended to allow for emission distributions modelled nonparametrically
(but still with the underlying Markov chain having finite state space) in [18,
4]. HMMs therefore form a tractable class of model nevertheless rich enough to
model many practical clustering settings well: see for instance [11, 27, 25,
37, 42, 41]. In this context note that given good estimates of the model
parameters one can almost match the optimal clustering and testing behaviour
of the Bayes classifier (e.g. see [39], [2]); let us emphasise once more that
this is possible essentially absent any constraint on the emission
distributions, in contrast to typical clustering algorithms which may require
parametric modelling or separation of clusters.

In drawing a contrast between the independent and dependent cases, we have so
far omitted to mention that of course an independent model is a degenerate
subcase of a Markov model. There are three ways in which the data
$(Y_{n})_{n\in\mathbb{N}}$ can fail to exhibit dependence: when the population
labels themselves are in reality independently distributed; when the emission
distributions are identical; or when only one population is observed. It is
thus of theoretical and practical importance to understand quantitatively what
happens when these limiting situations are approached.

The present work initiates an exploration of the limits of learnability of the
hidden Markov parameters as the independent subcase is approached. We focus on
the setting of two hidden states and multinomial data, and exhibit principles
which should generalise to much wider settings.

###  1.2 Contribution

Our main result, Theorem 1, gives upper and lower bounds showing the minimax
estimation rate for the model parameters, exhibiting that these parameters can
be learned if and only if the sample size $n$ is large enough compared to a
suitable measure of the closeness of the data to the independent subcase.

Important steps to get the main result are as follows. We introduce a
reparametrisation of the model leading to a statistical distance which appears
to be a key tool for the understanding of the fundamental limits of learning
the HMM parameters near the independent subcase. This statistical distance is
proved in Proposition 1 to be equivalent to the distance between the
distribution of three consecutive observations, and leads to an explicit upper
bound of the relative entropy rate for a specific part of parameters domain,
see Proposition 2, which we believe could have interest in itself. Upper
bounds for the learning of the new parameters are proved in Theorem 2 while
(almost) matching lower bounds are proved in Theorem 3.

###  1.3 Related work

Theoretical justification of a range of learning methods for HMMs with
emission distributions modelled parametrically or nonparametrically have been
developed in recent years: moment and tensor methods in [6, 13], and model
selection using penalized least squares estimation in [12, 29], using
penalized likelihood methods in [30], or using other techniques in [28]. These
works all give both asymptotic and nonasymptotic upper bounds controlling the
distance between estimators and the unknown parameters. All require the data
to truly be dependent, but none quantify explicitly how their sample
complexity results depend on the “distance” to independence. Indeed,
quantifying this dependence requires a sharp understanding of how the
distances between distributions evolve with respect to the distances between
parameters, as done for particular parametric finite mixture models in [21,
23, 16].

Results in [13] control the propagation of errors from parameter estimation to
the posterior probabilities when calculating the latter via plug-in, implying
that good control on the risk of the estimators will ensure the performance of
the empirical Bayes classifier is close to that of the true Bayes classifier
(whose optimality for clustering is a standard result in decision theory
[14]).

A topic closely related to binary classification/clustering is multiple
testing, in which one aims to identify within some large data set a collection
of data points which come from a “discovery” hypothesis, rather than from the
conservative null hypothesis. In this setting control of the false discovery
rate has been obtained recently for a knockoffs-based method in [36] and for
an empirical Bayes method in [39, 1]; in each case estimation of the HMM
parameters is an essential first step. Modelling the proportion of non-null
signals as vanishingly small, as our results permit, would allow for further
links to the setting of _sparse_ multiple testing, considered for example
(with independent data) in [3, 10].

Relative entropy rate, or equivalently Kullback-Leibler rate, between HMMs can
be expressed using Blackwell’s invariant measure [9], but no explicit
formulation exists [38]. Providing useful or meaningful upper and lower bounds
is a subject of ongoing research [15, 31, 17]. In Proposition 2 we obtain a
new bound on the Kullback-Leibler rate between HMMs which compared to the
aforementioned works does a better job at capturing the effects of the
underlying Markov dependency structure, at the expense of holding only for a
restricted subspace of parameters.

To the best of our knowledge no prior theoretical result exists addressing the
learning of parameters of a HMM when approaching the independent case. By
experimentally studying the EM algorithm when the multinomial emission
distributions approach each other, the authors in [35] find a range of
parameters for which the EM algorithm behaves badly. We believe such behavior
is primarily a result of the investigated region approaching the limit where
the parameters become unlearnable, not of a limitation of the EM algorithm
specifically.

Finally, let us mention that departure from the independence assumption has
been noted to allow for better learning also in HMM settings free from the
assumption that the Markov chain has a finite state space [20, 7] (at the
expense of stricter assumptions on the emission distributions), and also in
other problems including dynamic networks [32, 8], image denoising [33], and
deconvolution [19].

###  1.4 Organisation of the paper

We describe the setting in Section 2 and state our main result in Section 3.
The key reparametrisation is given in Section 4 where we state the basic
propositions involving the statistical distance we define. Intermediate upper
bound results are given in Section 5 while lower bounds are in Section 6. In
Section 7 we discuss our results and possible further work. All proofs are
deferred to Section 8.

##  2 Setting

Consider a two-state HMM with multinomial emissions, in which we observe the
first $n$ entries of a sequence
$\bm{Y}=(Y_{1},Y_{2},\dots)\in\\{1,\dots,K\\}^{\mathbb{N}}$ which, under a
parameter $\theta=(p,q,f_{0},f_{1})$, satisfies

$\begin{split}\mathbb{P}_{\theta}(Y_{n}=k\mid\bm{X})&=f_{X_{i}}(k),\\\
\bm{X}=(X_{n})_{n\in\mathbb{N}}&\sim\operatorname{Markov}(\pi,Q),\end{split}$
(1)

with the $Y_{j},\leavevmode\nobreak\ j\in\mathbb{N}$ conditionally independent
given $\bm{X}$. The vector $\bm{X}$ of ‘hidden states’ takes values in
$\\{0,1\\}^{\mathbb{N}}$ and the transition matrix of the chain is given by

$Q\coloneqq\begin{pmatrix}1-p&p\\\ q&1-q\end{pmatrix},$ (2)

with the convention that for $j\geq 1$, $\mathbb{P}_{\theta}(X_{j+1}=0\mid
X_{j}=0)=1-p<1$ and $\mathbb{P}_{\theta}(X_{j+1}=0\mid X_{j}=1)=q>0$. The
densities $f_{0},f_{1}$ are the ‘emission densities’ with respect to counting
measure on $\\{1,\dots,K\\}$. Grant also that $X_{1}$ is drawn from the
stationary distribution of the chain, i.e.
$\mathbb{P}_{\theta}(X_{1}=1)=p/(p+q)$. We throughout use
$\mathbb{P}_{\theta}$ to denote the law of $(\bm{X},\bm{Y})$, and all induced
marginal and conditional laws.

In the limit where the sequence $\bm{Y}$ becomes independent and identically
distributed (i.i.d.), learning the parameters becomes impossible due to
standard identifiability issues for mixture models : the distribution of
$Y_{1}$ may be decomposed in many ways as a convex combination of
multinomials. This i.i.d. limit can be approached in three ways:

  1. 1.

$p\approx 0$ or $q\approx 0$, and thus the chain $\bm{X}$ passes long periods
of time in one of the two states;

  2. 2.

the transition matrix $Q$ is nearly singular, so that $\bm{X}$ itself is
almost i.i.d; this is the case if $\lvert 1-p-q\rvert\approx 0$;

  3. 3.

the emission distributions are close to each other: $\lVert
f_{0}-f_{1}\rVert\approx 0$, where $\lVert\cdot\rVert$ denotes the usual
Euclidean norm, $\lVert f\rVert^{2}=\sum\lvert f(k)\rvert^{2}$.

We adopt a minimax point of view and encapsulate all the above scenarios
within the class of parameters defined, for some $\delta,\epsilon\in(0,1)$ and
some $\zeta>0$, by

$\Theta=\Theta(\delta,\epsilon,\zeta)=\\{\theta\;:p,q\geq\delta,\;\lvert
1-p-q\rvert\geq\epsilon,\>\lVert f_{0}-f_{1}\rVert\geq\zeta\\}.$

Introduce also the subset

$\Theta_{L}=\Theta_{L}(\delta,\epsilon,\zeta)=\Theta\cap\\{1-\lvert
1-p-q\rvert\geq L\\}.$

######  Remark 1.

Note that $1-\lvert 1-p-q\rvert$ is the absolute spectral gap of the chain
$\bm{X}$, and hence the mixing time of the chain can be upper bounded
uniformly in $\Theta_{L}$ since the state space has size 2 (so the chain is
automatically reversible). Here $L$ may be arbitrarily small but we think of
it as _fixed_ , in contrast to $\delta$, $\epsilon$ and $\zeta$ which are
allowed to depend on $n$. With the introduction of this lower bound we still
allow _one_ of $p,q$ to be vanishingly small (or arbitrarily close – even
equal – to 1), but not both.

######  Remark 2.

If $\zeta$ is too large compared to $1/K$, $\Theta(\delta,\epsilon,\zeta)$ may
be too small to be an interesting parameter space. To avoid this and ensure
that $\Theta(\delta,\epsilon,\zeta)$ contains near uniform density pairs, we
assume a mild compatibility condition: that

$\zeta\leq\frac{\sqrt{2\lfloor K/2\rfloor}}{4K}.$ (3)

##  3 Main results

To avoid a label-switching issue discussed in the next section we assume that
$f_{0}-f_{1}$ lies in some specified half-plane. Our main result is the
following.

######  Theorem 1.

There exist an estimator
$\hat{\theta}=(\hat{p},\hat{q},\hat{f}_{0},\hat{f}_{1})$ and a constant
$C=C(K,L)>0$ such that for all $1\leq x^{2}\leq
n\delta^{2}\epsilon^{4}\zeta^{6}$,

$\displaystyle\sup_{\theta\in\Theta_{L}}\mathbb{P}_{\theta}\Big{(}\max(\lvert\hat{p}-p\rvert,\lvert\hat{q}-q\rvert)>\frac{Cx}{\sqrt{n\delta^{2}\epsilon^{4}\zeta^{6}}}\max(\delta,\epsilon\zeta)\Big{)}\leq
e^{-x^{2}},$
$\displaystyle\sup_{\theta\in\Theta_{L}}\mathbb{P}_{\theta}\Big{(}\max(\lVert\hat{f}_{0}-f_{0}\rVert,\lVert\hat{f}_{1}-f_{1}\rVert)>\frac{Cx}{\sqrt{n\delta^{2}\epsilon^{4}\zeta^{4}}}\Big{)}\leq
e^{-x^{2}}.$

Grant condition (3). There exist constants $c=c(K)>0$ and $\epsilon_{1}>0$
such that for $\delta\leq 1/6$, $\epsilon\leq\epsilon_{1}$, $L\leq 1/3$ and
$n\delta^{2}\epsilon^{4}\zeta^{6}\geq 1$,

$\displaystyle\inf_{\check{\theta}}\sup_{\theta\in\Theta_{L}}\mathbb{P}_{\theta}\Big{(}\max(\lvert\check{p}-p\rvert,\lvert\check{q}-q\rvert)>\frac{c}{\sqrt{n\delta^{2}\epsilon^{4}\zeta^{6}}}\max(\delta,\epsilon\zeta)\Big{)}\geq
1/4,$
$\displaystyle\inf_{\check{\theta}}\sup_{\theta\in\Theta_{L}}\mathbb{P}_{\theta}\Big{(}\max(\lVert\check{f}_{0}-f_{0}\rVert,\lVert\check{f}_{1}-f_{1}\rVert)>\frac{c}{\sqrt{n\delta^{2}\epsilon^{4}\zeta^{4}}}\Big{)}\geq
1/4,$

where the infima are over all estimators
$\check{\theta}=(\check{p},\check{q},\check{f}_{0},\check{f}_{1}).$

The estimator $\hat{\theta}$ is built via plug-in from those constructed later
in Theorem 2. Note that the maxima are genuinely required in the lower bounds:
in the extreme case where $p$ is close to zero and $q$ is close to 1, one has
many samples with $X_{i}=0$ and few with $X_{i}=1$, so that $p$ and $f_{0}$
are easier to estimate accurately than $q$ and $f_{1}$.

We deduce immediately the sample complexity for learning the parameters. We do
not seek sharp dependence on $K$ in the bounds because we believe our results
can be extended to the nonparametric setting, which we leave for further work.

######  Corollary 1.

Fix a target error magnitude $E>0$ and a probability level $\alpha>0$. For the
same estimators as in Theorem 1, there exists a constant $C=C(K,L)$ such that
for any $\theta\in\Theta_{L}$ we have

$\displaystyle
n\geq\frac{\log(1/\alpha)}{\delta^{2}\epsilon^{4}\zeta^{6}}\max\Big{(}\frac{C\delta^{2}}{E^{2}},\frac{C\epsilon^{2}\zeta^{2}}{E^{2}},1\Big{)}\quad$
$\displaystyle\implies\quad\mathbb{P}_{\theta}(\max(\lvert\hat{p}-p\rvert,\lvert\hat{q}-q\rvert)>E)\leq\alpha,$
$\displaystyle
n\geq\frac{\log(1/\alpha)}{\delta^{2}\epsilon^{4}\zeta^{4}}\max\Big{(}\frac{C}{E^{2}},\frac{1}{\zeta^{2}}\Big{)}\quad$
$\displaystyle\implies\quad\mathbb{P}_{\theta}(\max(\lVert\hat{f_{0}}-f_{0}\rVert,\lVert\hat{f}_{1}-f_{1}\rVert)>E)\leq\alpha.$
Conversely there exists a constant $c=c(K)>0$ such that for all $0<E\leq c(K)$
and for any estimator
$\check{\theta}=(\check{p},\check{q},\check{f}_{0},\check{f}_{1})$ there
exists $\theta\in\Theta_{L}$ such that $\displaystyle
n\leq\frac{c^{2}\max(\delta^{2},\epsilon^{2}\zeta^{2})}{E^{2}\delta^{2}\epsilon^{4}\zeta^{6}}\quad$
$\displaystyle\implies\quad\mathbb{P}_{\theta}(\max(\lvert\check{p}-p\rvert,\lvert\check{q}-q\rvert)>E)\geq
1/4,$ $\displaystyle
n\leq\frac{c^{2}}{E^{2}\delta^{2}\epsilon^{4}\zeta^{4}}\quad$
$\displaystyle\implies\quad\mathbb{P}_{\theta}(\max(\lVert\check{f}_{0}-f_{0}\rVert,\lVert\check{f}_{1}-f_{1}\rVert)>E)\geq
1/4.$

Note that to apply Theorem 1 for the lower bounds we would initially also need
$n\geq(\delta^{2}\epsilon^{4}\zeta^{6})^{-1}$ but by monotonicity — i.e. the
fact that any measurable function of $(Y_{1},\dots,Y_{n})$ is also a
measurable function of $(Y_{1},\dots,Y_{N})$ for $N\geq n$ — the restriction
can be removed.

Let us sketch the main ideas behind the proof of Theorem 1. The full proof is
deferred to Section 8, along with all other proofs for this article.

The minimax upper bounds are obtained by producing an estimator that attains
the bounds. Building on the work of [6, 18] we know that $\theta$ is
identifiable from $p_{\theta}^{(3)}$, and we propose a reparametrisation of
the model to simplify the analysis. Indeed, motivated by a desire to simplify
the expression for $p_{\theta}^{(3)}$ (see equations 9 and 10 in Section 4),
we introduce new parameters $\phi,\psi$ and we show in Proposition 1 that
$\lVert
p_{\theta(\phi,\psi)}^{(3)}-p_{\theta(\tilde{\phi},\tilde{\psi})}^{(3)}\rVert$
is equivalent to $\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})$, where $\rho$ is
defined in the proposition and can be seen as the “natural” statistical
distance of the problem (see below). Then, we leverage that $p_{\theta}^{(3)}$
can be estimated in Euclidean distance at the parametric rate $n^{-1/2}$ by
the empirical estimator $\hat{p}_{n}^{(3)}$ defined in Section 5, Lemma 1.
This suggests that solving for
$(\hat{\phi},\hat{\psi})\in\operatorname*{arg\,min}_{\phi,\psi}\lVert
p_{\theta(\phi,\psi)}^{(3)}-\hat{p}_{n}^{(3)}\rVert$ will give a good
estimator $(\hat{\phi},\hat{\psi})$ for ($\phi,\psi$). By standard
calculations and using the equivalence between
$\|p_{\theta(\phi,\psi)}^{(3)}-p_{\theta(\tilde{\phi},\tilde{\psi})}^{(3)}\|$
and $\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})$ derived in Proposition 1, we
obtain bounds on maximum risk of such $(\hat{\phi},\hat{\psi})$ for estimating
$(\phi,\psi)$ in Theorem 2. Finally, the upper bounds for the original
parameters in Theorem 1 are obtained by taking
$\hat{\theta}=\theta(\hat{\phi},\hat{\psi})$.

Incidentally, we remark that the parameterization $(\phi,\psi)$ turns out to
be of special interest: the components of $\phi$ determine how close the
sequence $\bm{Y}$ is to being i.i.d in an interpretable way (see Section 4),
and the parameter $\psi$ is related to the stationary distribution of the
sequence $\bm{Y}$. For this reason, we also establish minimax bounds for the
estimation of $\phi$ and $\psi$ themselves in Theorems 2 and 3.

The minimax lower bounds are obtained by an argument à la Le Cam. In
particular, it is a famous result of Le Cam [26, 40] that the minimax rate
(under quadratic loss) of estimating a functional $g:\Theta\to\mathbb{R}$ is
always greater than the maximum value that $\lvert
g(\theta)-g(\tilde{\theta})\rvert^{2}$ can take for
$\theta,\tilde{\theta}\in\Theta$ under the constraint that
$K(p_{\theta}^{(n)};p_{\tilde{\theta}}^{(n)})\leq c$, where
$K(p_{\theta}^{(n)};p_{\tilde{\theta}}^{(n)})$ denotes the Kullback-Leibler
(KL) divergence between the laws of $(Y_{1},\dots,Y_{n})$ under parameters
$\theta$ and $\tilde{\theta}$, and $0<c<1$ is a small positive constant (see
Lemma 2 for the precise formulation we use). Understanding bounds on $\lvert
g(\theta)-g(\tilde{\theta})\rvert$ in terms of bounds on
$K(p_{\theta}^{(n)};p_{\tilde{\theta}}^{(n)})$ is also sufficient for
obtaining an upper bound on the minimax estimation rate. Since we have
dependent observations, the main difficulty of the proof is to relate
$K(p_{\theta}^{(n)};p_{\tilde{\theta}}^{(n)})$ to a suitable notion of
distance between $\theta$ and $\tilde{\theta}$. A key result is Proposition 2
showing that under mild assumptions
$K(p_{\theta(\phi,\psi)}^{(n)};p_{\theta(\tilde{\phi},\tilde{\psi})}^{(n)})$
is upper bounded by a constant times
$n\rho^{2}(\phi,\psi;\tilde{\phi},\tilde{\psi})$. Then the lower bounds for
$\phi$ (respectively $\psi$) in Theorem 3 are obtained by lower bounding the
value of the optimization problems
$\max\lvert\phi_{j}-\tilde{\phi}_{j}\rvert^{2}$ (respectively
$\max\lvert\psi_{j}-\tilde{\psi}_{j}\rvert^{2}$) subject to
$n\rho^{2}(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq c$ and
$\theta(\phi,\psi),\theta(\tilde{\phi},\tilde{\psi})\in\Theta$ for a small
enough constant $c>0$. Finally, the lower bounds for the original parameters
in the Theorem 1 are essentially deduced from the bounds for ($\phi,\psi$) and
inversion of the parameterization.

##  4 Change of parameterisation

We reparametrise the model in such a way that the i.i.d. limiting cases are
highlighted, by changing variables to $\phi=(\phi_{1},\phi_{2},\phi_{3})$ and
$\psi=(\psi_{1},\psi_{2})$ defined as

$\displaystyle\phi(\theta)=\big{(}\begin{matrix}\frac{q-p}{p+q}&1-p-q&\lVert
f_{0}-f_{1}\rVert\\\
\end{matrix}\big{)},\quad\psi(\theta)=\big{(}\begin{matrix}\frac{qf_{0}+pf_{1}}{p+q}&\frac{f_{0}-f_{1}}{\lVert
f_{0}-f_{1}\rVert}\\\ \end{matrix}\big{)}.$

Here we have separated the scalar parameters $\phi$ from the vector parameters
$\psi$. Defining

$r(\phi)=\tfrac{1}{4}(1-\phi_{1}^{2})\phi_{2}\phi_{3}^{2},$ (4)

it follows from the discussion in Section 2 that the data $\bm{Y}$ is close to
i.i.d. exactly when $r(\phi)\approx 0$. [This is of course true also of other
combinations of the components of $\phi$, but as equation 10 will show,
$r(\phi)$ is the appropriate combination measuring the “distance” to the
i.i.d. case.]

Define

$\displaystyle\Phi=\Phi(\delta,\epsilon,\zeta)=\\{(\phi(\theta),\psi(\theta)):\theta\in\Theta(\delta,\epsilon,\zeta)\\},$
$\displaystyle\Phi_{L}=\Phi_{L}(\delta,\epsilon,\zeta)=\\{(\phi(\theta),\psi(\theta)):\theta\in\Theta_{L}(\delta,\epsilon,\zeta)\\},$

and note that for $(\phi,\psi)\in\Phi$ we have

$-\frac{1-\delta}{1+\delta}\leq\phi_{1}\leq\frac{1-\delta}{1+\delta},\quad\epsilon\leq\lvert\phi_{2}\rvert\leq
1-2\delta,\quad\zeta\leq\phi_{3}\leq\sqrt{2},\quad\lvert
r(\phi)\rvert\geq\delta\epsilon\zeta^{2}/4,$ (5)

while for $(\phi,\psi)\in\Phi_{L}$ we additionally have

$\lvert\phi_{2}\rvert\leq 1-L.$ (6)

######  Remark 3.

When $K=2$, in view of identifiability issues discussed in the next
subsection, $\psi_{2}$ is not needed in the parametrisation, since we may
universally make the choice

$\psi_{2}=\Big{(}\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\Big{)}.$

######  Remark 4.

The parametrisation $\theta\mapsto(\phi,\psi)$ is invertible: we calculate

$\displaystyle p$ $\displaystyle=\tfrac{1}{2}(1-\phi_{2})(1-\phi_{1}),$
$\displaystyle q$ $\displaystyle=\tfrac{1}{2}(1-\phi_{2})(1+\phi_{1}),$
$\displaystyle f_{0}$
$\displaystyle=\psi_{1}-\tfrac{1}{2}\phi_{1}\phi_{3}\psi_{2}+\tfrac{1}{2}\phi_{3}\psi_{2},$
$\displaystyle f_{1}$
$\displaystyle=\psi_{1}-\tfrac{1}{2}\phi_{1}\phi_{3}\psi_{2}-\tfrac{1}{2}\phi_{3}\psi_{2}.$

######  Remark 5.

Suppose $\psi_{1}$ is a probability density function with respect to counting
measure on $\\{1,\dots,K\\}$, $\psi_{2}$ is a function satisfying
$\lVert\psi_{2}\rVert=1$ and $\sum_{k}\psi_{2}(k)=0$, and $\phi$ satisfies
$\lvert\phi_{1}\rvert\leq 1$, $\lvert\phi_{2}\rvert\leq 1$ and $\phi_{3}\geq
0$. Then $(\phi,\psi)$ lies in $\Phi(\delta,\epsilon,\zeta)$ if and only if

$\displaystyle\tfrac{1}{2}(1-\phi_{2})(1-\lvert\phi_{1}\rvert)\geq\delta,\quad\tfrac{1}{2}(1-\phi_{2})(1+\lvert\phi_{1}\rvert)\leq
1,\quad\lvert\phi_{2}\rvert\geq\epsilon,\quad\phi_{3}\geq\zeta,$ (7)
$\displaystyle\psi_{1}(k)-\tfrac{1}{2}\phi_{1}\phi_{3}\psi_{2}(k)-\tfrac{1}{2}\phi_{3}\lvert\psi_{2}(k)\rvert\geq
0,\quad\forall k\leq K.$ (8)

The model (1) is identifiable for the parameter set $\Theta$ only up to
‘label-switching’, since $\bm{Y}$ has the same distribution under the
parameters $(p,q,f_{0},f_{1})$ and $(q,p,f_{1},f_{0})$; in the parametrisation
$(\phi,\psi)$, the distribution of $\bm{Y}$ is the same under
$(\phi_{1},\phi_{2},\phi_{3},\psi_{1},\psi_{2})$ and under
$(-\phi_{1},\phi_{2},\phi_{3},\psi_{1},-\psi_{2})$. However, it was proved in
[6] that aside from this label-switching, the model parameters can be
identified from the law of just three consecutive observations. To that end,
for any integer $m$ denoting by $P_{\theta}^{(m)}$ the law of
$(Y_{1},\dots,Y_{m})$ under parameter $\theta\in\Theta$, and by
$p_{\theta}^{(m)}$ the corresponding density with respect to counting measure
on $\\{1,\dots,K\\}^{m}$, we calculate

$p_{\theta}^{(3)}=\left(\frac{q}{p+q}\right)g\otimes f_{0}\otimes
g+\left(\frac{p}{p+q}\right)h\otimes f_{1}\otimes h,$ (9)

where $g=(1-p)f_{0}+pf_{1}$ and $h=qf_{0}+(1-q)f_{1}$, and where $\otimes$
denotes the tensor product so that

$(f\otimes g\otimes
h)(a,b,c)=f(a)g(b)h(c),\quad(a,b,c)\in\\{1,\dots,K\\}^{3}.$

In the $(\phi,\psi)$ parametrisation, writing just $p^{(3)}_{\phi,\psi}$ for
$p^{(3)}_{\theta(\phi,\psi)}$ in a slight abuse of notation, we have

$p^{(3)}_{\phi,\psi}=\psi_{1}\otimes\psi_{1}\otimes\psi_{1}+r(\phi)\big{(}\psi_{2}\otimes\psi_{2}\otimes\psi_{1}+\psi_{1}\otimes\psi_{2}\otimes\psi_{2}\big{)}\\\
+\phi_{2}r(\phi)\psi_{2}\otimes\psi_{1}\otimes\psi_{2}-\phi_{1}\phi_{2}\phi_{3}r(\phi)\psi_{2}\otimes\psi_{2}\otimes\psi_{2},$
(10)

where we recall the notation
$r(\phi)=\tfrac{1}{4}(1-\phi_{1}^{2})\phi_{2}\phi_{3}^{2}$.

We define a statistical distance $\rho$ directly on the parameter space $\Phi$
which is equivalent to the Euclidean distance between the densities
$p^{(3)}_{\phi,\psi}$ and $p^{(3)}_{\tilde{\phi},\tilde{\psi}}$. The function
$\rho$ is not a true metric because it may not satisfy the triangle inequality
and because, due to the identifiability issues reflected by the appearance of
factors of $\operatorname{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)$ in
its definition, we may have $\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})=0$ with
$(\phi,\psi)\neq(\tilde{\phi},\tilde{\psi})$. Here $\langle\cdot,\cdot\rangle$
denotes the Euclidean inner product on $\mathbb{R}^{K}$, $\langle
f,g\rangle=\sum_{i=1}^{K}f(k)g(k).$

######  Proposition 1.

For $r$ as in equation 4 define $m$ by

$m(\phi)=(r(\phi),\phi_{2}r(\phi),\phi_{1}\phi_{2}\phi_{3}r(\phi)),$ (11)

and define

$\begin{split}\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})=\max\big{\\{}\lvert
m_{1}(\phi)-m_{1}(\tilde{\phi})\rvert,\,\lvert
m_{2}(\phi)-m_{2}(\tilde{\phi})\rvert,\,\lvert
m_{3}(\phi)-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot
m_{3}(\tilde{\phi})\rvert,\\\
\lVert\psi_{1}-\tilde{\psi}_{1}\rVert,\,\max\\{\lvert m_{1}(\phi)\rvert,\lvert
m_{1}(\tilde{\phi})\rvert\\}\cdot\lVert\psi_{2}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}\rVert\big{\\}}.\end{split}$
(12)

There exist constants $c_{1},c_{2}>0$ (which depend on $K$) such that for all
$(\phi,\psi),(\tilde{\phi},\tilde{\psi})\in\bigcup_{\delta,\epsilon,\zeta}\Phi(\delta,\epsilon,\zeta)$
we have

$c_{1}\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert\leq
c_{2}\rho(\phi,\psi;\tilde{\phi},\tilde{\psi}).$

Optimal estimation rates can be obtained if we adequately understand the
Kullback–Leibler divergence between distributions with different parameters.
The Kullback–Leibler divergence between $P^{(n)}_{\theta(\phi,\psi)}$ and
$P^{(n)}_{\theta(\tilde{\phi},\tilde{\psi})}$ can be related to the
statistical distance $\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})$ in a
neighbourhood of the independent subcase.

######  Proposition 2.

Assume there exists $c\in(0,1)$ such that
$\min(f_{0},f_{1},\tilde{f}_{0},\tilde{f}_{1})\geq c$. There exist constants
$C,\epsilon_{0}>0$ depending only on $c$ such that if
$\max(|\phi_{2}|,|\tilde{\phi}_{2}|)\leq\epsilon_{0}$, then with $\rho$ as in
equation 12,

$K(P_{\theta(\phi,\psi)}^{(n)},P_{\theta(\phi,\psi)}^{(n)})\leq
Cn\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})^{2}.$

We note that only the lower bound on $\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert$ in Proposition
1 is used in our paper (it is used in proving Theorem 2). The upper bound on
$\lVert p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert$ is
still of interest as it establishes the tightness (up to constants) of the
corresponding lower bound, thereby proving the equivalence between $\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert$ and
$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})$ and showing that $\rho$ is a
natural and adequate statistical metric for this problem. Furthermore, in
combination with Proposition 2, Pinsker’s inequality, and the fact that all
norms on the set $\\{1,\dots,K\\}^{3}$ are equivalent, it shows that whenever
$\max(|\phi_{2}|,|\tilde{\phi}_{2}|)$ is small enough,

$K(P_{\theta(\phi,\psi)}^{(n)},P_{\theta(\phi,\psi)}^{(n)})\leq
C^{\prime}n\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert^{2}\leq
C^{\prime\prime}nK(P_{\theta(\phi,\psi)}^{(3)},P_{\theta(\phi,\psi)}^{(3)}),$

for constants $C^{\prime},C^{\prime\prime}>0$, once again highlighting the
prominent role of the law of 3 consecutive observations in HMM modeling, and
illustrating that optimal estimators (up to numerical constants) can be built
solely on the basis of the empirical distribution of blocks of 3 consecutive
observations. This shows that as long as the chain $\bm{Y}$ is not “too
dependent”, it behaves almost as if we had observed i.i.d. blocks of 3
consecutive observations (in which case we would have that
$K(P_{\theta(\phi,\psi)}^{(n)},P_{\theta(\phi,\psi)}^{(n)})=(n/3)K(P_{\theta(\phi,\psi)}^{(3)},P_{\theta(\phi,\psi)}^{(3)})$,
for all $n$ divisible by $3$).

##  5 Upper bounds

We obtain the following upper bounds for estimating $\phi$ and $\psi$. Since
we are studying limits as the quantities of interest become small, the
relative risk may be of as much interest as the absolute risk, and we provide
bounds for both quantities. The bounds demonstrate that learning model
parameters is possible in the regime where $n$ is large enough in relation to
$\delta$, $\epsilon$ and $\zeta$. Observe firstly that estimation of $p^{(3)}$
is possible at a parametric rate.

######  Lemma 1.

Define the empirical estimator $\hat{p}^{(3)}_{n}:\\{1,\dots,K\\}^{n}\to[0,1]$
by

$\hat{p}^{(3)}_{n}(a,b,c)=\frac{1}{n}\sum_{i=1}^{n-2}\mathbbm{1}\\{Y_{i}=a,\leavevmode\nobreak\
Y_{i+1}=b,\leavevmode\nobreak\ Y_{i+2}=c\\}.$ (13)

Then for some constant $C=C(K,L)$ and any $x\geq 1$

$\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{(\phi,\psi)}(\lVert\hat{p}^{(3)}-p^{(3)}\rVert\geq
Cx/\sqrt{n})\leq e^{-x^{2}}.$

######  Theorem 2.

Assume $\Phi_{L}$ is non-empty and let $\hat{\phi},\hat{\psi}$ be any
measurable functions satisfying, for $\hat{p}^{(3)}_{n}$ as in equation 13,

$\lVert p^{(3)}_{\hat{\phi},\hat{\psi}}-\hat{p}_{n}^{(3)}\rVert\leq
2\inf_{(\tilde{\phi},\tilde{\psi})\in\Phi_{L}}\lVert
p^{(3)}_{\tilde{\phi},\tilde{\psi}}-\hat{p}^{(3)}_{n}\rVert.$

There exists a constant $C=C(K,L)>0$ such that the following hold.

  1. 1.

Assume $1\leq x^{2}\leq n\delta^{2}\epsilon^{4}\zeta^{6}$. Then

$\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\Big{\lvert}\frac{1-\hat{\phi}_{1}^{2}}{1-\phi_{1}^{2}}-1\Big{\rvert}^{2}\geq\frac{2Cx^{2}}{n\delta^{2}\epsilon^{4}\zeta^{6}}\Big{)}\\\
\leq\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\min(\lvert\hat{\phi}_{1}-\phi_{1}\rvert,\lvert\hat{\phi}_{1}+\phi_{1}\rvert)^{2}\geq\frac{Cx^{2}}{n\epsilon^{4}\zeta^{6}}\Big{)}\leq
e^{-x^{2}}.$

  2. 2.

Assume $1\leq x^{2}\leq n\delta^{2}\epsilon^{2}\zeta^{4}$. Then

$\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\Big{\lvert}\frac{\hat{\phi}_{2}}{\phi_{2}}-1\Big{\rvert}^{2}\geq
C\frac{x^{2}}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}\\\
\leq\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{2}-\phi_{2}\rvert^{2}\geq
C\frac{x^{2}}{n\delta^{2}\epsilon^{2}\zeta^{4}}\Big{)}\leq e^{-x^{2}}.$

  3. 3.

Assume $1\leq x^{2}\leq n\delta^{2}\epsilon^{4}\zeta^{6}$. Then

$\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\Big{\lvert}\frac{\hat{\phi}_{3}}{\phi_{3}}-1\Big{\rvert}^{2}\geq
C\frac{x^{2}}{n\delta^{2}\epsilon^{4}\zeta^{6}}\Big{)}\\\
\leq\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{3}-\phi_{3}\rvert^{2}\geq
C\frac{x^{2}}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}\leq e^{-x^{2}}.$

  4. 4.

Assume $1\leq x^{2}\leq n$. Then

$\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\lVert\hat{\psi}_{1}-\psi_{1}\rVert^{2}\geq\frac{Cx^{2}}{n}\Big{)}\leq
e^{-x^{2}}.$

  5. 5.

Assume $1\leq x^{2}\leq n\delta^{2}\epsilon^{2}\zeta^{4}$ and $K>2$. Then

$\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\min\big{(}\lVert\hat{\psi}_{2}-\psi_{2}\rVert^{2},\lVert\hat{\psi}_{2}+\psi_{2}\rVert^{2}\big{)}\geq\frac{Cx^{2}}{n\delta^{2}\epsilon^{2}\zeta^{4}}\Big{)}\leq
e^{-x^{2}}.$

Recall that estimating $\psi_{2}$ is unnecessary when $K=2$ (see Remark 3).
Note that the absolute loss in each case is bounded, and one can deduce that
the bounds for $\phi_{2}$ and for $\psi$ hold without an upper bound on $x$,
with $e^{-x^{2}}$ on the right replaced by zero (for $C$ large enough).

##  6 Lower bounds

We prove lower bounds, matching the previous upper bounds in a suitable regime
and demonstrating the impossibility of learning model parameters when $n$ is
not large enough in relation to $\delta$, $\epsilon$ and $\zeta$. The
particular value $1/4$ on the right sides in the following is not essential:
what is important is that the probabilities are bounded away from zero. The
lower bounds over $\Phi_{L}$ remain true over the larger set $\Phi$.

######  Theorem 3.

Grant the compatibility condition (3). There exist constants $c=c(K)>0$ and
$\epsilon_{0}>0$ such that whenever $\epsilon\leq\epsilon_{0}$, $\delta\leq
1/6$ and $L\leq 1/3$ the following hold. [The infima are over all estimators,
i.e. all measurable functions of the data $(Y_{1},\dots,Y_{n})$.]

  1. 1.

Assume $n\delta^{2}\epsilon^{4}\zeta^{6}\geq 1$. Then

$\inf_{\hat{\phi}_{1}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\min(\lvert\hat{\phi}_{1}-\phi_{1}\rvert^{2},\lvert\hat{\phi}_{1}+\phi_{1}\rvert^{2})\geq\frac{c}{n\epsilon^{4}\zeta^{6}}\Big{)}\\\
\geq\inf_{\hat{\phi}_{1}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\Big{\lvert}\frac{1-\tilde{\phi}_{1}^{2}}{1-\phi_{1}^{2}}-1\Big{\rvert}^{2}\geq\frac{2c}{n\delta^{2}\epsilon^{4}\zeta^{6}}\Big{)}\geq
1/4.$

  2. 2.

Assume $n\delta^{2}\epsilon^{4}\zeta^{4}\geq 1$. Then

$\inf_{\hat{\phi}_{2}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{2}-\phi_{2}\rvert^{2}\geq\frac{c}{n\delta^{2}\epsilon^{2}\zeta^{4}}\Big{)}\\\
\geq\inf_{\hat{\phi}_{2}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\Big{\lvert}\frac{\hat{\phi}_{2}}{\phi_{2}}-1\Big{\rvert}^{2}\geq\frac{c}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}\geq
1/4.$

  3. 3.

Assume $n\delta^{2}\epsilon^{4}\zeta^{6}\geq 1$. Then

$\inf_{\hat{\phi}_{3}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{3}-\phi_{3}\rvert^{2}\geq\frac{c}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}\\\
\geq\inf_{\hat{\phi}_{3}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\Big{\lvert}\frac{\hat{\phi}_{3}}{\phi_{3}}-1\Big{\rvert}^{2}\geq\frac{c}{n\delta^{2}\epsilon^{4}\zeta^{6}}\Big{)}\geq
1/4.$

  4. 4.

For any $n,$ $\delta$, $\epsilon$ and $\zeta$,

$\inf_{\hat{\psi}_{1}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\lVert\hat{\psi}_{1}-\psi_{1}\rVert^{2}\geq\frac{c}{n}\Big{)}\geq
1/4.$

  5. 5.

Assume $n\delta^{2}\epsilon^{2}\zeta^{4}\geq 1$ and $K>2$. Then

$\inf_{\hat{\psi}_{2}}\sup_{(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)}\mathbb{P}_{\phi,\psi}\Big{(}\min(\lVert\hat{\psi}_{2}-\psi_{2}\rVert,\lVert\hat{\psi}_{2}+\psi_{2}\rVert)^{2}\geq\frac{c}{n\delta^{2}\epsilon^{2}\zeta^{4}}\Big{)}\geq
1/4.$

##  7 Conclusions and future directions

In this work we have quantified the impact on learnability of approaching the
i.i.d. boundary within the set of parameters of a hidden Markov model. The
limiting cases occur when one hidden state is absorbing, when the underlying
Markov chain becomes a sequence of independent variables, or when the emission
distributions are equal. We have proved both upper and lower bounds for the
estimation rates of the parameters in a hidden Markov models with two hidden
states and finitely many possible outcomes. Our results characterize the
frontier in the parameter space between learnable and unlearnable parameters
and quantify how large the sample has to be in order to get estimators with
prescribed error with high probability.

Some tricky regions of the parameter space are not fully captured in the upper
and lower bounds. Specifically, the condition on $n$ in the lower bound for
estimating $\phi_{2}$ differs by a factor of $\epsilon^{2}$ from the
corresponding condition in the upper bound. Also, in the upper bound for
$\phi_{1}$, we do not describe the precise estimation behaviour in the region
$n\delta^{2}\epsilon^{4}\zeta^{6}<x^{2}<n\epsilon^{4}\zeta^{6}$: in this range
we can obtain something by applying the bound with
$y^{2}=\min(x^{2},n\delta^{2}\epsilon^{4}\zeta^{6})$ but we cannot expect that
this gives the correct dependence on $x$. [There is no issue in the region
$x^{2}\geq n\epsilon^{4}\zeta^{6}$ since we may replace the bound $e^{-x^{2}}$
with zero, similarly to the comment after the theorem regarding $\phi_{2}$ and
$\psi$.] A similar gap exists for estimating $\phi_{3}$. Our results already
work for a wide range of parameters, and extending to the few remaining cases
is an interesting issue for future research.

Regarding the upper bounds, we analysed a minimum distance estimator for
theoretical convenience, and we think the same upper bounds should hold for
more practical estimators (for example empirical least squares estimators and
tensor-based methods). Our proof method relies on the fact that the two steps
of estimating $p^{(3)}$ and of estimating, given $p^{(3)}$, the HMM parameters
themselves, decouple. This is because, with good mixing properties for the
Markov chain, estimation of $p^{(3)}$ can be done uniformly at a rate not
depending on the HMM parameters (Lemma 1). When the spectral gap is small the
underlying Markov chain mixes slowly, spending long periods remaining in
whichever of the two states it is in, so that estimation of $p^{(3)}$ becomes
hard for parameters for which there is small spectral gap. These are not the
same parameters for which recovering the HMM parameters given $p^{(3)}$ is
most difficult, and so to obtain accurate rates without a spectral gap
requires carefully addressing the two steps simultaneously, which is beyond
the scope of the paper (we could obtain a suboptimal rate using the current
methods just with careful tracking of the spectral gap, since it is lower
bounded by $1-2\delta$, but upper and lower bounds obtained in this way
mismatch by a factor of $\delta$). Note the above arguments explain the
requirement for a spectral gap, not an absolute spectral gap; we believe our
results will in fact hold in the near-periodic case when the spectral gap is
close to 2 and the absolute spectral gap is close to zero, but this would
require some extra technical calculations in the proof of Lemma 1.

We believe similar results hold with more than two hidden states and with
arbitrary nonparametric emission distributions. Investigation of the
fundamental limits for learning more general HMMs and misspecified modelling
will be the object of further work. Developments of our findings for
clustering, multiple testing and sparse settings will also be the object of
further work, and all will depend fundamentally on the results obtained here.

On the practical side, usual estimation algorithms can be expected to exhibit
bad computational behaviour when the unknown true parameters lie near the
learning frontier. We have not tackled this issue here and we believe it
merits substantive investigation, both in building robust algorithms and in
detecting the poor performance in the problematic region. This last question
is interesting both from a practical and a theoretical point of view.

##  8 Proofs

###  8.1 Proof of Proposition 1

Recall the definition (11) of $m$ as

$m(\phi)=(r(\phi),\phi_{2}r(\phi),\phi_{1}\phi_{2}\phi_{3}r(\phi)),\quad
r(\phi)=\tfrac{1}{4}(1-\phi_{1}^{2})\phi_{2}\phi_{3}^{2}.$

We write $\tilde{m}=m(\tilde{\phi})$, and we write $\psi_{ijk}$ for
$\psi_{i}\otimes\psi_{j}\otimes\psi_{k}$ and $\tilde{\psi}_{ijk}$ for
$\tilde{\psi}_{i}\otimes\tilde{\psi}_{j}\otimes\tilde{\psi}_{k}$. Then from
equation 10 we have

$\begin{split}p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}=(\psi_{111}-\tilde{\psi}_{111})+\\{m_{1}(\psi_{221}+\psi_{122})-\tilde{m}_{1}(\tilde{\psi}_{221}+\tilde{\psi}_{122})\\}\\\
+\\{m_{2}\psi_{212}-\tilde{m}_{2}\tilde{\psi}_{212}\\}-\\{m_{3}\psi_{222}-\tilde{m}_{3}\tilde{\psi}_{222}\\}.\end{split}$
(14)

Recalling that $\langle\cdot,\cdot\rangle$ denotes the Euclidean inner product
on $\mathbb{R}^{K}$, we have $\langle\psi_{1},1\rangle=1$,
$\langle\psi_{2},1\rangle=0$, $\lVert\psi_{2}\rVert=1$ and $\lVert
1\rVert=K^{1/2}$. Let $\langle\cdot,\cdot\rangle$ also denote the Euclidean
inner product on $\mathbb{R}^{K\times K\times K},$ wherein for functions
$f_{i},\tilde{f}_{i}:\\{1,\dots,K\\}\to\mathbb{R},\leavevmode\nobreak\ i\leq
3$ we have

$\langle f_{1}\otimes f_{2}\otimes
f_{3},\tilde{f}_{1}\otimes\tilde{f}_{2}\otimes\tilde{f}_{3}\rangle=\langle
f_{1},\tilde{f}_{1}\rangle\langle f_{2},\tilde{f}_{2}\rangle\langle
f_{3},\tilde{f}_{3}\rangle.$

#### Lower bounding $\lVert
p^{(3)}_{\phi,\psi}-p^{(3)}_{\tilde{\phi},\tilde{\psi}}\rVert$

For any function $f:\\{1,\dots,K\\}\to\mathbb{R}$, we have

$\langle p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},f\otimes
1\otimes 1\rangle=\langle\psi_{111}-\tilde{\psi}_{111},f\otimes 1\otimes
1\rangle=\langle\psi_{1}-\tilde{\psi}_{1},f\rangle.$

Then

$\displaystyle\lVert\psi_{1}-\tilde{\psi}_{1}\rVert$
$\displaystyle=\sup_{\lVert
f\rVert=1}\lvert\langle\psi_{1}-\tilde{\psi}_{1},f\rangle\rvert$
$\displaystyle=\sup_{\lVert f\rVert=1}\lvert\langle
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},f\otimes 1\otimes
1\rangle\rvert$ $\displaystyle\leq\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert\sup_{\lVert
f\rVert=1}\lVert f\otimes 1\otimes 1\rVert=K\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert,$ (15)

and similarly,

$\displaystyle\langle
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},1\otimes f\otimes
f\rangle$ $\displaystyle=\langle\psi_{111}-\tilde{\psi}_{111},1\otimes
f\otimes f\rangle+\langle
m_{1}\psi_{122}-\tilde{m}_{1}\tilde{\psi}_{122},1\otimes f\otimes f\rangle$
$\displaystyle=\langle\psi_{1}-\tilde{\psi}_{1},f\rangle^{2}+m_{1}\langle\psi_{2},f\rangle^{2}-\tilde{m}_{1}\langle\tilde{\psi}_{2},f\rangle^{2}.$
(16)

Choosing
$f=\psi_{2}+\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}$
(with the convention that $\operatorname{sgn}(0)=+1$), we observe that

$\langle\psi_{2},f\rangle=1+|\langle\psi_{2},\tilde{\psi}_{2}\rangle|=\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\langle\tilde{\psi}_{2},f\rangle.$

In particular we note that
$\langle\psi_{2},f\rangle^{2}=\langle\tilde{\psi}_{2},f\rangle^{2}=(1+|\langle\psi_{2},\tilde{\psi}_{2}\rangle|)^{2}\geq
1$. Since also $\lVert
f\rVert^{2}=2+2\lvert\langle\psi_{2},\tilde{\psi}_{2}\rangle\rvert\leq 4$,
returning to (16) we observe that

$\displaystyle\lvert m_{1}-\tilde{m}_{1}\rvert$ $\displaystyle\leq\lVert
f\rVert^{2}\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+\lVert 1\otimes f\otimes
f\rVert\lVert p^{(3)}_{\phi,\psi}-p^{(3)}_{\tilde{\phi},\tilde{\psi}}\rVert$
$\displaystyle\leq 4\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+4K^{1/2}\lVert
p^{(3)}_{\phi,\psi}-p^{(3)}_{\tilde{\phi},\tilde{\psi}}\rVert$
$\displaystyle\leq 4(K^{7/2}+K^{1/2})\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert,$ (17)

where for the last line we have used equation 15 and the fact that $\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert^{2}\leq K^{3}$.
We continue by considering the expression $f\otimes 1\otimes f$, for which we
have

$\displaystyle\langle
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},f\otimes 1\otimes
f\rangle$ $\displaystyle=\langle\psi_{111}-\tilde{\psi}_{111},f\otimes
1\otimes f\rangle+\langle
m_{2}\psi_{212}-\tilde{m}_{2}\tilde{\psi}_{212},f\otimes 1\otimes f\rangle$
$\displaystyle=\langle\psi_{1}-\tilde{\psi}_{1},f\rangle^{2}+m_{2}\langle\psi_{2},f\rangle^{2}-\tilde{m}_{2}\langle\tilde{\psi}_{2},f\rangle^{2}$

Recognising symmetry with equation 16, we again choose
$f=\psi_{2}+\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}$
to obtain

$\lvert m_{2}-\tilde{m}_{2}\rvert\leq 4(K^{7/2}+K^{1/2})\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert.$ (18)

Finally, considering the expression $f\otimes f\otimes f$, we observe that

$\begin{split}\langle
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},f\otimes f\otimes
f\rangle&=\langle\psi_{111}-\tilde{\psi}_{111},f\otimes f\otimes
f\rangle+\langle
m_{1}(\psi_{221}+\psi_{122})-\tilde{m}_{1}(\tilde{\psi}_{221}+\tilde{\psi}_{122}),f\otimes
f\otimes f\rangle\\\ &\quad+\langle
m_{2}\psi_{212}-\tilde{m}_{2}\tilde{\psi}_{212},f\otimes f\otimes
f\rangle-\langle m_{3}\psi_{222}-\tilde{m}_{3}\tilde{\psi}_{222},f\otimes
f\otimes f\rangle.\end{split}$

In other words,

$\begin{split}\langle
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},f\otimes f\otimes
f\rangle&=\langle\psi_{1}-\tilde{\psi}_{1},f\rangle^{3}+2\big{(}m_{1}\langle\psi_{2},f\rangle^{2}\langle\psi_{1},f\rangle-\tilde{m}_{1}\langle\tilde{\psi}_{2},f\rangle^{2}\langle\tilde{\psi}_{1},f\rangle\big{)}\\\
&\quad+\big{(}m_{2}\langle\psi_{2},f\rangle^{2}\langle\psi_{1},f\rangle-\tilde{m}_{2}\langle\tilde{\psi}_{2},f\rangle^{2}\langle\tilde{\psi}_{1},f\rangle\big{)}-\big{(}m_{3}\langle\psi_{2},f\rangle^{3}-\tilde{m}_{3}\langle\tilde{\psi}_{2},f\rangle^{3}\big{)}.\end{split}$

Once more choosing
$f=\psi_{2}+\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}$,
we obtain (recall that by construction $\lVert f\rVert\leq 2$,
$1\leq\langle\psi_{2},f\rangle^{2}=\langle\tilde{\psi}_{2},f\rangle^{2}\leq
4$, and also
$\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\langle\psi_{2},f\rangle=\langle\tilde{\psi}_{2},f\rangle$)

$\displaystyle\lvert
m_{3}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{m}_{3}\rvert$
$\displaystyle\leq 8\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{3}+8\lVert
p_{\phi,\psi}^{(3)}-p_{\phi,\psi}^{(3)}\rVert$
$\displaystyle\quad+8\big{\lvert}m_{1}\langle\psi_{1},f\rangle-\tilde{m}_{1}\langle\tilde{\psi}_{1},f\rangle\big{\rvert}+4\big{\lvert}m_{2}\langle\psi_{1},f\rangle-\tilde{m}_{2}\langle\tilde{\psi}_{1},f\rangle\big{\rvert}.$

For some constant $C=C(K)$ we have

$\displaystyle\big{\lvert}m_{1}\langle\psi_{1},f\rangle-\tilde{m}_{1}\langle\tilde{\psi}_{1},f\rangle\big{\rvert}$
$\displaystyle\leq\lvert\langle\psi_{1},f\rangle\rvert\big{\lvert}m_{1}-\tilde{m}_{1}\big{\rvert}+\lvert\tilde{m}_{1}\rvert\lvert\langle\psi_{1}-\tilde{\psi}_{1},f\rangle\rvert$
$\displaystyle\leq
2\lVert\psi_{1}\rVert\big{\lvert}m_{1}-\tilde{m}_{1}\big{\rvert}+2\lvert\tilde{m}_{1}\rvert\lVert\psi_{1}-\tilde{\psi}_{1}\rVert$
$\displaystyle\leq C\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert,$

where for the last line we have used equations 15 and 17 and that
$\lVert\psi_{1}\rVert\leq K^{1/2}$ and
$\lvert\tilde{m}_{1}\rvert\leq\tilde{\phi}_{3}^{2}/4\leq\lVert\tilde{f}_{0}-\tilde{f}_{1}\rVert^{2}/4\leq
K/4$.

Similarly, using equation 18 and the fact that $\lvert\tilde{m}_{2}\rvert$ is
suitably bounded, we have for some $C=C(K)$

$\displaystyle\big{\lvert}m_{2}\langle\psi_{1},f\rangle-\tilde{m}_{2}\langle\tilde{\psi}_{1},f\rangle\big{\rvert}$
$\displaystyle\leq C\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert.$

We deduce for some different constant $C=C(K)$ that

$\lvert
m_{3}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{m}_{3}\rvert\leq
C\lVert p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert.$ (19)

Finally, for $\psi_{2}$ we show that for some $C$ we have

$\max(\lvert
m_{1}\rvert,\lvert\tilde{m}_{1}\rvert)\lVert\psi_{2}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}\rVert\leq
C\lVert p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert.$ (20)

If $\psi_{2}=\tilde{\psi}_{2}$ there is nothing to prove, so we assume without
loss of generality that $\psi_{2}\neq\tilde{\psi}_{2}$. Also assume that
$\lvert m_{1}\rvert\geq\lvert\tilde{m}_{1}\rvert$, the final bound then
following by symmetry. Returning to equation 16 with $f$ to be chosen, we see
that

$m_{1}\big{(}\langle\psi_{2},f\rangle^{2}-\langle\tilde{\psi}_{2},f\rangle^{2}\big{)}=\langle\psi_{1}-\tilde{\psi}_{1},f\rangle^{2}-\langle
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)},1\otimes f\otimes
f\rangle-\langle\tilde{\psi}_{2},f\rangle^{2}(m_{1}-\tilde{m}_{1}).$

Since
$\langle\psi_{2},f\rangle^{2}-\langle\tilde{\psi}_{2},f\rangle^{2}=\langle\psi_{2}-\tilde{\psi}_{2},f\rangle\langle\psi_{2}+\tilde{\psi}_{2},f\rangle$
we obtain

$\lvert
m_{1}\langle\psi_{2}-\tilde{\psi}_{2},f\rangle\langle\psi_{2}+\tilde{\psi}_{2},f\rangle\rvert\leq\lVert
f\rVert^{2}\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+K\lVert f\rVert^{2}\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert+\lvert
m_{1}-\tilde{m}_{1}\rvert\langle\tilde{\psi}_{2},f\rangle^{2}.$ (21)

Observe that $\psi_{2}+\tilde{\psi}_{2}$ is orthogonal to
$\psi_{2}-\tilde{\psi}_{2}$ (this arises from the fact that $\psi_{2}$ and
$\tilde{\psi}_{2}$ have unit norms) and choose

$f=\frac{\psi_{2}+\tilde{\psi}_{2}}{\lVert\psi_{2}+\tilde{\psi}_{2}\rVert}+\frac{\psi_{2}-\tilde{\psi}_{2}}{\lVert\psi_{2}-\tilde{\psi}_{2}\rVert};$

note that

$\langle\psi_{2}-\tilde{\psi}_{2},f\rangle\langle\psi_{2}+\tilde{\psi}_{2},f\rangle=\lVert\psi_{2}-\tilde{\psi}_{2}\rVert\lVert\psi_{2}+\tilde{\psi}_{2}\rVert.$

Since also $\lVert f\rVert\leq 2$ and
$\lvert\langle\tilde{\psi}_{2},f\rangle\rvert\leq 2$, continuing from equation
21 and using equations 15 and 17 we see that for a constant $C=C(K)$

$\displaystyle\lvert
m_{1}\rvert\lVert\psi_{2}-\tilde{\psi}_{2}\rVert\lVert\psi_{2}+\tilde{\psi}_{2}\rVert$
$\displaystyle\leq 4\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+4K\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert+4\lvert
m_{1}-\tilde{m}_{1}\rvert$ $\displaystyle\leq 2C\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert.$

Observing that

$\displaystyle\lVert\psi_{2}-\tilde{\psi}_{2}\rVert^{2}\lVert\psi_{2}+\tilde{\psi}_{2}\rVert^{2}$
$\displaystyle=\lVert\psi_{2}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}\rVert^{2}\lVert\psi_{2}+\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}\rVert^{2}$
$\displaystyle=\lVert\psi_{2}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}\rVert^{2}\big{(}2+2\lvert\langle\psi_{2},\tilde{\psi}_{2}\rangle\rvert\big{)}$
$\displaystyle\geq
2\lVert\psi_{2}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\psi}_{2}\rVert^{2},$

and recalling we assumed that $\lvert
m_{1}\rvert\geq\lvert\tilde{m}_{1}\rvert$, equation 20 follows.

The proof that $\lVert
p^{(3)}_{\phi,\psi}-p^{(3)}_{\tilde{\phi},\tilde{\psi}}\rVert$ is lower
bounded up to a constant by $\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})$
follows by combining equations 15, 17, 18, 19 and 20

#### Upper bounding $\lVert
p^{(3)}_{\phi,\psi}-p^{(3)}_{\tilde{\phi},\tilde{\psi}}\rVert$

From equation 14,

$\begin{split}\lVert
p_{\phi,\psi}^{(3)}-p_{\tilde{\phi},\tilde{\psi}}^{(3)}\rVert&\leq\lVert\psi_{111}-\tilde{\psi}_{111}\rVert+\lvert
m_{1}-\tilde{m}_{1}\rvert\lVert\psi_{221}+\psi_{122}\rVert+\lvert\tilde{m}_{1}\rvert\lVert\psi_{221}-\tilde{\psi}_{221}\rVert\\\
&\quad+\lvert\tilde{m}_{1}\rvert\lVert\psi_{122}-\tilde{\psi}_{122}\rVert+\lvert
m_{2}-\tilde{m}_{2}\rvert\lVert\psi_{212}\rVert+\lvert\tilde{m}_{2}\rvert\lVert\psi_{212}-\tilde{\psi}_{212}\rVert\\\
&\quad+\lvert
m_{3}-\tilde{m}_{3}\rvert\lVert\psi_{222}\rVert+\lvert\tilde{m}_{3}\rvert\lVert\psi_{222}-\tilde{\psi}_{222}\rVert.\end{split}$
(22)

Note that the bound remains valid if we replace the final two terms by

$\lvert
m_{3}+\tilde{m}_{3}\rvert\lVert\psi_{222}\rVert+\lvert\tilde{m}_{3}\rvert\lVert\psi_{222}+\tilde{\psi}_{222}\rVert;$

we focus on the case where
$\operatorname{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)=+1$ for which the
original decomposition yields suitable bounds, but the proof in the other case
is similar using the alternative decomposition.

As used already in proving the lower bound on $\lVert
p^{(3)}_{\phi,\psi}-p^{(3)}_{\tilde{\phi},\tilde{\psi}}\rVert$, we note that

$\max(\lVert\psi_{221}\rVert,\lVert\psi_{122}\rVert,\lvert\tilde{m}_{1}\rvert,\lVert\psi_{212}\rVert,\lvert\tilde{m}_{2}\rvert,\lVert\psi_{222}\rVert,\lvert\tilde{m}_{3}\rvert)\leq
C,$

for some $C=C(K)$. To conclude the proof it thus suffices to bound the tensor
product terms $\lVert\psi_{ijk}-\tilde{\psi}_{ijk}\rVert$ in terms of the
differences
$\lVert\psi_{1}-\tilde{\psi}_{1}\rVert,\lVert\psi_{2}-\tilde{\psi}_{2}\rVert$.
First we decompose

$\lVert\psi_{1}\otimes\psi_{1}\otimes\psi_{1}-\tilde{\psi}_{1}\otimes\tilde{\psi}_{1}\otimes\tilde{\psi}_{1}\rVert\leq\lVert\psi_{1}\otimes\psi_{1}\otimes\psi_{1}-\tilde{\psi}_{1}\otimes\psi_{1}\otimes\psi_{1}\rVert\\\
\quad+\lVert\tilde{\psi}_{1}\otimes\psi_{1}\otimes\psi_{1}-\tilde{\psi}_{1}\otimes\tilde{\psi}_{1}\otimes\psi_{1}\rVert+\lVert\tilde{\psi}_{1}\otimes\tilde{\psi}_{1}\otimes\psi_{1}-\tilde{\psi}_{1}\otimes\tilde{\psi}_{1}\otimes\tilde{\psi}_{1}\rVert,$

so that

$\lVert\psi_{111}-\tilde{\psi}_{111}\rVert\leq\lVert\psi_{1}-\tilde{\psi}_{1}\rVert(\lVert\psi_{1}\rVert^{2}+\lVert\psi_{1}\rVert\lVert\tilde{\psi}_{1}\rVert+\lVert\tilde{\psi}_{1}\rVert^{2})\leq
3K\lVert\psi_{1}-\tilde{\psi}_{1}\rVert.$ (23)

We also note, recalling that $\psi_{2}$ and $\tilde{\psi}_{2}$ have unit
norms, that

$\displaystyle\lVert\psi_{221}-\tilde{\psi}_{221}\rVert^{2}$
$\displaystyle=\lVert\psi_{221}\rVert^{2}+\lVert\tilde{\psi}_{221}\rVert^{2}-2\langle\psi_{221},\tilde{\psi}_{221}\rangle$
$\displaystyle=\lVert\psi_{1}\rVert^{2}+\lVert\tilde{\psi}_{1}\rVert^{2}-2\langle\psi_{2},\tilde{\psi}_{2}\rangle^{2}\langle\psi_{1},\tilde{\psi}_{1}\rangle$
$\displaystyle=\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+2\langle\psi_{1},\tilde{\psi}_{1}\rangle\big{(}1-\langle\psi_{2},\tilde{\psi}_{2}\rangle^{2}\big{)}$
$\displaystyle\leq\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+2\lVert\psi_{1}\rVert\lVert\tilde{\psi}_{1}\rVert\lvert
1-\langle\psi_{2},\tilde{\psi}_{2}\rangle^{2}\rvert.$

Observe that

$\lVert\psi_{2}-\tilde{\psi}_{2}\rVert^{2}=2(1-\langle\psi_{2},\tilde{\psi}_{2}\rangle),$
(24)

and hence

$\big{\lvert}1-\langle\psi_{2},\tilde{\psi}_{2}\rangle^{2}\big{\rvert}=\big{\lvert}1+\langle\psi_{2},\tilde{\psi_{2}}\rangle\big{\rvert}\big{\lvert}1-\langle\psi_{2},\tilde{\psi}_{2}\rangle\big{\rvert}\leq
2\lvert
1-\langle\psi_{2},\tilde{\psi}_{2}\rangle\rvert=\lVert\psi_{2}-\tilde{\psi}_{2}\rVert^{2}.$

We deduce that

$\lVert\psi_{221}-\tilde{\psi}_{221}\rVert^{2}\leq\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+2\lVert\psi_{1}\rVert\lVert\tilde{\psi}_{1}\rVert\lVert\psi_{2}-\tilde{\psi}_{2}\rVert^{2}\leq\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}+2K\lVert\psi_{2}-\tilde{\psi}_{2}\rVert^{2}.$
(25)

By symmetry, the same bound holds for
$\lVert\psi_{122}-\tilde{\psi}_{122}\rVert$ and for
$\lVert\psi_{212}-\tilde{\psi}_{212}\rVert$. Furthermore
$\lVert\psi_{222}\rVert=1$, and using (24),

$\displaystyle\lVert\psi_{222}-\tilde{\psi}_{222}\rVert^{2}$
$\displaystyle=\lVert\psi_{222}\rVert^{2}+\lVert\tilde{\psi}_{222}\rVert^{2}-2\langle\psi_{222},\tilde{\psi}_{222}\rangle$
$\displaystyle=2-2\langle\psi_{2},\tilde{\psi}_{2}\rangle^{3}$
$\displaystyle=2\big{(}1-\langle\psi_{2},\tilde{\psi}_{2}\rangle\big{)}\big{(}1+\langle\psi_{2},\tilde{\psi}_{2}\rangle+\langle\psi_{2},\tilde{\psi}_{2}\rangle^{2}\big{)}$
$\displaystyle\leq 3\lVert\psi_{2}-\tilde{\psi}_{2}\rVert^{2}.$ (26)

The claim follows from inserting equations 23, 25 and 8.1 into equation 22.

###  8.2 Proof of Proposition 2

Write $X_{1:k}$ and $Y_{1:k}$ for the vectors $(X_{1},\dots,X_{k})$ and
$(Y_{1},\dots,Y_{k})$ respectively, and recall that $P_{\theta}^{(n)}$ denotes
the law of $Y_{1:n}$ for parameter $\theta$. Without loss of generality we may
assume that $\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)=+1$, since
one may substitute
$\tilde{\phi}^{\prime}=(-\tilde{\phi}_{1},\tilde{\phi}_{2},\tilde{\phi}_{3})$
and $\tilde{\psi}^{\prime}=(\tilde{\psi}_{1},-\tilde{\psi}_{2})$ for
$\tilde{\phi}$ and $\tilde{\psi}$ and obtain
$P_{\tilde{\theta}}^{(n)}=P_{\tilde{\theta^{\prime}}}^{(n)}$, hence
$K(P_{\theta}^{(n)};P_{\tilde{\theta}}^{(n)})=K(P_{\theta}^{(n)};P_{\tilde{\theta}^{\prime}}^{(n)})$,
but
$\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}^{\prime}\rangle)=-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)$.
Recall that $K(P;Q)$ is upper bounded by the chi-square distance
$\chi^{2}(P,Q)=\mathbb{E}_{Q}[(\mathrm{d}P/\mathrm{d}Q-1)^{2}]$ (e.g. [40,
Lemma 2.7]). Then using that
$\mathbb{P}_{\theta}(Y_{1}=\cdot)=\psi_{1}(\cdot)$ and
$\mathbb{P}_{\tilde{\theta}}(Y_{1}=\cdot)=\tilde{\psi}_{1}(\cdot)\geq c$, we
have

$\displaystyle K(P_{\theta}^{(1)};P_{\tilde{\theta}}^{(1)})$
$\displaystyle\leq\sum_{y\in\mathcal{Y}}\frac{[\mathbb{P}_{\theta}(Y_{1}=y)-\mathbb{P}_{\tilde{\theta}}(Y_{1}=y)]^{2}}{\mathbb{P}_{\tilde{\theta}}(Y_{1}=y)}\leq\frac{\|\psi_{1}-\tilde{\psi}_{1}\|^{2}}{c}.$
(27)

This yields the case $n=1$ since the definition (12) implies that
$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\geq\lVert\psi_{1}-\tilde{\psi}_{1}\rVert^{2}$.

Now assume that $n\geq 2$. By the chain rule for relative divergence (used
inductively), we have

$\displaystyle K(P_{\theta}^{(n)};P_{\tilde{\theta}}^{(n)})$
$\displaystyle=K(P_{\theta}^{(1)};P_{\tilde{\theta}}^{(1)})+\sum_{k=1}^{n-1}\mathbb{E}_{\theta}[K(\mathbb{P}_{\theta}(Y_{k+1}\in\cdot\mid
Y_{1:k});\mathbb{P}_{\tilde{\theta}}(Y_{k+1}\in\cdot\mid Y_{1:k}))].$ (28)

The first term was addressed above, and we now consider the remaining terms.
Again bounding the KL divergence by the chi-square distance, we have

$\displaystyle K(\mathbb{P}_{\theta}(Y_{k+1}\in\cdot\mid
Y_{1:k});\mathbb{P}_{\tilde{\theta}}(Y_{k+1}\in\cdot\mid Y_{1:k}))$
$\displaystyle\leq\sum_{y\in\mathcal{Y}}\frac{[\mathbb{P}_{\theta}(Y_{k+1}=y\mid
Y_{1:k})-\mathbb{P}_{\tilde{\theta}}(Y_{k+1}=y\mid
Y_{1:k})]^{2}}{\mathbb{P}_{\tilde{\theta}}(Y_{k+1}=y\mid Y_{1:k})}$
$\displaystyle\leq\frac{\|\mathbb{P}_{\theta}(Y_{k+1}=\cdot\mid
Y_{1:k})-\mathbb{P}_{\tilde{\theta}}(Y_{k+1}=\cdot\mid
Y_{1:k})\|^{2}}{\min_{y\in\mathcal{Y}}\mathbb{P}_{\tilde{\theta}}(Y_{k+1}=y\mid
Y_{1:k})}.$

But, for any $k\geq 1$,

$\displaystyle\mathbb{P}_{\theta}(Y_{k+1}=y\mid Y_{1:k})$
$\displaystyle=\sum_{x\in\\{0,1\\}^{k+1}}\mathbb{P}_{\theta}(Y_{k+1}=y\mid
Y_{1:k},X_{1:k+1}=x)\mathbb{P}_{\theta}(X_{1:k+1}=x\mid Y_{1:k})$
$\displaystyle=\sum_{x\in\\{0,1\\}^{k+1}}f_{x_{k+1}}(y)\mathbb{P}_{\theta}(X_{1:k+1}=x\mid
Y_{1:k})$
$\displaystyle=\sum_{x\in\\{0,1\\}}f_{x}(y)\mathbb{P}_{\theta}(X_{k+1}=x\mid
Y_{1:k}),$ (29)

where we have used that $Y_{k+1}\mid(Y_{1:k},X_{1:k+1})$ has the same law as
$Y_{k+1}\mid X_{k+1}$. Therefore when $\min(\tilde{f}_{0},\tilde{f}_{1})\geq
c$ we must have for all $Y_{1:k}$ and all $k\geq 1$

$\displaystyle\mathbb{P}_{\tilde{\theta}}(Y_{k+1}=y\mid Y_{1:k})$
$\displaystyle\geq
c\sum_{x\in\\{0,1\\}}\mathbb{P}_{\tilde{\theta}}(X_{k+1}=x\mid Y_{1:k})=c.$

Hence we have established that for all $Y_{1:k}$ and all $k\geq 1$

$K(\mathbb{P}_{\theta}(Y_{k+1}\in\cdot\mid
Y_{1:k});\mathbb{P}_{\tilde{\theta}}(Y_{k+1}\in\cdot\mid
Y_{1:k}))\leq\frac{\|\mathbb{P}_{\theta}(Y_{k+1}=\cdot\mid
Y_{1:k})-\mathbb{P}_{\tilde{\theta}}(Y_{k+1}=\cdot\mid Y_{1:k})\|^{2}}{c}.$
(30)

Let us now rewrite $\mathbb{P}_{\theta}(Y_{k+1}=y\mid Y_{1:k})$ in the
parametrisation $(\phi,\psi)$. For convenience we introduce the notation
$P_{k}(x)\coloneqq\mathbb{P}_{\theta}(X_{k+1}=x\mid Y_{1:k})$ for the
prediction filters, and we similarly write
$\tilde{P}_{k}(x)\coloneqq\mathbb{P}_{\tilde{\theta}}(X_{k+1}=x\mid Y_{1:k})$.
By equations 29 and 4,

$\displaystyle\mathbb{P}_{\theta}(Y_{k+1}=y\mid Y_{1:k})$
$\displaystyle=f_{0}(y)P_{k}(0)+f_{1}(y)P_{k}(1)$
$\displaystyle=\Big{(}\psi_{1}(y)-\tfrac{1}{2}\phi_{1}\phi_{3}\psi_{2}(y)+\tfrac{1}{2}\phi_{3}\psi_{2}(y)\Big{)}P_{k}(0)$
$\displaystyle\quad+\Big{(}\psi_{1}(y)-\tfrac{1}{2}\phi_{1}\phi_{3}\psi_{2}(y)-\tfrac{1}{2}\phi_{3}\psi_{2}(y)\Big{)}P_{k}(1)$
$\displaystyle=\psi_{1}(y)+\tfrac{1}{2}\big{(}P_{k}(0)-P_{k}(1)-\phi_{1}\big{)}\phi_{3}\psi_{2}(y).$

Define

$\displaystyle V_{k}$
$\displaystyle\coloneqq\phi_{3}(P_{k}(0)-P_{k}(1)-\phi_{1})=\phi_{3}(1-2P_{k}(1)-\phi_{1}),\qquad\tilde{V}_{k}\coloneqq\tilde{\phi}_{3}(1-2\tilde{P}_{k}(1)-\tilde{\phi}_{1}),\qquad
k\geq 1.$

Then combining equations 28, 27 and 30, we obtain

$\displaystyle K(P_{\theta}^{(n)};P_{\tilde{\theta}}^{(n)})$
$\displaystyle\leq\frac{\|\psi_{1}-\tilde{\psi}_{1}\|^{2}}{c}+\frac{1}{c}\sum_{k=1}^{n-1}\mathbb{E}_{\tilde{\theta}}\Big{[}\Big{\|}\psi_{1}-\tilde{\psi}_{1}+\frac{1}{2}V_{k}\psi_{2}-\frac{1}{2}\tilde{V}_{k}\tilde{\psi}_{2}\Big{\|}^{2}\Big{]}$
$\displaystyle\leq\frac{2n-1}{c}\|\psi_{1}-\tilde{\psi}_{1}\|^{2}+\frac{1}{2c}\sum_{k=1}^{n-1}\mathbb{E}_{\tilde{\theta}}[\|V_{k}\psi_{2}-\tilde{V}_{k}\tilde{\psi}_{2}\|^{2}]$
$\displaystyle\leq\frac{2n-1}{c}\|\psi_{1}-\tilde{\psi}_{1}\|^{2}+\frac{\|\psi_{2}-\tilde{\psi}_{2}\|^{2}}{c}\sum_{k=1}^{n-1}\mathbb{E}_{\tilde{\theta}}[V_{k}^{2}]+\frac{1}{c}\sum_{k=1}^{n-1}\mathbb{E}_{\tilde{\theta}}[(V_{k}-\tilde{V}_{k})^{2}],$
(31)

where in the last line we have used that $\|\tilde{\psi}_{2}\|^{2}=1$.

Let us now find an inductive formula for $V_{k}$. First we observe that, for
any $k\geq 2$

$\displaystyle P_{k}(x)$
$\displaystyle\coloneqq\mathbb{P}_{\theta}(X_{k+1}=x\mid Y_{1:k})$
$\displaystyle=\sum_{x^{\prime}\in\\{0,1\\}}\mathbb{P}_{\theta}(X_{k+1}=x\mid
Y_{1:k},X_{k}=x^{\prime})\mathbb{P}_{\theta}(X_{k}=x^{\prime}\mid Y_{1:k})$
$\displaystyle=\sum_{x^{\prime}\in\\{0,1\\}}\mathbb{P}_{\theta}(X_{k+1}=x\mid
X_{k}=x^{\prime})\mathbb{P}_{\theta}(X_{k}=x^{\prime}\mid Y_{1:k})$
$\displaystyle=\sum_{x^{\prime}\in\\{0,1\\}}Q_{x^{\prime},x}\mathbb{P}_{\theta}(X_{k}=x^{\prime}\mid
Y_{1:k-1},Y_{k}),$

and we further calculate

$\displaystyle\mathbb{P}_{\theta}(X_{k}=x^{\prime}\mid Y_{1:k-1},Y_{k}=y_{k})$
$\displaystyle=\frac{\mathbb{P}_{\theta}(X_{k}=x^{\prime},Y_{k}=y_{k}\mid
Y_{1:k-1})}{\mathbb{P}_{\theta}(Y_{k}\mid Y_{1:k-1})}$
$\displaystyle=\frac{f_{x^{\prime}}(y_{k})\mathbb{P}_{\theta}(X_{k}=x^{\prime}\mid
Y_{1:k-1})}{\sum_{x^{\prime\prime}\in\\{0,1\\}}\mathbb{P}_{\theta}(y_{k}\mid
Y_{1:k-1},X_{k}=x^{\prime\prime})\mathbb{P}_{\theta}(X_{k}=x^{\prime\prime}\mid
Y_{1:k-1})}$
$\displaystyle=\frac{f_{x^{\prime}}(y_{k})P_{k-1}(x^{\prime})}{\sum_{x^{\prime\prime}\in\\{0,1\\}}f_{x^{\prime\prime}}(y_{k})P_{k-1}(x^{\prime\prime})}.$

Similarly, for $k=1$,

$\displaystyle\mathbb{P}_{\theta}(X_{2}=x\mid Y_{1}=y_{1})$
$\displaystyle=\frac{\mathbb{P}_{\theta}(X_{2}=x,Y_{1}=y_{1})}{\mathbb{P}_{\theta}(y_{1})}$
$\displaystyle=\frac{\sum_{x^{\prime}\in\\{0,1\\}}\mathbb{P}_{\theta}(X_{2}=x,Y_{1}=y_{1}\mid
X_{1}=x^{\prime})\mathbb{P}_{\theta}(X_{1}=x^{\prime})}{\sum_{x^{\prime}\in\\{0,1\\}}f_{x^{\prime}}(y_{1})\mathbb{P}_{\theta}(X_{1}=x^{\prime})}$
$\displaystyle=\frac{\sum_{x^{\prime}\in\\{0,1\\}}f_{x^{\prime}}(y_{1})Q_{x^{\prime},x}\mathbb{P}_{\theta}(X_{1}=x^{\prime})}{\sum_{x^{\prime}\in\\{0,1\\}}f_{x^{\prime}}(y_{1})\mathbb{P}_{\theta}(X_{1}=x^{\prime})}$

To summarise, we have proved the recursive formula

$\displaystyle P_{k}(x)$
$\displaystyle=\begin{cases}\frac{\sum_{x^{\prime}\in\\{0,1\\}}Q_{x^{\prime},x}f_{x^{\prime}}(Y_{k})P_{k-1}(x^{\prime})}{\sum_{x^{\prime}\in\\{0,1\\}}f_{x^{\prime}}(Y_{k})P_{k-1}(x^{\prime})}&\mathrm{if}\
k\geq 2,\\\
\frac{\sum_{x^{\prime}\in\\{0,1\\}}f_{x^{\prime}}(Y_{1})Q_{x^{\prime},x}\mathbb{P}_{\theta}(X_{1}=x^{\prime})}{\sum_{x^{\prime}\in\\{0,1\\}}f_{x^{\prime}}(Y_{1})\mathbb{P}_{\theta}(X_{1}=x^{\prime})}&\mathrm{if}\
k=1.\end{cases}$

Therefore when $k\geq 2$,

$\displaystyle V_{k}$
$\displaystyle=\phi_{3}\Big{(}1-2\frac{Q_{0,1}f_{0}(Y_{k})P_{k-1}(0)+Q_{1,1}f_{1}(Y_{k})P_{k-1}(1)}{f_{0}(Y_{k})P_{k-1}(0)+f_{1}(Y_{k})P_{k-1}(1)}-\phi_{1}\Big{)}$
$\displaystyle=\phi_{3}\Big{(}1-\frac{2pf_{0}(Y_{k})P_{k-1}(0)+2(1-q)f_{1}(Y_{k})P_{k-1}(1)}{f_{0}(Y_{k})P_{k-1}(0)+f_{1}(Y_{k})P_{k-1}(1)}-\phi_{1}\Big{)}$
$\displaystyle=\phi_{3}\Big{(}1-\frac{2pf_{0}(Y_{k})+2P_{k-1}(1)[(1-q)f_{1}(Y_{k})-pf_{0}(Y_{k})]}{f_{0}(Y_{k})+P_{k-1}(1)[f_{1}(Y_{k})-f_{0}(Y_{k})]}-\phi_{1}\Big{)}.$

We write for convenience

$\displaystyle D_{k}$
$\displaystyle=f_{0}(Y_{k})+P_{k-1}(1)[f_{1}(Y_{k})-f_{0}(Y_{k})],$
$\displaystyle N_{k}$
$\displaystyle=(1-\phi_{1})\phi_{3}D_{k}-2\phi_{3}pf_{0}(Y_{k})-2\phi_{3}P_{k-1}(1)[(1-q)f_{1}(Y_{k})-pf_{0}(Y_{k})],$

so that $V_{k}=N_{k}/D_{k}$. We rewrite the previous expressions solely in
terms of the parameters $(\phi,\psi)$ [recall the inversion formulae in Remark
4]. First,

$\displaystyle D_{k}$
$\displaystyle=\psi_{1}(Y_{k})-\frac{1}{2}\phi_{1}\phi_{3}\psi_{2}(Y_{k})+\frac{1}{2}\phi_{3}\psi_{2}(Y_{k})-P_{k-1}(1)\phi_{3}\psi_{2}(Y_{k})$
$\displaystyle=\psi_{1}(Y_{k})+\frac{1}{2}\phi_{3}\psi_{2}(Y_{k})[1-2P_{k-1}(1)-\phi_{1}]$
$\displaystyle=\psi_{1}(Y_{k})+\frac{V_{k-1}}{2}\psi_{2}(Y_{k}).$

Also,

$\displaystyle 2pf_{0}$
$\displaystyle=(1-\phi_{1})(1-\phi_{2})\Big{[}\psi_{1}-\frac{1}{2}\phi_{1}\phi_{3}\psi_{2}+\frac{1}{2}\phi_{3}\psi_{2}\Big{]},$

and

$\displaystyle(1-q)f_{1}-pf_{0}$ $\displaystyle=(1-q-p)f_{1}-p(f_{0}-f_{1})$
$\displaystyle=\phi_{2}\Big{(}\psi_{1}-\frac{1}{2}\phi_{1}\phi_{3}\psi_{2}-\frac{1}{2}\phi_{3}\psi_{2}\Big{)}-\frac{1}{2}(1-\phi_{2})(1-\phi_{1})\phi_{3}\psi_{2}$
$\displaystyle=\phi_{2}\psi_{1}-\frac{1}{2}\phi_{3}\psi_{2}\Big{(}\phi_{2}+\phi_{1}\phi_{2}+(1-\phi_{2})(1-\phi_{1})\Big{)}$
$\displaystyle=\phi_{2}\psi_{1}-\frac{1}{2}\phi_{3}\psi_{2}\Big{(}1-\phi_{1}+2\phi_{1}\phi_{2}\Big{)}.$

Using the last three displays and the fact that
$2\phi_{3}P_{k-1}(1)=-V_{k-1}+\phi_{3}-\phi_{1}\phi_{3}$, we obtain that

$\displaystyle N_{k}$
$\displaystyle=(1-\phi_{1})\phi_{3}\Big{[}\psi_{1}(Y_{k})+\frac{V_{k-1}}{2}\psi_{2}(Y_{k})\Big{]}$
$\displaystyle\quad-\phi_{3}(1-\phi_{1})(1-\phi_{2})\Big{[}\psi_{1}(Y_{k})-\frac{1}{2}\phi_{1}\phi_{3}\psi_{2}(Y_{k})+\frac{1}{2}\phi_{3}\psi_{2}(Y_{k})\Big{]}$
$\displaystyle\quad+(V_{k-1}-\phi_{3}+\phi_{1}\phi_{3})\Big{[}\phi_{2}\psi_{1}(Y_{k})-\frac{1}{2}\phi_{3}\psi_{2}(Y_{k})\Big{(}1-\phi_{1}+2\phi_{1}\phi_{2}\Big{)}\Big{]}.$

Grouping together the terms proportional to $V_{k-1}$ and the others,

$\displaystyle N_{k}$
$\displaystyle=V_{k-1}\Big{[}\phi_{2}\psi_{1}(Y_{k})+\frac{1}{2}\Big{(}-\phi_{3}+\phi_{1}\phi_{3}-2\phi_{1}\phi_{2}\phi_{3}+(1-\phi_{1})\phi_{3}\Big{)}\psi_{2}(Y_{k})\Big{]}$
$\displaystyle\quad+\psi_{1}(Y_{k})\Big{[}(1-\phi_{1})\phi_{3}-\phi_{3}(1-\phi_{1})(1-\phi_{2})-\phi_{3}(1-\phi_{3})\phi_{2}\Big{]}$
$\displaystyle\quad+\frac{1}{2}\psi_{2}(Y_{k})\Big{[}-\phi_{3}^{2}(1-\phi_{1})^{2}(1-\phi_{2})+\phi_{3}^{2}(1-\phi_{1})(1-\phi_{1}+2\phi_{1}\phi_{2})\Big{]}.$

We remark that,

$\displaystyle-\phi_{3}+\phi_{1}\phi_{3}-2\phi_{1}\phi_{2}\phi_{3}+(1-\phi_{1})\phi_{3}$
$\displaystyle=-2\phi_{1}\phi_{2}\phi_{3},$

and

$\displaystyle(1-\phi_{1})\phi_{3}-\phi_{3}(1-\phi_{1})(1-\phi_{2})-\phi_{3}(1-\phi_{3})\phi_{2}$
$\displaystyle=0,$

and

$\displaystyle-\phi_{3}^{2}(1-\phi_{1})^{2}(1-\phi_{2})+\phi_{3}^{2}(1-\phi_{1})(1-\phi_{1}+2\phi_{1}\phi_{2})$
$\displaystyle\qquad=-\phi_{3}^{2}(1-\phi_{1})^{2}(1-\phi_{2})+\phi_{3}^{2}(1-\phi_{1})^{2}+2\phi_{1}\phi_{2}\phi_{3}^{2}(1-\phi_{1})$
$\displaystyle\qquad=\phi_{2}\phi_{3}^{2}(1-\phi_{1})^{2}+2\phi_{1}\phi_{2}\phi_{3}^{2}(1-\phi_{1})$
$\displaystyle\qquad=\phi_{2}\phi_{3}^{2}[1-2\phi_{1}+\phi_{1}^{2}+2\phi_{1}-2\phi_{1}^{2}]$
$\displaystyle\qquad=\phi_{2}\phi_{3}^{2}(1-\phi_{1}^{2}).$

That is,

$\displaystyle N_{k}$
$\displaystyle=\phi_{2}V_{k-1}\big{[}\psi_{1}(Y_{k})-\phi_{1}\phi_{3}\psi_{2}(Y_{k})\big{]}+\frac{\phi_{2}\phi_{3}^{2}(1-\phi_{1}^{2})}{2}\psi_{2}(Y_{k})$

which means that for $k\geq 2$,

$\displaystyle V_{k}$
$\displaystyle=\frac{\phi_{2}[\psi_{1}(Y_{k})-\phi_{1}\phi_{3}\psi_{2}(Y_{k})]V_{k-1}+2r(\phi)\psi_{2}(Y_{k})}{\psi_{1}(Y_{k})+\frac{1}{2}\psi_{2}(Y_{k})V_{k-1}}.$

For $k=1$, recalling that $Y_{1}\sim\psi_{1}$ and
$\mathbb{P}_{\theta}(X_{1}=1)=p/(p+q)$, we have

$\displaystyle V_{1}$ $\displaystyle=\phi_{3}(1-2P_{1}(1)-\phi_{1})$
$\displaystyle=\phi_{3}\Big{(}1-\phi_{1}-2\frac{f_{0}(Y_{1})\frac{pq}{p+q}+f_{1}(Y_{1})\frac{(1-q)p}{p+q}}{\psi_{1}(Y_{1})}\Big{)}$
$\displaystyle=\phi_{3}\Big{(}1-\phi_{1}-2\frac{f_{1}(Y_{1})\frac{p}{p+q}+\phi_{3}\psi_{2}(Y_{1})\frac{pq}{p+q}}{\psi_{1}(Y_{1})}\Big{)}$
$\displaystyle=\phi_{3}\Big{(}1-\phi_{1}-2\frac{[\psi_{1}(Y_{1})-\frac{1}{2}\phi_{1}\phi_{3}\psi_{2}(Y_{1})-\frac{1}{2}\phi_{3}\psi_{2}(Y_{1})]\frac{1-\phi_{1}}{2}+\phi_{3}\psi_{2}(Y_{1})\frac{(1-\phi_{2})(1-\phi_{1}^{2})}{4}}{\psi_{1}(Y_{1})}\Big{)}$
$\displaystyle=-\phi_{3}^{2}\psi_{2}(Y_{1})\frac{-\frac{(1-\phi_{1})(1+\phi_{1})}{2}+\frac{(1-\phi_{2})(1-\phi_{1}^{2})}{2}}{\psi_{1}(Y_{1})}$
$\displaystyle=\frac{\frac{1}{2}(1-\phi_{1}^{2})\phi_{2}\phi_{3}^{2}\psi_{2}(Y_{1})}{\psi_{1}(Y_{1})}$

Letting $m_{1}=r(\phi)$, $m_{2}=r(\phi)\phi_{2}$, and
$m_{3}=r(\phi)\phi_{1}\phi_{2}\phi_{3}$, we have obtained the inductive
formula

$\displaystyle
V_{k}=\begin{cases}\frac{[m_{2}\psi_{1}(Y_{k})-m_{3}\psi_{2}(Y_{k})]\frac{V_{k-1}}{m_{1}}+2m_{1}\psi_{2}(Y_{k})}{\psi_{1}(Y_{k})+\frac{1}{2}\psi_{2}(Y_{k})V_{k-1}}&\mathrm{if}\
k\geq 2,\\\ \frac{2m_{1}\psi_{2}(Y_{1})}{\psi_{1}(Y_{1})}&\mathrm{if}\
k=1.\end{cases}$

The strategy is now to bound $V_{k}-\tilde{V}_{k}$ for $k\geq 2$ in term of
$V_{1}-\tilde{V}_{1}$ using the above inductive formula. To do so, we will
need an upper bound for $V_{k}$ (respectively $\tilde{V}_{k}$) which we
establish now. We claim that $|V_{k}|\leq 4|m_{1}|/c$ for all $k\geq 1$
provided $\epsilon_{0}$ is taken small enough. Indeed,
$|\psi_{2}(Y_{1})|\leq\|\psi_{2}\|=1$ and $c\leq\psi_{1}(Y_{1})\leq 1$, hence
$|V_{1}|\leq 2|m_{1}|/c\leq 4|m_{1}|/c$. Now suppose that $|V_{k-1}|\leq
4|m_{1}|/c$; then, under the assumptions of the Proposition with for
$\epsilon_{0}=\epsilon_{0}(c)$ small enough, using equation 5 to see that
$|m_{1}|\leq|\phi_{2}|\leq\epsilon_{0}$,
$|\phi_{1}\phi_{2}\phi_{3}|\leq\sqrt{2}|\phi_{2}|\leq\sqrt{2}\epsilon_{0}$, we
have

$\displaystyle|V_{k}|$
$\displaystyle\leq\frac{(|m_{2}|+|m_{3}|)\frac{4}{c}+2|m_{1}|}{c-\frac{1}{2}\frac{4|m_{1}|}{c}}$
$\displaystyle\leq|m_{1}|\frac{(|\phi_{2}|+|\phi_{1}\phi_{2}\phi_{3}|)\frac{4}{c}+2}{c-4|m_{1}|/c}$
$\displaystyle\leq\frac{4|m_{1}|}{c}.$ (32)

Similarly $|\tilde{V}_{k}|\leq 4|\tilde{m}_{1}|/c$ for all $k\geq 1$. We are
now in position to bound $V_{k}-\tilde{V}_{k}$ for $k\geq 2$. Recall
$V_{k}=N_{k}/D_{k}$ and similarly write
$\tilde{V}_{k}=\tilde{N}_{k}/\tilde{D}_{k}$. Then

$\displaystyle
V_{k}-\tilde{V}_{k}=\frac{N_{k}}{D_{k}}-\frac{\tilde{N}_{k}}{\tilde{D}_{k}}=\frac{\tilde{D}_{k}N_{k}-D_{k}\tilde{N}_{k}}{D_{k}\tilde{D}_{k}}=\frac{(\tilde{D}_{k}-D_{k})N_{k}}{D_{k}\tilde{D}_{k}}+\frac{N_{k}-\tilde{N}_{k}}{\tilde{D}_{k}}.$

As when bounding $\lvert V_{k}\rvert$, we can assume that $\epsilon_{0}$ is
small enough to have $D_{k}\geq c/2$ and $\tilde{D}_{k}\geq c/2$, and

$\displaystyle|N_{k}|$
$\displaystyle\leq(|m_{2}|+|m_{3}|)\frac{4}{c}+2|m_{1}|\leq 4|m_{1}|.$

Therefore,

$\displaystyle|V_{k}-\tilde{V}_{k}|$
$\displaystyle\leq\frac{16|m_{1}|}{c^{2}}|D_{k}-\tilde{D}_{k}|+\frac{2}{c}|N_{k}-\tilde{N}_{k}|.$
(33)

But, recalling the definition (12) of $\rho$, we have

$\displaystyle|D_{k}-\tilde{D}_{k}|$
$\displaystyle=\Big{|}\psi_{1}(Y_{k})-\tilde{\psi}_{1}(Y_{k})+\frac{1}{2}\Big{(}\psi_{2}(Y_{k})V_{k-1}-\tilde{\psi}_{2}(Y_{k})\tilde{V}_{k-1}\Big{)}\Big{|}$
$\displaystyle\leq|\psi_{1}(Y_{k})-\tilde{\psi}_{1}(Y_{k})|+\frac{|\psi_{2}(Y_{k})|}{2}|V_{k-1}-\tilde{V}_{k-1}|+\frac{|\tilde{V}_{k-1}|}{2}|\psi_{2}(Y_{k})-\tilde{\psi}_{2}(Y_{k})|$
$\displaystyle\leq\|\psi_{1}-\tilde{\psi}_{1}\|+\frac{|V_{k-1}-\tilde{V}_{k-1}|}{2}+\frac{2|m_{1}|}{c}\|\psi_{2}-\tilde{\psi}_{2}\|$
$\displaystyle\leq\Big{(}1+\frac{2}{c}\Big{)}\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})+\frac{|V_{k-1}-\tilde{V}_{k-1}|}{2},$

and

$\displaystyle N_{k}-\tilde{N}_{k}$
$\displaystyle=[m_{2}\psi_{1}(Y_{k})-\tilde{m}_{2}\tilde{\psi}_{1}(Y_{k})-m_{3}\psi_{2}(Y_{k})+\tilde{m}_{3}\tilde{\psi}_{2}(Y_{k})]\frac{V_{k-1}}{m_{1}}$
$\displaystyle\quad+\Big{(}\frac{V_{k-1}}{m_{1}}-\frac{\tilde{V}_{k-1}}{\tilde{m}_{1}}\Big{)}\Big{(}\tilde{m}_{2}\tilde{\psi}_{1}(Y_{k})-\tilde{m}_{3}\tilde{\psi}_{2}(Y_{k})\Big{)}+2m_{1}\psi_{2}(Y_{k})-2\tilde{m}_{1}\tilde{\psi}_{2}(Y_{k}),$

from which we deduce that

$\displaystyle|N_{k}-\tilde{N}_{k}|$
$\displaystyle\leq\Big{(}|m_{2}|\|\psi_{1}-\tilde{\psi}_{1}\|+|m_{2}-\tilde{m}_{2}|+|m_{3}\|\psi_{2}-\tilde{\psi}_{2}\|+|m_{3}-\tilde{m}_{3}|\Big{)}\Big{|}\frac{V_{k-1}}{m_{1}}\Big{|}$
$\displaystyle\quad+\Big{(}|V_{k-1}-\tilde{V}_{k-1}|+|m_{1}-\tilde{m}_{1}|\Big{|}\frac{V_{k-1}}{m_{1}}\Big{|}\Big{)}\frac{|\tilde{m}_{2}|+|\tilde{m}_{3}|}{|\tilde{m}_{1}|}$
$\displaystyle\quad+2|m_{1}|\|\psi_{2}-\tilde{\psi}_{2}\|+2|m_{1}-\tilde{m}_{1}|$
$\displaystyle\leq
4|m_{1}-\tilde{m}_{1}|+\frac{4|m_{2}-\tilde{m}_{2}|}{c}+\frac{4|m_{3}-\tilde{m}_{3}|}{c}$
$\displaystyle\quad+\frac{4|m_{2}|\|\psi_{1}-\tilde{\psi}_{1}\|}{c}+\Big{(}\frac{4|m_{3}|}{c|m_{1}|}+2\Big{)}|m_{1}|\|\psi_{2}-\tilde{\psi}_{2}\|+\frac{c|V_{k-1}-\tilde{V}_{k-1}|}{8},$

where the last line holds when $\epsilon_{0}$ is small enough. Inserting these
bounds into equation 33, we find that there is a constant $B$ depending solely
on $c$ such that for all $k\geq 2$

$\displaystyle|V_{k}-\tilde{V}_{k}|$ $\displaystyle\leq
B\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})+\Big{(}\frac{1}{4}+\frac{8|m_{1}|}{c^{2}}\Big{)}|V_{k-1}-\tilde{V}_{k-1}|$
$\displaystyle\leq
B\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})+\frac{1}{2}|V_{k-1}-\tilde{V}_{k-1}|$

again when $\epsilon_{0}$ is small enough. Hence for $k\geq 2$,

$\displaystyle|V_{k}-\tilde{V}_{k}|$ $\displaystyle\leq
2(1-2^{-k})B\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})+2^{1-k}|V_{1}-\tilde{V}_{1}|$
$\displaystyle\leq\frac{3B}{2}\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})+\frac{|V_{1}-\tilde{V}_{1}|}{2}.$

To finish the proof, it is enough to show that $|V_{1}-\tilde{V}_{1}|$ is
bounded by a multiple constant of $\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})$,
which follows from its definition and the same arguments as above. Thus for
some constant $B^{\prime}>0$ depending only on $c$

$\max_{k=1,\dots,n}|V_{k}-\tilde{V}_{k}|\leq
B^{\prime}\rho(\phi,\psi;\tilde{\phi},\tilde{\psi}).$ (34)

The conclusion follows by combining equations 31, 32 and 34.

###  8.3 Proof of Theorem 2

We start with the proof of Lemma 1, that $p^{(3)}$ can be estimated at a
parametric rate.

###### Proof of Lemma 1.

We use a Markov chain concentration result from [34]. Theorem 3.4 therein (but
note there is an updated version of the paper on arXiv) tells us that for any
stationary Markov chain $\bm{Z}=(Z^{(1)},Z^{(2)},\dots)$ of pseudo-spectral
gap $\gamma_{\textnormal{ps}}$ (defined as in [34]) and any function $h$
satisfying $\mathbb{E}[h(Z^{(1)})^{2}]\leq\sigma^{2}$ and $\lVert
h\rVert_{\infty}\leq b$,

$\mathbb{P}(\lvert\sum_{i=1}^{n}h(Z^{(i)})-Eh(Z^{(1)})\rvert\geq x)\leq
2\exp\Big{(}-\frac{x^{2}\gamma_{\textnormal{ps}}}{8(n+1/\gamma_{\textnormal{ps}})\sigma^{2}+20bx}\Big{)}.$
(35)

We apply to the chain $\bm{Z}$ defined by
$Z^{(n)}=(X_{n},X_{n+1},X_{n+2},Y_{n},Y_{n+1},Y_{n+2})$; we begin by showing
the pseudo-spectral gap of this chain is bounded from below. Proposition 3.4
of the same reference shows that the reciprocal of the pseudo-spectral gap of
any chain is bounded above by twice the mixing time
$t_{\textnormal{mix}}^{\bm{Z}}$ of the chain, defined as the first time that
the law of $\bm{Z}$, regardless of the starting distribution, is within 1/4 of
its invariant distribution in total variation distance. We note that
$t_{\textnormal{mix}}^{\bm{Z}}$ is equal to the mixing time
$t_{\textnormal{mix}}^{\bm{X}^{(3)}}$ of the chain
$((X_{n},X_{n+1},X_{n+2})_{n\geq 0})$. This latter quantity is equal to
$t_{\textnormal{mix}}^{\bm{X}}+2$ where $t_{\textnormal{mix}}^{\bm{X}}$
denotes the mixing time of the chain $\bm{X}$ itself. Finally, the matrix $Q$
has eigenvalues $1$ and $\phi_{2}$, and an explicit computation yields that
$\max_{ij}\lvert
Q^{n}_{ij}-\pi_{j}\rvert=\max_{i}(\pi_{i})\lvert\phi_{2}\rvert^{n}$ so that
the mixing time of $\bm{X}$ is at most

$\Big{\lceil}\frac{\log
4}{\log(1/\lvert\phi_{2}\rvert)}\Big{\rceil}\leq\Big{\lceil}\frac{\log
4}{\log(1/(1-L))}\Big{\rceil}\leq\Big{\lceil}\frac{\log 4}{L}\Big{\rceil},$

which is a constant since $L$ is fixed. The pseudo-spectral gap of the chain
$\bm{Z}$ is thus lower bounded by some constant $\gamma=\gamma(L)$.

Applying equation 35 with $h(Z)=\mathbbm{1}\\{Z_{4}=a,Z_{5}=b,Z_{6}=c\\}$,
which satisfies $\mathbb{E}h^{2}\leq 1$ and $\lVert h\rVert_{\infty}\leq 1$,
we see that

$\mathbb{P}_{\phi,\psi}\big{(}n\lvert\hat{p}^{(3)}(a,b,c)-p_{\phi,\psi}^{(3)}(a,b,c)\rvert\geq
x\big{)}\leq 2\exp\Big{(}-\frac{\gamma x^{2}}{8n+8/\gamma+20x}\Big{)},$

hence for some constant $c^{\prime}>0$

$\mathbb{P}_{\phi,\psi}\big{(}\lvert\hat{p}^{(3)}(a,b,c)-p_{\phi,\psi}^{(3)}(a,b,c)\rvert\geq
x/\sqrt{n}\big{)}\leq
2\exp\Big{(}-c^{\prime}\min\Big{(}x^{2},x^{2}n,x\sqrt{n}\Big{)}\Big{)}.$

Using that $\lVert\hat{p}^{(3)}-p^{(3)}\rVert\leq
K^{3}\max_{a,b,c}\lvert\hat{p}^{(3)}(a,b,c)-p^{(3)}(a,b,c)\rvert$ and a union
bound, we deduce for some $C=C(K,L)$ and for $x\leq\sqrt{n}$ that

$\mathbb{P}_{\phi,\psi}(\lVert\hat{p}^{(3)}-p^{(3)}\rVert\geq
K^{3}x/\sqrt{n})\leq 2K^{3}\exp(-Cx^{2}).$

For $x\geq 1$ we may absorb the factor $2K^{3}$ into the exponential by
changing the constant $C$, and by replacing $x$ with $C^{\prime}x$ we can
remove this constant, yielding the result in the case where
$C^{\prime}x\leq\sqrt{n}$. In the other case, since
$\lVert\hat{p}^{(3)}-p^{(3)}\rVert$ is bounded (by $K^{3/2}$), by increasing
the constant $C^{\prime}$ if necessary we have $C^{\prime}x/\sqrt{n}\geq
K^{3/2}$ so that the probability in question is equal to $0\leq e^{-x^{2}}$. ∎

To prove Theorem 2, observe that by Lemma 1 there exist events
$\mathcal{A}_{n}$ of probability at least $e^{-x^{2}}$ on which

$\lVert\hat{p}^{(3)}_{n}-p_{\phi,\psi}^{(3)}\rVert\leq Cx/\sqrt{n}.$

The true parameter $(\phi,\psi)$ lies in $\Phi_{L}$ so that any estimators
constructed in Theorem 2 satisfy

$\lVert p^{(3)}_{\hat{\phi},\hat{\psi}}-\hat{p}^{(3)}_{n}\rVert\leq 2\lVert
p^{(3)}_{\phi,\psi}-\hat{p}^{(3)}_{n}\rVert,$

and hence on the event $\mathcal{A}_{n}$ further satisfy

$\lVert p^{(3)}_{\hat{\phi},\hat{\psi}}-p^{(3)}_{\phi,\psi}\rVert\leq\lVert
p^{(3)}_{\hat{\phi},\hat{\psi}}-\hat{p}^{(3)}_{n}\rVert+\lVert
p^{(3)}_{\phi,\psi}-\hat{p}^{(3)}_{n}\rVert\leq 3\lVert
p^{(3)}_{\phi,\psi}-\hat{p}^{(3)}_{n}\rVert\leq 3Cx/\sqrt{n},$

By Proposition 1 we deduce for a constant $C^{\prime}$ that
$\rho(\hat{\phi},\hat{\psi};\phi,\psi)\leq C^{\prime}x/\sqrt{n}$ on
$\mathcal{A}_{n}$. For estimating $\psi$, observe that
$\lVert\hat{\psi}_{1}-\psi_{1}\rVert\leq\rho(\hat{\phi},\hat{\psi};\phi,\psi)$
and $\lvert
r(\phi)\rvert\min(\lVert\hat{\psi}_{2}-\psi_{2}\rVert,\lVert\hat{\psi}_{2}+\psi_{2}\rVert)\leq\rho(\hat{\phi},\hat{\psi};\phi,\psi)$.
The upper bound for estimating $\psi_{1}$ is immediate and, recalling from
equation 5 that $\lvert r(\phi)\rvert\geq\delta\epsilon\zeta^{2}/4$, we also
deduce the bound for $\psi_{2}$.

For the bounds on $\phi$, observe firstly that it suffices to prove the upper
bounds on the absolute risk since, taking $\phi_{2}$ as an example, for
$(\phi,\psi)\in\Phi_{L}(\delta,\epsilon,\zeta)$ we have

$\begin{split}\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{2}/\phi_{2}-1\rvert^{2}\geq\frac{C}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}&=\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{2}-\phi_{2}\rvert^{2}\geq\frac{C\phi_{2}^{2}}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}\\\
&\leq\mathbb{P}_{\phi,\psi}\Big{(}\lvert\hat{\phi}_{2}-\phi_{2}\rvert\geq\frac{C\epsilon^{2}}{n\delta^{2}\epsilon^{4}\zeta^{4}}\Big{)}.\end{split}$
(36)

(See also after equation 37 for a similar argument with $\phi_{1}$.) Define

$\omega_{1}(\phi,\psi;\eta)\coloneqq\sup\left\\{\lvert\phi_{1}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\phi}_{1}\rvert\nonscript\,:\nonscript\,\mathopen{}\allowbreak\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq\eta\right\\},$

and

$\omega_{j}(\phi,\psi;\eta)\coloneqq\sup\left\\{\lvert\phi_{j}-\tilde{\phi}_{j}\rvert\nonscript\,:\nonscript\,\mathopen{}\allowbreak\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq\eta\right\\},\qquad
j=2,3.$

We have the following.

######  Proposition 3.

Let $\eta\in[0,1]$. There exist constants $c,C$ for which the following hold.

$\displaystyle\eta<c(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}$
$\displaystyle\implies\omega_{1}(\phi,\psi;\eta)\leq\frac{C\eta}{\phi_{2}^{2}\phi_{3}^{3}},$
$\displaystyle\eta<c(1-\phi_{1}^{2})\lvert\phi_{2}\rvert\phi_{3}^{2}$
$\displaystyle\implies\omega_{2}(\phi,\psi;\eta)\leq\frac{C\eta}{(1-\phi_{1}^{2})\lvert\phi_{2}\rvert\phi_{3}^{2}},$
$\displaystyle\eta<c(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}$
$\displaystyle\implies\omega_{3}(\phi,\psi;\eta)\leq\frac{C\eta}{(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{2}}.$

The conditions of Theorem 2 ensure that on the event $\mathcal{A}_{n}$ we may
apply Proposition 3 with $\eta=C^{\prime}x/\sqrt{n}$. We deduce the upper
bounds for estimating the components of $\phi$ immediately upon replacing
$\phi_{1},\phi_{2}$ and $\phi_{3}$ on the right sides in Proposition 3 by
their lower bounds [for $\phi_{1}$ we note that
$\min(\lvert\hat{\phi}_{1}-\phi_{1}\rvert,\lvert\hat{\phi}_{1}+\phi_{1}\rvert)\leq\lvert\phi_{1}-\operatorname{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\phi}_{1}\rvert$].

###### Proof of Proposition 3.

Recall that
$m(\phi)=(r(\phi),\phi_{2}r(\phi),\phi_{1}\phi_{2}\phi_{3}r(\phi))$ with
$r(\phi)=\tfrac{1}{4}(1-\phi_{1}^{2})\phi_{2}\phi_{3}^{2}$. If $r(\phi)=0$
then in each case no $\eta\in[0,1]$ satisfies the conditions and so there is
nothing to prove. Otherwise, note that $m$ is invertible when restricted to
$\\{\phi:r(\phi)\neq 0\\}\supset\Phi(\delta,\epsilon,\zeta)$ and its inverse
is given by $\phi(m)$ defined by

$\displaystyle\phi_{1}(m)$
$\displaystyle=m_{3}/(4m_{1}^{2}m_{2}+m_{3}^{2})^{1/2}$
$\displaystyle\phi_{2}(m)$ $\displaystyle=m_{2}/m_{1},$
$\displaystyle\phi_{3}(m)$
$\displaystyle=(4m_{1}^{2}m_{2}+m_{3}^{2})^{1/2}/m_{2}.$

For arbitrary $(\phi,\psi;\tilde{\phi},\tilde{\psi})$ satisfying
$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq\eta$, we define

$\Delta_{1}\coloneqq m_{1}(\tilde{\phi})-m_{1}(\phi),\quad\Delta_{2}\coloneqq
m_{2}(\tilde{\phi})-m_{2}(\phi),\quad\Delta_{3}\coloneqq\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot
m_{3}(\tilde{\phi})-m_{3}(\phi).$

Define also

$\displaystyle g(\phi)$ $\displaystyle\coloneqq
4m_{1}(\phi)^{2}m_{2}(\phi)+m_{3}(\phi)^{2}$
$\displaystyle=\\{m_{2}(\phi)\phi_{3}\\}^{2}$
$\displaystyle=\Big{\\{}\frac{1}{4}(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\Big{\\}}^{2},$

and, for $\Delta=(\Delta_{1},\Delta_{2},\Delta_{3})$,

$\begin{split}h_{\phi}(\Delta)&\coloneqq g(\tilde{\phi})-g(\phi)\\\
&=4(m_{1}(\phi)+\Delta_{1})^{2}(m_{2}(\phi)+\Delta_{2})+(m_{3}(\phi)+\Delta_{3})^{2}-\\{4m_{1}(\phi)^{2}m_{2}(\phi)+m_{3}(\phi)^{2}\\}.\end{split}$

Observe that

$\begin{split}h_{\phi}(\Delta)&=8m_{1}(\phi)m_{2}(\phi)\Delta_{1}+8m_{1}(\phi)\Delta_{1}\Delta_{2}+4m_{2}(\phi)\Delta_{1}^{2}\\\
&\quad+4\Delta_{1}^{2}\Delta_{2}+4m_{1}(\phi)^{2}\Delta_{2}+2m_{3}(\phi)\Delta_{3}+\Delta_{3}^{2}.\end{split}$

#### Bounding $\omega_{1}$

We decompose,

$\displaystyle\phi_{1}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\phi}_{1}$
$\displaystyle=\frac{m_{3}(\phi)}{\sqrt{4m_{1}(\phi)^{2}m_{2}(\phi)+m_{3}(\phi)^{2}}}-\frac{\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot
m_{3}(\tilde{\phi})}{\sqrt{4m_{1}(\tilde{\phi})^{2}m_{2}(\tilde{\phi})+m_{3}(\tilde{\phi})^{2}}}$
$\displaystyle=\frac{m_{3}(\phi)}{\sqrt{g(\phi)}}-\frac{m_{3}(\phi)+\Delta_{3}}{\sqrt{g(\phi)+h_{\phi}(\Delta)}}$
$\displaystyle=m_{3}(\phi)\Big{\\{}\frac{1}{\sqrt{g(\phi)}}-\frac{1}{\sqrt{g(\phi)+h_{\phi}(\Delta)}}\Big{\\}}-\frac{\Delta_{3}}{\sqrt{g(\phi)+h_{\phi}(\Delta)}}$
$\displaystyle=\frac{m_{3}(\phi)}{\sqrt{g(\phi)(g(\phi)+h_{\phi}(\Delta))}}\big{\\{}\sqrt{g(\phi)+h_{\phi}(\Delta)}-\sqrt{g(\phi)}\big{\\}}-\frac{\Delta_{3}}{\sqrt{g(\phi)+h_{\phi}(\Delta)}}$
$\displaystyle=\frac{m_{3}(\phi)}{\sqrt{g(\phi)(g(\phi)+h_{\phi}(\Delta))}}\frac{h_{\phi}(\Delta)}{\sqrt{g(\phi)+h_{\phi}(\Delta)}+\sqrt{g(\phi)}}-\frac{\Delta_{3}}{\sqrt{g(\phi)+h_{\phi}(\Delta)}}.$

Now we observe that $m_{3}(\phi)/\sqrt{g(\phi)}$ is equal to $\phi_{1}$, so
indeed

$\phi_{1}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\phi}_{1}=\frac{\phi_{1}h_{\phi}(\Delta)-\Delta_{3}(\sqrt{g(\phi)+h_{\phi}(\Delta)}+\sqrt{g(\phi)})}{\sqrt{g(\phi)+h_{\phi}(\Delta)}(\sqrt{g(\phi)+h_{\phi}(\Delta)}+\sqrt{g(\phi)})}.$

Call the numerator of this last fraction $N$ and call its denominator $D$.
Writing $h_{\phi}(\Delta)$ as
$h_{\phi}(\Delta)=\xi_{\phi}(\Delta)+\gamma_{\phi}(\Delta)$, where
$\gamma_{\phi}(\Delta)\coloneqq 2m_{3}(\phi)\Delta_{3}+\Delta_{3}^{2}$, we see
that

$N=\phi_{1}\xi_{\phi}(\Delta)+\phi_{1}\gamma_{\phi}(\Delta)-\Delta_{3}\big{\\{}(g(\phi)+h_{\phi}(\Delta))^{1/2}+g(\phi)^{1/2}\big{\\}}.$

In order to obtain the optimal upper bound, we need to do a fine analysis of
this expression. To this end, we calculate

$\displaystyle A$
$\displaystyle\coloneqq\phi_{1}\gamma_{\phi}(\Delta)-\Delta_{3}\\{(g+h)^{1/2}+g^{1/2}\\}$
$\displaystyle=2\Delta_{3}\\{\phi_{1}m_{3}(\phi)-g^{1/2}\\}+\phi_{1}\Delta_{3}^{2}-\Delta_{3}\\{(g+h)^{1/2}-g^{1/2}\\}$
$\displaystyle=-2\Delta_{3}(1-\phi_{1}^{2})g^{1/2}+\phi_{1}\Delta_{3}^{2}-\frac{\Delta_{3}h}{(g+h)^{1/2}+g^{1/2}}$
$\displaystyle=-2\Delta_{3}(1-\phi_{1}^{2})g^{1/2}-\Delta_{3}\frac{\gamma_{\phi}(\Delta)-\phi_{1}\Delta_{3}((g+h)^{1/2}+g^{1/2})}{(g+h)^{1/2}+g^{1/2}}-\frac{\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}},$

where the last line follows because
$\phi_{1}m_{3}(\phi)=\phi_{1}^{2}g(\phi)^{1/2}$. We now focus on the middle
term of this last display, which we will express as a function of $A$.

$\displaystyle B$
$\displaystyle\coloneqq\gamma_{\phi}(\Delta)-\phi_{1}\Delta_{3}((g+h)^{1/2}+g^{1/2})$
$\displaystyle=2\Delta_{3}(m_{3}(\phi)-\phi_{1}g^{1/2})+\Delta_{3}^{2}-\phi_{1}\Delta_{3}\\{(g+h)^{1/2}-g^{1/2}\\}$
$\displaystyle=\Delta_{3}^{2}-\frac{\phi_{1}\Delta_{3}h}{(g+h)^{1/2}+g^{1/2}}$
$\displaystyle=\Delta_{3}^{2}-\frac{\phi_{1}\Delta_{3}\gamma_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}-\frac{\phi_{1}\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}$
$\displaystyle=\Delta_{3}\frac{\Delta_{3}\\{(g+h)^{1/2}+g^{1/2}\\}-\phi_{1}\gamma_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}-\frac{\phi_{1}\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}$
$\displaystyle=-\frac{\Delta_{3}A}{(g+h)^{1/2}+g^{1/2}}-\frac{\phi_{1}\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}.$

Thus,

$\displaystyle A$
$\displaystyle=-2\Delta_{3}(1-\phi_{1}^{2})g^{1/2}-\frac{\Delta_{3}B}{(g+h)^{1/2}+g^{1/2}}-\frac{\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}$
$\displaystyle=-2\Delta_{3}(1-\phi_{1}^{2})g^{1/2}+\frac{\Delta_{3}^{2}A}{\\{(g+h)^{1/2}+g^{1/2}\\}^{2}}+\frac{\phi_{1}\Delta_{3}^{2}\xi_{\phi}(\Delta)}{\\{(g+h)^{1/2}+g^{1/2}\\}^{2}}-\frac{\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}},$

from which we deduce that

$N=\phi_{1}\xi_{\phi}(\Delta)+\frac{-2\Delta_{3}(1-\phi_{1}^{2})g^{1/2}+\frac{\phi_{1}\Delta_{3}^{2}\xi_{\phi}(\Delta)}{\\{(g+h)^{1/2}+g^{1/2}\\}^{2}}-\frac{\Delta_{3}\xi_{\phi}(\Delta)}{(g+h)^{1/2}+g^{1/2}}}{1-\Delta_{3}^{2}/\\{(g+h)^{1/2}+g^{1/2}\\}^{2}}.$

Since $m_{2}(\phi)\geq 0$, we see that $\xi_{\phi}(\Delta)$ has maximal
amplitude when $\Delta_{1}=\mathrm{sgn}(m_{1}(\phi))\eta$ and when
$\Delta_{2}=\eta$, in which case we have

$\displaystyle\lvert\xi_{\phi}(\Delta)\rvert$ $\displaystyle=8\lvert
m_{1}(\phi)\rvert m_{2}(\phi)\eta+8\lvert
m_{1}(\phi)\rvert\eta^{2}+4m_{2}(\phi)\eta^{2}+4\eta^{3}+4m_{1}(\phi)^{2}\eta$
$\displaystyle\leq 12m_{1}(\phi)^{2}\eta+12\lvert
m_{1}(\phi)\rvert\eta^{2}+4\eta^{3},$

where the last line follows since $m_{2}(\phi)\leq\lvert m_{1}(\phi)\rvert$.
Now we observe that under the condition of the lemma, we have
$\eta\lesssim\lvert m_{1}(\phi)\rvert$, and so we can find a constant $C>0$
such that

$\lvert\xi_{\phi}(\Delta)\rvert\leq Cm_{1}(\phi)^{2}\eta.$

Also, we have that $\lvert\gamma_{\phi}(\Delta)\rvert\leq 2\lvert
m_{3}(\phi)\rvert\eta+\eta^{2}$, and so

$\lvert h_{\phi}(\Delta)\rvert\leq Cm_{1}(\phi)^{2}\eta+2\lvert
m_{3}(\phi)\rvert\eta+\eta^{2},$

Noting that $\phi_{3}\leq\sqrt{K}$, for $c_{0}=c_{0}(K)$ sufficiently small in
the assumption of the proposition we have $\lvert h_{\phi}(\Delta)\rvert\leq
g(\phi)/2$. Consequently, noting also that $\lvert\Delta_{3}\rvert\leq\eta$
and $\eta\leq 4c_{0}g^{1/2}$, we find that

$\displaystyle\lvert N\rvert$ $\displaystyle\lesssim\lvert\phi_{1}\rvert
m_{1}(\phi)^{2}\eta+\eta(1-\phi_{1}^{2})g(\phi)^{1/2}$
$\displaystyle\lesssim\eta(1-\phi_{1}^{2})^{2}\phi_{2}^{2}\phi_{3}^{3},$

and

$\lvert D\rvert\gtrsim
g(\phi)\gtrsim(1-\phi_{1}^{2})^{2}\phi_{2}^{4}\phi_{3}^{6}.$

Hence we have

$\lvert\phi_{1}-\mathrm{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)\cdot\tilde{\phi}_{1}\rvert\lesssim\frac{\eta}{\phi_{2}^{2}\phi_{3}^{3}}.$

#### Bounding $\omega_{2}$

We rewrite,

$\displaystyle\phi_{2}-\tilde{\phi}_{2}$
$\displaystyle=\frac{m_{2}(\phi)}{m_{1}(\phi)}-\frac{m_{2}(\phi)+\Delta_{2}}{m_{1}(\phi)+\Delta_{1}}$
$\displaystyle=\frac{m_{2}(\phi)(m_{1}(\phi)+\Delta_{1})-(m_{2}(\phi)+\Delta_{2})m_{1}(\phi)}{m_{1}(\phi)(m_{1}(\phi)+\Delta_{1})}.$

Hence,

$\phi_{2}-\tilde{\phi}_{2}=\frac{\Delta_{1}m_{2}(\phi)-\Delta_{2}m_{1}(\phi)}{m_{1}(\phi)(m_{1}(\phi)+\Delta_{1})}.$

Under the assumptions of the theorem, we have that $\eta\leq m_{1}(\phi)/2$,
and thus

$\displaystyle\lvert\phi_{2}-\tilde{\phi}_{2}\rvert$
$\displaystyle\leq\frac{2\eta(m_{2}(\phi)+|m_{1}(\phi)|)}{m_{1}(\phi)^{2}}$
$\displaystyle\leq\frac{4\eta}{|m_{1}(\phi)|}$
$\displaystyle=\frac{16\eta}{(1-\phi_{1}^{2})|\phi_{2}|\phi_{3}^{2}}.$

#### Bounding $\omega_{3}$

We rewrite,

$\displaystyle\phi_{3}-\tilde{\phi}_{3}$
$\displaystyle=\frac{\sqrt{g(\phi)}}{m_{2}(\phi)}-\frac{\sqrt{g(\phi)+h_{\phi}(\Delta)}}{m_{2}(\phi)+\Delta_{2}}$
$\displaystyle=\frac{m_{2}(\phi)(\sqrt{g(\phi)}-\sqrt{g(\phi)+h_{\phi}(\Delta)})}{m_{2}(\phi)(m_{2}(\phi)+\Delta_{2})}+\frac{\Delta_{2}\sqrt{g(\phi)}}{m_{2}(\phi)(m_{2}(\phi)+\Delta_{2})}$
$\displaystyle=\frac{-h_{\phi}(\Delta)}{(m_{2}(\phi)+\Delta_{2})(\sqrt{g(\phi)+h_{\phi}(\Delta)}+\sqrt{g(\phi)})}+\frac{\Delta_{2}\phi_{3}}{m_{2}(\phi)+\Delta_{2}}$
$\displaystyle=\frac{-h_{\phi}(\Delta)+\Delta_{2}\phi_{3}(\sqrt{g(\phi)+h_{\phi}(\Delta)}+\sqrt{g(\phi)})}{(m_{2}(\phi)+\Delta_{2})(\sqrt{g(\phi)+h_{\phi}(\Delta)}+\sqrt{g(\phi)})}$

Let us call the numerator of the fraction on the right of the last display
$N$, and the denominator $D$. We further decompose $h_{\phi}(\Delta)$ as
$h_{\phi}(\Delta)=\xi_{\phi}(\Delta)+\gamma_{\phi}(\Delta)$, where
$\gamma_{\phi}(\Delta)\coloneqq 4m_{1}(\phi)^{2}\Delta_{2}$. We see that

$\displaystyle N$
$\displaystyle=-\xi_{\phi}(\phi)-4m_{1}(\phi)^{2}\Delta_{2}+\phi_{3}\Delta_{2}((g+h)^{1/2}+g^{1/2})$
$\displaystyle=-\xi_{\phi}(\phi)-4m_{1}(\phi)^{2}\Delta_{2}+\phi_{3}\Delta_{2}\\{(g+h)^{1/2}+g^{1/2}\\}$
$\displaystyle=-\xi_{\phi}(\phi)-4m_{1}(\phi)^{2}\Delta_{2}+2\phi_{3}\Delta_{2}g^{1/2}+\phi_{3}\Delta_{2}\\{(g+h)^{1/2}-g^{1/2}\\}$
$\displaystyle=-\xi_{\phi}(\phi)+\Delta_{2}(1+\phi_{1}^{2})\phi_{3}g^{1/2}+\frac{\phi_{3}\Delta_{2}h}{(g+h)^{1/2}+g^{1/2}},$

where the last line follows because
$m_{1}(\phi)^{2}=\frac{1}{4}(1-\phi_{1}^{2})\phi_{3}g^{1/2}$. Since
$m_{2}(\phi)\geq 0$, we see that $\xi_{\phi}(\Delta)$ has maximal amplitude
when $\Delta_{1}=\mathrm{sgn}(m_{1}(\phi))\eta$ and when $\Delta_{2}=\eta$, in
which case we have

$\displaystyle\lvert\xi_{\phi}(\Delta)\rvert$ $\displaystyle=8\lvert
m_{1}(\phi)\rvert m_{2}(\phi)\eta+8\lvert
m_{1}(\phi)\rvert\eta^{2}+4m_{2}(\phi)\eta^{2}+4\eta^{3}+2\lvert
m_{3}(\phi)\rvert\eta+\eta^{2}$ $\displaystyle\lesssim\\{\lvert
m_{1}(\phi)\rvert m_{2}(\phi)+2\lvert m_{3}(\phi)\rvert\\}\eta+\eta^{2}$
$\displaystyle\lesssim(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\max\\{(1-\phi_{1}^{2})\lvert\phi_{2}\rvert\phi_{3},\,\lvert\phi_{1}\rvert\\}\eta+\eta^{2},$

where the second line follows because under the assumptions of the proposition
we have that $m_{2}(\phi)\lesssim\lvert m_{1}(\phi)\rvert$ and $\eta\leq
m_{2}(\phi)/2$ (note that $\phi_{3}\leq K^{1/2}$). Since
$h_{\phi}(\Delta)=\xi_{\phi}(\Delta)+4m_{1}(\phi)^{2}\Delta_{2}$, we also have

$\lvert
h_{\phi}(\Delta)\rvert\lesssim(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\max\\{(1-\phi_{1}^{2})\phi_{3},\,\lvert\phi_{1}\rvert\\}\eta+\eta^{2},$

Hence,

$\displaystyle\lvert N\rvert$
$\displaystyle\lesssim(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\max\\{(1-\phi_{1}^{2})\lvert\phi_{2}\rvert\phi_{3},\,\lvert\phi_{1}\rvert\\}\eta+\eta^{2}$
$\displaystyle\quad+\eta\phi_{3}g^{1/2}+\frac{\eta^{2}\phi_{3}(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\max\\{(1-\phi_{1}^{2})\phi_{3},\lvert\phi_{1}\rvert\\}+\eta^{3}\phi_{3}}{g^{1/2}}$
$\displaystyle\lesssim(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\max\\{(1-\phi_{1}^{2})\lvert\phi_{2}\rvert\phi_{3},\,\lvert\phi_{1}\rvert\\}\eta+\eta^{2}$
$\displaystyle\quad+\eta\phi_{3}g^{1/2}+\eta^{2}\phi_{3}\max\\{(1-\phi_{1}^{2})\phi_{3},\lvert\phi_{1}\rvert\\}+\frac{\eta^{3}}{(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{2}}$

But by assumption $\eta\lesssim(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}$, and
$4g^{1/2}=(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{2}$, thus

$\lvert
N\rvert\lesssim(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{3}\max\\{\phi_{3},\,\lvert\phi_{1}\rvert\\}\eta+\eta^{2}.$

Note that $\max(\phi_{3},\lvert\phi\rvert_{1})\leq\sqrt{K}$. Moreover, under
the assumptions of the proposition and using that $\phi_{3}\leq\sqrt{K}$, it
is the case that $\lvert\Delta_{2}\rvert\leq\eta\lesssim m_{2}(\phi)$.
Therefore $\lvert D\rvert\gtrsim m_{2}(\phi)\sqrt{g(\phi)}$, and

$\lvert\phi_{3}-\tilde{\phi}_{3}\rvert\lesssim\frac{\eta}{(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{2}}+\frac{\eta^{2}}{(1-\phi_{1}^{2})^{2}\phi_{2}^{4}\phi_{3}^{5}}.$

Finally, since have assumed that
$\eta<\frac{(1-\phi_{1}^{2})\phi_{2}^{2}\phi_{3}^{2}}{8}$, we see that the
second term is at most a constant times the first, so that it can be absorbed
by increasing the constant $C$. ∎

###  8.4 Proof of Theorem 3

We give a standard two-point testing lower bound, summarising ideas that can
be found for example in Chapter 2 of [40].

######  Lemma 2.

Given data $X^{(n)}\sim p_{u}^{(n)}$ for parameter $u\in\mathcal{U}$, the
following lower bounds hold for estimating $u$.

Suppose $\mathcal{U}\subseteq\mathbb{R}$ and for some $r\leq 1/2$ assume that
there exist parameters $u_{0},u_{1}$ satisfying

  1. i.

$\lvert u_{1}/u_{0}-1\rvert\geq 4r$,

  2. ii.

$K(p^{(n)}_{u_{1}};p^{(n)}_{u_{0}})\leq 1/100$.

where we recall $K$ denotes the Kullback–Leibler divergence. Then

$\inf_{\hat{u}}\sup_{u\in\mathcal{U}}\mathbb{P}_{u}(\lvert\hat{u}/u-1\rvert\geq
r)\geq 1/4,$

where the infimum is over all estimators $\hat{u}$ based on the data
$X^{(n)}$.

If instead $(\mathcal{U},d)$ is a pseudo-metric space and for some $r\geq 0$
there exist parameters $u_{0},u_{1}$ satisfying

  1. i.

$d(u_{0},u_{1})\geq 2r$

  2. ii.

$K(p^{(n)}_{u_{1}},p^{(n)}_{u_{0}})\leq 1/100$,

then

$\inf_{\hat{u}}\sup_{u\in\mathcal{U}}\mathbb{P}_{u}(d(\hat{u},u)\geq r)\geq
1/4.$

###### Proof.

Given an estimator $\hat{u}$ we may construct a test $T$ of $u=u_{0}$ vs
$u=u_{1}$,

$T=\mathbbm{1}\Big{\\{}\Big{\lvert}\frac{\hat{u}}{u_{0}}-1\Big{\rvert}>\Big{\lvert}\frac{\hat{u}}{u_{1}}-1\Big{\rvert}\Big{\\}}.$

Observe that

$\displaystyle\Big{\lvert}\frac{\hat{u}}{u_{0}}-1\Big{\rvert}$
$\displaystyle=\Big{\lvert}\frac{u_{1}}{u_{0}}-1+\frac{\hat{u}-u_{1}}{u_{1}}\frac{u_{1}}{u_{0}}\Big{\rvert}$
$\displaystyle\geq 4r-\big{\lvert}\frac{\hat{u}}{u_{1}}-1\big{\rvert}(1+4r).$

Then

$\displaystyle\mathbb{P}_{u_{1}}(T=0)$
$\displaystyle=\mathbb{P}_{u_{1}}\Big{(}\Big{\lvert}\frac{\hat{u}}{u_{0}}-1\Big{\rvert}\leq\Big{\lvert}\frac{\hat{u}}{u_{1}}-1\Big{\rvert}\Big{)}$
$\displaystyle\leq\mathbb{P}_{u_{1}}\Big{(}4r-\big{\lvert}\frac{\hat{u}}{u_{1}}-1\big{\rvert}(1+4r)\leq\Big{\lvert}\frac{\hat{u}}{u_{1}}-1\Big{\rvert}\Big{)}$
$\displaystyle\leq\mathbb{P}_{u_{1}}\Big{(}\Big{\lvert}\frac{\hat{u}}{u_{1}}-1\Big{\rvert}\geq
r\Big{)},$

where for the last line we have used that $4r/(2+4r)\geq r$ for $r\leq 1/2$.
Also note that on the event $\\{T=1\\}\cap\\{\lvert\hat{u}/u_{0}-1\rvert<r\\}$
we have also $\lvert\hat{u}/u_{1}-1\rvert<r$ and hence

$\displaystyle\lvert u_{1}/u_{0}-1\rvert$
$\displaystyle=\lvert\hat{u}/u_{0}-1-(\hat{u}/u_{1}-1)-(\hat{u}/u_{1}-1)(u_{1}/u_{0}-1)\rvert$
$\displaystyle<2r+r\lvert u_{1}/u_{0}-1\rvert,$

so that $\lvert u_{1}/u_{0}-1\rvert<2r/(1-r)$ on this event. Having assumed
$r\leq 1/2$ and $\lvert u_{1}/u_{0}-1\rvert\geq 4r$ we deduce that
$\\{T=1\\}\cap\\{\lvert\hat{u}/u_{0}-1\rvert<r\\}=\emptyset$ so that
$\\{T=1\\}\subseteq\\{\lvert\hat{u}/u_{0}-1\rvert\geq r\\}$, and hence we have
shown

$\inf_{\hat{u}}\sup_{u}\mathbb{P}_{u}\Big{(}\Big{\lvert}\frac{\hat{u}}{u}-1\Big{\rvert}\geq
r\Big{)}\geq\inf_{\hat{u}}\max_{i=0,1}\mathbb{P}_{u_{i}}\Big{(}\Big{\lvert}\frac{\hat{u}}{u_{i}}-1\Big{\rvert}\geq
r\Big{)}\geq\inf_{T}\max_{i=0,1}\mathbb{P}_{u_{i}}(T\neq i),$

where the latter infimum is over all tests $T$. In the pseudo-metric case a
reduction considering the test
$T=\mathbbm{1}\\{d(\hat{u},u_{0})>d(\hat{u},u_{1})\\}$ and directly using the
triangle inequality likewise yields

$\inf_{\hat{u}}\sup_{u}\mathbb{P}_{u}\big{(}d(\hat{u},u)\geq
r\big{)}\geq\inf_{T}\max_{i=0,1}\mathbb{P}_{u_{i}}(T\neq i).$

It remains to lower bound the maximum probability of testing error by $1/4$.
Introducing the event $A=\big{\\{}\frac{p_{u_{0}}^{(n)}}{p_{u_{1}}^{(n)}}\geq
1/2\big{\\}}$, we see

$\mathbb{P}_{u_{0}}(T\not=0)\geq\mathbb{E}_{u_{1}}\big{[}\tfrac{p_{u_{0}}^{(n)}}{p_{u_{1}}^{(n)}}\mathbbm{1}_{A}T\big{]}\geq\tfrac{1}{2}[\mathbb{P}_{u_{1}}(T=1)-\mathbb{P}_{u_{1}}(A^{c})]$

Thus, writing $p_{1}=\mathbb{P}_{u_{1}}(T=1)$, we see

$\displaystyle\max(\mathbb{P}_{u_{0}}(T\not=0),\mathbb{P}_{u_{1}}(T\not=1))$
$\displaystyle\geq\max(\tfrac{1}{2}(p_{1}-\mathbb{P}_{u_{1}}(A^{c})),1-p_{1})$
$\displaystyle\geq\inf_{p\in[0,1]}\max(\tfrac{1}{2}(p-\mathbb{P}_{u_{1}}(A^{c})),1-p).$

The infimum is attained when $\frac{1}{2}(p-\mathbb{P}_{u_{1}}(A^{c}))=1-p$
and takes the value $\frac{1}{3}\mathbb{P}_{u_{1}}(A)$ so that

$\inf_{T}\max_{i=0,1}\mathbb{P}_{u_{i}}(T\neq
i)\geq\tfrac{1}{3}\mathbb{P}_{u_{1}}(A).$

Next observe

$\displaystyle\mathbb{P}_{u_{1}}(A)$
$\displaystyle=\mathbb{P}_{u_{1}}\big{[}\tfrac{p_{u_{1}}^{(n)}}{p_{u_{0}}^{(n)}}\leq
2\big{]}=1-\mathbb{P}_{u_{1}}^{n}\big{[}\log\big{(}\tfrac{p_{u_{1}}^{(n)}}{p_{u_{0}}^{(n)}}\big{)}>\log
2\big{]}\geq
1-\mathbb{P}_{\theta_{1}}^{n}\big{[}\lvert\log(\tfrac{p_{u_{1}}^{(n)}}{p_{u_{0}}^{(n)}})\rvert>\log
2\big{]}$ $\displaystyle\geq
1-(\log{2})^{-1}\mathbb{E}_{u_{1}}\big{\lvert}\log\big{(}\tfrac{p_{u_{1}}^{(n)}}{p_{u_{0}}^{(n)}}\big{)}\big{\rvert},$

where we have used Markov’s inequality to attain the final expression. By the
second Pinsker inequality (e.g. Proposition 6.1.7b in [22]), using the upper
bound on the Kullback–Leibler divergence we can continue the chain of
inequalities to see

$\mathbb{P}_{u_{1}}(A)\geq 1-(\log
2)^{-1}\big{[}K(p_{u_{1}}^{(n)},p_{u_{0}}^{(n)})+\sqrt{2K(p_{u_{1}}^{(n)},p_{u_{0}}^{(n)})}\big{]}\geq
1-(\log 2)^{-1}(\mu+\sqrt{2\mu}).$

For any $c<1/3$, we may choose $\mu=\mu(c)$ small enough that the testing
error satisfies

$\inf_{T}\max_{i=0,1}\mathbb{P}_{u_{i}}(T\neq
i)\geq\tfrac{1}{3}\Big{(}1-\frac{\mu+\sqrt{2\mu}}{\log 2}\Big{)}>c,$

and in particular a numerical calculation shows that $\mu=1+\tfrac{1}{4}\log
2-\sqrt{1+\tfrac{1}{2}\log 2}>1/100$ works for $c=1/4$. ∎

In view of Proposition 2, for any
$(\phi,\psi),(\tilde{\phi},\tilde{\psi})\in\Phi$ corresponding to strictly
positive emission densities, we have for $\phi_{2}$ and $\tilde{\phi}_{2}$
small enough that

$K(p_{\phi,\psi}^{(n)},p_{\tilde{\phi},\tilde{\psi}}^{(n)})\leq
Cn\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})^{2},$

where $C>0$ is a constant depending only on $K$ and a lower bound for the
emission densities. We remark that for all the hypotheses we will exhibit
below, we will have that $\phi_{2}$ and $\tilde{\phi}_{2}$ are of order
$\epsilon$, which is upper bounded by $\epsilon_{1}$ by assumption, so that
choosing the latter small enough the above bound on
$K(p_{\phi,\psi}^{(n)},p_{\tilde{\phi},\tilde{\psi}}^{(n)})$ will apply. Then,
to prove Item 1, it suffices to apply Lemma 2 to $u=1-\phi_{1}^{2}$ and prove
the existence of parameters
$(\phi,\psi),(\tilde{\phi},\tilde{\psi})\in\Phi_{L}(\delta,\epsilon,\zeta)$
satisfying for small enough $c_{1}>0$ and some $c_{2}>0$

$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq
c_{1}/\sqrt{n},\quad\text{and}\quad\Big{\lvert}\frac{1-\tilde{\phi}_{1}^{2}}{1-\phi_{1}^{2}}-1\Big{\rvert}\geq
c_{2}/\sqrt{n\delta^{2}\epsilon^{4}\zeta^{6}}$ (37)

which will give the lower bound on the absolute risk. Regarding the relative
risk, we then note that for any $a\geq 0$, since $\lvert\phi_{1}\rvert\leq 1$
and $1-\phi_{1}^{2}\geq\delta,$ so that we may assume the same of
$\hat{\phi}_{1}$, we have

$\displaystyle\mathbb{P}_{\phi,\psi}(\min(\lvert\hat{\phi}_{1}-\phi_{1}\rvert,\lvert\hat{\phi}_{1}+\phi_{1}\rvert)\geq
a)$
$\displaystyle\geq\mathbb{P}_{\phi,\psi}(\lvert(1-\hat{\phi}_{1}^{2})-(1-\phi_{1}^{2})\rvert\geq
2a)$
$\displaystyle\geq\mathbb{P}_{\phi,\psi}(\lvert(1-\hat{\phi}_{1}^{2})/(1-\phi_{1}^{2})-1\rvert\geq
2a/\delta).$

(See also equation 36 for a similar calculation with $\phi_{2}$.)

Similar conditions to (37) suffice for proving the other parts of Theorem 3
and we proceed now to verifying the existence of suitable parameters
$(\phi,\psi)$ and $(\tilde{\phi},\tilde{\psi})$, with the help of the
following lemma.

######  Lemma 3.

For a given $\phi$, assume conditions (6) and (7) and assume that
$\phi_{3}\leq\sqrt{2\lfloor K/2\rfloor}/(2K)$. Then there exists $\psi$ such
that $(\phi,\psi)$ lies in $\Phi_{L}$ and the corresponding emission densities
$f_{0},f_{1}$ are bounded below by some constant $c=c(K)>0$.

In particular, for $\lvert\phi_{1}\rvert\leq 1-3\delta$,
$\epsilon\leq\phi_{2}\leq\min(1/3,1-L)$, $\zeta\leq\phi_{3}\leq 2\zeta$, then
such a $\psi$ exists under the compatibility condition (3).

###### Proof.

Take

$\psi_{1}(k)=1/K,\quad\psi_{2}(k)=(2\lfloor
K/2\rfloor)^{-1/2}(\mathbbm{1}\\{k\textnormal{ odd,
}k<K\\}-\mathbbm{1}\\{k\textnormal{ even}\\}),\quad k\leq K.$

Under the assumed condition on $\phi_{3}$ and recalling that
$\lvert\phi_{1}\rvert\leq 1$ by assumption, we observe from the expressions
for $f_{0},f_{1}$ given in Remark 4 that these are lower bounded by $1/(2K)$.
In the particular case, one simply notes that all the conditions hold for such
$\phi$. ∎

#### Proof of Items 1 and 3

We prove the lower bounds for estimating $\phi_{1}$ and $\phi_{3}$ together.
For some small constant $c>0$, set $R=c\epsilon^{-2}\zeta^{-3}n^{-1/2}$ and,
writing $S=(2-6\delta-R)R/(6\delta-9\delta^{2})$, set

$\displaystyle\phi$ $\displaystyle=(1-3\delta,\epsilon,\zeta\sqrt{1+S}),$
$\displaystyle\tilde{\phi}$ $\displaystyle=(1-3\delta-R,\epsilon,\zeta).$

Recalling the definition $r(\phi)=(1-\phi_{1}^{2})\phi_{2}\phi_{3}^{2}/4$, the
choice of $\phi_{3}$ ensures that $r(\phi)=r(\tilde{\phi})$, and we note that
under the assumptions of the theorem we have $R\leq\delta\leq 1/6$ so that
$S\leq R/\delta\leq 1$ and $\zeta\leq\phi_{3}\leq 2\zeta$. By Lemma 3 there
exists $\psi$ such that $(\phi,\psi),(\tilde{\phi},\psi)\in\Phi_{L}$ and for
this $\psi$ we see that

$\rho(\phi,\psi;\tilde{\phi},\psi)=\lvert\phi_{1}\phi_{2}\phi_{3}r(\phi)-\tilde{\phi}_{1}\tilde{\phi}_{2}\tilde{\phi}_{3}r(\tilde{\phi})\rvert=\phi_{2}r(\phi)\lvert\phi_{1}\phi_{3}-\tilde{\phi}_{1}\tilde{\phi}_{3}\rvert.$

Using that $\sqrt{1+t}\leq 1+t$ for $t\geq 0$ we have

$\lvert\phi_{1}\phi_{3}-\tilde{\phi}_{1}\tilde{\phi}_{3}\rvert=(1-3\delta)\zeta(\sqrt{1+S}-1)+R\zeta\leq(S+R)\zeta\leq
2R\zeta/\delta,$

hence since $r(\phi)=(6\delta-9\delta^{2})\epsilon\zeta^{2}(1+S)/4\leq
3\delta\epsilon\zeta^{2}$, we obtain

$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq 6\epsilon^{2}\zeta^{3}R\leq
6cn^{-1/2}.$

Recalling that $R\leq\delta\leq 1/6$ and that $r(\phi)=r(\tilde{\phi})$ one
calculates

$\frac{1-\tilde{\phi}_{1}^{2}}{1-\phi_{1}^{2}}-1=S\geq R/(12\delta).$

For $c$ small enough we see that the conditions in equation 37 are satisfied,
yielding the claimed bound for estimating $\phi_{1}$.

To prove the lower bound for estimating $\phi_{3}$ it suffices to lower bound
$\lvert\phi_{3}/\tilde{\phi}_{3}-1\rvert$. Here we use the bound
$\sqrt{1+x}-1\geq x/(2\sqrt{1+x})\geq x/(2\sqrt{2})$ for $0\leq x\leq 1$ to
see for a constant $c^{\prime}>0$ that

$\lvert\phi_{3}/\tilde{\phi}_{3}-1\rvert\geq c^{\prime}R/\delta.$

The bound for $\phi_{3}$ follows from applying Lemma 2.

#### Proof of Item 2

For a constant $c>0$, define $R=c\delta^{-1}\epsilon^{-1}\zeta^{-2}n^{-1/2},$
define $\phi,\tilde{\phi}$ by

$\displaystyle\phi$
$\displaystyle=(1-3\delta,\epsilon,\zeta(1+R/\epsilon)^{1/2})$
$\displaystyle\tilde{\phi}$ $\displaystyle=(1-3\delta,\epsilon+R,\zeta),$

and observe that by construction $r(\phi)=r(\tilde{\phi})$. Noting that
$\phi_{2}\leq 2\epsilon\leq 1-L$ and $\phi_{3}\leq 2\zeta$ because the
assumptions of Theorem 3 ensure that $R\leq\epsilon\leq 1/3$, we deduce using
Lemma 3 that there exists some $\psi=\tilde{\psi}$ such that
$(\phi,\psi),(\tilde{\phi},\tilde{\psi})\in\Phi_{L}(\delta,\epsilon,\zeta)$.

Next observe, using that $(1+x)^{1/2}\leq 1+x$,

$\phi_{1}\lvert\phi_{2}\phi_{3}-\tilde{\phi}_{2}\tilde{\phi}_{3}\rvert\leq\lvert\phi_{2}\rvert\lvert\phi_{3}-\tilde{\phi}_{3}\rvert+\lvert\tilde{\phi}_{3}\rvert\lvert\phi_{2}-\tilde{\phi}_{2}\rvert=\epsilon\zeta(\sqrt{1+R/\epsilon}-1)+\zeta
R\leq 2\zeta R\leq R,$

the last inequality following from the fact that under the compatibility
condition (3) we have $\zeta\leq 1/2$. We deduce

$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})=r(\phi)\max(\lvert\phi_{2}-\tilde{\phi}_{2}\rvert,\lvert\phi_{1}\phi_{2}\phi_{3}-\tilde{\phi}_{1}\tilde{\phi}_{2}\tilde{\phi}_{3}\rvert)=Rr(\phi).$

Again using that $\phi_{3}\leq 2\zeta$ and noting also that
$(1-\phi_{1}^{2})=6\delta-9\delta^{2}\leq 6\delta$, we see that for some
$C^{\prime}>0$ we have

$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq
C^{\prime}\delta\epsilon\zeta^{2}R\leq cC^{\prime}n^{-1/2}.$

As with Items 1 and 3, for $c$ small enough in the definition of $R$ we may
apply Lemma 2 to deduce the claimed lower bound since
$\lvert\tilde{\phi}_{2}/\phi_{2}-1\rvert=R/\epsilon$.

#### Proof of Item 4

Set $\phi=\tilde{\phi}=(0,\epsilon,\zeta)$, set, as in Lemma 3,

$\psi_{1}(k)=1/K,\quad\psi_{2}(k)=(2\lfloor
K/2\rfloor)^{-1/2}(\mathbbm{1}\\{k\textnormal{ odd,
}k<K\\}-\mathbbm{1}\\{k\textnormal{ even}\\}),\quad k\leq K,$

and define $\tilde{\psi}_{1}=\psi_{1}+cn^{-1/2}\psi_{2}$. Note that under the
compatibility condition (3) we have
$(\phi,\psi),(\tilde{\phi},\tilde{\psi})\in\Phi_{L}$ for $n$ larger than some
$C=C(K,c)$, or for all $n\geq 1$ if $c$ is small enough. Then

$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})=cn^{-1/2}$

and we apply Lemma 2 to deduce the result.

#### Proof of Item 5

Set $\phi=\tilde{\phi}=(1-3\delta,\epsilon,\zeta)$, choose
$\psi_{1}=\tilde{\psi}_{1}$ to be the uniform density on $\\{1,\dots,K\\}$. As
with the previous parts, an application of Lemma 2 will yield the theorem if
we can exhibit $\psi_{2},\tilde{\psi}_{2}$ such that the induced emission
densities are bounded below by some $c^{\prime}=c^{\prime}(K)>0$,
$\lVert\psi_{2}-\tilde{\psi}_{2}\rVert=R:=c(n\delta^{2}\epsilon^{2}\zeta^{4})^{-1/2}$
for some $c>0$,
$\operatorname{sgn}(\langle\psi_{2},\tilde{\psi}_{2}\rangle)=+1$, and
$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})\leq c_{1}n^{-1/2}$ for a small
constant $c_{1}$. Such a choice is possible, for a small enough constant $c$,
under the compatibility condition (3) and for
$n\delta^{2}\epsilon^{2}\zeta^{4}\geq 1$; for example, define $\psi_{2}$ as in
Lemma 3 by

$\psi_{2}(k)=(2\lfloor K/2\rfloor)^{-1/2}(\mathbbm{1}\\{k\textnormal{ odd,
}k<K\\}-\mathbbm{1}\\{k\textnormal{ even}\\}),\quad k\leq K,$

and, for $h$ defined by $h(1)=2^{-1/2}$, $h(3)=-2^{-1/2}$ and $h(k)=0$ for all
other $k$, define

$\tilde{\psi}_{2}=(\psi_{2}+\alpha h)/(1+\alpha),\quad\alpha=R/(2-R).$

This satisfies $\lVert\tilde{\psi}_{2}-\psi_{2}\rVert=R$,
$\lVert\tilde{\psi}_{2}\rVert=1$, $\langle\tilde{\psi}_{2},1\rangle=0$ and
$\langle\tilde{\psi}_{2},\psi_{2}\rangle\geq 0$. For $k\not\in\\{1,3\\}$ the
condition (8) of Remark 5 holds with $1/(2K)$ in place of $0$ on the right,
and for $k\in\\{1,3\\}$ a direct calculation shows that the condition with
$1/(4K)$ in on the right if $R$ is upper bounded by some
$c^{\prime}=c^{\prime}(K)$,which is the case for $c=c(K)$ sufficiently small.
Then

$\rho(\phi,\psi;\tilde{\phi},\tilde{\psi})=\lvert
r(\phi)\rvert\lVert\psi_{2}-\tilde{\psi}_{2}\rVert\leq\delta\epsilon\zeta^{2}R\leq
cn^{-1/2}.$

###  8.5 Proofs for Section 3

###### Proof of Theorem 1.

We begin with the upper bounds. From the inversion formulae in Remark 4 we
have

$\max(\lVert\hat{f}_{0}-f_{0}\rVert,\lVert\hat{f}_{1}-f_{1}\rVert)\leq\lVert\hat{\psi}_{1}-\psi_{1}\rVert+\tfrac{1}{2}\lVert\hat{\phi}_{1}\hat{\phi}_{3}\hat{\psi}_{2}-\phi_{1}\phi_{3}\psi_{2}\rVert+\tfrac{1}{2}\lVert\hat{\phi}_{3}\hat{\psi}_{2}-\phi_{3}\psi_{2}\rVert$

Recalling that $\lvert\hat{\phi}_{1}\rvert\leq 1$, that $0\leq\phi_{3}\leq
K^{1/2}$ and that $\lVert\psi_{2}\rVert=\lVert\hat{\psi}_{2}\rVert=1$, we
decompose the second term on the right, with an implicit decomposition of the
third term included:

$\displaystyle\lVert\hat{\phi}_{1}\hat{\phi}_{3}\hat{\psi}_{2}-\phi_{1}\phi_{3}\psi_{2}\rVert$
$\displaystyle\leq\lvert\hat{\phi}_{1}\rvert\lVert\hat{\phi}_{3}\hat{\psi}_{2}-\phi_{3}\psi_{2}\rVert+\lvert\phi_{3}\rvert\lvert\hat{\phi}_{1}-\phi_{1}\rvert$
$\displaystyle\leq\lvert\hat{\phi}_{3}-\phi_{3}\rvert+K^{1/2}\lVert\hat{\psi}_{2}-\psi_{2}\rVert+\phi_{3}\lvert\hat{\phi}_{1}-\phi_{1}\rvert.$

It follows that for some constant $C$ we have

$\max(\lVert\hat{f}_{0}-f_{0}\rVert,\lVert\hat{f}_{1}-f_{1}\rVert)\leq
C\max(\lVert\hat{\psi}_{1}-\psi_{1}\rVert,\lVert\hat{\psi}_{2}-\psi_{2}\rVert,\lvert\hat{\phi}_{3}-\phi_{3}\rvert,\phi_{3}\lvert\hat{\phi}_{1}-\phi_{1}\rvert).$

Applying Proposition 3 as in the proof of Theorem 2, one can show that for
some $C>0$

$\mathbb{P}_{\phi,\psi}\Big{(}\phi_{3}^{2}\lvert\hat{\phi}_{1}-\phi_{1}\rvert^{2}\geq\frac{Cx^{2}}{n\epsilon^{4}\zeta^{4}}\Big{)}\leq
e^{-x^{2}}.$

The upper bounds for estimating $f_{0}$ and $f_{1}$ then follow from Theorem
2.

Similarly, Remark 4 and the fact that $\lvert\phi_{2}\rvert\leq 1$ give

$\max(\lvert\hat{p}-p\rvert,\lvert\hat{q}-q\rvert)\leq\tfrac{1}{2}(1+\lvert\hat{\phi}_{1}\rvert)\lvert\hat{\phi}_{2}-\phi_{2}\rvert+\tfrac{1}{2}\lvert\hat{\phi}_{1}-\phi_{1}\rvert\lvert
1-\phi_{2}\rvert\leq
2\max(\lvert\hat{\phi}_{1}-\phi_{1}\rvert,\lvert\hat{\phi}_{2}-\phi_{2}\rvert).$

The upper bounds then again follow from Theorem 2.

For the lower bounds, writing $\theta(\phi,\psi)=(p,q,f_{0},f_{1})$ and
$\theta(\tilde{\phi},\tilde{\psi})=(\tilde{p},\tilde{q},\tilde{f}_{0},\tilde{f}_{1})$,
observe by Lemma 2 that it suffices to lower bound $\max(\lvert
p-\tilde{p}\rvert,\lvert q-\tilde{q}\rvert)$ and $\max(\lVert
f_{0}-\tilde{f}_{0}\rVert,\lVert f_{1}-\tilde{f}_{1}\rVert)$ corresponding to
choices of $(\phi,\psi),(\tilde{\phi},\tilde{\psi})$ made in the proof of
Theorem 3.

From the inversion formulae in Remark 4 we calculate, for any
$\phi,\tilde{\phi}$,

$2\max(\lvert p-\tilde{p}\rvert,\lvert q-\tilde{q}\rvert)\\\
\geq\max((1+\lvert\phi_{1}\rvert)\lvert\phi_{2}-\tilde{\phi}_{2}\rvert-\lvert
1-\tilde{\phi}_{2}\rvert\lvert\phi_{1}-\tilde{\phi}_{1}\rvert,\lvert\phi_{1}-\tilde{\phi}_{1}\rvert\lvert
1-\tilde{\phi}_{2}\rvert-(1-\lvert\phi_{1}\rvert)\lvert\phi_{2}-\tilde{\phi}_{2}\rvert).$
(38)

If $\delta>\epsilon\zeta$ set $\phi=(1-3\delta,\epsilon,\zeta(1+S)^{1/2})$ and
$\tilde{\phi}=(1-3\delta-R,\epsilon,\zeta)$, where
$R=c(n\epsilon^{4}\zeta^{6})^{-1/2}$ for some $c>0$ and where
$S\in[R/(12\delta),R/\delta]$ is, as in the proof of Theorem 3 Item 1, such
that $r(\phi)=r(\tilde{\phi})$. If $\delta\leq\epsilon\zeta$ instead set
$\phi=(1-3\delta,\epsilon,\zeta(1+R/\epsilon)^{1/2}),$
$\tilde{\phi}=(1-3\delta,\epsilon+R,\zeta)$ with
$R=c(n\epsilon^{2}\delta^{2}\zeta^{4})^{-1/2}$. In either case the proof of
Theorem 3 demonstrates that for suitable $\psi=\tilde{\psi}$ we have
$K(p^{(n)}_{\phi,\psi},p^{(n)}_{\tilde{\phi},\tilde{\psi}})\leq 1/100$ for $c$
small enough hence by Lemma 2

$\inf_{\check{\theta}}\sup_{\theta\in\Theta}\mathbb{P}_{\theta}\Big{(}\max(\lvert\check{p}-p\rvert,\lvert\check{q}-q\rvert)>c^{\prime}\max(\lvert
p-\tilde{p}\rvert,\lvert q-\tilde{q}\rvert)\Big{)}\geq 1/4.$

Inserting from equation 38 we conclude the bound in either case.

For $(f_{0},f_{1})$, again set $\phi=(1-3\delta,\epsilon,\zeta(1+S)^{1/2})$,
$\tilde{\phi}=(1-3\delta-R,\epsilon,\zeta)$ where
$R=c\epsilon^{-2}\zeta^{-3}n^{-1/2}$, and choose $\psi=\tilde{\psi}$ by Lemma
3. As with $p$ and $q$ we deduce that for some $c^{\prime}>0$ we have

$\inf_{\check{\theta}}\sup_{\theta\in\Theta}\mathbb{P}_{\theta}\Big{(}\max(\lVert\check{f}_{0}-f_{0}\rVert,\lVert\check{f}_{1}-f_{1}\rVert)>c^{\prime}\max(\lVert
f_{0}-\tilde{f}_{0}\rVert,\lVert f_{1}-\tilde{f}_{1}\rVert)\Big{)}\geq 1/4.$

Using the inversion formulae in Remark 4 and the fact that $\psi=\tilde{\psi}$
and $\lVert\psi_{2}\rVert=1$, one calculates

$2\max(\lVert f_{0}-\tilde{f}_{0}\rVert,\lVert
f_{1}-\tilde{f}_{1}\rVert)=\lvert\phi_{1}\phi_{3}-\tilde{\phi}_{1}\tilde{\phi}_{3}\rvert+\lvert\phi_{3}-\tilde{\phi}_{3}\rvert\geq\lvert\phi_{3}-\tilde{\phi}_{3}\rvert$

For the current choice of $\phi,\tilde{\phi}$, calculating as in proving
Theorem 3 Item 3, we have $\lvert\phi_{3}-\tilde{\phi}_{3}\rvert\geq C\zeta
R/\delta$ for some $C>0$ and we deduce the lower bound. ∎

###### Proof of Corollary 1.

It suffices to substitute $\alpha=e^{-x^{2}}$ into Theorem 1 and solve for
error equal to $E$, while ensuring that $x^{2}=\log(1/\alpha)$ is suitably
bounded. ∎

Acknowledgments
This work was supported by a public grant as part of the Investissement
d’avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH, and by Institut
Universitaire de France.

## References

  * [1] K. Abraham, I. Castillo, and É. Gassiat.  Multiple testing in nonparametric hidden markov models: An empirical Bayes approach.  arXiv:2101.03838, 2021.
  * [2] Kweku Abraham, Ismael Castillo, and Elisabeth Gassiat.  Multiple testing in nonparametric hidden markov models: An empirical bayes approach, 2021.
  * [3] F. Abramovich, Y. Benjamini, D. L. Donoho, and I. M. Johnstone.  Adapting to unknown sparsity by controlling the false discovery rate.  Ann. Statist., 34(2):584–653, 2006.
  * [4] G. Alexandrovich, H. Holzmann, and A. Leister.  Nonparametric identification and maximum likelihood estimation for hidden Markov models.  Biometrika, 103(2):423–434, 2016.
  * [5] E. S. Allman, C. Matias, and J. A. Rhodes.  Identifiability of parameters in latent structure models with many observed variables.  Ann. Statist., 37(6A):3099–3132, 2009.
  * [6] A. Anandumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky.  Tensor decompositions for learning latent variable models.  J. Mach. Learn. Res., 15:2773–2832, 2014.
  * [7] P. Andreoletti, D. Loukianova, and C. Matias.  Hidden Markov model for parameter estimation of a random walk in a Markov environment.  ESAIM Probab. Stat., 19:605–625, 2015.
  * [8] A. Becker and H. Holzmann.  Nonparametric identification in the dynamic stochastic block model.  IEEE Trans. Inform. Theory, 65(7):4335–4344, 2019.
  * [9] David Blackwell.  The entropy of functions of finite-state Markov chains.  In Transactions of the first Prague conference on information theory, Statistical decision functions, random processes held at Liblice near Prague from November 28 to 30, 1956, pages 13–20. Publishing House of the Czechoslovak Academy of Sciences, Prague, 1957.
  * [10] I. Castillo and É. Roquain.  On spike and slab empirical Bayes multiple testing.  Ann. Statist., 48(5):2548–2574, 2020.
  * [11] L. Couvreur and C. Couvreur.  Wavelet based non-parametric HMMs: theory and methods.  In ICASSP ’00 Proceedings, pages 604–607, 2000.
  * [12] Y. De Castro, É. Gassiat, and C. Lacour.  Minimax adaptive estimation of nonparametric hidden Markov models.  J. Mach. Learn. Res., 17:Paper No. 111, 43, 2016.
  * [13] Y. De Castro, É. Gassiat, and S. Le Corff.  Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models.  IEEE Trans. Inform. Theory, 63(8):4758–4777, 2017.
  * [14] L. Devroye, L. Györfi, and G. Lugosi.  A probabilistic theory of pattern recognition, volume 31.  Springer Science & Business Media, 2013.
  * [15] Minh N. Do.  Fast approximation of Kullback–Leibler distance for dependence trees and hidden Markov models.  IEEE Signal Process. Lett., 10(4):115–118, 2003.
  * [16] N. Doss, Y. Wu, P. Yang, and H. H. Zhou.  Optimal estimation of high-dimensional gaussian mixtures.  arXiv:2002.05818, 2020.
  * [17] Cheng-Der Fuh and Yajun Mei.  Quickest change detection and Kullback-Leibler divergence for two-state hidden Markov models.  IEEE Trans. Signal Process., 63(18):4866–4878, 2015.
  * [18] É. Gassiat, A. Cleynen, and S. Robin.  Inference in finite state space non parametric hidden Markov models and applications.  Stat. Comput., 26(1-2):61–71, 2016.
  * [19] É. Gassiat, S. Le Corff, and L. Lehéricy.  Deconvolution with unknown noise distribution is possible for multivariate signals.  arXiv:2006.14226, 2020.
  * [20] É. Gassiat, S. Le Corff, and L. Lehéricy.  Identifiability and consistent estimation of nonparametric translation hidden Markov models with general state space.  J. Mach. Learn. Res., 21:Paper No. 115, 40, 2020.
  * [21] É. Gassiat and R. van Handel.  The local geometry of finite mixtures.  Trans. Amer. Math. Soc., 366(2):1047–1072, 2014.
  * [22] Evarist Giné and Richard Nickl.  Mathematical foundations of infinite-dimensional statistical models.  Cambridge Series in Statistical and Probabilistic Mathematics, [40]. Cambridge University Press, New York, 2016.
  * [23] P. Heinrich and J. Kahn.  Strong identifiability and optimal minimax rates for finite mixture estimation.  Ann. Statist., 46(6A):2844–2870, 2018.
  * [24] D. Hsu, S. M. Kakade, and T. Zhang.  A spectral algorithm for learning hidden Markov models.  J. Comput. System Sci., 78(5):1460–1480, 2012.
  * [25] M. F. Lambert, J. P. Whiting, and A. V. Metcalfe.  A non-parametric hidden Markov model for climate state identification.  Hydrology and Earth System Sciences, 7 (5):652–667, 2003\.
  * [26] L. Le Cam.  Asymptotic methods in statistical decision theory.  Springer-Verlag, New York, 1986.
  * [27] F. Lefèvre.  Non-parametric probability estimation for HMM-based automatic speech recognition.  Computer Speach and Language, 17:113–136, 2003.
  * [28] L. Lehéricy.  State-by-state minimax adaptive estimation for nonparametric hidden Markov models.  J. Mach. Learn. Res., 19:Paper No. 39, 46, 2018.
  * [29] L. Lehéricy.  Consistent order estimation for nonparametric hidden Markov models.  Bernoulli, 25(1):464–498, 2019.
  * [30] L. Lehéricy.  Nonasymptotic control of the MLE for misspecified nonparametric hidden Markov models.  arXiv:1807.03997, 2018.
  * [31] Jun Luo and Dongning Guo.  On the entropy rate of hidden Markov processes observed through arbitrary memoryless channels.  IEEE Trans. Inform. Theory, 55(4):1460–1467, 2009.
  * [32] C. Matias and V. Miele.  Statistical clustering of temporal networks through a dynamic stochastic block model.  J. R. Stat. Soc. Ser. B. Stat. Methodol., 79(4):1119–1141, 2017\.
  * [33] J. Ollion, C. Ollion, É. Gassiat, L. Lehéricy, and S. Le Corff.  Joint self-supervised blind denoising and noise estimation.  arXiv:2102.08023, 2021.
  * [34] D. Paulin.  Concentration inequalities for Markov chains by Marton couplings and spectral methods.  Electron. J. Probab., 20:no. 79, 32, 2015.
  * [35] N. Rau, J. Lucke, and A. K. Hartmann.  Phase transition for parameter learning of Hidden Markov Models.  arXiv:2003.11680, 2020.
  * [36] M. Sesia, C. Sabatti, and E. J. Candès.  Gene hunting with hidden Markov model knockoffs.  Biometrika, 106(1):1–18, 2019.
  * [37] L. Shang and K.P. Chan.  Nonparametric discriminant HMM and application to facial expression recognition.  In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 2090–2096, 2009.
  * [38] Jorge Silva and Shrikanth Narayanan.  Upper bound Kullback-Leibler divergence for transient hidden Markov models.  IEEE Trans. Signal Process., 56(9):4176–4188, 2008.
  * [39] Wenguang Sun and T. Tony Cai.  Large-scale multiple testing under dependence.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 71(2):393–424, 2009.
  * [40] A. B. Tsybakov.  Introduction to nonparametric estimation.  Springer-Verlag, New York, 2009.
  * [41] S. Volant, C. Bérard, M.-L. Martin-Magniette, and S. Robin.  Hidden Markov Models with mixtures as emission distributions.  Statistics and Computing, pages 1–12, 2013.
  * [42] C. Yau, O. Papaspiliopoulos, G. O. Roberts, and C. Holmes.  Bayesian non-parametric hidden Markov models with applications in genomics.  J. R. Stat. Soc. Ser. B Stat. Methodol., 73(1):37–57, 2011.