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?

$\begingroup$ What does i.i.d stand for? independently somethingsomething? $\endgroup$ – sleepless in beantown Nov 16 '10 at 3:56

$\begingroup$ I changed the tag since independenceresults refers to a different concept of independence. $\endgroup$ – Gjergji Zaimi Nov 16 '10 at 4:00

1$\begingroup$ See Devroye  NonUniform Random Variate Generation. $\endgroup$ – zhoraster Nov 16 '10 at 5:53

1$\begingroup$ I think the question is: we have $k$ i.i.d. standard Gaussian random variables ($X_i$) and using them we want to generate more than $k$ pairwise independent standard Gaussian random variables ($Y_i$) (and we want to do it an efficient way). Cross posted on cstheory.SE: cstheory.stackexchange.com/questions/3034/… $\endgroup$ – Kaveh Nov 16 '10 at 6:49

1$\begingroup$ @Kevin: $m = \omega(k)$ in this context means that $m$ must grow faster than $k$, so $m = \sqrt{k}$ would not be fine. $m = 0.0001 k \log k$ would be fine. $\endgroup$ – András Salamon Nov 16 '10 at 18:05
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(n1)/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 squareintegrable 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.

$\begingroup$ It is not clear if the transformations from normal to uniform and vice versa are considered efficient in our context (maybe the OP should decide). Anyway, I will give an elaborated answer for the uniform case, probably within a day. $\endgroup$ – Shai Covo Nov 17 '10 at 7:32

$\begingroup$ The method used in this paper is well known (see for example my answer: mathoverflow.net/questions/7998/…). Furthermore, you can easily get $2^m1$ pairwise independent rv's. In fact, I am not sure what the novelty of this paper is (but I only skimmed it). $\endgroup$ – Ori GurelGurevich Nov 17 '10 at 18:36

$\begingroup$ In my opinion, that previous thread on MO only suggests that the above solution is not well known; indeed, in our setting it is essential that the rv's be continuous. $\endgroup$ – Shai Covo Nov 18 '10 at 21:05
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.