Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems
Abstract Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste (Ann Appl Probab 6(3):695–750, 1996) computed the maximum ratio between the relative entropy and the Dirichlet form, obtaining the constant...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152926 |
| Summary: | Abstract
Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste (Ann Appl Probab 6(3):695–750, 1996) computed the maximum ratio between the relative entropy and the Dirichlet form, obtaining the constant
$$\alpha _2$$
α
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\ge 1$$
p
≥
1
). As an example, we show
$$\alpha _1 = 1+\frac{1+o(1)}{\log q}$$
α
1
=
1
+
1
+
o
(
1
)
log
q
. Furthermore, p-NLSIs allow us to conclude that for
$$q\ge 3$$
q
≥
3
, distributions that are not a product of identical distributions can have slower speed of convergence to equilibrium, unlike the case
$$q=2$$
q
=
2
. By integrating the 1-NLSI we obtain new strong data processing inequalities (SDPI), which in turn allows us to improve results of Mossel and Peres (Ann Appl Probab 13(3):817–844, 2003) on reconstruction thresholds for Potts models on trees. A special case is the problem of reconstructing color of the root of a q-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
$$\begin{aligned} \frac{\log q}{\log q - \log (q-1)} = (1-o(1))q\log q. \end{aligned}$$
log
q
log
q
-
log
(
q
-
1
)
=
(
1
-
o
(
1
)
)
q
log
q
.
This recovers previous results (of Sly in Commun Math Phys 288(3):943–961, 2009 and Bhatnagar et al. in SIAM J Discrete Math 25(2):809–826, 2011) in (slightly) more generality, but more importantly avoids the need for any coloring-specific arguments. Similarly, we improve the state-of-the-art on the weak recovery threshold for the stochastic block model with q balanced groups, for all
$$q\ge 3$$
q
≥
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. (Combin Probab Comput 31(6):1048–1069, 2022). These improvements advocate information-theoretic methods as a useful complement to the conventional techniques originating from the statistical physics. |
|---|