How to sample pairwise independent gaussians

2010-11-16T03:45:29Z

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?

Answer by Nate Eldredge for How to sample pairwise independent gaussians

2010-11-16T04:51:49Z

I'm not sure what you mean by "is there a way to sample". But the following fact may be of interest:

Proposition. 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$.

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$.

If you're looking for a practical algorithm, then you should probably be on http://stats.stackexchange.com.

Answer by Shai Covo for How to sample pairwise independent gaussians

2010-11-16T17:17:36Z

Here is the answer I promised in my last comment.

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.

The rest of this answer is based on the recent paper "Recycling physical random numbers", available at 1 or 2. 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 < r_2 < \cdots < 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.

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 < \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.

How to sample pairwise independent gaussians - MathOverflow

How to sample pairwise independent gaussians

Answer by Nate Eldredge for How to sample pairwise independent gaussians

Answer by Shai Covo for How to sample pairwise independent gaussians