How to sample pairwise independent gaussians - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T14:38:39Z http://mathoverflow.net/feeds/question/46180 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46180/how-to-sample-pairwise-independent-gaussians How to sample pairwise independent gaussians Anindya De 2010-11-16T03:45:29Z 2010-11-17T12:37:43Z <p>If $X_1, \ldots , X_k$ are i.i.d normal random variables with mean $0$ and variance $1$, then is there a way to sample $Y_1, \ldots , Y_m$ for $m=\omega(k)$ such that each of the $Y_i$'s is a normal random variable with mean $0$ and variance $1$ and they are pairwise independent?</p> http://mathoverflow.net/questions/46180/how-to-sample-pairwise-independent-gaussians/46188#46188 Answer by Nate Eldredge for How to sample pairwise independent gaussians Nate Eldredge 2010-11-16T04:51:49Z 2010-11-16T04:51:49Z <p>I'm not sure what you mean by "is there a way to sample". But the following fact may be of interest:</p> <blockquote> <p><b>Proposition.</b> Let $F_1, F_2, \dots$ be any sequence of distributions (possibly infinite), and let $X$ be a single random variable with any continuous distribution. There exist measurable functions $g_n$ such that $g_n(X)$ are independent random variables with corresponding distributions $F_n$.</p> </blockquote> <p>Sketch: Let $F$ be the cdf of $X$; then $F(X)$ is uniformly distributed on (0,1). So its bits are iid Bernoulli. By picking apart and reassembling these bits you can get an iid sequence $U_n$ of uniform (0,1) random variables. Now apply the inverses of $F_n$ to the $U_n$.</p> <p>If you're looking for a practical algorithm, then you should probably be on <a href="http://stats.stackexchange.com" rel="nofollow">http://stats.stackexchange.com</a>.</p> http://mathoverflow.net/questions/46180/how-to-sample-pairwise-independent-gaussians/46264#46264 Answer by Shai Covo for How to sample pairwise independent gaussians Shai Covo 2010-11-16T17:17:36Z 2010-11-17T12:37:43Z <p>Here is the answer I promised in my last comment.</p> <p>Instead of considering ${\rm N}(0,1)$ variables, we may consider uniform$[0,1)$ variables. Indeed, if $Z_i$ are i.i.d. ${\rm N}(0,1)$ variables, then, with $\Phi(\cdot)$ denoting the ${\rm N}(0,1)$ distribution function, $U_i := \Phi (Z_i)$ are i.i.d. uniform$[0,1)$ variables. In turn, if $\tilde U_i$ are pairwise independent uniform$[0,1)$ variables, then $\tilde Z_i := \Phi^{-1} (\tilde U_i)$ are pairwise independent ${\rm N}(0,1)$ variables.</p> <p>The rest of this answer is based on the recent paper "Recycling physical random numbers", available at <a href="http://projecteuclid.org/euclid.ejs/1262617417" rel="nofollow">1</a> or <a href="http://www-stat.stanford.edu/~owen/reports/recycle.pdf" rel="nofollow">2</a>. Henceforth, we use the same letters as in that paper. Suppose that $U_1,\ldots,U_n$ are independent uniform$[0,1)$ variables. Fix $2 \leq m \leq n$, and define $N_m = {n \choose m}$. Now let $X_i$, for $i = 1,\ldots,N_m$, comprise all $N_m$ distinct sums of the form $U_{r_1 } \oplus U_{r_2 } \oplus \cdots \oplus U_{r_m }$, for $1 \le r_1 &lt; r_2 &lt; \cdots &lt; r_m \le n$. Here $U_{r_1 } \oplus U_{r_2 } \oplus \cdots \oplus U_{r_m }$ is the sum modulo $1$ of the $U_{r_i}$, given explicitly by $$U_{r_1 } \oplus U_{r_2 } \oplus \cdots \oplus U_{r_m } = U_{r_1 } + U_{r_2 } + \cdots + U_{r_m } - \left\lfloor {U_{r_1 } + U_{r_2 } + \cdots + U_{r_m } } \right\rfloor ,$$ where $\left\lfloor \cdot \right\rfloor$ is the floor function. Then, the $X_i$ are pairwise independent uniform$[0,1)$ variables. In particular, by letting $m=2$, we can efficiently construct $n(n-1)/2$ pairwise independent uniform variables from $n$ independent ones.</p> <p>Finally, for general purposes it might be worth stating the following simple fact (Proposition 2 in the aforementioned paper). For $N \geq 2$, let $Y_1,\ldots,Y_N$ be pairwise independent random variables with common mean $\mu$ and common variance $\sigma^2 &lt; \infty$. Define $\bar Y = \frac{1}{N}\sum\nolimits_{i = 1}^N {Y_i }$ and $s^2 = \frac{1}{{N - 1}}\sum\nolimits_{i = 1}^N {(Y_i - \bar Y)^2 }$. Then, ${\rm E}(\bar Y) = \mu$, ${\rm Var}(\bar Y) = \sigma^2/N$, and ${\rm E}(s^2) = \sigma^2$. Combined with the previous paragraph, a straightforward implication is that for a square-integrable function $f$ defined on $[0,1)$, we can approximate the integral $\mu = \int_{[0,1)} {f(x)\,{\rm d}x}$ using a modest number $n$ of independent random inputs. Indeed, note that $n$ independent random inputs can be used to get unbiased Monte Carlo estimates for $\mu$ with the same variance as with $N_m = {n \choose m}$ independent random inputs.</p>