Clustering consistency with
Dirichlet process mixtures

Filippo Ascolania,b<EMAIL_ADDRESS>
Antonio Lijoia,b<EMAIL_ADDRESS>
Giovanni Rebaudob,c<EMAIL_ADDRESS>
Giacomo Zanellaa,b<EMAIL_ADDRESS>
aDepartment of Decision Sciences, Bocconi University,

via Röentgen 1, 20136 Milan, Italy bBocconi Institute for Data Science and
Analytics, Bocconi University,

Via Röntgen 1, 20136 Milan, Italy cDepartment of Statistics and Data Sciences,
University of Texas at Austin,

105 East 24th Street D9800, Austin, TX 78712, USA

Abstract

Dirichlet process mixtures are flexible non-parametric models, particularly
suited to density estimation and probabilistic clustering. In this work we
study the posterior distribution induced by Dirichlet process mixtures as the
sample size increases, and more specifically focus on consistency for the
unknown number of clusters when the observed data are generated from a finite
mixture. Crucially, we consider the situation where a prior is placed on the
concentration parameter of the underlying Dirichlet process. Previous findings
in the literature suggest that Dirichlet process mixtures are typically not
consistent for the number of clusters if the concentration parameter is held
fixed and data come from a finite mixture. Here we show that consistency for
the number of clusters can be achieved if the concentration parameter is
adapted in a fully Bayesian way, as commonly done in practice. Our results are
derived for data coming from a class of finite mixtures, with mild assumptions
on the prior for the concentration parameter and for a variety of choices of
likelihood kernels for the mixture.

Key Words: Asymptotic; Bayesian nonparametric; Consistency; Clustering;
Dirichlet process mixture; Number of components.

Short/Running Title: Clustering consistency with DPM

##  1 Introduction

Bayesian nonparametric methods have experienced a huge development in the last
two decades, often standing out for their flexibility and coherent
probabilistic foundations; see the monographs by Müller et al. (2017) and
Ghosal and Van Der Vaart (2017) for recent stimulating accounts. The
cornerstone of Bayesian nonparametrics is the model based on the Dirichlet
process (Ferguson, 1973), which can be expressed as
$X_{i}\mid\tilde{P}\stackrel{{\scriptstyle\mbox{\scriptsize{iid}}}}{{\sim}}\tilde{P}$
and $\tilde{P}\sim\text{DP}(\alpha,Q_{0})$, where $\alpha>0$ is the
_concentration parameter_ and $Q_{0}$ is the _baseline distribution_ over the
sample space $(\mathbb{X},\mathcal{X})$. The success of the Dirichlet process
in actual implementations of the Bayesian approach to nonparametric problems
is mostly due to its mathematical tractability, which is highlighted by
conjugacy, and flexibility, which is assessed in terms of its large
topological support.

Since $\tilde{P}$ is almost surely discrete, if one wishes to model continuous
data one may convolve it with a density kernel $k$ parametrized by a latent
variable $\theta$ that is drawn from a Dirichlet process. This yields the
popular Dirichlet process mixture (Lo, 1984), which exhibits appealing
asymptotic properties in the context of density estimation: in several
relevant cases, the posterior distribution concentrates at the true data-
generating density at the minimax-optimal rate, up to a logarithmic factor, as
the sample size increases (Ghosal et al., 1999; Ghosal and Van der Vaart,
2007). Such a model and mevery of its variants are widely used across
scientific areas, thanks also to the availability of a wide variety of
efficient computational methods to perform inference, see for instance Escobar
and West (1995, 1998); MacEachern and Müller (1998); Neal (2000); Blei and
Jordan (2006).

Thanks to the discreteness of the Dirichlet process, the latent parameters
$\theta_{i}$’s exhibit ties with positive probability. Hence, the Dirichlet
process mixture model is also routinely used to perform clustering since it
partitions observations into groups based on whether their corresponding
latent parameters $\theta_{i}$ coincide or not. The ubiquitous use of
Dirichlet process mixtures for clustering motivates the interest in the
asymptotic behaviour of the posterior distribution of the underlying
partition, and in particular in the inferred number of clusters (i.e.
subpopulations), as the number of observations increases. Nguyen (2013) showed
posterior consistency of the mixing distribution $\tilde{P}$ under general
conditions. However, this does not imply consistency for the number of
clusters, due to the use of the Wasserstein distance. Indeed, Miller and
Harrison (2013) proved that Dirichlet process mixtures are not consistent for
the number of components when data are generated from a mixture with a single
standard normal component. See also Miller and Harrison (2014) for extensions.
These results, however, are derived under the assumption that the
concentration parameter $\alpha$ is known and fixed. This is crucial because
the clustering behaviour of Dirichlet process mixtures is governed by the
choice of $\alpha$. Indeed, under the Dirichlet process mixture model, the
prior probability of observing ties is a function solely of $\alpha$, since
$\text{pr}(\theta_{i}=\theta_{j})=1/(\alpha+1)$.

In order to have a more flexible distribution on the clustering of the data,
in most implementations of the Dirichlet process mixture a prior $\pi$ for
$\alpha$ is specified, leading to a mixing measure that is itself a mixture in
the sense of Antoniak (1974). Here we show that introducing such a prior has a
major impact on the asymptotic behaviour of the number of clusters, as
Dirichlet process mixtures can be consistent for the number of clusters. We
provide consistency results under fairly general conditions on $\pi$ and for a
moderately large class of kernels $k$, including uniform and truncated normal
distributions. Following Miller and Harrison (2013), we focus on data-
generating mixtures with a single component. Our results also extend to the
more general case of finite mixtures with multiple components, when a suitable
separation assumption between the elements of the mixtures is fulfilled.
Crucially, we prove consistency for cases where using a non-random $\alpha$
yields inconsistency, thus suggesting that a hyperprior may be beneficial even
beyond the cases considered here. We stress that the framework we study is
arguably closer to the way Dirichlet process mixtures are used in practice,
compared to holding $\alpha$ fixed.

We note that studying an asymptotic regime where the data-generating truth is
a mixture with a finite and fixed number of components entails some degree of
model misspecification. Indeed, Dirichlet process mixtures are nonparametric
models with an infinite number of components or, in other words, a number of
clusters growing with the size of the dataset. Thus, our results can be
interpreted as a form of robustness of the prior: if the number of components
of the data-generating is finite, it can still be recovered by adapting
appropriately the value of $\alpha$, despite the prior is concentrated on
mixtures with infinitely mevery components. In particular we show that, under
all the data generation mechanisms we consider in the next sections, the
posterior distribution of $\alpha$ converges to a point mass at 0 at a
specific rate, which is crucial to ensure consistency. See Section 5 for more
discussion and some related literature.

##  2 Dirichlet process mixtures and random partitions

Henceforth, we will be focusing on Dirichlet process mixture models with a
prior on the concentration parameter, namely

$X_{i}|\theta_{i}\stackrel{{\scriptstyle\mbox{\scriptsize{ind}}}}{{\sim}}k(\cdot|\theta_{i}),\quad\theta_{i}\mid\tilde{P}\stackrel{{\scriptstyle\mbox{\scriptsize{iid}}}}{{\sim}}\tilde{P},\quad\tilde{P}\mid\alpha\sim\text{DP}(\alpha,Q_{0}),\quad\alpha\sim\pi,$
(1)

where $k(\,\cdot\,|\theta)$ is some density function, for every $\theta$.
Since we are interested in the distribution of the number of clusters, it is
reasonable to rewrite (1) in terms of the distribution on partitions, related
to the so-called Chinese restaurant process. For every pair of natural numbers
$(n,s)$ such that $s\leq n$, denote with $\tau_{s}(n)$ the set of partitions
of $\\{1,\ldots,n\\}$ into $s$ non empty subsets. Conditionally on $\alpha$,
the sequence $(\theta_{i})_{i\geq 1}$ induces a prior distribution on the
space of partitions of $\mathds{N}$ that, for every $n\geq 2$, is
characterized by

$\text{pr}(A\mid\alpha)=\dfrac{\alpha^{s}}{\alpha^{(n)}}\prod_{j=1}^{s}(a_{j}-1)!,\quad(A=\\{A_{1},\ldots,A_{s}\\}\in\tau_{s}(n),s\leq
n),$ (2)

where $\alpha^{(n)}=\alpha\cdots(\alpha+n-1)$ is the ascending factorial and
$a_{j}=|A_{j}|$ stands for the cardinality of set $A_{j}$. Conditionally on
the partition $A$, the probability distributions of the data
$X_{1:n}=(X_{1},\dots,X_{n})$ and of the cluster-specific parameters
$\hat{\theta}_{1:s}=(\hat{\theta}_{1},\ldots,\hat{\theta}_{s})$ are

$\text{pr}(X_{1:n}\mid\hat{\theta}_{1:s},A)=\prod_{j=1}^{s}\prod_{i\in
A_{j}}k(X_{i}\mid\hat{\theta}_{j}),\quad\text{pr}(\hat{\theta}_{1:s}\mid
A,\alpha)=\text{pr}(\hat{\theta}_{1:s}\mid
A)=\prod_{j=1}^{s}q_{0}(\hat{\theta}_{j}).$ (3)

The number of clusters in a sample of size $n$ is denoted by $K_{n}$ and under
(1) it has the following prior distribution

$\text{pr}(K_{n}=s)=\int\sum_{A\in\tau_{s}(n)}\text{pr}(A\mid\alpha)\pi(\mathrm{d}\alpha).$

Since we are concerned with the large sample properties of
$\text{pr}(K_{n}=s\mid X_{1:n})$, we focus on the joint distribution of the
vector $(X_{1:n},K_{n})$ which, for every
$x_{1:n}=(x_{1},\dots,x_{n})\in\mathbb{X}^{n}$, is given by

$\text{pr}(X_{1:n}=x_{1:n},K_{n}=s)=\sum_{A\in\tau_{s}(n)}\text{pr}(A)\prod_{j=1}^{s}m(x_{A_{j}}),$
(4)

where pr$(A)=\int\mbox{pr}(A|\alpha)\,\pi(\mathrm{d}\alpha)$ and
$m(x_{A_{j}})=\int\prod_{i\in
A_{j}}k(x_{i}\mid\theta)q_{0}(\theta)\mathrm{d}\theta$ is the marginal
likelihood for the subset of observations identified by $A_{j}$, given that
they are clustered together. We study the asymptotic behaviour of the
posterior induced by model (1) when the observations are independent and
identically distributed samples from a finite mixture, that is we assume the
following data generation mechanism

$X_{i}\stackrel{{\scriptstyle\mbox{\scriptsize{iid}}}}{{\sim}}P=\sum_{j=1}^{t}p_{j}R_{j},\quad(i=1,2,\dots),$
(5)

where, for every $t\geq 1$, the $R_{j}$’s are distinct probability measures on
$\mathbb{X}$ and the $p_{j}$’s are probability weights, i.e. $p_{j}\in(0,1)$
for every $j$ and $\sum_{j}p_{j}=1$. We will let $P^{(n)}$ and $P^{(\infty)}$
be the product probability measures induced on $\mathbb{X}^{n}$ and
$\mathbb{X}^{\infty}$ respectively, and denote (5) by $X_{1:\infty}\sim
P^{(\infty)}$. In the following, we will consider each $R_{j}$ to be dominated
by a suitable measure and denote the resulting density by
$f_{j}(\cdot):=f(\cdot\mid\theta_{j}^{\ast})$. We say that model in (1) is
_well-specified_ for $P$ if $k(\cdot|\theta)=f(\cdot\mid\theta)$, that is if
the data-generating distribution is a mixture of kernels belonging to the same
parametric family that defines (1).

We say that posterior consistency for the number of clusters holds if
$\text{pr}(K_{n}=t\mid X_{1:n})\to 1$ as $n\to\infty$ in
$P^{(\infty)}$-probability. Note that the conditional probability
$\text{pr}(K_{n}=t\mid X_{1:n})$ is defined with respect to the model in (1),
while the convergence in probability is with respect to the data-generating
process $X_{1:\infty}\sim P^{(\infty)}$. Since $\text{pr}(K_{n}=t\mid
X_{1:n})$ lies between 0 and 1, convergence in $P^{(\infty)}$-probability is
equivalent to convergence in $L^{1}$ with respect to $P^{(\infty)}$ and thus
we could equivalently define consistency in terms of $L^{1}$ convergence.

##  3 Main consistency results

The investigation of the asymptotics of the number of clusters $K_{n}$,
induced by the model in (1), will rely on the following assumptions on the
prior $\pi$ of $\alpha$

  1. $A1.$

_Absolute continuity_ : $\pi$ is absolutely continuous with respect to the
Lebesgue measure and its density is still denoted as $\pi$;

  2. $A2.$

_Polynomial behaviour around the origin_ : $\exists\,\epsilon$, $\delta$,
$\beta$ such that $\forall\alpha\in(0,\epsilon)$ it holds
$\frac{1}{\delta}\alpha^{\beta}\leq\pi(\alpha)\leq\delta\alpha^{\beta}$;

  3. $A3.$

_Subfactorial moments_ : $\exists\,D,\nu,\rho>0$ such that
$\int\alpha^{s}\pi(\alpha)\,d\alpha<D\rho^{-s}\Gamma(\nu+s+1)$ for every
$s\geq 1$.

The first two assumptions are sufficient to study the posterior moments of
$\alpha$, conditional to the number of groups $K_{n}$, as will be clarified in
Proposition 3. Assumption $A3$, instead, will be useful specifically for
consistency purposes: the minimum value of $\rho$ required to achieve
consistency depends on the problem at hand, that is on the specific choice of
$P$ in (5) and $k$ in (1), as will be stated in Theorems 2 and 3. Assumptions
$A1$-$A3$ are satisfied by common families of distributions, as displayed in
the next lemma.

######  Lemma 1.

The following choices of $\pi$ satisfy assumptions $A1$, $A2$ and $A3$ (for a
fixed $\rho>0$)

  * (1)

every distribution with bounded support that satisfies assumptions $A1$ and
$A2$, such as the uniform distribution over $(0,c)$, with $c>0$;

  * (2)

The Generalized Gamma distribution with density proportional to
$\alpha^{d-1}e^{-\left(\frac{\alpha}{a}\right)^{p}}$, provided that $p>1$;

  * (3)

The Gamma distribution with shape $\nu$ and rate $\rho$.

Note that the rate parameter of the Gamma distribution corresponds to the
quantity $\rho$ in assumption $A3$.

###  3.1 General consistency result for location families
with bounded support

For our general result we consider kernels of the form

$\displaystyle k(x\mid\theta)$ $\displaystyle=g(x-\theta)$
$\displaystyle(x\in\mathbb{R}),$ (6)

where $c>0$ and $\theta\in\mathbb{R}$ is a location parameter. Here $g$ is a
density function on the real line satisfying the following assumptions

  1. $B1.$

$g$ is strictly positive on some interval $[a,b]$ and 0 elsewhere;

  2. $B2.$

$g$ is differentiable with bounded derivative in $(a,b)$;

  3. $B3.$

The base measure $Q_{0}$ is absolutely continuous with respect to the Lebesgue
measure, and its density $q_{0}$ is bounded.

The above assumptions essentially require that the kernel is a location-family
distribution with positive density on a bounded support. The class is fairly
general and it includes, as relevant special cases, the uniform distribution
and the truncated Gaussian distribution, among others.

When considering a mixture of the kernels in (6) as data generation mechanism
satisfying $B1$–$B3$, with true parameters
$\theta^{*}=(\theta_{1}^{*},\dots,\theta_{t}^{*})$, we say that $\theta^{*}$
is _completely separated_ if $|\theta_{j}^{*}-\theta_{k}^{*}|>b-a$, for every
$j\neq k$. This assumption is somewhat restrictive, but sufficient to prove
that the addition of a prior on $\alpha$ may solve the inconsistency issue.
Indeed, we have the following general consistency result.

######  Theorem 1.

Suppose $k$ and $q_{0}$ satisfy assumptions $B1$–$B3$. If $\pi$ satisfies
assumptions $A1$–$A3$ with $\rho$ high enough then, for every $P$ as in (5)
with $t\in\\{1,2,\dots\\}$, $f_{j}=k(\cdot|\theta^{*}_{j})$, $\theta^{*}$
completely separated and $\theta^{*}_{j}$ belonging to the interior support of
$Q_{0}$ for every $j$, we have

$\text{pr}(K_{n}=t\mid X_{1:n})\to 1$

as $n\to\infty$ in $P^{(\infty)}$-probability. On the contrary, if
$\pi(\alpha)=\delta_{\alpha^{*}}(\alpha)$, with $\alpha^{*}>0$, then

$\lim\sup\text{pr}(K_{n}=t\mid X_{1:n})<1$

as $n\to\infty$ in $P^{(\infty)}$-probability.

As discussed above, the minimum value of $\rho$ needed depends on the specific
function $g$ and prior distribution $Q_{0}$. Therefore, a prior on the
concentration parameter yields consistency when the true data generating
distribution meets a condition of complete separability, that informally
amounts to having cluster locations sufficiently distinct. Note that this
condition is automatically satisfied when $t=1$. We additionally show that,
even under such an assumption, the Dirichlet process mixture model with fixed
$\alpha$ still fails to be consistent at the number of clusters. Hence, a
prior on $\alpha$ is crucial to overcome issues with learning the true number
of clusters as the sample size increases.

Moreover, the posterior mass on a smaller number of clusters than the truth
vanishes, as explained in the next proposition. The latter holds under mild
assumptions on model (1), satisfied either by bounded distributions as above
or for instance by the Gaussian kernel.

######  Proposition 1.

Let $P$ be as in (5), with true parameters
$\theta^{*}_{1},\dots,\theta^{*}_{t}$. Let $\theta_{j}^{*}$ belong to the
support of $Q_{0}$ for every $j=1,\dots,t$ and let $k$ satisfy assumptions
$B1$–$B3$ above or $H1$–$H4$ in the supplementary material. Then

$\text{\rm pr}(K_{n}<t\mid X_{1:n})\to 0$ (7)

in $P^{(\infty)}$-probability as $n\to\infty$.

###  3.2 Consistency on specific examples

Theorem 1 requires $\rho$ in assumption $A3$ to be high enough, depending on
the specific formulation of the model. In order to provide an example, we
focus on the case of uniform kernel and $t=1$, that is

$f=\text{Unif}(\theta^{\ast}-c,\theta^{\ast}+c),\quad
k(\cdot|\theta)=\text{Unif}(\theta-c,\theta+c),\quad
q_{0}=\text{Unif}(\theta^{\ast}-c,\theta^{\ast}+c),$ (8)

where $\theta^{\ast}\in\mathbb{R}$ is a fixed location parameter and $c>0$. In
this setting the marginal distribution is available and with a suitable
application of Hölder’s inequality one can prove consistency for specific
values of $\rho$.

######  Theorem 2.

Consider $f$, $k$ and $q_{0}$ as in (8), and assume $\pi$ satisfies $A1$–$A3$
(with $\rho\geq 38$). Then

$\text{pr}(K_{n}=1\mid X_{1:n})\to 1$

as $n\to\infty$ in $P^{(\infty)}$-probability.

As a second example, we move beyond bounded kernels and consider a simple, yet
interesting, case. More precisely, we specialize model (1) to Gaussian kernels
and assume constant data, equal to some fixed real number $\theta^{\ast}$,
setting

$f=\delta_{\theta^{\ast}},\quad k(\cdot|\theta)=\text{N}(\theta,1),\quad
q_{0}=\text{N}(0,1).$ (9)

Unlike the other examples, this case is not well-specified, as
$k(\cdot|\theta)\neq f(\cdot)$ for every $\theta$. This makes the definition
of true or data-generating number of clusters more delicate. Nonetheless,
being an example with constant data, one would hope the posterior of the
number of clusters to concentrate on one cluster. However, even in such a
limiting case, Miller and Harrison (2013) show that under (1) with fixed
concentration parameter $\text{pr}(K_{n}=1|X_{1:n})$ does not converge to $1$
as $n$ diverges.

Once again, placing a prior on $\alpha$ impacts the posterior asymptotic
behaviour of $K_{n}$ and one achieves consistency, as detailed in the next
theorem.

######  Theorem 3.

Consider $(f,k,q_{0})$ as in (9) and assume $\pi$ satisfies $A1$–$A3$ (with
$\rho>16$). Then

$\text{pr}(K_{n}=1\mid X_{1:n})\to 1$

$P^{(\infty)}$-almost surely as $n\to\infty$.

Finally, note that the previous consistency results are related to another
property of general interest, namely the posterior distribution of the
concentration parameter converges to a point mass at $0$, if posterior
consistency for the number of clusters holds.

######  Proposition 2.

Let the data be generated as in (5) with $t\in\mathbb{N}$ and assume $\pi$
satisfies $A1$ and $A2$. Then if $\text{pr}(K_{n}=t\mid X_{1:n})\to 1$ we have

$\pi(\alpha\mid X_{1:n})\rightarrow\delta_{0}$

weakly, as $n\to\infty$, in $P^{(\infty)}$-probability.

Hence, under the conditions that ensure consistency for the number of
clusters, the posterior distribution of the concentration parameter converges
to a degenerate distribution at $0$. This is not surprising since the
Dirichlet process mixture model is concentrated on mixtures with infinitely
mevery components and one way to achieve consistency is to let $\alpha$ tend
to zero, which entails that the prior is swamped by the data.

##  4 Methodology and proof technique

###  4.1 The role of the prior on the concentration parameter

Our proofs of consistency in Theorems 1, 2 and 3 rely on the following lemma.

######  Lemma 2.

The convergence $\text{\rm pr}(K_{n}=t\mid X_{1:n})\to 1$ as $n\to\infty$ in
$P^{(\infty)}$-probability holds true if and only if one has, in
$P^{(\infty)}$-probability,

$\sum_{s\neq t}\frac{\text{\rm pr}(K_{n}=s\mid X_{1:n})}{\text{\rm
pr}(K_{n}=t\mid X_{1:n})}\to 0\quad\text{as }n\to\infty\,.$ (10)

Working with the ratios of conditional probabilities in (10) is beneficial, as
the marginal distribution of $X_{1:n}$ involved in the definition of
$\text{pr}(K_{n}=t\mid X_{1:n})$ cancels. Also, it is convenient to write such
ratios of probabilities as follows: first, recall from (2) and (4) that

$\text{pr}(X_{1:n}=x_{1:n},K_{n}=s)=\int\dfrac{\alpha^{s}}{\alpha^{(n)}}\pi(\alpha)\mathrm{d}\alpha\sum_{A\in\tau_{s}(n)}\prod_{j=1}^{s}(a_{j}-1)!m(x_{A_{j}})$

for every $s\geq 1$, which implies that

$\frac{\text{pr}(K_{n}=s\mid X_{1:n})}{\text{pr}(K_{n}=t\mid
X_{1:n})}=\underbrace{\frac{\int\dfrac{\alpha^{s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int\dfrac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}}_{C(n,t,s)}\underbrace{\frac{\sum_{A\in\tau_{s}(n)}\prod_{j=1}^{s}(a_{j}-1)!\prod_{j=1}^{s}m(X_{A_{j}})}{\sum_{B\in\tau_{t}(n)}\prod_{j=1}^{t}(b_{j}-1)!\prod_{j=1}^{t}m(X_{B_{j}})}}_{R(n,t,s)}.$
(11)

The decomposition of (11) into the factors $C(n,t,s)$ and $R(n,t,s)$ is useful
to understand the role of the prior distribution over $\alpha$, and to compare
our results with the one of Miller and Harrison (2013, 2014). In particular,
the term $R(n,t,s)$ does not depend on $\alpha$ and, hence, on the choice of
$\pi$. This is indeed the key term studied in Miller and Harrison (2014),
where it is shown that, under some assumptions, $\liminf R(n,t,s)>0$ as
$n\to\infty$ in $P^{(\infty)}$-probability, for $t<s$. On the contrary,
$C(n,t,s)$ incorporates information about $\alpha$ and its prior distribution.
In the fixed $\alpha$ case, which can be thought of as having a degenerate
prior $\pi=\delta_{\alpha}$ for some $\alpha>0$, the term $C(n,t,s)$ boils
down to $\alpha^{s-t}$ which is constant with respect to $n$. This is
sufficient for Miller and Harrison (2014) to deduce lack of consistency for
fixed $\alpha$, which means that

$\lim\sup\,\text{pr}(K_{n}=t\mid X_{1:n},\alpha)<1$ (12)

as $n\to\infty$ in $P^{(\infty)}$-probability for every $\alpha>0$.

However, once a non-degenerate prior $\pi$ is employed, $C(n,t,s)$ depends on
$n$ and, as we show in the next section, converges to 0 as $n\to\infty$ under
mild assumptions on $\pi$. Thus, $\liminf R(n,t,s)>0$ is not everymore
sufficient to establish whether consistency holds true or not. Instead, one
needs to compare the rate at which $C(n,t,s)$ converges to 0 with the
behaviour of $R(n,t,s)$, as done in the following sections. Note that further
lower bounds for $R(n,t,s)$ for general values of $s$ are given in Miller and
Harrison (2014); Yang et al. (2019). However, once combined with $C(n,t,s)$,
these are too loose to deduce either consistency or lack thereof. Therefore,
we need to exploit different techniques to determine the rate of $R(n,t,s)$.
Since $\text{pr}(K_{n}=t\mid X_{1:n})=\int\text{pr}(K_{n}=t\mid
X_{1:n},\alpha)\pi(\alpha\mid X_{1:n})\,\mathrm{d}\alpha$, by (12) we deduce
$\lim\sup\,\text{pr}(K_{n}=t\mid X_{1:n},\alpha)<1$ for every $\alpha>0$.
This, however, does not imply that $\lim\sup\text{pr}(K_{n}=t\mid X_{1:n})<1$,
as one first needs to ascertain whether limit and integral can be
interchanged. The main reason is that, in the asymptotic regime we are
considering, the posterior distribution $\pi(\alpha\mid X_{1:n})$ concentrates
around $0$ as $n\to\infty$, see Proposition 2 above.

###  4.2 Asymptotic behaviour of the concentration parameter

We are now concerned with studying $C(n,t,s)$ in (11). We prove that for
priors $\pi$ satisfying assumptions $A1$–$A3$ $C(n,t,s)$ converges to $0$ at a
logarithmic rate in $n$. The asymptotic behaviour of $C(n,t,s)$ is not
specific to some kernel $k$ and data generating distribution $f$ and thus can
be useful to prove consistency, or lack thereof, for arbitrary Dirichlet
process mixture models with random concentration parameter. In order to
facilitate the intuition, the term $C(n,t,s)$ can be interpreted as a moment
of $\alpha$, conditional on the $n$ observations being clustered in $t$
groups. Indeed, under (1) it holds

$\pi(\alpha\mid K_{n}=t)\propto\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)$

and thus $C(n,t,t+s)=\int\alpha^{s}\pi(\alpha\mid
K_{n}=t)\,d\alpha=E(\alpha^{s}\mid K_{n}=t)$. Next proposition shows its
asymptotic behaviour.

######  Proposition 3.

Suppose $\pi$ satisfies $A1$–$A2$. Then there exist $F,G>0$ such that for
every $0<s\leq n-t$

$\displaystyle
F\,\frac{\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}}{\\{\hbox{log}(n)+1\\}^{s}}\leq
C(n,t,t+s)\leq\frac{Gs}{\epsilon^{s}}E(\alpha^{t+s-1})\frac{\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}}{\\{\hbox{log}n/(1+\epsilon)\\}^{s}},$

where $\gamma(x,y)$ is the lower incomplete Gamma function and
$E(\alpha^{s})=\int\alpha^{s}\pi(\alpha)\,d\alpha$.

Thus, for a fixed $s$ that does not depend on $n$, $C(n,t,t+s)$ decreases
logarithmically as a function of $n$ since $\gamma(x,y)\leq\gamma(x)$ for
every $x$ and $y$. Thus, by looking at the ratios in (11), the addition of a
prior favours a smaller number of clusters when $n\to\infty$, with $s$ fixed.

The consistency results of the previous section are established by combining
Proposition 3 with suitable upper bounds on $R(n,t,s)$ to prove the
convergence in (10), so that

$E\left\\{\sum_{s=1}^{n-t}\frac{\text{\rm pr}(K_{n}=t+s\mid
X_{1:n})}{\text{\rm pr}(K_{n}=t\mid
X_{1:n})}\right\\}\leq\frac{1}{\hbox{log}n}\sum_{s=1}^{n-t}h(s),$

where $h(s)$ is a function that depends on the specific kernel $k$ and is such
that $\lim\sup$ $\sum_{s=1}^{n}h(s)<\infty$ for every $s$. Indeed, instead of
proving directly convergence in probability of (10), we show the stronger
$L^{1}$ convergence. In this way we will avoid the study of the specific
partition at hand. The following lemma shows how the problem simplifies in
this case, when $t=1$.

######  Lemma 3.

Assume $(X_{1},X_{2},\dots)$ is an exchangeable sequence. Then for every $n$

$E\left\\{\sum_{A\in\tau_{s}(n)}\frac{\prod_{j=1}^{s}(a_{j}-1)!}{(n-1)!}\frac{\prod_{j=1}^{s}m(X_{A_{j}})}{m(X_{1:n})}\right\\}=\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\frac{n}{s!\prod_{j=1}^{s}a_{j}}E\left\\{\frac{\prod_{j=1}^{s}m(X_{A^{\bm{a}}_{j}})}{m(X_{1:n})}\right\\},$

where the sum runs over
$\mathcal{F}_{s}(n)=\\{\bm{a}\in\\{1,\ldots,n\\}^{s}:\sum_{j=1}^{s}a_{j}=n\\}$
and $A^{\bm{a}}$ is an arbitrary partition in $\tau_{s}(n)$ such that
$|A_{j}^{\bm{a}}|=a_{j}$ for $j=1,\dots,s$.

##  5 Discussion

There are mevery avenues to extend our results and some of the tools we
introduced here may prove useful to accomplish such tasks. First of all, the
separability assumption given in Theorem 1 could be relaxed to prove
consistency in the setting with a general number of components. The main issue
is that $R(n,t,s)$ in (11) is harder to study, since it becomes the ratio of
sums over the space of partitions: in particular Lemma 3 is not easy to
generalize and this explains why the case $t=1$ is simpler to address.
Different mixture kernels present similar difficulties, since they require to
study $R(n,t,s)$ for each specific case. Summarising, the impact of the prior
is fully understood, by Proposition 3 above, but a more general positive
result would require finer bounds on the likelihood component than the ones
available here and in the literature.

Another interesting question worth studying is whether consistency can also be
attained by estimating the concentration parameter through maximization of the
marginal likelihood, in an empirical Bayes fashion (Liu, 1996; McAuliffe et
al., 2006). In this paper we preferred to focus on the fully Bayesian approach
because it is arguably the one most commonly employed by practitioners using
Dirichlet process mixtures. Moreover, the empirical Bayes estimator of
$\alpha$ may not be well defined on $(0,\infty)$ because the marginal
likelihood can easily have its maximum at both $0$ or infinity, thus raising
theoretical and practical issues.

It is also worth noticing that our consistency results require the kernel to
be perfectly specified: even a small amount of misspecification will probably
lead the number of clusters to diverge. Indeed, recovering the true density
will require an increasing number of components. This phenomenon has been
formally studied in Cai et al. (2021) for finite mixture models, when a prior
on the number of components is placed.

We note that the asymptotic analysis of the posterior distribution of the
number of clusters for Dirichlet process mixtures has recently attracted
considerable theoretical interest (Yang et al., 2019; Ohn and Lin, 2022; Cai
et al., 2021), and has motivated various methodological developments (Miller
and Harrison, 2018; Zeng and Duan, 2020). Ohn and Lin (2022) showed that, if
$\alpha$ is sent deterministically to 0 at appropriate rates as $n\to\infty$,
the posterior distribution of the number of clusters concentrates on finite
values when data are generated from a finite mixture, which is a necessary
condition for consistency. Such results are similar in spirit to ours,
although we consider the substantially different setting where $\alpha$ is
learned through a prior, which is arguably more natural in a Bayesian
framework. Finally, our results also provide an answer, at least partially, to
the question of Yang et al. (2019): _“there exists a natural way to correct
the problem instead of truncating the number of clusters?”_ , by showing that
placing a prior on $\alpha$ can be sufficient to recover consistency.

## Supplementary material

Supplementary material includes all the proofs of the theoretical results.

## References

  * Antoniak (1974) Antoniak, C. E. (1974).  Mixtures of Dirichlet processes with applications to Bayesian nonparametric problems.  The Annals of Statistics, 2, 1152–1174.
  * Blei and Jordan (2006) Blei, D. M. and Jordan, M. I. (2006).  Variational inference for Dirichlet process mixtures.  Bayesian Analysis, 1, 121–143.
  * Cai et al. (2021) Cai, D., Campbell, T., and Broderick, T. (2021).  Finite mixture models do not reliably learn the number of components.  38th International Conference on Machine Learning, 139, 1158–1169.
  * Escobar and West (1995) Escobar, M. D. and West, M. (1995).  Bayesian density estimation and inference using mixtures.  Journal of the American Statistical Association, 90, 577–588.
  * Escobar and West (1998) Escobar, M. D. and West, M. (1998).  Computing nonparametric hierarchical models.  In Practical Nonparametric and Semiparametric Bayesian Statistics, pages 1–22. Springer, New York, NY.
  * Ferguson (1973) Ferguson, T. S. (1973).  A Bayesian analysis of some nonparametric problems.  The Annals of Statistics, 1, 209–230.
  * Ghosal and Van der Vaart (2007) Ghosal, S. and Van der Vaart, A. W. (2007).  Posterior convergence rates of Dirichlet mixtures at smooth densities.  The Annals of Statistics, 35, 697–723.
  * Ghosal and Van Der Vaart (2017) Ghosal, S. and Van Der Vaart, A. W. (2017).  Fundamentals of Nonparametric Bayesian Inference.  Cambridge University Press.
  * Ghosal et al. (1999) Ghosal, S., Ghosh, J. K., and Ramamoorthi, R. V. (1999).  Posterior consistency of Dirichlet mixtures in density estimation.  The Annals of Statistics, 27, 143–158.
  * Liu (1996) Liu, J. S. (1996).  Nonparametric hierarchical Bayes via sequential imputations.  The Annals of Statistics, 24, 911–930.
  * Lo (1984) Lo, A. Y. (1984).  On a class of Bayesian nonparametric estimates: I. Density estimates.  The Annals of Statistics, 12, 351–357.
  * MacEachern and Müller (1998) MacEachern, S. N. and Müller, P. (1998).  Estimating mixture of Dirichlet process models.  Journal of Computational and Graphical Statistics, 7, 223–238.
  * McAuliffe et al. (2006) McAuliffe, J. D., Blei, D. M., and Jordan, M. I. (2006).  Nonparametric empirical Bayes for the Dirichlet process mixture model.  Statistics and Computing, 16, 5–14.
  * Miller and Harrison (2013) Miller, J. W. and Harrison, M. T. (2013).  A simple example of Dirichlet process mixture inconsistency for the number of components.  Advances in Neural Information Processing Systems, 26, 199–206.
  * Miller and Harrison (2014) Miller, J. W. and Harrison, M. T. (2014).  Inconsistency of Pitman-Yor process mixtures for the number of components.  Journal of Machine Learning Research, 15, 3333–3370.
  * Miller and Harrison (2018) Miller, J. W. and Harrison, M. T. (2018).  Mixture models with a prior on the number of components.  Journal of the American Statistical Association, 113, 340–356.
  * Müller et al. (2017) Müller, P., Quintana, F. A., and Page, G. L. (2017).  Nonparametric Bayesian inference in applications.  Statistical Methods & Applications, 27, 175–206.
  * Neal (2000) Neal, R. M. (2000).  Markov chain sampling methods for Dirichlet process mixture models.  Journal of Computational and Graphical Statistics, 9, 249–265.
  * Nguyen (2013) Nguyen, X. (2013).  Convergence of latent mixing measures in finite and infinite mixture models.  The Annals of Statistics, 41, 370–400.
  * Ohn and Lin (2022) Ohn, I. and Lin, L. (2022).  Optimal Bayesian estimation of Gaussian mixtures with growing number of components.  Bernoulli, forthcoming.
  * Yang et al. (2019) Yang, C.-Y., Ho, N., and Jordan, M. I. (2019).  Posterior distribution for the number of clusters in Dirichlet process mixture models.  Preprint at arXiv:1905.09959v1.
  * Zeng and Duan (2020) Zeng, C. and Duan, L. L. (2020).  Quasi-Bernoulli stick-breaking: infinite mixture with cluster consistency.  Preprint at arxiv:2008.09938.

Supplementary Materials for
Clustering consistency with
Dirichlet process mixtures

Filippo Ascolania,b<EMAIL_ADDRESS>
Antonio Lijoia,b<EMAIL_ADDRESS>
Giovanni Rebaudob,c<EMAIL_ADDRESS>
Giacomo Zanellaa,b<EMAIL_ADDRESS>
aDepartment of Decision Sciences, Bocconi University,

via Röentgen 1, 20136 Milan, Italy bBocconi Institute for Data Science and
Analytics, Bocconi University,

Via Röntgen 1, 20136 Milan, Italy cDepartment of Statistics and Data Sciences,
University of Texas at Austin,

105 East 24th Street D9800, Austin, TX 78712, USA

## Summary

This document contains the proofs of all the results in the main document. In
order to follow the logical lines of the arguments, we present the proofs of
Sections 4 and 3, in this order.

##  S.1 Proof of Lemma 2

###### Proof.

The result immediately follows upon noting that

$\text{pr}(K_{n}=t\mid X_{1:n})=\left\\{1+\sum_{s\neq
t}\frac{\text{pr}(K_{n}=s\mid X_{1:n})}{\text{pr}(K_{n}=t\mid
X_{1:n})}\right\\}^{-1}.$

$\Box$

##  S.2 Proof of Proposition 3

By assumptions $A1$ and $A2$ there exist $\epsilon,\delta,\beta>0$ such that

$\frac{1}{\delta^{2}}\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s+\beta}}{\alpha^{(n)}}\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t+\beta}}{\alpha^{(n)}}\,\mathrm{d}\alpha}\leq\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}\leq\delta^{2}\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s+\beta}}{\alpha^{(n)}}\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t+\beta}}{\alpha^{(n)}}\,\mathrm{d}\alpha}\,.$
(S.1)

Notice that, if assumption $A2$ holds for $\epsilon\geq 1$, it holds also for
$\epsilon<1$. Thus, without loss of generality, we will assume $\epsilon<1$
and the main object of interest will be

$E_{n}(\alpha^{s})=\int_{0}^{\epsilon}\alpha^{s}p_{n}(\alpha)\mathrm{d}\alpha,$

where $E_{n}$ denotes the expected value with respect to the probability
distribution with density

$p_{n}(\alpha)=\frac{f_{n}(\alpha)}{\int_{0}^{\epsilon}f_{n}(x)\,\mathrm{d}x},\quad
f_{n}(x)=\frac{x^{t+\beta}}{x^{(n)}}\>\mathbbm{1}_{(0,\epsilon)}(x),$ (S.2)

where $\mathbbm{1}_{A}$ stands for the indicator function of set $A$. We now
provide three lemmas that will be useful to prove Proposition 1.

######  Lemma S.1.

Let $f$ and $g$ be two pdf’s on $\mathbb{R}$ such that $g(x)/f(x)$ is non-
decreasing in $x$. Then $\int h(x)f(x)\mathrm{d}x\leq\int h(x)g(x)\mathrm{d}x$
for every non-decreasing $h:\mathbb{R}\to\mathbb{R}$.

###### Proof.

Let $X\sim f$ and $Y\sim g$. Since $g(x)/f(x)$ is non-decreasing we have
$g(x_{0})f(x_{1})\leq g(x_{1})f(x_{0})$ for every $x_{0}<x_{1}$. Thus we have

$\displaystyle F_{Y}(x_{1})f(x_{1})$
$\displaystyle=\int_{-\infty}^{x_{1}}g(x_{0})f(x_{1})\mathrm{d}x_{0}\leq\int_{-\infty}^{x_{1}}g(x_{1})f(x_{0})\mathrm{d}x_{0}=F_{X}(x_{1})g(x_{1})$

and

$\displaystyle\\{1-F_{X}(x_{0})\\}g(x_{0})$
$\displaystyle=\int_{x_{0}}^{\infty}g(x_{0})f(x_{1})\mathrm{d}x_{1}\leq\int_{x_{0}}^{\infty}g(x_{1})f(x_{0})\mathrm{d}x_{1}=\\{1-F_{Y}(x_{0})\\}f(x_{0}).$

It follows

$\displaystyle\frac{F_{Y}(x)}{F_{X}(x)}\leq\frac{g(x)}{f(x)}\leq\frac{1-F_{Y}(x)}{1-F_{X}(x)}\,,$

for every $x\in\mathbb{R}$, which implies

$\displaystyle\frac{F_{Y}(x)}{1-F_{Y}(x)}\leq\frac{F_{X}(x)}{1-F_{X}(x)}\,.$

Thus, $Y$ stochastically dominates $X$, i.e. the corresponding cdf’s satisfy
$F_{Y}(x)~{}\leq~{}F_{X}(x)$ for every $x\in\mathbb{R}$, which implies that
$E\\{h(X)\\}\leq E\\{h(Y)\\}$ for every non-decreasing $h$. $\Box$

######  Lemma S.2.

Under assumptions $A1$ and $A2$, for every $n-t>s\geq 1$ it holds

$\frac{\gamma[t+s+\beta,\epsilon\\{\hbox{log}(n)+1\\}]}{\delta^{2}\gamma[t+\beta,\epsilon\\{\hbox{log}(n)+1\\}]}\\{\hbox{log}(n)+1\\}^{-s}\leq\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}\leq\frac{\delta^{2}\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}}{\gamma\\{t+\beta,\epsilon\hbox{log}(n)\\}}\\{\hbox{log}(n)/(1+\epsilon)\\}^{-s},$

where $\gamma(x,y)$ is the lower incomplete Gamma function and we recall that
$\epsilon,\delta,\beta>0$ are such that for every $\alpha\in(0,\epsilon)$ it
holds $\frac{1}{\delta}\alpha^{\beta}\leq\pi(\alpha)\leq\delta\alpha^{\beta}$.

###### Proof.

By (S.1) it suffices to find suitable bounds of $E_{n}(\alpha^{s})$. For the
upper inequality we apply Lemma S.1 with $f=p_{n}$,
$g(\alpha)\propto(cn)^{-\alpha}\alpha^{t+\beta-1}\mathbbm{1}_{\left(\alpha\in[0,\epsilon]\right)}$
with $c=(1+\epsilon)^{-1}$ and $h(\alpha)=\alpha^{s}$. To verify that
$g(\alpha)/p_{n}(\alpha)$ is non-decreasing for $\alpha\in(0,\epsilon]$ we
compute

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\alpha}\hbox{log}\left\\{\frac{g(\alpha)}{p_{n}(\alpha)}\right\\}=$
$\displaystyle-\hbox{log}\left(\frac{n}{1+\epsilon}\right)+\sum_{i=1}^{n-1}\frac{1}{\alpha+i}$
$\displaystyle\geq$
$\displaystyle-\hbox{log}\left(\frac{n+\epsilon}{1+\epsilon}\right)+\sum_{i=1}^{n-1}\frac{1}{i+\epsilon}\geq
0,$

where the last inequality follows from

$\int_{1}^{k}\frac{1}{x+\epsilon}\,dx<\sum_{i=1}^{k-1}\frac{1}{i+\epsilon}$

for every $k>1$. Thus, since $h(\alpha)=\alpha^{s}$ is non-decreasing in
$\alpha$ it follows by Lemma S.1 that

$\displaystyle E_{n}(\alpha^{s})\leq$
$\displaystyle\frac{\int_{0}^{\epsilon}\alpha^{t+s+\beta-1}(cn)^{-\alpha}\mathrm{d}\alpha}{\int_{0}^{\epsilon}\alpha^{t+\beta-1}(cn)^{-\alpha}\,\mathrm{d}\alpha}=\frac{\\{\hbox{log}(cn)\\}^{-s}\int_{0}^{\epsilon\hbox{log}(cn)}z^{t+s+\beta-1}e^{-z}\mathrm{d}z}{\int_{0}^{\epsilon\hbox{log}(cn)}z^{t+\beta-1}e^{-z}\,\mathrm{d}z}$
$\displaystyle=$
$\displaystyle\frac{\\{\hbox{log}(cn)\\}^{-s}\gamma\\{t+s+\beta,\epsilon\hbox{log}(cn)\\}}{\gamma\\{t+\beta,\epsilon\hbox{log}(cn)\\}}.$

The lower bound again follows from Lemma S.1 with
$f(\alpha)\propto(en)^{-\alpha}\alpha^{t+\beta-1}\mathbbm{1}_{\left(\alpha\in[0,\epsilon]\right)}$,
$g(\alpha)=p_{n}(\alpha)$ and $h(\alpha)=\alpha^{s}$. To verify that
$p_{n}(\alpha)/f(\alpha)$ is non-decreasing for $\alpha\in(0,\epsilon]$ we
compute

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}\alpha}\hbox{log}\left\\{\frac{p_{n}(\alpha)}{f(\alpha)}\right\\}=$
$\displaystyle-\sum_{i=1}^{n-1}\frac{1}{\alpha+i}+\hbox{log}(n)+1$
$\displaystyle\geq$
$\displaystyle-\sum_{i=1}^{n-1}\frac{1}{i}+\hbox{log}(n)+1\geq 0,$

where the last inequality follows from

$\sum_{i=1}^{k}\frac{1}{i}\leq\hbox{log}(k)+1$

for every $k\geq 1$. Thus, since $h(\alpha)=\alpha^{s}$ is non-decreasing in
$\alpha$, we have

$\displaystyle E_{n}(\alpha^{s})\geq$
$\displaystyle\frac{\int_{0}^{\epsilon}\alpha^{t+s+\beta-1}(en)^{-\alpha}\mathrm{d}\alpha}{\int_{0}^{\epsilon}\alpha^{t+\beta-1}(en)^{-\alpha}\,\mathrm{d}\alpha}=\frac{\\{\hbox{log}(en)\\}^{-s}\int_{0}^{\epsilon\hbox{log}(en)}z^{t+s+\beta-1}e^{-z}\mathrm{d}z}{\int_{0}^{\epsilon\hbox{log}(en)}z^{t+\beta-1}e^{-z}\,\mathrm{d}z}$
$\displaystyle=\frac{\\{\hbox{log}(en)\\}^{-s}\gamma\\{t+s+\beta,\epsilon\hbox{log}(en)\\}}{\gamma\\{t+\beta,\epsilon\hbox{log}(en)\\}}.$

The proof is completed by combining the bounds with (S.1). $\Box$

######  Lemma S.3.

For every $\epsilon>0$, there exists $M>0$ such that, for every $n\geq 1$, it
holds

$M\,\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha\geq\int_{\epsilon}^{\infty}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha\,.$

###### Proof.

Define
$p=\frac{\int_{\epsilon}^{\infty}\alpha^{t}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\frac{\epsilon}{2}}\alpha^{t}\pi(\alpha)\,\mathrm{d}\alpha}$.
Then

$\displaystyle\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha-\int_{\epsilon}^{\infty}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha=$
$\displaystyle\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha-\int_{0}^{\frac{\epsilon}{2}}p\frac{\alpha^{t}}{\epsilon^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha$
$\displaystyle\geq$
$\displaystyle\int_{0}^{\frac{\epsilon}{2}}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha-\int_{0}^{\frac{\epsilon}{2}}p\frac{\alpha^{t}}{\epsilon^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha.$

Choose $m$ such that
$\left(\frac{\epsilon}{2}\right)^{(m)}<\frac{\epsilon^{(m)}}{p}$, which is
always possible because
$\left\\{\epsilon^{(m)}\right\\}^{-1}\left(\frac{\epsilon}{2}\right)^{(m)}\to
0$ as $m\to\infty$. Thus

$\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha\geq\int_{\epsilon}^{\infty}\frac{\alpha^{t}}{\alpha^{(n)}}\,\pi(\alpha)\,\mathrm{d}\alpha,\quad
n\geq m$

and it suffices to set $M=\max(P,1)$ with

$P=\max_{1\leq i\leq
m}\left\\{\frac{\int_{\epsilon}^{\infty}\frac{\alpha^{t}}{\alpha^{(i)}}\,\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(i)}}\,\pi(\alpha)\,\mathrm{d}\alpha}\right\\}\,.$

$\Box$

###### Proof of Proposition 3.

We first prove the upper bound. We have

$\displaystyle C(n,t,t+s)$
$\displaystyle\leq\frac{\int_{0}^{\infty}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}=\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}+\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}\frac{\int_{\epsilon}^{\infty}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}.$

Moreover, it holds

$\frac{\int_{\epsilon}^{\infty}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}\leq\frac{\int_{\epsilon}^{\infty}\alpha^{t+s-1}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\alpha^{t+s-1}\pi(\alpha)\,\mathrm{d}\alpha}\leq\delta\frac{\int_{\epsilon}^{\infty}\alpha^{t+s-1}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\alpha^{t+s+\beta-1}\,\mathrm{d}\alpha}\leq\delta\,E(\alpha^{t+s-1})\frac{t+s+\beta}{\epsilon^{t+s+\beta}},$

where the first inequality follows since $\alpha^{(n)}\geq\epsilon^{(n)}$ for
$\alpha\in(\epsilon,\infty)$ and $\alpha^{(n)}\leq\epsilon^{(n)}$ for
$\alpha\in(0,\epsilon)$, while the second one follows from assumption $A2$.
Moreover, $E$ stands for the expected value with respect to $\pi$. Thus from
Lemma S.2 it holds

$C(n,t,t+s)\leq\frac{\delta^{2}\left\\{1+E(\alpha^{t+s-1})\,\frac{t+s+\beta}{\epsilon^{t+s+\beta}}\right\\}\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}}{\gamma\\{t+\beta,\epsilon\hbox{log}(n)\\}}\\{\hbox{log}(n)/(1+\epsilon)\\}^{-s}.$

Then choose
$G=\frac{4\delta^{2}}{\epsilon^{t+\beta}\gamma(t+\beta,\epsilon\hbox{log}2)}$
to obtain the upper bound. For the lower bound, apply Lemma S.2 and Lemma S.3
to get

$C(n,t,t+s)\geq\frac{1}{M+1}\frac{\int_{0}^{\epsilon}\frac{\alpha^{t+s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int_{0}^{\epsilon}\frac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}\geq\frac{1}{M+1}\frac{\gamma[t+s+\beta,\epsilon\\{\hbox{log}(n)+1\\}]}{\delta^{2}\gamma[t+\beta,\epsilon\\{\hbox{log}(n)+1\\}]}\\{\hbox{log}(n)+1\\}^{-s}.$

Then choose $F=\frac{1}{(M+1)\delta^{2}\gamma(t+\beta)}$. $\Box$

The following corollary of Proposition 3 will be useful.

######  Corollary S.1.

Suppose $\pi$ satisfies assumptions $A1$ and $A2$. Then $G>0$ as in
Proposition 3 is such that for every $0<s<n$ and $n\geq 4$ it holds

$\displaystyle
C(n,t,t+s)\leq\frac{G\Gamma(t+\beta+1)2^{s}s}{\epsilon}E(\alpha^{t+s-1})\hbox{log}\\{n/(1+\epsilon)\\}^{-1}.$

###### Proof.

By Proposition 3 we have

$C(n,t,t+s)\leq\frac{Gs}{\epsilon^{s}}E(\alpha^{t+s-1})\frac{\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}}{\hbox{log}\\{n/(1+\epsilon)\\}^{s}}.$

Note that

$\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}=\int_{0}^{\epsilon\hbox{log}(n)}x^{t+s+\beta-1}e^{-x}\,\mathrm{d}x\leq\epsilon^{s-1}\\{\hbox{log}(n)\\}^{s-1}\Gamma(t+\beta+1),$

that implies

$\frac{\gamma\\{t+s+\beta,\epsilon\hbox{log}(n)\\}}{\epsilon^{s}\hbox{log}^{s}\\{n/(1+\epsilon)\\}}\leq\frac{\Gamma(t+\beta+1)}{\epsilon}\left[\frac{\hbox{log}(n)}{\hbox{log}\\{n/(1+\epsilon)\\}}\right]^{s-1}\hbox{log}\\{n/(1+\epsilon)\\}^{-1}.$

Moreover, since $\epsilon<1$, we have
$\hbox{log}\\{n/(1+\epsilon)\\}\geq\frac{1}{2}\hbox{log}(n)$ for every $n\geq
4$. Combining the inequalities above we obtain the desired result. $\Box$

##  S.3 Proof of Lemma 3

###### Proof.

We need to study $R(n,1,s)$ as in (11). Taking the expectation with respect to
the data generating distribution we have

$\displaystyle E\\{R(n,1,s)\\}$
$\displaystyle=\sum_{A\in\tau_{s}(n)}\frac{\prod_{j=1}^{s}(a_{j}-1)!}{(n-1)!}E\left\\{\frac{\prod_{j=1}^{s}m(X_{A_{j}})}{m(X_{1:n})}\right\\}$
$\displaystyle=\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\binom{n}{a_{1}\cdots
a_{j}}\frac{\prod_{j=1}^{s}(a_{j}-1)!}{s!(n-1)!}E\left\\{\frac{\prod_{j=1}^{s}m(X_{A_{j}^{\bm{a}}})}{m(X_{1:n})}\right\\}$
$\displaystyle=\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\frac{n}{s!\prod_{j=1}^{s}a_{j}}E\left\\{\frac{\prod_{j=1}^{s}m(X_{A_{j}^{\bm{a}}})}{m(X_{1:n})}\right\\}.$

$\Box$

##  S.4 Proof of Lemma 1

###### Proof.

Assumptions $A1$ and $A2$ are immediately satisfied in all three cases
discussed in the statement of the lemma. We thus focus on proving that $A3$ is
satisfied, considering each of the three cases separately. Suppose first that
the support of the density $\pi$ is contained in $[0,c]$ with $c>0$. Then

$\int_{0}^{\infty}\alpha^{s}\pi(\alpha)\,\mathrm{d}\alpha\leq c^{s}.$

Thus in this case assumption $A3$ is satisfied for every $\rho>0$ because
$c^{s}<D\rho^{-s}\Gamma(s+1)$ with
$D=\underset{s\in\mathbb{N}}{\max}\frac{(c\rho)^{s}}{\Gamma(s+1)}$ for every
$\rho>0$. Suppose now the prior is given by a Generalized Gamma distribution,
so that

$\int_{0}^{\infty}\alpha^{s}\pi(\alpha)\,\mathrm{d}\alpha=\frac{p}{a^{d}\Gamma\left(\frac{d}{p}\right)}\int_{0}^{\infty}\alpha^{d+s-1}e^{-\left(\frac{\alpha}{a}\right)^{p}}\,\mathrm{d}\alpha\,.$

The condition $p>1$ implies that, for every fixed $\rho>0$ and $a>0$, there
exists $k>0$ such that $\rho\alpha\leq\left(\frac{\alpha}{a}\right)^{p}$ for
every $\alpha\geq k$. Thus

$\displaystyle\int_{0}^{\infty}\alpha^{d+s-1}e^{-\left(\frac{\alpha}{a}\right)^{p}}\,\mathrm{d}\alpha$
$\displaystyle\leq\int_{0}^{k}\alpha^{s+d-1}e^{-\left(\frac{\alpha}{a}\right)^{p}}\,\mathrm{d}\alpha+\int_{k}^{\infty}\alpha^{s+d-1}e^{-\rho\alpha}\,\mathrm{d}\alpha$
$\displaystyle\leq
k^{s+d-1}e^{-\left(\frac{k}{a}\right)^{p}}+\rho^{-d-s}\Gamma(s+d).$

Also,

$\displaystyle\int_{0}^{\infty}\alpha^{s}\pi(\alpha)\,\mathrm{d}\alpha\leq$
$\displaystyle\frac{p}{a^{d}\Gamma\left(\frac{d}{p}\right)}\Gamma(s+d)\left\\{\frac{k^{s+d-1}e^{-\left(\frac{k}{a}\right)^{p}}}{\Gamma(s+d)}+\rho^{-d-s}\right\\}\leq$
$\displaystyle\leq D\rho^{-s}\Gamma(s+d),$

with
$D=\underset{s\in\mathbb{N}}{\max}\,\frac{p}{a^{d}\Gamma\left(\frac{d}{p}\right)}\left\\{\frac{k^{s+d-1}e^{-\left(\frac{k}{a}\right)^{p}\rho^{s}}}{\Gamma(s+d)}+\rho^{-d}\right\\}$,
so that also in this case assumption $A3$ is satisfied for every $\rho>0$.
Finally, in the case of Gamma distribution we get

$\int_{0}^{\infty}\alpha^{s}\pi(\alpha)\,\mathrm{d}\alpha=\frac{\Gamma(\nu+s)}{\Gamma(\nu)}\rho^{-s}$

and assumption $A3$ holds. $\Box$

##  S.5 Proof of Theorem 1

Through a linear rescaling, we may assume $[a,b]=[-c,c]$ without loss of
generality. We rewrite the assumptions on $g$ and $Q_{0}$ as

  1. $T1.$

$\exists\,m,M$ such that $0<m\leq g(x)\leq M<\infty$ for every $x\in[-c,c]$;

  2. $T2.$

$g$ is differentiable on $(-c,c)$ and $\exists\,R$ such that
$|\frac{g^{\prime}(x)}{g(x)}|\leq R<\infty$ for every $x\in(-c,c)$;

  3. $T3.$

$\exists\,U>0$ such that $h(y)=q_{0}(y)+q_{0}(-y)\leq U$ for every
$y\in[0,2c]$;

  4. $T4.$

$\exists\,L>0$ such that $q_{0}(\theta)\geq L$ for every $\theta$ in a
neighborhood of $\theta_{j}^{*}$, for every $j$.

Denote with $f(x)=\sum_{j=1}^{t}p_{j}k(x\mid\theta_{j}^{*})$ the density of
the data generating $P=\sum_{j=1}^{t}p_{j}R_{j}$, with $t\in\mathbb{N}$,
$p_{j}\in(0,1)$ and $\sum_{j=1}^{t}p_{j}=1$. Since
$\theta^{*}=(\theta_{1}^{*},\dots,\theta_{t}^{*})$ is completely separated and
$X^{\infty}\sim P^{(\infty)}$, each point $x$ has non-null density for at most
one component of the mixture, i.e.

$x\in[\theta_{i}^{*}+a,\theta_{i}^{*}+b]\quad\Rightarrow\quad
f(x)=p_{i}k(x\mid\theta_{i}^{*})=p_{i}g(x-\theta_{i}^{*}).$

Therefore we can define

$C_{j}=\left\\{i\in\\{1,\dots,n\\}\,:\,x_{i}\in[\theta_{j}^{*}+a,\theta_{j}^{*}+b]\right\\},\quad
n_{j}=|C_{j}|.$

Notice that $C_{i}\cap C_{j}=\emptyset$ for every $i\neq j$ and
$\\{1,\dots,n\\}=\bigcup_{j=1}^{t}C_{j}$, so that $\sum_{j=1}^{t}n_{j}=n$.
Moreover, defining

$C^{(n)}=\left\\{n_{j}>0\text{ for every $j$}\right\\},$

for every $x_{1:n}\in C^{(n)}$ it holds

$\displaystyle\sum_{A\in\tau_{s}(n)}\prod_{j=1}^{s}(a_{j}-1)!\prod_{j=1}^{s}m(x_{A_{j}})=0\quad\text{for
every }s<t,$ (S.3)
$\displaystyle\sum_{B\in\tau_{t}(n)}\prod_{j=1}^{t}(b_{j}-1)!\prod_{j=1}^{t}m(x_{B_{j}})=\prod_{j=1}^{t}(n_{j}-1)!\prod_{j=1}^{t}m(x_{C_{j}}).$

Since $p_{j}>0$ for every $j=1,\dots,s$, we have $P^{(n)}(C^{(n)})\to 1$ as
$n\to\infty$. We need a technical lemma.

######  Lemma S.4.

Let $\Omega_{n}$ be a sequence of sets depending on $X_{1:n}$, and let $Z_{n}$
be random variables on the same probability space such that
$P^{(\infty)}(\Omega_{n})\to 1$ and

$Z_{n}\mathbbm{1}_{\Omega_{n}}\to 0$

in $P^{(\infty)}$-probability as $n\to\infty$. Then $Z_{n}\to 0$ in
$P^{(\infty)}$-probability as $n\to\infty$.

###### Proof.

By assumption
$P^{(\infty)}\left(\mathbbm{1}_{\Omega_{n}}Z_{n}>\epsilon\right)\to 0$ as
$n\to\infty$. Thus, we have

$P^{(\infty)}\left(Z_{n}>\epsilon\right)\leq
P^{(\infty)}\left\\{(Z_{n}>\epsilon)\cap\Omega_{n}\right\\}+P^{(\infty)}\left(\Omega_{n}^{c}\right)\to
0$

as $n\to\infty$. $\Box$

Thus by Lemma S.4 it suffices to study

$\frac{\text{pr}(K_{n}=s\mid X_{1:n})}{\text{pr}(K_{n}=t\mid
X_{1:n})}\mathbbm{1}_{C^{(n)}}=\frac{\int\dfrac{\alpha^{s}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}{\int\dfrac{\alpha^{t}}{\alpha^{(n)}}\pi(\alpha)\,\mathrm{d}\alpha}\frac{\sum_{A\in\tau_{s}(n)}\prod_{j=1}^{s}(a_{j}-1)!\prod_{j=1}^{s}m(X_{A_{j}})}{\sum_{B\in\tau_{t}(n)}\prod_{j=1}^{t}(b_{j}-1)!\prod_{j=1}^{t}m(X_{B_{j}})}\mathbbm{1}_{C^{(n)}}.$
(S.4)

By (S.3), we have

$\frac{\text{pr}(K_{n}=s\mid X_{1:n})}{\text{pr}(K_{n}=t\mid
X_{1:n})}\mathbbm{1}_{C^{(n)}}=0$

for every $s<t$. Let us now consider the case $s>t$. Again by complete
separability, $A\in\tau_{s}(n)$ yields positive marginal density only if $A$
is a refinement of the partition $\left\\{C_{1},\dots,C_{t}\right\\}$, i.e. if

$A\in\tilde{\tau}_{s}(n)=\left\\{A\in\tau_{s}(n)\,:\,\forall\,i=1,\dots,s\text{
there exists }j\in\\{1,\dots,t\\}\text{ such that }A_{i}\subset
C_{j}\right\\}.$

Therefore, if $A\in\tilde{\tau}_{s}(n)$, we write the $j$-the element as
$A_{j}=(A^{j}_{1},\dots,A^{j}_{s_{j}})$ with $a^{j}_{k}=|A^{j}_{k}|$, so that

$\sum_{A\in\tilde{\tau}_{s}(n)}\prod_{j=1}^{s}(a_{j}-1)!\prod_{j=1}^{s}m(X_{A_{j}})=\sum_{\textbf{s}\in\text{S}}\prod_{j=1}^{t}\sum_{A_{j}\in\tau_{s_{j}}(n_{j})}\prod_{k=1}^{s_{j}}(a^{j}_{k}-1)!\prod_{k=1}^{s_{j}}m(X_{A^{j}_{k}}),$

where $\textbf{S}=\left\\{(s_{1},\dots,s_{t})\,:\,1\leq s_{j}\leq
n_{j},\,\forall j,\text{ and }\sum_{j=1}^{t}s_{j}=s\right\\}$. By the above
and (S.3) we can rewrite (S.4) as

$\displaystyle\frac{\text{pr}(K_{n}=s\mid X_{1:n})}{\text{pr}(K_{n}=t\mid
X_{1:n})}\mathbbm{1}_{C^{(n)}}$
$\displaystyle=C(n,t,s)\frac{\sum_{A\in\tilde{\tau}_{s}(n)}\prod_{j=1}^{s}(a_{j}-1)!\prod_{j=1}^{s}m(X_{A_{j}})}{\prod_{j=1}^{t}(n_{j}-1)!\prod_{j=1}^{t}m(X_{C_{j}})}\mathbbm{1}_{C^{(n)}}$
(S.5)
$\displaystyle=C(n,t,s)\sum_{\textbf{s}}\prod_{j=1}^{t}\sum_{A_{j}\in\tau_{s_{j}}(n_{j})}\frac{\prod_{k=1}^{s_{j}}(a^{j}_{k}-1)!}{(n_{j}-1)!}\frac{\prod_{k=1}^{s_{j}}m(X_{A^{j}_{k}})}{m(A_{C_{j}})}\mathbbm{1}_{C^{(n)}},$

where

$m(X_{C_{j}})=\int_{\mathbb{R}}\prod_{i\in
C_{j}}k(X_{i}\mid\theta_{j})\,Q_{0}(\mathrm{d}\theta_{j})=\int_{\mathbb{R}}\prod_{i\in
C_{j}}g(X_{i}-\theta_{j})\,Q_{0}(\mathrm{d}\theta_{j})$

and

$m(X_{A^{j}_{h}})=\int_{\mathbb{R}}\prod_{i\in
A^{j}_{h}}k(X_{i}\mid\theta_{h})\,Q_{0}(\mathrm{d}\theta_{h})=\int_{\mathbb{R}}\prod_{i\in
A^{j}_{h}}g(X_{i}-\theta_{h})\,Q_{0}(\mathrm{d}\theta_{h}),$

with $h=1,\dots,s_{j}$. We divide and multiply by

$\prod_{i=1}^{n}f(X_{i})=\prod_{j=1}^{t}\prod_{i\in
C_{j}}p_{j}k(X_{i}\mid\theta_{j}^{*})=\prod_{j=1}^{t}\prod_{h=1}^{s_{j}}\prod_{i\in
A_{h}^{j}}p_{j}k(X_{i}\mid\theta_{j}^{*}),$

so that the sum on the right hand side of (S.5) becomes

$\sum_{\textbf{s}}\prod_{j=1}^{t}\sum_{A_{j}\in\tau_{s_{j}}(n_{j})}\frac{\prod_{k=1}^{s_{j}}(a^{j}_{k}-1)!}{(n_{j}-1)!}\frac{\prod_{k=1}^{s_{j}}\int_{\mathbb{R}}\prod_{i\in
A^{j}_{k}}\frac{g(X_{i}-\theta_{k})}{p_{j}g(X_{i}-\theta_{j}^{*})}\,Q_{0}(\mathrm{d}\theta_{k})}{\int_{\mathbb{R}}\prod_{i\in
C_{j}}\frac{g(X_{i}-\theta_{j})}{p_{j}g(X_{i}-\theta_{j}^{*})}\,Q_{0}(\mathrm{d}\theta_{j})}\mathbbm{1}_{C^{(n)}},\quad\text{for
}s>t.$ (S.6)

We start with the denominator. The next lemma specifies the behaviour of the
maximum for each group, where $X^{j}_{(r)}$ denotes the $r$-th order statistic
of $X_{C_{j}}$.

######  Lemma S.5.

For every $j=1,\dots,t$ it holds

$Y^{j}_{n_{j}}:=\min\left[1,n_{j}(\hbox{log}(n))^{\frac{1}{2t}}\\{c+\theta_{j}^{*}-X^{j}_{(n_{j})}\\}\right]\to
1$

in $P^{(\infty)}$-probability as $n\to\infty$.

###### Proof.

First, notice that $n_{j}\to\infty$ $P^{(\infty)}$-almost surely as
$n\to\infty$. By definition $Y^{j}_{n_{j}}\leq 1$, so we have to prove that
$\forall\epsilon>0$

$P^{(\infty)}\left(1-Y^{j}_{n_{j}}>\epsilon\right)\to 0$

as $n_{j}\to\infty$, where pr is evaluated with respect to $P^{(\infty)}$.
Without loss of generality assume $\theta_{j}^{*}=0$. Thus, by definition we
have

$\displaystyle P^{(\infty)}(1-Y^{j}_{n_{j}}>\epsilon)$
$\displaystyle=P^{(\infty)}\left[n_{j}(\hbox{log}(n))^{\frac{1}{2t}}\\{c-X^{j}_{(n)}\\}\leq
1-\epsilon\right]=P^{(\infty)}\left\\{X^{j}_{(n)}\geq
c-\frac{1-\epsilon}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}\right\\}$
$\displaystyle=1-\left\\{1-\int_{c-\frac{1-\epsilon}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}}^{c}g(x)\,\mathrm{d}x\right\\}^{n}\,.$

Thus, by $T1$ we have that
$\int_{c-\frac{1-\epsilon}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}}^{c}g(x)\,\mathrm{d}x\leq\frac{M(1-\epsilon)}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}$,
so that

$P^{(\infty)}(1-Y^{j}_{n_{j}}>\epsilon)\leq
1-\left\\{1-\frac{M(1-\epsilon)}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}\right\\}^{n}=1-e^{-\frac{M(1-\epsilon)}{(\hbox{log}(n))^{\frac{1}{2t}}}+n_{j}\,\text{o}\left(\frac{1}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}\right)}\to
0,$

as $n\to\infty$, by the Taylor expansion of the logarithmic function. $\Box$

######  Lemma S.6.

For every $j=1,\dots,t$ it holds

$\prod_{i\in C_{j}}\frac{g(x_{i}-\theta_{j})}{g(x_{i})}\geq
e^{-R}\mathbbm{1}_{[0,\frac{1}{n_{j}}]}(|\theta_{j}-\theta_{j}^{*}|)\mathbbm{1}_{[x^{j}_{(n_{j})}-c,x^{j}_{(1)}+c]}(\theta_{j}-\theta_{j}^{*}).$

with $R$ defined in $T2$ and $x^{j}_{(r)}$ denotes the $r$-th order statistic
of $x_{C_{j}}$.

###### Proof.

Without loss of generality assume $\theta_{j}^{*}=0$. Define
$p(x):=\hbox{log}g(x)$, with $x\in[-c,c]$, so that
$p^{\prime}(x)=\frac{g^{\prime}(x)}{g(x)}$. By $T2$ and the Fundamental
Theorem of Integral Calculus

$|p(y)-p(x)|=\left\lvert\int_{x}^{y}p^{\prime}(t)\,\mathrm{d}t\right\rvert\leq\int_{x}^{y}\left|\frac{g^{\prime}(t)}{g(t)}\right|\mathrm{d}t\leq
R|y-x|,\quad-c<x\leq y<c.$

Thus, we have

$\frac{g(x-\theta_{j})}{g(x)}=e^{p(x-\theta_{j})-p(x)}=e^{-\\{p(x)-p(x-\theta_{j})\\}}\geq
e^{-R|\theta_{j}|},\quad x\in[-c,c].$

Finally, we get

$\displaystyle\prod_{i\in C_{j}}\frac{g(x_{i}-\theta_{j})}{g(x_{i})}$
$\displaystyle\geq
e^{-Rn_{j}|\theta_{j}|}\mathbbm{1}_{[x^{j}_{(n_{j})}-c,x^{j}_{(1)}+c]}(\theta_{j})\geq
e^{-Rn|\theta_{j}|}\mathbbm{1}_{[0,\frac{1}{n_{j}}]}(|\theta_{j}|)\mathbbm{1}_{[x^{j}_{(n_{j})}-c,x^{j}_{(1)}+c]}(\theta_{j})$
$\displaystyle\geq
e^{-R}\mathbbm{1}_{[0,\frac{1}{n_{j}}]}(|\theta_{j}|)\mathbbm{1}_{[x^{j}_{(n_{j})}-c,x^{j}_{(1)}+c]}(\theta_{j}).$

$\Box$

######  Lemma S.7.

For every $j=1,\dots,t$ there exists $K>0$ and $N_{j}\in\mathbb{N}$ such that
for all $n_{j}\geq N_{j}$ it holds

$\int_{\mathbb{R}}\prod_{i\in
C_{j}}\frac{g(X_{i}-\theta_{j})}{g(X_{i}-\theta_{j}^{*})}q_{0}(\theta_{j})\,\mathrm{d}\theta_{j}\geq\frac{K^{\frac{1}{t}}Y^{j}_{n_{j}}}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}},$

with $Y^{j}_{n_{j}}$ defined in Lemma S.5.

###### Proof.

Without loss of generality assume $\theta_{j}^{*}=0$. Notice that, by $T4$,
there exists $N_{j}\in\mathbb{N}$ such that $q_{0}(\theta)\geq L$ for every
$\theta\in\left[-\frac{1}{N_{j}},0\right]$. Thus, applying Lemma S.6 and
considering $n_{j}\geq N_{j}$, we get

$\displaystyle\int_{\mathbb{R}}\prod_{i\in
C_{j}}\frac{g(X_{i}-\theta_{j})}{g(X_{i})}q_{0}(\theta_{j})\,\mathrm{d}\theta_{j}$
$\displaystyle\geq
e^{-R}\int_{\mathbb{R}}\mathbbm{1}_{[0,\frac{1}{n_{j}}]}(|\theta_{j}|)\mathbbm{1}_{[X^{j}_{(n_{j})}-c,x^{j}_{(1)}+c]}(\theta_{j})\,q_{0}(\theta_{j})\,\mathrm{d}\theta_{j}$
$\displaystyle\geq
e^{-R}\int_{-\frac{1}{n_{j}}}^{0}\mathbbm{1}_{\\{X^{j}_{(n_{j})}\leq\theta_{j}+c\\}}\,q_{0}(\theta_{j})\,\mathrm{d}\theta_{j}\geq
Le^{-R}\min\left\\{\frac{1}{n_{j}},c-X^{j}_{(n_{j})}\right\\},$

with $L$ defined in $T4$. Thus, multiplying both the numerator and the
denominator by $n_{j}(\hbox{log}(n))^{\frac{1}{2t}}$, with $n\geq N$, we have

$\displaystyle\int_{\mathbb{R}}\prod_{i\in
C_{j}}\frac{g(X_{i}-\theta_{j})}{g(X_{i})}q_{0}(\theta_{j})\,\mathrm{d}\theta_{j}$
$\displaystyle\geq
2Le^{-R}\min\left\\{\frac{1}{n_{j}},c-X^{j}_{(n_{j})}\right\\}$
$\displaystyle\geq\frac{K^{\frac{1}{t}}\min\left[1,n_{j}(\hbox{log}(n))^{\frac{1}{2t}}\\{c-X_{(n)}\\}\right]}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}}=\frac{K^{\frac{1}{2t}}Y_{n}}{n_{j}(\hbox{log}(n))^{\frac{1}{2t}}},$

with $K=(2Le^{-R})^{t}$. $\Box$

Define the event

$\Omega_{n}=\left\\{\text{for every $j=1,\dots,t$ it holds: }n_{j}\geq
N_{j},Y^{j}_{n_{j}}\in[1/2,1]\right\\},$ (S.7)

such that $P^{(n)}(\Omega_{n})\to 1$ thanks to Lemma S.5 and Lemma S.7. Thus,
an upper bound of (S.6) with $\Omega_{n}$ in place of $C^{(n)}$ is given by

$T^{(n)}:=\frac{2^{t}\sqrt{\hbox{log}(n)}}{K}\sum_{\textbf{s}}\prod_{j=1}^{t}\sum_{A_{j}\in\tau_{s_{j}}(n_{j})}n_{j}\frac{\prod_{k=1}^{s_{j}}(a^{j}_{k}-1)!}{(n_{j}-1)!}\prod_{h=1}^{s_{j}}\int_{\mathbb{R}}\prod_{i\in
A^{j}_{h}}\frac{g(X_{i}-\theta_{h})}{g(X_{i}-\theta_{j}^{*})}\,Q_{0}(\mathrm{d}\theta_{h})\mathbbm{1}_{\Omega_{n}},$
(S.8)

for $s>t$. Now we apply the expected value with respect to the values of each
group, as shown in the next lemma.

######  Lemma S.8.

Under $X_{1:n}\sim P^{(n)}$, for every $j=1,\dots,t$, $s_{j}\geq 1$ and
$(\theta_{1},\dots,\theta_{s_{j}})\in\mathbb{R}^{s_{j}}$, we have

$\displaystyle
E\left\\{\prod_{h=1}^{s_{j}}\int_{\mathbb{R}^{s_{j}}}\prod_{i\in
A^{j}_{h}}\frac{g(X_{i}-\theta_{h})}{g(X_{i}-\theta_{j}^{*})}q_{0}(\theta_{h})\,\mathrm{d}\theta_{h}\right\\}$
$\displaystyle\leq\left(\frac{U}{m}\right)^{s_{j}}\prod_{h=1}^{s_{j}}\frac{1}{a^{j}_{h}+1},$

with $m$ and $U$ defined in $T1$ and $T3$.

###### Proof.

Without loss of generality assume $\theta_{j}^{*}=0$. Taking the expectation
under $P^{(n)}$ we have

$\displaystyle
E\left\\{\int_{\mathbb{R}^{s_{j}}}\prod_{h=1}^{s_{j}}\prod_{i\in
A^{j}_{h}}\frac{g(X_{i}-\theta_{h})}{g(X_{i})}q_{0}(\theta_{h})\,\mathrm{d}\theta_{h}\right\\}$
$\displaystyle=\int_{\mathbb{R}^{s_{j}}}\int_{[-c,c]^{n_{j}}}\prod_{h=1}^{s_{j}}\prod_{i\in
A^{j}_{h}}g(x_{i}-\theta_{h})q_{0}(\theta_{h})\,\mathrm{d}x_{i}\,\mathrm{d}\theta_{h},$
(S.9)

By the change of variables $z=x-\theta_{h}$, we have

$\int_{-c}^{c}g(x-\theta_{h})\mathbbm{1}_{[\theta_{h}-c,\theta_{h}+c]}(x)\,\mathrm{d}x=\int_{-c-\theta_{h}}^{c-\theta_{h}}g(z)\mathbbm{1}_{[-c,c]}(z)\,\mathrm{d}z.$

If $\theta_{h}>0$, then

$\displaystyle\int_{-c-\theta_{h}}^{c-\theta_{h}}g(z)\mathbbm{1}_{[-c,c]}(z)\,\mathrm{d}z$
$\displaystyle=\mathbbm{1}_{[0,2c]}(\theta_{h})\int_{-c}^{c-\theta_{h}}g(z)\,\mathrm{d}z$
$\displaystyle=\mathbbm{1}_{[0,2c]}(\theta_{h})\left(1-\int_{c-\theta_{h}}^{c}g(z)\,\mathrm{d}z\right)\leq\mathbbm{1}_{[0,2c]}(|\theta_{h}|)\left(1-m|\theta_{h}|\right).$

Similarly, if $\theta_{h}<0$ we get

$\displaystyle\int_{-c-\theta_{h}}^{c-\theta_{h}}g(z)\mathbbm{1}_{[-c,c]}(z)\,\mathrm{d}z$
$\displaystyle=\mathbbm{1}_{[-2c,0]}(\theta_{h})\int_{-c-\theta_{h}}^{c}g(z)\,\mathrm{d}z$
$\displaystyle=\mathbbm{1}_{[-2c,0]}(\theta_{h})\left(1-\int_{-c}^{-c-\theta_{h}}g(z)\,\mathrm{d}z\right)\leq\mathbbm{1}_{[0,2c]}(|\theta_{h}|)\left(1-m|\theta_{h}|\right).$

Thus

$\int_{-c}^{c}g(x-\theta_{h})\mathbbm{1}_{[\theta_{h}-c,\theta_{h}+c]}(x)\,\mathrm{d}x\leq\mathbbm{1}_{[0,2c]}(|\theta_{h}|)\left(1-m|\theta_{h}|\right),\quad
h=1,\dots,s_{j},$

which implies

$\prod_{h=1}^{s_{j}}\prod_{i\in
A^{j}_{h}}\int_{-c}^{c}g(x-\theta_{h})\mathbbm{1}_{[\theta_{h}-c,\theta_{h}+c]}(x)\,\mathrm{d}x\leq\prod_{h=1}^{s_{j}}\mathbbm{1}_{[0,2c]}(|\theta_{h}|)\left(1-m|\theta_{h}|\right).$

Considering $h$ defined as in $T3$, we have

$\int_{\mathbb{R}}\mathbbm{1}_{[0,2c]}(|\theta_{h}|)\left(1-m|\theta_{h}|\right)q_{0}(\theta_{h})\,\mathrm{d}\theta_{h}=\int_{0}^{2c}\left(1-m|\theta_{h}|\right)h(\theta_{h})\,\mathrm{d}\theta_{h},\quad
h=1,\dots,s_{j}.$

Combining the above with (S.9) we get

$\displaystyle
E\left\\{\int_{\mathbb{R}^{s_{j}}}\prod_{h=1}^{s_{j}}\prod_{i\in
A^{j}_{h}}\frac{g(X_{i}-\theta_{h})}{g(X_{i})}q_{0}(\theta_{h})\,\mathrm{d}\theta_{h}\right\\}$
$\displaystyle=\int_{\mathbb{R}^{s_{j}}}\int_{[-c,c]^{n_{j}}}\prod_{h=1}^{s_{j}}\prod_{i\in
A^{j}_{h}}g(x_{i}-\theta_{h})q_{0}(\theta_{h})\,\mathrm{d}x_{i}\,\mathrm{d}\theta_{h}$
(S.10)
$\displaystyle\leq\prod_{h=1}^{s_{j}}\int_{0}^{2c}\left(1-m|\theta_{h}|\right)h(\theta_{h})\,\mathrm{d}\theta_{h}.$

With $U$ defined as in $T3$, we have

$\int_{0}^{2c}(1-my)^{a_{h}^{j}}h(y)\,\mathrm{d}y\leq
U\int_{0}^{2c}(1-my)^{a_{h}^{j}}\,\mathrm{d}y.$

Now consider the change of variables $u=1-my$ and compute

$\displaystyle\int_{0}^{2c}(1-my)^{a_{h}^{j}}\,\mathrm{d}y$
$\displaystyle=\frac{1}{m}\int_{1-2mc}^{1}u^{a_{h}^{j}}\,\mathrm{d}u=\frac{1-(1-2mc)^{a_{h}^{j}+1}}{m(a_{h}^{j}+1)}\leq\frac{1}{m(a_{h}^{j}+1)}.$

Finally, through (S.10), we have

$\displaystyle
E\left\\{\int_{\mathbb{R}^{s_{j}}}\prod_{h=1}^{s_{j}}\prod_{i\in
A^{j}_{h}}\frac{g(X_{i}-\theta_{h})}{g(X_{i})}q_{0}(\theta_{h})\,\mathrm{d}\theta_{h}\right\\}$
$\displaystyle\leq\prod_{h=1}^{s_{j}}\int_{0}^{2c}\left(1-m|\theta_{h}|\right)h(\theta_{h})\,\mathrm{d}\theta_{h}$
$\displaystyle\leq\left(\frac{U}{m}\right)^{s_{j}}\prod_{h=1}^{s_{j}}\frac{1}{a_{h}^{j}+1},$

as desired. $\Box$

###  S.5.1 Proof of Theorem 1

We have the next two technical lemmas.

######  Lemma S.9.

Let $p^{*}=\min_{j\in\\{1,\dots,t\\}}p_{j}\in(0,1)$. It holds

$\sum_{\textbf{s}\in\textbf{S}}\frac{s!}{\prod_{j=1}^{t}s_{j}!}=\sum_{\textbf{s}}\binom{s}{s_{1},\dots,s_{t}}\leq(p^{*})^{-s},$

where $\textbf{S}=\left\\{(s_{1},\dots,s_{t})\,:\,s_{j}\leq n_{j}\text{ and
}\sum_{j=1}^{t}s_{j}=s\right\\}$.

###### Proof.

The result follows immediately from

$\displaystyle\sum_{\textbf{s}\in\textbf{S}}\binom{s}{s_{1},\dots,s_{t}}$
$\displaystyle\leq(p^{*})^{-s}\sum_{\textbf{s}\in\textbf{S}}\binom{s}{s_{1},\dots,s_{t}}\prod_{j=1}^{t}p_{j}^{s_{j}}$
$\displaystyle\leq(p^{*})^{-s}\sum_{\textbf{s}\in
R_{t}}\binom{s}{s_{1},\dots,s_{t}}\prod_{j=1}^{t}p_{j}^{s_{j}}=(p^{*})^{-s},$

where $R_{t}=\left\\{(s_{1},\dots,s_{t})\,:\,\sum_{j=1}^{t}s_{j}=s\right\\}$,
since the sum on the right-hand side is the sum of the probabilities over all
the possible values of a multinomial distribution with parameters
$(s,p_{1},\dots,p_{t})$. $\Box$

######  Lemma S.10.

For every $p>1$ and for every integers $s\geq 2$ and $n\geq s$ it holds

$\displaystyle\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\left(\frac{n}{\prod_{j=1}^{s}a_{j}}\right)^{p}<C_{p}^{s-1},$

where
$\mathcal{F}_{s}(n)=\left\\{\textbf{a}\in\\{1,\ldots,n\\}^{s}:\sum_{j=1}^{s}a_{j}=n\right\\}$
and $C_{p}=2^{p}\zeta(p)$, with
$\zeta(p)=\sum_{a=1}^{\infty}\frac{1}{a^{p}}<\infty$.

###### Proof.

We prove the result by induction. Consider the base case $s=2$. By the strict
convexity of $x\mapsto x^{p}$ for $p>1$ we have

$\displaystyle\sum_{\bm{a}\in\mathcal{F}_{2}(n)}\left(\frac{n}{a_{1}a_{2}}\right)^{p}=\sum_{a=1}^{n-1}\left\\{\frac{n}{a(n-a)}\right\\}^{p}=2^{p}\sum_{a=1}^{n-1}\left(\frac{1}{2}\frac{1}{a}+\frac{1}{2}\frac{1}{n-a}\right)^{p}<2^{p}\sum_{a=1}^{n-1}\frac{1}{a^{p}}<C_{p},$

for every $n\geq 2$. For the induction step, assume that for some $s\geq 3$ we
have

$\sum_{\bm{a}\in\mathcal{F}_{s-1}(n)}\left(\frac{n}{\prod_{j=1}^{s-1}a_{j}}\right)^{2}<C_{p}^{s-2}$

for all $n\geq s-1$. Then

$\displaystyle\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\left(\frac{n}{\prod_{j=1}^{s}a_{j}}\right)^{p}$
$\displaystyle=\sum_{a_{s}=1}^{n-s+1}\sum_{(a_{1},\dots,a_{s-1})\in\mathcal{F}_{s-1}(n-a_{s})}\left(\frac{n}{\prod_{j=1}^{s}a_{j}}\right)^{p}$
$\displaystyle=\sum_{a_{s}=1}^{n-s+1}\left\\{\frac{n}{(n-a_{s})a_{s}}\right\\}^{p}\sum_{(a_{1},\dots,a_{s-1})\in\mathcal{F}_{s-1}(n-a_{s})}\left(\frac{n-a_{s}}{\prod_{j=1}^{s-1}a_{j}}\right)^{p}$
$\displaystyle\leq
C_{p}^{s-2}\sum_{a_{s}=1}^{n-s+1}\left\\{\frac{n}{(n-a_{s})a_{s}}\right\\}^{p}<C_{p}^{s-1}$

and thus the thesis follows by induction. $\Box$

In the following we will drop the subscript in $C_{p}$ when the value of $p$
is clear from the context, thus denoting $C=C_{p}$.

######  Lemma S.11.

Consider the setting of (1) with $(f,k,q_{0})$ as in Theorem 1. Moreover,
assume $\pi(\alpha)$ satisfies assumptions $A1$, $A2$, and $A3$. Then, under
$X_{1:\infty}\sim P^{(\infty)}$ we have

$E\left\\{\mathbbm{1}_{\Omega_{n}}\sum_{s=1}^{n-t}\frac{\text{pr}(K_{n}=t+s\,|\,X_{1:n})}{\text{pr}(K_{n}=t\,|\,X_{1:n})}\right\\}\to
0$

as $n\to\infty$, with $\Omega_{n}$ as in (S.7).

###### Proof.

Applying Lemma S.8 we can upper bound the expected value of $T^{(n)}$ in (S.8)
as follows

$\displaystyle\mathbb{E}\left\\{T^{(n)}\right\\}\leq\frac{2^{t}\sqrt{\hbox{log}(n)}}{K}\left(\frac{U}{m}\right)^{s}$
$\displaystyle\sum_{\textbf{s}}\prod_{j=1}^{t}\sum_{A_{j}\in\tau_{s_{j}}(n_{j})}\frac{n_{j}}{(n_{j}-1)!\prod_{k=1}^{s_{j}}(a^{j}_{k}+1)}$
$\displaystyle\leq\frac{2^{t}\sqrt{\hbox{log}(n)}}{K}\left(\frac{U}{m}\right)^{s}\sum_{\textbf{s}}\prod_{j=1}^{t}\frac{1}{s_{j}!}\sum_{\textbf{a}_{j}\in\mathcal{F}_{s_{j}}(n_{j})}\left(\frac{n_{j}}{\prod_{k=1}^{s_{j}}a^{j}_{k}}\right)^{2},$

where the last inequality follows from Lemma 3. Moreover, from Lemma S.10 we
have

$\sum_{\textbf{a}_{j}\in\mathcal{F}_{s_{j}}(n_{j})}\left(\frac{n_{j}}{\prod_{k=1}^{s_{j}}a^{j}_{k}}\right)^{2}<C^{s_{j}},$

with constant $C<7$. Thus

$\mathbb{E}\left\\{T^{(n)}\right\\}\leq\frac{2^{t}\sqrt{\hbox{log}(n)}}{K}\left(\frac{UC}{m}\right)^{s}\sum_{\textbf{s}}\prod_{j=1}^{t}\frac{1}{s_{j}!}.$
(S.11)

Moreover, from Corollary S.1 and $A3$ we have

$\displaystyle C(n,t,t+s)$
$\displaystyle\leq\frac{G\Gamma(t+\beta+1)2^{s}s}{\epsilon}E(\alpha^{t+s-})\hbox{log}\\{n/(1+\epsilon)\\}^{-1}$
(S.12)
$\displaystyle\leq\frac{DG\Gamma(t+\beta+1)2^{s}s}{\epsilon}\rho^{-(t+s-1)}\Gamma(\nu+t+s)\hbox{log}\\{n/(1+\epsilon)\\}^{-1},\quad
n\geq 4\,.$

By (S.11), combined with Lemma S.9, and (S.12) we finally have

$\displaystyle E\biggl{\\{}\mathbbm{1}_{\Omega_{n}}$
$\displaystyle\sum_{s=1}^{n-t}\frac{\text{pr}(K_{n}=s+t|X_{1:n})}{\text{pr}(K_{n}=t|X_{1:n})}\biggr{\\}}=\sum_{s=1}^{n-t}C(n,t,t+s)E\\{\mathbbm{1}_{\Omega_{n}}R(n,t,t+s)\\}$
$\displaystyle\leq\frac{2^{t}\rho^{1-t}(U/m)^{t}DG\Gamma(t+\beta+1)\sqrt{\hbox{log}(n)}}{K\epsilon\hbox{log}\\{n/(1+\epsilon)\\}}\underbrace{\sum_{s=1}^{n-1}\frac{s(2CUp^{*}/m)^{s}\rho^{-s}\Gamma(\nu+t+s)}{(s+1)!}}_{<\infty}\to
0,$

as $n\to\infty$, where finiteness follows by taking $\rho$ sufficiently large.
$\Box$

###### Proof of Theorem 1.

First of all, assume $\pi(\cdot)$ satisfies $A1-A3$. By Lemma S.11 it holds

$\mathbbm{1}_{\Omega_{n}}\sum_{s=1}^{n-t}\frac{\text{pr}(K_{n}=t+s\,|\,X_{1:n})}{\text{pr}(K_{n}=t\,|\,X_{1:n})}\to
0$

in $P^{(\infty)}$–probability as $n\to\infty$. The desired result then follows
from Lemma S.4 with
$Z_{n}=\sum_{s=1}^{n-t}\frac{\text{pr}(K_{n}=t+s\,|\,X_{1:n})}{\text{pr}(K_{n}=t\,|\,X_{1:n})}$
and $\Omega_{n}$ as in (S.7).

Assume instead $\pi(\alpha)=\delta_{\alpha^{*}}(\alpha)$ with $\alpha^{*}>0$.
By (S.5) we have

$\frac{p(K_{n}=t+1\mid X_{1:n})}{p(K_{n}=t\mid
X_{1:n})}\geq\alpha^{*}\sum_{\textbf{s}\in\textbf{S}}\prod_{j=1}^{t}\sum_{A_{j}\in\tau_{s_{j}}(n_{j})}\frac{\prod_{k=1}^{s_{j}}(a^{j}_{k}-1)!}{(n_{j}-1)!}\frac{\prod_{k=1}^{s_{j}}m(X_{A^{j}_{k}})}{m(A_{C_{j}})}.$

Notice that, with $n$ high enough, $n_{1}>1$ almost surely. Then, denoting
$i\in C_{1}$, we consider the special case

$\textbf{s}=(2,1,\dots,1),\quad
A^{1}_{1}=\\{i\\},A_{2}^{1}=A_{C_{1}}\backslash\\{i\\},$

and $A_{j}=\\{A_{C_{j}}\\}$ for every $j\geq 2$. Thus we can write

$\frac{p(K_{n}=t+1\mid X_{1:n})}{p(K_{n}=t\mid
X_{1:n})}\geq\alpha^{*}\sum_{i\in
C_{1}}\frac{1}{n_{1}-1}\frac{m(X_{i})m\left(X_{C_{1}\backslash
i}\right)}{m\left(X_{C_{j}}\right)}.$ (S.13)

By $T1$ we have

$\displaystyle m\left(X_{C_{j}}\right)$
$\displaystyle=\int_{\mathbb{R}}\prod_{j\in
C_{1}}g(X_{j}-\theta)q_{0}(\theta)\,\mathrm{d}\theta$ $\displaystyle\leq
M\int_{\mathbb{R}}\prod_{j\in C_{1}\backslash
i}g(X_{j}-\theta)q_{0}(\theta)\,\mathrm{d}\theta=M\,m\left(X_{C_{1}\backslash
i}\right).$

Moreover, by $T4$ there exists $\epsilon>0$ such that

$\displaystyle
m(X_{i})=\int_{\mathbb{R}}g(X_{i}-\theta)q_{0}(\theta)\mathrm{d}\theta$
$\displaystyle\geq
m\int_{\theta_{1}^{*}-\epsilon}^{\theta_{1}^{*}+\epsilon}q_{0}(\theta)\mathrm{d}\theta$
$\displaystyle\geq 2mL\epsilon.$

Therefore, (S.13) becomes

$\frac{p(K_{n}=t+1\mid X_{1:n})}{p(K_{n}=t\mid
X_{1:n})}\geq\frac{2\alpha^{*}mL\epsilon}{M}\sum_{i\in
C_{1}}\frac{1}{n_{1}-1}=\frac{2\alpha^{*}mL\epsilon}{M}\frac{n_{1}}{n_{1}-1},$

and

$\lim\inf_{n\to\infty}\sum_{s\neq t}\frac{p(K_{n}=s\mid
X_{1:n})}{p(K_{n}=t\mid
X_{1:n})}\geq\lim\inf_{n\to\infty}\frac{p(K_{n}=t+1\mid
X_{1:n})}{p(K_{n}=t\mid X_{1:n})}\geq\frac{\alpha^{*}mL\epsilon}{M}>0.$

Then

$\displaystyle\lim\sup_{n\to\infty}\text{pr}(K_{n}=t\mid X_{1:n})$
$\displaystyle=\lim\sup_{n\to\infty}\left\\{1+\sum_{s\neq
t}\frac{\text{pr}(K_{n}=s\mid X_{1:n})}{\text{pr}(K_{n}=t\mid
X_{1:n})}\right\\}^{-1}$
$\displaystyle=\frac{1}{1+\lim\inf_{n\to\infty}\sum_{s\neq
t}\frac{p(K_{n}=s\mid X_{1:n})}{p(K_{n}=t\mid X_{1:n})}}>0,$

which completes the proof. $\Box$

##  S.6 Proof of Proposition 1

We adapt the proof of Theorem $2.1$ in Cai et al. (2021). Denote by

$\Psi=\left\\{k(\cdot\mid\theta):\theta\in\Theta\subseteq\mathbb{R}^{p}\right\\}$

the family of kernels, dominated by $\mu$, either Lebesgue or counting
measure, and with common domain $\mathbb{X}\subseteq\mathbb{R}^{q}$. Denote
with $B_{x}(\epsilon)$ the closed ball of center $x\in\mathbb{X}$ and radius
$\epsilon>0$. Let $\bar{\Theta}$ be the closure of $\Theta$ and define the set

$\mathbb{B}:=\left\\{\bar{\theta}\in\bar{\Theta}\backslash\Theta\,:\,\lim_{\theta\to\bar{\theta}}\left\\{\sup_{x}k(x\mid\theta)\right\\}=\infty\right\\}.$

Let $\mathbb{G}_{s}$ be the set of mixtures of exactly $s$ elements in $\Psi$,
that is

$f\in\mathbb{G}_{s}\quad\Leftrightarrow\quad
f=\sum_{j=1}^{s}q_{j}k(\cdot\mid\theta_{j}),$

with $q_{j}>0$ for every $j$, $\sum_{j=1}^{s}q_{j}=1$ and
$\theta_{i}\neq\theta_{h}$ for every $i\neq h$. Let $\mathcal{P}(G)$ be the
set of probability measures on a generic space $G$; with a slight abuse of
notation we will say $f\in\mathcal{P}(G)$ when $f$ is the density of a
probability measure $P\in\mathcal{P}(G)$. Therefore, given
$P\in\mathbb{G}_{t}$, with weights $\\{p_{j}\\}_{j=1}^{t}$ and parameters
$\\{\theta_{j}^{*}\\}_{j=1}^{t}$, we define the Kullback-Leibler neighborhoods
of $P$ as

$KL_{\epsilon}(P):=\bigg{\\{}h\in\mathcal{P}(\mathbb{X}):\int\hbox{log}\bigg{\\{}\frac{\sum_{j=1}^{t}p_{j}k(x\mid\theta_{j}^{\ast})}{h(x)}\bigg{\\}}P(\mathrm{d}x)<\epsilon\bigg{\\}},$
(S.14)

for $\epsilon>0$. We make the following assumptions:

  1. $H1.$

For every $\bar{\theta}\in\Theta\backslash\mathbb{B}$, for $\mu$-almost every
$x\in\mathbb{X}$ there exists
$A:=A(\bar{\theta},x)\subset\Theta\backslash\mathbb{B}$ neighborhood of
$\bar{\theta}$ so that the mapping $\theta\in A\to k(x\mid\theta)$ is
continuous. Moreover $\mathbb{B}$ is closed;

  2. $H2.$

Let $\\{\theta_{i}\\}_{i=1}^{\infty}\subset\Theta$. If
$||\theta_{i}||\to\infty$ as $i\to\infty$, then for every compact set
$K\subset\mathbb{X},$
$\int_{K}k(x\mid\theta_{i})\,\mu(\mathrm{d}x)\to 0$, as $i\to\infty$. If
$\theta_{i}\to\bar{\theta}\in\mathbb{B}$, then there exists
$x^{*}\in\mathbb{X}$ such that
$k(\cdot\mid\theta_{i})\to\delta_{x^{*}}(\cdot)$ weakly as $i\to\infty$;

  3. $H3.$

If $f\in\mathbb{G}_{t}$, then there exist no $f^{\prime}\in\mathbb{G}_{s}$,
with $s<t$, such that $f(x)=f^{\prime}(x)$ $\mu$-almost surely;

  4. $H4.$

For every $P\in\mathbb{G}_{t}$, $t\geq 1$, with
$\theta_{1}^{*},\dots,\theta_{t}^{*}$ belonging to the support of $Q_{0}$, we
have
$\text{pr}(h\in K_{\epsilon}(P))>0$ for every $\epsilon>0$, where $h$ follows
the prior distribution in (1).

Assumption $H2$ says that, when $\theta$ diverges or converges to elements in
$\mathbb{B}$, the kernel $k$ degenerates: it is satisfied for instance when
the elements of $\theta$ are location or scale parameters. $H3$ instead
implies that the clustering problem is not ill-posed, in the sense that
different numbers of components always lead to different distribution. $H4$
finally requires that the finite mixtures of the kernel $k(\cdot\mid\theta)$
belongs to the Kullback-Leibler support of the prior. They are all weak
requirements, satisfied by the most common kernels. Next Lemma shows that they
are satisfied under assumptions $B1-B3$.

######  Lemma S.12.

Suppose the kernel $k(x\mid\theta)$ satisfies assumptions $B1-B3$. Then
$H1-H4$ are fulfilled.

###### Proof.

Assumption $H3$ can be easily deduced from $B1$ and (6). As regards $H1$,
since $\sup_{\theta\in\Theta,x\in\mathbb{X}}k(x\mid\theta)<\infty$, we have
$\mathbb{B}=\emptyset$. Moreover, fix $\bar{\theta}\in\mathbb{R}$. If
$x>\theta+b$, choose

$A(\bar{\theta},x)=\left(\bar{\theta}-\frac{x-\bar{\theta}-b}{2},\bar{\theta}+\frac{x-\bar{\theta}-b}{2}\right),$

so that $x>\theta+b$ that implies $k(x\mid\theta)=0$ for every $\theta\in
A(\bar{\theta},x)$. Similarly, if $x<\theta+a$, choose

$A(\bar{\theta},x)=\left(\bar{\theta}-\frac{\bar{\theta}+a-x}{2},\bar{\theta}+\frac{\bar{\theta}+a-x}{2}\right).$

Finally, if $x\in(\bar{\theta}+a,\bar{\theta}+b)$, denoting
$d=\min\\{\bar{\theta}+b-x,x-\bar{\theta}-a\\}$, choose

$A(\bar{\theta},x)=\left(\bar{\theta}-\frac{d}{2},\bar{\theta}+\frac{d}{2}\right).$

Then $k(x\mid\theta)=g(x-\theta)$ for every $\theta\in A(\bar{\theta},x)$ and
$g$ is continuous on $(a,b)$, by $B2$. Thus we can find the required
neighborhood $A(\bar{\theta},x)$ for every
$x\not\in\\{\bar{\theta}+a,\bar{\theta}+b\\}$, that is for $\mu$-almost every
$x$, since $\mu$ is the Lebesgue measure. Therefore $H1$ is satisfied.

$H2$ follows since $\theta$ is a location parameter and $\bar{\Theta}=\Theta$.
We are left to show that $H4$ is satisfied: we prove the case $t=1$ and the
general setting follows similarly.

Recall that assumptions $B1-B3$ can be rewritten as $T1-T4$ in the proof of
Theorem 1 and let $f(x)=k(x\mid\theta^{*})$ be the density function of $P$.
Fix $\delta>0$, $\epsilon>0$ and denote $r=1-exp(\epsilon/4)$. Define the set

$\displaystyle\mathbb{F}(\delta,r):=\biggl{\\{}p(x)=\sum_{j=1}^{\infty}q_{j}k(x\mid\theta_{j})\,:$
$\displaystyle q_{1}\in[1-r,1],q_{2}\in[r/2,1],$ (S.15) $\displaystyle
0\leq\theta^{\ast}-\theta_{1}\leq\delta,0\leq\theta_{2}-\theta^{\ast}\leq\delta\biggr{\\}}.$

We denote $[a_{j},b_{j}]:=[a+\theta_{j},b+\theta_{j}]$, with $j\geq 1$, and
similarly $[a^{*},b^{*}]:=[a+\theta^{*},b+\theta^{*}]$. Then we can choose
$\delta$ small enough such that

$[a_{1},b_{1}]\cup[a_{2},b_{2}]\supseteq[a^{\ast},b^{\ast}],$

for every $\theta_{1}$ and $\theta_{2}$ as in (S.15). Moreover, for every
$x\in S_{1}:=[a_{1},b_{1}]\cap[a^{\ast},b^{\ast}]$ we have

$\displaystyle\hbox{log}\left\\{\frac{g(x-\theta^{\ast})}{q_{1}g(x-\theta_{1})}\right\\}$
$\displaystyle=-\hbox{log}(q_{1})+\hbox{log}\left\\{\frac{g(x-\theta^{\ast})}{g(x-\theta_{1})}\right\\}\leq\epsilon/4+\hbox{log}\left\\{\frac{g(x-\theta^{\ast})}{g(x-\theta_{1})}\right\\}$
$\displaystyle\leq\epsilon/4+R|\theta^{*}-\theta_{1}|\,$

with $R>0$ as in $T2$. Therefore we can choose $\delta$ small enough so that

$\hbox{log}\left\\{\frac{g(x-\theta^{\ast})}{q_{1}g(x-\theta_{1})}\right\\}<\frac{\epsilon}{2}$
(S.16)

for every $x\in S_{1}$. Similarly, we can choose $\delta$ small enough so that
for every $x\in S_{2}:=[a^{\ast},b^{\ast}]\setminus[a_{1},b_{1}]$ we have

$\int_{S_{2}}g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{q_{2}g(x-\theta_{2})}\bigg{\\}}\mathrm{d}x<\frac{\epsilon}{2}.$
(S.17)

Indeed, since $g(x-\theta^{*})\leq M$ and $m\leq g(x-\theta_{2})$ for every
$x$ in $S_{2}$, with $m$ and $M$ as in $T1$, we have

$g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{q_{2}g(x-\theta_{2})}\bigg{\\}}<M\hbox{log}\\{2M/(mr)\\},$

and $S_{2}$ has arbitrarily small length with $\delta$ small enough. For every
$p\in\mathbb{F}(\delta,r)$, by applying (S.16) and (S.17), we have

$\displaystyle\int_{a^{*}}^{b^{*}}g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{\sum_{j=1}^{\infty}q_{j}g(x-\theta_{j})}\bigg{\\}}\mathrm{d}x=$
$\displaystyle\int_{S_{1}}g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{\sum_{j=1}^{\infty}q_{j}g(x-\theta_{j})}\bigg{\\}}\mathrm{d}x+\int_{S_{2}}g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{\sum_{j=1}^{\infty}q_{j}g(x-\theta_{j})}\bigg{\\}}\mathrm{d}x\leq$
$\displaystyle\int_{S_{1}}g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{q_{1}g(x-\theta_{1})}\bigg{\\}}\mathrm{d}x+\int_{S_{2}}g(x-\theta^{\ast})\hbox{log}\bigg{\\{}\frac{g(x-\theta^{\ast})}{q_{2}g(x-\theta_{2})}\bigg{\\}}\mathrm{d}x\leq\epsilon.$

Thus, $\mathbb{F}(\delta,r)\subseteq K_{\epsilon}(P)$ for $\delta$ small
enough. Moreover, since $\theta^{*}$ belongs to the support of $Q_{0}$ and the
Dirichlet process prior has full weak support on the space of probability
weights $\\{q_{j}\\}_{j}$, we have that

$\text{pr}\\{h\in
K_{\epsilon}(P)\\}\geq\text{pr}\\{h\in\mathbb{F}(\delta,r)\\}>0,$

as desired. $\Box$

The proof of Proposition 1 will rely on the following Lemma.

######  Lemma S.13.

Let assumption $H4$ be satisfied and let $P\in\mathbb{G}_{t}$ with parameters
$\theta_{1}^{*},\dots,\theta_{t}^{*}$ belonging to the support of $Q_{0}$.
Assume there exists $\mathcal{U}$ weak neighborhood of $P$ such that
$\mathcal{U}\cap\mathbb{G}_{s}=\emptyset$ for every $s<t$. Then

$\text{pr}\left(K_{n}<t\mid X_{1:n}\right)\to 0,$

in $P^{(\infty)}$-probability as $n\to\infty$.

###### Proof.

By assumption $H4$, the posterior distribution is consistent at $P$ under the
weak topology, in virtue of Schwartz theorem (see e.g.Theorem $6.16$ and
Example $6.20$ in Ghosal and Van Der Vaart (2017)), so that

$\text{pr}(h\in\mathcal{U}^{c}\mid X_{1:n})\to 0,$ (S.18)

in $P^{(\infty)}$-probability as $n\to\infty$. Moreover, we have

$\text{pr}(h\in\mathcal{U}^{c}\mid
X_{1:n})\geq\text{pr}(h\in\mathcal{U}^{c}\mid
X_{1:n},K_{n}<t)\text{pr}\left(K_{n}<t\mid X_{1:n}\right).$

Notice that, conditional on $K_{n}<t$, the domain of the posterior
distribution is a subset of $\cup_{s<t}\mathbb{G}_{s}$. Thus we have
$\text{pr}(h\in\mathcal{U}^{c}\mid X_{1:n},K_{n}<t)=1$ and

$\text{pr}(h\in\mathcal{U}^{c}\mid X_{1:n})\geq\text{pr}\left(K_{n}<t\mid
X_{1:n}\right).$

The result follows from (S.18). $\Box$

We need two technical Lemmas.

######  Lemma S.14.

Assume a sequence $\\{f_{i}\\}_{i=1}^{\infty}\subset\cup_{s<t}\mathbb{G}_{s}$
is such that $f_{i}\to f\in\mathcal{P}(\mathbb{X})$ weakly as $i\to\infty$.
Then there exist $s^{\prime}<t$ and a sequence
$\\{f^{\prime}_{i}\\}_{i=1}^{\infty}\subset\mathbb{G}_{s^{\prime}}$ such that
$f^{\prime}_{i}\to f$ weakly as $i\to\infty$.

###### Proof.

Define

$a_{s}:=\sup\\{i\geq 1\,:\,f_{i}\in\mathbb{G}_{s}\\}$

with $s<t$. By construction, there exists $s^{\prime}$ such that
$a_{s^{\prime}}=\infty$ and $\\{f^{\prime}_{i}\\}$ is the subsequence of
elements of $\\{f_{i}\\}$ that belong to $\mathbb{G}_{s^{\prime}}$. $\Box$

######  Lemma S.15.

Let
$\left\\{f_{i}=\sum_{j=1}^{s}q_{j,i}k(\cdot\mid\theta_{j,i})\right\\}_{i=1}^{\infty}\subset\mathbb{G}_{s}$
be such that $f_{i}\to f\in\mathcal{P}(\mathbb{X})$ weakly as $i\to\infty$.
Then there exist $s^{\prime}\leq s$ and a sequence
$\\{f^{\prime}_{i}\\}_{i=1}^{\infty}\subset\mathbb{G}_{s^{\prime}}$ such that
$f^{\prime}_{i}\to f$ weakly as
$i\to\infty$ and

$\lim\inf_{i}q^{\prime}_{j,i}>0$

for every $j=1,\dots,s^{\prime}$.

###### Proof.

If $\lim\inf_{i}q_{j,i}=0$ for every $j=1,\dots,s$, the statement is true by
taking $s:=s^{\prime}$ and $f^{\prime}_{i}:=f_{i}$ for every $i\geq 1$. Then
assume there exists $l$ such that $\lim\inf_{i}q_{l,i}=0$. Consider a
subsequence $\\{\tilde{f}_{i}\\}_{i=1}^{\infty}$, with weights
$\\{\tilde{q}_{j,i}\\}_{i}$ and parameters $\\{\tilde{\theta}_{j,i}\\}_{i}$,
such that $\lim_{i}\tilde{q}_{l,i}=0$ and define

$f^{\prime}_{i}(x)=\sum_{j\neq l}\frac{\tilde{q}_{j,i}}{\sum_{r\neq
l}\tilde{q}_{r,i}}k(x\mid\tilde{\theta}_{j,i}),$

where $\sum_{r\neq l}\tilde{q}_{r,i}\to 1$, by construction. Let
$A\subset\mathbb{X}$, then

$\displaystyle\left\lvert\int_{A}\tilde{f}_{i}(x)\mu(\mathrm{d}x)-\int_{A}f^{\prime}_{i}(x)\mu(\mathrm{d}x)\right\rvert$
$\displaystyle=\sum_{j\neq l}\left(\frac{\tilde{q}_{j,i}}{\sum_{r\neq
l}\tilde{q}_{r,i}}-\tilde{q}_{j,i}\right)\int_{A}k(x\mid\tilde{\theta}_{j,i})\mu(\mathrm{d}x)$
$\displaystyle+\tilde{q}_{l,i}\int_{A}k(x\mid\tilde{\theta}_{l,i})\mu(\mathrm{d}x)\leq\sum_{j\neq
l}\left(\frac{\tilde{q}_{j,i}}{\sum_{r\neq
l}\tilde{q}_{r,i}}-\tilde{q}_{j,i}\right)+\tilde{q}_{l,i}\to 0,$

as $i\to\infty$. Therefore, since $A$ is arbitrary and $\\{\tilde{f}_{i}\\}$
converges to $f$, also $\\{f^{\prime}_{i}\\}$ converges weakly to $f$ and
$\\{f^{\prime}_{i}\\}_{i=1}^{\infty}\in\mathbb{G}_{s-1}$. The result follows
by applying recursively the above procedure for every $l$ satisfying
$\lim\inf_{i}q_{l,i}=0$. $\Box$

###### Proof of Proposition 1.

By Lemma S.12 we can assume $H1-H4$ and by Lemma S.13, it suffices to prove
the existence of a weak neighborhood $\mathcal{U}$ of $P$ such that
$\mathcal{U}\cap\mathbb{G}_{s}=\emptyset$, for every $s<t$. Assume by
contradiction that no such $\mathcal{U}$ exists. Then, there exists a sequence
$\\{f_{i}\\}\in\cap_{s<t}\mathbb{G}_{s}$ such that $f_{i}\to f$ weakly, as
$i\to\infty$, where $f$ is the density of $P$. By Lemmas S.14 and S.15 we can
assume without loss of generality that $\\{f_{i}\\}\in\mathbb{G}_{s}$, with
$s<t$, and $\lim\inf_{i}q_{j,i}>0$ for every $j=1,\dots,s$. We will consider
three scenarios, of which at least one must hold: (i) there exists
$l\in\\{1,\dots,s\\}$ such that $\lim\sup_{i}||\theta_{l,i}||=\infty$, (ii)
the sequences $\\{\theta_{j,i}\\}_{i=1}^{\infty}$, with $j=1,\dots,s$, belong
to a compact set $C\subset\Theta\backslash\mathbb{B}$ for $i$ large enough,
(iii) the sequences $\\{\theta_{j,i}\\}_{i=1}^{\infty}$, with $j=1,\dots,s$,
belong to a compact set $C\subset\Theta$ and there exists
$l\in\\{1,\dots,s\\}$ such that
$\lim\inf_{i}\inf_{\theta\in\mathbb{B}}||\theta_{l,i}-\theta||=0$.

First consider case (i) and assume there exists $1\leq l\leq s$ such that
$||\theta_{l,r(i)}||\to\infty$ as $i\to\infty$ for a suitable subsequence
$r(i)$. Fix $0<\epsilon<\lim\inf_{i}q_{l,i}$ and choose $K\subset\mathbb{X}$
compact set such that $P(K)>1-\epsilon/4$. By assumption $H2$ we have

$\int_{K^{c}}f_{r(i)}(x)\mu(\mathrm{d}x)>q_{l,r(i)}\int_{K^{c}}k(x\mid\theta_{l,r(i)})\mu(\mathrm{d}x)>\frac{\epsilon}{2},$

for $i$ large enough, which contradicts the weak convergence of
$\\{f_{i}\\}_{i=1}^{\infty}$ to $f$.

Second, assume to be in case (ii) and there exists a compact set
$C\subset\Theta\backslash\mathbb{B}$ such that $\theta_{i,j}\in C$ for every
$i\geq 1$ and $j=1,\dots,s$. Define the set

$\mathbb{D}_{s}:=\left\\{\nu(\mathrm{d}\theta)=\sum_{j=1}^{s}q_{j}\delta_{\theta_{j}}(\mathrm{d}\theta)\,:\,\theta_{j}\in
C,q_{j}>0,\sum_{j=1}^{s}q_{j}=1\right\\}\subset\mathcal{P}(\Theta).$

Since $C$ is compact, we have that $\mathbb{D}_{s}$ is tight. By Prokhorov’s
Theorem $\mathbb{D}_{s}$ is also relatively compact, so that there exists a
subsequence $r(i)$ such that

$\nu_{r(i)}=\sum_{j=1}^{s}q_{j,r(i)}\delta_{\theta_{j,r(i)}}\to\nu\in\mathcal{P}(\Theta)$

weakly as $i\to\infty$. By Lemma $4.1$ in Cai et al. (2021) we have
$\nu\in\mathbb{D}_{s}$, so that
$\nu=\sum_{j=1}^{s}\tilde{q}_{j}\delta_{\tilde{\theta}_{j}}$ for some
$\tilde{q}_{j}\in(0,1)$, $\sum_{j=1}^{s}\tilde{q}_{j}=1$ and
$\tilde{\theta}_{j}\in C$, for $j=1,\dots,s$. By $H1$ and
$C\subset\Theta\backslash\mathbb{B}$, for $\mu$-almost every $x\in\mathbb{X}$,
we can find $C_{j}:=C_{j}(x,\tilde{\theta}_{j})$, with $j=1,\dots,s$, closed
neighborhood of $\tilde{\theta}_{j}$, so that $k(x\mid\theta)$ is continuous
as a function of $\theta$, with $\theta\in C_{j}$. Define
$D:=\left\\{\bigcup_{j=1}^{s}C_{j}\right\\}\cap C$ compact set: notice that
$D\neq\emptyset$, since $\tilde{\theta}_{j}\in C\cap C_{j}$, with
$j=1,\dots,s$. Moreover, by construction, the mapping $\theta\in D\to
k(x\mid\theta)$ is continuous and therefore bounded, since $D$ is compact.
Since $\nu_{i}\to\nu$ weakly, as $i\to\infty$, there exists $I$ such that for
every $i\geq I$ we have $\theta_{j,r(i)}\in D$, for every $j=1,\dots,s$. Thus,
by definition of weak convergence we have

$\sum_{j=1}^{s}q_{j,r(i)}k(x\mid\theta_{j,r(i)})=\int
k(x\mid\theta)\nu_{r(i)}(\mathrm{d}\theta)\to\int
k(x\mid\theta)\nu(\mathrm{d}\theta)=\sum_{j=1}^{s}\tilde{q}_{j}k(x\mid\tilde{\theta}_{j}),$

as $i\to\infty$. Since almost sure pointwise convergence of densities implies
weak convergence, we have

$f_{r(i)}\to\tilde{f}=\sum_{j=1}^{s}\tilde{q}_{j}k(\cdot\mid\tilde{\theta}_{j})$

weakly as $i\to\infty$. By uniqueness of the weak limit, $\tilde{f}(x)=f(x)$
for $\mu$-almost every $x$, that contradicts $H3$.

Third, consider case (iii). Since $\theta_{j,i}\in C\subset\Theta$ compact
set, for every $j=1,\dots,s$ and $i\geq 1$, there exists a suitable
subsequence $r(i)$ such that $\theta_{l,r(i)}\to\bar{\theta}$. Since
$\mathbb{B}$ is closed by $H1$, we have that $\bar{\theta}\in\mathbb{B}$. By
definition of $\mathbb{B}$, this is not possible if $\mu$ is the counting
measure, since $k(x\mid\theta)\leq 1$, for every $x\in\mathbb{X}$ and
$\theta\in\Theta$. Thus, let $\mu$ be the Lebesgue measure. Then we can fix
$\epsilon>0$ such that

$P(B_{x^{*}}(\epsilon))<\frac{\lim\inf_{i}q_{l,i}}{4},$

with $x^{*}$ as in $H2$. Then by $H2$ we have

$\int_{B_{x^{*}}(\epsilon)}f_{r(i)}(x)\mu(\mathrm{d}x)>q_{l,r(i)}\int_{B_{x^{*}}(\epsilon)}k(x\mid\theta_{l,r(i)})\mu(\mathrm{d}x)>\frac{\lim\inf_{i}q_{l,i}}{2},$

for $i$ large enough, that again contradicts the weak convergence of
$\\{f_{i}\\}_{i=1}^{\infty}$ to $f$. $\Box$

##  S.7 Proof of Theorem 2

The marginal distribution is available and given by the following lemma.

######  Lemma S.16.

Consider $k$ and $q_{0}$ as in (8). Then it holds

$\displaystyle m(x_{1:n})$
$\displaystyle=\frac{2c-\\{\max(x_{1:n},\theta^{\ast})-\min(x_{1:n},\theta^{\ast})\\}}{(2c)^{n+1}},$
$\displaystyle(x_{1:n}\in[\theta^{\ast}-c,\theta^{\ast}+c]^{n}).$

###### Proof.

Note that $x_{i}\in(\theta-c,\theta+c)$ for all $i\in\\{1,\dots,n\\}$ if and
only if $\theta\in(\max(x_{1:n})-c,\min(x_{1:n})+c)$. Thus

$\displaystyle m(x_{1:n})$
$\displaystyle=\frac{1}{(2c)^{n+1}}\int_{\Theta}\prod_{i=1}^{n}\mathbbm{1}_{(\theta-c,\theta+c)}(x_{i})\mathbbm{1}_{(\theta^{\ast}-c,\theta^{\ast}+c)}(\theta)\mathrm{d}\theta$
$\displaystyle=\frac{1}{(2c)^{n+1}}\int_{\Theta}\mathbbm{1}_{(\max(x_{1:n})-c,\min(x_{1:n})+c)}(\theta)\mathbbm{1}_{(\theta^{\ast}-c,\theta^{\ast}+c)}(\theta)\mathrm{d}\theta$
$\displaystyle=\frac{2c-\\{\max(x_{1:n},\theta^{\ast})-\min(x_{1:n},\theta^{\ast})\\}}{(2c)^{n+1}}\,.$

$\Box$

Define $\text{Range}(X_{A})=\max_{i\in A}\left(X_{i}\right)-\min_{i\in
A}\left(X_{i}\right)$. Lemma S.16 has an important corollary, that is stated
after a technical lemma.

######  Lemma S.17.

Let $A\subset\\{1,\dots,n\\}$ such that $|A|=a$, Then it holds:

$\frac{2c-\\{\max(X_{A},\theta^{\ast})-\min(X_{A},\theta^{\ast})\\}}{(2c)^{a+1}}\leq\frac{2c-\text{\rm
Range}(X_{A})}{(2c)^{a+1}}.$

###### Proof.

The result follows immediately from $\max(X_{A},\theta^{\ast})\geq\max(X_{A})$
and $\min(X_{A},\theta^{\ast})\leq\min(X_{A})$. $\Box$

######  Corollary S.2.

In the setting of (1) with $(f,k,q_{0})$ as in (8), define
$\Omega_{n}=\left\\{x\in X^{\infty}\,:\,\max(x_{1:n})\geq\theta^{\ast}\text{
and }\min(x_{1:n})\leq\theta^{\ast}\right\\}$. Then

$\displaystyle\frac{\prod_{j=1}^{s+1}m(X_{A_{j}})}{m(X_{1:n})}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})\leq\frac{\prod_{j=1}^{s+1}\\{2c-\text{\rm
Range}(X_{A_{j}})\\}}{(2c)^{s}\\{2c-\text{\rm Range}(X_{1:n})\\}},$ (S.19)

for every $A\in\tau_{s+1}(n)$ .

###### Proof.

As regards the numerator, apply firstly Lemma S.16 and then Lemma S.17 to get

$m(X_{A_{j}})=\frac{2c-\\{\max(X_{A_{j}},\theta^{\ast})-\min(X_{A_{j}},\theta^{\ast})\\}}{(2c)^{a_{j}+1}}\leq\frac{2c-\text{Range}(X_{A_{j}})}{(2c)^{a_{j}+1}},\quad
j=1,\dots,s+1\,.$

Apply Lemma S.16 to $m(x_{1:n})$ for every $x\in\Omega_{n}$, to get

$\displaystyle m(X_{1:n})\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})$
$\displaystyle=\frac{2c-\\{\max(X_{1:n},\theta^{\ast})-\min(X_{1:n},\theta^{\ast})\\}}{(2c)^{n+1}}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})$
$\displaystyle=\frac{2c-\\{\max(X_{1:n})-\min(X_{1:n})\\}}{(2c)^{n+1}}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty}),$

as desired. $\Box$

The lemma below shows that, in order to prove Theorem 2, it is sufficient to
show
$\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})\sum_{s=1}^{n-1}\frac{\text{pr}(K_{n}=s+1|X_{1:n})}{\text{pr}(K_{n}=1|X_{1:n})}\to
0$ in $P^{(\infty)}$-probability.

######  Lemma S.18.

Consider $f$ as in (8) and define $\Omega_{n}=\left\\{x\in
X^{\infty}\,:\,\max(x_{1:n})\geq\theta^{\ast}\text{ and
}\min(x_{1:n})\leq\theta^{\ast}\right\\}$. Let $\left\\{Y_{n}\right\\}$ be a
sequence of positive random variables. Thus,
$Y_{n}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})\to 0$ in
$P^{(\infty)}$-probability implies $Y_{n}\to 0$ in $P^{(\infty)}$-probability.

###### Proof.

First of all, by definition of $f$ we have

$\max(X_{1:n})\to\theta^{\ast}+c,\quad\min(X_{1:n})\to\theta^{\ast}-c$

almost surely with respect to $P^{(\infty)}$ as $n\to\infty$. Then
$P^{(\infty)}(\Omega_{n})\to 1$, as $n\to\infty$, by definition of
$\Omega_{n}$. Thus, fix $\epsilon>0$ and notice that

$P^{(\infty)}\left(Y_{n}>\epsilon\right)=P^{(\infty)}\left\\{\left(Y_{n}>\epsilon\right)\cap\Omega_{n}\right\\}+P^{(\infty)}\left\\{\left(Y_{n}>\epsilon\right)\cap\Omega_{n}^{c}\right\\}.$

The first term on the right-hand side goes to $0$, since
$Y_{n}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})\to 0$ in
$P^{(\infty)}$-probability, while the second vanishes because
$P^{(\infty)}(\Omega_{n}^{c})\to 0$, both as $n\to\infty$. $\Box$

Combining Corollary S.2 and Lemma S.18 we are ready to prove Theorem 2.

###### Proof of Theorem 2.

For every $s\geq 1$ and $A\in\tau_{s}(n)$, from Corollary S.2 we have

$\frac{\prod_{j=1}^{s}m(X_{A_{j}})}{m(X_{1:n})}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})\leq\frac{\prod_{j=1}^{s}\\{2c-\text{Range}(X_{A_{j}})\\}}{(2c)^{s-1}\\{2c-\text{Range}(X_{1:n})\\}}.$

Note that $\\{2c-\text{Range}(X_{A_{j}})\\}/(2c)\sim\text{Beta}(2,a_{j}-1)$
independently for $j=1,\ldots,s$. Moreover, recall that if
$Z\sim\text{Beta}(\alpha,\beta)$ then for $p>-\alpha$

$E(Z^{p})=\frac{\Gamma(\alpha+p)\Gamma(\alpha+\beta)}{\Gamma(\alpha+p+\beta)\Gamma(\alpha)}.$

Thus, by Hölder’s inequality with exponents $3$ and $3/2$ we get

$\displaystyle
E\bigg{\\{}\frac{\prod_{j=1}^{s}m(X_{A_{j}})}{m(X_{1:n})}\bigg{\\}}$
$\displaystyle\leq
E\left\\{\prod_{j=1}^{s}m(X_{A_{j}})^{3}\right\\}^{1/3}E\left\\{m(X_{1:n})^{-3/2}\right\\}^{2/3}$
$\displaystyle=\bigg{\\{}\frac{\Gamma(5)}{\Gamma(2)}\bigg{\\}}^{s/3}\bigg{\\{}\frac{\Gamma(1/2)}{\Gamma(2)}\bigg{\\}}^{2/3}\bigg{\\{}\prod_{j=1}^{s}\frac{\Gamma(1+a_{j})}{\Gamma(a_{j}+4)}\bigg{\\}}^{1/3}\bigg{\\{}\frac{\Gamma(1+n)}{\Gamma(n-1/2)}\bigg{\\}}^{2/3}.$

By the recursive definition of the Gamma function and recalling that
$\Gamma(1/2)=\pi^{1/2}$, the upper bound above becomes

$\displaystyle
E\bigg{\\{}\frac{\prod_{j=1}^{s}m(X_{A_{j}})}{m(X_{1:n})}\bigg{\\}}$
$\displaystyle\leq
24^{s/3}\pi^{1/3}\bigg{\\{}\prod_{j=1}^{s}\frac{\Gamma(1+a_{j})}{\Gamma(a_{j}+4)}\bigg{\\}}^{1/3}\bigg{\\{}\frac{\Gamma(1+n)}{\Gamma(n-1/2)}\bigg{\\}}^{2/3}$
$\displaystyle=24^{s/3}\pi^{1/3}\bigg{\\{}\prod_{j=1}^{s}\frac{1}{(a_{j}+3)(a_{j}+2)(a_{j}+1)}\bigg{\\}}^{1/3}\bigg{\\{}\frac{(n-1/2)\Gamma(1+n)}{\Gamma(n+1/2)}\bigg{\\}}^{2/3}.$

Moreover, exploiting again the recursive definition of the Gamma function,
Gautschi’s Inequality, i.e.
$\frac{\Gamma(1+n)}{\Gamma(n+1/2)}\leq(n+1)^{1/2}$, and
$(n+1)/(a_{j}+1)<n/a_{j}$, we have

$\displaystyle
E\bigg{\\{}\frac{\prod_{j=1}^{s}m(X_{A_{j}})}{m(X_{1:n})}\bigg{\\}}\leq
24^{s/3}K\bigg{\\{}\prod_{j=1}^{s}\frac{(n+1)^{3}}{(a_{j}+1)^{3}}\bigg{\\}}^{1/3}\leq
24^{s/3}K\bigg{(}\frac{n^{3}}{\prod_{j=1}^{s}a_{i}^{3}}\bigg{)}^{1/3}=24^{s/3}K\frac{n}{\prod_{j=1}^{s}a_{j}}.$

Thus, applying Lemma 3 and Lemma S.10 with $p=2$ and $C=4\zeta(2)<7$ we get

$E\\{R(n,1,s)\\}\leq\frac{24^{s/3}K}{s!}\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\bigg{(}\frac{n}{\prod_{j=1}^{s}a_{j}}\bigg{)}^{2}<\frac{C^{s-1}24^{s/3}K}{s!},$

where $R(n,1,s)$ is defined as in (11). From Corollary S.1 we have

$C(n,1,s+1)\leq\frac{G\Gamma(2+\beta)2^{s}s}{\epsilon}E(\alpha^{s})\hbox{log}\\{n/(1+\epsilon)\\}^{-1},\quad
n\geq 4\,.$

Thus, combining the inequalities above with (11) and assumption $A3$ we have

$\displaystyle E\biggl{\\{}\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})$
$\displaystyle\sum_{s=1}^{n-1}\frac{\text{pr}(K_{n}=s+1|X_{1:n})}{\text{pr}(K_{n}=1|X_{1:n})}\biggr{\\}}=\sum_{s=1}^{n-1}C(n,1,s+1)E\\{\mathbbm{1}_{\Omega_{n}}(X_{1:\infty})R(n,1,s+1)\\}$
$\displaystyle\leq\frac{24^{1/3}DGK\Gamma(2+\beta)}{\epsilon\hbox{log}\\{n/(1+\epsilon)\\}}\underbrace{\sum_{s=1}^{n-1}\frac{s(2C24^{1/3})^{s}\rho^{-s}\Gamma(\nu+s+1)}{(s+1)!}}_{<\infty}\to
0\qquad\hbox{as }n\to\infty\,,$

where finiteness follows from $\rho\geq 38>24^{1/3}\times 2C$. This implies
that

$\sum_{s=1}^{n-1}\frac{\text{pr}(K_{n}=s+1|X_{1:n})}{\text{pr}(K_{n}=1|X_{1:n})}\rightarrow
0$

in $L^{1}$ and thus in $P^{(\infty)}$-probability as $n\to\infty$. Lemma S.18
with
$Y_{n}=\sum_{s=1}^{n-1}\frac{\text{pr}(K_{n}=s+1|X_{1:n})}{\text{pr}(K_{n}=1|X_{1:n})}$
concludes the proof. $\Box$

##  S.8 Proof of Theorem 3

We first need the following result.

######  Lemma S.19.

Let $k$ and $q_{0}$ be as in (9) and $x_{1}=\cdots=x_{n}=\theta^{\ast}$ for
some $\theta^{\ast}\in\mathbb{R}$. Then

$\displaystyle\frac{\prod_{j=1}^{s}m(x_{A_{j}})}{m(x_{1:n})}$
$\displaystyle=\left\\{\frac{n+1}{\prod_{j=1}^{s}(a_{j}+1)}\right\\}^{1/2}\exp\bigg{\\{}\frac{{\theta^{\ast}}^{2}}{2}\bigg{(}-\frac{n^{2}}{n+1}+\sum_{j=1}^{s}\frac{a_{j}^{2}}{a_{j}+1}\bigg{)}\bigg{\\}}<\left(\frac{n}{\prod_{j=1}^{s}a_{j}}\right)^{1/2}\,,$

for every $s=1,\dots,n$ and every partition
$A=\\{A_{1},\ldots,A_{s}\\}\in\tau_{s}(n)$.

###### Proof.

Since the marginal likelihood can be rewritten as

$m(x_{A_{j}})=(a_{j}+1)^{-1/2}q_{0}(\theta^{\ast})^{a_{j}}\exp\bigg{\\{}\frac{{\theta^{\ast}}^{2}}{2}\frac{a_{j}^{2}}{a_{j}+1}\bigg{\\}},$

the first equality is obtained. The inequality follows from

$\displaystyle-\frac{n^{2}}{n+1}+\sum_{j=1}^{s}\frac{a_{j}^{2}}{a_{j}+1}$
$\displaystyle=n-\frac{n^{2}}{n+1}+\sum_{j=1}^{s}\bigg{(}\frac{a_{j}^{2}}{a_{j}+1}-a_{j}\bigg{)}=\frac{n}{n+1}-\sum_{j=1}^{s}\frac{a_{j}}{a_{j}+1}=$
$\displaystyle=\sum_{j=1}^{s}a_{j}\bigg{(}\frac{1}{n+1}-\frac{1}{a_{j}+1}\bigg{)}\leq
0$

and

$\frac{n+1}{\prod_{j=1}^{s}(a_{j}+1)}\leq\frac{n}{\prod_{j=1}^{s}a_{j}},$

which easily follows from $a_{j}\leq n$, for every $j=1,\dots,s$. $\Box$

###### Proof of Theorem 3.

First, we study $R(n,1,s)$ as defined in (11). Since all the observations are
almost surely equal, we have

$R(n,1,s)=\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\frac{n}{s!\prod_{j=1}^{s}a_{j}}\frac{\prod_{j=1}^{s}m(X_{A^{\bm{a}}_{j}})}{m(X_{1:n})}\,,$

where $A^{\bm{a}}$ is an arbitrary partition in $\tau_{s}(n)$ such that
$|A_{j}^{\bm{a}}|=a_{j}$ for $j=1,\dots,s$. By application of Lemma S.19 and
Lemma S.10 with $p=3/2$, it turns out that the constant
$C=2^{\frac{3}{2}}\zeta\left(\frac{3}{2}\right)<8$ is such that

$R(n,1,s)<\frac{1}{s!}\sum_{\bm{a}\in\mathcal{F}_{s}(n)}\left(\frac{n}{\prod_{j=1}^{s}a_{j}}\right)^{3/2}<\frac{C^{s-1}}{s!}.$

From Corollary S.1 we have

$C(n,1,s+1)\leq\frac{G\Gamma(2+\beta)2^{s}s}{\epsilon}E(\alpha^{s})\hbox{log}\\{n/(1+\epsilon)\\}^{-1},\quad
n\geq 4\,.$ (S.20)

Thus, combining the inequalities above with (11) and assumption $A3$ we have

$\displaystyle\sum_{s=1}^{n-1}\frac{\text{pr}(K_{n}=s+1|X_{1:n})}{\text{pr}(K_{n}=1|X_{1:n})}$
$\displaystyle=\sum_{s=1}^{n-1}C(n,1,s+1)R(n,1,s+1)$ (S.21)
$\displaystyle\leq\frac{DG\Gamma(2+\beta)}{\epsilon\hbox{log}\\{n/(1+\epsilon)\\}}\underbrace{\sum_{s=1}^{n-1}\frac{s(2C)^{s}\rho^{-s}\Gamma(\nu+s+1)}{(s+1)!}}_{<\infty}\to
0\qquad\hbox{as }n\to\infty\,,$

where the finiteness follows from $\rho>16>2C$. Then we conclude applying a
variation of Lemma 2 with equalities and limits in probability replaced by
almost sure equalities and limits (the proof of Lemma 2 extends trivially to
that case). $\Box$

##  S.9 Proof of Proposition 2

###### Proof.

Under (1), for every $\epsilon>0$ we have

$\displaystyle\text{pr}(\alpha<\epsilon\mid X_{1:n})$
$\displaystyle=\sum_{s=1}^{n}\text{pr}(\alpha<\epsilon\mid K_{n}=s)\,\
\text{pr}(K_{n}=s\mid X_{1:n})=$
$\displaystyle\geq\text{pr}(\alpha<\epsilon\mid K_{n}=t)\,\
\text{pr}(K_{n}=t\mid X_{1:n}).$

By assumption, $\text{pr}(K_{n}=t\mid X_{1:n})\to 1$ in
$P^{(\infty)}$-probability as $n\to\infty$. Moreover, by Proposition 3 with
$s=1$ we get

$E(\alpha\mid K_{n}=t)=C(n,t,t+1)\rightarrow 0,$

as $n\to\infty$. It follows $\text{pr}(\alpha<\epsilon\mid K_{n}=t)\to 1$ in
$P^{(\infty)}$-probability as $n\to\infty$, as desired. $\Box$

## References

Cai, D., Campbell, T., and Broderick, T. (2021). Finite mixture models do not
reliably learn the number of components. _38th International Conference on
Machine Learning_ 139, 1158–1169.

Ghosal, S. and Van Der Vaart, A. W. (2017). _Fundamentals of Nonparametric
Bayesian Inference_. Cambridge University Press.