论文标题
Potts半群的非线性日志贝伯夫不平等和重建问题的应用
Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
论文作者
论文摘要
考虑在完整的图表上随机步行的半群，我们称之为Potts Semigroup。 DiaConis和Saloff-Coste计算了相对熵的比率和Dirichlet表单的最大值，在$ 2 $ -LOG-SOBOLOLEV不平等中获得常数$α_2$（$ 2 $ -LSI）。在本文中，我们获得了有关熵的最佳非线性不平等现象（即$ p $ -nlsi，$ p \ ge1 $）。例如，我们显示$α_1= 1+ \ frac {1+o（1）} {\ log k} $。 通过整合$ 1 $ -NLSI，我们获得了新的强数据处理不平等（SDPI），这又使我们能够改善树木上Potts模型的重建阈值的Mossel和Peres的结果。一个特殊情况是，考虑到所有叶子的颜色的知识，重建$ k $颜料的根的颜色的问题。我们表明，要有一个非平凡的重建概率，这棵树的分支数至少应为$$ \ frac {\ log k} {\ log k- \ log log（k-1）} =（1- o（1-o（1- o（1）k \ logk。$ $着色专题论点。同样，我们以$ k $平衡的组（所有$ k \ ge 3 $）的随机块模型的弱恢复阈值提高了最新的恢复阈值。为了进一步显示我们方法的功能，我们证明了使用高斯内核在树模型上广播的最佳非重建结果，闭合了Eldan等人的距离。这些改进主张信息理论方法是源自统计物理学的常规技术的有用补充。
Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste computed the maximum of the ratio of the relative entropy and the Dirichlet form obtaining the constant $α_2$ in the $2$-log-Sobolev inequality ($2$-LSI). In this paper, we obtain the best possible non-linear inequality relating entropy and the Dirichlet form (i.e., $p$-NLSI, $p\ge1$). As an example, we show $α_1 = 1+\frac{1+o(1)}{\log k}$. By integrating the $1$-NLSI we obtain the new strong data processing inequality (SDPI), which in turn allows us to improve results of Mossel and Peres on reconstruction thresholds for Potts models on trees. A special case is the problem of reconstructing color of the root of a $k$-colored tree given knowledge of colors of all the leaves. We show that to have a non-trivial reconstruction probability the branching number of the tree should be at least $$\frac{\log k}{\log k - \log(k-1)} = (1-o(1))k\log k.$$ This recovers previous results (of Sly and Bhatnagar et al.) in (slightly) more generality, but more importantly avoids the need for any coloring-specialized arguments. Similarly, we improve the state-of-the-art on the weak recovery threshold for the stochastic block model with $k$ balanced groups, for all $k\ge 3$. To further show the power of our method, we prove optimal non-reconstruction results for a broadcasting on trees model with Gaussian kernels, closing a gap left open by Eldan et al. These improvements advocate information-theoretic methods as a useful complement to the conventional techniques originating from the statistical physics.
