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 something-something? $\endgroup$ – sleepless in beantown Nov 16 '10 at 3:56
  • $\begingroup$ I changed the tag since independence-results refers to a different concept of independence. $\endgroup$ – Gjergji Zaimi Nov 16 '10 at 4:00
  • 1
    $\begingroup$ See Devroye - Non-Uniform 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(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.

  • $\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^m-1$ pairwise independent rv's. In fact, I am not sure what the novelty of this paper is (but I only skimmed it). $\endgroup$ – Ori Gurel-Gurevich 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.