Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that $Y_i$'s are pairwise independent gaussians with mean $0$ and variance $1$.

share|cite|improve this question
@Suresh, $E[(X_i+X_j)(X_i+X_k)] = E[X_i^2] = 1$ so it does not seem to work. – Kaveh Nov 16 '10 at 4:43
I don't know why, but I find the MO answer to this question quite hilarious (apart from the pointer to stats.SE):… – Suresh Venkat Nov 16 '10 at 5:30
What I was looking for was something like taking linear combinations (which obviously does not work) or polynomials etc. (which don't work immediately) but I cannot really think of any reasonable notion which Shai's answer on mathoverflow does not meet. – Anindya De Nov 17 '10 at 16:40
maybe you should update the question pointing out the answer on MO ? – Suresh Venkat Nov 24 '10 at 7:37
Do you need a jointly Gaussian distribution? If so, what you need seems to be impossible since such a distribution is determined by its covariance matrix and thus, pairwise independence and full independence would be the same. – MCH Jan 4 '12 at 23:48

The posting on MathOverflow tells how to go from a small number of independent Uniform[0,1] random variables to a larger number of pairwise-independent Uniform[0,1] random variables. You can of course go back and forth between Uniform[0,1] and Gaussian by inverting the CDF. But that requires numerical analysis as the CDF is not closed-form.

However, there is a simpler way to from Gaussian to uniform. Given two independent Gaussians $X_1, X_2$, the angle $\arctan(X_1/X_2)$ is uniform in the range $[0,2 \pi]$.

Similarly, the Box-Muller method transforms two independent Uniform[0,1] variables into two independent Gaussian random variables.

Using these two transformations, you consume two Gaussians to produce a uniform or two uniforms to produce a Gaussian. So there is only a factor of $O(1)$ in the sampling efficiency. Furthermore, no inversion of the Normal cdf is required.

share|cite|improve this answer

This construction does NOT give pairwise independent variables (indeed, $|Y_{i,j}| = |Y_{i,j'}|$ below) as asked by Anindya, but it gives pairwise uncorrelated variables which is enough for getting good concentration bounds for the sum through Chebyshev's inequality (and this is many times the end goal).

For each distinct pair $(i,j) \in {[k] \choose 2}$, let $Y_{i,j} = |X_i| \cdot \sigma(X_i X_j)$, where $\sigma(\cdot)$ is the sign function. It's clear that each $Y_{i,j}$ is a normal variable with mean 0 and variance 1. To see that they are orthogonal, for $(i,j) \neq (i',j')$, note that $$\mathbb{E}[Y_{i,j}Y_{i',j'}] = \mathbb{E}[|X_i X_{i'}| \cdot \sigma(X_i X_{i'} X_j X_{j'})]$$ which can be easily checked to equal 0 by looking at the various cases of possible equalities between $i,i',j,j'$.

P.S.: A previous version falsely claimed pairwise independence.

share|cite|improve this answer
I cannot follow why the mean of the product being zero would imply independence. – Tsuyoshi Ito Jan 4 '12 at 11:41
@TsuyoshiIto: Your criticism was correct, of course. I've still left this answer up, as I think it's interesting. – arnab Jan 5 '12 at 5:43
If you want to keep your post, please use necessary precaution to avoid confusing the readers. You may argue that the current version (revision 3) of your post does not state anything incorrect. True, but the question asks something, and your post answers something else without stating so. Please understand that it is extremely confusing to the readers. – Tsuyoshi Ito Jan 5 '12 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.