Quantitative Correlation Inequalities via Semigroup Interpolation.
A. De and
S. Nadimpalli and
R. Servedio.
12th Innovations in Theoretical Computer Science Conference (ITCS), 2021, pp. 69:1-69:20.
Journal version appeared as
Quantitative Correlation Inequalities via Extremal Power Series.
Probability Theory and Related Fields, 2022, 183, pp, 649-675.
Abstract:
Most correlation inequalities for high-dimensional functions in the
literature, such as the Fortuin-Kasteleyn-Ginibre inequality and the celebrated Gaussian Correlation Inequality of Royen, are
qualitative statements which establish that any two functions of a certain type have non-negative correlation.
In this work we give a general approach that can be used to bootstrap many
qualitative correlation inequalities for functions over product spaces into
quantitative statements. The approach combines a new
extremal result about power series, proved using complex analysis, with
harmonic analysis of functions over product spaces.
We instantiate this general approach in several different concrete settings
to obtain a range of new and near-optimal quantitative correlation
inequalities, including:
A quantitative version of Royen's celebrated Gaussian Correlation
Inequality \cite{roy14}. In \cite{roy14} Royen confirmed a conjecture, open for
40 years,
stating that any two symmetric convex sets must be non-negatively correlated
under any centered
Gaussian distribution. We give a lower bound on the correlation in terms of
the vector of degree-2 Hermite coefficients of the two convex sets,
conceptually similar to Talagrand's
quantitative correlation bound for monotone Boolean functions over $\{0,1\}^n$ \cite{Talagrand:96}. We
show that our quantitative version of Royen's theorem is within a logarithmic
factor of being optimal.
A quantitative version of the well-known FKG inequality for monotone
functions over any finite product
probability space. This is a broad generalization of Talagrand's quantitative correlation bound for functions from $\{0,1\}^n$ to $\{0,1\}$ under the uniform distribution
\cite{Talagrand:96}; the only prior generalization of which we are aware is due
to Keller \cite{Keller12,kell08-prod-measure,Keller09}, which extended
\cite{Talagrand:96} to product distributions over $\{0,1\}^n$. In the special case
of $p$-biased distributions over $\{0,1\}^n$ that was considered by Keller, our new
bound essentially saves a factor of $p \log(1/p)$ over the quantitative bounds
given in \cite{Keller12,kell08-prod-measure,Keller09}. We also give two different quantitative
versions of the FKG inequality for monotone functions over the continuous domain
$[0,1]^n$, answering a question of Keller \cite{Keller09}.
pdf of conference version
pdf of full version on arxiv
journal version
Back to
main papers page