论文标题
稀疏种植匹配问题中的恢复阈值
Recovery thresholds in the sparse planted matching problem
论文作者
论文摘要
我们考虑通过利用通过使用两个不同的分布来用于内部和外部匹配的边缘上的权重来引起的信息，从而恢复隐藏在加权随机图中的未知完美匹配的统计推断问题。最近的一项工作表明，在完全连接图上的特定形式的权重分布的特定形式的完整恢复阶段之间存在相变的存在。我们将此结果概括并扩展到两个方向：我们获得了通用权重分布和可能稀疏图的相位转换位置的标准，从而利用了分支随机步行过程的技术连接，以及对围绕相变的关键方案的定量更精确描述。
We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.
