# Sufficientness postulates for measure-valued Pólya urn sequences

Hristo Sariev<EMAIL_ADDRESS><EMAIL_ADDRESS>Institute of
Mathematics and Informatics, Bulgarian Academy of Sciences, 8 Acad. Georgi
Bonchev Str., Sofia 1113, Bulgaria  Faculty of Mathematics and Informatics,
Sofia University ”St. Kliment Ohridski”, 5 James Bourchier Blvd, Sofia 1164,
Bulgaria  Mladen Savov<EMAIL_ADDRESS><EMAIL_ADDRESS>Faculty of Mathematics and Informatics, Sofia University ”St. Kliment
Ohridski”, 5 James Bourchier Blvd, Sofia 1164, Bulgaria  Institute of
Mathematics and Informatics, Bulgarian Academy of Sciences, 8 Acad. Georgi
Bonchev Str., Sofia 1113, Bulgaria

###### Abstract

In a recent paper, the authors studied the distribution properties of a class
of exchangeable processes, called measure-valued Pólya urn sequences, which
arise as the observation process in a generalized urn sampling scheme. Here we
provide three results in the form of “sufficientness” postulates that
characterize their predictive distributions. In particular, we show that
exchangeable measure-valued Pólya urn sequences are the unique exchangeable
models for which the predictive distributions are a mixture of the marginal
distribution and an average of some probability kernels evaluated at past
observation. When the latter coincides with the empirical measure, we recover
a well-known result for the exchangeable model with a Dirichlet process prior.
The other two sufficientness postulates consider the case when the state space
is finite.

Keywords: Bayesian nonparametrics, Exchangeability, Pólya sequences, Urn
models, Predictive distributions, Sufficientness postulate

MSC2020 Classification: 60G09, 60G25, 62G99, 62B99

##  1 Introduction

The exchangeable model with a Dirichlet process prior is a cornerstone of
Bayesian nonparametric analysis and has inspired much of the subsequent work
in this area (for an overview, see [12]). One remarkable feature of the
Dirichlet process, due to [15] and later [13], is that it is the unique prior
for which the predictive distributions of the underlying exchangeable process
are a mixture of the marginal distribution and the empirical measure. More
formally, let $(X_{n})_{n\geq 1}$ be an exchangeable sequence of random
variables with marginal distribution $\nu$ on a standard space
$(\mathbb{X},\mathcal{X})$. By de Finetti representation theorem for
exchangeable sequences, see, e.g., [1, Section 3], there exists a random
probability measure $\tilde{P}$ on $\mathbb{X}$ such that, given $\tilde{P}$,
the random variables $X_{1},X_{2},\ldots$ are conditionally i.i.d. according
to $\tilde{P}$,

$\displaystyle X_{n}\mid\tilde{P}$ $\displaystyle\overset{i.i.d.}{\sim}$
$\displaystyle\tilde{P}$ $\displaystyle\tilde{P}$ $\displaystyle\sim$
$\displaystyle Q$

and $Q$ is called the prior distribution of the process $(X_{n})_{n\geq 1}$.
Assuming that, for each $n=1,2,\ldots$, there exists a constant
$a_{n}\in(0,1)$ such that

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=(1-a_{n})\nu(\cdot)+a_{n}\cdot\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}(\cdot)\qquad\mbox{a.s.},$
(1)

then Theorem 1 in [13] implies that $(i)$ $a_{n}=n\bigr{/}(n+\theta)$, where
$\theta:=a_{1}^{-1}-1$; and $(ii)$ $\tilde{P}\sim\mbox{DP}(\theta,\nu)$ is a
Dirichlet process with parameters $(\theta,\nu)$.

Predictive characterizations of the type (1) are usually referred to as
“sufficientness” postulates and date back to the writings of Cambridge
philosopher W. E. Johnson [11] (for more historical details, see [18]). Unlike
the usual notions of sufficiency, see, e.g., [7, Section 5], sufficientness
postulates provide conditions on the functional form of the predictive
distributions arising from philosophical considerations on the inductive
process of learning. Such a predictive approach to modelling, based solely on
the assessment of observable facts, is deeply rooted in the philosophical
foundations of Bayesian analysis [6]. As an example, for the case when
$\mathbb{X}=\\{x_{1},\ldots,x_{k}\\}$, Johnson’s sufficientness postulate,
which characterizes the $k$-dimensional Dirichlet prior distribution, suggests
that, for each $j=1,\ldots,k$ and $n=1,2,\ldots$,

$\mathbb{P}(X_{n+1}=x_{j}|X_{1},\ldots,X_{n})=f_{n,j}(N_{n,j})\qquad\mbox{a.s.},$
(2)

where the function $f_{n,j}$ depends on the sample $(X_{1},\ldots,X_{n})$ only
by the number of observations
$N_{n,j}:=\sum_{i=1}^{n}\delta_{X_{i}}(\\{x_{j}\\})$ equal to $x_{j}$. A
similar characterization due to [9] is discussed in Section 3. By Theorem 2.1
in [18], the function $f_{n,j}$ is linear in $N_{n,j}$; thus, (1) becomes a
natural extension of (2) to more general spaces $\mathbb{X}$ (for a
philosophical treatment of the issue, refer to [20, p. 352]). Similar
considerations about the relevance of different pieces of sample information
have led to sufficientness postulates for the two-parameter Poisson-Dirichlet
process [20], Gibbs-type priors [2], feature-sampling models [5], neutral to
the right priors [17], and recurrent Markov exchangeable sequences [19].

In this work, we consider an extension of the sufficientness postulate (1),
where the information from each past observation is not necessarily binary.
This is achieved by replacing the Dirac measure $\delta_{x}$ in (1) with a
general probability measure $R_{x}$ on $\mathbb{X}$, so that

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=(1-a_{n})\nu(\cdot)+a_{n}\cdot\frac{1}{n}\sum_{i=1}^{n}R_{X_{i}}(\cdot)\qquad\mbox{a.s.},$
(3)

for some constant $a_{n}\in(0,1)$, where the mapping $x\mapsto R_{x}$ is
assumed to be $\mathcal{X}$-measurable. Our goal is to characterize the class
of exchangeable processes that are governed by (3). Notice that when
$a_{n}=n\bigr{/}(n+\theta)$ for some $\theta>0$, as is the case for (1), then

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=\frac{\theta\nu(\cdot)+\sum_{i=1}^{n}R_{X_{i}}(\cdot)}{\theta+n}\qquad\mbox{a.s.},$
(4)

and, following [16], the process $(X_{n})_{n\geq 1}$ is known as a measure-
valued Pólya urn sequences (MVPS). The predictive structure (4) has a physical
interpretation in terms of a generalized urn sampling scheme, where at stage
$n$ of the experiment, given that a ball of color $X_{n}$ has been observed,
the urn composition, $\theta\nu+\sum_{i=1}^{n-1}R_{X_{i}}$, gets reinforced by
$R_{X_{n}}$, in the sense that, for each $B\in\mathcal{X}$, the quantity
$R_{X_{n}}(B)$ represents the total mass of balls with colors in $B$ that are
added to the urn. A new ball is then sampled from the urn with probability
proportional to the updated urn composition (4), and its color is recorded by
$X_{n+1}$. These measure-valued urn models have been studied by [3, 8, 10, 14]
as extensions of classical $k$-color Pólya urns, and the case where the
observation process $(X_{n})_{n\geq 1}$ in (4) is exchangeable has been
investigated by [4, 16].

From the characterization result about the Dirichlet process, when
$R_{x}=\delta_{x}$, one might expect that the coefficients in (3) for general
$R$ should also be equal to $a_{n}=n\bigr{/}(n+\theta)$, for $n=1,2,\ldots$,
where $\theta:=a_{1}^{-1}-1$. In that case, the only processes having
predictive rules (3) would be exchangeable MVPSs, and the distribution results
in [4] and [16] would carry over. In particular, it would follow from Theorem
9 in [16] that $x\mapsto R_{x}$ is necessarily a regular version of the
conditional distribution for $\nu$ given some sub-$\sigma$-algebra
$\mathcal{G}$ of $\mathcal{X}$,

$R_{x}(\cdot)=\nu(\cdot\mid\mathcal{G})(x)\qquad\mbox{for }\nu\mbox{-a.e. }x.$
(5)

This representation proves extremely useful in [4] and [16] when
characterizing the prior distribution of any exchangeable MVPS, which in the
case of a countable $\mathbb{X}$ or dominated $R$ turns out to be a Dirichlet
process mixture prior (see also Examples 3 and 4). Our main result, Theorem 1,
states that any exchangeable process $(X_{n})_{n\geq 1}$ satisfying the
sufficientness postulate (3) is indeed an exchangeable MVPS. Thus, from (5),
the exchangeable model (3) is essentially “parameterized” by the
sub-$\sigma$-algebra $\mathcal{G}$. Despite the obvious parallels with (1),
the proof of Theorem 1 is more involved and makes extensive use of the
measure-valued nature of the expression in (3).

The rest of the paper is structured as follows. In the next section, we
discuss MVPSs and provide notation that will be used later on. Theorem 1 is
stated in Section 3 along with two other sufficientness postulates that
generalize (2) for the case when $\mathbb{X}$ is finite. The proof of Theorem
1 is postponed to Section 4.

##  2 Preliminaries and notation

Let $(\Omega,\mathcal{H},\mathbb{P})$ be a probability space, $\mathbb{X}$ a
complete separable metric space, and $\mathcal{X}$ the associated Borel
$\sigma$-algebra on $\mathbb{X}$. Standard results imply that $\mathcal{X}$ is
countably generated.

Given two arbitrary measures $\mu,\pi$ on $\mathbb{X}$, we say that $\mu$ is
absolutely continuous w.r.t. $\pi$, denoted $\mu\ll\pi$, if $\mu(A)=0$
whenever $\pi(A)=0$ for any $A\in\mathcal{X}$, and we say that $\mu$ and $\pi$
are mutually singular, denoted $\mu\perp\pi$, if there exists
$S\in\mathcal{X}$ such that $\mu(S)=0=\pi(S^{c})$. A transition kernel on
$\mathbb{X}$ is a function
$R:\mathbb{X}\times\mathcal{X}\rightarrow\mathbb{R}_{+}$ such that $(i)$
$x\mapsto R_{x}(B)$ is $\mathcal{X}$-measurable for every $B\in\mathbb{X}$,
and $(ii)$ $R_{x}$ is a measure on $\mathbb{X}$; if, in addition,
$R_{x}(\mathbb{X})=1$ for each $x\in\mathbb{X}$, then $R$ is said to be a
probability kernel.

Following [16], we call any sequence $(X_{n})_{n\geq 1}$ of
$\mathbb{X}$-valued random variables on $(\Omega,\mathcal{H},\mathbb{P})$ a
measure-valued Pólya urn sequence with parameters $\theta,\nu$ and $R$,
denoted MVPS$(\theta,\nu,R)$, if $\mathbb{P}(X_{1}\in\cdot\,)=\nu(\cdot)$ and,
for each $n=1,2,\ldots$,

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=\frac{\theta\nu(\cdot)+\sum_{i=1}^{n}R_{X_{i}}(\cdot)}{\theta+\sum_{i=1}^{n}R_{X_{i}}(\mathbb{X})}\qquad\mbox{a.s.},$

where $R$ is a finite transition kernel on $\mathbb{X}$, called the
reinforcement measure of the process, $\nu$ is a probability measure on
$\mathbb{X}$, known as the base measure, and $\theta>0$ is a positive
constant. If an MVPS is i.i.d.$(\nu)$, then by Remark 5 in [16] it is also an
MVPS$(\theta,\nu,\nu)$ for any constant $\theta>0$. When $R_{x}(\mathbb{X})=1$
for $\nu$-a.e. $x$, the corresponding MVPS is said to be balanced. It follows
from Corollary 6 in [16] that any exchangeable MVPS$(\theta,\nu,R)$ is also an
exchangeable MVPS$(\tilde{\theta},\nu,\tilde{R})$ for some probability kernel
$\tilde{R}$ and constant $\tilde{\theta}$, so in the sequel the distinction
becomes vacuous as all processes are assumed exchangeable. As a consequence,
any exchangeable MVPS satisfies the sufficientness postulate (3) with
$\tilde{R}$ and coefficients

$a_{n}=\frac{n}{n+\tilde{\theta}},\qquad\mbox{for }n=1,2,\ldots$ (6)

##  3 Results

Theorem 1, together with the discussion preceding (6), states that an
equivalence relation exists between the class of exchangeable MVPSs and
exchangeable processes satisfying the sufficientness postulate (3).

######  Theorem 1.

Let $R$ be a probability kernel on $\mathbb{X}$, and $(X_{n})_{n\geq 1}$ an
exchangeable sequence of $\mathbb{X}$-valued random variables with marginal
distribution $\nu$. If for each $n=1,2,\ldots$ there exists a constant
$a_{n}\in(0,1)$ such that

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=(1-a_{n})\nu(\cdot)+a_{n}\cdot\frac{1}{n}\sum_{i=1}^{n}R_{X_{i}}(\cdot)\qquad\mbox{a.s.},$
(7)

then $a_{n}=n\bigr{/}(a_{1}^{-1}-1+n)$, for $n=1,2,\ldots$, and
$(X_{n})_{n\geq 1}$ is an MVPS with parameters $(a_{1}^{-1}-1,\nu,R)$.

######  Remark 2.

Given that the exchangeable process in Theorem 1 is an MVPS, Theorem 9 in [16]
provides additional guidance on the possible exchangeable models (7). In
particular, following Theorem 9 in [16], all admissible reinforcement measures
have the form

$R_{x}(\cdot)=\nu(\cdot\mid\mathcal{G})(x)\qquad\mbox{for }\nu\mbox{-a.e. }x,$
(8)

where $\mathcal{G}$ is some sub-$\sigma$-algebra of $\mathcal{X}$ on
$\mathbb{X}$. Therefore, within a Bayesian nonparametric framework, when
making the initial assessment that the exchangeable model has the predictive
structure (7), instead of choosing a probability kernel $R$, one actually has
to decide on a predefined body of knowledge in the form of the
$\sigma$-algebra $\mathcal{G}$.

On the other hand, if in Theorem 1 we assume from the outset that the
reinforcement measure $R$ has the form (8), then it can be shown, arguing as
in Theorem 8 in [4], that $(R_{X_{n}})_{n\geq 1}$ is an exchangeable process
with predictive distributions

$\mathbb{P}(R_{X_{n+1}}\in\cdot\mid
R_{X_{1}},\ldots,R_{X_{n}})=(1-a_{n})(\nu\circ
R^{-1})(\cdot)+a_{n}\cdot\frac{1}{n}\sum_{i=1}^{n}\delta_{R_{X_{i}}}(\cdot)\qquad\mbox{a.s.},$

where $\nu\circ R^{-1}$ is the image measure of $\nu$ under $x\mapsto R_{x}$.
In that case, Theorem 1 in [13] implies that $a_{n}=n\bigr{/}(n+\theta)$ with
$\theta:=a_{1}^{-1}-1$, for $n=1,2,\ldots$, and hence

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=\frac{\theta\nu(\cdot)+\sum_{i=1}^{n}R_{X_{i}}(\cdot)}{\theta+n}\qquad\mbox{a.s.}$

######  Example 3 (Mixture model).

Let $D_{1},D_{2},\ldots\in\mathcal{X}$ form a countable partition of
$\mathbb{X}$, $P_{1},P_{2},\ldots$ be probability measures on $\mathbb{X}$
such that $P_{k}(D_{k}^{c})=0$ for $k\geq 1$, and $(X_{n})_{n\geq 1}$ be as in
Theorem 1. Suppose that $\nu(D_{k})>0$ and

$R_{x}(\cdot)=P_{(x)}(\cdot),$

where $P_{(x)}\equiv P_{k}$ if and only if $x\in D_{k}$, for every
$x\in\mathbb{X}$ and $k\geq 1$. In other words, we assume that the
reinforcement measure $R_{x}$ depends on $x$ only through the particular
category $D_{k}$ to which $x$ belongs, and it reinforces only colors of that
category. By Theorem 1, letting $\theta:=a^{-1}_{1}-1$,

$\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n})=\frac{\theta}{\theta+n}\nu(\cdot)+\frac{1}{\theta+n}\sum_{i=1}^{n}P_{(X_{i})}(\cdot)\qquad\mbox{a.s.}$

Since $(X_{n})_{n\geq 1}$ is an MVPS, then Theorem 15 in [16] implies the
existence of sets $C,S\in\mathcal{X}$ such that $\nu(C)=1$,

$P_{(x)}\perp\nu\quad\mbox{and}\quad P_{(x)}(S^{c})=0,\qquad\mbox{for every
}x\in C\cap S,$

and

$P_{(x)}\ll\nu\quad\mbox{and}\quad P_{(x)}(S)=0,\qquad\mbox{for every }x\in
C\cap S^{c}.$

As $P_{(x)}\equiv P_{k}$ for each $x\in D_{k}$, there is a subcollection
$\\{D_{j_{1}},D_{j_{2}},\ldots\\}$ such that $C\cap
S^{c}\subseteq\bigcup_{i\geq 1}D_{j_{i}}$ and $C\cap
S\subseteq\bigl{(}\bigcup_{i\geq 1}D_{j_{i}}\bigr{)}^{c}$; thus,
$P_{(x)}\ll\nu$ for all $x\in\bigcup_{i\geq 1}D_{j_{i}}$. Moreover,

$\mathbb{P}(X_{n+1}\in\cup_{i\geq
1}D_{j_{i}}|X_{1},\ldots,X_{n}\bigr{)}\geq\frac{\theta}{n+\theta}\nu(\cup_{i\geq
1}D_{j_{i}})\qquad\mbox{a.s.},$

which implies that $\sum_{n=1}^{\infty}\mathbb{P}(X_{n+1}\in\cup_{i\geq
1}D_{j_{i}}|X_{1},\ldots,X_{n})=\infty$ a.s., so from the conditional Borel-
Cantelli lemma, $\mathbb{P}(X_{n}\in\cup_{i\geq 1}D_{j_{i}}\mbox{ i.o.})=1$.
As a consequence, working with the sequence $(X_{n})_{n\geq 1}$ conditional on
being in $\bigcup_{i\geq 1}D_{j_{i}}$, it can be shown from Theorem 11 in [16]
that, for every $i\geq 1$,

$P_{j_{i}}(\cdot)=\nu(\cdot\mid D_{j_{i}}).$

If, in addition, $\nu(S)=1$ or, equivalently, $P_{k}\ll\nu$ for all $k\geq 1$,
then

$P_{k}(\cdot)=\nu(\cdot\mid D_{k}),$

in which case

$R_{x}(\cdot)=\sum_{k\geq 1}\nu(\cdot\mid
D_{k})\cdot\mathbbm{1}_{D_{k}}(x)\equiv\nu(\cdot\mid\sigma(D_{1},D_{2},\ldots))(x).$

Following the discussion after Theorem 14 in [16], such an exchangeable MVPS
has a Dirichlet process mixture prior,

$\displaystyle X_{n}\mid\tilde{P}$ $\displaystyle\quad\overset{i.i.d.}{\sim}$
$\displaystyle\int_{\mathbb{X}}P_{(x)}(\cdot)\tilde{P}(dx)=\sum_{k\geq
1}\tilde{P}(D_{k})P_{k}(\cdot)$ (9) $\displaystyle\tilde{P}$
$\displaystyle\quad\;\,\sim$ $\displaystyle\mbox{DP}(\theta,\nu)$

######  Example 4.

($k$-color urn model) Suppose that $\mathbb{X}=\\{x_{1},\ldots,x_{k}\\}$. If
$(X_{n})_{n\geq 1}$ is an exchangeable sequence of $\mathbb{X}$-valued random
variables governed by (7) for some probability measure $\nu$ and probability
kernel $R$, then, following Remark 2, there exists a sub-$\sigma$-algebra
$\mathcal{G}$ of $\mathcal{X}$ such that $R_{x}=\nu(\cdot\mid\mathcal{G})(x)$
for $\nu$-a.e. $x$. Since $|\mathbb{X}|=k$, then in fact
$\mathcal{G}=\sigma(D_{1},\ldots,D_{m})$, where $D_{1},\ldots,D_{m}$ forms a
finite partition of $\mathbb{X}$ for some $1\leq m\leq k$. As a consequence,

$R_{x}(\cdot)=\sum_{l=1}^{m}\nu(\cdot\mid
D_{l})\cdot\mathbbm{1}_{D_{l}}(x)\qquad\mbox{for }\nu\mbox{-a.e. }x,$ (10)

so $(X_{n})_{n\geq 1}$ is distributed as in (9), and the random parameter
$\tilde{P}$ is $m$-dimensional. Taking $\nu$ and $\theta=a^{-1}_{1}-1$ as
given, from (10), the number of exchangeable models on a finite state space
with predictive rules (7), and thus the total number of $k$-color exchangeable
MVPS, is equal to the number of possible partitions of $\mathbb{X}$, also
known as Bell’s number, which is given by the formula

$B_{k}=\frac{1}{k!}\sum_{j=0}^{k}\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^{k},$

with $B_{2}=2$, $B_{3}=5$, $B_{4}=15$, etc.

For each $j=1,\ldots,k$, let us denote by $m(j)$ the index
$l\in\\{1,\ldots,m\\}$ such that $x_{j}\in D_{l}$ and let us define, for every
$l=1,\ldots,m$ and $n=1,2,\ldots$, the number of observations in a sample
$(X_{1},\ldots,X_{n})$ of size $n$ that belong to $D_{l}$ by

$N_{n,l}:=\sum_{i=1}^{n}\mathbbm{1}_{D_{l}}(X_{i}),$

with $N_{0,l}:=0$. The representation (10) implies that, for each
$j=1,\ldots,k$, on a set of probability one,

$\mathbb{P}(X_{n+1}=x_{j}|X_{1},\ldots,X_{n})=\frac{\theta\nu(\\{x_{j}\\})+\sum_{i=1}^{n}\nu(\\{x_{j}\\}|D_{m(j)})\cdot\mathbbm{1}_{D_{m(j)}}(X_{i})}{\theta+n}=\frac{\theta\nu(\\{x_{j}\\})+N_{n,m(j)}\frac{\nu(\\{x_{j}\\})}{\nu(D_{m(j)})}}{\theta+n},$

that is, the predictive distribution of $X_{n+1}$ depends on the sample
information only through the total number of counts in each element of the
partition, $(N_{n,1},\ldots,N_{n,m})$. This fact motivates the next
proposition, which is a generalization of Johnson’s sufficientness postulate
(2).

For ease of notation, we will denote by

$\mathbb{P}_{0}(\cdot)=\mathbb{P}(X_{1}\in\cdot\;)\qquad\mbox{and}\qquad\mathbb{P}_{n}(\cdot)=\mathbb{P}(X_{n+1}\in\cdot\mid
X_{1},\ldots,X_{n}),\quad\mbox{for all }n=1,2,\ldots$

In addition, we will work under the assumption that any sequence of
observations has a positive probability of occurring,

$\mathbb{P}(X_{1}=y_{1},\ldots,X_{n}=y_{n})>0\qquad\mbox{for all
}(y_{1},\ldots,y_{n})\in\mathbb{X}^{n}\mbox{ and }n=1,2,\ldots$ (A)

######  Proposition 5.

Suppose that $\mathbb{X}=\\{x_{1},\ldots,x_{k}\\}$. Let
$\\{D_{1},\ldots,D_{m}\\}$ be a partition of $\mathbb{X}$ with $3\leq m\leq
k$, and $(X_{n})_{n\geq 1}$ an exchangeable sequence of $\mathbb{X}$-valued
random variables satisfying (A). Using the notation established in Example 4,
if for each $j=1,\ldots,k$ and $n=0,1,\ldots$ it holds that

$\mathbb{P}_{n}(\\{x_{j}\\})=f_{n,j}(N_{n,m(j)})\qquad\mbox{a.s.},$ (11)

for some functions $f_{n,j}:\\{0,\ldots,n\\}\rightarrow[0,1]$, then there
exist $w_{1},\ldots,w_{k}>0$ such that $(X_{n})_{n\geq 1}$ is an MVPS with
constant $\bar{w}=\sum_{j=1}^{k}w_{j}$, base measure
$\nu(\cdot)=\sum_{j=1}^{k}w_{j}\delta_{x_{j}}(\cdot)\bigr{/}\bar{w}$ and
reinforcement measure

$R_{x}(\cdot)=\nu(\cdot\mid\sigma(D_{1},\ldots,D_{m}))(x).$

###### Proof.

Let us define, for $n\geq 0$, $l=1,\ldots,m$ and $n_{l}=0,1,\ldots,n$,

$g_{n,l}(n_{l}):=\sum_{j:x_{j}\in D_{l}}f_{n,j}(n_{l}).$

It follows from (A) that $f_{n,j}(n_{l})>0$, and hence $g_{n,l}(n_{l})>0$.
Moreover,

$\mathbb{P}_{n}(D_{l})=g_{n,l}(N_{n,l})\qquad\mbox{a.s.}$ (12)

Recall that $m(j)$ denotes, for each $j=1,\ldots,k$, the index
$l\in\\{1,\ldots,m\\}$ such that $x_{j}\in D_{l}$. Define $Y_{n}:=m(X_{n})$,
for $n=1,2,\ldots$. Then the process $(Y_{n})_{n\geq 1}$ is exchangeable and,
by (12), for each $l=1,\ldots,m$ and $n=1,2,\ldots$,

$\mathbb{P}(Y_{n+1}=l|Y_{1},\ldots,Y_{n})=g_{n,l}(N_{n,l})\qquad\mbox{a.s.},$

which coincides with Johnson’s sufficientness postulate (2) for the case of
$m$ states. It follows from Theorem 2.1 and Corollary 2.1 in [18], applied to
$(Y_{n})_{n\geq 1}$, that there exist $\bar{w}_{1},\ldots,\bar{w}_{m}>0$ such
that

$g_{n,l}(n_{l})=\frac{\bar{w}_{l}+n_{l}}{\bar{w}+n},$ (13)

where $\bar{w}:=\sum_{l=1}^{m}\bar{w}_{l}$; thus, in particular, for each
$l=1,\ldots,m$,

$\mathbb{P}_{0}(D_{l})=g_{0,l}(0)=\frac{\bar{w}_{l}}{\bar{w}}.$ (14)

Let $j\in\\{1,\ldots,k\\}$ be such that $D_{m(j)}=\\{x_{j}\\}$. Then
$f_{n,j}(n_{m(j)})=g_{n,m(j)}(n_{m(j)})$, so it follows from (13) and (14)
that, for each $n=0,1,\ldots$, on a set of probability one,

$\mathbb{P}_{n}(\\{x_{j}\\})=g_{n,m(j)}(N_{n,m(j)})=\frac{\bar{w}\cdot\mathbb{P}_{0}(\\{x_{j}\\})+\sum_{i=1}^{n}\mathbbm{1}_{D_{m(j)}}(X_{i})}{\bar{w}+n}.$
(15)

Let $i,j\in\\{1,\ldots,k\\}$ be such that $i\neq j$ and $m(i)=m(j)$. Fix
$n\geq 0$111For $n=0$, the expression $\mathbb{P}(\cdot\mid
X_{1},\ldots,X_{n})$ is meant as an unconditional distribution.. It follows
for every $h=1,2,\ldots$ that

$\displaystyle\mathbb{P}(X_{n+1}=x_{j},X_{n+2}\in
D_{m(j)}^{c},\ldots,X_{n+h+1}$ $\displaystyle\in
D_{m(j)}^{c}|X_{1},\ldots,X_{n})$
$\displaystyle=f_{n,j}(N_{n,m(j)})\prod_{s=1}^{h}\bigl{(}1-g_{n+s,m(j)}(N_{n,m(j)}+1)\bigr{)},$

and

$\displaystyle\mathbb{P}(X_{n+1}\in D_{m(j)}^{c},\ldots,X_{n+h}\in
D_{m(j)}^{c},X_{n+h+1}$ $\displaystyle=x_{j}|X_{1},\ldots,X_{n})$
$\displaystyle=f_{n+h,j}(N_{n,m(j)})\prod_{s=0}^{h-1}\bigl{(}1-g_{n+s,m(j)}(N_{n,m(j)})\bigr{)}.$

By exchangeability, the two expressions are equal on a set of probability one,
so we obtain

$\frac{f_{n,j}(N_{n,m(j)})}{f_{n+h,j}(N_{n,m(j)})}=\frac{\prod_{s=0}^{h-1}\bigl{(}1-g_{n+s,m(j)}(N_{n,m(j)})\bigr{)}}{\prod_{s=1}^{h}\bigl{(}1-g_{n+s,m(j)}(N_{n,m(j)}+1)\bigr{)}}.$

Since the right-hand side of the equation depends on $j$ only through $m(j)$,
then the ratio $f_{n,i}\bigr{/}f_{n+h,i}$ for $i$ is equal to the same
quantity; therefore, with $n_{m(j)}\equiv n_{m(i)}$ fixed, for any
$h=1,2,\ldots$,

$\frac{f_{n,i}(n_{m(i)})}{f_{n,j}(n_{m(j)})}=\frac{f_{n+h,i}(n_{m(i)})}{f_{n+h,j}(n_{m(j)})}.$
(16)

On the other hand, for every $h=1,\ldots,n$,

$\displaystyle\mathbb{P}(X_{1}\in D_{m(j)}^{c},\ldots,X_{n}$ $\displaystyle\in
D_{m(j)}^{c},X_{n+1}=x_{j},X_{n+2}\in D_{m(j)},\ldots,X_{2n+1}\in D_{m(j)})$
$\displaystyle=f_{n,j}(0)\prod_{s=0}^{n-1}\bigl{(}1-g_{n-s,m(j)}(0)\bigr{)}\prod_{s=1}^{n}g_{n+s,m(j)}(s),$

and, using the permutation $\sigma$ of $\\{1,\ldots,2n+1\\}$, which swaps
$\\{1,\ldots,h\\}$ and $\\{n+2,\ldots,n+h+1\\}$,

$\displaystyle\mathbb{P}(X_{\sigma(1)}$ $\displaystyle\in
D_{m(j)}^{c},\ldots,X_{\sigma(n)}\in
D_{m(j)}^{c},X_{\sigma(n+1)}=x_{j},X_{\sigma(n+2)}\in
D_{m(j)},\ldots,X_{\sigma(2n+1)}\in D_{m(j)})$
$\displaystyle=f_{n,j}(h)\prod_{s=0}^{h-1}g_{s,m(j)}(s)\prod_{s=0}^{n-h-1}\bigl{(}1-g_{h+s,m(j)}(h)\bigr{)}\prod_{s=1}^{h}\bigl{(}1-g_{n+s,m(j)}(h)\bigr{)}\prod_{s=1}^{n-h}g_{n+h+s,m(j)}(h+s-1).$

Since
$(X_{1},\ldots,X_{2n+1})\overset{d}{=}(X_{\sigma(1)},\ldots,X_{\sigma(2n+1)})$
by exchangeability, arguing as in (16), we obtain that, with $n$ fixed, for
any $h=1,\ldots,n$,

$\frac{f_{n,i}(0)}{f_{n,j}(0)}=\frac{f_{n,i}(h)}{f_{n,j}(h)}.$ (17)

It follows from (16) and (17) that, for any such pair $i,j$, the ratio below
is independent of $n$ and $n_{m(j)}\equiv n_{m(i)}$,

$\frac{f_{n,i}(n_{m(i)})}{f_{n,j}(n_{m(j)})}=:d_{i,j}.$

Summing over $i$ and letting $w_{j}:=\bar{w}_{m(j)}\bigr{/}\sum_{i:x_{i}\in
D_{m(j)}}d_{i,j}$, gives

$f_{n,j}(n_{m(j)})=\frac{1}{\sum_{i:x_{i}\in
D_{m(j)}}d_{i,j}}g_{n,m(j)}(n_{m(j)})=\frac{w_{j}}{\bar{w}_{m(j)}}g_{n,m(j)}(n_{m(j)});$

thus, in particular, we get

$\mathbb{P}_{0}(\\{x_{j}\\})=f_{0,j}(0)=\frac{w_{j}}{\bar{w}_{m(j)}}g_{0,m(j)}(0)=\frac{w_{j}}{\bar{w}}.$

In that case,
$\mathbb{P}_{0}(\\{x_{j}\\}|D_{m(j)})=w_{j}\bigr{/}\bar{w}_{m(j)}$; therefore,
on a set of probability one,

$\displaystyle\begin{aligned}
\mathbb{P}_{n}(\\{x_{j}\\})&=f_{n,j}(N_{n,m(j)})\\\
&=\frac{w_{j}}{\bar{w}_{m(j)}}\frac{\bar{w}_{m(j)}+N_{n,m(j)}}{\bar{w}+n}=\frac{\bar{w}\cdot\mathbb{P}_{0}(\\{x_{j}\\})+\mathbb{P}_{0}(\\{x_{j}\\}|D_{m(j)})\sum_{i=1}^{n}\mathbbm{1}_{D_{m(j)}}(X_{i})}{\bar{w}+n}.\end{aligned}$
(18)

We can now conclude from (15) and (18) that, for each $n=1,2,\ldots$, on a set
of probability one,

$\displaystyle\mathbb{P}(X_{n+1}\in dy\mid X_{1},\ldots,X_{n})$
$\displaystyle=\frac{\bar{w}\cdot\mathbb{P}_{0}(dy)+\sum_{i=1}^{n}\sum_{l=1}^{m}\mathbb{P}_{0}(dy|D_{l})\cdot\mathbbm{1}_{D_{l}}(X_{i})}{\bar{w}+n}$
$\displaystyle=\frac{\bar{w}\cdot\mathbb{P}_{0}(dy)+\sum_{i=1}^{n}\mathbb{P}_{0}(dy\mid\sigma(D_{1},\ldots,D_{m}))(X_{i})}{\bar{w}+n},$

which implies that $(X_{n})_{n\geq 1}$ is an MVPS with parameters
$\bigl{(}\bar{w},\mathbb{P}_{0},\mathbb{P}_{0}(\cdot\mid\sigma(D_{1},\ldots,D_{m}))\bigr{)}$.
∎

Regarding the necessity of the condition $m\geq 3$ in Proposition 5, observe
that when $m=1$, then $D_{1}=\mathbb{X}$ and, for every $j=1,\ldots,k$ and
$n\geq 0$,

$\mathbb{P}_{n}(\\{x_{j}\\})=f_{n,j}(n)\qquad\mbox{a.s.},$

which is independent of $X_{1},\ldots,X_{n}$. From there,

$\mathbb{P}(X_{n+2}=x_{j}|X_{1},\ldots,X_{n})=\mathbb{E}\bigl{[}\mathbb{P}(X_{n+2}=x_{j}|X_{1},\ldots,X_{n+1})\bigr{|}X_{1},\ldots,X_{n}\bigr{]}=f_{n+1,j}(n+1)\qquad\mbox{a.s.},$

and, since
$(X_{1},\ldots,X_{n},X_{n+1})\overset{d}{=}(X_{1},\ldots,X_{n},X_{n+2})$ by
exchangeability,

$f_{n,j}(n)=\mathbb{P}(X_{n+1}=x_{j}|X_{1},\ldots,X_{n})=\mathbb{P}(X_{n+2}=x_{j}|X_{1},\ldots,X_{n})=f_{n+1,j}(n+1)\qquad\mbox{a.s.}$

Moreover,
$\mathbb{P}_{0}(\\{x_{j}\\})=\mathbb{P}(X_{2}=x_{j})=\mathbb{E}\bigl{[}\mathbb{P}(X_{2}=x_{j}|X_{1})\bigr{]}=f_{1,j}(1)$;
therefore,

$\mathbb{P}(X_{n+1}=x_{j}|X_{1},\ldots,X_{n})=\mathbb{P}_{0}(\\{x_{j}\\})\qquad\mbox{a.s.},$

which implies that $(X_{n})_{n\geq 1}$ is i.i.d.$(\mathbb{P}_{0})$.

On the other hand, when $m=2$, the sufficientness postulate (12) at the level
of the partition does not necessarily imply (13), and so $(X_{n})_{n\geq 1}$
need not be an MVPS (see Remark 1 in [18] and references therein). To obtain
(13) when $m=2$, the authors in [18] suggest assuming that the function
$g_{n,l}$ in (12) is linear in $n_{l}$. However, a different approach,
following the work of Hill and coauthors [9], is presented in the next
proposition, which is more in the spirit of Proposition 5 and covers the case
$m=2$. Hill et al.’s [9] original result is itself recovered by taking
$D_{j}=\\{x_{j}\\}$, for $j=1,\ldots,k$.

######  Proposition 6.

Let $w_{1},\ldots,w_{k}>0$, $\\{D_{1},\ldots,D_{m}\\}$ be a partition of
$\mathbb{X}=\\{x_{1},\ldots,x_{k}\\}$, and $(X_{n})_{n\geq 1}$ an
exchangeable, but not i.i.d. sequence of $\mathbb{X}$-valued random variables
satisfying (A). Define $\bar{w}:=\sum_{j=1}^{k}w_{j}$ and
$\bar{w}_{l}:=\sum_{i:x_{j}\in D_{l}}w_{j}$, for $l=1,\ldots,m$. Using the
established notation in Example 4, if for each $j=1,\ldots,k$ and
$n=0,1,\ldots$ it holds that

$\mathbb{P}_{n}(\\{x_{j}\\})=f_{j}\biggl{(}\frac{\bar{w}_{m(j)}+N_{n,m(j)}}{\bar{w}+n}\biggr{)}\qquad\mbox{a.s.},$

for some functions $f_{j}:[0,1]\rightarrow[0,1]$, then $(X_{n})_{n\geq 1}$ is
an MVPS with constant $\bar{w}$, base measure
$\nu(\cdot)=\sum_{j=1}^{k}w_{j}\delta_{x_{j}}(\cdot)\bigr{/}\bar{w}$ and
reinforcement measure

$R_{x}(\cdot)=\nu(\cdot\mid\sigma(D_{1},\ldots,D_{m}))(x).$

###### Proof.

Let us define, for $l=1,\ldots,m$ and
$p_{l}\in\bigl{\\{}(\bar{w}_{l}+n_{l})\bigr{/}(\bar{w}+n):n_{l}=0,1,\ldots,n;n=0,1,\ldots\bigr{\\}}$,

$g_{l}(p_{l}):=\sum_{j:x_{j}\in D_{l}}f_{j}(p_{l}).$

Then a straightforward extension of the arguments in [9] to $m$ colors gives
$g_{l}(p_{l})=p_{l}$. The rest of the proof follows the same steps as in the
proof of Proposition 5, starting from (13). ∎

##  4 Proof of Theorem 1

We begin the proof of Theorem 1 by deriving some relations between $\nu$, $R$
and $(a_{n})_{n\geq 1}$ as a consequence of exchangeability.

Let $A,B\in\mathcal{X}$. It follows from (7) and $\mathbb{P}(X_{1}\in
dx)=\nu(dx)$ that

$\displaystyle\mathbb{P}(X_{1}\in A,X_{2}\in B)$
$\displaystyle=\int_{A}\mathbb{P}(X_{2}\in B|X_{1}=x)\mathbb{P}(X_{1}\in dx)$
$\displaystyle=\int_{A}\bigl{\\{}(1-a_{1})\nu(B)+a_{1}R_{x}(B)\bigr{\\}}\nu(dx)=(1-a_{1})\nu(A)\nu(B)+a_{1}\int_{A}R_{x}(B)\nu(dx).$

Since $(X_{1},X_{2})\overset{d}{=}(X_{2},X_{1})$ by exchangeability, then

$\displaystyle(1-a_{1})\nu(A)\nu(B)+a_{1}\int_{A}R_{x}(B)\nu(dx)$
$\displaystyle=\mathbb{P}(X_{1}\in A,X_{2}\in B)$
$\displaystyle=\mathbb{P}(X_{1}\in B,X_{2}\in
A)=(1-a_{1})\nu(A)\nu(B)+a_{1}\int_{B}R_{x}(A)\nu(dx);$

therefore, $\int_{x\in A}\int_{y\in B}R_{x}(dy)\nu(dx)=\int_{x\in B}\int_{y\in
A}R_{x}(dy)\nu(dx)$ or, as measures,

$R_{x}(dy)\nu(dx)=R_{y}(dx)\nu(dy).$ (19)

On the other hand, we get for $\nu$-a.e. $x$ that

$\displaystyle\mathbb{P}(X_{3}\in B|X_{1}=x)$
$\displaystyle=\int_{\mathbb{X}}\mathbb{P}(X_{3}\in
B|X_{1}=x,X_{2}=y)\mathbb{P}(X_{2}\in dy|X_{1}=x)$
$\displaystyle=\int_{\mathbb{X}}\Bigl{\\{}(1-a_{2})\nu(B)+\frac{a_{2}}{2}R_{x}(B)+\frac{a_{2}}{2}R_{y}(B)\Bigr{\\}}\bigl{(}(1-a_{1})\nu(dy)+a_{1}R_{x}(dy)\bigr{)}$
$\displaystyle=(1-a_{2})\nu(B)+\frac{a_{2}}{2}R_{x}(B)+\frac{(1-a_{1})a_{2}}{2}\int_{\mathbb{X}}R_{y}(B)\nu(dy)+\frac{a_{1}a_{2}}{2}\int_{\mathbb{X}}R_{y}(B)R_{x}(dy)$
$\displaystyle\overset{(a)}{=}(1-a_{2})\nu(B)+\frac{a_{2}}{2}R_{x}(B)+\frac{(1-a_{1})a_{2}}{2}\nu(B)+\frac{a_{1}a_{2}}{2}\int_{\mathbb{X}}R_{y}(B)R_{x}(dy),$

for every $B\in\mathcal{X}$, where $(a)$ follows from (19) as
$\int_{\mathbb{X}}R_{y}(B)\nu(dy)=\nu(B)$. Since
$(X_{1},X_{2})\overset{d}{=}(X_{1},X_{3})$ by exchangeability, for $\nu$-a.e.
$x$,

$\displaystyle(1-a_{1})\nu(B)+a_{1}R_{x}(B)$
$\displaystyle=\mathbb{P}(X_{2}\in B|X_{1}=x)$
$\displaystyle=\mathbb{P}(X_{3}\in B|X_{1}=x)$
$\displaystyle=(1-a_{2})\nu(B)+\frac{a_{2}}{2}R_{x}(B)+\frac{(1-a_{1})a_{2}}{2}\nu(B)+\frac{a_{1}a_{2}}{2}\int_{\mathbb{X}}R_{y}(B)R_{x}(dy);$

thus, rearranging the terms and using that $\mathcal{X}$ is countably
generated, we obtain for $\nu$-a.e. $x$ that, as measures,

$\int_{\mathbb{X}}R_{y}(dz)R_{x}(dy)=\Bigl{(}1-\frac{a_{2}-2a_{1}+a_{1}a_{2}}{a_{1}a_{2}}\Bigr{)}R_{x}(dz)+\frac{a_{2}-2a_{1}+a_{1}a_{2}}{a_{1}a_{2}}\nu(dz)=(1-c^{*})R_{x}(dz)+c^{*}\nu(dz),$
(20)

where $c^{*}:=\frac{a_{2}-2a_{1}+a_{1}a_{2}}{a_{1}a_{2}}$.

Take $n\geq 2$. It follows222Strictly speaking, (7) implies that, for
$\mathbb{P}_{X_{1},\ldots,X_{n}}$-a.e. $(x_{1},\ldots,x_{n-1},x)$ in
$\mathbb{X}^{n}$, as measures,  $\mathbb{P}(X_{n+1}\in dy\mid
X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)=(1-a_{n})\nu(dy)+\frac{a_{n}}{n}\sum_{i=1}^{n-1}R_{x_{i}}(dy)+\frac{a_{n}}{n}R_{x}(dy).$
(A) Disintegrating $\mathbb{P}(X_{1}\in dx_{1},\ldots,X_{n}\in dx_{n})$
repeatedly via (7), one obtains (see also (28))  $\mathbb{P}(X_{1}\in
dx_{1},\ldots,X_{n}\in
dx_{n})\geq\prod_{i=1}^{n-1}(1-a_{i})\nu(dx_{1})\cdots\nu(dx_{n});$ thus, (A)
remains true for $(\nu\times\cdots\times\nu)$-a.e. $(x_{1},\ldots,x_{n-1},x)$
in $\mathbb{X}^{n}$.  from (7) that, for $(\nu\times\cdots\times\nu)$-a.e.
$(x_{1},\ldots,x_{n-1},x)$ in $\mathbb{X}^{n}$,

$\mathbb{P}(X_{n+1}\in
B|X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)=(1-a_{n})\nu(B)+\frac{a_{n}}{n}\sum_{i=1}^{n-1}R_{x_{i}}(B)+\frac{a_{n}}{n}R_{x}(B),$

for every $B\in\mathcal{X}$; thus, for $\nu$-a.e. $x$,

$\displaystyle\int_{\mathbb{X}}\cdots$
$\displaystyle\int_{\mathbb{X}}\mathbb{P}(X_{n+1}\in
B|X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)\nu(dx_{n-1})\cdots\nu(dx_{1})$
$\displaystyle=(1-a_{n})\nu(B)+\frac{a_{n}}{n}\sum_{i=1}^{n-1}\nu(B)+\frac{a_{n}}{n}R_{x}(B)=(1-a_{n})\nu(B)+\frac{(n-1)a_{n}}{n}\nu(B)+\frac{a_{n}}{n}R_{x}(B),$
(21)

using that $\int_{\mathbb{X}}R_{x_{i}}(B)\nu(dx_{i})=\nu(B)$, for
$i=1,\ldots,n-1$. On the other hand,

$\displaystyle\mathbb{P}(X_{n+2}$ $\displaystyle\in
B|X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)$
$\displaystyle=\int_{\mathbb{X}}\mathbb{P}(X_{n+2}\in
B|X_{1}=x_{1},\ldots,X_{n}=x,X_{n+1}=y)\mathbb{P}(X_{n+1}\in
dy|X_{1}=x_{1},\ldots,X_{n}=x)$ $\displaystyle\begin{aligned}
=\int_{\mathbb{X}}\Bigl{\\{}(1-a_{n+1})\nu(B)&+\frac{a_{n+1}}{n+1}\sum_{i=1}^{n-1}R_{x_{i}}(B)+\frac{a_{n+1}}{n+1}R_{x}(B)+\\\
&+\frac{a_{n+1}}{n+1}R_{y}(B)\Bigr{\\}}\Bigl{(}(1-a_{n})\nu(dy)+\frac{a_{n}}{n}\sum_{i=1}^{n-1}R_{x_{i}}(dy)+\frac{a_{n}}{n}R_{x}(dy)\Bigr{)}\end{aligned}$
$\displaystyle\begin{aligned}
=(1-a_{n+1})\nu(B)&+\frac{a_{n+1}}{n+1}\sum_{i=1}^{n-1}R_{x_{i}}(B)+\frac{a_{n+1}}{n+1}R_{x}(B)+\frac{(1-a_{n})a_{n+1}}{n+1}\int_{\mathbb{X}}R_{y}(B)\nu(dy)+\\\
&+\frac{a_{n}a_{n+1}}{n(n+1)}\sum_{i=1}^{n-1}\int_{\mathbb{X}}R_{y}(B)R_{x_{i}}(dy)+\frac{a_{n}a_{n+1}}{n(n+1)}\int_{\mathbb{X}}R_{y}(B)R_{x}(dy)\end{aligned}$
$\displaystyle\begin{aligned}
\overset{(a)}{=}(1-a_{n+1})&\nu(B)+\frac{a_{n+1}}{n+1}\sum_{i=1}^{n-1}R_{x_{i}}(B)+\frac{a_{n+1}}{n+1}R_{x}(B)+\frac{(1-a_{n})a_{n+1}}{n+1}\nu(B)+\\\
&+\frac{a_{n}a_{n+1}}{n(n+1)}\sum_{i=1}^{n-1}\int_{\mathbb{X}}R_{y}(B)R_{x_{i}}(dy)+(1-c^{*})\frac{a_{n}a_{n+1}}{n(n+1)}R_{x}(B)+c^{*}\frac{a_{n}a_{n+1}}{n(n+1)}\nu(B),\end{aligned}$
(22)

where $(a)$ follows from (20) and as
$\int_{\mathbb{X}}R_{x_{i}}(B)\nu(dx_{i})=\nu(B)$, for $i=1,\ldots,n-1$.
Notice that by applying (19) twice, we obtain

$\int_{\mathbb{X}}\int_{\mathbb{X}}R_{y}(B)R_{x_{i}}(dy)\nu(dx_{i})=\int_{\mathbb{X}}\int_{\mathbb{X}}R_{y}(B)R_{y}(dx_{i})\nu(dy)=\int_{\mathbb{X}}R_{y}(B)R_{y}(\mathbb{X})\nu(dy)=\int_{\mathbb{X}}R_{y}(B)\nu(dy)=\nu(B),$

for $i=1,\ldots,n-1$. Thus, integrating (22), we get for $\nu$-a.e. $x$ that

$\displaystyle\int_{\mathbb{X}}\cdots\int_{\mathbb{X}}\mathbb{P}($
$\displaystyle X_{n+2}\in
B|X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)\nu(dx_{n-1})\cdots\nu(dx_{1})$
$\displaystyle\begin{aligned}
=(1-a_{n+1})\nu(B)&+\frac{a_{n+1}}{n+1}\sum_{i=1}^{n-1}\nu(B)+\frac{a_{n+1}}{n+1}R_{x}(B)+\frac{(1-a_{n})a_{n+1}}{n+1}\nu(B)+\\\
&+\frac{a_{n}a_{n+1}}{n(n+1)}\sum_{i=1}^{n-1}\nu(B)+(1-c^{*})\frac{a_{n}a_{n+1}}{n(n+1)}R_{x}(B)+c^{*}\frac{a_{n}a_{n+1}}{n(n+1)}\nu(B)\end{aligned}$
$\displaystyle\begin{aligned}
=(1-a_{n+1})\nu(B)&+\frac{(n-1)a_{n+1}}{n+1}\nu(B)+\frac{a_{n+1}}{n+1}R_{x}(B)+\frac{(1-a_{n})a_{n+1}}{n+1}\nu(B)+\\\
&+\frac{(n-1)a_{n}a_{n+1}}{n(n+1)}\nu(B)+(1-c^{*})\frac{a_{n}a_{n+1}}{n(n+1)}R_{x}(B)+c^{*}\frac{a_{n}a_{n+1}}{n(n+1)}\nu(B).\end{aligned}$
(23)

Since $(X_{1},\ldots,X_{n},X_{n+1})\overset{d}{=}(X_{1},\ldots,X_{n},X_{n+2})$
by exchangeability, it follows from (21) and (23) that, for $\nu$-a.e. $x$,

$\displaystyle(1-a_{n})\nu(B)$
$\displaystyle+\frac{(n-1)a_{n}}{n}\nu(B)+\frac{a_{n}}{n}R_{x}(B)$
$\displaystyle=\int_{\mathbb{X}}\cdots\int_{\mathbb{X}}\mathbb{P}(X_{n+1}\in
B|X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)\nu(dx_{n-1})\cdots\nu(dx_{1})$
$\displaystyle=\int_{\mathbb{X}}\cdots\int_{\mathbb{X}}\mathbb{P}(X_{n+2}\in
B|X_{1}=x_{1},\ldots,X_{n-1}=x_{n-1},X_{n}=x)\nu(dx_{n-1})\cdots\nu(dx_{1})$
$\displaystyle\begin{aligned}
=(1-a_{n+1})\nu(B)&+\frac{(n-1)a_{n+1}}{n+1}\nu(B)+\frac{a_{n+1}}{n+1}R_{x}(B)+\frac{(1-a_{n})a_{n+1}}{n+1}\nu(B)+\\\
&+\frac{(n-1)a_{n}a_{n+1}}{n(n+1)}\nu(B)+(1-c^{*})\frac{a_{n}a_{n+1}}{n(n+1)}R_{x}(B)+c^{*}\frac{a_{n}a_{n+1}}{n(n+1)}\nu(B),\end{aligned}$

for every $B\in\mathcal{X}$; therefore, after some simple algebra, we get for
$\nu$-a.e. $x$ that, as measures,

$\bigl{(}na_{n+1}-(n+1)a_{n}+(1-c^{*})a_{n}a_{n+1}\bigr{)}\nu(dy)=\bigl{(}na_{n+1}-(n+1)a_{n}+(1-c^{*})a_{n}a_{n+1}\bigr{)}R_{x}(dy).$
(24)

We proceed by showing that, for different specifications of $R$, equations
(20) and (24) together imply the prescribed form of the coefficients $a_{n}$
and, in particular, that $c^{*}=0$. To that end, let us consider for each
$x\in\mathbb{X}$ the decomposition

$R_{x}=R_{x}^{a}+R_{x}^{\perp},$

where $R_{x}^{a}\ll\nu$ and $R_{x}^{\perp}\perp\nu$, say w.r.t.
$S_{x}\in\mathcal{X}$, so that $R_{x}^{\perp}(S_{x}^{c})=0=\nu(S_{x})$. Let us
define

$D:=\\{x\in\mathbb{X}:R_{x}\neq\nu\\}\qquad\mbox{and}\qquad
F:=\\{x\in\mathbb{X}:R_{x}^{\perp}(S_{x})>0\\}.$

Case 1: $\nu(D)>0$.

By construction, for every $x\in D$, there exists $B_{x}\in\mathcal{X}$ such
that $\nu(B)\neq R_{x}(B)$. It follows from (24) that, for $\nu$-a.e. $x$ in
$D$,

$\bigl{(}na_{n+1}-(n+1)a_{n}+(1-c^{*})a_{n}a_{n+1}\bigr{)}\nu(B_{x})=\bigl{(}na_{n+1}-(n+1)a_{n}+(1-c^{*})a_{n}a_{n+1}\bigr{)}R_{x}(B_{x}),$

which is true if and only if

$na_{n+1}-(n+1)a_{n}+(1-c^{*})a_{n}a_{n+1}=0,$

or, equivalently,

$\frac{a_{n+1}}{n+1}=\frac{a_{n}}{n+(1-c^{*})a_{n}}.$

Using the substitution $b_{n}=n/a_{n}$, we obtain $b_{n+1}=b_{n}+(1-c^{*})$;
thus, $b_{n}=b_{1}+(n-1)(1-c^{*})$ for each $n=1,2,\ldots$, and so

$a_{n}=\frac{n}{(n-1)(1-c^{*})+\frac{1}{a_{1}}}.$ (25)

If $c^{*}=1$, then $a_{n}=na_{1}$, which leads to a contradiction since by
assumption $0<a_{n}<1$ for $n=1,2,\ldots$. On the other hand,

$\lim_{n\rightarrow\infty}a_{n}=\lim_{n\rightarrow\infty}\frac{1}{(1-c^{*})-\frac{1-c^{*}}{n}+\frac{1}{a_{1}n}}=\frac{1}{1-c^{*}};$

therefore, $c^{*}\leq 0$, otherwise $a_{n}\notin(0,1)$ for $n$ large enough,
absurd.

Sub-Case 1a: $\nu(D)>0$ and $\nu(F)>0$.

Let $G\in\mathcal{X}$ be the $\nu$-a.s. set in (20). Define

$G_{0}:=\\{x\in G:R_{x}(G)=1\\}\qquad\mbox{and}\qquad G_{n}:=\\{x\in
G_{n-1}:R_{x}(G_{n-1})=1\\},\quad\mbox{for all }n\geq 1.$

It follows from (19) that

$1=\int_{\mathbb{X}}R_{x}(\mathbb{X})\nu(dx)=\int_{G}R_{x}(\mathbb{X})\nu(dx)=\int_{\mathbb{X}}R_{x}(G)\nu(dx),$

so $\nu(G_{0})=1$. By induction, $\nu(G_{n})=1$ for all $n\geq 1$; thus,
letting $G^{*}:=\bigcap_{n=0}^{\infty}G_{n}$, we get $\nu(G^{*})=1$ and
$R_{x}(G_{n})=1$, for all $x\in G^{*}$ and $n\geq 1$. Moreover,
$G^{*}\subseteq G$ and, as a result, $R_{x}(G^{*})=1$ and

$\int_{\mathbb{X}}R_{y}(dz)R_{x}(dy)=(1-c^{*})R_{x}(dz)+c^{*}\nu(dz),$

for all $x\in G^{*}$.

Recall that $F=\\{x\in\mathbb{X}:R_{x}^{\perp}(S_{x})>0\\}$. Let us define

$\beta:=\sup_{x\in F\cap G^{*}}R_{x}^{\perp}(S_{x}),$

Assuming that $\nu(F)>0$, we have $\beta>0$. Fix $\epsilon\in(0,\beta)$. From
the properties of suprema, there exists $x\in F\cap G^{*}$ such that
$R_{x}^{\perp}(S_{x})\geq\beta-\epsilon$. Moreover, $\nu(S_{x})=0$ implies
that $R_{y}^{a}(S_{x})=0$ for all $y\in\mathbb{X}$, so

$(1-c^{*})R_{x}(S_{x})+c^{*}\nu(S_{x})=(1-c^{*})R_{x}^{\perp}(S_{x})\geq(1-c^{*})(\beta-\epsilon),$

since $c^{*}\leq 0$, and

$\int_{\mathbb{X}}R_{y}(S_{x})R_{x}(dy)=\int_{\mathbb{X}}R_{y}^{\perp}(S_{x})R_{x}(dy)\leq\int_{\mathbb{X}}R_{y}^{\perp}(S_{y})R_{x}(dy)\overset{(a)}{=}\int_{F\cap
G^{*}}R_{y}^{\perp}(S_{y})R_{x}(dy)\leq\beta,$

using in $(a)$ that $R_{y}(S_{y})=0$ on $F^{c}$ by construction and
$R_{x}(G^{*})=1$ from before. Therefore, by (20),

$\beta\geq\int_{\mathbb{X}}R_{y}(S_{x})R_{x}(dy)=(1-c^{*})R_{x}(S_{x})+c^{*}\nu(S_{x})\geq(1-c^{*})(\beta-\epsilon).$

Letting $\epsilon\downarrow 0$, we get
$1-c^{*}\leq\beta\bigr{/}(\beta-\epsilon)\rightarrow 1$; hence, $c^{*}\geq 0$.
As a consequence, $c^{*}=0$ and, from (25),

$a_{n}=\frac{n}{n+\frac{1}{a_{1}}-1};$

thus, denoting $\theta:=a_{1}^{-1}-1$, we obtain $\theta>0$ and
$a_{n}=n\bigr{/}(n+\theta)$ for each $n=1,2,\ldots$, so

$\mathbb{P}(X_{n+1}\in dy\mid
X_{1},\ldots,X_{n})=\frac{\theta}{\theta+n}\nu(dy)+\frac{n}{\theta+n}\cdot\frac{1}{n}\sum_{i=1}^{n}R_{X_{i}}(dy)=\frac{\theta\nu(dy)+\sum_{i=1}^{n}R_{X_{i}}(dy)}{\theta+n}\qquad\mbox{a.s.},$

that is, $(X_{n})_{n\geq 1}$ is an MVPS with parameters $(\theta,\nu,R)$.

Sub-Case 1b: $\nu(D)>0$ and $\nu(F)=0$.

If $\nu(F)=0$ instead, then $R_{x}\ll\nu$ for $\nu$-a.e. $x$, so arguing as in
the proof of Theorem 11 in [16], there exists a jointly measurable function
$r:\mathbb{X}^{2}\rightarrow\mathbb{R}_{+}$ such that

$R_{x}(dy)=r(x,y)\nu(dy)\qquad\mbox{for }\nu\mbox{-a.e. }x.$ (26)

In that case, (19) implies that

$r(x,y)\nu(dx)\nu(dy)=r(y,x)\nu(dx)\nu(dy).$ (27)

Let $A,B,C\in\mathcal{X}$. It follows from (7) that

$\displaystyle\mathbb{P}(X_{1}$ $\displaystyle\in A,X_{2}\in B,X_{3}\in C)$
$\displaystyle=\int_{A}\int_{B}\mathbb{P}(X_{3}\in
C|X_{1}=x,X_{2}=y)\mathbb{P}(X_{2}\in dy|X_{1}=x)\nu(dx)$
$\displaystyle=\int_{A}\int_{B}\Bigl{\\{}(1-a_{2})\nu(C)+\frac{a_{2}}{2}R_{x}(C)+\frac{a_{2}}{2}R_{y}(C)\Bigr{\\}}\bigl{(}(1-a_{1})\nu(dy)+a_{1}R_{x}(dy)\bigr{)}\nu(dx)$
$\displaystyle\begin{aligned}
=\int_{A}\Bigl{\\{}(1-a_{1})&(1-a_{2})\nu(B)\nu(C)+a_{1}(1-a_{2})\nu(C)R_{x}(B)+\frac{(1-a_{1})a_{2}}{2}\nu(B)R_{x}(C)+\\\
&+\frac{a_{1}a_{2}}{2}R_{x}(B)R_{x}(C)+\frac{(1-a_{1})a_{2}}{2}\int_{B}R_{y}(C)\nu(dy)+\frac{a_{1}a_{2}}{2}\int_{B}R_{y}(C)R_{x}(dy)\Bigr{\\}}\nu(dx)\end{aligned}$
$\displaystyle\begin{aligned}
=(1-a_{1})(1-a_{2})\nu(A)&\nu(B)\nu(C)+a_{1}(1-a_{2})\nu(C)\int_{A}R_{x}(B)\nu(dx)+\\\
&+\frac{(1-a_{1})a_{2}}{2}\nu(B)\int_{A}R_{x}(C)\nu(dx)+\frac{a_{1}a_{2}}{2}\int_{A}R_{x}(B)R_{x}(C)\nu(dx)+\\\
&+\frac{(1-a_{1})a_{2}}{2}\nu(A)\int_{B}R_{y}(C)\nu(dy)+\frac{a_{1}a_{2}}{2}\int_{A}\int_{B}R_{y}(C)R_{x}(dy)\nu(dx).\end{aligned}$
(28)

By exchangeability,

$\mathbb{P}(X_{1}\in A,X_{2}\in B,X_{3}\in C)=\mathbb{P}(X_{1}\in A,X_{2}\in
C,X_{3}\in B),$

so using that $\int_{B}R_{y}(C)\nu(dy)=\int_{C}R_{y}(B)\nu(dy)$ from (19), we
obtain

$\displaystyle a_{1}$
$\displaystyle(1-a_{2})\nu(C)\int_{A}R_{x}(B)\nu(dx)+\frac{(1-a_{1})a_{2}}{2}\nu(B)\int_{A}R_{x}(C)\nu(dx)+\frac{a_{1}a_{2}}{2}\int_{A}\int_{B}R_{y}(C)R_{x}(dy)\nu(dx)$
$\displaystyle=a_{1}(1-a_{2})\nu(B)\int_{A}R_{x}(C)\nu(dx)+\frac{(1-a_{1})a_{2}}{2}\nu(C)\int_{A}R_{x}(B)\nu(dx)+\frac{a_{1}a_{2}}{2}\int_{A}\int_{C}R_{y}(B)R_{x}(dy)\nu(dx),$

which after some simple algebra becomes

$\int_{A}\int_{B}R_{y}(C)R_{x}(dy)\nu(dx)-c^{*}\cdot\nu(C)\int_{A}R_{x}(B)\nu(dx)=\int_{A}\int_{C}R_{y}(B)R_{x}(dy)\nu(dx)-c^{*}\cdot\nu(B)\int_{A}R_{x}(C)\nu(dx).$

Using the representation (26), we get in terms of measures that

$\displaystyle\bigl{(}r(x,y)r(y,z)-c^{*}r(x,y)\bigr{)}\nu(dz)\nu(dy)\nu(dx)$
$\displaystyle=\bigl{(}r(x,z)r(z,y)-c^{*}r(x,z)\bigr{)}\nu(dz)\nu(dy)\nu(dx)$
$\displaystyle=\bigl{(}r(x,z)r(y,z)-c^{*}r(x,z)\bigr{)}\nu(dz)\nu(dy)\nu(dx),$

where the last equality follows from (27). As a result, for
$(\nu\times\nu\times\nu)$-a.e. $(x,y,z)$ in $\mathbb{X}^{3}$, we have

$r(x,y)\bigl{(}r(y,z)-c^{*}\bigr{)}=r(x,z)\bigl{(}r(y,z)-c^{*}\bigr{)}.$

Suppose by contradiction that $c^{*}<0$. Then

$r(x,y)=r(x,z).$ (29)

It follows from (27) and (29) that, for $(\nu\times\nu\times\nu)$-a.e.
$(x,y,z)$ in $\mathbb{X}^{3}$,

$r(x,y)r(y,z)=r(x,z)r(z,y);$

therefore, for $\nu$-a.e. $x$ in $D$,

$\displaystyle\int_{\mathbb{X}}R_{y}(B_{x})R_{x}(dy)$
$\displaystyle=\int_{y\in\mathbb{X}}\int_{z\in
B_{x}}r(x,y)r(y,z)\nu(dy)\nu(dz)$ $\displaystyle=\int_{y\in
B_{x}}\int_{z\in\mathbb{X}}r(x,y)r(y,z)\nu(dy)\nu(dz)=\int_{B_{x}}R_{y}(\mathbb{X})R_{x}(dy)=R_{x}(B_{x}).$

On the other hand, by (20), for $\nu$-a.e. $x$ in $D$,

$\int_{\mathbb{X}}R_{y}(B_{x})R_{x}(dy)=(1-c^{*})R_{x}(B_{x})+c^{*}\nu(B_{x});$

therefore, $R_{x}(B_{x})=\nu(B_{x})$, absurd. As a result, $c^{*}=0$, which
implies as in the previous sub-case that $(X_{n})_{n\geq 1}$ is an MVPS with
parameters $(a^{-1}-1,\nu,R)$.

Case 2: $\nu(D)=0$.

If $\nu(D)=0$, then $R_{x}\equiv\nu$ for $\nu$-a.e. $x$, and since

$\mathbb{P}(X_{n+1}\in dy\mid
X_{1}=x_{1},\ldots,X_{n}=x_{n})=(1-a_{n})\nu(dy)+a_{n}\cdot\frac{1}{n}\sum_{i=1}^{n}R_{x_{i}}(dy),$

for $(\nu\times\cdots\times\nu)$-a.e. $(x_{1},\ldots,x_{n})$ in
$\mathbb{X}^{n}$ (see footnote 2), we must have

$\mathbb{P}(X_{n+1}\in dy\mid X_{1}=x_{1},\ldots,X_{n}=x_{n})=\nu(dy).$

The latter implies in particular that, for any
$B_{1},\ldots,B_{n}\in\mathcal{X}$,

$\mathbb{P}(X_{1}\in B_{1},\ldots,X_{n}\in B_{n})=\prod_{i=1}^{n}\nu(B_{i});$

therefore, $(X_{n})_{n\geq 1}$ is i.i.d.$(\nu)$, and thus trivially an MVPS,
which can be parameterized by $(a^{-1}-1,\nu,R)$. This concludes the proof of
Theorem 1.

### Acknowledgments

This study is financed by the European Union-NextGenerationEU, through the
National Recovery and Resilience Plan of the Republic of Bulgaria, project No.
BG-RRP-2.004-0008

## References

  * Aldous [1985] D. J. Aldous.  Exchangeability and related topics.  _École d’Été de Probabilités de Saint-Flour XIII 1983_ , 1117:1–198, 1985.
  * Bacallado et al. [2017] S. Bacallado, M. Battiston, S. Favaro, and L. Trippa.  Sufficientness postulates for Gibbs-type priors and hierarchical generalizations.  _Statist. Sci._ , 32(4):487–500, 2017.
  * Bandyopadhyay and Thacker [2022] A. Bandyopadhyay and D. Thacker.  A new approach to Pólya urn schemes and its infinite color generalization.  _Ann. Appl. Probab._ , 32(1):46–79, 2022.
  * Berti et al. [2023] P. Berti, E. Dreassi, F. Leisen, L. Pratelli, and P. Rigo.  Kernel based Dirichlet sequences.  _Bernoulli_ , 29(2):1321–1342, 2023.
  * Camerlenghi and Favaro [2021] F. Camerlenghi and S. Favaro.  On Johnson’s “sufficientness” postulates for feature-sampling models.  _Mathematics, special issue “Bayesian Predictive Inference and Related Asymptotics – Festschrift for Eugenio Regazzini’s 75th Birthday”_, 9:2891, 2021.
  * Fortini and Petrone [2023] S. Fortini and S. Petrone.  Prediction-based uncertainty quantification for exchangeable sequences.  _Phil. Trans. R. Soc. A_ , 381:20220142, 2023.
  * Fortini et al. [2000] S. Fortini, L. Ladelli, and E. Regazzini.  Exchangeability, predictive distributions and parametric models.  _Sankhya, Series A_ , 62:86–109, 2000.
  * Fortini et al. [2021] S. Fortini, S. Petrone, and H. Sariev.  Predictive constructions based on measure-valued Pólya urn processes.  _Mathematics, special issue “Bayesian Predictive Inference and Related Asymptotics – Festschrift for Eugenio Regazzini’s 75th Birthday”_, 9:2845, 2021.
  * Hill et al. [1987] B. M. Hill, D. Lane, and W. Sudderth.  Exchangeable urn processes.  _Ann. Probab._ , 15(4):1586–1592, 1987.
  * Janson [2019] S. Janson.  Random replacements in Pólya urns with infinitely many colours.  _Electron. Commun. Probab._ , 24, 2019.  paper no. 23, 11 pp.
  * Johnson [1932] W. E. Johnson.  Probability: the deductive and inductive problems.  _Minds_ , 41:409–423, 1932.
  * Lijoi and Prünster [2010] A. Lijoi and I. Prünster.  Models beyond the Dirichlet process.  In _Bayesian Nonparametrics_ , N. L. Hjort, C. Holmes, P. Müller and S. G. Walker, eds., pages 80–136. Cambridge University Press, Cambridge, UK, 2010.
  * Lo [1991] A. Y. Lo.  A characterization of the Dirichlet process.  _Statist. Probab. Lett._ , 12:185–187, 1991.
  * Mailler and Marckert [2017] C. Mailler and J.-F. Marckert.  Measure-valued Pólya urn processes.  _Electron. J. Probab._ , 22, 2017.  paper no. 26, 33 pp.
  * Regazzini [1978] E. Regazzini.  Intorno ad alcune questioni relative alla definizione del premio secondo la teoria della credibilià.  _G. Ist. Ital. Attuari_ , 41:77–89, 1978.
  * Sariev and Savov [2023] H. Sariev and M. Savov.  Characterization of exchangeable measure-valued Pólya urn sequences.  2023\.  Preprint. Available on https://arxiv.org/abs/2305.10083.
  * Walker and Muliere [1999] S. Walker and P. Muliere.  A characterization of a neutral to the right prior via an extension of “sufficientness” postulate.  _Ann. Statist._ , 27(2):589–599, 1999.
  * Zabell [1982] S. L. Zabell.  W. E. Johnson’s “sufficientness” postulate.  _Ann. Statist._ , 10(4):1090–1099, 1982.
  * Zabell [1995] S. L. Zabell.  Characterizing Markov exchangeability.  _J. Theor. Probab._ , 8(2):175–178, 1995.
  * Zabell [1997] S. L. Zabell.  The continuum of inductive methods revisited.  In _The Cosmos of Science: Essays in Exploration_ , J. Earman and J. D. Norton, eds., pages 351–385. Univ. Pittsburgh Press, Pittsburgh, PA, 1997\.