Tree-structured Ising models can be learned efficiently

We provide the first polynomial-sample and polynomial-time algorithm for learning tree-structured Ising models. In particular, we show that $n$-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance~$\epsilon$ from an optimal $O(n \log n/\epsilon^2)$ samples, where $O(.)$ hides an absolute constant which does not depend on the model being learned -- neither its tree nor the magnitude of its edge strengths, on which we place no assumptions. Our guarantees hold, in fact, for the celebrated Chow-Liu [1968] algorithm, using the plug-in estimator for mutual information. While this (or any other) algorithm may fail to identify the structure of the underlying model correctly from a finite sample, we show that it will still learn a tree-structured model that is close to the true one in TV distance, a guarantee called"proper learning."Prior to our work there were no known sample- and time-efficient algorithms for learning (properly or non-properly) arbitrary tree-structured graphical models. In particular, our guarantees cannot be derived from known results for the Chow-Liu algorithm and the ensuing literature on learning graphical models, including a recent renaissance of algorithms on this learning challenge, which only yield asymptotic consistency results, or sample-inefficient and/or time-inefficient algorithms, unless further assumptions are placed on the graphical model, such as bounds on the"strengths"of the model's edges. While we establish guarantees for a widely known and simple algorithm, the analysis that this algorithm succeeds is quite complex, requiring a hierarchical classification of the edges into layers with different reconstruction guarantees, depending on their strength, combined with delicate uses of the subadditivity of the squared Hellinger distance over graphical models to control the error accumulation.


Introduction
Markov Random Fields (MRFs) and Bayesian Networks (Bayesnets) are popular frameworks for graphically representing high-dimensional distributions, allowing the explicit specification of conditional independence properties that a high-dimensional distribution may satisfy. These properties can be exploited to decrease the sample and computational requirements to learn the distribution, as well as to perform inference once the distribution has been learned. A particularly simple special case of both frameworks occurs when the underlying graph is a tree. In this case, many basic inference tasks that are computationally intractable even to approximate in general, e.g. computing marginals or the mode of the distribution, can be carried out exactly by simple, linear-time algorithms, such as the popular sum-product and max-product algorithms. For an introduction to MRFs and Bayesnets, their uses, and associated algorithms see, e.g., [15,23,17].
The attractiveness of these graphical models and their widespread use in application domains have motivated a vast literature on learning them from samples; see e.g. the references above and [5,6,16,18,20,11,19,1,21,13,10,24,22]. Even when the model to be learned is tree-structured, however, these methods only yield asymptotic consistency results, or sample-inefficient and/or time-inefficient algorithms, unless further assumptions are placed on the distribution. Indeed, recent works on efficiently learning Ising models (and more general MRFs) only provide guarantees that the learned distribution is close (under some probabilistic distance) to the one being learned, assuming a bound on the total "strength" of the edges (resp. hyper-edges) adjacent to each node. Under even stronger assumptions, some of these works also identify the graphical structure of the Ising model (resp. MRF).
Our goal in this paper is to study whether a tree-structured Ising model (equivalently a tree-structured binary-alphabet Bayesnet or a tree-structured binary-alphabet MRF) can be learned without making any assumptions about the distribution. More precisely, we target the following challenge.
Learning Challenge: Given samples from an arbitrary n-variable tree-structued Ising model P, learn some n-variable distribution Q that is within some desired total variation distance > 0 from P, using a number of samples and total computation time that scale polynomially in n and 1/ , and are independent of any property of P.
While efficiently learning arbitrary tree-structured Ising models in any fashion is already an open problem, we will additionally insist on what is called proper learning, i.e. we will aim to compute a tree-structured Ising model Q such that d TV (P, Q) ≤ . We want to identify a tree-structured Ising model Q as we want to maintain the computational benefits of tree-structured models when performing inference tasks on the learned Q. And, of course, we want that Q is close to the true model P in total variation distance so that the inferences on Q are approximately correct. We resolve both challenges by showing that the celebrated Chow-Liu algorithm [5] attains these guarantees. Theorem 1.0.1 (Main Theorem-Restated as Theorem 4.0.1 in Section 4). For n ∈ N, , γ ∈ (0, 1], given O n(ln n+ln 1/γ) 2 samples from an arbitrary n-variable binary-alphabet Bayesnet P defined on an unknown tree, the Chow-Liu algorithm with the plug-in estimator for estimating mutual information (namely Algorithm 1), learns an n-variable tree-structured Bayesian Network Q on a (possibly different) tree such that d TV (P, Q) ≤ with probability at least 1 − γ. The running time of the algorithm is polynomial, and is dominated by the time to compute the mutual information between all pairs of variables on the empirical distribution defined by the samples, and running a Maximum Spanning tree algorithm. Finally, the number of samples is optimal up to a constant factor. Importantly, the O(·) in our sample complexity is hiding an absolute constant which does not depend on the model being learned-neither its tree nor the magnitude of the edge strengths.
We note that it is well-understood that the celebrated Chow-Liu algorithm [5] can be used to obtain an asymptotically consistent estimator of tree-structured models [6]. Recall that the Chow-Liu algorithm computes a tree on random variables X 1 , . . . , X n by running a Maximum Spanning Tree algorithm on a weighted clique with nodeset V = {X 1 , . . . , X n } and edge weight w ij between every pair of nodes X i and X j that is set equal to an estimate of the mutual information, I(X i ; X j ), between X i and X j . (These are precisely Steps 2-4 of Algorithm 1.) When the distribution P of the random variables is a tree-structured model defined on some tree T wherein the distributions of the endpoints (X i , X j ) of each edge satisfy some non-degeneracy condition, and when the estimation error of each I(X i ; X j ) is small enough, it is known that the computed maximum spanning tree will equal T. Moreover, once T known, it is not hard to see-using e.g. the results of [8]-that O(n ln n/ 2 ) samples from P suffice to define some Q on this tree such that d TV (P, Q) ≤ .

Probability Notation
In this paper we use the term random variable (or just variable) to refer to some symbol, say X, that takes value in some alphabet set, say A, whose exact distribution is left to be assigned. This deviates slightly from the general convention in probability literature where the term "random variable" also encompasses the assignment of a distribution. Our choice makes it so that it is possible to speak of different distributions for the same random variable. For example, it now makes sense to say "suppose P and Q are distributions for X". This will greatly simplify our notation.
Throughout the text, we use subscripts at probability symbols to help zoom in on subsets of random variables. If P is a joint distribution for a set of random variables X 1 , . . . , X n , and S is a subset of those variables, or just a subset of the indexes [n] = {1, . . . , n}, then we use P S to denote the marginal distribution of P for those variables in S. For example, we use P X i X j X k , or just P ijk , to denote the marginal of P for the triplet of variables X i , X j , X k . When the variables (or indexes) are spelled out explicitly at the subscript, the values inside the parentheses that may follow are to be assigned to the variables in the order they (or their indexes) are spelled out. For example, P ijk (a, b, c) is the probability of the event "X i = a, X j = b, X k = c". We list the indexes in alphabetical order at the subscripts whenever possible to make such variable assignments easier to read.
If the event of interest is made clear inside the parentheses, we may drop the subscript at the probability symbol, as in P(X i = 1, X j = −1, X k = 1) or P(X i = X j ). The generalization of everything so far to conditional distributions is straightforward, with examples including P S|S , P ik|j (a, b|c), and P(X i = a, X k = b | X j = c).
When S is a subset of the indexes, we use X S to denote the set of variables with indexes in S, and x S to denote a specific assignment of values to those variables, perhaps as a restriction of the general assignment x.

Markov Random Fields and Bayesian Networks
We provide the basic definitions of Markov Random Fields and Bayesian Networks.

Definition 2.2.1. A Markov Random Field (MRF)
is a joint distribution P for X 1 , . . . , X n with an underlying undirected graph G on [n], where each X i takes value in A. Associated with each maximal clique C ∈ cl(G) is a potential function ψ C : A C → [0, 1], where cl(G) is the set of all maximal cliques of G. In terms of these potentials, P assigns to each vector x ∈ A n a probability P(x) satisfying where Z is a normalization constant making sure that P, as defined above, is a distribution. In the degenerate case where the products on the RHS of (1) always evaluate to 0, we assume that P is the uniform distribution over A n . In that case, we get the same distribution by assuming that all potential functions are identically 1. Hence, we can assume that the products on the RHS of (1) cannot always evaluate to 0.

Definition 2.2.2.
A Bayesian network, or Bayesnet, is a joint distribution P for X 1 , . . . , X n with an underlying directed acyclic graph G, where each X i takes value in A. To describe P, one specifies conditional probabilities P i|Π i (x i |x Π i ), for all i ∈ [n], and configurations x i ∈ A and x Π i ∈ A Π i , where Π i represents the set of parents of i in G, taken to be ∅ if i has no parents. In terms of these conditional probabilities, P assigns to each vector x ∈ A n a probability P(x) satisfying It is important to note that both MRFs and Bayesnets allow the study of distributions in their full generality, as long as the graphs on which they are defined are sufficiently dense. In particular, the graphs underlying these models captures conditional independence relations, and is sufficiently flexible to capture the structure of intricate dependencies in the data.
In this paper, we focus on the special case of tree-structured MRFs and Bayesnets, namely: • MRFs whose underlying undirected graphs are trees; • Bayesnets whose underlying DAGs are directed rooted trees (with a designated root and all edges oriented away from the root).
It is easy to see that tree-structured MRFs and Bayesnets have the exact same expressive power. More specifically, for any directed rooted tree T, the set of all Bayesnets on T coincides with the set of all MRFs on the undirected version of T. In view of this equivalence, we will only use the term "tree-structured Bayesnet", but think of the underlying tree T as undirected, unless otherwise noted. Tree-structured Bayesnets on T satisfy the following graph separation criterion for conditional independence relations: if A, B, C are disjoint subsets of [n] such that the path in T between any i ∈ A and any j ∈ B goes through at least one node in C (that is, C separates A from B in T), then X A and X B are independent conditional on X C . By "path", we mean the unique shortest path (in the tree being specified), always.
Markov chains are special cases of tree-structured Bayesnets whose underlying trees are simply lines. A Markov chain for X 1 , . . . , X n , in that order, is a tree-structured Bayesnet whose underlying tree has edges (1, 2), (2,3), . . . , (n − 1, n). In this paper, we mostly utilize the Markov chain property of certain subsets of the variables. We will come back to this point in Section 2.3.
In this paper, we also focus on the case of binary alphabets, i.e. Ising models. We use A = {1, −1} throughout.
Finally, we call a binary Bayesnet symmetric iff each variable takes each of 1, −1 with probability 1 2 .

Tree-Structured Bayesnets
A tree-structured Bayesnet P for X 1 , . . . , X n can be uniquely determined by specifying its underlying tree T, together with its marginal distributions for pairs of variables corresponding to edges of T (in the binary case, for example, each such marginal P ij is described by four nonnegative numbers P ij (1, 1), P ij (1, −1), P ij (−1, 1), and P ij (−1, −1) that sum to 1). The only requirement is that the set of all those pairwise marginals is consistent, in the sense that if two edges share some node i, then further marginalizations of the two corresponding pairwise marginals onto X i provide the same result. To see that, root T at 1, and assume without loss of generality (by possibly reindexing) that i < j implies the depth of i is at most the depth of j. For 2 ≤ i ≤ n, let π(i) denote the parent of i (our assumption implies π(i) < i). Note that the edges of T are then {(i, π(i)) | 2 ≤ i ≤ n}. Since π(i) separates i from everything else in 1, . . . , i − 1, we have P(x) = P 1 (x 1 ) n i=2 P i|1...i−1 (x i |x 1 , . . . , x i−1 ) = P 1 (x 1 ) n i=2 P i|π(i) (x i |x π(i) ). (2) Note that the values of the terms in the rightmost expression can be determined from the marginal distributions for the edges of T, which we assume to have been specified. Given a tree-structured Bayesnet P specified as above, we might be interested in the properties of P S for some subset S of [n]. We will characterize a class of subsets for which this description is simple. We need some definitions first.

Definition 2.3.1 (Induced Subgraph, T T T-connectedness). For a tree T, and a subset of nodes S, we say that S is T T T-connected if and only if T[S] is connected, where T[S] T[S] T[S] is the subgraph in T induced by S. Equivalently, S is
T-connected iff for any i, j ∈ S, all the nodes on the path in T between i and j are in S.
If a tree-structured Bayesnet P has underlying tree T, and S is a T-connected subset of [n], then P S is also a tree-structured Bayesnet. Furthermore, its underlying tree is T[S] (a tree according to Definition 2.3.1), and for an edge (i, j) of T[S], its marginal distribution for (i, j) is P ij . To see that, notice that if A, B, C are disjoint subsets of S, then C separates A from B in T[S] if and only if C separates A from B in T. Thus, P S satisfies all conditional independence relations implied by T[S], and so admits a factorization with respect to T[S] (follow steps similar to those leading to (2) above). The assertion on the marginals of P S for edges of T[S] is obvious.
There are also subsets that are not necessarily T-connected for which the marginals of P are simple to describe. Instead of striving for the most general results in this vein, we content ourselves with the following special case that will appear many times throughout the paper. Suppose indexes i 1 , i 2 . . . , i r lie on a path in T T T, that is, i 2 sits on the path in T between i 1 and i r , i 3 sits on the path in T between i 2 and i r , and so on. Then it is easy to see that P i 1 i 2 ···i r is a Markov chain for X i 1 , X i 2 , . . . , X i r , in that order, with marginal P i s i s+1 for the pair of variables X i s , X i s+1 for each s = 1, . . . , r − 1.

Binary Symmetric Tree-Structured Bayesnets
For a binary symmetric tree-structured Bayesnet P, its marginal distribution for each pair (X i , X j ) (not necessarily an edge of the underlying tree) is determined simply by the probability of the two nodes being equal, namely P(X i = X j ). For convenience, we reparametrize P(X i = X j ) using α ij , such that P(X i = X j ) = 1+α ij 2 , and P(X i = −X j ) = 1−α ij 2 . So overall we have P(X i = 1, X j = 1) = 1 2 1+α ij 2 , P(X i = 1, X j = −1) = 1 2 1−α ij 2 , P(X i = −1, X j = 1) = 1 2 1−α ij 2 , and P(X i = −1, X j = −1) = 1 2 1+α ij 2 . We call α ij the α α α-value of the pair (X i , X j ), or just of (i, j), for P. A binary symmetric tree-structured Bayesnet P can therefore be uniquely determined by specifying its underlying tree T, together with the α-value of each edge of T. Edges with α-values close to 1 or −1 are strong; the two variables are almost always equal or almost always unequal under P. Edges with α-values close to 0 are weak; the two variables are nearly independent under P.
The convenience of using the α-value lies in their multiplicativity, which we prove after first proving an independence result. Lemma 2.4.1. Suppose a binary symmetric tree-structured Bayesnet P has underlying tree T, and i, j, k lie on a path in T, then P(X i = X j , X j = X k ) = P(X i = X j )P(X j = X k ).
The identity still holds if we replace "X i = X j " with "X i = −X j " (on both sides), or "X j = X k " with "X j = −X k ", or both.
where ( * ) follows from Lemma 2.4.1. The desired statement thus follows by induction on r.

Distances and the Subadditivity of Squared Hellinger
Even though our final goal is to learn in the total variation distance, d TV , for the most part of our argument we will work instead with the Hellinger distance H, and its square H 2 . Let's define those quantities.

Definition 2.5.1 (Total Variation, Hellinger).
For two discrete distributions p = (p 1 , . . . , p L ) and p = (p 1 , . . . , p L ) over a domain of size L, their total variation distance is defined as whereas their Hellinger distance is defined as The squared Hellinger is therefore Note that while d TV and H satisfy the triangle inequality, H 2 does not, so it is not a distance metric on probability distributions. The Hellinger distance always takes value in [0, 1]. Compared with the total variation distance, Hellinger distance satisfies the following inequalities.
The following important corollary of Theorem 2.5.3 will be used heavily in bounding the Hellinger distance between the true distribution and our learned distribution. Corollary 2.5.4. Suppose P and P are tree-structured Bayesnets for X 1 , . . . , X n , with underlying trees T and T , respectively. Suppose A 1 , . . . , A Λ are nonempty, pairwise disjoint sets whose union is [n], such that

A λ is both T -connected and T -connected, for each λ;
2. there is an edge in T between A λ and A µ iff there is an edge in T between A λ and A µ , for each pair λ, µ.
Let E be the set of all unordered pairs (λ, µ) such that there is an edge in T and an edge in T straddling A λ and A µ (note that each straddling edge must be unique due to the T /T -connectedness of A λ and A µ ). For each (λ, µ) ∈ E, let W λµ be the set of endpoints of those two straddling edges, so it has cardinality 2, 3, or 4, depending on how many endpoints are shared. Then, H 2 (P , P ) ≤ Λ λ=1 H 2 (P A λ , P A λ ) + (λ,µ)∈E H 2 (P W λµ , P W λµ ). (3) Proof. It is easy to see that the edges in E form a tree on [Λ]. Call it T . Consider T as rooted at 1, we can assume without loss of generality (by possibly reindexing the A λ 's) that λ < µ implies the depth of λ is at most the depth of µ. For 2 ≤ λ ≤ Λ, let π(λ) denote the parent of λ (our assumption implies π(λ) < λ).
Note that the edge set E then has the form {(λ, π(λ)) | 2 ≤ λ ≤ Λ}. To simplify notation, for 2 ≤ λ ≤ Λ, let U λ = W λ,π(λ) ∩ A π(λ) , so it consists of the endpoints of the edges in T and T straddling A λ and A π(λ) that are on the A π(λ) side. Let V λ = W λ,π(λ) ∩ A λ , so it consists of the endpoints of the edges in T and T straddling A λ and A π(λ) that are on the A λ side. Then, P and P have the common factorization Since U λ ∪ V λ = W λ,π(λ) , we can apply Theorem 2.5.3 to obtain the desired inequality.

Notation for Creating Markov Chains on 3 or 4 Nodes with Various Orderings
The notation to be introduced next is useful later, for example, when we reason about the relative positioning of a small subset (3 or 4) of nodes in the (unknown) underlying tree of the distribution we wish to learn.
The definition relies on the method for specifying a tree-structured Bayesnet mentioned in Section 2.3. The subscript at each symbol is a drawing of the underlying line graph of the Markov chain being represented. For example, i−j k is the line graph on i, j, k with edges (i, j) and (i, k). It is the underlying tree of P i−j k , a Markov chain for X j , X i , X k , in that order (we want to keep the indexes at the subscripts in alphabetical order, which is why we adopted i−j k instead of j − i − k, for example).
Definition 2.6.1. Given an arbitrary joint distribution P for random variables X 1 , . . . , X n , and i, j, k ∈ [n], we adopt the following notations: P i−j k -the Markov chain for X j , X i , X k , in that order, with the marginal for (i, j) equal to P ij , and the marginal for (i, k) equal to P ik ; P i−j−k -the Markov chain for X i , X j , X k , in that order, with the marginal for (i, j) equal to P ij , and the marginal for (j, k) equal to P jk ; P ij−k -the Markov chain for X i , X k , X j , in that order, with the marginal for (i, k) equal to P ik , and the marginal for (j, k) equal to P jk .
At the subscript of each of the three symbols listed above, the indexes are regarded as being spelled out in the order of i, j, k. The convention regarding assigning values to variables introduced in Section 2.1 still applies, and we use, for example, P i−j k (a, b, c) to denote the probability of the event "X i = a, X j = b, X k = c" under P i−j k .
We can generalize the paradigm above to subsets of four nodes. For h, i, j, k ∈ [n], we have for example P h−ij−k -the Markov chain for X h , X i , X k , X j , in that order, with the marginal for (h, i) equal to P hi , the marginal for (i, k) equal to P ik , and the marginal for (j, k) equal to P jk ; P h˚ −i j−k -the Markov chain for X i , X h , X k , X j , in that order, with the marginal for (h, i) equal to P hi , the marginal for (h, k) equal to P hk , and the marginal for (j, k) equal to P jk , and so on. At the subscript of each of the two symbols listed above, the indexes are regarded as being spelled out in the order of h, i, j, k. So we use, for example, P h−ij−k (a, b, c, d) to denote the probability of the event "X h = a, Remark 2.6.2. Note that while P ijk (or P hijk ) may not satisfy any conditional independence relation, the five distributions listed in Definition 2.6.1 are constrained to be Markov chains with the specified orderings of nodes, by design.
The following lemma is a good exercise to get familiar with the notation just introduced. It also involves some simple applications of squared Hellinger subadditivity (Lemma 2.5.3) introduced in Section 2.5. Lemma 2.6.3. Suppose a tree-structured Bayesnet P has underlying tree T, and h, i, j, k lie on a path in T. Then, Proof. We will use P h−ij−k as an intermediate step between P hijk and P h˚ −i j−k . See Figure 1 for depictions of the three distributions involved). To bound the distance between P hijk and P h−ij−k , notice that they share the common factorization structure: (In fact we have equality, which can be seen by directly applying the definition of H 2 to H 2 (P hijk , P h−ij−k ) and H 2 (P ijk , P ij−k ), and using the common factorization of P hijk and P h−ij−k above. However, the inequality version suffices, and demonstrates the use of Lemma 2.5.3.) Simiarly, to bound the distance between P h−ij−k and P h˚ −i j−k , notice that they share the common factorization structure:

Estimating Bernoulli Parameters
The following lemma deals with the precision in which we can approximate a Bernoulli parameter p, in the absolute value sense, using the empirical average. Note that our bound here depends on p.
We use the following multiplicative form of Chernoff Bound, which says that for 0 ≤ δ ≤ 1 we have Definition 2.8.1 (ind). Given an arbitrary joint distribution P on a set of random variables that includes X and Y, we define P (ind) XY to be the independent pairwise distribution for X and Y with the same individual marginals at X and Y, respectively, as P XY does.
The following definitions for the KL-divergence, the mutual information, and the conditional mutual information are standard. Definition 2.8.2 (KL-Divergence, Mutual Information, Conditional Mutual Information). For two discrete distributions p = (p 1 , . . . , p L ) and p = (p 1 , . . . , p L ) over a domain of size L, the KL-divergence from p to p is defined as Given an arbitrary joint distribution P for a set of random variables that includes X, Y, and Z (with alphabet sets A X , A Y , and A Z , respectively), the mutual information of X and Y with respect to P is defined as the KL-divergence from P (ind) XY to P XY : and the conditional mutual information of X and Y given Z with respect to P is defined as the expected value of the mutual information of X and Y with respect to their conditional pairwise distribution conditioning on Z = z, with z drawn according to P Z : We will also need the following extension of the notation introduced in Definition 2.6.1.

Definition 2.8.3.
Given an arbitrary joint distribution P for random variables X 1 , . . . , X n , and h, i, j, k ∈ [n], we adopt the following notations: P h−i−(jk) -the Markov chain for X h , X i , X jk , in that order, with the marginal for (h, i) equal to P hi , and the marginal for i, j, k equal to P ijk ; P (hi)j−k -the Markov chain for X hi , X k , X j , in that order, with the marginal for h, i, k equal to P hik , and the marginal for (j, k) equal to P jk , and so on. At the subscript of each of the two symbols listed above, the indexes are regarded as being spelled out in the order of h, i, j, k. So we use, for example, P (hi)j−k (a, b, c, d) to denote the probability of the event "X h = a, X i = b, X j = c, X k = d" under P (hi)j−k . Remark 2.8.4. In Definition 2.8.3 when we say for example P (hi)j−k is a Markov chain for X hi , X k , X j , in that order, we are treating the pair (X h , X i ) as one single random variable X hi so that the Markov structure is really on three (super) random variables. We don't order between X h and X i . In other words, the only conditional independence property implied by the Markov structure is that X hi and X j are independent conditioning on X k .
Next we define four measures that are important in classifying the edges and reasoning about the layers for the general case. Definition 2.8.5 (minmrg). Given an arbitrary joint distribution P for binary random variables X 1 , . . . , X n , and U ⊂ [n], we define minmrg( That is, minmrg(P U ) denotes the minimum probability among those assigned to either 1 or −1 by any of the marginals of P U for individual variables. A small P U implies that at least one of those variables is very biased towards either 1 or −1. ).
Note that I H 2 (P ij ) measures how far from independent P ij is in H 2 , and that I H 2 (P ij ) = 0 is equivalent to X i and X j being independent. Therefore, mindisc(P ij ) provides yet another way to measure the strength of interaction between X i and X j .
The final lemma of this section is a strengthening of Lemma 2.7.1 in the case p is small. It will be used to bound certain mutual information-related terms for the general case in Section 4. Lemma 2.8.9. There exists B > 0 such that given any > 0, γ < 1 2 , and 0 < p < , if we let m ≥ B · 1 ln 1 γ , and p = X 1 +···+X m m , where X 1 , . . . , X m are i.i.d Bernoulli random variables with parameter p, then we have p ln p ≤ with probability at least 1 − γ.
Proof. By Lemma 2.7.1, for all big enough B we have | p − p| ≤ 1 100 · max √ p , = 1 100 . Assuming that, we argue by cases.
Case 1 : 1 100 < p < Let p = a , so that 1 100 < a < 1. We have where the last inequality follows from the fact that ln t t < 1 2 for t > 1. Case 2 : p ≤ 1 100 Again let p = a , so that a ≤ 1 100 . Consider the following multiplicative form of Chernoff Bound, which says that for δ > 0 we have as long as B ≥ 4. Note that ( * ) holds because a ≤ 1 100 implies β ≥ e 2 , and ( * * ) holds because t 1 2 ln t > 1 for t > 1.
Thus, we have p ≤ βp with probability at least 1 − γ. When that happens, we have

The Symmetric Case
As the analysis for general tree-structured Ising models is much more complex, here we first focus on learning symmetric models, wherein every node has a uniform marginal. Even in this case, proving learnability guarantees for the Chow-Liu algorithm is non-trivial, so we focus on a closely related, but slightly easier to analyze algorithm. The analysis of this variation of the Chow-Liu algorithm for proper learnings of binary symmetric tree-structured Bayesnets will nevertheless illustrate all the major ideas present in the analysis of the general case. In Section 4, we provide the necessary modifications to our argument to analyze Chow-Liu for general tree-structured Ising models. Throughout Section 3, we reserve the symbol P to represent the unknown binary symmetric treestructured Bayesnet for X 1 , . . . , X n that we wish to properly learn. The dimension of P is n. We reserve T to represent the true (but unknown) underlying tree of P, and α ij to represent the true (but unknown) α-value of the pair (i, j) under P (see Section 2.4 for a discussion of α-values). Our proper learning algorithm for the symmetric case is presented as Algorithm 2 below. See Section 2.4 for a discussion on specifying a binary symmetric tree-structured Bayesnet.

Algorithm 2: PROPER LEARNING OF A BINARY SYMMETRIC TREE-STRUCTURED BAYESNET
Input: , γ ∈ (0, 1] Output: specification of a binary symmetric tree-structured Bayesnet Q, approximating P 2 Let P be the empirical joint distribution of (X 1 , . . . , X n ) induced by the m samples, so that Run Kruskal's algorithm to find a maximum weight spanning tree T of the complete graph on [n] with weight α ij for (i, j). (1) T as Q's underlying tree, (2) α ij as Q's α-value for (i, j), for each edge (i, j) of T.

return
Throughout the section, we will also reserve the symbols P, α ij , T, and Q for the respective meanings they carry in Algorithm 2. We call α ij the α α α-estimate of the pair (i, j), and α ij the | α α α|-estimate of the pair (i, j). Our main result for Algorithm 2 is the following.
In fact, we establish something stronger and perhaps surprising. We show that Algorithm 2 is successful as long as the empirical distribution P satisfies a deterministic criterion, presented below. Definition 3.0.2 . For a given run of Algorithm 2, P is said to satisfy 3-consistency if for every S ⊆ [n] of cardinality 3 and every W ⊆ {1, −1} 3 we have The criterion of Definition 3.0.2 specifies that P well-approximates the true distribution P for all events involving up to 3 variables. Some concrete examples of the event "X S ∈ W" in Definition 3.0.2 are "X i = −X j , X j = X k ", "X i = X j ", and "X i = 1". For example, "X i = X j " is expressed by taking S = {i, j, k} (where k is any index other than i, j) and W = {(1, 1, 1), (1, 1, −1), (−1, −1, 1), (−1, −1, −1)}.
We show that whenever the samples provided to Algorithm 2 induce P which satisfies 3-consistency, the algorithm succeeds (up to a constant), as per the following theorem. Notice that there are less than n 3 choices for S, and 2 8 choices for W for each S. By Lemma 2.7.1 and the union bound, 3-consistency fails with probability at most γ if B is chosen large enough. Consequently, showing Theorem 3.0.3 implies Theorem 3.0.1 (up to a constant). We will focus on proving Theorem 3.0.3.

Outline of the Proof
In this section, we outline our analysis, presenting the intuition guiding our proof as well as the critical techniques that we develop to complete it. All lemmas presented in this section are restated copies of lemmas with the same label stated and proved in Section 3.2.
Narrowing into a deterministic condition for success. A few words first on the 3-consistency condition (see Definition 3.0.2). We'd ideally like to have a simple deterministic condition describing the samples that is satisfied with probability at least 1 − γ, and that yields d TV (P, for all i and x i ∈ {1, −1}, with probability at least 1 − γ. In fact, for any fixed constant K, by choosing a big enough B we can get similar guarantees simultaneously for all events of the form "X S ∈ W" for all subsets S of K indexes and all W ⊆ {1, −1} K , with probability at least 1 − γ. Our surprising finding is that taking K = 3 (and c = 1 10 ) is sufficient to guarantee the success of the algorithm. From now on we assume that P satisfies 3-consistency. It suffices to show that this alone implies d TV (P, Q) ≤ O ( ), for the output Q of the algorithm (that is, it suffices to prove Theorem 3.0.3). It is worth emphasizing that our argument from this point on is completely deterministic. In fact, if P were obtained in some way other than being the empirical joint distribution of i.i.d samples (for example, from dependent samples or even an oracle), as long as it satisfies 3-consistency Algorithm 2 would still output Q such that d TV (P, Q) ≤ O ( ).
Long hybrid arguments vs squared Hellinger subadditivity. We first illustrate how H (Hellinger distance) and the subadditivity of H 2 (squared Hellinger) play an important role in the argument even though our final goal is to provide a bound in d TV (total variation distance). Suppose, for the sake of this illustration, that we happened to learn the structure of the tree correctly, that is T = T. In this case, P and Q would only differ in their α-values on the edges of the true T (α ij for P and α ij for Q). How could we bound d TV (P, Q)? One way is to use a hybrid argument modifying P to Q by changing the α-value of one edge of T at a time from α ij to α ij , resulting in a sequence of intermediate distributions all with the same underlying tree T and with increasingly more edges of T having α-value α ij instead of α ij . It easily follows from 3-consistency that the difference between α ij and α ij is O , and this bounds the cost in d TV when we change the α-value of an edge from α ij to α ij . In general, this cost is upper bounded by O √ n , so for n − 1 changes of α-value the triangle inequality gives an overall d TV bound between P and Q of O √ n , which is not good enough.
H suffers from the same problem. It can be shown that the cost in H when we change the α-value of an edge from α ij to α ij is O √ n (see Lemma 3.2.5 in Section 3.2.1), which is also not enough to make the hybrid argument work. But, here is an important insight. The H 2 subadditivity property (see Corollary 2.5.4) applied to our case implies that H 2 (P, Q) is bounded by the sum of H 2 (P ij , Q ij ) for all edges (i, j) of T. Note that H 2 is not a distance metric, so the subadditivity is not the result of some hybrid argument changing the α-values one edge at a time. Rather, we are changing the α-values for all n − 1 edges of T in one round. Since we pay in H 2 per edge, in total we pay O 2 in squared Hellinger, yielding d TV (P, Q) ≤ √ 2H(P, Q) ≤ O ( ), as desired.
Causes of structural uncertainty. Of course, we can't expect T = T. It is possible that T may be very different from T. If a subset of nodes are linked together in T by edges with α-values 1, then those nodes will always equal each other in the sample, and there is no way Algorithm 2 can tell what the true edges are. Algorithm 2 will be similarly clueless if the linking edges all have α-values 1 or −1, or if they all have α-values 0 (in which case the variables will be mutually independent). Intuitively, we should expect Algorithm 2 to also have difficulty picking out the true edges if the α-values are close enough to 1 or −1, or close enough to 0. When different strength scales interact the algorithm may get a "partial clue" of the structure. For example, suppose n = 3 and X 1 , X 2 , X 3 form a Markov chain, in that order, with α 12 = 1 2 and α 23 close to 1. Then Algorithm 2 should be able to pick out edge (2, 3), but might have trouble distinguishing between (1, 2) and (1, 3) (in other words, | α 23 | should be the clear winner but the order between | α 12 | and | α 13 | might be reversed). The case α 12 close to 0 and α 23 = 1 2 is similar. As n gets larger the picture gets complicated very quickly, and it seems very hard to reason about the effect of interactions among different edges and the order relationships among different α ij 's. The central difficulty in our argument is controlling the error when T and T differ in many edges. The main difficulty is to bound the error when switching the edges from those of T to those of T. Once that is done, further switching the α-values of the edges of T from α ij to α ij (with the underlying tree fixed to be T) can be dealt with relatively easily as illustrated above. More specifically, if we define the hybrid distribution P (4) (the reason for calling it P (4) will be clear later), with underlying tree T and α-value equal to α ij for every edge (i, j) in T, it follows from our earlier H 2 -subadditivity argument that d TV (P (4) , Q) ≤ O ( ). So our focus from now on is bounding d TV (P, P (4) ). Some modest understanding. Let's start simple and consider only three nodes i, j, k that lie on a path in T (n can be arbitrary, and i, j, k don't have to be adjacent to each other). The multiplicativity of α-values along a path (Lemma 2.4.2) implies that α ik = α ij α jk is no greater in absolute value than either α ij or α jk . Algorithm 2 may "reverse the order" between (i, j) and (i, k) if α ij ≤ | α ik |. The following lemma characterizes when this can possibly happen (assuming 3-consistency): Lemma 3.2.7. If i, j, k lie on a path in T, and α ij ≤ | α ik |, then α 2 The next lemma bounds the H 2 distance between P ijk and P ij−k (see Definition 2.6.1 for the definitions of symbols such as P ij−k ). It is the error in H 2 when we switch from (i, j) to (i, k). See Figure 2 for depictions of those two distributions.
The next lemma follows directly from Lemmas 3.2.7 and 3.2.6. It says that if Algorithm 2 makes a structural mistake and "reverses the order" between (i, j) and (i, k), then the resulting error in H 2 between the true structure and the wrong structure must be small (assuming 3-consistency). Lemma 3.2.8. If i, j, k lie on a path in T, and α ij ≤ | α ik |, then H 2 (P ijk , P ij−k ) ≤ 2 2 n .
We also have the following four-node version of Lemma 3.2.8 (see Figure 3 for depictions of the two distributions involved):  The challenges of going bigger. It is not hard to see using Lemmas 3.2.8 and 3.2.9 that if Algorithm 2 picks a single wrong edge, then H(P, P (4) ) ≤ O √ n . So what if the algorithm picks multiple wrong edges? An obvious idea is to use the triangle inequality (satisfied by H) and create many intermediate distributions between P and P (4) , going from T to T replacing one edge at a time (possibly through the use of some intermediate edges that belong to neither T nor T), assigning to each edge (i, j) of the underlying tree of each intermediate distribution α-value α ij , and using Lemmas 3.2.8 and 3.2.9 to bound the error in H after each edge replacement. Unfortunately, this does not work, not only because the triangle inequality would lead to a bound that is potentially √ n times too big, but also because there are examples of T and T for which there does not even exist a sequence of replacements that would allow us to properly apply Lemmas 3.2.8 or 3.2.9 to bound the error in H after every replacement. 1 See Figure 4 for such a pair of T and T.
To salvage the situation we choose to use Corollary 2.5.4 (squared Hellinger subadditivity) which allows us to replace many edges in one round, as long as they are "compatible," as per the statement of that corollary. If we allow r general rounds of edge replacements, then we may need to replace Θ n r edges per round. Assume that either Lemma 3.2.8 or 3.2.9 is applicable for each individual edge replacement, then we can get an error bound of O » n r · 2 n = O √ r in H per round, and so O √ r in H in total. This suggests aiming for a constant number of rounds. It is not clear at all how this might be achieved. For that, we introduce another crucial structural ingredient-layering-which allows us to be more precise about the manner in which T may differ from T. Figure 4: A pair of T and T for which there is no way to go from T to T by replacing one edge at a time in a way that allows us to properly apply Lemmas 3.2.8 and 3.2.9 to bound the error in H after every replacement Building a hierarchy. We classify the edges of T based on their | α|-estimates. This induces a hierarchical classification of nodes into groups, which in turn induces a classification of the edges of T. 2 We emphasize that this entire layering is merely a thought experiment to facilitate the proof.
At the top level of our layering, we classify an edge (i, j) of T as a T T T-road if α ij ≥ 1 − 10 2 n . The T-roads cluster the n nodes into connected components, each of which is called a city. An edge (i, j) of T with i, j belonging to the same city is classified as a T T T-road. We can prove the following structural results. Lemma 3.2.13 says that each city is not only spanned by the T-roads in it (this is by definition), but also spanned by the T-roads in it. Intuitively, the T-roads and T-roads are so strong that within each city it doesn't make much difference (in terms of H 2 ) if the nodes were connected by T-roads or by T-roads. Later, we will replace the set of all T-roads with the set of all T-roads in a single round of edge replacement in the process of going from T to T.
For the next level of our layering, we classify an edge (i, j) of T as a T T T-highway if 1 2 ≤ α ij < 1 − 10 2 n . The T-highways cluster the cities into bigger connected components, each of which is called a country. An edge (i, j) of T with i, j belonging to different cities in the same country is classified as a T T T-highway. We can prove the following structural results. Proof. (sketch of the "only if" direction). Suppose for the sake of contradiction that (i, k) is a T-highway between cities C and D, and that there is no edge of T between C and D (any such edge would in fact be classified as a T-highway because C and D are clearly different cities in the same country). Then, the path in T between i and k must contain some j that belongs to neither C nor D. Since | α ik | ≥ 1 2 , by 3-consistency |α ik | ≥ 1 2 − 1 n in the proof sketch above for a precise version that takes estimation errors into account. Lemma 3.2.14 says that the T-highways and T-highways can be matched into parallel pairs, where each parallel pair consists of a T-highway and a T-highway going between the same pair of cities (in the same country). Later, we will replace the set of all T-highways with the set of all T-highways in a single round of edge replacement in the process of going from T to T.
For the next level of our layering, we classify an edge (i, j) of T as a T T T-railway if 2 √ n ≤ α ij < 1 2 .
The T-railways cluster the countries into bigger connected components, each of which is called a continent. An edge (i, j) of T with i, j belonging to different countries in the same continent is classified as a T T T-railway. We can prove the following structural results.   The proof of Lemma 3.2.17 is similar to that of Lemma 3.2.14. The lower threshold 2 √ n in the criterion for T-railways has been chosen in view of Lemma 3.2.7 and Lemma 3.2.16 so that Lemma 3.2.17 will work. We want to roughly aim for Ä lower threshold for T-railways Lemma 3.2.17 says that the T-railways and T-railways can be matched into parallel pairs, where each parallel pair consists of a T-railway and a T-railway going between the same pair of countries (in the same continent). Later, we will replace the set of all T-railways with the set of all T-railways in a single round of edge replacement in the process of going from T to T. At the bottom layer, we classify the remaining edges of T as T T T-airways, and the remaining edges of T as T T T-airways. Those are edges that go between different continents. Intuitively, the T-airways and T-airways are so weak (with α-value O √ n ) that it doesn't make much difference (in terms of H 2 ) if the continents were linked together with each other by T-airways or by T-airways. In fact, those edges can be cut (i.e. change the α-value to 0) without incurring too much error. Later, we will replace the set of all T-airways with the set of all T-airways in a single round of edge replacement in the process of going from T to T.

Summary of layering.
To summarize, the edges of T are classified into T-roads, T-highways, T-railways, and T-airways based on their | α|-estimates. The n nodes are clustered into cities by the T-roads, which are further clustered into countries by the T-highways, which are further clustered into continents by the T-railways, which are finally linked into one component by the T-airways. This hierarchical classification of nodes into groups then induces a classification of the edges of T: an edge of T is classified as a T-road if its two end-nodes belong to the same city, a T-highway if its two end-nodes belong to different cities in the same country, a T-railway if its two end-nodes belong to different countries in the same continent, or a T-airway if its two end-nodes belong to different continents.
Note that each city, country, or continent is T-connected by definition. We can prove that every city, country, or continent is also T-connected. Furthermore, we can prove that the T-highways and T-highways can be matched into parallel pairs, that is, there is a T-highway between two cities if and only if there is a T-highway between them. The same goes for railways: there is a T-railway between two countries if and only if there is a T-railway between them. One consequence of everything we stated so far is that the exact same clusters (i.e. cities, countries, or continents) at each level of the hierarchy would have been achieved if we were to cluster the n nodes first by T-roads, then T-highways, then T-railways, and finally T-airways.
For a diagrammatic illustration of our structural results see Figure 5. The solid connections represent edges of T, and the dashed connections represent edges of T. The thickness of the line increases as we go down in the hierarchy, with the roads being the thinnest and the airways being the thickest. The circles represent the cities, the rectangular boxes represent the countries, and the saw-toothed regions represent the continents. Note that the T-highways and T-highways can be matched into parallel pairs, each going between the same pair of cities (in the same country). An example is (1, 2) and (3,4). Similarly, the T-railways and T-railways can be matched into parallel pairs, each going between the same pair of countries (in the same continent). An example is (5, 6) and (7,8). This parallelism needs not hold for roads and airways. For example, there is no T-airway that goes between the same pair of continents as the T-airway (9, 10) does, and there is no T-airway that goes between the same pair of continents as the T-airway (11,12) does.
Putting everything together. We are now ready to bound d TV (P, Q). Recall that P (4) was defined as the distribution with underlying tree T and α-value equal to α ij for every edge (i, j) in T. We already argued that d TV (P (4) , Q) ≤ O( ), so it suffices to bound H(P, P (4) ) (remember d TV is upper bounded by √ 2 times H). There will be four rounds of edge replacements to go from T to T. Starting with T, first we replace the set of all T-airways by the set of all T-airways, then replace the set of all T-railways by the set of all T-railways, then replace the set of all T-highways by the set of all T-highways, and finally replace the set of all T-roads by the set of all T-roads (as will soon be seen, it is crucial that we do those edge replacements in a bottom-up fashion, starting with the airways and ending with the roads). This creates three intermediate distributions P (1) , P (2) , P (3) between P and P (4) . The underlying trees of P (1) , P (2) , P (3) are various hybrids between T and T (for example, the underlying tree of P (2) consists of the T-roads, the T-highways, the T-railways, and the T-airways). For each of these distributions the α-value for each edge (i, j) of its underlying tree is α ij .
To bound H(P, P (1) ), we perform one sub-step in which we "cut" all the T-airways (i.e. change their α-values to 0) so that the continents become mutually independent, and another step in which we "install" all the T-airways. For each of those two sub-steps, we apply Corollary 2.5.4 with A 1 , . . . , A Λ being the continents. The potentially nonzero terms on the right hand of (3) in Corollary 2.5.4 are those in the second summand, with the W λµ 's corresponding to the T-airways for the first sub-step, and to the T-airways for the second sub-step. By Lemma 3.2.19, every T-airway or T-airway has |α|-value O √ n . It can be shown that (see To bound H(P (1) , P (2) ), we apply Corollary 2.5.4 with A 1 , . . . , A Λ being the countries. The potentially nonzero terms on the right hand side of (3) in Corollary 2.5.4 are those in the second summand, each of which corresponds to switching between a parallel pair of T-railway and T-railway that go between the same pair of countries (W λµ is the set of endpoints of those two railways). By Lemma 3.2.9 (or Lemma 3.2.8 if the parallel pair of railways share an end-node), each such switch costs us O Ä 2 n ä in H 2 . Note that those lemmas are indeed applicable because each country is both T-connected and T-connected, and that the edges within each country haven't been replaced yet and are still edges of the true tree T; here we see that it is crucial to replace the edges from the bottom layer to the top layer). So overall we lose O( ) in H in this round. The bounding of H(P (2) , P (3) ) is similar; we apply Corollary 2.5.4 with A 1 , . . . , A Λ being the cities. Finally, to bound H(P (3) , P (4) ), we first "tighten" all the T-roads (i.e. turn their α-values to 1 or −1 depending on which is closer). At this point we can equivalently think of each city as being held together by the T-roads in it with appropriately chosen 1 or −1 as α-values. We then "relax" all the T-roads back to their original α-values. For each of those two sub-steps we apply Corollary 2.5.4 with A 1 , . . . , A Λ being the individual nodes. The potentially nonzero terms on the right hand of (3) in Corollary 2.5.4 are those in the second summand, with the W λµ 's corresponding to the T-roads for the first sub-step, and to the T-roads for the second sub-step. Every T-road or T-road has |α|-value that is 1 − O Ä 2 n ä . It can be shown that (see

The Detailed Proof of the Symmetric Case
We present the detailed proof of Theorem 3.0.3, following the steps sketched in Section 3.1. Throughout the section, we assume that P satisfies 3-consistency, and our goal is to demonstrate that under this condition, Algorithm 2 will compute a distribution Q satisfying d TV (P, Q) ≤ O ( ). Section 3.2.1 contains a collection of lemmas each involving a small number (2, 3, or 4) of variables. Section 3.2.2 contains structural results on the relation between T and T, stated in the language of various hierarchies to be defined at the beginning of that section. The layers defined here dictate how we switch from T to T in the hybrid argument later. Section 3.2.3 proves the desired bound in total variation distance between P and Q with the aid of a few intermediate hybrid distributions. Throughout the section we assume ≤ 1 10 (it's easy to see that it suffices to deal only with sufficiently small ).

Lemmas on 2, 3, or 4 Variables
This subsection includes a collection of lemmas each involving a small number (2, 3, or 4) of variables that form the basis of our analysis later of more complex structures (e.g. those of T and T) and distributions.
Our first lemma indicates the degree to which P can be gauranteed to approximate P on events involving (up to) 3 variables, as a consequence of assuming 3-consistency. (ii) If P(X S ∈ W) ≤ 10 2 n , then P(X S ∈ W) − P(X S ∈ W) ≤ 1 2 2 n ; (iii) If P(X S ∈ W) ≤ 5 2 n , then P(X S ∈ W) − P(X S ∈ W) ≤ 1 2 2 n . Proof. To prove (i), note that 3-consistency implies To prove (ii), note that if P(X S ∈ W) ≤ 10 2 n , then 3-consistency implies To prove (iii), assume P(X S ∈ W) ≤ 5 2 n . If we were to have P(X S ∈ W) ≥ 10 2 n , then 3-consistency implies and so leading to P(X S ∈ W) > 5 2 n , a contradiction. Thus, we must have P(X S ∈ W) ≤ 10 2 n , and we can apply (ii). The next lemma indicates the degree to which α ij can be guaranteed to approximate α ij . It follows from Lemma 3.2.1 and the fact that α ij and α ij are simply linear transformations of the probabilities of the event "X i = X j " (or the event "X i = −X j ") under P and P, respectively.
and (i) follows from Lemma 3.2.1 (i).
The next lemma bounds the H 2 between a pair of variables i, j with α-value α ij and the same pair of variable with α-value 0. It is the error in H 2 when we "cut" an edge with α-value α ij . P ij -the binary symmetric distribution for X i , X j with α-value α ij ; P (ind) ij -the independent binary symmetric distribution for X i , X j , i.e. α-value 0.
Proof. We have the following: Thus, we have where ( * ) follows from the fact that The next lemma bounds the H 2 between a pair of variables i, j with α-value α ij and the same pair of variable with α-value 1 or −1, whichever is closer to α ij . It is the error in H 2 when we "tighten" an edge with α-value α ij .

Lemma 3.2.4. Fix any i, j ∈ [n]. Consider the following pair of distributions:
P ij -the binary symmetric distribution for X i , X j with α-value α ij ; where sgn(t) equals 1 for t ≥ 0, and −1 otherwise. Then H 2 (P ij , P Assume α ij ≥ 0 (the case α ij < 0 follows symmetrically). We have Thus, by Lemma 2.5.2 we have which is exactly what we want.
The next lemma bounds the H 2 between a pair of variables i, j with α-value α ij and the same pair of variable with α-value α ij .

Lemma 3.2.5. Fix any i, j ∈ [n]. Consider the following pair of distributions:
P ij -the binary symmetric distribution for X i , X j with α-value α ij ; P (est) ij -the binary symmetric distribution for X i , X j with α-value α ij .
, we have the following: where ( * ) follows from 3-consistency and Lemma 2.7.3.
For any i, j, k that lie on a path in T, the next lemma bounds the H 2 between the true distribution on those three nodes (i.e. P ijk ) and the alternative distribution if i were to be mistakenly regarded as closer to k than to j (i.e. P ij−k ). See Definition 2.6.1 for definitions of symbols such as P ij−k ). See Figure 2 in Section 3.1 for a depiction of those two distributions.
So, in either case, we have This is exactly what we want.
For any i, j, k that lie on a path in T, the multiplicativity of α-values along a path (Lemma 2.4.2) implies that α ik = α ij α jk is no greater in absolute value than either α ij or α jk . Algorithm 2 may "reverse the order" The following lemma characterizes when this can possibly happen (assuming 3-consistency).
Proof. Let δ jk = 1 − α jk . Assume α ij ≥ 0, α jk ≥ 0 (the other three cases follow symmetrically). Note that this implies α ik = α ij α jk ≥ 0. If either α ij ≤ √ n or δ jk ≤ 2 n , the conclusion obviously holds. So for the rest of the proof we assume both Consider the following identities: The cancelation of the term P(X i = X j , X j = X k ) during the last step is crucial, as it allows us to apply 3-consistency to events with smaller probability masses under P, thereby obtaining tighter bounds (the argument below wouldn't have worked if we were to stop at the penultimate line of (6) and apply 3consistency to the events "X i = X j " and "X i = X k ") . We have since we assumed δ jk ≥ 2 n , and similarly which, together with α ij − α ik ≤ 0, implies α 2 ij δ jk ≤ 4 25 2 n < 2 n . This is exactly what we want.
Lemma 3.2.7 is important because it tells us, at least for the setting of three nodes lying on a path in T, when it's possible for Algorithm 2 to make a structural mistake and when it's not. It will serve as a guideline on how to classify the edges and define the layers in Section 3.2.2 (which allows us to speak more precisely about the manners in which T might differ from T). Furthermore, when combined with Lemma 3.2.6, it bounds the error in H 2 if Algorithm 2 does make a mistake in inferring the structure in the setting of three nodes lying on a path in T, as the following lemma shows.
Proof. This follows directly from Lemma 3.2.6 and Lemma 3.2.7.
We also have the following four-node version of Lemma 3.2.8 (see Figure 3 in Section 3.1 for a depiction of the two distributions involved): Proof. The proof is analogous to that of Lemma 3.2.8 through Lemma 3.2.6 and Lemma 3.2.7.
Assume α hi ≥ 0, α ij ≥ 0, α jk ≥ 0 (the other seven cases follow symmetrically). Note that this implies α hk = α hi α ij α jk ≥ 0. For ease of notation, let We have by Lemma 2.6.3 To rest of our job is to prove We break α ij − α hk into the sum of α ij − α ik and α ik − α hk , and deal with them separately. For α ij − α ik , we can obtain in a similar way as in (6), (7), (8), (9) in Lemma 3.2.7 (remembering our n . For α ik − α hk , we can obtain in a similar way (but working with k, i, h instead) that n . Adding up the two bounds, we get

Hierarchies and Structural Results for T vs. T
This subsection contains structural results on the relation between T and T, stated in the language of various hierarchies to be defined first. The layers we define here dictate how we switch from T to T in the hybrid argument for bounding d TV (P, Q) in the next subsection.
Recall that T is a maximum weight spanning tree with respect to the | α|-estimates (Line 4 of Algorithm 2). We first classify all the edges of T based on their | α|-estimates. This induces a hierarchical classification of nodes into groups, which in turn induces a classification of the edges of T.

Definition 3.2.10 (Hierarchies).
We establish the following hierarchies, starting with the empty graph G on [n] and adding edges incrementally: n is classified as a T T T-road. Adding the T-roads to G links the n nodes into connected components, each of which is called a city. An edge (i, j) of T with i, j belonging to the same city is classified as a T T T-road.
n is classified as a T T T-highway. Adding the T-highways to G further links the cities into bigger connected components, each of which is called a country. An edge (i, j) of T with i, j belonging to different cities in the same country is classified as a T T T-highway.
• An edge (i, j) of T with 2 √ n ≤ α ij < 1 2 is classified as a T T T-railway. Adding the T-railways to G further links the countries into even bigger connected components, each of which is called a continent. An edge (i, j) of T with i, j belonging to different countries in the same continent is classified as a T T T-railway.
• An edge (i, j) of T with α ij < 2 √ n is classified as a T T T-airway. Adding the T-airways to G further links the continents into one single connected component of all n nodes. An edge (i, j) of T with i, j belonging to different continents is classified as a T T T-airway.
Our first lemma shows that each T-road or T-road must be strong, in the sense that its |α|-value must be close to 1. In other words, its two end-nodes are either almost always equal or almost always unequal under P. This will enable us to prove that within a city it doesn't matter much in terms of H 2 whether the nodes are held together by the T-roads in the city or by the T-roads in the city.
n according to Definition 3.2.10, and so α ij ≥ 1 − 11 2 n by Lemma 3.2.2 (iii). Suppose (i, j) is a T-road. Imagine removing (i, j) from T. This partitions [n] into two T-connected subsets U and V, with i ∈ U and j ∈ V. By Definition 3.2.10, i, j belong to the same city, which is T-connected. So all the edges on the path in T between i and j are T-roads. At least one of those T-roads goes between U and V. Say (h, k) does, with h ∈ U and k ∈ V. Then, h, i, j, k lie on a path in T, and we have α hk = α hi α ij α jk by Lemma 2.4.2. We already proved that |α hk | ≥ 1 − 11 2 n . As a result, α ij ≥ 1 − 11 2 n .
The following lemma can be seen as a partial converse to Lemma 3.2.11. Lemma 3.2.12. If i, j belong to different cities, then α ij < 1 − 9 2 n .
Proof. Suppose for the sake of contradiction that α ij ≥ 1 − 9 2 n . By Lemma 3.2.2 (ii), we have α ij ≥ 1 − 10 2 n . Consider the path in T between i and j. By the cycle property of maximum weight spanning trees, each edge on that path must have an | α|-estimate at least that of α ij ≥ 1 − 10 2 n , and is therefore classified as a T-road according to Definition 3.2.10. Consequently, i and j must belong to the same city, a contradiction.
Obviously, every city is T-connected by definition. We show that it is also T-connected. Intuitively, this means that we can regard every city as a "supernode" in the context of both T and T.

Lemma 3.2.13. Every city is T-connected.
Proof. We want to show that for a city C and i, j ∈ C, all the nodes on the path in T between i and j are in C. Since any two nodes in the same city are linked by a series of T-roads, it suffices to argue only for the case Suppose the path in T between i and j consists of i = i 0 , i 1 , . . . , i r = j, in that order. Then we have holds whenever 2 n < 7 81 , which is satisfied because we assumed ≤ 1 10 . As a result, (10) implies that α i s i s+1 ≥ 1 − 9 2 n for all but at most one index s. By Lemma 3.2.12, i s and i s+1 belong to the same city, for all but at most one index s. Consequently, for any s, either i 0 , . . . , i s all belong to the same city, or i s , . . . , i r all belong to the same city. Either case leads to the desired conclusion that i s ∈ C, because i 0 = i and i r = j are both in C.
Our next goal is to emulate Lemma 3.2.13 and prove that every country is T-connected (it is obviously T-connected by definition). In fact, we show something stronger in the next lemma, the proof of which also explains the choice of the lower threshold 1 2 in the criterion for a T-highway.

Lemma 3.2.14.
There is a T-highway between a pair of cities if and only if there is a T-highway between the same pair of cities.
Proof. First, we prove that if there is a T-highway between a pair of cities, then there is a T-highway between the same pair of cities. Suppose for the sake of contradiction that (i, k) is a T-highway between cities C and D, with i ∈ C and k ∈ D, such that there is no T-highway between C and D. Note that C and D are different cities in the same country, because they are linked together directly by the T-highway (i, k). Consequently, there must exist no edge of T at all between C and D, because any such edge would have been classified as a T-highway according to Definition 3.2.10.
As a result, the path in T between i and k must contain some j that belongs to neither C nor D. Since (i, k) is an edge of T, either k sits on the path in T between i and j, or i sits on the path in T between k and j. Without loss of generality we assume it is the former case. Then, by the cycle property of maximum weight spanning n . On the other hand, since (i, k) is a T-highway, we have | α ik | ≥ 1 2 according to Definition 3.2.10, and so Also, since j, k belong to different cities, Lemma 3.2.12 implies α jk < 1 − 9 2 n . As a result, (recall that ≤ 1 10 ), a contradiction.
Next, we prove that if there is a T-highway between a pair of cities, then there is a T-highway between the same pair of cities.
Suppose for the sake of contradiction that (i, j) is a T-highway between cities C and D, with i ∈ C and k ∈ D, such that there is no T-highway between C and D. According to Definition 3.2.10 the fact that (i, j) is a T-highway implies that C and D are different cities in the same country. Since there is no T-highway between C and D, according to Definition 3.2.10 there must exist a sequence of distinct cities C = C 0 , C 1 , . . . , C r = D, r ≥ 2, such that there is a T-highway between C s and C s+1 for each s. By the only if part of this Lemma that we already established, there is a T-highway between C s and C s+1 for each s. Since each C s is T-connected by Lemma 3.2.13, it is easy to see that there is a path in T between i and j that visits the cities C = C 0 , C 1 , . . . , C r = D, in that order. On the other hand, (i, j) by itself constitutes another path in T between i and j. So we have more than one paths in T between i and j, contradicting the fact that T is a tree. Now we can easily prove that every country is T-connected.

Lemma 3.2.15. Every country is T-connected.
Proof. Recall that a country consists of a collection of cities linked together by T-highways. Its T-connectedness then follows from Lemma 3.2.13 and Lemma 3.2.14.
The following lemma is the country-level version of Lemma 3.2.12.
Proof. Suppose for the sake of contradiction that Consider the path in T between i and j. By the cycle property of maximum weight spanning trees, each edge on that path must have an | α|-estimate at least that of α ij ≥ 1 2 , and is therefore classified either as a T-road or as a T-highway, according to Definition 3.2.10. In either case, the two end-nodes of that edge belong to the same country. Consequently, i and j must belong to the same country, a contradiction.
The next three lemmas parallelize the three previous lemmas but are one layer lower in the hierarchy. Proof. First, we prove that if there is a T-railway between a pair of countries, then there is a T-railway between the same pair of countries.
Suppose for the sake of contradiction that (i, k) is a T-railway between countries C and D, with i ∈ C and k ∈ D, such that there is no T-railway between C and D. Note that C and D are different countries in the same continent, because they are linked together directly by the T-railway (i, k). Consequently, there must exist no edge of T at all between C and D, because any such edge would have been classified as a T-railway according to Definition 3.2.10.
As a result, the path in T between i and k must contain some j that belongs to neither C nor D. Since (i, k) is an edge of T, either k sits on the path in T between i and j, or i sits on the path in T between k and j. Without loss of generality we assume it is the former case. Then, by the cycle property of maximum weight spanning n according to Definition 3.2.10, and so |α ik | ≥ 9 5 √ n by Lemma 3.2.2 (i), which implies α ij ≥ 9 5 √ n since α ik = α ij α jk . Also, since j, k belong to different countries, Lemma 3.2.16 implies α jk < 1 2 + 1 n (recall that ≤ 1 10 ), a contradiction. Next, we prove that if there is a T-railway between a pair of countries, then there is a T-railway between the same pair of countries.
Suppose for the sake of contradiction that (i, j) is a T-railway between countries C and D, with i ∈ C and k ∈ D, such that there is no T-railway between C and D. According to Definition 3.2.10 the fact that (i, j) is a T-railway implies that C and D are different countries in the same continent. Since there is no T-railway between C and D, according to Definition 3.2.10 there must exist a sequence of distinct countries C = C 0 , C 1 , . . . , C r = D, r ≥ 2, such that there is a T-railway between C s and C s+1 for each s. By the only if part of this Lemma that we already established, there is a T-railway between C s and C s+1 for each s. Since each C s is T-connected by Lemma 3.2.15, it is easy to see that there is a path in T betwenn i and j that visits the countries C = C 0 , C 1 , . . . , C r = D, in that order. On the other hand, (i, j) by itself constitutes another path in T between i and j. So we have more than one paths in T between i and j, contradicting the fact that T is a tree.  Proof. Suppose for the sake of contradiction that α ij ≥ 11 Consider the path in T between i and j. By the cycle property of maximum weight spanning trees, each edge on that path must have an | α|-estimate at least that of α ij ≥ 2 √ n , and is therefore classified as a T-road, a T-highway, or a T-railway according to Definition 3.2.10. In any case, the two end-nodes of that edge belong to the same continent. Consequently, i and j must belong to the same continent, a contradiction.
For a summary of the structural results proved in this section, as well as a diagrammatic illustration, see the part that begins with "Summary of layering" in Section 3.1.

Bounding the Distance between P and Q
This subsection puts together everything we have so far and proves the desired bound in total variation distance between P and Q.
As outlined in Section 3.1, we need a few hybrid distributions to serve as intermediate steps in bounding the total variation distance between P and Q. We first replace the edges of T by the edges of T one layer at a time from the bottom to the top, assigning α-value α ij to each edge (i, j) of the resulting tree after each step to get the hybrid distributions P (1) , P (2) , P (3) , and P (4) . The step going from P (4) to Q keeps the underlying tree fixed at T but changes the α-value of each edge (i, j) of T from α ij to α ij . We now formally specify the underlying tree and the α-values for the tree edges for all the distributions involved: • P: the underlying tree is T; the α-value for each edge (i, j) of T is α ij ; • P (1) : the underlying tree T (1) consists of all the T-roads, T-highways, T-railways, and T-airways; the • P (2) : the underlying tree T (2) consists of all the T-roads, T-highways, T-railways, and T-airways; the : the underlying tree T (3) consists of all the T-roads, T-highways, T-railways, and T-airways; the • P (4) : the underlying tree is T; the α-value for each edge (i, j) of T is α ij ; • Q: the underlying tree is T; the α-value for each edge (i, j) of T is α ij .
We bound the Hellinger distance separately between each adjacent pair in the list above. The desired total variation distance bound between P and Q as stated in Theorem 3.0.3 then follows from the triangle inequality and the fact that d TV is upper bounded by √ 2 times H (Lemma 2.5.2).
Bounding H(P, P (1) ) To bound the Hellinger distance between P and P (1) , we introduce two more binary symmetric tree-structured Bayesnets as intermediate steps: Note that P ( 1 3 ) and P ( 2 3 ) have the same marginal for each continent, and that different continents are mutually independent according to both. So P ( 1 3 ) and P ( 2 3 ) are in fact equal! To bound the Hellinger distance between P and P ( 1 3 ) , we can apply Corollary 2.5.4 with P = P, P = P ( 1 3 ) , T = T = T, and the sets A λ 's being the continents C 1 , . . . , C Λ , to obtain where E contains all (λ, µ) for which C λ and C µ are straddled by a T-airway, and W λµ consists of the two end-nodes of that straddling edge. The first summation on the right hand side of (11) is zero. For a term in the second summation corresponding to (λ, µ) ∈ E , let the T-airway straddling C λ and Since |E | < n, (11) implies H 2 (P, P ( 1 3 ) ) ≤ n · 3 2 n = 3 2 , and so H(P, In a similar fashion we can also get H(P ( 2 3 ) , P (1) ) ≤ √ 3 . In this case we apply Corollary 2.5.4 with P = P ( 2 3 ) , P = P (1) , T = T = T (1) , and the sets A λ 's being the continents C 1 , . . . , C Λ . The only possibly nonzero terms on the right hand side of the resulting inequality correspond to (λ, µ) for which C λ and C µ are straddled by a T-airway.
Overall, we have H(P, P (1) ) ≤ H(P, Bounding H(P (1) , P (2) ) To bound the Hellinger distance between P (1) and P (2) , we can apply Corollary 2.5.4 with P = P (1) , P = P (2) , (2) , and the sets A λ 's being the countries C 1 , . . . , C Λ to obtain where E contains all (λ, µ) for which C λ and C µ are straddled by (1) a T-airway or (2) a T-railway and a T-railway, and W λµ consists of all end-nodes of those straddling edges.
The only possibly nonzero terms on the right hand side of (12) are those in the second summation corresponding to (λ, µ) such that C λ and C µ are straddled by a T-railway and a T-railway. For such a pair (λ, µ), let the T-railway straddling C λ and C µ be (i, j), with i ∈ C λ and j ∈ C µ , and the T-railway straddling C λ and C µ be (h, k), with h ∈ C λ and k ∈ C µ .
First suppose h = i and j = k. In this case, W λµ = {h, i, j, k}, and h, i, j, k lie on a path in T because every country is T-connected. Also, i, h, k, j lie on a path in T because every country is T-connected. So the cycle property of maximum weight spanning trees implies that α ij ≤ | α hk |. Note that P (1) hijk equals P hijk , and P (2) hijk equals P h˚ −i j−k (because the edges within each country haven't been replaced yet and are still edges of the true tree T). By Lemma 3.2.9 we thus have Next suppose h = i and j = k (the case h = i and j = k is symmetric). In this case, W λµ = {i, j, k}, and i, j, k lie on a path in T. It is easy to see that i, k, j lie on a path in T. So the cycle property of maximum weight spanning trees implies that α ij ≤ | α ik |. Note that P (1) ijk equals P ijk , and P (2) ijk equals P ij−k . By Lemma 3.2.8 we thus have This is similar to the bounding between P (1) and P (2) , but centered at the city/highway level of the hierarchy instead of the country/railway level. We apply Corollary 2.5.4 with P = P (2) , P = P (3) , T = T (2) , T = T (3) , and the sets A λ 's being the cities C 1 , . . . , C Λ . The only possibly nonzero terms on the right hand side of the resulting inequality correspond to (λ, µ) for which C λ and C µ are straddled by a T-highway and a T-highway. An analysis parallel to that for the pair P (1) and P (2) leads to H(P (2) , P (3) ) ≤ 3 .

Bounding H(P (3) , P (4) )
To bound the Hellinger distance between P (3) and P (4) , we can apply Corollary 2.5.4 with P = P (3) , P = P (4) , T = T (3) , T = T (4) , and the sets A λ 's being the cities C 1 , . . . , C Λ to obtain where E contains all (λ, µ) for which C λ and C µ are straddled by a T-airway, a T-railway, or a T-highway, and W λµ consists of both end-nodes of that straddling edge. The second summation on the right hand side of (13) is zero. We now focus on a term in the first summation corresponding to λ. Let E C λ be the set of all T-roads in C λ , and E C λ be the set of all T-roads in C λ .
To bound the Hellinger distance between P (3) C λ and P (4) C λ , we introduce two more binary symmetric tree-structured Bayesnets on C λ as intermediate steps: where sgn(t) equals 1 if t ≥ 0, and −1 otherwise.
Also define . . , i r = j be the path in T between i and j. Then we have by Lemma 2.4.2 that x where the multiplicativity of the sgn(·) function holds because none of the arguments is 0 (which is the case because α ij ≥ 1 − 11 2 n > 0 by Lemma 3.2.11 and the fact that ≤ 1 10 ). Since the T-roads in C λ span C λ , we To bound the Hellinger distance between P The first summation on the right hand side of (14) is zero.
For a term in the second summation corresponding to (i, j), note that P ij has α-value α ij , and P n , and so we obtain H(P n . In a similar fashion we can also get H(P n . In this case we apply Corollary 2.5.4 with P = P , T = T = T C λ , and the sets A λ 's being the single-node sets {i}, i ∈ C λ . By the triangle inequality H(P Bounding H(P (4) , Q) To bound the Hellinger distance between P (4) and Q, we can apply Corollary 2.5.4 with P = P (4) , P = Q, T = T = T, and the sets A λ 's being the single-node sets {1}, . . . , {n}, to obtain where E is the set of edges of T.
The first summation on the right hand side of (15) is clearly zero.
Proof of Theorem 3.0.3. Combining the bounds between adjacent pairs from the list of distributions at the beginning of Section 3.2.3, we have by the triangle inequality

The General Case
In this section, we prove our main result for proper learning general binary-alphabet tree-structured Bayesnets. In particular, we show that this is achieved by the Chow-Liu algorithm using the plug-in estimator for estimating all required mutual information quantities (or equivalently, by running the Chow-Liu algorithm on the empirical joint distribution induced by the samples). We prove our main result, which is stated as Theorem 1.0.1 in the introduction and restated as Theorem 4.0.1 below. (Our claim about the sample optimality of the algorithm, up to a constant factor, which appears in the statement of Theorem 1.0.1 and follows from [14] as discussed in the introduction, will not be discussed in this section.) Throughout Section 4, we reserve the symbol P to represent the unknown binary tree-structured Bayesnet on X 1 , . . . , X n that we wish to properly learn. The dimension of P is n. We reserve T to represent the true (but unknown) underlying tree of P.
The Chow-Liu Algorithm, using the plug-in estimator for estimating mutual information, is presented in the introduction as Algorithm 1 and restated below in a more detailed form. See Section 2.3 for a discussion on specifying a (binary-alphabet) tree-structured Bayesnet.

Algorithm 1: FINITE SAMPLE CHOW-LIU ALGORITHM FOR PROPER LEARNING OF A BINARY-ALPHABET TREE-STRUCTURED BAYESNET
Input: , γ ∈ (0, 1] Output: specification for a binary tree-structured Bayesnet Q, approximating P 2 Let P be the empirical joint distribution for X 1 , . . . , X n constructed from the m samples, so that , ∀(i, j). 4 Run Kruskal's algorithm to find a maximum weight spanning tree T of the complete graph on [n] with weight I P (X i ; X j ) for (i, j). (1) T as Q's underlying tree, (2) P ij as Q's marginal for the pair X i , X j , for each edge (i, j) of T.

return
Throughout this section, we will also reserve the symbols P, T, and Q for the respective meanings they carry in Algorithm 1. Our main result for Algorithm 1 is the following: Theorem 4.0.1. There exists B > 0 such that for any , γ ∈ (0, 1], Algorithm 1 specifies a binary tree-structured Bayesnet Q such that d TV (P, Q) ≤ , with error probability at most γ.
In fact, we establish something stronger and perhaps surprising. We show that Algorithm 1 is successful as long as the empirical distribution P satisfies a deterministic criterion, presented below.
It is said to satisfy strong 4-consistency if furthermore whenever P(X S ∈ W) < 2 n we also have The criterion (16) of Definition 4.0.2 specifies that P well-approximates the true distribution P for all events involving up to 4 variables, and the criterion (17) is a strengthening of (16) for events (involving up to 4 variables) that have small probabilities under P. Some concrete examples of the event "X S ∈ W" in Definition 4.0.2 are "X h = −1, X i = X j = X k ", "X i = −X j , X j = X k ", and "X h = X i = 1". For example, "X i = −X j , X j = X k " is expressed by taking S = {h, i, j, k} (where h is any index other than i, j, k) and We show that whenever the samples provided to Algorithm 1 induce P which satisfies strong 4consistency, the algorithm succeeds (up to a constant), as per the following theorem.

Outline of the Proof
In this section, we outline our proof for the general case. The proof that the Chow-Liu algorithm (Algorithm 1) succeeds in properly learning arbitrary binary tree-structured Bayesnets employs the same basic ideas -namely, the squared Hellinger subadditivity and layering -as our proof that the Chow-Liu variant (Algorithm 2) succeeds in the symmetric case, given in Section 3. However, the general case involves a few new challenges and the argument is much more complicated. Our proof sketch in this section will be less detailed than the proof sketch in Section 3.1 for the symmetric case, and we will focus mainly on the new challenges encountered in the general case and the necessary modifications required, as compared to the symmetric case. All lemmas presented in this section are restated copies of lemmas with the same label stated and proved in Section 4.2, which includes the full proof for the general case.

The deterministic condition for the success of Chow-Liu.
Recall that when analyzing Algorithm 2 in the symmetric case we were able to identify a deterministic condition on the relationship between P and P, called 3-consistency, that holds with probability at least 1 − γ for a run of Algorithm 2 (for a big enough constant B) and that can be shown to imply the desired bound d TV (P, Q) ≤ O ( ). Roughly speaking, 3-consistency says that P and P assign similar probabilities to all events involving up to three variables. For the general case we need something a bit stronger. First, we need precision guarantees for events involving up to four variables. See (16) in Definition 4.0.2. We call it 4-consistency. But even that is not enough. Recall that Algorithm 1 uses the plug-in estimator to estimate mutual informations, based on which it runs Kruskal's Algorithm to infer the underlying tree. Naturally, we need to ensure that the estimated mutual informations are close to the actual mutual informations. However, each term in the expression for an estimated mutual information involves the appearances of estimated probabilities in the denominator (inside the logarithm), and so the value of such a term is particularly sensitive to the estimation error of a probability whose estimate appears in the denominator if this probability is small. Thus, we need an extra condition that places more stringent precision requirements on events involving up to 4 variables that have small probabilities under P. See (17) in Definition 4.0.2. We call the combination of (16) and (17) strong 4-consistency. It can be shown that strong 4-consistency holds with probability at least 1 − γ for a run of Algorithm 1 (for a big enough constant B), and is sufficient to guarantee the success of the algorithm. Note that strong 4-consistency is still made up of conditions that each involves only a constant number (i.e. 4) of variables, so in some sense it is still "local". From now on we assume that P satisfies strong 4-consistency.
The core of the argument. As in the symmetric case, the main challenge is to control the error as a result of structural mistakes (i.e. incorrectly learned edges), as opposed to "parameter mistakes" (i.e. placing the estimated pairwise distribution P ij rather than the actual pairwise distribution P ij on each edge (i, j) of the tree T of the output distribution Q). So we focus on bounding the distance between P on one hand, and the hybrid distribution with underlying tree T but with the correct marginal P ij assigned to each edge (i, j) of T, on the other. After getting from T to T in the sense just described, the remaining error due to the "parameter mistakes" (that is, having P ij versus having P ij on each edge (i, j) of T) can be dealt with easily via a single application of Corollary 2.5.4. 3 As will be seen, we will go from T to T in a constant number of rounds 4 where in each round we either "cut" a set of edges, "install" a set of edges, or replace a set of edges by another, resulting in a sequence of forests interpolating between T and T. For each forest in the sequence, we define a hybrid distribution that is a Bayesnet with that forest as underlying graph and with P ij assigned to each edge (i, j) of the forest. 5 This yields a sequence of hybrid distributions interpolating between P on one hand, and the hybrid distribution with underlying tree T and with P ij assigned to each edge (i, j) of T, on the other. We will be able to prove that the total variation distance between any adjacent pair in this sequence of hybrid distributions is small, and the tool we will rely on to establish every such bound is, unsurprisingly, Corollary 2.5.4. The edges we "cut", "install", or swap at each of the rounds will be carefully choosen based on classifications of the edges of T and T into layers, in order to ensure that Corollary 2.5.4 is indeed applicable and that the error introduced is indeed small. This is all quite similar to the symmetric case. The rest of our discussion focuses on the realization of the program outlined in this paragraph.
As in the symmetric case, in order to obtain some guidance on how to classify the edges and define the layers (which allows us to speak more precisely about the manners in which T might differ from T, and which dictates the edges we "cut", "install", or swap in going from T to T), as well as to bound the error in H 2 incurred by swapping edges, we need to answer (1) when can Algorithm 1 possibly make a structural mistake and (2) what is the error in H 2 if Algorithm 1 does make a structural mistake, for the modest case of i, j, k lying on a path in T (assuming strong 4-consistency). In this case, a structural mistake is made when Algorthm 1 prioritizes (i, k) over (i, j) or prioritizes (i, k) over (j, k). Let's focus on it prioritizing (i, k) over (i, j) (as the other case is symmetric), which may happen when P is such that I P (X i ; X j ) ≤ I P (X i ; X k ) (note that I P (X i ; X j ) ≥ I P (X i ; X k ) by the data processing inequality).
Recall that for the symmetric case the first question above is answered by Lemma 3.2.7, which provides a necessary condition on α ij and α jk (i.e. α 2 ij (1 − α jk ) ≤ 2 n ) for Algorithm 2 to make the structural mistake. Combined with Lemma 3.2.6 (which says H 2 (P ijk , P ij−k ) ≤ 2α 2 ij (1 − α jk )), it yields a bound on the error in H 2 when Algorithm 2 does make the structural mistake, answering the second question above. See Lemma 3.2.8, as well as the four-node version Lemma 3.2.9.
For analyzing Algorithm 1 for the general case the following lemma is central to answering the questions above. The proof of this lemma is the only place in the entire argument where we need those implications of strong 4-consistency that are beyond those implied by just 3-consistency. Lemma 4.2.14.
(i) If i, j, k lie on a path in T, and I P (X i ; X j ) ≤ I P (X i ; X k ), then H 2 (P ijk , P ij−k ) ≤ 22 2 n .
Proof. (sketch of (i) showing only the main steps and without paying attention to the specific constants). We expand I P (X i ; X j , X k ) using the chain rule for mutual information in two different ways: 3 See the passage entitled "Long hybrid arguments vs squared Hellinger subadditivity" in Section 3.1 for an explanation on why it is important to use the squared Hellinger and its subadditivity in situations like this, even though our ultimate goal is to bound the error in total variation distance. 4 See the passage entitled "The challenges of going deeper" in Section 3.1 for a discussion (applicable also to the general case here) of why it is important that the number of rounds is constant. 5 More specifically, it is the distribution under which the set of variables corresponding to each connected component of the forest are distributed according to a tree-structured Bayesnet with underlying tree being that connected component, and with P ij assigned to each edge (i, j) of that connected component; furthermore, the sets of variables corresponding to different connected components of the forest are mutually independent. Note that, in Section 2 we did not formally define forest-structured Bayesnets, as these can easily be seen to be special cases of tree-structured Bayesnets, and our formal proof later we will do everything in terms of tree-structured Bayesnets. We speak of forest-structured Bayesnets here only, for the sake of intuition. and I P (X i ; X j , X k ) = I P (X i ; X k ) + I P (X i ; X j |X k ).
Comparing the two we see that I P (X i ; X j ) ≤ I P (X i ; X k ) implies I P (X i ; X k |X j ) ≥ I P (X i ; X j |X k ).
Notice that i, j, k lying on a path in T implies that I P (X i ; X k |X j ) = 0. Using strong 4-consistency we can show that I P (X i ; X k |X j ) is also close to 0. More precisely, we can show that I P (X i ; (the first inequality is in fact generally true with any joint distribution taking the place of P, and any i, j, k not necessarily lying on a path in T).
. Using strong 4-consistency we can also show that H 2 (P ijk , P ijk ) ≤ O Ä 2 n ä and (in fact just 3-consistency is enough here). Taking square roots and applying triangle inequality for Hellinger distance, we get A full proof of this lemma can be found in Section 4.2.1.
Notice that Lemma 4.2.14 (i) fully answers the second question above, i.e. "what is the error in H 2 if Algorithm 1 makes a structural mistake?" The answer is 22 2 n . It also partially answers the first question, i.e. "when can Algorithm 1 possibly make a structural mistake?" The answer is that, if H 2 (P ijk , P ij−k ) > 22 2 n , then Algorithm 1 cannot possibly prioritize (i, k) over (i, j). We only say "partially" because we would like the answer to be stated in terms of conditions on pairwise distributions P ij and P jk rather than three-wise distributions, as ultimately we want to use those conditions as guidance to classify the individual edges of T into layers. (Indeed, recall that this is what we did in the symmetric case, by utilizing Lemma 3.2.7, which provided a necessary condition for a structural mistake involving only α ij and α jk .) Thus, we want to find conditions involving only P ij and P jk that would guarantee H 2 (P ijk , P ij−k ) > 22 2 n . To state these conditions, we define a few useful measures on (binary) pairwise distributions. It is easier to motivate the definitions of our measures in parallel with looking for reasonable ways to define the layers via a classification of the edges of T. We proceed to do this next.
The problem of using (estimated) mutual information to classify the edges of T. Recall that, in the symmetric case, the edges of T are classified into layers based on their | α|-estimates. Indeed, the | α|-estimates serve both as the edge-weights for computing the maximum weight spanning tree T in Algorithm 2, and as the measure according to which we classify the edges of T. The situation is different in the general case: while the estimated mutual informations are used by Algorithm 1 (the Chow-Liu algorithm) as edge-weights in computing the maximum weight spanning tree T, they cannot be used for classifying the edges of T.
To see why, note that, to mimic what we did in the symmetric case, in the top layer of our layering we want to group edges of T whose two end-nodes are almost always equal or almost always unequal (under P), as doing so will allow us to prove that within each group of the top layer it doesn't matter much in terms of H 2 whether the nodes are held together by edges of T or by edges of T (so we can swap between the two configurations without incurring too much error). More precisely, we want to identify edges whose two end-nodes are equal with probability at least 1 − Θ Ä 2 n ä , or unequal with probability at least 1 − Θ Ä 2 n ä . However, unlike the symmetric case in which a pair of nodes are almost always equal or almost always unequal if and only if the |α|-value (and therefore the | α|-estimate) for the pair is close to one, for the general case a pair of nodes that are almost always equal or almost always unequal could have (estimated) mutual information that lies anywhere between 0 and ln 2, depending on the degree of bias of the individual node marginals. Indeed, if X i and X j are always equal, and each assumes 1 with probability p, then as p goes from 0 to 1 2 the mutual information between X i and X j goes from 0 to ln 2. Thus, if we set the estimated mutual information threshold for the top layer of edges close to the higher end (say at some ln 2 − Θ Ä 2 n ä threshold), then we would miss edges whose end-nodes are slightly biased but are nevertheless almost always equal or almost always unequal to each other. On the other hand, if we set the estimated mutual information threshold for the top layer at any value bounded away from the higher end, then we may include, for example, edges whose two end-nodes are (close to) uniform but are nevertheless neither almost always equal nor almost always unequal, in the sense we described above. The above discussion serves to motivate the use of different measures than mutual information for classifying the edges of T. Those new measures -minmrg minmrg minmrg, mindiag mindiag mindiag, mindisc mindisc mindisc, and I H 2 I H 2 I H 2 -are defined in Section 2.8 (see Definition 2.8.5, Definition 2.8.6, Definition 2.8.7, and Definition 2.8.8).
The top layer. For the top layer we use a combination of minmrg and mindiag, and classify an edge (i, j) of T as a T T T-avenue (we will explain later why we don't call it a "road" reflecting our terminology for the symmetric case) if minmrg( P ij ) ≥ 10 6 2 n and mindiag( P ij ) ≤ 10 5 2 n , 6 where The T-avenues cluster the n nodes into connected components, each of which is called a broken-city (we will explain the terminology later).
Striving to make the broken-cities T-connected. The condition mindiag( P ij ) ≤ 10 5 2 n obviously says that X i and X j are estimated to be almost always equal or almost always unequal. But why do we need the condition minmrg( P ij ) ≥ 10 6 2 n ? Recall that in the symmetric case each city is shown to be not only T-connected, but also T-connected, which allows us to apply Corollary 2.5.4 with A 1 , . . . , A Λ being the cities in order to bound H(P (2) , P (3) ) (the pair of distributions in our final hybrid argument related by the replacement of T-highways by the T-highways; see Section 3.2.3). We hope the same is true in the general case: if i and j belong to the same broken-city, we would hope that all the nodes on the path in T between i and j also belong to that broken-city. If we didn't impose the condition minmrg( P ij ) ≥ 10 6 2 n in our definition of T-avenues, then we can't exclude, for example, that X i and X j are both always equal to 1. In this extreme case, the distributions for the intermediate nodes and edges on the path in T between i and j can be arbitrary, and it would be impossible to prove that each intermediate node also belongs to the broken-city containing i and j. The main issue here is that even though X i and X j are always equal, they are also independent of each other! This phenomenon can only occur when the individual marginals are allowed to be very biased, which can happen in the general case, but not in the symmetric case. In general, to avoid this kind of situations, we need to prevent including in the top layer edges of T whose end-nodes are almost always equal or almost always unequal but are also almost independent. To do that, we have to exclude edges of T whose end-nodes are "too biased". The condition minmrg( P ij ) ≥ 10 6 2 n does exactly that. With a lower bound on minmrg included in the requirement for a T-avenue, the following lemma becomes applicable, as we will see shortly.
Lemma 4.2.10 is in some sense an analog of the multiplicativity of α-values along a path in T (Lemma 2.4.2), for the measure mindiag (recall that the α-values provide a measure on pairwise distributions for the symmetric case). Roughly speaking, Lemma 4.2.10 (ii) says that closer pairs along a path in T are stronger as measured by mindiag (for α-values for the symmetric case the analogous relationship is min α ij , α jk ≥ |α ik |), and (iii) controls the manner in which the strengths of the pairs (as measured by mindiag) concatenate/decompose along a path in T.
Note that Lemma 4.2.10 (iii) implies that if (i, k) is a T-avenue and j is on the path in T between i and k then at least one of mindiag(P ij ) and mindiag(P jk ) is significantly less than mindiag(P ik ) (it is important that we have "significantly less than" instead of just "less than" here because we need to allow space for estimation error). Say it is mindiag(P ij ). Then following some quite involved argument (the main complication being that (i, j) might not be an edge of T so we can't simply deduce that i and j belong to the same broken-city even if P ij satisfies the criteria for a T-avenue; instead, we have to reason about the edges of T on the path in T between i and j; see Lemma 4.2.30, Definition 4.2.31, and Lemma 4.2.32), we can arrive at the desired conclusion that j belongs to the same broken-city as i does, as long as minmrg(P j ) ≥ 10 7 2 n . We call a node j biased if minmrg(P j ) < 10 7 2 n . Consequently, every unbiased node on the path in T between the two end-nodes of some T-avenue must belong to the same broken-city as those two end-nodes. In reality, the constant 10 7 in the threshold for biased nodes can be replaced by any number strictly greater than 10 6 (recall 10 6 is the constant in the minmrg threshold for T-avenues) as long as we make B (in the sample complexity of the algorithm) big enough.
Failure to make the broken-cities T-connected. Unfortunately, the above argumentation still doesn't yield that every broken-city is T-connected due to potential "holes" created by biased nodes (a "hole" j for a broken-city is a node which doesn't belong to the broken-city, but which lies on the path in T between some i and k belonging to the broken-city). Indeed, our analysis is ultimately not going to guarantee that every broken-city is necessarily T-connected. Whatever we set the minmrg threshold for T-avenues to be, the minmrg threshold for a node to be considered unbiased has to be strictly greater than that in order for us to be able to prove that unbiased nodes won't create any "holes." On the other hand, if i, j, k lie on a path in T, we can't eliminate the possibility that minmrg(P j ) is strictly less than both minmrg(P i ) and minmrg(P k ) (or their P counterparts) (see Lemma 4.2.10 (i) for the best lower bound we can get). Consequently, it could potentially happen that (i, k) is classified as a T-avenue, but j is biased. When that happens, we can't prove that j belongs to the same broken-city as i and k do. So a broken-city might not be T-connected (which is why we don't just call it a "city"). We have to work around that.
The remedy. The key to the remedy is, as we have already noted, that every "hole" must be biased. That is, every "hole" is either almost always equal to 1, or almost always equal to −1, under P. Roughly speaking, the "holes" can be neglected, because every edge incidental to a "hole" must be close to being independent in H 2 under P due to the "hole" having a small minmrg under P (see Lemma 4.2.7). We define the convex hull (in T) of a broken-city by filling in all the "holes" (see Definition 4.2.23). While any two different broken-cities must be disjoint, their convex hulls might intersect. Whenever the convex hulls of two broken-cities intersect, we have to merge those broken-cities together. The resulting clusters after we merge every pair of broken-cities whose convex hulls intersect are called the cities (see Definition 4.2.24). It can be shown that every city is T-connected (see Lemma 4.2.26). It is worth noting though that a city might not be T-connected, but we will be able to work around that. 7 To complete our definitions at the top layer, we classify every edge of T whose two end-nodes belong to the same city as a T T T-road. Recall that in the symmetric case, one of the steps in the process of going from T to T is to replace the set of all T-roads by the set of all T-roads, and that each city is spanned by the T-roads in it, as well as by the T-roads in it. We would like something similar for the general case to make our argument down the road simpler and clearer. Because each city C is T-connected, it is spanned by those T-roads whose two end-nodes belong to C. On the other hand, the T-avenues whose two end-nodes belong to C are not necessarily enough to span C (which is why we don't call them " T-roads"); they only span the broken-cities contained in C individually. To augment them into a spanning set for C we have to throw in some edges that connect together the broken-cities contained in C. In fact, those additional edges can be selected from among the set of T-roads with end-nodes in C. See Definition 4.2.27 and Remark 4.2.28. We call each of those additional edges a T T T-trail. Thus, each city C is spanned by the union of the T-avenues with end-nodes in C and the T-trails with end-nodes in C. One of the steps in the process of going from T to T is to replace the set of all T-roads by the union of the set of all T-avenues and the set of all T-trails. Notice that the T-trails are selected from among the T-roads, and so this round of edge replacement is in fact leaving those edges unchanged. Again, it is for the clarity of our argument that we insist on their involvement so that within each city we are replacing one spanning tree by another spanning tree (see the bounding argument for H(P (3) , P (4) ) in Section 4.2.3). Of course, the T-trails are not necessarily edges of T so we have to get rid of them eventually. It can be shown that every T-trail must be incidental to at least one biased node, and so it is close to being independent in H 2 under P (see Lemma 4.2.34). Consequently, they can be cut away without incurring too much error in H 2 (see the bounding argument for H(P (4) , P (5) ) in Section 4.2.3).
For a diagrammatic illustration of the top layer see Figure 6. The solid connections represent edges of T, and the dashed connections represent edges of T. The small shaded circles represent the broken-cities, the shaded regions with irregular curved boundaries represent the convex hulls in T of the broken-cities, and the big hollow circle represents the city C. The operations of taking convex hulls in T fill in the "holes." For example, 16 ∈ conv T ( C 5 ) because the node 16 lies on the path in T between nodes 12 and 13, both of which belong to C 5 . Recall that all "holes" must be biased (that is, having minmrg less than 10 7 2 n ). In our case, the "holes" are marked with cross marks right next to them. Also, the broken-cities whose convex hulls in T intersect are merged into the same city. In our case, the broken-cities C 1 , . . . , C 7 are merged into the city C, while C 8 and C 9 belong to some other city (not shown) because their convex hulls in T don't intersect with the convex hull in T of any of C 1 , . . . , C 7 . Lastly, we use tiny hollow circles placed at the middle of the edges to mark the six T-roads that, along with the T-avenues in C, form a spanning tree of C. We can select those T-roads to be the T-trails in C (the selection is not unique: we could have selected (13,17) instead of (13, 16), for example).
The T-highways link the broken-cities into broken-countries, and link the cities into countries (from which it follows immediately that each country is a union of broken-countries). An edge (i, j) of T with i, j belonging to different cities in the same country is classified as a T T T-highway. We can prove the following structural results (note that (iii) is an analog of Lemma 3.2.14 for the symmetric case):

Lemma 4.2.35. (i) A T-highway goes between different cities.
(ii) There can be at most one T-highway and at most one T-highway between any pair of cities.
(iii) There is a T-highway between a pair of cities if and only if there is a T-highway between the same pair of cities, and if so, those two highways in fact go between the same pair of broken-cities.
Proof. (a rough and slightly imprecise sketch of the "only if" direction of (iii)). Suppose for the sake of contradiction that (i, k) is a T-highway between broken-cities C and ‹ D that are contained respectively in cities C and D (note that (i) implies that C and D are different cities), and that there is no edge of T between C and ‹ D (any such edge would in fact be classified as a T-highway because C and D are clearly different cities in the same country). Then, the path in T between i and k must contain some j that belongs to neither C nor ‹ D. Note that (i, k), being a T-highway, has a significant mindisc by definition. It follows that the pair i, j must also have a significant mindisc because they are "closer" on the path (see Lemma 4.2.12). Furthermore, it can be shown that the pair j, k must have a significant mindiag because they lie in different broken-cities (see Lemma 4.2.30). Lastly, it can be shown that j must have a significant minmrg (see Lemma 4.2.20). Thus, Lemma 4.2.15 (stated below) implies that H 2 (P ijk , P ij−k ) must be significant (that is, greater than 22 2 n ). It then follows from (the contrapositive of) Lemma 4.2.14 (i) that I P (X i ; X j ) > I P (X i ; X k ). Symmetrically we also have I P (X j ; X k ) > I P (X i ; X k ). Together they imply that (i, k) could not possibly be picked to be an edge of T by the maximum spanning tree algorithm. Lemma 4.2.15. If i, j, k lie on a path in T, then H 2 (P ijk , P ij−k ) ≥ 1 100 mindisc(P ij ) 2 · min ¶ minmrg(P j ), mindiag(P jk ) © .
As in the symmetric case, we will replace the set of all T-highways with the set of all T-highways in a single round of edge replacements in the process of going from T to T (see the bounding argument for H(P (2) , P (3) ) in Section 4.2.3). Also note that Lemma 4.2.35 (iii) and the fact that every city is T-connected imply that every country is T-connected.
The third layer. For the next layer, we classify an edge (i, j) of T with I H 2 ( P ij ) ≥ 10 10 2 n that is not a T-avenue or a T-highway as a T T T-railway, where is the independent pairwise distribution that has the same individual node marginals at i and j, respectively, as P ij does. The T-railways link the broken-countries into broken-continents, and link the countries into continents (from which it follows immediately that each continent is a union of brokencontinents). An edge (i, j) of T with i, j belonging to different countries in the same continent is classified as a T T T-railway. We can prove the following structural results (note that (iii) is an analog of Lemma 3.2.17 for the symmetric case):

Lemma 4.2.39.
(i) A T-railway goes between different countries.
(ii) There can be at most one T-railway and at most one T-railway between any pair of countries.
(iii) There is a T-railway between a pair of countries if and only if there is a T-railway between the same pair of countries, and if so, those two railways in fact go between the same pair of broken-countries.
Proof. (a rough and slightly imprecise sketch of the "only if" direction of (iii)). Suppose for the sake of contradiction that (i, k) is a T-railway between broken-countries C and ‹ D that are contained respectively in countries C and D (note that (i) implies that C and D are different countries), and that there is no edge of T between C and ‹ D (any such edge would in fact be classified as a T-railway because C and D are clearly different countries in the same continent). Then, the path in T between i and k must contain some j that belongs to neither C nor ‹ D. Note that (i, k), being a T-railway, has a significant I H 2 by definition. It follows that the pair i, j must also have a significant I H 2 because they are "closer" on the path (see Lemma 4.2.13). Furthermore, it can be shown that the pair j, k must have a mindisc significantly far from 1 because they lie in different broken-countries (see Lemma 4.2.38). Thus, Lemma 4.2.16 (stated below) implies that H 2 (P ijk , P ij−k ) must be significant (that is, greater than 22 2 n ). It then follows from (the contrapositive of) Lemma 4.2.14 (i) that I P (X i ; X j ) > I P (X i ; X k ). Symmetrically we also have I P (X j ; X k ) > I P (X i ; X k ). Together they imply that (i, k) could not possibly be picked to be an edge of T by the maximum spanning tree algorithm.
As in the symmetric case, we will replace the set of all T-railways with the set of all T-railways in a single round of edge replacements in the process of going from T to T (see the bounding argument for H(P (1) , P (2) ) in Section 4.2.3). Also note that Lemma 4.2.39 (iii) and the fact that every country is T-connected imply that every continent is T-connected.
The bottom layer. Finally, an edge (i, j) of T that is yet to be classfied is classified as a T T T-tunnel, and an edge (i, j) of T that is yet to be classified is classified as a T T T-airway. While a T-airway must go between two different continents, a T-tunnel might not. In fact, the two end-nodes of a T-tunnel might belong to the same city, to different cities in the same country, to different countries in the same continent, or to different continents (that's why we call it a T-tunnel, instead of a " T-airway"). Nevertheless, it can be shown that an edge that is a T-tunnel or T-airway must be close to being independent in H 2 under P (see Lemma 4.2.42), so that they can be cut away without incurring too much error in H 2 (see the bounding argument for H(P, P (1) ) and H(P (6) , P (7) ) in Section 4.2.3).

Summary of layering.
To summarize, the edges of T are classified into T-avenues, T-highways, T-railways, and T-tunnels based on a combination of the measures minmrg, mindiag, mindisc, and I H 2 . The n nodes are clustered into broken-cities by the T-avenues, which are further clustered into broken-countries by the T-highways, which are further clustered into broken-continents by the T-railways, which are finally linked into one component by the T-tunnels.
Note that each broken-city, broken-country, or broken-continent is T-connected by definition. Unlike what happened in the symmetric case, it is however not necessarily T-connected. To remedy that, we define the convex hull (in T) of a broken-city by filling in all the "holes" (a "hole" for a broken-city is a node which doesn't belong to the broken-city, but which lies on the path in T between some two nodes that belong to the broken-city; we can prove that every "hole" is biased, in that it is almost always 1 or almost always −1). Whenever the convex hulls of two broken-cities intersect, we merge those broken-cities together. The resulting clusters after we merge every such pair of broken-cities are called the cities. The T-highways (each of which can be shown to go between different cities) link the cities into countries, and the T-railways (each of which can be shown to go between different countries) link the countries into continents. This hierarchical classification of nodes into groups then induces a classification of the edges of T: an edge of T is classified as a T-road if its two end-nodes belong to the same city, a T-highway if its two end-nodes belong to different cities in the same country, a T-railway if its two end-nodes belong to different countries in the same continent, or a T-airway if its two end-nodes belong to different continents. For edges of T, we similarly have that the two end-nodes of each T-avenue belong to the same (broken-)city, those of each T-highway belong to different (broken-)cities in the same (broken-)country, and those of each T-railway belong to different (broken-)countries in the same (broken-)continent. However, while the two end-nodes of each T-tunnel surely belong to different broken-continents, they might in fact belong to the same city, to different cities in the same country, to different countries in the same continent, or to different continents.
We can prove that every city, country, or continent is T-connected (they are not necessarily T-connected, though). Furthermore, we can prove that the T-highways and T-highways can be matched into parallel pairs, that is, there is a T-highway between two broken-cities if and only if there is a T-highway between them (and there is at most one such pair between every pair of cities). The same goes for railways: there is a T-railway between two broken-countries if and only if there is a T-railway between them (and there is at most one such pair between every pair of countries). One consequence of everything we stated so far is that the exact same cities, countries, and continents would have been achieved if we were to cluster the n nodes first by T-roads, then T-highways, then T-railways, and finally T-airways.
Lastly, for every city C we select among the set of T-roads with end-nodes in C a subset that, together with the T-avenues with end-nodes in C, form a spanning tree of C. We call those selected edges T-trails. We can prove that every T-trail must be incidental to a biased node and is therefore close to being independent in H 2 .
For a diagrammatic illustration of our structural results see Figure 7. The solid connections represent edges of T, and the dashed connections represent edges of T. The thickness of the line increases as we go down in the hierarchy, with the T-roads and T-avenues being the thinnest and the T-airways and T-tunnels being the thickest. The shaded circles with dashed boundaries represent the broken-cities, the shaded rectangular boxes with dashed boundaries represent the broken-countries, and the shaded regions with dashed saw-tooth boundaries represent the broken-continents. The hollow circular or oval regions with solid boundaries represent the cities, the hollow regions with solid axis-aligned boundaries represent the countries, and the hollow regions with solid saw-tooth boundaries represent the continents. To avoid cluttering the figure, we don't show the convex hulls (in T) of the broken-cities. Note that the T-highways and T-highways can be matched into parallel pairs, each going between the same pair of broken-cities (in different cities in the same country). An example is (1, 2) and (3,4). Similarly, the T-railways and T-railways can be matched into parallel pairs, each going between the same pair of broken-countries (in different countries in the same continent). An example is (5, 6) and (7,8). This parallelism needs not hold other types of edges. For example, there is no edge of T that goes between the same pair of continents as the T-airway (9, 10) does, and there is no T-airway that goes between the same pair of continents as the T-tunnel (11,12) does. The T-tunnels can behave wildly, in the sense that the two end-nodes of a T-tunnel could belong to different continents (e.g. (13,14)), to different countries in the same continent (e.g. (15,16)), to different cities in the same country (e.g. (17,18)), or even to the same city (e.g. (19,20)). Lastly, we use tiny hollow circles placed at the middle of the edges to mark one possible selection for the T-trails. (There are some structural properties illustrated in the diagram that were not discussed in the outline above. For example, the path in T between the end-nodes of a T-highway or a T-railway must not contain any biased node. Consequently, it must not contain any "hole" for any of the broken-cities. Those properties will turn up in the proof details.)

The Detailed Proof of the General Case
We present the detailed proof of Theorem 4.0.3, following the steps sketched in Section 4.1. Throughout the section, we assume that P satisfies strong 4-consistency, and our goal is to demonstrate that under this condition, Algorithm 1 will compute a distribution Q satisfying d TV (P, Q) ≤ O ( ). Section 4.2.1 contains a collection of lemmas each involving a small number (1, 2, 3, or 4) of variables. Section 4.2.2 contains structural results on the relation between T and T, stated in the language of various hierarchies to be defined at the beginning of that section. The layers defined here dictate how we switch from T to T in the hybrid argument later. Section 4.2.3 proves the desired bound in total variation distance between P and Q with the aid of a few intermediate hybrid distributions. Throughout the section we assume ≤ 1 10 100 (it's easy to see that it suffices to deal only with sufficiently small ).

Lemmas on 1, 2, 3, or 4 Variables
This subsection includes a collection of lemmas each involving a small number (1, 2, 3, or 4) of variables that form the basis of our analysis later of more complex structures (e.g. those of T and T) and distributions.
Our first lemma provides bounds on the difference in H 2 for certain pairs of distributions involving a small number of variables, as a consequence of assuming 4-consistency. The distributions in (i), (ii), (iii), and (iv) are simply marginals of P or P, while (most of) the distributions in (v), (vi), (vii), and (viii) are derived from P or P by means of Definition 2.6.1 or Definition 2.8.3.  (iv) For any h, i, j, k ∈ [n], H 2 (P hijk , P hijk ) ≤ 8 · 1 10 20 2 n ; (v) For any i, j, k ∈ [n], H 2 (P i−j−k , P i−j−k ) ≤ 4 · 1 10 20 2 n ; (vi) For any h, i, j, k ∈ [n], H 2 (P (hi)−j−k , P (hi)−j−k ) ≤ 6 · 1 10 20 2 n ; (vii) If i, j, k lie on a path in T, then H 2 ( P i−j−k , P ijk ) ≤ 16 · 1 10 20 2 n ; (viii) If h, i, j, k lie on a path in T, then H 2 ( P (hi)−j−k , P hijk ) ≤ 28 · 1 10 20 2 n . Proof. First we show (iv). Note that for any x h , x i , x j , x k ∈ {1, −1}, 4-consistency implies that n . We thus have The proofs for (i), (ii), and (iii) are similar to that for (iv). For (i) we only need to bound for, and sum over, the two combinations corresponding to x i ∈ {1, −1}, for (ii) we have four combinations corresponding to x i , x j ∈ {1, −1}, and for (iii) we have eight combinations corresponding to x i , x j , x k ∈ {1, −1}.
To prove (v), note that P i−j−k and P i−j−k have the common factorization structure By Lemma 2.5.3 and (ii) above, we have To prove (vi), note that P (hi)−j−k and P (hi)−j−k have the common factorization structure

By Lemma 2.5.3 and (ii), (iii) above, we have
To prove (vii), note that the fact i, j, k lie on a path in T means P i−j−k = P ijk . Applying triangle inequality for Hellinger distance, and (iii), (v) above, we get To prove (viii), note that the fact h, i, j, k lie on a path in T means P (hi)−j−k = P hijk . Applying triangle inequality for Hellinger distance, and (iv), (vi) above, we get The next lemma indicates the precision to which P can be guaranteed to approximate P on events involving (up to) 4 variables, as a consequence of assuming 4-consistency. (ii) If P(X S ∈ W) ≤ 10 20 2 n , then P(X S ∈ W) − P(X S ∈ W) ≤ 2 n ; (iii) If P(X S ∈ W) ≥ 2 n , then and so P(X S ∈ W) P(X S ∈ W) − 1 ≤ 1 10 20 · 2 n P(X S ∈ W) ≤ 1 10 20 .
The next four lemmas provide bounds on the error due to estimation of, respectively, the measures minmrg, mindiag, mindisc, and I H 2 , as a consequence of assuming 4-consistency. Proof. Recall that To prove (i), suppose that minmrg(P U ) ≤ 10 20 2 n . Suppose minmrg(P U ) = P j (x j ) for some j ∈ U and x j ∈ {1, −1}. This implies P j (x j ) ≤ 10 20 2 n , and by Lemma 4 On the other hand, suppose that P i (x i ) < minmrg(P U ) − 2 n for some i ∈ U and x i ∈ {1, −1}. This implies P i (x i ) < 10 20 2 n , and by Lemma 4 n for all i ∈ U and x i ∈ {1, −1}, which means that minmrg( P U ) ≥ minmrg(P U ) − 2 n . This concludes the proof of (i). To prove (ii), suppose that minmrg( P U ) ≤ 10 20 2 n . Suppose minmrg( P U ) = P j (x j ) for some j ∈ U and x j ∈ {1, −1}. This implies P j (x j ) ≤ 10 20 2 n , and by Lemma 4 On the other hand, suppose that P i (x i ) < minmrg( P U ) − 2 n for some i ∈ U and x i ∈ {1, −1}. This implies P i (x i ) < 10 20 2 n , and by Lemma 4 n . This concludes the proof of (ii). (ii) If mindiag( P ij ) ≤ 10 20 2 n , then mindiag(P ij ) − mindiag( P ij ) ≤ 2 n .
Proof. Recall that To prove (i), suppose that mindiag(P ij ) ≤ 2 · 10 20 2 n . Suppose without loss of generality that mindiag(P ij ) = P(X i = −X j ) (the case mindiag(P ij ) = P(X i = X j ) is symmetric). This implies P(X i = −X j ) ≤ 2 · 10 20 2 n , and by Lemma 4.2.2 (i), we have P( To prove (ii), suppose that mindiag( P ij ) ≤ 10 20 2 n . Suppose without loss of generality that mindiag( P ij ) = P(X i = −X j ). This implies P(X i = −X j ) ≤ 10 20 2 n , and by Lemma 4.2.2 (ii), we have P( n . Since P(X i = X j ) = 1 − P(X i = −X j ) and P(X i = X j ) = 1 − P(X i = −X j ), we also have P(X i = X j ) − P(X i = X j ) ≤ 2 n . From here on (ii) follows as in the proof of (i). Proof. Recall that We have where we used the fact that minmrg(P ij ) ≥ 100 2 n implies P j (1) ≥ 100 2 n . Similarly, we have .
Thus, we have Similarly, we have The desired conclusion follows because perturbing each argument of the min function by at most 1 10 20 changes the overall min value by at most 1 10 20 .  .
n . By triangle inequality for the Hellinger distance, we have To prove (i), suppose I H 2 (P ij ) ≥ 2 n . Then I H (P ij ) ≥ √ n . We have by (18) and Thus, 1 4 ≤ We have by (18) and Thus, we still have 1 4 ≤ The next three lemmas prove various relationships among the measures minmrg, mindiag, mindisc, and I H 2 , for a single pair of variables. Lemma 4.2.7 implies that, for example, a pair of variables must be close to being independent in H 2 under P if at least one of them has a very biased binary distribution under P.
Proof. Without loss of generality, suppose minmrg(P ij ) = P i (1). Notice that Continuing this way, we see that the value P ij ( where ( * ) follows from Lemma 2.5.2.

Lemma 4.2.8. For any
Proof. Without loss of generality, suppose that mindiag(P ij ) = P(X i = −X j ). We have which implies that Similarly, P j (−1) − P i (−1) ≤ mindiag(P ij ). Recall that minmrg(P i ) = min {P i (1), P i (−1)} and minmrg(P j ) = min ¶ P j (1), P j (−1) © . The desired conclusion follows because perturbing each argument of the min function by at most mindiag(P ij ) changes the overall min value by at most mindiag(P ij ).
Proof. Without loss of generality, suppose that mindiag(P ij ) = P(X i = −X j ). Then minmrg(P ij ) . By symmetry the same lower bound also holds for P j|i (1|1) − P j|i (1| − 1) . So we have mindisc(P ij ) = min P i|j (1|1) − P i|j (1| − 1) , P j|i (1|1) − P j|i (1| − 1) The next lemma is in some sense an analog of the multiplicativity of α-values along a path in T (Lemma 2.4.2), for the measure mindiag. Roughly speaking, Lemma 4.2.10 (ii) says that closer pairs along a path in T are stronger as measured by mindiag (for α-values for the symmetric case the analogous relationship is min α ij , α jk ≥ |α ik |), and (iii) controls the manner in which the strengths of the pairs (as measured by mindiag) concatenate/decompose along a path in T. Lemma 4.2.10. If i, j, k lie on a path in T, and minmrg(P ik ) > 8 · mindiag(P ik ), then (iii) mindiag(P ij ) + mindiag(P jk ) ≤ 7 6 mindiag(P ik ).
Proof. Note that the condition implies mindiag(P ik ) < 1 8 . Recall that mindiag(P ik ) = min {P(X i = X k ), P(X i = −X k )}. Without loss of generality, suppose that mindiag(P ik ) = P(X i = −X k ). The other case is symmetric, and can be reduced to the current case by switching the labels 1 and −1 for X k . Note that the relabeling does not change any of the minmrg(·)'s and mindiag(·)'s.
We can also suppose without loss of generality that P ij (1, 1) ≥ P ij (−1, 1). The other case is symmetric, and can be reduced to the current case by switching the labels 1 and −1 for both X i and X k (so that the assumption mindiag(P ik ) = P(X i = −X k ) in the previous paragraph is unaffected). Note that the relabeling does not change any of the minmrg(·)'s and mindiag(·)'s.
We first argue that we must have P ij (1, −1) ≤ P ij (−1, −1). Suppose for the sake of contradiction that P ij (1, −1) > P ij (−1, −1). Then we have contradicting the assumption that minmrg(P ik ) proving (i). We can also use (19) to lower bound P ij (1, 1): At this point, we can repeat the same argument above for P jk instead of P ij . The only caveat is that we can not assume without loss of generality for free that P jk (1, 1) ≥ P jk (1, −1) -our earlier "without loss of generality assumptions" mindiag(P ij ) = P(X i = −X j ) and P ij (1, 1) ≥ P ij (−1, 1) took that freedom away from us. We have to prove P jk (1, 1) ≥ P jk (1, −1).
The next lemma generalizes Lemma 4.2.10 (ii) to four nodes that lie on a path in T.
The next lemma is an analog of Lemma 4.2.10 (ii), for the measure mindisc. Roughly speaking, it says that closer pairs along a path in T are stronger as measured by mindisc. Lemma 4.2.12. If i, j, k lie on a path in T, then we have mindisc(P ij ) ≥ mindisc(P ik ) and mindisc(P jk ) ≥ mindisc(P ik ).
The next lemma is an analog of Lemma 4.2.10 (ii) (or Lemma 4.2.12), for the measure I H 2 . Roughly speaking, it says that closer pairs along a path in T are stronger as measured by I H 2 . Lemma 4.2.13. If i, j, k lie on a path in T, then we have both I H 2 (P ij ) ≥ I H 2 (P ik ) and I H 2 (P jk ) ≥ I H 2 (P ik ).
Proof. Consider the convex function f (t) = 1 − √ t. We have where ( * ) follows from Jensen's Inequality. The proof for The next lemma is central in our analysis for the general case. Part (i), for example, provides a necessary condition (H 2 (P ijk , P ij−k ) ≤ 22 2 n ) for Algorithm 1 to make a structural mistake, in the case of i, j, k lying on a path in T, by "reversing the order" between (i, j) and (i, k). This not only bounds the error in H 2 when Algorithm 1 does make the structural mistake, but also provides a guideline on how to classify the edges and define the layers (which allows us to speak more precisely about the manners in which T might differ from T) in Section 4.2.2. The proof for this lemma is the only place in the entire argument where we need those implications of strong 4-consistency that are beyond those implies by just 3-consistency.

Lemma 4.2.14.
(i) If i, j, k lie on a path in T, and I P (X i ; X j ) ≤ I P (X i ; X k ), then H 2 (P ijk , P ij−k ) ≤ 22 2 n .
Proof. We will prove (i) and (ii) in parallel in four steps. The first step provides a general inequality relating the mutual information and the squared Hellinger distance. The second step contains some numerical inequalities. The third step provides upper bounds on some estimated conditional mutual informations, using only the assumption that i, j, k (or h, i, j, k) lie on a path in T. The fourth step finishes the proof by taking into account the assumed inequalities between estimated mutual informations.
Step 1: In this step we show that for any u, v, w ∈ [n] we have 8 and that for any t, u, v, w ∈ [n] we have To prove (25), first note that This proves the equality part of (25). The inequality part follows from the general fact that whenever p = (p 1 , . . . , p L ) and p = (p 1 , . . . , p L ) are discrete distributions over a domain of size L, we have where ( * ) follows from Jensen's Inequality and the concavity of ln(t), and ( * * ) follows from the fact that ln (1 − t) ≤ −t for t ≤ 1.
The proof of (26) is similar -just treat the pair (X t , X u ) as one (super) random variable X tu .
Step 2: In this step we show that for a, b ≥ 0 we have The case b < 1 2 a is trivial. The case b > 3 2 a follows from The case 1 2 a ≤ b ≤ 3 2 a follows from where the Taylor expansion for ( * ) is possible due to b−a a ≤ 1 2 , and ( * * ) follows from the fact that 1 2 − 1 3 t + 1 4 t 2 − · · · < 1 for |t| ≤ 1 2 .
Step 3: In this step we show that i, j, k lie on a path in T implies I P (X i ; X k |X j ) ≤ 41 2 n , and that h, i, j, k lie on a path in T implies I P (X h ; X j , X k |X i ) ≤ 81 2 n . Note that both quantities above become 0 if we replace P by P at the superscripts of I due to conditional independence.
Suppose that i, j, k lie on a path in T. We have by the equality part of (25) that Note that i, j, k lie on a path in T implies P ijk = P i−j−k , so To bound the summands in (28) we divide into two cases P ijk (x i , x j , x k ) ≥ 2 n and P ijk ( Note that in this case we also have P ij (x i , x j ) ≥ 2 n , P jk (x j , x k ) ≥ 2 n , and P j (x j ) ≥ 2 n . Thus, Lemma 4.2.2 (iii) implies that each of the quantities P jk (x j ,x k ) , and P j (x j ) P j (x j ) lies within the interval [1 − 1 10 20 , 1 + 1 10 20 ]. By (29) must lie between 1 2 and 3 2 . Therefore, we can apply the middle case of (27) in Step 2 to get , then by the last two cases of (27) in Step 2 we have Now assume P i−j−k (x i , x j , x k ) < 1 2 P ijk (x i , x j , x k ). We first bound the four fractions in the last line of (29). Note that 4-consistency implies P ijk (x i , x j , x k ) < (1 + 1 10 20 ) 2 n , and so If P j (x j ) ≥ 2 n , then by Lemma 4.2.2 (iii) we have n , then 4-consistency implies P j (x j ) < (1 + 1 10 20 ) 2 n , and so . Either way (using that P ijk ( Similarly we also have P jk (x j , x k ) Combining (29), (32), (33), (34), (35), and the first case of (27) in Step 2, we get where the last inequality follows from the bound P ijk (x i , x j , x k ) < (1 + 1 10 20 ) 2 n , strong 4-consistency (this is the only place in the entire proof that the "strong part" of strong 4-consistency is used), and the fact that ln t t ≤ 1, for t > 0.
Combining (30), (31), and (36), we have for any of the eight combinations x i , x j , x k ∈ {1, −1}. Plugging them into (28), noting that the eight terms sum to 0, we get where ( * ) follows from Lemma 4.2.1 (vii). This proves the first claim stated at the beginning of Step 3. Now suppose that h, i, j, k lie on a path in T. The argument for bounding I P (X h ; X j , X k |X i ) is completely parallel to the three-node case above if we view (X j , X k ) as a single random variable. For example we can apply the equality part of (26) to get Similarly, note that h, i, j, k lie on a path in T implies P hijk = P h−i−(jk) , so To bound the summands in (37) we similarly divide into two cases P hijk (x h , x i , x j , x k ) ≥ 2 n and P hijk (x h , x i , x j , x k ) < 2 n and bound the four fractions at the end of (38) separately. We omit the detail, noting only that at the end we will have where ( * ) follows from Lemma 4.2.1 (viii) (note that the coefficients are different from those in the three-node case because we have 16 terms instead of 8). This finishes Step 3.
Step 4: We finish the proof in this step.
To prove (i), suppose i, j, k lie on a path in T, and I P (X i ; X j ) ≤ I P (X i ; X k ). We will proceed in a way similar to the standard proof of the data-processing inequality for Markov chains. Let's expand I P (X i ; X j , X k ) using the chain rule for mutual information in two different ways: and I P (X i ; X j , X k ) = I P (X i ; X k ) + I P (X i ; X j |X k ).
Compare the two we see that I P (X i ; X j ) ≤ I P (X i ; X k ) implies I P (X i ; X k |X j ) ≥ I P (X i ; X j |X k ). By Step 3, n . By triangle inequality for Hellinger distance, and Lemma 4.2.1 (iii), (v), we have To prove (ii), suppose h, i, j, k lie on a path in T, and I P (X i ; X j ) ≤ I P (X h ; X k ). Let's expand I P (X h , X i ; X j , X k ) using the chain rule for (conditional) mutual information in two different ways: Compare the two we see that I P (X i ; X j ) ≤ I P (X h ; X k ) implies I P (X i ; X k |X j ) + I P (X h ; X j , X k |X i ) ≥ I P (X i ; X k |X h ) + I P (X h , X i ; X j |X k ).

By
Step 3, I P (X i ; X k |X j ) ≤ 41 2 n and I P (X h ; X j , X k |X i ) ≤ 81 2 n . Thus we have I P (X i ; X k |X h ) ≤ 122 2 n and I P (X h , X i ; X j |X k ) ≤ 122 2 n . By (25), we have H 2 ( P hik , P h−i k ) ≤ 1 2 I P (X i ; X k |X h ) ≤ 61 2 n . By triangle inequality for Hellinger distance, and Lemma 4.2.1 (iii), (v), we have By (26) with the pair (X h , X i ) viewed as a single random variable we have H 2 ( P hijk , P (hi)j−k ) ≤ 1 2 I P (X h , X i ; X j |X k ) ≤ 61 2 n . We want to get rid of the index h in H 2 ( P hijk , P (hi)j−k ). To that end, we have where ( * ) follows from Cauchy's Inequality, and ( * * ) follows from the facts that P hijk 's marginal distribution for X i , X j , X k is P ijk and P (hi)j−k 's marginal distribution for X i , X j , X k is P ij−k . (In fact, it is generally true that restricting to a subset of variables will not increase the Hellinger distance, by an argument like the one we had above). Thus, we in fact have H 2 ( P ijk , P ij−k ) ≤ 61 2 n . We can then obtain as in (39) that H 2 (P ijk , P ij−k ) ≤ 62 2 n . Finally, by Lemma 2.6.3 we have This completes the entire proof. Lemma 4.2.14 implies that if i, j, k lie on a path in T and H 2 (P ijk , P ij−k ) > 22 2 n , then Algorithm 1 can not possibly make a structural mistake by "reversing the order" between (i, j) and (i, k). The condition H 2 (P ijk , P ij−k ) > 22 2 n involves P ijk . We would also want other forms of this condition that are stated in terms only of P ij and P jk , as ultimately we are going to classify the individual edges (of T) independently in the definition of layers in Section 4.2.2. We want to find conditions involving only P ij and P jk that would guarantee H 2 (P ijk , P ij−k ) > 22 2 n . The following two lemmas enable us to do that.
We have Similarly, we have It's easy to see that we also have the following: The claim at the beginning of the lemma follows from (40), (41), (42), and a bit of case work. Without loss of generality we can assume that P i|j (1|1) − P i|k (1|1) ≥ 1 2 mindisc(P ij ) and P jk (1, 1) ≥ 1 2 min ¶ minmrg(P j ), mindiag(P jk ) © . We then have where ( * ) follows from the fact that Lemma 4.2.16. If i, j, k lie on a path in T, then H 2 (P ijk , P ij−k ) ≥ 1 100 , we can suppose without loss of generality that It is easy to see that P ij (1, 1) To shorten the length of subsequent equation-displays, We use the shorthand We have Combining the two we have where We also have P ij−k (1, 1, 1) = P jk (1, 1)P i|k (1|1) and similarly (for obtaining the first equality below) Combining the two we have where Combining (44) and (45), recall the definition so that one of P j|k (1|1) − P j|k (1| − 1) and P k|j (1|1) − P k|j (1| − 1) is equal to mindisc(P jk ), and the other is at most 1, we have This means that at least one of |A − C| and |B − D| is at least 1 2 Ä 1 − mindisc(P jk ) ä · |V|. Suppose without loss of generality that it is |A − C|. Plugging in the values we represent using A and C, we have Inequalities (43) and (46) are all we need to establish our desired bound. We have where ( * ) is an equality in the case P ijk (1, 1, 1) < P ij−k (1, 1, 1), and follows from the fact that (1, 1, 1); ( * * ) follows from the same fact. (1,1), and so Therefore, no matter V < 0 or V ≥ 0, we have Combining (43, (47), and (48) we have The last five lemmas in this subsection prove various relationships among the measures minmrg, mindiag, mindisc, and I H 2 , for i, j, k that lie on a path in T. For example, Lemma 4.2.18 says that the pair (i, k) must be strong as measured by I H 2 if the pairs (i, j) and (j, k) are strong as measured by I H 2 and mindisc, respectively. Lemma 4.2.21 generalizes Lemma 4.2.7. It implies that, for example, a pair of variables must be close to being independent in H 2 under P if there is a node on the path in T between them that has a very biased distribution under P. Proof. Without loss of generality, suppose that mindiag(P jk ) = P(X j = −X k ). We have P k (1) = P j (1) − P jk (1, −1) + P jk (−1, 1), which implies that Similarly, P k (−1) − P j (−1) ≤ mindiag(P jk ).
We also have which implies that and similarly P k|i (1| − 1) − P j|i (1| − 1) ≤ mindiag(P jk ) minmrg(P ij ) . Thus, We also have Since the desired conclusion follows from (49) and (50) because perturbing each argument of the min function by at most 4 · mindiag(P jk ) minmrg(P ij ) changes the overall min value by at most 4 · mindiag(P jk ) minmrg(P ij ) .
, we can suppose without loss of generality that It is easy to see that P ij (1, 1) To shorten the length of subsequent equation-displays, We use the shorthand Since mindisc(P jk ) ≤ P j|k (1|1) − P j|k (1| − 1) , at least one of P j|k (1|1) and P j|k (1| − 1) is at least mindisc(P jk ).
Proof. Without loss of generality (by possibly switching the labels 1 and −1 for some nodes) we can assume that mindiag(P ij ) = P(X i = −X j ) and mindiag(P jk ) = P(X j = −X k ). Since X i = −X k implies either Lemma 4.2.20. If i, j, k lie on a path in T, then minmrg(P j ) ≥ minmrg(P ik )mindisc(P ik ).

Hierarchies and Structural Results for T vs. T
This subsection contains structural results on the relation between T and T, stated in the language of various hierarchies to be defined first. The layers we define here dictate how we switch from T to T in the hybrid argument for bounding d TV (P, Q) in the next subsection. The major complication is that, unlike for the symmetric case, the groups at the top layer as directly induced by the classification of edges of T are not necessarily T-connected (in fact this issue propagates to the groups at lower layers too). This would prevent us from describing our structural results and from applying Corollary 2.5.4 in the way we wanted. Additional steps have to be taken to work around this issue.
We first classify all the edges of T based on a combination of minmrg, mindiag, mindisc, and I H 2 . This induces a preliminary hierarchical classification of nodes into groups.

Definition 4.2.22.
We establish the following hierarchies, starting with the empty graph G on [n] and adding edges incrementally: • An edge (i, j) of T with minmrg( P ij ) ≥ 10 6 2 n and mindiag( P ij ) ≤ 10 5 2 n is classified as a T T T-avenue. Adding the T-avenues to G links the n nodes into connected components, each of which is called a broken-city.
• An edge (i, j) of T with minmrg( P ij ) ≥ 10 8 2 n and mindisc( P ij ) ≥ 1 2 that is not a T-avenue is classified as a T T T-highway. Adding the T-highways to G further links the broken-cities into bigger connected components, each of which is called a broken-country.
• An edge (i, j) of T with I H 2 ( P ij ) ≥ 10 10 2 n that is not a T-avenue or a T-highway is classified as a T T T-railway. Adding the T-railways to G further links the broken-countries into even bigger connected components, each of which is called a broken-continent.
• Each remaining edge of T is classified as a T T T-tunnel. Adding the T-tunnels to G further links the brokencontinents into one single connected component of all n nodes.
As we mentioned, the broken-cities might not be T-connected. The following definition allows us to obtain sets from them that are T-connected by filling in the "holes" (a "hole" for a broken-city is a node which doesn't belong to the broken-city, but which lies on the path in T between some pair of nodes that belong to the broken-city).

Definition 4.2.23 (conv T (·)
conv T (·) conv T (·)). For a subset S of [n], let conv T (S) conv T (S) conv T (S) (called the convex hull of S in T) denote the set of nodes consisting of nodes in S, as well as every node that lies on the path in T between some i, j ∈ S. In other words, conv T (S) is the minimal T-connected subset of [n] that contains S.
The convex hull in T of each broken-city is obviously T-connected. However, the convex hulls of different broken-cities might intersect, and whenever that happens, we need to merge the two broken-cities. Doing that leads to a partition of the n nodes into T-connected subsets, which forms the top layer of our hierarchy. The definitions for the lower layers and the (induced) classification of edges of T are also contained in the following: Definition 4.2.24. We establich the following hierarchy: • The set of nodes [n] is partitioned into cities such that each city is a union of broken-cities, and that two broken-cities C and ‹ D are contained in the same city if and only if there exists a sequence of broken-cities C = C 0 , C 1 , . . . , C r = ‹ D such that conv T ( C s ) ∩ conv T ( C s+1 ) = ∅ for each s = 0, . . . , r − 1. An edge (i, j) of T with i, j belonging to the same city is classified as a T T T-road.
• The set of nodes [n] is partitioned into countries such that each country is a union of cities, and that two cities C and D are contained in the same country if and only if there exists a sequence of cities C = C 0 , C 1 , . . . , C r = D such that there exists a T-highway between C s and C s+1 for each s = 0, . . . , r − 1. An edge (i, j) of T with i, j belonging to the different cities in the same country is classified as a T T T-highway.
• The set of nodes [n] is partitioned into continents such that each continent is a union of countries, and that two countries C and D are contained in the same continent if and only if there exists a sequence of countries C = C 0 , C 1 , . . . , C r = D such that there exists a T-railway between C s and C s+1 for each s = 0, . . . , r − 1. An edge (i, j) of T with i, j belonging to the different countries in the same continent is classified as a T T T-railway.
• An edge (i, j) of T with i, j belonging to different continents is classified as a T T T-airway.
Our first lemma compiles a list of containment relationships among the (preliminary) groups we defined.

Lemma 4.2.25.
(i) A broken-country is a union of broken-cities.
(ii) A broken-continent is a union of broken-countries.
(iii) A country is a union of cities.
(iv) A continent is a union of countries.
(v) A city is a union of broken-cities.
(vi) A city is the union of the convex hulls in T of those broken-cities contained in the city.
(vii) A country is a union of broken-countries.
(viii) A continent is a union of broken-continents.
To prove (vi) it suffices to show that if C is a broken-city contained in a city C, then conv T ( C) is also contained in C. To see that, let i be any node in conv T ( C). If i ∈ C then obviously i ∈ C. Otherwise, let ‹ D be the broken-city containing i. Since i ∈ conv T ( C) ∩ conv T ( ‹ D) = ∅, by Definition 4.2.24 C and ‹ D are contained in the same city. So i ∈ C and (vi) is proved.
By Definition 4.2.22 a broken-country consists of a collection of broken-cities linked together by Thighways. By Definition 4.2.24 the two end-nodes of each T-highway belong to the same country. Since each broken-city is contained entirely in one city (by (v)), and therefore entirely in one country, we see that each broken-country is contained entirely in one country, and (vii) follows.
By Definition 4.2.22 a broken-continent consists of a collection of broken-countries linked together by T-railways. By Definition 4.2.24 the two end-nodes of each T-railway belong to the same continent. Since each broken-country is contained entirely in one country (by (vii)), and therefore entirely in one continent, we see that each broken-continent is contained entirely in one continent, and (viii) follows.
The formal proof that every city is T-connected is as follows: Proof. Let C be any city, and i, j be any pair of nodes in C. It suffices to show that we can go from i to j using only edges of T without leaving C.
Let C and ‹ D be broken-cities such that i ∈ C and j ∈ ‹ D. By Definition 4.2.24 there exists a sequence of broken-cities C = C 0 , C 1 , . . . , C r = ‹ D such that conv T ( C s ) ∩ conv T ( C s+1 ) = ∅ for each s = 0, . . . , r − 1. It is easy to see that Definition 4.2.24 implies C s ⊂ C for each s = 0, . . . , r, and so conv T ( C s ) ⊂ C by Lemma 4.2.25 (vi). For each s = 0, . . . , r − 1, let k s be any node in conv T ( C s ) ∩ conv T ( C s+1 ).
Since i, k 0 ∈ conv T ( C 0 ), and conv T ( C 0 ) is T-connected, the path in T between i and k 0 lies entirely in conv T ( C 0 ) ⊂ C. Similarly, for each s = 0, . . . , r − 1, we have k s , k s+1 ∈ conv T ( C s+1 ), and so the path in T between them lies entirely in conv T ( C s+1 ) ⊂ C. Lastly, k r−1 , j ∈ conv T ( C r ), so the path in T between them lies entirely in conv T ( C r ) ⊂ C. Tracing all those paths in order allows us to go from i to j using only edges of T without leaving C.
As discussed in the part titled "The remedy" in Section 4.1, the fact that a city is not necessarily spanned by the T-avenues whose two end-nodes belong to the city prompted us to find edges that augment them into a spanning set for the city (we will use this spanning set to replace the spanning set formed by the T-roads with both end-nodes in the city in the process of going from T to T). Specifically, those edges can be selected from among the T-roads with both end-nodes in the city. We now formalize the definition and the selection procedure.

Definition 4.2.27 (T T T-trails).
For every city C, we select a subset of edges among the T-roads with both end-nodes in C such that the selected edges, together with the set of all T-avenues with both end-nodes in C, form a spanning tree of C. We do not select any T-avenue. See Remark 4.2.28 below for one way to do it. Each selected edge is called a T T T-trail. To see that the set of selected edges by the end of the procedure above indeed, together with all T-avenues with both end-nodes in C, form a spanning tree of C, first note that obviously there can be no cycle. On the other hand, suppose C can be partitioned into two non-empty subsets with no selected edge or T-avenue going in between. Since C is T-connected by Lemma 4.2.26, there must exist a T-road between those two subsets, and this T-road should have been selected when we examined it in the selection procedure above. This is a contradiction.
We show that a pair of nodes that is either a T-road or a T-avenue must be almost always equal or almost always unequal under P (in other words, the pair is strong as measured by mindiag). Note that the case of a T-trail is also included because a T-trail is a T-road by Definition 4.2.27. This will enable us to prove that within a city it doesn't matter much in terms of H 2 whether the nodes are held together by the T-roads in the city or by the T-avenues and T-trails in the city. Proof. If (i, j) is a T-avenue, then by definition mindiag( P ij ) ≤ 10 5 2 n . By Lemma 4.2.4 (ii), we have mindiag(P ij ) ≤ (10 5 + 1) 2 n , as desired. Suppose from now on that (i, j) is a T-road. First we show that (i, j) is on the path in T between the two end-nodes of some T-avenue. Suppose not for the sake of contradiction. Imagine removing (i, j) from T. This partitions [n] into two T-connected subsets U and V. Then for each T-avenue, its two end-nodes must both belong to U or both belong to V. Since a broken-city is spanned by T-avenues, we see that each broken-city must be contained either entirely in U or entirely in V. Since U and V are T-connected, the convex hull in T of each broken-city must be contained either entirely in U or entirely in V. It is then easy to see that i and j can't belong to the same city because the sequence of broken-cities bridging between i's and j's broken-cities as required according to Definition 4.2.24 can't possibly exist. This contradicts the assumption that (i, j) is a T-road.
So we can indeed find h, k such that (h, k) is a T-avenue and that (i, j) is on the path in T between h and k. By definition minmrg( P hk ) ≥ 10 6 2 n and mindiag( P hk ) ≤ 10 5 2 n . Note that minmrg( P hk ) ≥ 10 6 2 n implies minmrg(P hk ) ≥ (10 6 − 1) 2 n (the contrapositive of this follows from Lemma 4.2.3 (i)). Also mindiag(P hk ) ≤ (10 5 + 1) 2 n by Lemma 4.2.4 (ii). Thus, we can apply Lemma 4.2.10 (or Lemma 4.2.11) with h and k at the two ends and any node(s) on the path in T between h and k in the middle. It is easy to argue that in any case we have mindiag(P ij ) ≤ mindiag(P hk ) ≤ (10 5 + 1) 2 n , as desired. The next lemma provides sufficient conditions for a pair i, j to belong to the same broken-city. The proof of this lemma is relatively involved. The main complication is that, even though the stated conditions appear stronger than those for T-avenues (Definition 4.2.22), we can not directly deduce that i, j belong to the same broken-city because the pair might not be an edge of T and so might not even be subject to the classification as described in Definition 4.2.22 at all. Instead, we have to reason about the edges of T on the path in T between i and j. Lemma 4.2.30. If minmrg(P ij ) ≥ (5 · 10 6 + 1) 2 n and mindiag(P ij ) ≤ (6 · 10 4 − 1) 2 n , then i, j belong to the same broken-city.
Proof. Suppose the path in T between i and j consists of nodes i = i 0 , . . . , i r = j, in that order. We first show that minmrg(P i s ) ≥ 3 · 10 6 2 n , for all s = 0, . . . , r. By the cycle property of maximum weight spanning tree I P (X i ; X j ) ≤ I P (X i s ; X i s+1 ) for all s = 0, . . . , r − 1.
Note that our assumption leads to I P (X i ; X j ) > I P (X i s ; X i s+1 ), a contradiction. Consequently, we must have minmrg(P i s ) ≥ 3 · 10 6 2 n , for all s = 0, . . . , r. Suppose the path in T between i and j consists of nodes i = i 0 , . . . , i q = j, in that order. Since minmrg(P ij ) ≥ (5 · 10 6 + 1) 2 n and mindiag(P ij ) ≤ (6 · 10 4 − 1) 2 n , applications of Lemma 4.2.10 (i), (ii), and Lemma 4.2.11 yield, say, minmrg(P i u ) ≥ 2 · 10 6 2 n for all u = 0, . . . , q and mindiag(P i u i u+1 ) ≤ 6 · 10 4 2 n for all u = 0, . . . , q − 1. Recall that the path in T between i and j is i = i 0 , . . . , i r = j, and that we already proved minmrg(P i s ) ≥ 3 · 10 6 2 n , for all s = 0, . . . , r. Our goal is to prove that i and j belong to the same broken-city. It suffices to prove the following claim, which we deal with exclusively for the rest of the proof of this lemma. For convenience we will keep using symbols like i, j, q, r, s, u in the statement and proof of the claim below, where they might refer to different things from what they have been referring to so far in the proof. For example, we are not assuming minmrg(P ij ) ≥ (5 · 10 6 + 1) 2 n any more. Basically think of what follows as the statement and proof of a fresh lemma.
Claim: For any i, j ∈ [n], let the path in T between them be i = i 0 , . . . , i q = j, in that order, and the path in T between them be i = i 0 , . . . , i r = j, in that order (the two paths might share any number of intermediate nodes). If • minmrg(P i u ) ≥ 2 · 10 6 2 n for all u = 0, . . . , q • mindiag(P i u i u+1 ) ≤ 6 · 10 4 2 n for all u = 0, . . . , q − 1 • minmrg(P i s ) ≥ 3 · 10 6 2 n , for all s = 0, . . . , r then i and j belong to the same broken-city.
For an illustration of the setting described in our claim, which also contains the notation introduced for its proof below, see Figure 8.
We prove the claim by induction on r. We will jump into the induction step right away; the base case r = 1 will be dealt with naturally in the midst of that.
Letū be so that I P (X iū ; X iū +1 ) is the smallest among I P (X i u ; X i u+1 ) for u = 0, . . . , q − 1. Imagine removing (iū, iū +1 ) from T. This partitions [n] into two T-connected subsets U and V, with iū ∈ U and iū +1 ∈ V. Clearly we have i = i 0 ∈ U and j = j 0 ∈ V, so at least one edge on the path in T between i = i 0 and j = j 0 goes between U and V. Say (i s , i s+1 ) does. Suppose that i s ∈ U and i s+1 ∈ V (the argument for i s ∈ V and i s+1 ∈ U is similar). Then i s , iū, iū +1 , i s+1 lie on a path in T. Now imagine removing (i s , i s+1 ) from T. This partitions [n] into two T-connected subsets U and V , with is ∈ U and is +1 ∈ V . Clearly we have i = i 0 ∈ U and j = j 0 ∈ V , so at least one edge on the path in T between i = i 0 and j = j 0 goes between U and V . Say (iü, iü +1 ) does. Thus, the path in T between iü and iü +1 must include (i s , i s+1 ). By the cycle property of maximum weight spanning tree we have I P (X iü , X iü +1 ) ≤ I P (X i s , X i s+1 ).
Note that the way we initially pickedū implies I P (X iū ; X iū +1 ) ≤ I P (X iü , X iü +1 ), so we have I P (X iū ; X iū +1 ) ≤ Since minmrg(P iūiū +1 ) ≥ 2 · 10 6 2 n and mindiag(P iūiū +1 ) ≤ 6 · 10 4 2 n , Lemma 4.2.9 implies that mindisc(P iūiū +1 ) ≥ 0.94. We also have minmrg(P iū +1 ) ≥ 2 · 10 6 2 n . Thus, (56) implies mindiag(P iū +1 i s+1 ) ≤ 10 4 2 n . Similarly, Figure 8: An illustration of the setting described in our claim, which also contains the notation introduced for its proof: The solid connections represent edges of T, while the broken connections represent edges of T. The solid curves represent paths in T, while the broken curves represent paths in T. We also show the T-connected subsets U and V obtained from removing the edge (iū, iū +1 ) of T, and the T-connected subsets U and V obtained from removing the edge (is, is +1 ) of T. This illustration is intended only for conveying the basic paradigm. In reality, some of the nodes shown as distinct in the figure might coincide. For example, the path in T between i and j (the upper arch) and the path in T between i and j (the lower arch) might share some nodes. Also, while the path in T between iū and i s must be contained U, nodes such as i or i 1 might not. Similar cautions apply to V, U and V . mindiag(P i s iū ) ≤ 10 4 2 n . We can then apply Lemma 4.2.19 (twice) to get mindiag(P i s i s+1 ) ≤ mindiag(P i s iū ) + mindiag(P iūiū +1 ) + mindiag(P iū +1 i s+1 ) ≤ 8 · 10 4 2 n .
By Lemma 4.2.4 (i) we certainly have mindiag( P i s i s+1 ) ≤ 10 5 2 n . Note minmrg(P i s i s+1 ) ≥ 3 · 10 6 2 n certainly implies minmrg( P i s i s+1 ) ≥ 10 6 2 n (the contrapositive of this follows from Lemma 4.2.3 (ii)). We see that (i s , i s+1 ) satisfies the criterion for a T-avenue and thus must be classified as one.
If r = 1 then (i s , i s+1 ) must simply be (i, j). So i and j belong to the same broken-city and we are done (this is the base case).
If r > 1 then at least one ofs ands + 1 belongs to {1, . . . , r − 1} (so i s is a strict intermediate node on the path in T between i and j). Says does (the other case is argued in the same way).
Therefore, all the nodes and edges on the path in T between iū and i s satisfy the first two bullet points of the claim we are proving. Note that all the nodes and edges on the path in T between i and iū also satisfy those two bullet points by assumption. Since the path in T between i and i s is contained in the union of the path in T between i and iū and the path in T between iū and i s , and the path in T between i and i s is part of the path in T between i and j (so all its nodes satisfy the third bullet point of the claim), we see that all the conditions listed in our claim are satisfied with i and i s in place of i and j. Furthermore, the lengths of the path in T between i and i s is strictly smaller than the length r of the path in T between i and j. The induction setup (assuming the claim is true for all lengths less than r) thus allows us to conclude that i and i s belong to the same broken-city Similarly, all the conditions listed in our claim are satisfied with i s and j in place of i and j, and the length r −s of the path in T between i s and j is strictly smaller than the length r of the path in T between i and j. The induction setup thus allows us to conclude that i s and j belong to the same broken-city.
Combining the two yields that i and j belong to the same broken-city. The induction step is established, and we are done.
Recall that a broken-city might not be T-connected due to the presence of "holes". We now show that every such "hole" must have a small minmrg. That is, it is either almost always equal to 1, or almost always equal to −1. Proof. Let j be any node in conv T ( C) \ C, we want to show that j is biased. First we show that there exist i, k ∈ C such that (i, k) is a T-avenue and that j lies on the path in T between i and k. Suppose not for the sake of contradiction. Imagine removing j and its incidental edges from T. This separates the rest of the nodes into a number (equal to the degree of j in T) of T-connected subsets. The two end-nodes of every T-avenue in C must belong to the same such T-connected subset (call it U), else the path in T between those two end-nodes would pass through j. Since C is spanned by the T-avenues in C, the entire C must in fact be contained in U, and so conv T ( C) must, too. This contradicts the fact that j ∈ conv T ( C).
Intuitively, the following lemma says that the nodes responsible for "gluing together" different brokencities in the same city must be biased in the sense of Definition 4.2.31. Lemma 4.2.33. The path in T between two nodes from different broken-cities in the same city must contain at least one biased node (possibly at one of its two ends).
Proof. Suppose for the sake of contradiction that there is a path in T containing no biased node between some two nodes from different broken-cities in the same city. Since a city is T-connected by Lemma 4.2.26, the entire path must be contained in that same city. Since the two end-nodes of that path belong to different broken-cities, there must exist an edge (i, j) on the path such that i and j belong to different broken-cities (in the same city).
Imagine removing (i, j) from T. This partitions [n] into two T-connected subsets U and V. Note that any broken-city must be contained either entirely in U or entirely in V. Otherwise, its convex hull in T would contain both i and j, and so both i and j must in fact be contained in that broken-city by Lemma 4.2.32 because none of them is biased, a contradiction. Consequently, since U and V are T-connected, the convex hull in T of each broken-city must be contained either entirely in U or entirely in V. It is then easy to see that i and j can't belong to the same city because the sequence of broken-cities bridging between i's and j's broken-cities as required according to Definition 4.2.24 can't possibly exist. This is a contradiction.
The following lemma shows that each T-trail is incidental to at least one biased node and so is close to being independent in H 2 . As a result, they can be cut away without incurring too much error in H 2 .
Lemma 4.2.34. If (i, j) is a T-trail, then at least one of i, j is biased, and I H 2 (P ij ) < 2 · 10 7 2 n . Proof. Suppose for the sake of contradiction that none of i, j is biased. The fact that (i, j) is a T-trail means that i, j belong to the same city. Since T-trails are selected among T-roads (see Definition 4.2.27), we have that (i, j) is a T-road and so Lemma 4.2.33 implies that i, j must belong to the same broken-city. Since (i, j) is not a T-avenue (see Definition 4.2.27), it creates a cycle with the T-avenues spanning that broken-city. This contradicts the description in Definition 4.2.27.
The next lemma contains important structural results regarding the highways. Definition 4.2.22 obviously implies that a T-highway goes between different broken-cities, and (i) below shows that it in fact must go between different cities. Also, (ii) and (iii) show that the T-highways and the T-highways can be matched into parallel pairs, where each parallel pair consists of a T-highway and a T-highway going between the same pair of broken-cities (residing in different cities in the same country). This is an analog of Lemma 3.2.14 for the symmetric case. (ii) There can be at most one T-highway and at most one T-highway between any pair of cities.
(iii) There is a T-highway between a pair of cities if and only if there is a T-highway between the same pair of cities, and if so, those two highways in fact go between the same pair of broken-cities.
Therefore, none of the nodes on the path in T between i and k is biased. Note that (i, k), being a T-highway, obviously goes between different broken-cities. It must in fact go between different cities, as otherwise the path in T between i and k would have to contain at least one biased node by Lemma 4.2.33, a contradiction. This proves (i).
We move on to prove the only if direction of (iii). Keep the notation so far. Let C, ‹ D be broken-cities containing i, k, respectively.
We want to show that there exists a T-highway between C and ‹ D. Suppose for the sake of contradiction that there is no T-highway between C and ‹ D. Note that by (i) C and ‹ D are contained in different cities. They are in the same country because they are linked together directly by the T-highway (i, k). Consequently, there must exist no edge of T at all between C and ‹ D, because any such edge would have been classified as a T-highway according to Definition 4.2.24.
As a result, there must exist some j on the path in T between i and k such that j belongs to neither C nor ‹ D. Since (i, k) is an edge of T, either k sits on the path in T between i and j, or i sits on the path in T between k and j. Without loss of generality we assume it is the former case. Then, by the cycle property of maximum weight spanning trees, we have I P (X i ; X j ) ≤ I P (X i ; X k ). Since i, j, k lie on a path in T, Lemma 4.2.14 (i) implies that H 2 (P ijk , P ij−k ) ≤ 22 2 n . On the other hand, we know that none of i, j, k is biased, so minmrg(P jk ) ≥ 10 7 2 n . Since j, k belong to different broken-cities, Lemma 4.2.30 implies that mindiag(P jk ) > (6 · 10 4 − 1) 2 n . By Lemma 4.2.12 we have mindisc(P ij ) ≥ mindisc(P ik ) ≥ 1 2 − 1 10 20 . Applying Lemma 4.2.15, we have n , a contradiction. We just proved that the existence of a T-highway between a pair of broken-cities (which necessarily lie in different cities by (i)) implies the existence of a T-highway between the same pair of broken-cities. This is the only if direction of (iii). Before tackling the if direction, let's prove (ii) first.
That there can be at most one T-highway between any pair of cities is clear because every city is T-connected by Lemma 4.2.26.
Suppose there are two T-highways between some pair of cities. Because every broken-city is obviously T-connected according to Definition 4.2.22, there can't be more than one edge of T between the same pair of broken-cities. Therefore, those two T-highways must go between two different pairs of broken-cities. The only if direction of (iii) we already proved implies that for each of those two pairs of broken-cities there must be a T-highway going between them. But then there are two T-highways between the same pair of cities, a contradiction. This proves (ii).
We now prove the if direction of (iii). We reset the meaning of all symbols defined so far in this proof (e.g. i, j, k). Suppose (i, j) is a T-highway between broken-cities C and ‹ D, which are contained in cities C and D, respectively.
We first show that there must exist a T-highway between C and D. Suppose not. According to Definition 4.2.24 the fact that (i, j) is a T-highway means C and D are different cities in the same country. Since there is no T-highway between C and D, according to Definition 4.2.24 there must exist a sequence of distinct cities C = C 0 , C 1 , . . . , C r = D, r ≥ 2, such that there is a T-highway between C s and C s+1 for each s. By the only if direction of (iii) we already proved, there is a T-highway between C s and C s+1 for each s. Since each C s is T-connected by Lemma 4.2.26, it is easy to see that there is a path in T between i and j that visits the cities C = C 0 , C 1 , . . . , C r = D, in that order. On the other hand, (i, j) by itself constitutes another path in T between i and j. So we have more than one paths in T between i and j, contradicting the fact that T is a tree.
So there exists a T-highway between C and D. We show that it must in fact go between C and ‹ D. Suppose for the sake of contradiction that it goes between a different pair of broken-cities. By the only if direction of (iii) we already proved, there is a T-highway between that other pair of broken-cities. This means that there is an edge of T different from (i, j) that also goes between C and D, which can't happen because C and D are T-connected by Lemma 4.2.26. This contradiction shows that the existing T-highway between C and D must in fact go between C and ‹ D. This finishes the proof of (iii).
Now we can easily prove that every country is T-connected. The following lemma is the country-level version of Lemma 4.2.33. Figure 9: An illustration of our setting: The solid connections represent edges of T, while the broken connections represent edges of T. The solid curves represent paths in T, while the broken curves represent paths in T. We also show the T-connected subsets U and V obtained from removing the edge (i , j ) of T. This illustration is intended only for conveying the basic paradigm. In reality, some of the nodes shown as distinct in the figure might coincide. For example, the path in T between i and j and the path in T between i and j might share some nodes. Also, while the path in T between i = i 0 and i s = h must be contained U, nodes such as i or i 1 might not. A similar caution applies to V.
The next four lemmas parallelize the four previous lemmas but are one layer lower in the hierarchy.

Lemma 4.2.39.
(i) A T-railway goes between different countries.
(ii) There can be at most one T-railway and at most one T-railway between any pair of countries.
same continent by showing that (h , k ) is a T-road, a T-highway, or a T-railway. Note that h , i , j , k lie on a path in T, and I P (X i ; X j ) ≤ I P (X h ; X k ). Lemma Combining (59), (60), and the one bound we established in between, we see that we have mindisc(P h i ) > 9 10 and mindisc(P j k ) > 9 10 . By Lemma 4.2.18 we have I H 2 (P i k ) ≥ 1 100 mindisc(P j k ) 3 · I H 2 (P i j ) > 10 14 2 n . By Lemma 4.2.18 again we have I H 2 (P h k ) ≥ 1 100 mindisc(P h i ) 3 · I H 2 (P i k ) > 10 11 2 n . Finally, I H 2 ( P h k ) ≥ 1 4 I H 2 (P h k ) > 10 10 2 n by Lemma 4.2.6 (i). According to Definition 4.2.22, (h , k ) is classified as either a T-road, a T-highway, or a T-railway. In any case, h , k belong to the same broken-continent, and therefore to the same continent. Since a continent is T-connected by Lemma 4.2.40, and h , i , j , k lie on a path in T, we see that h , i , j , k all belong to the same continent. This contradicts the fact that i , j belong to different continents (see start of the second paragraph), and the proof is completed.
For a summary of the structural results proved in this section, as well as a diagrammatic illustration, see the part that begins with "Summary of layering" in Section 4.1.

Bounding the Distance between P and Q
This subsection puts together everything we have so far and proves the desired bound in total variation distance between P and Q.
As outlined in Section 4.1, we need a few hybrid distributions to serve as intermediate steps in bounding the total variation distance between P and Q. We specify the underlying tree and the pairwise marginal distributions for the tree edges for all the distributions involved: • P: the underlying tree is T; the marginal for each edge (i, j) of T is P ij ; • P (1) : the underlying tree is T; the marginal for each edge (i, j) of T is P ij , except if (i, j) is a T-airway, in which case the marginal is P • P (5) : the underlying tree isT; the marginal for each edge (i, j) ofT is P ij , except if (i, j) is a T-trail or a T-airway, in which case the marginal is P (ind) ij ; • P (6) : the underlying tree is T; the marginal for each edge (i, j) of T is P ij , except if (i, j) is a T-tunnel, in which case the marginal is P (ind) ij ; • P (7) : the underlying tree is T; the marginal for each edge (i, j) of T is P ij ; • Q: the underlying tree is T; the marginal for each edge (i, j) of T is P ij .
We bound the Hellinger distance separately between each adjacent pair in the list above. The desired total variation distance bound between P and Q as stated in Theorem 4.0.3 then follows from the triangle inequality and the fact that d TV is upper bounded by √ 2 times H (Lemma 2.5.2).
Bounding H(P, P (1) ) To bound the Hellinger distance between P and P (1) , we can apply Corollary 2.5.4 with P = P, P = P (1) , T = T = T, and the sets A λ 's being the continents C 1 , . . . , C Λ , to obtain H 2 (P, P (1) ) ≤ Λ λ=1 H 2 (P C λ , P (1) where E contains all (λ, µ) for which C λ and C µ are straddled by a T-airway, and W λµ consists of the two end-nodes of that straddling edge. The first summation on the right hand side of (61) is zero. For a term in the second summation corresponding to (λ, µ) ∈ E , let the T-airway straddling C λ and C µ be (i, j W λµ ) = H 2 (P ij , P ij ) = H 2 (P ij , P (ind) ij ) = I H 2 (P ij ) < 10 17 2 n .
Bounding H(P (1) , P (2) ) To bound the Hellinger distance between P (1) and P (2) , we can apply Corollary 2.5.4 with P = P (1) , P = P (2) , T = T, T = T (2) , and the sets A λ 's being the countries C 1 , . . . , C Λ to obtain H 2 (P (1) , P (2) ) ≤ W λµ ), where E contains all (λ, µ) for which C λ and C µ are straddled by (1) a T-airway or (2) a T-railway and a T-railway, and W λµ consists of all end-nodes of those straddling edges. The only possibly nonzero terms on the right hand side of (62) are those in the second summation corresponding to (λ, µ) such that C λ and C µ are straddled by a T-railway and a T-railway. For such a pair (λ, µ), let the T-railway straddling C λ and C µ be (i, j), with i ∈ C λ and j ∈ C µ , and the T-railway straddling C λ and C µ be (h, k), with h ∈ C λ and k ∈ C µ . By Lemma 4.2.39 (iii), h, i belong to the same broken-country, and j, k belong to the same broken-country.
First suppose h = i and j = k. In this case, W λµ = {h, i, j, k}, and h, i, j, k lie on a path in T (because every country is T-connected). It is easy to see that i, h, k, j lie on a path in T (because every broken-country is T-connected). So the cycle property of maximum weight spanning trees implies that I P (X i ; X j ) ≤ I P (X h ; X k ).
Note that P (1) hijk equals P hijk , and P (2) hijk equals P h˚ −i j−k (because the edges within each country haven't been replaced yet and are still edges of the true tree T). By Lemma 4.2.14 (ii) we thus have W λµ ) = H 2 (P (1) hijk , P hijk ) = H 2 (P hijk , P h˚ −i j−k ) ≤ 248 2 n .
Next suppose h = i and j = k (the case h = i and j = k is symmetric). In this case, W λµ = {i, j, k}, and i, j, k lie on a path in T. It is easy to see that i, k, j lie on a path in T. So the cycle property of maximum weight spanning trees implies that I P (X i ; X j ) ≤ I P (X i ; X k ). Note that P (1) ijk equals P ijk , and P (2) ijk equals P ij−k . By Lemma 4.2.14 (i) we thus have W λµ ) = H 2 (P (1) ijk , P (2) ijk ) = H 2 (P ijk , P ij−k ) ≤ 22 2 n .
Bounding H(P (2) , P (3) ) This is similar to the bounding between P (1) and P (2) , but centered at the city/highway level of the hierarchy instead of the country/railway level. We apply Corollary 2.5.4 with P = P (2) , P = P (3) , T = T (2) , T = T (3) , and the sets A λ 's being the cities C 1 , . . . , C Λ . The only possibly nonzero terms on the right hand side of the resulting inequality correspond to (λ, µ) for which C λ and C µ are straddled by a T-highway and a T-highway. An analysis parallel to that for the pair P (1) and P (2) leads to H(P (2) , P (3) ) ≤ 16 .
Bounding H(P (3) , P (4) ) To bound the Hellinger distance between P (3) and P (4) , we can apply Corollary 2.5.4 with P = P (3) , P = P (4) , T = T (3) , T =T, and the sets A λ 's being the cities C 1 , . . . , C Λ to obtain H 2 (P (3) , P (4) ) ≤ where E contains all (λ, µ) for which C λ and C µ are straddled by a T-airway, a T-railway, or a T-highway, and W λµ consists of both end-nodes of that straddling edge. The second summation on the right hand side of (63) is zero. We now focus on a term in the first summation corresponding to λ. LetË C λ be the set of all T-avenues and T-trails in C λ .
Ignoring the term ln 1/γ, we look for the smallest constant c such thatˆ 100,0.25 (m) is dominated by c · » 100·ln 100 m for each of the ten sample sizes m under investigation (an even smaller constant can be chosen if we take the term ln 1/γ into consideration). That constant turns out to be 0.502515. The function 0.502515 · » 100·ln 100 m is plotted in Figure 10, along with the ten points (m,ˆ 100,0.25 (m)). Note the nice fit between the two. This provides an indication thatˆ 100,0.25 (m) decreases at the rate of some multiple of

Conclusion and Future Work
In this paper, we establish that there exist computationally efficient algorithms for properly learning treestructured Ising models-which are an equivalent class to tree-structured binary-alphabet Bayesian networks and tree-structured binary-alphabet Markov Random Fields, requiring an asymptotically tight Θ(n ln n/ 2 ) number of samples, where n is the number of nodes and is the total variation distance between the learned model, which is constrained to also be a tree-structured Ising model, and the true model. We note that the constants hidden inside the Θ(·) notation are absolute constants that do not depend on the model being learned. Moreover, the algorithm attaining these guarantees is the celebrated Chow-Liu algorithm using the plug-in estimator to compute, using the available samples, its required pairwise mutual information quantities. Our results are the first to simultaneously attain computational and statistical efficiency for learning tree-structured Ising models, without making extra assumptions on the model being learned. In particular, our required number of samples asymptotically matches that required by the inefficient algorithm suggested by [9]. On the other hand, the vast literature on learning graphical models (e.g. [16,18,20,11,19,1,21,13,10,24,22]) provides sample inefficient methods or computationally inefficient methods, or obtains time and sample efficient algorithms by imposing assumptions on the model being learned, such as upper bounds on the strengths of the edges of the Ising model being learned and bounds on the degree of the underlying graph (or more generally bounds on the total strength of edges adjacent to each node). In contrast, we make no assumptions whatsoever about the model being learned. Finally, consistent with the notion of proper learning, we insist on the output of our algorithm being a tree-structured Ising model, which has downstream computational benefits for doing inference with the learned model. We note that, even if we did not insist on proper learning, there are no known computationally and statistically efficient methods to learn the density of a tree-structured Ising model.
More broadly, our work is motivated by the central challenge of learning high-dimensional probability distributions. Without making any modeling assumptions about the distribution being learned, this task is of course meaningless, facing the curse of dimensionality in terms of both representing the distribution and in terms of the number of samples required to learn it, motivating the definition of various models of high-dimensional distributions with structure, such as Ising models, Bayesian networks, Markov Random Fields, Boltzmann Machines, etc. These models have been used extensively in applications, and recent work has shown that under appropriate assumptions these distributions can be learned computationally and statistically efficiently with respect to the dimension of these distributions [1,21,13,10,24,22,12,3]. The broader goal of our line of work is to provide computationally and statistically efficient algorithms for learning such distributions without making any additional assumptions about the distribution being learned, except that it belongs to one of these families, and we do obtain such algorithms for tree-structured Ising models. Going forward, our work motivates several open problems. The two obvious ones are extending our work from learning tree-structured Ising models to (i) learning tree-structured Markov Random Fields that are jointly Gaussian (i.e. tree-structured Gaussian Random Fields) and (ii) learning tree-structured Markov Random Fields whose nodes take values in a larger discrete alphabet. Even more ambitiously, our work motivates learning (iii) general-structured Ising models, (iv) general-structured Markov Random Fields, whose maximum clique size is bounded by an absolute constant, and (v) general-structured Bayesian networks, whose maximum in-degree is bounded by an absolute constant. In all cases, we don't want to make any additional assumptions about the distributions targeted by (i), (ii), (iii), (iv), and (v). We believe that the techniques developed in this paper can readily serve as a starting point towards resolving (i) and (ii), although additional techniques must be developed to handle the new intricacies imposed by these models. Resolving (iii), (iv) and (v) will necessitate significantly new ideas. While it is unclear what these will be, it is important to point out that the sample complexity of these problems is known to be polynomial as shown, e.g., in [9] for (i) and (iii), and in [4] for (ii), (iv) and (v).