Dimension-Free Noninteractive Simulation from Gaussian Sources

MaRDI QIDQ6391521zbMATH OpenFDO

Authors Steven Heilman, Alex Tarter

Publication date 18 February 2022

Abstract: Let $X$ and $Y$ be two real-valued random variables. Let $(X_1,Y_1),(X_2,Y_2),ldots$ be independent identically distributed copies of $(X,Y)$. Suppose there are two players A and B. Player A has access to $X_1,X_2,ldots$ and player B has access to $Y_1,Y_2,ldots$. Without communication, what joint probability distributions can players A and B jointly simulate? That is, if $k,m$ are fixed positive integers, what probability distributions on ${1,ldots,m}^2$ are equal to the distribution of $(f(X_1,ldots,X_k),,g(Y_1,ldots,Y_k))$ for some $f,gcolonmathbb{R}^{k}o1,ldots,m$? When $X$ and $Y$ are standard Gaussians with fixed correlation $hoin(-1,1)$, we show that the set of probability distributions that can be noninteractively simulated from $k$ Gaussian samples is the same for any $kgeq{m}^2$. Previously, it was not even known if this number of samples $m^2$ would be finite or not, except when $mleq2$. Consequently, a straightforward brute-force search deciding whether or not a probability distribution on ${1,ldots,m}^2$ is within distance $0<epsilon<|ho|$ of being noninteractively simulated from $k$ correlated Gaussian samples has run time bounded by $(5/epsilon{)}^{m(log(epsilon/2)/log|ho|{)}^{m^2}}$, improving a bound of Ghazi, Kamath and Raghavendra. A nonlinear central limit theorem (i.e. invariance principle) of Mossel then generalizes this result to decide whether or not a probability distribution on ${1,ldots,m}^2$ is within distance $0<epsilon<|ho|$ of being noninteractively simulated from $k$ samples of a given finite discrete distribution $(X,Y)$ in run time that does not depend on $k$, with constants that again improve a bound of Ghazi, Kamath and Raghavendra.

This page was built for publication: Dimension-Free Noninteractive Simulation from Gaussian Sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6391521)