The tightness of the Kesten-Stigum reconstruction bound for a symmetric model with multiple mutations

International Conference on Quantum Mechanics and Applications

July 20-21, 2018 | Atlanta, USA

Wenjian Liu

City University of New York, USA

Posters & Accepted Abstracts: J Laser Opt Photonics

Abstract :

Background: Determining the reconstruction threshold of a broadcast models on d-ary regular tree, as the interdisciplinary subject, has attracted more and more attention from probabilists, statistical physicists, biologists, etc. Does this leaves-configuration contain a non-vanishing information on the letter transmitted by the root, as n goes to infinity? It is believed that the second largest eigenvalue (λ) (in absolute value) of transition matrix is crucial to reconstruction, and the model is always reconstructible when dλ²>1. However, in a small number of models only rigorous reconstruction thresholds have been established. Liu and Ning (2016) have established the critical condition of the asymmetric binary channel to make the Kesten-Stigum bound the reconstruction threshold on regular d-ary trees. Objective: Consider a 2q-state symmetric transition matrix as the noisy communication channel on each edge of a regular d-ary tree. Suppose there are two categories, one of which contains exactly q states, and 3 transition probabilities: the probability to remain in the same state, the probability to mutate to other state but remain in the same category, and the probability to change categories. Consider all the symbols received at the vertices of the nth generation. Does this leaves-configuration contain a non-vanishing information on the letter transmitted by the root, as n goes to infinity? By means of a refined analysis of moment recursion on a weighted version of the magnetization, concentration investigation, and large degree asymptotics, we construct a nonlinear second-order dynamical system based on this model and show that the Kestenâ??Stigum reconstruction bound is not tight when q is greater than 3. On the other side, when q=2, that is, Kimura Model of DNA evolution, the interactions of nodes on tree become weaker as d increases. This allows us to utilize the Gaussian approximation by the Central Limit Theorem. Therefore, we explore stability of the fixed point of Gaussian approximation function in order to verify the tightness of Kesten-Stigum reconstruction bound. Application: The reconstruction problem is concerned essentially with a tradeoff between noise and duplication in a tree communication network; phylogenetic reconstruction is a major task of systematic biology; reconstruction thresholds on trees are believed to determine the dynamic phase transitions in many constraint satisfaction problems including random K-SAT and random colorings on random graphs; the reconstruction threshold is also believed to play an important role in the efficiency of the Glauber dynamics on trees and random graphs.

Biography :

E-mail: wjliu@qcc.cuny.edu