## 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)].

### MSC:

 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

### Keywords:

Percolation; spin; Ising model; electrical network; noisy computation

Zbl 1081.82515
Full Text:

### References:

  Benjamini, I., Pemantle, R. and Peres, Y. (1998). Unpredictable paths and percolation. Ann. Probab. 26 1198-1211. · Zbl 0937.60070  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  Brightwell, G. R. and Winkler, P. (1999). Graph homomorphisms and phase transitions. J. Combin. Theory Ser. A. · Zbl 1026.05028  Cavender, J. (1978). Taxonomy with confidence. Math. Biosci. 40 271-280. · Zbl 0391.92015  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.  Cover, T. M. and Thomas, J. A. (1991). Elements of Information Theory. Wiley, New York. · Zbl 0762.94001  Doyle, P. G. and Snell, E. J. (1984). Random Walks and Electrical Networks. Math. Assoc. Amer., Washington, D.C. · Zbl 0583.60065  Evans, W. (1994). Information theory and noisy computation. Ph.D. dissertation, Dept. Computer Science, Univ. California, Berkeley.  Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (1995). A critical phenomenon in a broadcast process. Unpublished manuscript.  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.  Evans, W. and Schulman, L. J. (1994). Lower bound on the depth of noisy circuits. Unpublished manuscript.  Fitch, W. M. (1971). Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20 406-416.  EVANS, KENYON, PERES AND SCHULMAN  Georgii, H. O. (1988). Gibbs Measures and Phase Transitions. de Gruyter, Berlin. · Zbl 0657.60122  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  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  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  Hartigan, J. A. (1971). Minimum mutation fits to a given tree. Biometrics 29 53-65.  Higuchi, Y. (1977). Remarks on the limiting Gibbs state on a d+1 -tree. Publ. RIMS Kyoto Univ. 13 335-348. · Zbl 0376.60096  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  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  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  Le Cam, L. (1974). Notes on Asymptotic Methods in Statistical Decision Theory. Centre de Rech. Math., Univ. Montréal.  Lyons, R. (1989). The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys. 125 337-352. · Zbl 0679.60101  Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931-958. · Zbl 0714.60089  Lyons, R. (1992). Random walks, capacity, and percolation on trees. Ann. Probab. 20 2043- 2088. · Zbl 0766.60091  Lyons, R. and Peres, Y. (1997). Probability on Trees and Networks. To appear. Available at http://php.indiana.edu/ rdlyons/. URL:  Moore, T. and Snell, J. L. (1979). A branching process showing a phase transition. J. Appl. Probab. 16 252-260. JSTOR: · Zbl 0421.60052  Mossel, E. (1998). Recursive reconstruction on periodic trees. Random Structures Algorithms 13 81-97. · Zbl 0959.05112  Mossel, E. (1999). Reconstruction on trees: beating the second eigenvalue. Unpublished manuscript. · Zbl 1021.90008  Pemantle, R. and Peres, Y. (1994). Domination between trees and application to an explosion problem. Ann. Probab. 22 180-194. · Zbl 0806.60098  Pemantle, R. and Peres, Y. (1995). Recursions on trees and the Ising model at critical temperatures. Unpublished manuscript. · Zbl 0837.60066  Pippenger, N. (1988). Reliable computation by formulas in the presence of noise. IEEE Trans. Inform. Theory 34 194-197. · Zbl 0652.94022  Preston, C. J. (1974). Gibbs States on Countable Sets. Cambridge Univ. Press. · Zbl 0297.60054  Spitzer, F. (1975). Markov random fields on an infinite tree. Ann Probab. 3 387-394. · Zbl 0313.60072  Steel, M. (1989). Distribution in bicolored evolutionary trees. Ph.D. thesis, Massey Univ., Palmerston North, New Zealand.  Steel, M. and Charleston, M. (1995). Five surprising properties of parsimoniously colored trees. Bull. Math. Biology 57 367-375. · Zbl 0822.92013  Vajda, I. (1989). Theory of Statistical Inference and Information. Kluwer, Dordrecht. · Zbl 0711.62002  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.  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.