DIMACS Series in Discrete Mathematics and Theoretical Computer Science Survey: Information flow on trees
---
paper_title: Five surprising properties of parsimoniously colored trees

paper_content:

Trees with a coloration of their leaves have an induced “length” which forms the basis of the widely used maximum parsimony method for reconstructing evolutionary trees in biology. Here we describe five unexpected properties of this length function, including refinements of earlier results.
---
paper_title: Taxonomy with confidence

paper_content:

Abstract There are essentially three ways in which four species may be related in a phylogenetic tree graph. It is usual to compute for each of these three possibilities the smallest number of mutations that could have brought about the observed distribution of characteristics among the four species. The graph that minimizes this number is then preferred. In fact, the hypothesis that the graph chosen in this way is correct may be accepted with confidence if the minimum is strong in a sense described here. In principle, the theory could be extended to treat sets of more than four species.
---
paper_title: On the purity of the limiting gibbs state for the Ising model on the Bethe lattice

paper_content:

We give a proof that for the Ising model on the Bethe lattice, the limiting Gibbs state with zero effective field (disordered state) persists to be pure for temperature below the ferromagnetic critical temperatureT c F until the critical temperatureT c SG of the corresponding spin-glass model. This new proof revises the one proposed earlier.
---
paper_title: Elements of Information Theory

paper_content:

Preface to the Second Edition. Preface to the First Edition. Acknowledgments for the Second Edition. Acknowledgments for the First Edition. 1. Introduction and Preview. 1.1 Preview of the Book. 2. Entropy, Relative Entropy, and Mutual Information. 2.1 Entropy. 2.2 Joint Entropy and Conditional Entropy. 2.3 Relative Entropy and Mutual Information. 2.4 Relationship Between Entropy and Mutual Information. 2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information. 2.6 Jensen's Inequality and Its Consequences. 2.7 Log Sum Inequality and Its Applications. 2.8 Data-Processing Inequality. 2.9 Sufficient Statistics. 2.10 Fano's Inequality. Summary. Problems. Historical Notes. 3. Asymptotic Equipartition Property. 3.1 Asymptotic Equipartition Property Theorem. 3.2 Consequences of the AEP: Data Compression. 3.3 High-Probability Sets and the Typical Set. Summary. Problems. Historical Notes. 4. Entropy Rates of a Stochastic Process. 4.1 Markov Chains. 4.2 Entropy Rate. 4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph. 4.4 Second Law of Thermodynamics. 4.5 Functions of Markov Chains. Summary. Problems. Historical Notes. 5. Data Compression. 5.1 Examples of Codes. 5.2 Kraft Inequality. 5.3 Optimal Codes. 5.4 Bounds on the Optimal Code Length. 5.5 Kraft Inequality for Uniquely Decodable Codes. 5.6 Huffman Codes. 5.7 Some Comments on Huffman Codes. 5.8 Optimality of Huffman Codes. 5.9 Shannon-Fano-Elias Coding. 5.10 Competitive Optimality of the Shannon Code. 5.11 Generation of Discrete Distributions from Fair Coins. Summary. Problems. Historical Notes. 6. Gambling and Data Compression. 6.1 The Horse Race. 6.2 Gambling and Side Information. 6.3 Dependent Horse Races and Entropy Rate. 6.4 The Entropy of English. 6.5 Data Compression and Gambling. 6.6 Gambling Estimate of the Entropy of English. Summary. Problems. Historical Notes. 7. Channel Capacity. 7.1 Examples of Channel Capacity. 7.2 Symmetric Channels. 7.3 Properties of Channel Capacity. 7.4 Preview of the Channel Coding Theorem. 7.5 Definitions. 7.6 Jointly Typical Sequences. 7.7 Channel Coding Theorem. 7.8 Zero-Error Codes. 7.9 Fano's Inequality and the Converse to the Coding Theorem. 7.10 Equality in the Converse to the Channel Coding Theorem. 7.11 Hamming Codes. 7.12 Feedback Capacity. 7.13 Source-Channel Separation Theorem. Summary. Problems. Historical Notes. 8. Differential Entropy. 8.1 Definitions. 8.2 AEP for Continuous Random Variables. 8.3 Relation of Differential Entropy to Discrete Entropy. 8.4 Joint and Conditional Differential Entropy. 8.5 Relative Entropy and Mutual Information. 8.6 Properties of Differential Entropy, Relative Entropy, and Mutual Information. Summary. Problems. Historical Notes. 9. Gaussian Channel. 9.1 Gaussian Channel: Definitions. 9.2 Converse to the Coding Theorem for Gaussian Channels. 9.3 Bandlimited Channels. 9.4 Parallel Gaussian Channels. 9.5 Channels with Colored Gaussian Noise. 9.6 Gaussian Channels with Feedback. Summary. Problems. Historical Notes. 10. Rate Distortion Theory. 10.1 Quantization. 10.2 Definitions. 10.3 Calculation of the Rate Distortion Function. 10.4 Converse to the Rate Distortion Theorem. 10.5 Achievability of the Rate Distortion Function. 10.6 Strongly Typical Sequences and Rate Distortion. 10.7 Characterization of the Rate Distortion Function. 10.8 Computation of Channel Capacity and the Rate Distortion Function. Summary. Problems. Historical Notes. 11. Information Theory and Statistics. 11.1 Method of Types. 11.2 Law of Large Numbers. 11.3 Universal Source Coding. 11.4 Large Deviation Theory. 11.5 Examples of Sanov's Theorem. 11.6 Conditional Limit Theorem. 11.7 Hypothesis Testing. 11.8 Chernoff-Stein Lemma. 11.9 Chernoff Information. 11.10 Fisher Information and the Cram-er-Rao Inequality. Summary. Problems. Historical Notes. 12. Maximum Entropy. 12.1 Maximum Entropy Distributions. 12.2 Examples. 12.3 Anomalous Maximum Entropy Problem. 12.4 Spectrum Estimation. 12.5 Entropy Rates of a Gaussian Process. 12.6 Burg's Maximum Entropy Theorem. Summary. Problems. Historical Notes. 13. Universal Source Coding. 13.1 Universal Codes and Channel Capacity. 13.2 Universal Coding for Binary Sequences. 13.3 Arithmetic Coding. 13.4 Lempel-Ziv Coding. 13.5 Optimality of Lempel-Ziv Algorithms. Compression. Summary. Problems. Historical Notes. 14. Kolmogorov Complexity. 14.1 Models of Computation. 14.2 Kolmogorov Complexity: Definitions and Examples. 14.3 Kolmogorov Complexity and Entropy. 14.4 Kolmogorov Complexity of Integers. 14.5 Algorithmically Random and Incompressible Sequences. 14.6 Universal Probability. 14.7 Kolmogorov complexity. 14.9 Universal Gambling. 14.10 Occam's Razor. 14.11 Kolmogorov Complexity and Universal Probability. 14.12 Kolmogorov Sufficient Statistic. 14.13 Minimum Description Length Principle. Summary. Problems. Historical Notes. 15. Network Information Theory. 15.1 Gaussian Multiple-User Channels. 15.2 Jointly Typical Sequences. 15.3 Multiple-Access Channel. 15.4 Encoding of Correlated Sources. 15.5 Duality Between Slepian-Wolf Encoding and Multiple-Access Channels. 15.6 Broadcast Channel. 15.7 Relay Channel. 15.8 Source Coding with Side Information. 15.9 Rate Distortion with Side Information. 15.10 General Multiterminal Networks. Summary. Problems. Historical Notes. 16. Information Theory and Portfolio Theory. 16.1 The Stock Market: Some Definitions. 16.2 Kuhn-Tucker Characterization of the Log-Optimal Portfolio. 16.3 Asymptotic Optimality of the Log-Optimal Portfolio. 16.4 Side Information and the Growth Rate. 16.5 Investment in Stationary Markets. 16.6 Competitive Optimality of the Log-Optimal Portfolio. 16.7 Universal Portfolios. 16.8 Shannon-McMillan-Breiman Theorem (General AEP). Summary. Problems. Historical Notes. 17. Inequalities in Information Theory. 17.1 Basic Inequalities of Information Theory. 17.2 Differential Entropy. 17.3 Bounds on Entropy and Relative Entropy. 17.4 Inequalities for Types. 17.5 Combinatorial Bounds on Entropy. 17.6 Entropy Rates of Subsets. 17.7 Entropy and Fisher Information. 17.8 Entropy Power Inequality and Brunn-Minkowski Inequality. 17.9 Inequalities for Determinants. 17.10 Inequalities for Ratios of Determinants. Summary. Problems. Historical Notes. Bibliography. List of Symbols. Index.
---
paper_title: Reconstruction on trees: Beating the second eigenvalue

paper_content:

We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T . We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an independent copy of some channel (Markov chain) M, where M is irreducible and aperiodic on A. The goal is to reconstruct the symbol at the root from the symbols at the nth level of the tree. This model has been studied in information theory, genetics, and statistical physics. The basic question is: Is it possible to reconstruct (some information on) the root? In other words, does the probability of correct reconstruction tend to 1=jAj as n ! 1? It is known that reconstruction is possible if d 2 (M) > 1, where 2(M) is the second eigen-value of M. Moreover, in this case it is possible to reconstruct using a majority algorithm which ignores the location of the data at the boundary of the tree. When M is a symmetric binary channel, this threshold is sharp. In this paper we show, that both for the binary asymmetric channel and for the symmetric channel on many symbols it is sometimes possible to reconstruct even when d 2 (M) < 1. This result indicates that for many (maybe most) tree indexed Markov chains the location of the data on the boundary plays a crucial role in reconstruction problems.
---
paper_title: Glauber dynamics on trees and hyperbolic graphs

paper_content:

Abstract.We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |λ1−λ2|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time τ2 satisfies τ2=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.
---
paper_title: Reconstruction on trees: Beating the second eigenvalue

paper_content:

We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T . We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an independent copy of some channel (Markov chain) M, where M is irreducible and aperiodic on A. The goal is to reconstruct the symbol at the root from the symbols at the nth level of the tree. This model has been studied in information theory, genetics, and statistical physics. The basic question is: Is it possible to reconstruct (some information on) the root? In other words, does the probability of correct reconstruction tend to 1=jAj as n ! 1? It is known that reconstruction is possible if d 2 (M) > 1, where 2(M) is the second eigen-value of M. Moreover, in this case it is possible to reconstruct using a majority algorithm which ignores the location of the data at the boundary of the tree. When M is a symmetric binary channel, this threshold is sharp. In this paper we show, that both for the binary asymmetric channel and for the symmetric channel on many symbols it is sometimes possible to reconstruct even when d 2 (M) < 1. This result indicates that for many (maybe most) tree indexed Markov chains the location of the data on the boundary plays a crucial role in reconstruction problems.
---
paper_title: On the maximum tolerable noise for reliable computation by formulas

paper_content:

It is shown that if formulas constructed from error-prone three-input gates are used to compute Boolean functions, then a per-gate failure probability of 1/6 or more cannot be tolerated. The result is shown to be tight if the per-gate failure probability is constant and precisely known. >
---
paper_title: On the purity of the limiting gibbs state for the Ising model on the Bethe lattice

paper_content:

We give a proof that for the Ising model on the Bethe lattice, the limiting Gibbs state with zero effective field (disordered state) persists to be pure for temperature below the ferromagnetic critical temperatureT c F until the critical temperatureT c SG of the corresponding spin-glass model. This new proof revises the one proposed earlier.
---
paper_title: On the extremality of the disordered state for the Ising model on the Bethe lattice

paper_content:

We give a simple proof that the limit Ising Gibbs measure with free boundary conditions on the Bethe lattice with the forward branching ratio k≥2 is extremal if and only if β is less or equal to the spin glass transition value, given by tanh(β c SG = 1/√k.
---
paper_title: Glauber dynamics on trees and hyperbolic graphs

paper_content:

Abstract.We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |λ1−λ2|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time τ2 satisfies τ2=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.
---
paper_title: Reconstruction on trees: Beating the second eigenvalue

paper_content:

We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T . We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an independent copy of some channel (Markov chain) M, where M is irreducible and aperiodic on A. The goal is to reconstruct the symbol at the root from the symbols at the nth level of the tree. This model has been studied in information theory, genetics, and statistical physics. The basic question is: Is it possible to reconstruct (some information on) the root? In other words, does the probability of correct reconstruction tend to 1=jAj as n ! 1? It is known that reconstruction is possible if d 2 (M) > 1, where 2(M) is the second eigen-value of M. Moreover, in this case it is possible to reconstruct using a majority algorithm which ignores the location of the data at the boundary of the tree. When M is a symmetric binary channel, this threshold is sharp. In this paper we show, that both for the binary asymmetric channel and for the symmetric channel on many symbols it is sometimes possible to reconstruct even when d 2 (M) < 1. This result indicates that for many (maybe most) tree indexed Markov chains the location of the data on the boundary plays a crucial role in reconstruction problems.
---
paper_title: Large Deviations Techniques and Applications

paper_content:

LDP for Finite Dimensional Spaces.- Applications-The Finite Dimensional Case.- General Principles.- Sample Path Large Deviations.- The LDP for Abstract Empirical Measures.- Applications of Empirical Measures LDP.
---
paper_title: Reconstruction on trees: Beating the second eigenvalue

paper_content:

We consider a process in which information is transmitted from a given root node on a noisy d-ary tree network T . We start with a uniform symbol taken from an alphabet A. Each edge of the tree is an independent copy of some channel (Markov chain) M, where M is irreducible and aperiodic on A. The goal is to reconstruct the symbol at the root from the symbols at the nth level of the tree. This model has been studied in information theory, genetics, and statistical physics. The basic question is: Is it possible to reconstruct (some information on) the root? In other words, does the probability of correct reconstruction tend to 1=jAj as n ! 1? It is known that reconstruction is possible if d 2 (M) > 1, where 2(M) is the second eigen-value of M. Moreover, in this case it is possible to reconstruct using a majority algorithm which ignores the location of the data at the boundary of the tree. When M is a symmetric binary channel, this threshold is sharp. In this paper we show, that both for the binary asymmetric channel and for the symmetric channel on many symbols it is sometimes possible to reconstruct even when d 2 (M) < 1. This result indicates that for many (maybe most) tree indexed Markov chains the location of the data on the boundary plays a crucial role in reconstruction problems.
---
paper_title: Gibbs Measures and Dismantlable Graphs

paper_content:

We model physical systems with “hard constraints” by the space Hom(G, H) of homomorphisms from a locally finite graph G to a fixed finite constraint graph H. Two homomorphisms are deemed to be adjacent if they differ on a single site of G. We investigate what appears to be a fundamental dichotomy of constraint graphs, by giving various characterizations of a class of graphs that we call dismantlable. For instance, H is dismantlable if and only if, for every G, any two homomorphisms from G to H which differ at only finitely many sites are joined by a path in Hom(G, H). If H is dismantlable, then, for any G of bounded degree, there is some assignment of activities to the nodes of H for which there is a unique Gibbs measure on Hom(G, H). On the other hand, if H is not dismantlable (and not too trivial), then there is some r such that, whatever the assignment of activities on H, there are uncountably many Gibbs measures on Hom(Tr, H), where Tr is the (r+1)-regular tree.
---
paper_title: The random-cluster model on a homogeneous tree

paper_content:

The random-cluster model on a homogeneous tree is defined and studied. It is shown that for 1≦q≦2, the percolation probability in the maximal random-cluster measure is continuous inp, while forq>2 it has a discontinuity at the critical valuep=p c (q). It is also shown that forq>2, there is nonuniqueness of random-cluster measures for an entire interval of values ofp. The latter result is in sharp contrast to what happens on the integer lattice Z d .
---
paper_title: Reliable computation by formulas in the presence of noise

paper_content:

It is shown that if formulas are used to compute Boolean functions in the presence of randomly occurring failures then: (1) there is a limit strictly less than 1/2 to the failure probability per gate that can be tolerated, and (2) formulas that tolerate failures must be deeper (and, therefore, compute more slowly) than those that do not. The heart of the proof is an information-theoretic argument that deals with computation and errors in very general terms. The strength of this argument is that it applies with equal ease no matter what types of gate are available. Its weaknesses is that it does not seem to predict quantitatively the limiting value of the failure probability or the ratio by which computation proceeds more slowly in the presence of failures. >
---
paper_title: Phase transitions in phylogeny

paper_content:

We apply the theory of markov random fields on trees to derive a phase transition in the number of samples needed in order to reconstruct phylogenies. ::: We consider the Cavender-Farris-Neyman model of evolution on trees, where all the inner nodes have degree at least 3, and the net transition on each edge is bounded by e. Motivated by a conjecture by M. Steel, we show that if 2 (1 - 2 e) (1 - 2e) > 1, then for balanced trees, the topology of the underlying tree, having n leaves, can be reconstructed from O(log n) samples (characters) at the leaves. On the other hand, we show that if 2 (1 - 2 e) (1 - 2 e) < 1, then there exist topologies which require at least poly(n) samples for reconstruction. ::: Our results are the first rigorous results to establish the role of phase transitions for markov random fields on trees as studied in probability, statistical physics and information theory to the study of phylogenies in mathematical biology.
---
paper_title: Taxonomy with confidence

paper_content:

Abstract There are essentially three ways in which four species may be related in a phylogenetic tree graph. It is usual to compute for each of these three possibilities the smallest number of mutations that could have brought about the observed distribution of characteristics among the four species. The graph that minimizes this number is then preferred. In fact, the hypothesis that the graph chosen in this way is correct may be accepted with confidence if the minimum is strong in a sense described here. In principle, the theory could be extended to treat sets of more than four species.
---
paper_title: Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology

paper_content:

Fitch, W. M. (Dept. of Physiological Chemistry, Univ. of Wisconsin, Madison, Wisconsin, 53706), 1971. Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool., 20:406-416.-A method is presented that is asserted to provide all hypothetical ancestral character states that are consistent with describing the descent of the present-day character states in a minimum number of changes of state using a predetermined phylogenetic relationship among the taxa represented. The character states used as examples are the four messenger RNA nucleotides encoding the amino acid sequences of proteins, but the method is general. [Evolution; parsimonious trees.] It has been a goal of those attempting to deduce phylogenetic relationships from information on biological characteristics to find the ancestral relationship(s) that would permit one to account for the descent of those characteristics in a manner requiring a minimum number of evolutionary steps or changes. The result could be called the most parsimonious evolutionary tree and might be expected to have a high degree of correspondence to the true phylogeny (Camin and Sokal, 1965). It's justification lies in the most efficient use of the information available and does not presuppose that evolution follows a most parsimonious course. There are no known algorithms for finding the most parsimonious tree(s) apart from the brute force method of examining nearly every possible tree.' This is impractical for trees involving a dozen or more taxonomic units. Most numerical taxonomic procedures (Sokal and Sneath, 1963; Farris, 1969, 1970; Fitch and Margoliash, 1967) provide dendrograms that would be among the more parsimonious solutions; one just cannot be sure that a more parsimonious tree structure does not exist. Farris (1970) has explicitly considered the parsimony principle as a part of 'An elegant beginning to an attack on the problem has recently been published by Farris (1969) who developed a method which estimates the reliability of various characters and then weights the characters on the basis of that reliability. his method which, like the present method, has its roots in the Wagner tree (Wagner,
---
paper_title: On the purity of the limiting gibbs state for the Ising model on the Bethe lattice

paper_content:

We give a proof that for the Ising model on the Bethe lattice, the limiting Gibbs state with zero effective field (disordered state) persists to be pure for temperature below the ferromagnetic critical temperatureT c F until the critical temperatureT c SG of the corresponding spin-glass model. This new proof revises the one proposed earlier.
---
paper_title: Recursions on trees and the ising model at critical temperatures

paper_content:

A leak-proof stackable container for shipping ice cooled foodstuff has a bottom provided with a centrally located well. Between the upstanding walls of the container and the upstanding walls of the well there is a peripheral bottom portion uniting these walls and providing support for wooden fillet boxes or perforated plates on which perishable food mixed with ice is deposited. The container is covered with a lid having a centrally located recess of a size to receive the well of a second container stacked thereon. The lid is provided with flanges engaging the upper lip of the container to seal the contents in the container. The lid and container may be insulated with a foamed plastic. Fore greater strength the walls are strengthened with ribs.
---
paper_title: On the extremality of the disordered state for the Ising model on the Bethe lattice

paper_content:

We give a simple proof that the limit Ising Gibbs measure with free boundary conditions on the Bethe lattice with the forward branching ratio k≥2 is extremal if and only if β is less or equal to the spin glass transition value, given by tanh(β c SG = 1/√k.
---
paper_title: Signal propagation, with application to a lower bound on the depth of noisy formulas

paper_content:

We study the decay of an information signal propagating through a series of noisy channels. We obtain exact bounds on such decay, and as a result provide a new lower bound on the depth of formulas with noisy components. This improves upon previous work of N. Pippenger (1988) and significantly decreases the gap between his lower bound and the classical upper bound of von Neumann. We also discuss connections between our work and the study of mixing rates of Markov chains. >
---
paper_title: On the impossibility of reconstructing ancestral data and phylogenies

paper_content:

We prove that it is impossible to reconstruct ancestral data at the root of "deep" phylogenetic trees with high mutation rates. Moreover, we prove that it is impossible to reconstruct the topology of "deep" trees with high mutation rates from a number of characters smaller than a low-degree polynomial in the number of leaves. Our impossibility results hold for all reconstruction methods. The proofs apply tools from information theory and percolation theory.
---
paper_title: Glauber dynamics on trees and hyperbolic graphs

paper_content:

Abstract.We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |λ1−λ2|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time τ2 satisfies τ2=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.
---
paper_title: The Ising model on trees: boundary conditions and mixing time

paper_content:

We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics for the Ising model. Specifically, we show that the mixing time on an -vertex regular tree with -boundary remains at all temperatures (in contrast to the free boundary case, where the mixing time is not bounded by any fixed polynomial at low temperatures). We also show that this bound continues to hold in the presence of an arbitrary external field. Our results are actually stronger, and provide tight bounds on the log-Sobolev constant and the spectral gap of the dynamics. In addition, our methods yield simpler proofs and stronger results for the mixing time in the regime where it is insensitive to the boundary condition. Our techniques also apply to a much wider class of models, including those with hard constraints like the antiferromagnetic Potts model at zero temperature (colorings) and the hard-core model (independent sets).
---
paper_title: A Phase Transition for a Random Cluster Model on Phylogenetic Trees

paper_content:

We investigate a simple model that generates random partitions of the leaf set of a tree. Of particular interest is the reconstruction question: what number k of independent samples (partitions) are required to correctly reconstruct the underlying tree (with high probability)? We demonstrate a phase transition for k as a function of the mutation rate, from logarithmic to polynomial dependence on the size of the tree. We also describe a simple polynomial-time tree reconstruction algorithm that applies in the logarithmic region. This model and the associated reconstruction questions are motivated by a Markov model for genomic evolution in molecular biology.
---
paper_title: Reconstruction thresholds on regular trees

paper_content:

We consider a branching random walk with binary state space and index set $T^k$, the infinite rooted tree in which each node has k children (also known as the model of "broadcasting on a tree"). The root of the tree takes a random value 0 or 1, and then each node passes a value independently to each of its children according to a 2x2 transition matrix P. We say that "reconstruction is possible" if the values at the d'th level of the tree contain non-vanishing information about the value at the root as $d\to\infty$. Adapting a method of Brightwell and Winkler, we obtain new conditions under which reconstruction is impossible, both in the general case and in the special case $p_{11}=0$. The latter case is closely related to the "hard-core model" from statistical physics; a corollary of our results is that, for the hard-core model on the (k+1)-regular tree with activity $\lambda=1$, the unique simple invariant Gibbs measure is extremal in the set of Gibbs measures, for any k.
---
paper_title: Phase transitions in phylogeny

paper_content:

We apply the theory of markov random fields on trees to derive a phase transition in the number of samples needed in order to reconstruct phylogenies. ::: We consider the Cavender-Farris-Neyman model of evolution on trees, where all the inner nodes have degree at least 3, and the net transition on each edge is bounded by e. Motivated by a conjecture by M. Steel, we show that if 2 (1 - 2 e) (1 - 2e) > 1, then for balanced trees, the topology of the underlying tree, having n leaves, can be reconstructed from O(log n) samples (characters) at the leaves. On the other hand, we show that if 2 (1 - 2 e) (1 - 2 e) < 1, then there exist topologies which require at least poly(n) samples for reconstruction. ::: Our results are the first rigorous results to establish the role of phase transitions for markov random fields on trees as studied in probability, statistical physics and information theory to the study of phylogenies in mathematical biology.
---
paper_title: Robust reconstruction on trees is determined by the second eigenvalue

paper_content:

Consider a Markov chain on an infinite tree T = (V,E) rooted at . In such a chain, once the initial root state ( ) is chosen, each vertex iteratively chooses its state from the one of its parent by an application of a Markov transition rule (and all such applications are independent). Let µj denote the resulting measure for ( ) = j. µj is defined on configurations = ( (x))x2V 2 A V , where A is some finite set. Let µ n denote the restriction of µ to the sigma-algebra generated by the variables (x) where x is at distance exactly n from . Letting n = maxi,j2A dTV (µ n ,µ n ), where dTV denotes total variation distance, we say that the reconstruction problem is solvable if liminfn!1 n > 0. Reconstruction solvability roughly means that the n’th level of the tree contains a non-vanishing amount of information on the root of the tree, as n ! 1. In this paper we study the problem of robust reconstruction. Let be a non degenerate distribution on A and > 0. Let be chosen according to µ n and 0 be obtained from by letting for each node independently (v) = 0 (v) with probability 1 and 0 (v) to be an independent sample from otherwise. We denote by µ n [, ] the resulting measure on 0 . The measure µ n [, ] is a perturbation of the measure µ n . Letting n(, ) = maxi,j2A dTV (µ n [, ],µ n [, ]), we say that the reconstruction problem is -robust-solvable if liminfn!1 n(, ) > 0 for all 0 1, where 2(M) is the second largest eigenvalue of M (in absolute value), then for all non-degenerate , the reconstruction problem is -robust-solvable. We prove a converse and show that the reconstruction problem is not -robust-solvable if B| 2(M)| 2 < 1. This proves a conjecture by the second author and Peres. We also consider other models of noise and general trees.
---
paper_title: On the impossibility of reconstructing ancestral data and phylogenies

paper_content:

We prove that it is impossible to reconstruct ancestral data at the root of "deep" phylogenetic trees with high mutation rates. Moreover, we prove that it is impossible to reconstruct the topology of "deep" trees with high mutation rates from a number of characters smaller than a low-degree polynomial in the number of leaves. Our impossibility results hold for all reconstruction methods. The proofs apply tools from information theory and percolation theory.
---

Title: DIMACS Series in Discrete Mathematics and Theoretical Computer Science Survey: Information flow on trees

Section 1: Introduction
Description 1: Introduce the concept of information flow on trees and discuss its significance in genetic propagation and communication networks.

Section 2: The reconstruction problem
Description 2: Define the process and explore the solvability of the reconstruction problem, including census solvability and equivalent definitions.

Section 3: The Ising model
Description 3: Discuss the Ising model on trees, including known results for symmetric binary channels and various reconstruction algorithms.

Section 4: Census solvability
Description 4: Investigate the threshold for census solvability and demonstrate the conditions under which the root can be reconstructed using the census of the tree level.

Section 5: Potts models
Description 5: Explore the reconstruction problem for Potts models, including asymmetric binary channels and ferromagnetic models, with associated threshold conditions.

Section 6: General channels
Description 6: Discuss techniques and criteria applicable to the reconstruction problem for general channels, including recursive methods and spectral gaps in Glauber dynamics.

Section 7: Terminology and related problems
Description 7: Review related problems and terminology from various fields, such as statistical physics, information theory, and biology, and discuss their connections to the reconstruction problem.

Section 8: Very recent results
Description 8: Highlight new developments and recent findings related to the reconstruction problem, including better bounds and robust solvability.