Estimating the history of a random recursive tree

arXiv:2403.09755v1 Announce Type: cross
Abstract: This paper studies the problem of estimating the order of arrival of the vertices in a random recursive tree. Specifically, we study two fundamental models: the uniform attachment model and the linear preferential attachment model. We propose an order estimator based on the Jordan centrality measure and define a family of risk measures to quantify the quality of the ordering procedure. Moreover, we establish a minimax lower bound for this problem, and prove that the …

abstract arxiv cs.lg cs.si estimator history linear paper random recursive stat.ml studies study tree type uniform