RELATIONAL EXCHANGEABILITY

arXiv:1607.06762v2 [math.ST] 28 Apr 2017

HARRY CRANE AND WALTER DEMPSEY

Abstract. A relationally exchangeable structure is a random combinatorial
structure whose law is invariant with respect to relabeling its relations,
as opposed to its elements. Aside from exchangeable random partitions,
examples include edge exchangeable random graphs and hypergraphs,
path exchangeable processes, and a range of other network-like structures
that arise in statistical applications. We prove a de Finetti-type structure
theorem for the general class of relationally exchangeable structures.

1. Introduction
Consider a random sequence X = (X1 , . . . , Xn ) taking values in an at most
countable set S. For concreteness, we may regard S as a set of species, so
that X records the species for a random sample of animals from a certain
population. From X, we define an equivalence relation ∼X on [n] := {1, . . . , n}
by
(1)

i ∼X j

if and only if Xi = X j .

We write Π(X) = {B1 , B2 , . . .} to denote the set partition whose blocks
B1 , B2 , . . . are the equivalence classes induced by ∼X . We sometimes write
∼Π in place of ∼X when convenient.
Suppose now that X = (X1 , . . . , Xn ) is exchangeable, meaning that
(Xσ(1) , . . . , Xσ(n) ) =D (X1 , . . . , Xn )
for all permutations σ : [n] → [n], where =D denotes equality in law.
Exchangeability of X induces exchangeability on the equivalence relation Π := Π(X) as in (1) in the sense that Πσ =D Π for all permutations
σ : [n] → [n], with Πσ defined by
i ∼Πσ j

if and only if σ−1 (i) ∼Π σ−1 ( j).

Below we present a theory of general relationally exchangeable structures which
contains the above example as a special case and generalizes Kingman’s
correspondence for exchangeable random partitions [4].
To appreciate the generality in which we work, let S again be a countable
set but now consider a sequence X = (X1 , . . . , Xn ) taking values in S × S, so
Date: May 1, 2017.
Key words and phrases. Edge exchangeable graph; Kingman’s correspondence; paintbox
process; exchangeable random partition.
H. Crane is partially supported by NSF grants CNS-1523785 and CAREER DMS-1554092.
1

2

HARRY CRANE AND WALTER DEMPSEY

Figure 1. (a) Representation of sequence of ordered pairs in
S = {a, b, c, d, e} with X1 = (a, b), X2 = (c, a), X3 = (d, e), X4 =
(a, c). (b) Representation of sequence of ordered pairs in
S = {a, b, c, d, e} with X10 = (c, a), X20 = (d, e), X30 = (a, c), X40 =
(a, b). The object in (b) can be obtained from that in (a) by
reordering (X1 , X2 , X3 , X4 ) as (X2 , X3 , X4 , X1 ). In both (a) and
(b), the edges are labeled according to where they appear in
sequence.
that each Xi is an ordered pair (ci , ri ). For a concrete application, we can
think of each Xi = (ci , ri ) as identifying the caller and receiver of a phone
call sampled uniformly at random from a telephone call log. While the data
comes in the form of a sequence X, the structure relating the calls can be
represented by a network-like object as in Figure 1. Since the sequence X
is exchangeable, the model assigns equal probability to structures that are
isomorphic up to relabeling edges as in Figures 1(a) and 1(b).
Just as we disregarded the species names in passing from X to its induced
equivalence relation ∼X in (1), we may also disregard the vertex labels in
Figure 1 to obtain an edge-labeled graph, as shown in Figure 2. The edgelabeled graph is defined formally as the equivalence class X  of all sequences
X 0 that yield the same structure as X after removing vertex labels:
(2)

X  := {X 0 : [n] → S × S : ρ X 0 = X for some bijection ρ : S → S},

where here we overload notation by allowing the bijection ρ : S → S to act on
S × S by (c, r) 7→ (ρ(c), ρ(r)), so that ρ X 0 := ρ ◦ X 0 : [n] → S × S is well-defined
by composition of functions. Exchangeability of X immediately implies edge
exchangeability of the edge-labeled graph associated to X  [1].
For another example, let S represent a set of scientists and let X =
(X1 , . . . , Xn ) record names of coauthors on a collection of n scientific journal
articles sampled uniformly from a database (e.g., arXiv). Each Xi is a finite
subset {si,1 , . . . , si,ki } ⊂ S. The assumption of uniform sampling again makes
X an exchangeable sequence, which in turn induces exchangeability on
the associated edge-labeled hypergraph constructed by disregarding vertex
labels in the induced hypergraph structure in a manner analogous to the
construction of edge-labeled graphs from the equivalence class (2).
For another example, let S be a set of Internet Protocol (IP) addresses and
let each entry of X = (X1 , . . . , Xn ) correspond to the path taken by a message
sent between two IP addresses over the Internet. Each Xi corresponds to

RELATIONAL EXCHANGEABILITY

3

Figure 2. (a) Edge-labeled graph induced by disregarding
vertex labels in Figure 1(a). (b) Edge-labeled graph induced
by disregarding vertex labels in Figure 1(b). The graphs in (a)
and (b) have equal probability under an edge exchangeable
model.
a path (si , ai,1 , . . . , ai,ki , ti ) from source si to target ti by passing through the
intermediate nodes ai,1 , . . . , ai,ki , altogether indicating that the path traversed
s to ai,1 to ai,2 and so on until passing from si,k1 to ti . If X was obtained,
for example, by uniform random sampling of source-target pairs (si , ti ) and
then by applying an algorithm, such as traceroute, to obtain a path between
si and ti , then the sequence of paths X is exchangeable and, therefore, so is
the induced path-labeled structure shown in Figure 3.
Another example in the realm of networks is to take each Xi to be an
r-step ego network, obtained, e.g., by snowball sampling a neighborhood
of size r from a randomly chosen vertex. The relationally labeled structure
is constructed by piecing together the neighborhoods obtained from the
r-neighborhoods of n randomly chosen “egos” in this population. We omit
the details of this example and instead move on to our general treatment.
Myriad other data structures arise according to a similar recipe: let S be
a set of elements and R be a set of relations on the elements in S; sample an
exchangeable sequence X taking values in R; construct a structure from X
(as in Figure 1) and obtain the corresponding relationally labeled structure
by removing the vertex labels (as in Figure 2). The resulting structure is
exchangeable with respect to relabeling of its relations, a property which we
call relational exchangeability. We now define this notion formally and prove
a generic structure theorem for infinite relationally exchangeable structures.
The formal statement is given in Theorem 2.6.
2. Relational Exchangeability
Let (S, S) be any Borel space. A countably infinite sequence of S-valued
random variables X = (X1 , X2 , . . .) is exchangeable if X σ =D X for every
permutation σ : N → N, where =D denotes equality in distribution and
X σ := (Xσ(1) , Xσ(2) , . . .) is the reordering of X according to σ. By de Finetti’s
theorem [3], the distribution of every such countably infinite sequence can
be expressed as a mixture of independent, identically distributed (i.i.d.) sequences. In particular, with P(S) denoting the space of probability measures

4

HARRY CRANE AND WALTER DEMPSEY

Figure 3. (a) and (b) both correspond to the structures induced by taking the equivalence class over paths between
vertices. In this illustration, all paths have the same source
vertex and each path is labeled by a different color, so that
the structure in (b) can be obtained by recoloring the paths
from (a) (i.e., green to orange, red to green, and orange to
red).
on (S, S), there is a unique probability measure φ on P(S) such that the
distribution of X can be expressed as
Z
(3)
P(X ∈ ·) =
ν∞ (·)φ(dν),
P(S)

where ν∞ denotes the infinite product measure induced by ν on S∞ . We call
the measure φ in (3) the de Finetti measure of X.
de Finetti’s theorem figures into our treatment of relationally exchangeable structures, which we now define. Note that all of the examples in
Section 1, and many more that could arise in practice, involve relational
structures as they are defined in the coming section. Example 2.2 provides
a concrete illustration.
2.1. Relational structures. Let α : N → N ∪{0} be a signature such that
α( j) = 0 implies α(k) = 0 for all k ≥ j. An α-structure with domain A is a
collection A = (RA
, RA
, . . .), where A is a set and each RA
⊆ Aα(j) is a relation
2
1
j

of arity α(j) on A. We adopt the convention A0 := ∅ so that RA
= ∅ whenever
j
α( j) = 0.
We write dom A := A for the domain of A and Finα for the P
set of all αA
structures A with finite dom A ⊂ Z = {. . . , −1, 0, 1, . . .} such that ∞
j=1 |R j | <
∞, where |S| denotes the cardinality of a set S. Writing dom A ⊂ f Z to denote
that dom A is a finite subset of Z, we have
Finα := {A =

(RA
, RA
2 , . . .)
1

: dom A ⊂ f Z and

∞
X
j=1

|RA
| < ∞}.
j

RELATIONAL EXCHANGEABILITY

5

A
j≥1 |R j | < ∞ implies that to every A ∈ Finα there is an rA :=
max{k ≥ 1 : RA
, ∅} < ∞, making it convenient to sometimes express A ∈
k
A
Finα as (R1 , . . . , RA
rA ) by omitting the infinite sequence of empty relations

Condition

P

after rA .
For any A∗ ⊇ A and any injection ρ : A∗ → A0 there is an induced action
ρ(A)
ρ(A)
on A = (RA
, RA
, . . .) by A 7→ ρ(A) = (R1 , R2 , . . .) with dom ρ(A) =
2
1
ρ(A) := {ρ(a) : a ∈ A} and
(4)

ρ(A)

(ρ(a1 ), . . . , ρ(aα(j) )) ∈ R j

if and only if

(a1 , . . . , aα(j) ) ∈ RA
j

for each j = 1, 2, . . ..
For n ≥ 1 and any at most countable subset of finite α-structures R ⊆ Finα
for which each A ∈ R has dom A ⊆ Z + := {1, 2, . . .}, we consider the set
 of equivalence classes of R-valued sequences x : [n] → R obtained
R[n]
as follows. Any x : [n] → R determines a relationally labeled structure by
removing the labels of the elements contained in each of the x(i) while
maintaining the integrity of the overall structure induced by x. Formally,
we define the relationally labeled structure induced by x as the equivalence
class
(5)

x  := {x 0 : [n] → R : ρ x 0 = x for some bijection ρ : Z → Z},

where ρ x : [n] → R is defined by (ρ x)(i) = ρ(x(i)) as in (4) above. We write
 as the set of all x constructed from some x : [n] → R in this way.
R[n]

Remark 2.1 (Notation). Below we reserve lowercase letters x, y, . . . for generic
(non-random) objects and uppercase letters X, Y, . . . for random objects. We use
bold letters x, y, . . . for generic (non-random) functions x : [n] → R and X, Y, . . .
for random functions X : [n] → R.
Example 2.2. In this example, we demonstrate how the structures in Section 1
fit into the framework of α-structures. For this we write A = (RA
, RA
, . . .) as an
2
1
α-structure with dom A = A and α varying according to the context.
For α(1) = 1 and α(k) = 0 for k ≥ 2, each α-structure A is determined by a
subset RA
⊆ A. If we then choose R ⊆ Finα to consist of all singleton subsets of N,
1
so that each RA
has the form {i}, i ≥ 1, then the equivalence class of x : [n] → R in
1
(5) corresponds to the equivalence relation induced by x as in (1).
For α(1) = 2, α(k) = 0 for k ≥ 2, each α-structure A with dom A = A
corresponds to a binary relation RA
⊆ A2 . Taking R ⊆ Finα to consist of all
1
A
structures with R1 = {(i, j)} for i , j corresponds to sampling from the phone call
database in Section 1: each sampled Xk = {(i, j)} corresponds to a caller-receiver pair
(i, j). The equivalence class x  gives an edge-labeled (directed) graph as in Figure 2.
(To get an undirected graph we would take each RA
to consist of symmetric pairs
1
{(i, j), ( j, i)}.)
Taking α( j) = j for all j ≥ 1 means that any α-structure is determined by a
collection RA
⊆ A j of subsets of j-tuples for every j ≥ 1. If we take R ⊂ Finα
j

6

HARRY CRANE AND WALTER DEMPSEY

to consist only of those α-structures of the form RA
= {(aσ(1) , aσ(2) , . . . , aσ(k) ) :
k
A
permutations σ : [k] → [k]} for some k ≥ 1 and R j = ∅ for all j , k, then the
elements A ∈ R can be used to represent the set of coauthors in a sample of articles.
Also for α( j) = j for all j ≥ 1, if we take R ⊂ Finα to consist only of those
α-structures of the form RA
= {(a1 , a2 , . . . , ak )} for some k ≥ 1 and RA
= ∅ for all
j
k
j , k, then each A ∈ R corresponds to a path from a1 to ak , as discussed at the end
of Section 1.
Our discussion below specializes to the case of random structures labeled
by the countable set N, which are those structures constructed just as in (5)
but for a countable sequence x : N → R. (Note well the difference between
the index set N and the domain of the structures in R, which we take to be
Z + . The domain labeling is “quotiented out” in (5), while the indexing N
remains, serving as the “edge labels” in the associated interpretation as an
edge-labeled graph in Figure 2.)
 to denote the set of such structures and we equip R with
We write RN
N
the Borel σ-field associated to its product-discrete topology induced by the
 and n ≥ 1, we define the restriction R x
following metric. For any x  ∈ RN
n 
 as the structure obtained by taking any x 0 ∈ x (i.e., x 0 : N → R
of x  to R[n]

for which there exists ρ such that ρ x 0 = x), restricting its domain to [n]
by x 0|[n] : [n] → R, i 7→ x 0 (i), and putting Rn x  := (x 0|[n] ) as in (5). By the
 , it is clear that this is well-defined and does not depend on
definition of RN
 by
the specific choice of x 0 ∈ x  . We then define the metric on RN
d(x  , x 0 ) := 1/(1 + sup{n ≥ 1 : Rn x  = Rn x 0 }),


x  , x 0 ∈ RN
,

 is compact.
with the convention that 1/∞ = 0, under which RN
 by
For any permutation σ : N → N, we define the relabeling of x  ∈ RN
σ
0
σ as the structure x  obtained by first choosing any x ∈ x  and putting
x σ := (x 0 ◦σ) , where x 0 ◦σ : N → R is defined by usual composition of
functions, (x 0 ◦σ)(i) := x 0 (σ(i)). It is once again clear that this does not
depend on the specific choice of representative x 0 ∈ x  since the actions of
ρ : N → N and σ : N → N commute for all x 0 , i.e., ρ(x 0 ◦σ) = (ρ x 0 ) ◦ σ.
 is
Definition 2.3 (Relational exchangeability). A random structure X  ∈ RN
relationally exchangeable if X σ =D X  for all permutations σ : N → N.

2.2. Representation theorem. Our main theorem establishes a generic con . The
struction for infinite relationally exchangeable structures X  in RN
construction proceeds by sampling a sequence X1 , X2 , . . . conditionally i.i.d.
in a related space R? and then modifying these observations to obtain a
new sequence X † := (X1† , X2† , . . .). We then construct the equivalence class
X † based on the sequence X1† , X2† , . . . as in (5). Since stating the theorem
formally requires some new ideas and notation, we give the construction
and key ideas of the proof prior to stating the result in Theorem 2.6.

RELATIONAL EXCHANGEABILITY

7

As above, let α : N → N ∪{0} and R ⊆ Finα be an at most countable set of
α-structures such that α(j) = 0 implies α(k) = 0 for all k ≥ j and each A ∈ R
has dom A ⊂ f Z + . Since R is at most countable, we may fix an ordering
R = {Rn }n≥1 of its elements. Given any A = (RA
, RA
, . . .) ∈ Finα and any
2
1
[0, 1]-valued sequence (Ti )i∈Z , we define TA :≡ T ◦ A as the α-structure TA
with dom(TA) := {Ti : i ∈ dom A} and relations RTA
given by
j
(6)

(Ta1 , . . . , Taα( j) ) ∈ RTA
j

if and only if

(a1 , . . . , aα(j) ) ∈ RA
j

for each j = 1, 2, . . .. We then define
[
R[0,1] :=
{TRn : T = (Ti )i∈Z ∈ [0, 1]Z }
n≥1

as the set of α-structures obtained by associating [0, 1]-valued labels to
the elements of R. More generally, if (Ξi )i∈dom A is a collection of subsets
Ξi ⊆ [0, 1], then we define ΞA by
ΞA := {TA : Ti ∈ Ξi for each i ∈ dom A}.
We equip R[0,1] with the σ-field on R[0,1] generated by all sets of the form
ΞA with A ∈ R and Ξ = (Ξi )i∈dom A a collection of Borel subsets of [0, 1].
 and any sequence ξ = (ξ )
From any x  ∈ RN
i i∈Z of i.i.d. Uniform[0, 1]
random variables, we write ξ x  to denote a random R[0,1] -valued sequence
(Zi )i≥1 obtained by first taking any representative x 0 ∈ x  and then putting
Zi = ξ x 0 (i) for each i ≥ 1, with ξ x 0 (i) defined as in (6). Since x  is fixed
in this example, each ξ x 0 (i) corresponds to an assignment of Uniform[0, 1]
random labels to the elements in the domain of x 0 (i). Since ξi , ξ j with
probability 1 for all i , j, it is immediate that the distribution of ξ x  does
not depend on the manner in which the representative x 0 is chosen. Now for
 and a sequence ξ of
any infinite relationally exchangeable structure X  ∈ RN
Uniform[0, 1] random variables independent of X  , ξ X  = (Zi )i≥1 defines a
random sequence obtained by putting Zi = ξ x 0 (i) for a representative x 0 ∈ x 
on the event X  = x  . By exchangeability of X  , the sequence Z = (Zi )i≥1
obtained in this way is also exchangeable and de Finetti’s theorem implies
that Z is distributed as an i.i.d. sequence from a random measure ν on R[0,1] ,
as described in (3).
Given ν, we define the propensity of u ∈ [0, 1] in Z by
(7)

ν? (u) := ν({A ∈ R[0,1] : u ∈ dom A}),

which equals the conditional probability of the event {u ∈ dom Z j } given ν,
for each j ≥ 1. It is clear that each u ∈ [0, 1] appears in either 0, 1, or infinitely
many of the relations (Zi )i≥1 with probability 1. First, if ν? (u) > 0, then the
strong law of large numbers implies that u occurs in infinitely many of the
relations Zi with proportion ν? (u). If ν? (u) = 0 and u ∈ Zi for some i, then
the probability that u occurs in Z j is ν? (u) = 0 independently for each j , i
and therefore u appears only once in Z with probability 1.

8

HARRY CRANE AND WALTER DEMPSEY

Clearly the set U = {u : ν? (u) > 0} is at most countable since | dom(Zi )| <
∞ for each i = 1, 2, . . .. We can, therefore, order the elements of U as u1 , u2 , . . .
such that ν? (u j ) ≥ ν? (u j+1 ) for j ≥ 1, breaking ties ν? (v) = ν? (w) as follows.
For each A ∈ R, we define
ν? (u; A) := ν({TA : T = (Ti )i∈Z ∈ [0, 1]Z such that u ∈ dom(TA)}),

u ∈ [0, 1],

to be the measure assigned to the subset of R[0,1] whose structure is consistent
with A and which contains u in its domain. Assuming ν? (v) = ν? (w), we
assign the smaller label to v if there is some k ≥ 1 such that ν? (v; R j ) =
ν? (w; R j ) for all j < k and ν? (v; Rk ) > ν? (w; Rk ). If ν? (v; R j ) = ν? (w; R j ) for all
j ≥ 1, then we label v and w in increasing order, i.e., if we are to assign labels
j and j + 1 to v and w and if v < w, then we shall put u j = v and u j+1 = w;
otherwise, we put u j = w and u j+1 = v. The ordering U = (u j ) j≥1 is thus
uniquely determined by ν and the fixed ordering of R chosen at the outset.
Now given U, for any A ∈ R[0,1] we define A? (suppressing the dependence on ν) by replacing each occurrence of u j ∈ U by j and replacing each occurrence of v0 < U in A by a unique non-positive integer z(v0 ) = 0, −1, −2, . . .
so that for v0 , v00 < U and both in dom A with v0 ≤ v00 we have z(v0 ) ≤ z(v00 )
and the z(v0 ) are chosen to be the largest possible non-positive integers that
satisfy this condition. (For example, if v1 < v2 < v3 are the only elements in
dom A that are not in U, we assign z(v3 ) = 0, z(v2 ) = −1, and z(v1 ) = −2.)
Every A ∈ R[0,1] thus corresponds to a unique such A? and we define
R? as the set of all structures A? obtained in this way. Note that since
R is at most countable, so is R? . Also, although we have constructed R?
using U (and therefore ν), the set R? depends only on R, justifying the term
R-simplex in our definition of FR in (8) below.
The elements of R? are thus α-structures A? with dom A? ⊆ Z. We
define the R-simplex FR by




X




? : fB ≥ 0 and
(8)
FR := 
(
f
)
f
=
1
,

B
B
B∈R




?
B∈R

on which we equip the metric
dFR ( f, f 0 ) :=

X

| fB − fB0 |,

f, f 0 ∈ FR ,

B∈R?

and the associated Borel σ-field.
 by first
Any f ∈ FR determines a unique probability measure ε f on RN
drawing X = (X1 , X2 , . . .) i.i.d. from
(9)

P(Xi = B | f ) = fB ,

B ∈ R? ,

and then constructing X † = (X1† , X2† , . . .) from X as follows. We initialize by
putting m0 = 0. For each n ≥ 1, given mn−1 , we replace the non-positive
elements in dom Xn according to the rule:
(i) If dom Xn has no non-positive elements, then put mn = mn−1 and
Xn† := Xn .

RELATIONAL EXCHANGEABILITY

9

(ii) If dom Xn has non-positive elements 0, . . . , −k for k ≥ 0, then define
Xn† by replacing each occurrence of −i, for 0 ≤ i ≤ k, in Xn by
mn−1 −i, then putting mn = mn−1 −k−1 and keeping positive elements
unchanged. See Example 2.5 below for an illustration.
Note the distinction between the use of non-positive elements in construction
of Xi and Xi† respectively. The non-positive elements of each Xi ∈ R? serve
to denote the non-recurring particles that appear only within this particular
relation. The non-positive elements of Xi† , on the other hand, serve to denote
the non-recurring particles across all relations in the sequence X † . We define
ε f to be the distribution of X † constructed by applying (5) to the sequence
X†.
From ν, we define f ν = ( fBν )B∈R? ∈ FR by
(10)

fBν := ν({A ∈ R[0,1] : A? = B}),

B ∈ R? .

This choice of f ν = ( fBν )B∈R? is uniquely determined by ν and the fixed
ordering of R. Conversely, given f = ( fB )B∈R? ∈ FR we construct a measure
ν f on R[0,1] to be the distribution of ξY from (6) for Y drawn from distribution
(9) and ξ = (ξi )i∈Z i.i.d. Uniform[0, 1] independent of Y. Proposition 2.4
proves that the above procedure does not alter the random, relationally
labeled structure.
Proposition 2.4. Let X  be relationally exchangeable and let θ = (θi )i∈Z be i.i.d.
Uniform[0, 1] independent of X  . Then (((θ X  )? )† ) = X  a.s., where (θ X  )?
denotes the application of ? : R[0,1] → R? to each component of the sequence θ X  .
Proof. Let θ = (θi )i∈Z be i.i.d. Uniform[0, 1] independently of X  . Each event
X  = x  gives rise to a probability measure ν on R[0,1] through the de Finetti
measure of θ x  ; see (3). Let U = (ui )i≥1 be the ordered subset of [0, 1]
corresponding to the atoms of ν? as in (7). Since θ are i.i.d. Uniform[0, 1],
we have
P{θi , θ j for all i , j} = 1,
which implies that distinct i, j ∈ Z are labeled distinctly in θ x  with probability 1. In particular, the non-positive labels in (θ x  )? account for all those
elements that appear in only one entry of the sequence θ x  . It follows
that ((θ x  )? )† ∈ x  with probability 1 and, thus, (((θ x  )? )† ) = x  with
probability 1 for all possible outcomes X  = x  .

Example 2.5. To illustrate the above procedure, let R consist of the singleton
sets ({i}), i ≥ 1, just as in the first part of Example 2.2, written as {1}, {2}, . . . for
simplicity. Let U = (ui )i≥1 be a countable subset of [0, 1]. From R = {{1}, {2}, . . .},
we obtain R? = {{0}, {1}, . . .} since for any sequence T = (Ti )i∈Z and any {i}, i ≥ 1,
the transformed relation T{i} ≡ {Ti } has either Ti ∈ U or Ti < U. If Ti = uk ∈ U,
then {Ti }? = {k} for k ≥ 1; and if Ti = v < U, then {Ti }? = ({0}).
Given ( f{0} , f{1} , . . .) ∈ FR , we generate a sequence X1 , X2 , . . . of singleton sets
i.i.d. as in (9), from which we obtain X1† , X2† , . . . by reassigning occurrences of 0

10

HARRY CRANE AND WALTER DEMPSEY

to the greatest negative integer that has not yet appeared in the sequence. For
example, if the sequence begins {4}, {0}, {2}, {0}, {2}, {2}, {0}, . . ., then we reassign
labels to obtain {4}, {0}, {2}, {−1}, {2}, {2}, {−2}, . . .. Delabeling according to (5) (or
equivalently (1)) yields the equivalence classes {1}, {2}, {3, 5, 6}, {4}, {7}.
For another example, let R consist of ordered pairs {(i, j)}, 1 ≤ i , j < ∞, so that
we are in the phone call example of Section 1. Let U = (ui )i≥1 be a countable subset
of [0, 1]. Then R = {{(i, j)} : i , j ≥ 1} and
R? = {{(i, 0)} : i ≥ 1} ∪ {{(0, i)} : i ≥ 1} ∪ {{(0, −1)}, {(−1, 0)}} ∪ R
since any T = (Ti )i∈Z and any {(i, j)} ∈ R is transformed by T{(i, j)} = {(Ti , T j )},
which may have Ti = ui0 ∈ U and T j = u j0 ∈ U in which case {(Ti , T j )}? = {(i0 , j0 )}.
If Ti = ui0 ∈ U and T j < U, then {(Ti , T j )}? = {(i0 , 0)}. If Ti < U and T j = u j0
then {(Ti , T j )}? = {(0, j0 )}. If Ti , T j < U then {(Ti , T j )}? will equal {(0, −1)} or
{(−1, 0)} depending on whether T j < Ti or Ti < T j , respectively.
The above construction gives the following representation theorem.
Theorem 2.6. Let α be a signature, R ⊆ Finα , and fix an ordering R = (Rn )n≥1 .
 . Then there exists a
Let X  be a relationally exchangeable random structure in RN
probability measure φ on FR such that X  ∼ εφ , where
Z
(11)
εφ (·) =
ε f (·)φ(d f ).
FR

A canonical version of the measure φ in Theorem 2.6 can be constructed
as in (10) above, and this is the measure we construct in the following proof.
Proof. We proceed by constructing φ as in (10) and showing that Y † ∼ εφ
satisfies Y † =D X  .
To see this, we first let ψ be the de Finetti measure on P(R[0,1] ) (i.e., the
space of probability measures on R[0,1] ) associated to ξ X  for ξ = (ξi )i∈Z
i.i.d. Uniform[0, 1] independently of X  . In particular, the distribution of
ξ X  is conditionally i.i.d. from ν ∼ ψ. The measure ψ determines a measure
φ on FR through (10).
Given f ∼ φ, we construct Y = (Y1 , Y2 , . . .) as conditionally i.i.d. from the
distribution in (9) and Y † as in (i) and (ii) above. Let U = (ui )i≥1 be the atoms
of θ Y † for θ = (θi )i∈Z i.i.d. Uniform[0, 1] independent of Y † , let ζ = (ζk )k≤0 be
i.i.d. Uniform[0, 1] independently of everything else, and define ξ f = (ξi )i∈Z
by
(
ui ,
i ≥ 1,
ξi =
ζi , otherwise.
First note that the conditional distribution of ξ f Y † given f is the same as the
conditional law of θ Y † given ν f , since the ξi for i ≥ 1 were constructed from
the atoms of θ Y † . Writing D(X | Y) to denote the conditional distribution

RELATIONAL EXCHANGEABILITY

11

of X given Y, we thus have
(12)

D(ξ f Y † | f ) = D(θ Y † | ν f )

(13)

D(ξ f Y † | f ) = D(θ X  | ν f ),

and

where (13) follows from the construction of φ from the de Finetti measure ψ
of ξ X  . From (12) and (13) it follows that
D((((ξ f Y † )? )† ) | f ) = D((((θ Y † )? )† ) | ν f )
D((((ξ f Y † )? )† )

and

? †

| f ) = D((((θ X  ) ) ) | ν f ),

and thus
D((((θ Y † )? )† ) | ν f ) = D((((θ X  )? )† ) | ν f ).
By Proposition 2.4, we have (((θ Y † )? )† ) = Y † a.s. and (((θ X  )? )† ) = X  ,
implying Y † =D X  as desired.

2.3. Special cases. As discussed in Example 2.5, the case in which R corresponds to the singleton sets {i} for i ≥ 1 gives FR equal to the ranked
simplex




X




↓
∆ := 
(
f
,
f
,
.
.
.)
:
f
≥
f
≥
·
·
·
≥
0,
f
≥
0,
f
=
1
.

0 1
2
0
1
i




i≥0

To see this note that R[0,1] is the set of singleton elements of [0, 1], i.e.,
R[0,1] := {{u} : u ∈ [0, 1]}.
An exchangeable sequence X = (X1 , X2 , . . .) in R[0,1] gives rise to a random
countable subset U ⊂ [0, 1] of elements that appear infinitely often among
the Xi and its complement [0, 1] \ U consisting of all elements appearing at
most once among the Xi . In the construction of X † from X described above,
any occurrence Xi = {u} for u < U gives rise to Xi? = {0}, explaining why the
definition of FR in (8) corresponds to the simplex of elements ( fi )i≥0 .
Following Example 2.2, the case of edge exchangeable random (directed)
graphs corresponds to R ⊂ Finα with α(1) = 2 and α(k) = 0 for k ≥ 2, with
each A ∈ R having RA
= {(i, j)}, i , j. In this case, R[0,1] corresponds to all
1
pairs (u, v) for u, v ∈ [0, 1]. An exchangeable sequence X in R[0,1] determines
a random subset U ⊂ [0, 1]. Now, in each Xi there can be 0, 1, or 2 elements
v < U. Occurrences of such elements are replaced by 0 and −1, as explained
in Example 2.5.
In general, we call the occurrences of any u < U in the sequence X blips.
These elements are merely a ‘blip’ in the overall sequence X—they occur only
for an instant and then never again. Our labeling convention in defining R?
is that the non-positive labels correspond to the blips. Theorem 2.6 describes
how blips arise in general relationally exchangeable structures.

12

HARRY CRANE AND WALTER DEMPSEY

3. Concluding
Recent work in the statistical analysis of network data underscores the
significance of relationally labeled structures in applications, as many data
structures which are typically represented graphically, such as social networks and networks detailing email correspondence and professional collaborations, arise from a process by which interactions or relations accumulate
within a population of otherwise indistinguishable individuals. The work in
[1] focused on the case of edge and hyperedge exchangeable random graphs,
but the additional examples in Section 1 involving repeated path sampling
and snowball sampling are also highly relevant in networks applications.
The representation theorem serves two immediate statistical purposes. First,
the representation characterizes a general class of nonparametric statistical
models of potential interest in the aforementioned applications. Second,
it establishes that vertices arrive in size-biased random order in relationally exchangeable structures, explaining why the common assumption of
exchangeable vertex labeling, as presented in graphon models [5], is not
tenable in many applications. We reserve discussion of these practical
implications for other work; see [1, 2].
References
[1] H. Crane and W. Dempsey. Edge exchangeable models for network data. arXiv:1603.04571,
2015.
[2] H. Crane and W. Dempsey. A framework for statistical network modeling.
arXiv:1509.08185, 2015.
[3] B. de Finetti. La prévision: ses lois logiques, ses sources subjectives. Annales de l’Institut
Henri Poincaré, 7:1–68.
[4] J. F. C. Kingman. Random partitions in population genetics. Proc. Roy. Soc. London Ser. A,
361(1704):1–20, 1978.
[5] L. Lovász and B. Szegedy. Limits of dense graph sequences. J. Comb. Th. B, 96:933–957,
2006.
Department of Statistics & Biostatistics, Rutgers University, 110 Frelinghuysen Avenue, Piscataway, NJ 08854, USA
E-mail address: hcrane@stat.rutgers.edu
URL: http://stat.rutgers.edu/home/hcrane
Department of Statistics, University of Michigan, 1085 S. University Ave, Ann Arbor,
MI 48109, USA
E-mail address: wdem@umich.edu

