论文标题
关于随机生长的树的历史的推断
Inference on the History of a Randomly Growing Tree
论文作者
论文摘要
传染病在人类社区中的传播或在社交媒体上的假新闻的扩散可以建模为随机生长的树状图。随机生长过程的历史通常未观察到，但包含重要信息，例如感染的来源。我们仅使用最终树的单个快照来考虑对潜在历史记录方面的统计推断问题。我们的方法是将随机标签应用于观察到的未标记树，并分析生长过程的结果分布，这是根据最终结果的条件。我们表明，这种条件分布在形状 - 交换性条件下是可以解决的，我们在此处介绍，并且对于许多流行的模型，用于随机生长的树木（例如均匀的附件，线性优先附件和$ d $ regratigard-regregular树上的均匀附件）满足了这种情况。为了在形状 - 外观性下推断根，我们提出了用于构建具有有效频繁覆盖范围的置信集的O（n log n）时间算法，以及对置信集的预期大小的界限。我们还提供有效的抽样算法，将我们的方法扩展到广泛的推理问题。
The spread of infectious disease in a human community or the proliferation of fake news on social media can be modeled 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 unlabeled tree and analyze the resulting distribution of the growth process, conditional on the final outcome. We show that this conditional distribution is tractable under a shape-exchangeability condition, 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 a $D$-regular tree. For inference of the root under shape-exchangeability, we propose O(n log n) 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 that extend our methods to a wide class of inference problems.
