Inference for Recursive Trees

• Activity Number: 602 - Theory at the Intersection of Machine Learning and Statistics
• Type: Invited
• Date/Time: Thursday, August 2, 2018 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Nicolas Fraiman* and Shankar Bhamidi and Andrew B Nobel and Ruituo Fan
• Companies: University of North Carolina at Chapel Hill and University of North Carolina at Chapel Hill and University of North Carolina at Chapel Hill and University of North Carolina at Chapel Hill
• Keywords: recursive tree; reconstruction; partial information; discrete structure; combinatorial statistics

Abstract

Recursive trees occur frequently in analysis of algorithms, in network evolution, and in biological phylogenetics. In this talk we discuss inference problems where we observe a realization of the tree but some information is missing. This setup of partial information is common in Combinatorial Statistics.

Consider a dynamically growing tree with parameter q in [0,1] where vertices arrive one by one, and each vertex is either blue or red with probability 1/2. Start with a red and a blue vertex joined by an edge. Each new vertex attaches to a uniform vertex of its own color with probability q, and to a random vertex of a different color with probability 1-q.

Suppose that we observe a tree generated by this process where the colors have been removed. We propose methods for testing and estimation of the parameter q. Moreover, we also discuss reconstructing the missing information, that is, recovering the color of the vertices.