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$.
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
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. |
|||
|
|
|
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. |
|||||||||
|
