{'fraction_non_alphanumeric': 0.06271094432249993, 'fraction_numerical': 0.018480492813141684, 'mean_word_length': 3.72246990637539, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The cut metric for probability distributions

Guided by the theory of graph limits, we investigate a variant of the cut metric for limit objects of sequences of discrete probability distributions. Apart from establishing basic results, we introduce a natural operation called {\em pinning} on the space of limit objects and show how this operation yields a canonical cut metric approximation to a given probability distribution akin to the weak regularity lemma for graphons. We also establish the cut metric continuity of basic operations such as taking product measures.


INTRODUCTION AND RESULTS
1.1. Background and motivation. The theory of graph limits clearly qualifies as one of the great recent success of modern combinatorics [5,6,24,26]. Exhibiting a complete metric space of limit objects of sequences of finite graphs, the theory strikes a link between combinatorics and analysis. In fact, the notion of graphon convergence unifies several combinatorially meaningful concepts, such as convergence of subgraph counts or with respect to the cut metric. In effect, combinatorial ideas admit neat analytic interpretations. For instance, the Szemerédi regularity lemma yields the compactness of the graphon space [27].
While sequences of graphs occur frequently in combinatorics (e.g., in the theory of random graphs), sequences of probability distributions on increasingly large discrete domains play no less prominent a role in the mathematical sciences. For instance, such sequences are the bread and butter of mathematical physics. A classical example is the Ising model on a d-dimensional integer lattice of side length n, a model of ferromagnetism. The Ising model renders a probability measure, the so-called Boltzmann distribution, on the space {−1, +1} [n] d that captures the distribution of the magnetic spins of the n d vertices. The objective is to extract properties of this probability distribution in the limit of large n such as the nature of correlations. While mathematical physics has a purpose-built theory of limits of probability measures on lattices [17], this theory fails to cover other classes of important statistical mechanics models, such as mean-field models that 'live' on random graphs [30]. Additionally, in statistics and data science sequences of discrete probability distributions arise naturally, e.g., as the empirical distributions of samples as more data are acquired. Nevertheless, there has been little research on a general theory of limits of probability measures on discrete domains. Perhaps the most prominent exception is the Aldous-Hoover representation of exchangeable arrays, and its ramifications [1,19,21].
The purpose of this paper is to show how the theory of graph limits can be adapted and extended to obtain a similarly coherent theory of limits of discrete probability distributions. First cursory steps were already taken in an earlier contribution [11]. For instance, a probabilistic version of the cut metric was defined in that paper. Moreover, Diaconis and Janson [13] and Panchenko [34] pointed out the connection between the theory of graph limits and the Aldous-Hoover representation. But thus far a complete and concise disquisition has been lacking. We therefore develop the basics of a cut-norm based limiting theory for probability measures, including the completeness and compactness of the space of limiting objects, a kernel representation, a sampling theorem and a discussion of the connection with exchangeable arrays. Some of the proofs rely on arguments similar to the ones used in the theory of graph limits, and none of them will come as a gross surprise to experts. In fact, a few statements (such as the compactness of the space of limiting objects) already appeared in [11], albeit without detailed proofs, and a few others (such as the characterisation of exchangeable arrays) are generalisations of results from [13]. But here we present unified proofs of these basic results in full generality to provide a coherent and mostly self-contained treatment that, we hope, will facilitate applications.
Additionally, and this constitutes the main technical novelty of the paper, we present a new construction of regular partitions for limit objects of discrete probability distributions. This construction is a continuous generalisation of the pinning operation for discrete probability distributions introduced in [8,32,36]. The result provides 1 n (σ,τ)∈S x∈X γ(σ, τ) 1{σ x = ω} − 1{τ ϕ(x) = ω} . (1.1) The idea is that we first get to align µ, ν as best as possible by choosing a suitable coupling γ along with a permutation ϕ of the n coordinates. Then an adversary comes along and points out the largest remaining discrepancy. Specifically, the adversary picks an event S ⊂ Ω n × Ω n under the coupling, a set X ⊂ [n] of coordinates and an element ω ∈ Ω and reads off the discrepancy of the frequency of ω on S, X . It is easily verified that (1.1) defines a pre-metric on the space L n = L n (Ω) of probability distribution on Ω n . Thus, ∆ ⊠ ( · , · ) is symmetric and satisfies the triangle inequality. But distinct µ, ν need not satisfy ∆ ⊠ (µ, ν) > 0. Hence, to obtain a metric space L n = L n (Ω) we identify any µ, ν ∈ L n with ∆ ⊠ (µ, ν) = 0. Following [11], we embed the spaces L n into a joint space L . Specifically, let P (Ω) be the space of all probability distributions on Ω. We identify P (Ω) with the standard simplex in R n and thus endow P (Ω) with the Euclidean topology and the corresponding Borel algebra. Further, let S be the space of all measurable maps σ : [0, 1] → P (Ω), σ → σ x , up to equality (Lebesgue-)almost everywhere. We equip S with the L 1 -metric and the corresponding Borel algebra, thus obtaining a complete, separable space. Much as in the discrete case, for probability distributions µ, ν on S we let Γ(µ, ν) be the space of all couplings of µ, ν, i.e., probability distributions γ on S × S with marginals µ, ν. Moreover, let S be the space of all measurable bijections ϕ : [0, 1] → [0, 1] such that both ϕ and its inverse ϕ −1 map the Lebesgue measure to itself. 1 Then the cut distance of µ, ν is defined by the expression where, of course, S, X range over measurable sets. Thus, as in the discrete case we first align µ, ν as best as possible by choosing a coupling and a suitable 'permutation' ϕ. Then the adversary puts their finger on the largest remaining discrepancy. One easily verifies that (1.2) defines a pre-metric on L . Thus, identifying any µ, ν with P (Ω) whose value on the interval [(i − 1)/n, i /n) is just the atom δ σ i ∈ P (Ω) for each i ∈ [n]. (This construction is somewhat similar to the one proposed for 'decorated graphs' in [25].) Then we letμ ∈ L be the distribution oḟ σ ∈ S for σ chosen from µ; in symbols,μ Thus, we obtain a map L n → L , µ →μ. The definition of the cut metric guarantees that D ⊠ (μ,ν) = 0 if ∆ ⊠ (µ, ν) = 0. Consequently, the map µ →μ induces a map L n → L. The following statement shows that this map is in fact an embedding, and that therefore the space L unifies all the spaces L n , n ≥ 1.
We will see a few examples of convergence in the cut metric momentarily. But let us first explore a convenient representation of the space L.
1.2.2. The kernel representation. As in the case of graph limits, Ω-laws can naturally be represented by functions on the unit square that we call kernels. To be precise, let K be the set of all measurable maps κ : [0, 1] 2 → P (Ω), (s, x) → κ s,x , up to equality almost everywhere. For κ, κ ′ ∈ K we define, with S, X ranging over measurable sets, As before (1.3) defines a pre-metric on K . We obtain a metric space K by identifying κ, There is a natural map K → L . Namely, for a kernel κ and s ∈ [0, 1] let κ s : [0, 1] → P (Ω) be the measurable map x → κ s,x . This map belongs to the space S . Thus, κ induces a probability distribution µ κ on S , namely the distribution of κ s for a uniformly random s ∈ [0, 1]. The definition of the cut distance guarantees that Therefore, as pointed out in [11], the map κ → µ κ induces a map K → L.
Thus, any Ω-law µ can be represented by an Ω-kernel, which we denote by κ µ .

Example 1.4.
With Ω = {0, 1} let µ (n) ∈ L n be uniformly distributed over all σ ∈ {0, 1} n with even parity. In symbols, Similarly, let ν (n) be uniformly distributed on the set of σ ∈ {0, 1} n with odd parity. Then µ (n) , ν (n) have total variation distance one for all n because they are supported on disjoint subsets of {0, 1} n . Nevertheless, in the cut distance both sequences (µ (n) ) n , (ν (n) ) n converge to the common limit µ = δ u ∈ L supported on u : [0, 1] → P ({0, 1}), x → (1/2, 1/2). Specifically, we claim that To verify the first bound, consider the following coupling γ (n) : choose the first n −1 bits σ 1 , . . . , σ n−1 ∈ {0, 1} uniformly and independently and choose σ n ∈ {0, 1} so that n i=1 σ i ≡ 0 mod 2. Then γ (n) ∈ P (Ω n × Ω n ) is the distribution of ((σ 1 , . . . , σ n ), (σ 1 , . . . , 1−σ n )). In effect, under γ (n) the two n-bit vectors differ in exactly one position, whence the first part of (1.4) follows from (1.1). The second bound in (1.4) follows from the central limit theorem. Example 1.5. Let µ (n) be the probability distribution on {0, 1} n induced by the following experiment. First, pick s ∈ [0, 1] uniformly at random. Then, given s, obtain σ ∈ {0, 1} n by letting σ i = 1 with probability i s/n independently for each i ∈ [n]. In formulas, Kernel representations κ (n) of µ (n) are displayed in Figure 1 for some values of n. The sequence κ (n) converges to the kernel κ : [0, 1] 2 → P ({0, 1}) defined by κ s,x (1) = sx, κ s,x (0) = 1 − sx. Example 1.6. The Curie-Weiss model is an (extremely) simple model of ferromagnetism. The vertices of a complete graph of order n correspond to iron atoms that can take one of two possible magnetic spins ±1. Energetically it is beneficial for atoms to be aligned and the impact of the energetic term is governed by a temperature parameter T > 0. To be precise, the Boltzmann distribution µ (n) on {±1} n defined by captures the distribution of spin configurations at a given temperature. The Curie-Weiss model is completely understood mathematically and it is well known that a phase transition occurs at T = 1. In the framework of the cut distance, this phase transition manifests itself in the different limits that the sequence (µ (n) T ) n converges to. Specifically, the kernel κ T representing the limit reads where 0 < m T < 1 is the unique zero of m T /T − ln(1 + m T )/2 + ln(1 − m T )/2 for T > 1.

Counting and sampling.
In the theory of graph limits convergence with respect to the cut metric is equivalent to convergence of subgraph counts. We are going to derive a similar equivalence for Ω-laws. In fact, we are going to derive an extension of this result that links the cut metric to the theory of exchangeable arrays. We recall that a probability distribution Ξ on the space Ω N×N of infinite Ω-valued arrays is exchangeable if the following is true. If X Ξ = (X Ξ (i , j )) i,j ≥1 ∈ Ω N×N is drawn randomly from Ξ, then for any integer n and for any permutations ϕ, ψ : [n] → [n] the random n × n-arrays are identically distributed. Let X = X(Ω) denote the set of all exchangeable distributions. Since the product space Ω N×N is compact by Tychonoff's theorem, endowed with the weak topology X is a compact, separable space. A kernel κ ∈ K naturally induces an exchangeable distribution. Specifically, let s 1 , x 1 , s 2 , x 2 , . . . ∈ [0, 1] be mutually independent uniformly distributed random variables. We obtain a random array X κ ∈ Ω N×N by drawing independently for any i , j ∈ N and element X κ (i , j ) ∈ Ω from the distribution κ s i ,x j ∈ P (Ω). Clearly, the distribution Ξ κ of X κ is exchangeable. By extension, a probability distribution π on K induces an exchangeable distribution as well. Indeed, with κ π ∈ K drawn from π, we let Ξ π ∈ X be the distribution of the random array X π ∈ Ω N×N obtained by first drawing κ π independently of the (s k , x ℓ ) k,l ≥1 and then drawing each entry X π (i , j ) from κ π s i ,x j . We equip the space P (K) of probability measure on K with the weak topology.
For µ ∈ L let us write X µ for the exchangeable array X κ µ induced by a kernel representation of µ. Suppose that (µ N ) N≥1 is a sequence of Ω-laws that converges to µ ∈ L. Then Theorem 1.7 shows that for any n ≥ 1 and for any (1.5) Conversely, if µ N , µ ∈ L are such that (1.5) holds for all n, τ, then Theorem 1.7 implies that lim N→∞ D ⊠ (µ N , µ) = 0.
Thus, with Ω n×n -matrices replacing subgraphs, Theorem 1.7, provides the probabilistic counterpart of the equivalence of subgraph counting and graphon convergence [24,Theorem 11.5].
Additionally, the theory of graph limits shows that a large enough random graph obtained from a graphon by sampling is close to the original graphon in the cut metric. There is a corresponding statement in the realm of probability distributions as well. Specifically, for an integer n ≥ 1 let µ n ∈ P (Ω n ) be the discrete probability distribution defined by In words, µ n is the empirical distribution of the rows of (X µ (i , j )) i,j ∈[n] . Strictly speaking, being dependent on the random coordinates (s i , x j ) i,j ≥1 , µ n is a random probability distribution on Ω n . The following theorem supplies a probabilistic version of the sampling theorem for graphons [5,Lemma 4.4]. The following theorem implies that the dependence on n in Theorem 1.8 is best possible, apart from the value of the constant c. Theorem 1.9. There is a constant c > 0 such that for any ε > 0 there exists µ ∈ L such that D ⊠ (µ, ν) ≥ ε for all ν ∈ L whose support contains at most exp(c/ε 2 ) configurations.

Extremality.
Among all the probability measures on the discrete domain Ω n , the product measures are clearly the simplest. We will therefore be particularly interested in distributions that are close to product measures in the cut metric. To this end, for a probability measure µ on Ω n we let Thus,μ i ∈ P (Ω) is the marginal distribution of the i th coordinate under the measure µ, andμ is the product measure with the same marginals as µ. Then ∆ ⊠ (µ,μ) gauges how 'similar' µ is to a product measure. To be precise, since the cut metric is quite weak, a 'small' value of ∆ ⊠ (µ,μ) need not imply that µ behaves like a product measure in every respect. For instance, the entropy of µ might be much smaller than that ofμ. But if ∆ ⊠ (µ,μ) is small, then (1.5) implies that the joint distribution of a bounded number of randomly chosen coordinates of µ is typically close to a product measure in total variation distance. A similar measure of proximity to a product distribution is meaningful on the space of Ω-laws as well. Formally, for µ ∈ L defineμ ∈ L as the atom concentrated on the single function Since D ⊠ (μ,ν) = 0 whenever D ⊠ (µ, ν) = 0, (1.6) induces a map µ ∈ L →μ ∈ L. The lawsμ with µ ∈ L represent the generalisation of discrete product measures. Since each µ ∈ L is represented by a distribution on S that places all the probability mass on a single point, we call the lawsμ extremal. Moreover, µ ∈ L is called ε-extremal if D ⊠ (µ,μ) < ε. The following result summarises basic properties of extremal laws and of the map µ →μ.
Furthermore, the set of extremal laws is a closed subset of L. 5 1.2.5. Pinning. The regularity lemma constitutes one of the most powerful tools of modern combinatorics. In a nutshell, the lemma shows that any graph can be approximated by a mixture of a bounded number of 'simple' graphs, namely quasi-random bipartite graphs. We will present a corresponding result for probability measures, respectively laws. Specifically, we will show that any law can be approximated by a mixture of a small number of extremal laws. Indeed, we will show that actually this approximation can be obtained by a simple, mechanical procedure called 'pinning'. This is in contrast to the proof of the graphon regularity lemma, where the regular partition results from a delicate construction that involves tracking a potential function.
To state this result, we observe that the pinning construction is well-defined on the space L as well. To be precise, if µ, ν ∈ L have cut distance zero, then µσ ↓θ , νσ ↓θ are identically distributed, and so are µ ↓θ and ν ↓θ . Consequently, we can apply the pinning operation directly to elements of the space L.
Hence, the law µ ↓θ , a mixture of no more than |Ω| θ extremal laws, likely provides an ε-approximation to µ. Thus, Theorem 1.11 can be viewed as a weak regularity lemma.
1.2.6. Continuity and overlaps. There are certain natural operations on probability measures and, by extension, laws that turn out to be continuous with respect to the cut metric. First, we consider the construction of the product measure. For discrete measures µ, ν ∈ L n (Ω) we can view their product µ ⊗ ν as a probability distribution on (Ω × Ω) n such that for any σ 1 , τ 1 , . . . , σ n , τ n ∈ Ω, We extend this construction to laws by way of the kernel representation. To this end, let Λ : ⊗-operation is well defined on the kernel space K. Hence, due to Theorem 1.3 the construction extends to laws, i.e., given Ω-laws µ, ν we obtain an Ω 2 -law µ ⊗ ν. Furthermore, it is easy to see that for any µ, ν ∈ L n (Ω) the Ω 2 -law representing the product measure µ ⊗ ν is precisely the ⊗-product of the lawsμ,ν representing µ, ν.
There is a second fundamental operation on distributions/laws that resembles the operation of obtaining a n × n-rank one matrix from two vectors of length n. Specifically, for vectors σ, We extend the ⊕-operation to kernels as follows. For κ, κ ′ : It is easy to see that for κ, ⊕-operation is well-defined on the space K and thus, due to Theorem 1.3, on the space L as well. Moreover, for discrete measures µ, ν ∈ P (Ω n ) one verifies immediately that the law representing µ ⊕ ν coincides withμ ⊕ν.
1.3. Discussion and related work. Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi launched the theory of (dense) graph limits in a series of important and influential articles [5,6,25,26,27]. Lovász [24] provides a unified account of the state of the art up to about 2012. Moreover, Janson [20] gives an excellent account of the measuretheoretic foundations of the theory of graph limits and some of its generalisation.
Given the many areas of application where sequences of probability measures on increasingly large discrete cubes appear, the most prominent example being perhaps the study of Boltzmann distributions in mathematical physics, it is unsurprising that attempts have been made to construct limiting objects for such sequences. The theory of Gibbs measures embodies the classical, physics-inspired approach to this task [17]. Here the aim is to construct and classify all possible 'infinite-volume' limits of Boltzmann distributions defined on spatial structures such as trees or lattices. The limiting objects are called Gibbs measures. A fundamental question, whose ramifications extend from the study of phase transitions in physics to the computational complexity of counting and sampling, is whether there is a unique Gibbs measure that satisfies all the finite-volume conditional equations (e.g, [16,37,38]). However, since the theory of Gibbs measures is confined to systems with an underlying latticelike geometry, numerous applications are beyond its reach. For instance, Marinari et al. [30] argued that the classical theory of Gibbs measures does not provide an appropriate framework for the study of (diluted) mean-field models such as the Sherrington-Kirkpatrick model, the Viana-Bray model or the hardcore model on a sparse random graph. Further examples of 'non-spatial' sequences of distributions abound in computer science, statistics and data science.
Panchenko [34,35] employed the more abstract Aldous-Hoover representation of exhangeable arrays in his work on mean-field models [1,19]. Kallenberg's monograph [21] provides the definite treatment of this abstract theory. Furthermore, Austin [3] extends and generalises the concept of exchangeable arrays and discusses applications to the Viana-Bray spin glass model. The close relationship between the theory of graph limits and exchangeable arrays was first noticed by Diaconis and Janson [13]. Their [13, Theorem 9.1] is essentially equivalent to Theorem 1.7. Moreover, the appendix of Panchenko's monograph [34] also contains a proof of the Aldous-Hoover representation theorem via graph limits.
Although the connection between genuinely probabilistic constructions such as the Aldous-Hoover representation and graph limits was noticed in prior work [13,34], those contributions did not actually work out a full adaptation of the theory of graph limits to a probabilistic setting. Only a prior article by Coja-Oghlan, Perkins and Skubch [11] made a first cursory attempt at filling this gap. The article [11] already contained the definition (1.2) of the cut metric and of the space L of laws. Additionally, the compactness of the space L (Theorem 1.1) and a weaker version of the kernel representation (Theorem 1.3) were stated in [11], although no detailed proofs were given. Furthermore, a definition similar to the discrete cut metric (1.1) was devised in [10] and a statement similar to Theorem 1.13 was previously proved by Coja-Oghlan and Perkins [9, Proposition A.2]. Finally, versions of the pinning operation for discrete probability measures appeared in [8,32,36] and recently Eldad [14] devised an extension to subspaces of R n , i.e., to the case of spins that need not take discrete values.
The contribution of the present paper is that we expressly and explicitly adapt and extend the concepts of the theory of graph limits to the context of probability distributions on increasing discrete domains. We present in a unified way the proofs of the most important basic facts such as the relationship between the discrete and the continuous cut metric (Theorem 1.2), the kernel representation (Theorem 1.3), the sampling theorem (Theorem 1.8) and the continuity of product measures (Theorems 1.12 and 1.13). The proofs of these results are based on extensions and adaptations of techniques from the theory of graph limits. Moreover, we present a self-contained derivation of the representation theorem for exchangeable arrays (Theorem 1.7). The added value by comparison to prior work [11,13] is that here we present detailed, unified proofs that operate directly in the probabilistic setting, rather than by extensive allusion to the graphon space. Additionally, we present a self-contained proof of the compactness result (Theorem 1.1). While the argument set out in, e.g., [24,Chapter 9] could be adapted to the probabilistic setting, we present a different argument based on analytic techniques that might be of independent interest. But the main technical novelty is certainly the pinning theorem (Theorem 1.11) that generalises the discrete version from [8]. The proof is delicate and uses many of the other, more basic results.
Finally, we remark that the pinning operation from Theorem 1.11 is somewhat reminiscent of Tao's construction of regular partitions [40]. Specifically, Tao's construciton of a regular partition is based on sampling a number θ of vertices of a graph G and then partitioning the remaining vertices into 2 θ classes according to their adjacencies with the reference vertices. The discrete version pinning operation from [8,36] proceeds similarly; see Theorem 4.1 below, except that the number of pinned coordinates θ is chosen randomly, rather than deligently given G. The same is true of the number of pinned coordinates in Theorem 1.11, which additionally yields a continuous version applicable to general Ω-laws. It might be an interesting question for future work to see if the pinning operation might yield an elegant and efficient algorithmic regularity lemma, and whether the construction extends to stronger versions of regularity.
1.4. Outline. After presenting the necessary background and notation in Section 2, in Section 3 we will prove the basic facts about laws and the cut metric stated above. Specifically, Section 3 contains the proofs of Theorems 1.1, 1.3, 1.7, 1.8, 1.10, 1.12 and 1.13. Subsequently, in Section 4 we prove Theorem 1.11, which constitutes the main technical contribution of the paper. Finally, in Section 4.4 we establish Theorem 1.2.
2. PRELIMINARIES 2.1. Measure theory. Throughout the paper we continue to denote by λ the Lebesgue measure on the Euclidean space R k ; the reference to k will always be clear from the context. For the convenience of the reader we collect a few basic facts from measure theory that we will need. The first lemma follows from the Isomorphism Theorem, see e.g. [ The following is known as the Riesz-Markov-Kakutani representation theorem [18].

Lemma 2.4.
Suppose that E is a compact separable metric space and that ϕ : Suppose that (E , D) is a complete separable metric space. Then so is the space P (E ) of probability measures on E equipped with the Wasserstein metric with Γ(X , Y ) denoting the set of all couplings of X , Y . We will frequently be working with the Wasserstein metric D ⊠ ( · , · ) induced by the cut metric on L or K.

Variations on the cut metric.
When we defined the cut metric D ⊠ (µ, ν) in (1.2) we allowed for a coupling of µ, ν as well as a 'coordinate permutation' ϕ ∈ S. Sometimes the latter is not desirable. Therefore, for µ, ν ∈ L we define the strong cut distance as with S, X ranging over measurable sets. It is easily verified that D ( · , · ) is a pre-metric on L . Analogously, for µ, ν ∈ P (Ω n ) let Similarly, we will be led to consider several variants of the kernel cut metric from (1.3). Specifically, let K R = K R (Ω) be the set of all maps κ, κ ′ : [0, 1] 2 → R Ω such that the functions (s, x) ∈ [0, 1] 2 → κ s,x (ω) belong to L 1 ([0, 1] 2 , R) for all ω ∈ Ω, up to equality almost everywhere. Then for κ, κ ′ ∈ K R we define Thus, D ⊠ ( · , · ) is the natural extension of (1.3) to K R , D ( · , · ) is the kernel version of (2.2), D ( · , · ) represents the strongest variant of the cut metric that does not allow for any measure-preserving transformations, and D ■ ( · , · ) is the graphon cut metric as studied in [25]. We also recall the graphon cut (pre-)metric for L 1 -functions κ, κ ′ : [0, 1] 2 → R from [24], which is defined as The different variants of the cut metric are related as follows. For a measurable map ϕ : [0, 1] → [0, 1] and κ ∈ K R define κ ϕ , κ ϕ ∈ K R by letting κ ϕ s,x = κ s,ϕ(x) and κ ϕ s,x = κ ϕ(s),x , respectively. Then As a consequence, for all κ, κ ′ ∈ K R we have For a function W : (s, x) → W s,x defined on [0, 1] 2 we define the transpose W † : (s, x) → W x,s . We call W symmetric if W = W † . For κ ∈ K R we define a family (κ (ω) ) ω∈Ω of symmetric functions defined by We can interpret κ (ω) s,x as the edge weight in a bipartite graph with vertex set [0, 1].
Remark 2.6. The cut metric from the theory of graph limits D ■ (·, ·) can be bounded from above by the present definition D ⊠ (·, ·) as can be seen in (2.5). Strictly speaking, in the case Ω = {0, 1} we can turn kernels κ, κ ′ ∈ K into 'bipartite graphons' via (2.6) and find directly The converse bound does not hold for any constant as can be seen as follows. Let κ s,x = 1 {s < 1/2} and κ ′ s,x = κ x,s . By choosing the measure preserving map ϕ(x) = 1 − x, we get But as κ ′ represents the law ν supported only on δ σ with σ x = 1 {x ≤ 1/2}, whilst κ ′ is the uniform distribution over the two configurations σ 1 = 1 and σ 0 = 0, we can bound D ⊠ (κ, Then · ✷ is a norm on L 1 ([0, 1] 2 , R). Analogously, for a matrix A ∈ R n×n we define We need the following 'sampling lemma' for the cut norm.
2.4. Regularity. For a kernel κ ∈ K R and partitions S = (S 1 , . . . , S k ), X = (X 1 , . . . , X ℓ ) of the unit interval into pairwise disjoint measurable subsets define κ S,X ∈ K by In words, κ S,X s,x is the conditional expectation of κ s,x given the σ-algebra generated by the rectangles S i × X j . If the two partitions S, X are identical, we write κ S instead of κ S,X . We use similar notation for maps κ : [0, 1] 2 → R. The following fact is a kernel variant of the well-known Frieze-Kannan regularity lemma. This notion of regularity is robust with respect to refining the partition. Applying Lemma 2.9 to the step function κ R for a partition R that refines a partition S of [0, 1], we obtain to following corollary.

FUNDAMENTALS
This section contains the proofs of the basic facts, namely the compactness of the space of Ω-laws (Theorem 1.1), the isometric property of the kernel representation (Theorem 1.3), the sampling theorem (Theorem 1.8), the comparison of the discrete and the continuous cut metric (Theorem 1.2), the continuity statements from Theorems 1.12 and 1.13 and the connection to exchangeable arrays (Theorem 1.7). We begin with the proof of Theorem 1.3.  Proof. Fix ω ∈ Ω and ϕ ∈ S. The construction of κ f , κ g guarantees that with s ∈ [0, 1] chosen uniformly at random, the distribution γ of the pair (κ f s , κ g ϕ(s) ) ∈ S × S is a coupling of µ f , µ g . We now claim that whence (3.1) follows. Finally, since (3.1) holds for all ϕ, ω, we conclude that D (µ f , µ g ) ≤ D (κ f , κ g ).
The following lemma establishes the converse of Lemma 3.1 for functions that take only finitely many values.
. Then Consequently, any coupling γ of µ f , µ g induces a coupling g ∈ P ( Then for any i , j there exists a bijection ϕ i,j : V i,j → W i,j such that both ϕ i,j and ϕ −1 i,j are measurable and preserve the Lebesgue measure. Piecing these maps together, we obtain the bijection Both ϕ and ϕ −1 are measurable and preserve the Lebesgue measure, i.e., ϕ ∈ S. Moreover, for any sets S, X ⊂ [0, 1] and any ω ∈ Ω we have Since (3.3) holds for all S, X , ω, γ, the assertion follows. Finally, the assertion follows from (3.4), (3.6), (3.7) and the triangle inequality.

Corollary 3.4. For all κ, κ
Proof. This is an immediate consequence of Lemma 3.1 and Corollary 3.3.

Proof of Theorem 1.3. Corollary 3.4 and (2.4)
show that the map K → L, κ → µ κ is an isometry. Moreover, Lemma 2.1 implies that this map is surjective. Thus, because K,L are metric spaces, κ → µ κ is an isometric bijection.

Proof of Theorem 1.8.
We begin by extending Lemma 2.8 to (not necessarily symmetric) kernels κ ∈ K .
Now, for any ω, I , J the random variable i∈I j ∈J X i,j ,ω is a sum of |I × J | independent Bernoulli variables. Therefore, Azuma's inequality yields Since (3.13) holds for any specific I , J , ω, the assertion follows from the union bound and (3.12). 13 Proof of Theorem 1.8. Lemma 3.5 yields partitions X = (X 1 , . . . , X ℓ ), S = (S 1 , . . . , S ℓ ) of [0, 1] with ℓ ≤ n 1/4 such that (3.14) Applying Lemma 3.6 to κ and κ S,X , we obtain In addition, we claim that To see this, let Since N h , M h are binomial variables, the Chernoff bound shows that with probability Providing that the bounds (3.17) hold, we can construct ϕ, ψ ∈ S such that for all h ∈ [n], whence (3.16) follows. Finally, the assertion follows from (3.14), (3.15) and (3.16) and Theorem 1.3.

Proof of Theorem1.1.
We begin by proving that the space K is complete with respect to D ( · , · ), the strongest version of the cut metric.
Lemma 3.8. The space K equipped with the D ( · , · ) metric is complete.
Corollary 3.9. The space K equipped with the D ( · , · ) metric is complete.
Proof. We adapt a well know proof that a quotient of a Banach space with respect to a linear subspace is complete [7,Theorem 1.12.14]. Thus, suppose that (κ n ) n is a D ( · , · )-Cauchy sequence. There exists a subsequence (κ n ℓ ) ℓ such that D (κ n ℓ , κ n ℓ+1 ) < 2 −ℓ for all ℓ. Hence, passing to this subsequence, we may assume that (κ n ) n satisfies D (κ n , κ n+1 ) < 2 −n for all n. (3.22) We are now going to construct a sequence (k n ) n of maps [0, 1] 2 → P (Ω) such that D (κ n , k n ) = 0 for all n and D (k n , k n+1 ) < 2 −n for all n. (3.23) We let k 1 be any kernel such that D (k 1 , κ 1 ) = 0 and proceed by induction. Having constructed k 1 , . . . , k n already, we observe that the definition of D ( · , · ) ensures that Therefore, (3.22) implies that there is k n+1 : [0, 1] 2 → P (Ω) with D (κ n 1 , k) = 0 such that D (k n , k n+1 ) < 2 −n . Thus, we obtain a sequence (k n ) n satisfying (3.23). Finally, any sequence (k n ) n that satisfies (3.23) is D ( · , · )-Cauchy. Therefore, Lemma 3.8 shows that (k n ) n has a limit k. Since D (k n , κ n ) = 0, we conclude that lim n→∞ D (κ n , k) = 0, i.e., (κ n ) n converges to k. Proof. To establish the completeness of K we repeat the same argument as in the proof of Corollary 3.9. The completeness of L then follows from Theorem 1.3. Moreover, Theorem 3.5 shows that the set of laws with finite support is dense in L. Since S is separable (being a subset of a separable Hilbert space), we conclude that L is separable. Hence, Theorem 1.3 shows that the same is true of K.
We denote by P (L) the space of probability distributions on the Polish space L, endowed with the topology of weak convergence. As we saw in Section 2.1, this topology is metrised by the Wasserstein metric We begin by proving that P (L) is compact. To this end we will construct a continuous map from another compact space onto P (L). Specifically, recall that Ω N×N is a compact Polish space with respect to the product topology. The space P (Ω N×N ) equipped with the weak topology is therefore compact as well. Further, the space X ⊂ P (Ω N×N ) of exchangeable distributions is closed with respect to the weak topology, and therefore compact.
To construct a continuous map X → P (L), ξ → ρ ξ we are going to take a pointwise limit of maps X → P (L), ξ → ρ ξ,n . Given ξ ∈ X and n ≥ 1 we define ρ ξ,n as follows. Draw X ξ = (X ξ i,j ) i,j ≥1 ∈ Ω N×N from ξ. Then define a probability distribution on Ω n by letting (3.24) Thus, µ ξ,n * is the empirical distribution of the rows of the top-left n × n minor of X ξ . Finally, let µ ξ,n =μ ξ,n * ∈ L be the law induced by this discrete distribution and let ρ ξ,n ∈ P (L) be the distribution of µ ξ,n (with respect to the choice of X ξ ).
Proof. Since P (L) is complete, to establish the existence of the limit we just need to prove that the sequence (ρ ξ,n ) n is Cauchy. Thus, let ξ ∈ X, ε > 0, pick a large n = n(ε) > 0 and suppose that N > n. We aim to prove that D ⊠ (ρ ξ,n , ρ ξ,N ) < ε. (3.25) To this end, we couple ρ ξ,n , ρ ξ,N by drawing X ξ ∈ Ω N×N from ξ and letting g be the distribution of the pair (µ ξ,n , µ ξ,N ). By definition of the Wasserstein metric, to establish (3.25) it suffices to show that for n = n(ε) large enough, But (3.26) follows from Theorem 1.8. Indeed, the construction (3.24) ensures that µ ξ,n is the empirical distribution of rows of the upper left n×n-block of X ξ , while µ ξ,N is the empirical distribution of the rows of the N ×N -upper left block. Due to the exchangeability of ξ, the distribution of the upper left n × n-block is identical to the distribution 15 of a random n × n-minor of the matrix X ξ . Therefore, in the notation of Theorem 1.8 we have µ ξ,n d = µ ξ,N n,n , whence we obtain (3.26) and thus (3.25). Hence, the limit ρ ξ = lim n→∞ ρ ξ,n exists for all ξ.
As a next step we are going to embed the space L into X.
Corollary 3.14. The space L is compact.
Proof. The space X is compact as it is the space of probability measures on the compact Polish space Ω N×N . Since Lemma 3.11 and Corollary 3.13 render a continuous surjective map X → P (L) and a continuous image of a compact space is compact, the space P (L) is compact. To finally conclude that L is compact as well, consider a sequence (µ n ) n≥1 in L. Because P (L) is compact, the sequence (δ µ n ) n≥1 possesses a convergent subsequence (n ℓ ) ℓ≥1 . Let π be the limit of that subsequence. Consider a point ν in the support of π and let (U k ) k≥0 be a sequence of open neighbourhoods of ν such that k≥1 U k = {ν}. By Urysohn's lemma there are continuous functions f k : L → [0, 1] such that f k takes the value one on U k and the value 0 outside U k−1 . Now, for all k ≥ 1 we have Hence, µ n ℓ ∈ U k−1 for almost all ℓ. Consequently, ν = lim ℓ→∞ µ n ℓ . Thus, the metric space L is sequentially compact and therefore compact.
3.4. Proof of Proposition 1.10. Let µ, ν ∈ L . Toward the proof of (1.7) let Since µ, ν are atoms concentrated on the pure state (1.6), respectively, we obtain 16 whence (1.7) is immediate. Moreover, the first part of (1.8) follows from (3.28), while the second part is immediate from the triangle inequality.
3.6. Proof of Theorem 1.7. The product topology on Ω N×N is the weakest topology under which all the functions are continuous. Equivalently, the product topology is induced by the metric Hence, the weak topology on X ⊂ P (Ω N×N ) is induced by the corresponding Wasserstein metric D max ( · , · ).
In order to show that π → Ξ π is surjective, let Ξ ∈ X and let X ∈ Ω N×N be a random array with distribution Ξ.
Further, let κ X n ∈ K be the kernel representing the discrete probability distribution Moreover, let π n ∈ P (K) be the distribution of κ X n (with respect to the choice of X , naturally). Because K is a compact separable space, so is P (K). Consequently, (π n ) n has a subsequence that converges to some π ∈ P (K).
Passing to a subsequence, we may assume that π = lim n→∞ π n . We now claim that Ξ = Ξ π . Indeed, by continuity it suffices to show that lim n→∞ D max (Ξ, Ξ π n ) = 0. To see this, let ε > 0, choose a large enough integer N = N (ε) > 0 and an even larger n = n(N ). Recall that κ N is the kernel obtained from κ via sampling. Then by exchangeability and the birthday paradox, we have provided that n/N is large enough, as the difference in the distributions of X N and (κ X n ) N behaves like the difference in distribution between sampling N items with and without replacement out of a set of n items. Consequently, the definition (3.30) of the metric shows that with κ n chosen from π n , D max (Ξ, Ξ π n ) = D max (X , X κ n ) < 2ε, Thus, we know that P (K) → X, π → Ξ π is a continuous bijection. Finally, since P (K) is compact and the continuous image of a compact set is compact, the map π → Ξ π is open and thus a homeomorphism.  Proof of Theorem 1.9. Let G be a graph given by the previous theorem and let κ G be the corresponding graphon. Denote by κ a kernel consisting of κ G and its transposed graphon given by (2.6) in the special case Ω = {0, 1}. Denote by µ = µ(G) ∈ L the corresponding law given by Theorem 1.3. Assume there is ν ∈ L with support of size less then l = exp Θ(ε −2 ) and D ⊠ (µ, ν) < ε 2 . Then ν induces a partition K of [0, 1] into at most l parts s.t. D ⊠ (κ, κ ν ) = D ⊠ (κ, κ K ) ≤ ε 2 which implies that there is a partition S and a graphon κ S s.t. D ■ (κ G , κ S ) ≤ ε. As κ G and κ S are by definition embeddings of (finite) graphs into the space of graphons, this is a contradiction to Theorem 3.17.

THE PINNING OPERATION
In this section we prove Theorem 1.11. We begin by investigating a discrete version of the pinning operation, which played a key role in recent work on random factor graphs [8]. The discrete version of the pinning theorem, Theorem 4.1 below, was already established as [8,Lemma 3.5]. In Section 4.1 we give a shorter proof, based on an argument form [36]. Moreover, in Section 4.2 we show by a somewhat delicate argument that the pinning operation is continuous with respect to the cut metric. Finally, in Section 4.3 we complete the proof of Theorem 1.11. 4.1. Discrete pinning. For a probability measure µ ∈ L n and a set I ⊂ [n] we denote by µ I the joint distribution of the coordinates i ∈ I . Thus, µ I is the probability distribution on Ω I defined by Where I = {i 1 , . . . , i t } is given explicitly, we use the shorthand µ I = µ i 1 ,...,i t . Apart from [8,Lemma 3.5], statements related to Theorem 4.1 were previously obtained by Montanari [32] and Raghavendra and Tan [36]. To be precise, [32, Theorem 2.2] deals with the special case of the discrete pinning operation for graphical channels and the number θ of pinned coordinates scales linearly with the dimension n. The original proof of Theorem 4.1 in [8] was based on a generalisation of Montanari's argument. Moreover, [36,Lemma 4.5] asserted the existence of T = T (µ, ε) > 0 such that rather than showing that a random θ does the trick. But at second glance the proof given in [36], which is significantly simpler than the one from [8], actually implies Theorem 4.1.
For completeness we include the short proof of Theorem 4.1 via the argument from [36]. We need a few concepts from information theory. Let X , Y , Z be random variables that take values in finite domains. We recall that the conditional mutual information of X , Y given Z is defined as with the conventions 0log 0 = 0, 0log 0 0 = 0 and with the sum ranging over all possible values x, y, z of X , Y , Z , respectively. Moreover, the conditional entropy of X given Y reads We also recall the basic identity Finally, Pinsker's inequality provides that for any two probability distribution µ, ν on a finite set X , signifies the Kullback-Leibler divergence. The proof of the following lemma is essentially identical to the proof of [36,Lemma 4.5].

Lemma 4.2.
Let µ ∈ P (Ω n ) and let σ ∈ Ω n be a sample drawn from µ. Let i , i ′ , i 1 , . . . ∈ [n] be uniformly distributed and mutually independent as well as independent of σ. Then for any integer T we have Proof. Due to (4.3), for every θ ≥ 0, Summing on θ = 1, . . . , T , we obtain The desired bound follows because H (σ i ) ≤ log q and H (σ i | σ i 1 , . . . , σ i T +1 ) ≥ 0. Now let let T > 0 be an integer and draw 0 ≤ θ ≤ T uniformly at random and constructμ as in Theorem 4.1. Then as an immediate consequence of Lemma 4.2 we obtain the following bound, where, of course, the expectation refers to the choice ofμ and the independently chosen and uniform i , i ′ .

Continuity.
Recall that for a given µ ∈ L the pinned µ ↓n ∈ L is random. Thus, for the pinned laws we consider the D ⊠ -Wasserstein metric. The aim in this paragraph is to establish the following key statement.
Lemma 4.6. For any n ≥ 1, ε > 0 there is δ > 0 such that for all κ ∈ K and all κ ′ ∈ K 1 with D 1 (κ, κ ′ ) < δ we have Toward the proof of Lemma 4.6 we require the following statement.