Broadcasting on trees and the Ising model. (English) Zbl 1052.60076

The authors consider the following process. At the root \(\rho\) of a tree \(T\) there is a binary random variable (spin) taking its values with equal probabilities. This bit is then propagated through the tree as follows: each vertex receives the bit from its parent unchanged with probability \((1-\varepsilon)\) and changed with probability \(\varepsilon\in (0, 1/2]\). The events on different edges are statistically independent. Let \(W\) be a subset of the set of vertices of \(T\). For such \(W\), let the set of the bits arrived at each element of \(W\) be given. Then one tries to reconstruct the original bit on the base of this information. Clearly the probability to do this correctly is at least \(1/2\); denote this probability by \((1+\Delta)/2\), where \(\Delta = \Delta (T, W, \varepsilon)\). The main results of the paper are upper and lower bounds for such \(\Delta(T, W, \varepsilon)\). If the tree is infinite, the bounds yield the following: \(\lim_{n\rightarrow +\infty} \Delta(T, T_n \varepsilon) > 0\) if \(\varepsilon < \varepsilon_c\) and \(\lim_{n\rightarrow +\infty} \Delta(T, T_n \varepsilon) = 0\) if \(\varepsilon > \varepsilon_c\). Here \(T_n\) is the set of the vertices of \(T\) of \(n\)th level. For regular trees, the problem of determining \(\varepsilon_c\) was solved by P. M. Bleher, J. Ruiz and V. A. Zagrebnov [J. Stat. Phys. 79, 473–482 (1995; Zbl 1081.82515)].


60K35 Interacting random processes; statistical mechanics type models; percolation theory
68M10 Network design and communication in computer systems
68R99 Discrete mathematics in relation to computer science
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics


Zbl 1081.82515
Full Text: DOI


[1] Benjamini, I., Pemantle, R. and Peres, Y. (1998). Unpredictable paths and percolation. Ann. Probab. 26 1198-1211. · Zbl 0937.60070
[2] Bleher, P. M., Ruiz, J. and Zagrebnov, V. A. (1995). On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice. J. Statist. Phys. 79 473-482. · Zbl 1081.82515
[3] Brightwell, G. R. and Winkler, P. (1999). Graph homomorphisms and phase transitions. J. Combin. Theory Ser. A. · Zbl 1026.05028
[4] Cavender, J. (1978). Taxonomy with confidence. Math. Biosci. 40 271-280. · Zbl 0391.92015
[5] Chayes, J. T., Chayes, L., Sethna, J. P. and Thouless, D. J. (1986). A mean field spin glass with short range interactions, Comm. Math. Phys. 106 41-89.
[6] Cover, T. M. and Thomas, J. A. (1991). Elements of Information Theory. Wiley, New York. · Zbl 0762.94001
[7] Doyle, P. G. and Snell, E. J. (1984). Random Walks and Electrical Networks. Math. Assoc. Amer., Washington, D.C. · Zbl 0583.60065
[8] Evans, W. (1994). Information theory and noisy computation. Ph.D. dissertation, Dept. Computer Science, Univ. California, Berkeley.
[9] Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (1995). A critical phenomenon in a broadcast process. Unpublished manuscript.
[10] Evans, W. and Schulman, L. J. (1993). Signal propagation, with application to a lower bound on the depth of noisy formulas. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science 594-603.
[11] Evans, W. and Schulman, L. J. (1994). Lower bound on the depth of noisy circuits. Unpublished manuscript.
[12] Fitch, W. M. (1971). Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20 406-416.
[14] Georgii, H. O. (1988). Gibbs Measures and Phase Transitions. de Gruyter, Berlin. · Zbl 0657.60122
[15] Grimmett, G. R. (1996). Percolation and disordered systems. Lectures in Probability Theory and Statistics, Ecole d’Eté de Probabilités de Saint Flour XXVI. Lecture Notes in Math. 1665 153-300. Springer, Berlin. · Zbl 0884.60089
[16] Häggstr öm, O. and Mossel, E. (1998). A nearest neighbor process with low predictability and percolation in 2 + dimensions. Ann. Probab. 26 1212-1231. · Zbl 0937.60071
[17] Hajek, B. and Weller, T. (1991). On the maximum tolerable noise for reliable computation by formulas. IEEE Trans. Inform. Theory 37 388-391. · Zbl 0721.94025
[18] Hartigan, J. A. (1971). Minimum mutation fits to a given tree. Biometrics 29 53-65.
[19] Higuchi, Y. (1977). Remarks on the limiting Gibbs state on a d+1 -tree. Publ. RIMS Kyoto Univ. 13 335-348. · Zbl 0376.60096
[20] Ioffe, D. (1996). A note on the extremality of the disordered state for the Ising model on the Bethe lattice. Lett. Math. Phys. 37 137-143. · Zbl 0848.60090
[21] Ioffe, D. (1996). A note on the extremality of the disordered state for the Ising model on the Bethe lattice. In Trees (B. Chauvin, S. Cohen, A. Roualt, eds.). Birkhäuser, Boston. · Zbl 0848.60090
[22] Kesten, H. and Stigum, B. P. (1966). Additional limit theorems for indecomposable multidimensional Galton-Watson processes. Ann. Math. Statist. 37 1463-1481. · Zbl 0203.17402
[23] Le Cam, L. (1974). Notes on Asymptotic Methods in Statistical Decision Theory. Centre de Rech. Math., Univ. Montréal.
[24] Lyons, R. (1989). The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys. 125 337-352. · Zbl 0679.60101
[25] Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931-958. · Zbl 0714.60089
[26] Lyons, R. (1992). Random walks, capacity, and percolation on trees. Ann. Probab. 20 2043- 2088. · Zbl 0766.60091
[27] Lyons, R. and Peres, Y. (1997). Probability on Trees and Networks. To appear. Available at http://php.indiana.edu/ rdlyons/. URL:
[28] Moore, T. and Snell, J. L. (1979). A branching process showing a phase transition. J. Appl. Probab. 16 252-260. JSTOR: · Zbl 0421.60052
[29] Mossel, E. (1998). Recursive reconstruction on periodic trees. Random Structures Algorithms 13 81-97. · Zbl 0959.05112
[30] Mossel, E. (1999). Reconstruction on trees: beating the second eigenvalue. Unpublished manuscript. · Zbl 1021.90008
[31] Pemantle, R. and Peres, Y. (1994). Domination between trees and application to an explosion problem. Ann. Probab. 22 180-194. · Zbl 0806.60098
[32] Pemantle, R. and Peres, Y. (1995). Recursions on trees and the Ising model at critical temperatures. Unpublished manuscript. · Zbl 0837.60066
[33] Pippenger, N. (1988). Reliable computation by formulas in the presence of noise. IEEE Trans. Inform. Theory 34 194-197. · Zbl 0652.94022
[34] Preston, C. J. (1974). Gibbs States on Countable Sets. Cambridge Univ. Press. · Zbl 0297.60054
[35] Spitzer, F. (1975). Markov random fields on an infinite tree. Ann Probab. 3 387-394. · Zbl 0313.60072
[36] Steel, M. (1989). Distribution in bicolored evolutionary trees. Ph.D. thesis, Massey Univ., Palmerston North, New Zealand.
[37] Steel, M. and Charleston, M. (1995). Five surprising properties of parsimoniously colored trees. Bull. Math. Biology 57 367-375. · Zbl 0822.92013
[38] Vajda, I. (1989). Theory of Statistical Inference and Information. Kluwer, Dordrecht. · Zbl 0711.62002
[39] von Neumann, J. (1956). Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata Studies (C. E. Shannon and J. McCarthy, eds.) 43-98. Princeton Univ. Press.
[40] LRI, Université de Paris-Sud Orsay France E-mail: Claire.Kenyon@lri.fr
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.