Dimension-Free Noninteractive Simulation From Gaussian Sources

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 ,..., Xk ), g ( Y 1 ,..., Yk )) for some f , g : R 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² , 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.