Inference on the History of a Randomly Growing Tree
Inference on the History of a Randomly Growing Tree
复制标题
随机生长树的历史推断
DOI：
10.1111/rssb.12428
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xu, Min
中科院分区：
文献类型：
--
作者：
Crane, Harry;Xu, Min
传染病在人类社区中的传播或社交媒体上假新闻的扩散可以被建模为一个随机增长的树形图。随机增长过程的历史往往是不可观察的，但包含重要的信息，如感染源。我们考虑的问题，统计推断方面的潜在的历史只使用一个单一的快照的最终树。我们的方法是将随机标签应用于观察到的未标记的树，并分析生长过程的分布，以最终结果为条件。我们证明了这个条件分布在我们引入的形状可交换性条件下是易处理的，并且这个条件对于许多流行的随机生长树模型都是满足的，如均匀连接，线性优先连接和均匀连接在一个D-正则树上。对于根的推理下的形状交换，我们proposeO（nlogn）时间算法构造的置信集与有效的频率覆盖率以及对置信集的预期大小的界限。我们还提供了有效的采样算法，扩展我们的方法广泛的一类推理问题。
The spread of infectious disease in a human community or the proliferation of fake news on social media can be modelled as a randomly growing tree-shaped graph. The history of the random growth process is often unobserved but contains important information such as the source of the infection. We consider the problem of statistical inference on aspects of the latent history using only a single snapshot of the final tree. Our approach is to apply random labels to the observed unlabelled tree and analyse the resulting distribution of the growth process, conditional on the final outcome. We show that this conditional distribution is tractable under ashape exchangeabilitycondition, which we introduce here, and that this condition is satisfied for many popular models for randomly growing trees such as uniform attachment, linear preferential attachment and uniform attachment on aD-regular tree. For inference of the root under shape exchangeability, we proposeO(nlogn) time algorithms for constructing confidence sets with valid frequentist coverage as well as bounds on the expected size of the confidence sets. We also provide efficient sampling algorithms which extend our methods to a wide class of inference problems.