论文标题
高斯来源的无维度非互相模拟
Dimension-Free Noninteractive Simulation from Gaussian Sources
论文作者
论文摘要
令$ x $和$ y $为两个实价的随机变量。令$（x_ {1}，y_ {1}），（x_ {2}，y_ {2}），\ ldots $是$（x，y）$的独立分布副本。假设有两个播放器A和B。玩家A可以访问$ x_ {1}，x_ {2}，\ ldots $，并且玩家B可以访问$ y_ {1}，y_ {2}，\ ldots $。没有沟通，玩家A和B可以共同模拟什么共同的概率分布？也就是说，如果$ k，m $是固定的正整数，那么$ \ {1，\ ldots，m \}^{2} $上的概率分布等于$（f（x_ {1}，\ ldots，x_ {k}），x_ {k}），\ __________________________） $ f，g \ colon \ mathbb {r}^{k} \ to \ {1，\ ldots，m \} $？ 当$ x $和$ y $是具有固定相关性$ρ\ in（-1,1）$的标准高斯人时，我们表明，可以从$ k $高斯样本中非互相模拟的一组概率分布对于任何$ k \ geq m^{2} $都是相同的。以前，甚至还不知道此数量的样本$ m^{2} $是否有限，除非$ m \ leq 2 $。 因此，一个直接的蛮力搜索决定是否在$ \ {1，\ ldots，m \}^{2} $上分布在$ 0 <ε<|ρ| $之内。 \ log |ρ|）^{m^{2}}} $，改善了Ghazi，Kamath和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<ε<|ρ|$ of being noninteractively simulated from $k$ samples of a given finite discrete distribution $(X,Y)$ in run time that does not depend on $k$,随着常数再次改善了加兹，卡马斯和拉格文德拉的界限。
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,g\colon\mathbb{R}^{k}\to\{1,\ldots,m\}$? When $X$ and $Y$ are standard Gaussians with fixed correlation $ρ\in(-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\geq m^{2}$. Previously, it was not even known if this number of samples $m^{2}$ would be finite or not, except when $m\leq 2$. Consequently, a straightforward brute-force search deciding whether or not a probability distribution on $\{1,\ldots,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,\ldots,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.
