Honors Oral Exam

A Study on the Non-Reconstruction Conjecture in Markov Trees

Yurong Liu (University of Rochester)

Friday, April 28th, 2023
12:00 PM - 12:50 PM
Hylan 105

Consider a \(d\)-ary tree \(T\) which simulates the process of broadcasting information from the root to other vertices, where each edge is a copy of an irreducible and aperiodic Markov chain \(M\) with reversible transition matrix \(\mathbb{M} \in \mathbf{R}^{n \times n}\) on state space \(\Omega\), the goal is to reconstruct the value of the root given values of nodes at level \(n\) of the tree, where \(n \rightarrow \infty\). This branching process is useful for modeling complex populations that exhibit dependencies between the states of individuals and their ancestors. It can be used to study a wide range of phenomena, including the spread of diseases in populations, the growth of organisms in ecosystems, and the diffusion of information and ideas. We are going to work on the non-reconstruction conjecture of this problem. The conjecture states that information on root cannot be reconstructed if \(\vert \lambda_2(\mathbb{M}) \vert < \frac{1}{d}\), where \(\lambda_2(\mathbb{M})\) is the second largest eigenvalue of \(\mathbb{M}\). Our focus is on the scenario where \(\mathbb{M}\) is symmetric.

Event contact: jonathan dot pakianathan at rochester dot edu