MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 deleted 8 characters in body

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 this1 or this2. 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.
show/hide this revision's text 2 added 2384 characters in body; deleted 2 characters in body

Would

Here is the following fact help you?

If answer I promised in my last comment.

Instead of considering $U_1,\ldots,U_n$ {\rm N}(0,1)$ variables, we may consider uniform$[0,1)$ variables.Indeed, if $Z_i$ are i.i.d. uniform$[0,1)$ ${\rm N}(0,1)$ variables, thenthey can be used to construct , with ${n \Phi(\cdot)$ denoting the ${\rm N}(0,1)$ distribution function, $U_i := \choose k}$ 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 this1 or this2. 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 k 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 simple explicit waystraightforward 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. I Indeed, note that $n$ independent random inputs can elaborate if you wish (including some analysis)be used to get unbiased Monte Carlo estimates for $\mu$ with the same variance as with $N_m = {n \choose m}$ independent random inputs.
show/hide this revision's text 1

Would the following fact help you?

If $U_1,\ldots,U_n$ are i.i.d. uniform$[0,1)$ variables, then they can be used to construct ${n \choose k}$ pairwise independent uniform$[0,1)$ variables, $2 \leq k \leq n$, in a simple explicit way. I can elaborate if you wish (including some analysis).