Dimension-Free Noninteractive Simulation from Gaussian Sources
share
Let X and Y be two real-valued random variables. Let (X_1,Y_1),(X_2,Y_2),… 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,… and player B has access to Y_1,Y_2,…. 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,…,m}^2 are equal to the distribution of (f(X_1,…,X_k), g(Y_1,…,Y_k)) for some f,gℝ^k→{1,…,m}? When X and Y are standard Gaussians with fixed correlation ρ∈(-1,1), we show that the set of probability distributions that can be noninteractively simulated from k Gaussian samples is the same for any k≥ m^2. Previously, it was not even known if this number of samples m^2 would be finite or not, except when m≤ 2. Consequently, a straightforward brute-force search deciding whether or not a probability distribution on {1,…,m}^2 is within distance 0<ϵ<|ρ| of being noninteractively simulated from k correlated Gaussian samples has run time bounded by (5/ϵ)^m(log(ϵ/2) / log|ρ|)^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,…,m}^2 is within distance 0<ϵ<|ρ| 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.
READ FULL TEXT