Arrow Contraction and Expansion in Tropical Diagrams Authors: Rostislav Matveev, Jacobus W Portegies, Daniel Chicharro Published: 2023 ABSTRACT AbstractArrow contraction applied to a tropical diagram of probability spaces is a modification of the diagram, replacing one of the morphisms with an isomorphism while preserving other parts of the diagram. It is related to the rate regions introduced by Ahlswede and Körner. In a companion article, we use arrow contraction to derive information about the shape of the entropic cone. Arrow expansion is the inverse operation to the arrow contraction.Keywords: tropical probability, entropic cone 1. Introduction In [1], we have initiated the theory of tropical probability spaces for the systematic study of information optimization problems in information theory and artificial intelligence, such as those arising in robotics [2], neuroscience [3], artificial intelligence [4], variational autoencoders [5], information decomposition [6], and causal inference [7]. In [8], we applied the techniques to derive a dimension-reduction result for the entropic cone of four random variables. Two of the main tools used for the latter are what we call arrow contraction and arrow expansion. They are formulated for tropical commutative diagrams of probability spaces. Tropical diagrams are points in the asymptotic cone of the metric space of commutative diagrams of probability spaces endowed with the asymptotic entropy distance. Arrows in diagrams of probability spaces are (equivalence classes of) measure-preserving maps. Arrow contraction and expansion take a commutative diagram of probability spaces as input, modify it, but preserve important properties of the diagram. The precise results are formulated as Theorems 3 and 4 in the main text. Their formulation requires language, notation, and definitions that we review in Section 2. However, to give an idea of the results in this paper, we now present two examples. For basic terminology and notations used in these examples below, the reader unfamiliar with them is referred either to Section 2 of the present article or in the introductory material in the article [9]. 1.1. Two Examples 1.1.1. Arrow Contraction and Expansion in a Two-Fan Suppose we are given a fan Z=(X←Z→Y), and we would like to complete it to a diamond such that the entropy of V, denoted by [V], equals the mutual information [X:Y] between X and Y, i.e., we would like to realize the mutual information between X and Y by a pair of reductions X→V and Y→V. This is not always possible, not even approximately. The Gacs-Körner Theorem [10] describes when such exact realization of mutual information is possible. Arrow contraction instead produces another fan Z′=(X←Z′→V), such that the reduction Z′→X is an isomorphism and the relative entropy [X|V] of X given V equals [X|Y]. By collapsing this reduction, we obtain as a diagram just the reduction X→V. If necessary, we can keep the original spaces Z and Y in the modified diagram obtaining the “broken diamond” diagram such that [V]=[X:Y]. Of course, no special technique is necessary to achieve this result since it is easy to find a reduction from a tropical space [X] to another tropical probability space with the prespecified entropy, as long as the Shannon inequalities are not violated. However, a similar operation becomes non-trivial and in fact impossible without passing to the tropical limit, if instead of a single space X, there is a more complex sub-diagram as in the example in the next subsection. To explain how arrow expansion works, we start with the chain of reductions Z→X→V. Can we extend it to a diamond, as in (1), so that [X:Y|V]=0? This is again not possible, in general. However, if we pass to tropical diagrams, then such an extension always exists. 1.1.2. One More Example of Arrow Expansion and Contraction Consider a diagram presented in Figure 1. Such a diagram is called a Λ3-diagram. We would like to find a reduction X→V so that [X|U]=[X|V]. It is not possible to achieve this within the realm of diagrams of classical probability spaces. But once we pass to the tropical limit, the reduction [X]→[V] can be found by contracting and then collapsing the arrow [Z]→[X], as shown in Figure 1. Arrow contraction and expansion in a Λ3-diagram. The fan ([X]←[Z]→[U]) (shown in red in the Figure) is admissible. Spaces [Z1], [Z2] and [Z] belong to the co-ideal U. After the operation the part of the diagram shown in blue in the Figure is left unmodified. Arrow contraction is closely related to the Shannon channel coding theorem. This is perhaps most obvious from the proof. Furthermore, arrow contraction has connections with rate regions, as introduced by Ahlswede and Körner, see [11,12]. These results by Ahlswede and Körner were applied by [13], resulting in a new non-Shannon information inequality. Moreover, in [13], a new proof was given of the results; this new proof is similar to the proof of the arrow contraction result in the present paper. The main contribution of our work lies in the fact that we prove a much stronger preservation of properties of the diagram under arrow contraction. 2. Preliminaries 2.1. Probability Spaces and Their Diagrams Our main objects of study will be commutative diagrams of probability spaces. A finite probability space X is a set with a probability measure on it, supported on a finite set. We denote by |X| the cardinality of the support of the measure. The statement x∈X means that point x is an atom with positive weight in X. For details see [1,9,14]. Examples of commutative diagrams of probability spaces are shown in Figure 2. The objects in such diagrams are finite probability spaces and morphisms are equivalence classes of measure-preserving maps. Two such maps are considered to be equivalent if they coincide on a set of full measurements. To record the combinatorial structure of a commutative diagram, i.e., the arrangement of spaces and morphisms, we use indexing categories, which are finite poset categories satisfying an additional property, which we describe below. Examples of diagrams of probability spaces. 2.1.1. Indexing Categories A poset category is a finite category such that there is at most one morphism between any two objects either way. For a pair of objects k,l in a poset category G=i;γij, such that there is a morphism γkl in G, we call k an ancestor of l and l a descendant of k. The set of all ancestors of an object k together with all the morphisms between them is itself a poset category and will be called a co-ideal generated by k and denoted by k. Co-ideals are also sometimes called filters. Similarly, a poset category consisting of all descendants of k∈G and morphisms between them will be called an ideal generated by k and denoted k. An indexing category G=i;γij used for indexing diagrams is a poset category satisfying the following additional property: for any pair of objects i1,i2∈G the the intersection of co-ideals is also a co-ideal generated by some object i3∈G, In other words, for any pair of objects i1,i2∈G there exists a least common ancestor i3, i.e., i3 is an ancestor to both i1 and i2 and any other common ancestor is also an ancestor of i3. Any indexing category is initial, i.e., there is a (necessarily unique) initial object ı^ in it, which is the ancestor of any other object in G, in other words G=ı^. A fan in a category is a pair of morphisms with the same domain. Such a diagram is also called a span in some literature on Category Theory. A fan (i←k→j) is called minimal, if for any other fan (i←l→j) included in a commutative diagram the vertical morphism (k→l) must be an isomorphism. Any indexing category also satisfies the property that, for any pair of objects in it, there exists a unique minimal fan with target objects of the given ones. This terminology will also be applied to diagrams of probability spaces indexed by G. Thus, given a space X in a G-diagram, we can talk about its ancestors, descendants, co-ideal X, and ideal X. We use square brackets to denote tropical diagrams and spaces in them. For the (co-)ideals in tropical diagrams, in order to unclutter notations, we will write 2.1.2. Diagrams For an indexing category G=i;γij and a category Cat, a commutative G-diagram X=Xi;χij is a functor X:G→Cat. A diagram X is called minimal if it maps minimal fans in G to minimal fans in Cat. A constant G-diagram denoted XG is a diagram where all the objects equal to X, and all morphisms are identities. Important examples of indexing categories are a two-fan, a diamond category, a full category Λn on n spaces, chains Cn. For detailed descriptions and more examples, the reader is referred to the articles cited at the beginning of this section. 2.2. Tropical Diagrams 2.2.1. Intrinsic Entropy Distance For a fixed indexing category G, the space of commutative G-diagrams will be denoted by ProbG. Evaluating entropy on every space in a G diagram gives a map where the target space RG is the space of real-valued functions on objects of G. We endow this space with the ℓ1-norm. For a fan F=(X←Z→Y) of G-diagrams we define the entropy distance between its terminal objects by and the intrinsic entropy distance between two arbitrary G-diagrams by This intrinsic version of the entropy distance was introduced in [15,16]. The triangle inequality for k and various other properties are discussed in [1]. In the same article, a useful estimate for the intrinsic entropy distance called the Slicing Lemma is also proven. The following corollary ([1], Corollary 3.10(1)) of the Slicing Lemma will be used in the next section. Let G be an indexing category, X,Y∈ProbG and U∈Prob included in a pair of two fans Then 2.2.2. Tropical Diagrams Points in the asymptotic cone of (ProbG,k) are called tropical G-diagrams and the space of all tropical G-diagrams, denoted Prob[G], is endowed with the asymptotic entropy distance. We explain this now in more detail, and a more extensive description can be found in [14]. To describe points in Prob[G] we consider quasi-linear sequences X¯:=(X(n):n∈N) of G-diagrams. That is, we fix a “slowly growing” increasing function φ:R≥0→R satisfying for some constant Dφ>0 and any t>1. We call a sequence X¯:=(X(n):n∈N) φ-quasi-linear if it satisfies the bound for all m,n∈N We have shown in [14] that the space Prob[G] does not depend on the choice of function φ as long as it is not zero. The space of all such sequences is endowed with the asymptotic entropy distance defined by A tropical diagram [X] is defined to be an equivalence class of such sequences, where two sequences X¯ and Y¯ are equivalent if κ(X¯,Y¯)=0. The space Prob[G] carries the asymptotic entropy distance and has the structure of a R≥0-semi-module—one can take linear combinations with non-negative coefficients of tropical diagrams. The linear entropy functional Ent*:Prob[G]→RG is defined by A detailed discussion about tropical diagrams can be found in [14]. In the cited article, we show that the space Prob[G] is metrically complete and isometrically isomorphic to a closed convex cone in some Banach space. For G=Ck a chain category, containing k objects 1,…,k and unique morphism i→j for every pair i≥j, we have shown in [14] that the space Prob[Ck] is isomorphic to the following cone in (Rk,·1) The isomorphism is given by the entropy function. Thus, we can identify tropical probability spaces (elements in Prob[C1]) with non-negative numbers via entropy. We will simply write [X] to mean the entropy of the space [X]. Along these lines, we also adopt the notations [X|Y], [X:Y] and [X:Y|Z] for the conditional entropy and mutual information for the tropical spaces included in some diagrams. 2.3. Asymptotic Equipartition Property for Diagrams 2.3.1. Homogeneous Diagrams A G-diagram X is called homogeneous if the automorphism group Aut(X) acts transitively on every space in X. Homogeneous probability spaces are uniform. For more complex indexing categories, this simple description is not sufficient. 2.3.2. Tropical Homogeneous Diagrams The subcategory of all homogeneous G-diagrams will be denoted ProbGh and we write ProbGh,m for the category of minimal homogeneous G-diagrams. These spaces are invariant under the tensor product. Thus, they are metric Abelian monoids. Passing to the tropical limit, we obtain spaces of tropical (minimal) homogeneous diagrams that we denote Prob[G]h and Prob[G]h,m. 2.3.3. Asymptotic Equipartition Property In [1] the following theorem is proven Suppose X∈ProbG is a G-diagram of probability spaces for some fixed indexing category G. Then, there exists a sequence H¯=(Hn)n=0∞ of homogeneous G-diagrams such that where C(|X0|,[[G]]) is a constant only depending on |X0| and [[G]]. The approximating sequence of homogeneous diagrams is evidently quasi-linear with the defect bounded by the admissible function Thus, Theorem 1 above states that L(ProbG)⊂Prob[G]h. On the other hand, we have shown in [14] that the space of linear sequences L(ProbG) is dense in Prob[G]. Combining the two statements, we obtain the following theorem. For any indexing category G, the space Prob[G]h is dense in Prob[G]. Similarly, the space Prob[G]h,m is dense in Prob[G]m. It is possible that the spaces Prob[G]h and Prob[G] coincide. At this time, we have neither a proof nor a counterexample to this conjecture. 2.4. Conditioning in Tropical Diagrams For a tropical G-diagram [X] containing a space [U] we defined a conditioned diagram [X|U]. It can be understood as the tropical limit of the sequence (X(n)|un), where (X(n)) is the homogeneous approximation of [X], U(n) is the space in X(n) that corresponds to [U] under combinatorial isomorphism and un is any atom in U(n). We have shown in [9] that operation of conditioning is Lipschitz-continuous with respect to the asymptotic entropy distance. 3. Arrow Contraction 3.1. Arrow Collapse, Arrow Contraction, and Arrow Expansion 3.1.1. Prime Morphisms A morphism γij:i→j in an indexing category G=i;γij will be called prime if it cannot be factored into a composition of two non-identity morphisms in G. A morphism in a G-diagram indexed by a prime morphism in G will also be called prime. 3.1.2. Arrow Collapse Suppose Z is a G-diagram such that for some pair i,j∈G, the prime morphism ζij:Zi→Zj is an isomorphism. Arrow collapse applied to Z results in a new diagram Z′ obtained from Z by identifying Zi and Zj via the isomorphism ζij. The combinatorial type of Z′ is different from that of Z. The spaces Zi and Zj are replaced by a single space, and the new space will inherit all the morphisms in Z with targets and domains Zi and Zj. 3.1.3. Arrow Contraction and Expansion Arrow contraction and expansion are two operations on tropical G-diagrams. Roughly speaking, arrow contraction applied to a tropical G-diagram [Z] results in another tropical G-diagram [Z′] such that one of the arrows becomes an isomorphism, while some parts of the diagram are not modified. Arrow expansion is an inverse operation to arrow contraction. 3.1.4. Admissible and Reduced Sub-Fans An admissible fan in a G-diagram Z is a minimal fan X←Z→U, such that Z is the initial space of Z and any space in Z belongs either to the co-ideal X or ideal U. For example, in the left-most diagram of Figure 1, the fan X←Z→U is admissible, while X1←Z1→U or X←Z→Z2 are not. An admissible fan X←Z→U in a diagram will be called reduced if the morphism Z→X is an isomorphism. 3.2. The Contraction Theorem Our aim is to prove the following theorem. Let ([X]←[Z]→[U]) be an admissible fan in some tropical G-diagram [Z]. Then for every ε>0 there exists a G-diagram [Z′] containing an admissible fan ([X′]←[Z′]→[U′]), corresponding to the original admissible fan through the combinatorial isomorphism, such that, with the notations X=X and X′=X′, the diagram [Z′] satisfies (i) κ([X′|U′],[X|U])≤ε κ([X′|U′],[X|U])≤ε (ii) κ(X′,X)≤ε κ(X′,X)≤ε (iii) [Z′|X′]≤ε [Z′|X′]≤ε It is not clear that constructing diagrams Z′ as in the theorem above for a sequence of values of parameter ε decreasing to 0, we can obtain a convergent sequence in Prob[G] with the limiting diagram satisfying conclusions of the theorem with ε=0. If Prob[G] were a locally compact space, which is an open question at the moment. The convergence would be guaranteed, and then ε in the theorem above could be replaced by 0. The proof of Theorem 3 is based on the following proposition, which will be proven in Section 5. Let (X0←Z0→U) be an admissible fan in some homogeneous G-diagram of probability spaces Z. Then there exists a G-diagram Z′ containing the admissible fan (X0′←Z0′→U′) such that, with the notations X:=X0 and X′:=X0′, it holds that (1) X|u=X′|u′ for any u∈U and u′∈U′. X|u=X′|u′ for any u∈U and u′∈U′. (2) κ(X,X′)≤k(X,X′)≤20·[[G]] κ(X,X′)≤k(X,X′)≤20·[[G]] (3) [Z0′|X0′]≤4lnln|X0| [Z0′|X0′]≤4lnln|X0| First, we assume that [Z] is a homogeneous tropical diagram. It means that it can be represented by a quasi-linear sequence (Z(n))n∈N0 of homogeneous diagrams, with defect of the sequence bounded by the function φ(t):=C·t3/4 for some C≥0. This means that for any m,n∈N where Dφ is some constant depending on φ, see [14]. Fix a number n∈N and apply Proposition 2 to the homogeneous diagram Z(n), containing the admissible fan X0(n)←Z0(n)→U(n) and sub-diagram X(n)=X0(n). As a result, we obtain a diagram Z″ containing the fan X0″←Z0″→U″ and the sub-diagram X″=X0″, such that Recall that for a diagram A of probability spaces, we denote by A→ the tropical diagram represented by the linear sequence (Ak:k∈N0). As an element of a closed convex cone Prob[G], it can be scaled by an arbitrary non-negative real number; see, for instance, Section 2.3.5 in [14]. For example, 1nA→ is represented by the sequence (Akn:k∈N0). Define the two tropical diagrams Since X″|u″ does not depend on u″ and X(n)|u does not depend on u we have [X′|U′]=(1/n)·(X″|u″)→ and [X˜|U˜]=(1/n)·(X(n)|u)→. From (3), we obtain The distance between [Z˜] and [Z] can be bounded as follows This also implies Since conditioning is a Lipschitz-continuous operation with Lipschitz constant 2, we also have Combining the estimates in (4)–(7) we obtain Please note that |X0(n)| grows at most exponentially (it is bounded by en([X0]+C) for some C) and φ is a strictly sub-linear function. Thus, by choosing sufficiently large n depending on the given ε>0, we obtain [Z′], satisfying conclusions of the theorem for homogeneous [Z]. To prove the theorem in full generality, observe that all the quantities on the right-hand side of the inequalities are Lipschitz-continuous. Since Prob[G]h is dense in Prob[G] the theorem extends to any [Z] by first approximating it with any precision by a homogeneous configuration and applying the argument above. □ 3.3. The Expansion Theorem The following theorem is complementary to Theorem 3. The expansion applied to a diagram containing a reduced admissible fan produces a diagram with an admissible fan, such that the contraction of it is the original diagram. Thus, arrow expansion is a right inverse of the arrow contraction operation. In general, contraction erases some information stored in the diagram, so there are many right inverses. We prove the theorem below by providing a simple construction of one such right inverse. Let ([X]←[Z′]→[U′]) be a reduced admissible fan in some tropical G-diagram [Z′] and λ>0. Let [X]:=X. Then there exists a G-diagram [Z] containing the copy of [X], such that the corresponding admissible fan ([X]←[Z]→[U]) has [Z|X]=λ and [X|U]=[X|U′]. Let [W] be a tropical probability space with entropy equal to λ. For any reduction of tropical spaces [A]→[B], there are natural reductions We construct the diagram [Z] by replacing every space [V] in the ideal U′ with [U]+[W]. Every morphism [V1]→[V2] within U′ is replaced by And any morphism from [V] in U′ to a space [Y] in X is replaced by a composition Clearly, the resulting diagram satisfies the conclusion of the theorem. □ The rest of the article is devoted to the development of the necessary tools and the proof of Proposition 2. 4. Local Estimate In this section, we derive a bound, very similar to Fano’s inequality, on the intrinsic entropic distance between two diagrams of probability spaces with the same underlying diagram of sets. The bound will be in terms of the total variation distance between two distributions corresponding to the diagrams of probability spaces. It will be used in the next section to prove Proposition 2. 4.1. Distributions 4.1.1. Distributions on Sets For a finite set S we denote by ΔS the collection of all probability distributions on S and by ∥π1−π2∥1 we denote the total variation distance between π1,π2∈ΔS. 4.1.2. Distributions on Diagrams of Sets Let Set denote the category of finite sets and surjective maps. For an indexing category G, we denote by SetG the category of G-diagrams in Set. That is, objects in SetG are commutative diagrams of sets indexed by the category G, the spaces in such a diagram are finite sets, and arrows represent surjective maps, subject to commutativity relations. For a diagram of sets S=Si;σij we define the space of distributions on the diagram S by where f*:ΔS→ΔS′ is the affine map induced by a surjective map f:S→S′. If S0 is the initial space of S, then there is an isomorphism Using the isomorphism (8) we define total variation distance between two distributions π,π′∈ΔS as Given a G-diagram of sets S=Si;σij and an element π∈ΔS we can construct a G-diagram of probability spaces (S,π):=(Si,πi);σij. Below, we give the estimate of the entropy distance between two G-diagrams of probability spaces (S,π) and (S,π′) in terms of the total variation distance π−π′ between distributions. 4.2. The Estimate The upper bound on the entropy distance, which we derive below, has two summands. One is linear in the total variation distance with the slope proportional to the log-cardinality of S0. The second one is super-linear in the total variation distance, but it does not depend on S. So, we have the following interesting observation: of course, the super-linear summand always dominates the linear one locally. However, as the cardinality of S becomes large, it is the linear summand that starts playing the main role. This will be the case when we apply the bound in the next section. For α∈[0,1] consider a binary probability space with the weight of one of the atoms equal to α For an indexing category G, consider a G-diagram of sets S=Si,σij∈SetG. Let π,π′∈ΔS be two probability distributions on S. Denote X:=(S,π), Y:=(S,π′) and α:=12π−π′1. Then To prove the local estimate, we decompose both π and π′ into a convex combination of a common part π^ and rests π+ and π′+. The coupling between the common parts gives no contribution to the distance and the worst possible estimate on the other parts is still enough to obtain the bound in the lemma, using Proposition 1. Let S0 be the initial set in the diagram S. We will need the following obvious rough estimate of the entropy distance that holds for any π,π′∈ΔS: It can be obtained by taking a tensor product for the coupling between X and Y. Our goal now is to write π and π′ as the convex combination of three other distributions π^, π+ and π′+ as in with the smallest possible α∈[0,1]. We could do it the following way. Let π0 and π0′ be the distributions on S0 that correspond to π and π′ under isomorphisms (8). Let α:=12π−π′1. If α=1 then the proposition follows from the rough estimate (9), so from now on, we assume that α<1. Define three probability distributions π^0, π0+ and π0′+ on S0 by setting for every x∈S0 Denote by π^,π+,π′+∈ΔS the distributions corresponding to π^0,π0+,π0′+∈ΔS0 under isomorphism (8). Thus, we have Now, we construct two fans of G-diagrams by setting and The reduction in the fans in (10) is given by coordinate projections. Note that the following isomorphisms hold Now we apply Proposition 1 along with the rough estimate in (9) to obtain the desired inequality □ 5. Proof of Proposition 2 In this section, we prove Proposition 2, which is shown below verbatim. The proof consists of the construction in Section 5.1 and estimates in Propositions 5 and 6. 5.1. The Construction In this section, we fix an indexing category G, a minimal G-diagram of probability spaces Z with an admissible sub-fan X0←Z0→U. We denote X:=X0 and by H we denote the combinatorial type of X=Xi;χij. Instead of diagram Z, we consider an extended diagram, which is a two-fan of H-diagrams where Y=Yi;υij consists of those spaces in Z, which are initial spaces of two fans with feet in U and in some space in X. That is for every i∈H the space Yi is defined to be the initial space in the minimal fan Xi←Yi→U in Z. It may happen that for some pair of indices i1,i2∈H the initial spaces of the fans with one feet U and the other Xi1 and Xi2 coincide in Z. In Y, however, they will be treated as separate spaces so that the combinatorial type of Y is H. Starting with the diagram in (11) one can recover Z by collapsing all the isomorphism arrows. The initial space of Y will be denoted Y0. We would like to construct a new fan X′←π1′Y′→VH, such that Once this goal is achieved, we collapse all the isomorphisms to obtain G-diagram satisfying conditions in the conclusion of Proposition 2. We start with a general description of the idea behind the construction, followed by a detailed argument. To introduce the new space V we take its points to be N atoms in u1,…,uN∈U. Ideally, we would like to choose the atoms in such a way that X0|un are disjoint and cover the whole of X0. It is not always possible to achieve this exactly. However, when |X0| is large, N is taken slightly larger than e[X0:U], and u1,…,uN are chosen at random, then with high probability the spaces X0|un will overlap only little and will cover most of X0. The details of the construction follow. We fix N∈N and construct several new diagrams. For each of the new diagrams, we provide a verbal and formal description. The space UN. Points in it are independent samples of length N of points in U. The space UN. Points in it are independent samples of length N of points in U. The space VN=(1,…,N,unif). A point n∈VN should be interpreted as a choice of index in a sample u¯∈UN. The space VN=(1,…,N,unif). A point n∈VN should be interpreted as a choice of index in a sample u¯∈UN. The H-diagram A, where A=Ai;αijAi=(x,n,u¯):x∈Xi|un,unifαij=(χij,Id,Id)A point (x,n,u¯) in Ai corresponds to the choice of a sample u¯∈UN, an independent choice of a member of the sample un and a point x∈Xi|un. Recall that the original diagram Z was assumed to be homogeneous and, in particular, the distribution on Xi|un is uniform. Due to the assumption on homogeneity of Z, the space Xi|u does not depend on u∈U. Since VN is also equipped with the uniform distribution, it follows that the distribution on Ai will also be uniform. The H-diagram A, where A=Ai;αijAi=(x,n,u¯):x∈Xi|un,unifαij=(χij,Id,Id) A point (x,n,u¯) in Ai corresponds to the choice of a sample u¯∈UN, an independent choice of a member of the sample un and a point x∈Xi|un. Recall that the original diagram Z was assumed to be homogeneous and, in particular, the distribution on Xi|un is uniform. Due to the assumption on homogeneity of Z, the space Xi|u does not depend on u∈U. Since VN is also equipped with the uniform distribution, it follows that the distribution on Ai will also be uniform. The H-diagram B, where B=Bi;βijBi=(x,u¯):x∈⋃n=1NXi|un,pBiβij=(χij,Id)A point (x,u¯)∈Bi is the choice of a sample u¯∈UN and a point x in one of the fibers Xi|un, n=1,…,N. The distribution pBi on Bi is chosen so that the natural projection Ai→Bi is the reduction of probability spaces. Given a sample u¯, if the fibers Xi|un are not disjoint, then the distribution on Bi|u¯ need not to be uniform. Below, we will give an explicit description of pB and study the dependence of pB(·|u¯) on the sample u¯∈UN. The H-diagram B, where B=Bi;βijBi=(x,u¯):x∈⋃n=1NXi|un,pBiβij=(χij,Id) A point (x,u¯)∈Bi is the choice of a sample u¯∈UN and a point x in one of the fibers Xi|un, n=1,…,N. The distribution pBi on Bi is chosen so that the natural projection Ai→Bi is the reduction of probability spaces. Given a sample u¯, if the fibers Xi|un are not disjoint, then the distribution on Bi|u¯ need not to be uniform. Below, we will give an explicit description of pB and study the dependence of pB(·|u¯) on the sample u¯∈UN. These diagrams can be organized into a minimal diamond diagram of H-diagrams, where reductions are obvious projections. To describe the probability distribution on B, first we define several relevant quantities: Recall that the distribution pB is completely determined by the distribution pB0 on the initial space of B via isomorphism (8). From homogeneity of Z it follows that distributions on both A0 and A|u¯ are uniform. Therefore The desired fan (X′←Y′→VH) mentioned in the beginning of the section is obtained from the top fan in the diagram in (13) by conditioning on u¯∈UN. We will show later that for an appropriate choice of N and for most choices of u¯, the fan we obtain in this way has the required properties. First, we would like to make the following observations. Fix an arbitrary u¯∈UN. Then: (1)The underlying set of the probability space B0|u¯=X0|u¯ is X_0. The underlying set of the probability space B0|u¯=X0|u¯ is X_0. (2)The diagrams Yu¯′:=A|u¯Xu¯′:=B|u¯ are included in a two-fan of H-diagrams which is obtained by conditioning the top fan in the diagram in (13).The very important observation is that diagrams Xu¯′|n and X|u are isomorphic for any choice of n∈VN and u∈U. The isomorphism is the composition of the following sequence of isomorphisms Xu¯′|n→B|(u¯,n)→A|(u¯,n)→X|un→X|u where the first isomorphism follows from the definition of Xu¯′, the second—from minimality of the fan B←A→VN, the third—from the definition of A and the fourth—from the homogeneity of Z. The diagrams Yu¯′:=A|u¯Xu¯′:=B|u¯ are included in a two-fan of H-diagrams which is obtained by conditioning the top fan in the diagram in (13). The very important observation is that diagrams Xu¯′|n and X|u are isomorphic for any choice of n∈VN and u∈U. The isomorphism is the composition of the following sequence of isomorphisms Xu¯′|n→B|(u¯,n)→A|(u¯,n)→X|un→X|u where the first isomorphism follows from the definition of Xu¯′, the second—from minimality of the fan B←A→VN, the third—from the definition of A and the fourth—from the homogeneity of Z. 5.2. The Estimates We now claim and prove that one could choose a number N and u¯ in UN such that (1)k(Xu¯′,X)≤20[[H]]. k(Xu¯′,X)≤20[[H]]. (2)[Yu¯,0′|Xu¯,0′]≤4lnln|X0|, where Yu¯,0′ and Xu¯,0′ are initial spaces in Xu¯′ and Yu¯′, respectively. [Yu¯,0′|Xu¯,0′]≤4lnln|X0|, where Yu¯,0′ and Xu¯,0′ are initial spaces in Xu¯′ and Yu¯′, respectively. 5.2.1. Total Variation and Entropic Distance Estimates If we fix some x0∈X0, then ν=ν(x0,·) is a scaled binomially distributed random variable with parameters N and ρ, which means that N·ν∼Bin(N,ρ). First, we state the following bounds on the tails of a binomial distribution. Let ν be a scaled binomial random variable with parameters N and ρ, then (i) for any t∈[0,1] holds P|ν−ρ|>ρ·t≤2·e−13·N·ρ·t2 for any t∈[0,1] holds P|ν−ρ|>ρ·t≤2·e−13·N·ρ·t2 (ii) for any t∈[0,2] holds Pνρlnνρ>t≤e−112·N·ρ·t2 for any t∈[0,2] holds Pνρlnνρ>t≤e−112·N·ρ·t2 The proof of Lemma 1 can be found at the end of this section. Below we use the notation P:=pUN for the probability distribution on UN. For a pair of complete diagrams C, C′ with the same underlying diagram of sets and with initial spaces C0, C0′, we will write α(C,C′) for the halved total variation distance between their distributions In the settings above, for t∈[0,1], the following inequality holds Recall that by definition Xu¯′=B|u¯. We use Equation (15) to expand the left-hand side of the inequality as follows Since by homogeneity of the original diagram, all the summands are the same, we can fix some x0∈X0 and estimate further: Applying Lemma 1(i), we obtain the required inequality. □ In the propositions below we assume that |X0| is sufficiently large (larger than e20). In the settings above and for any 10ln|X0|≤t≤1 holds: We will use local estimate, Proposition 3, to bound the entropy distance and then apply Proposition 4. To simplify notations, we will write simply α for α(Xu¯′,X)=α(B|u¯,X). Please note that in the chosen regime, t≥10/ln|X0|, the first summand in the right-hand side of the inequality is larger than the second, i.e., α≥Ent(Λα)/ln|X0| and therefore we can write □ 5.2.2. The “Height” Estimate Recall that for given N∈N and u¯∈UN we have constructed a two-fan of H-diagrams We will now estimate the length of the arrow Yu¯,0′→Xu¯,0′. In the settings above and for t∈[0,2] First, we observe that the fiber of the reduction Yu¯,0′→Xu¯,0′ over a point x∈Xu¯,0′ is a homogeneous probability space of cardinality equal to N(x,u¯), therefore its entropy is lnN(x,u¯). The last inequality above follows from Lemma 1 (ii). □ 5.3. Proof of Proposition 2 Let Xu¯′←Yu¯′→VN be the fan constructed in Section 5.1. The construction is parameterized by number N and atom u¯∈UN. Below, we will choose a particular value for N and apply estimates in Propositions 5 and 6 with particular choice of parameter t to show that there is u¯∈UN, so that the fan satisfies the conclusions of Proposition 2. Let With these choices of N and t, Proposition 5 implies while Proposition 6 gives Therefore, there is a choice of u¯ such that the fan satisfies conditions in (12). As we have explained at the beginning of Section 5.1, by collapsing isomorphism arrows, we obtain G-diagram Z′ satisfying conclusions of Proposition 2. 5.4. Proof of Lemma 1 The Chernoff bound for the tail of a binomially distributed random variable X∼Bin(N,ρ) asserts that for any 0≤δ≤1 holds Applying the bound for the upper and lower tail for the binomially distributed random variable N·ν, we obtain the inequality in (i). The second assertion follows from the following estimate For 0≤t≤2 we have 1+4t−1≥t, therefore By the Chernoff bound, we have Author Contributions Investigation, R.M. and J.W.P. All authors have read and agreed to the published version of the manuscript. Institutional Review Board Statement Not applicable. Data Availability Statement No new data were created or analyzed in this study. Data sharing is not applicable to this article. Conflicts of Interest The authors declare no conflict of interest. Funding Statement Open Access funding was provided by the Max Planck Society. Footnotes Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. References Associated Data Data Availability Statement No new data were created or analyzed in this study. Data sharing is not applicable to this article.