# Constructing Bernoulli random variables with prescribed correlation

For which $n \times n$ correlation matrix $C$ can one construct Bernoulli random variables $(B_1, \ldots, B_n)$ with correlation $C$ ?

Following the approach described in this MO thread, one can think of the following construction. Define independent Bernoulli random variables $B_{k_1, \ldots, k_n}$ for $(k_1, \ldots, k_n) \in \mathbb{Z}^n$ and another independent $\mathbb{Z}^k$-valued random variable $I=(I_1, \ldots, I_n)$. Then $(B_{I_1}, \ldots, B_{I_n})$ is a correlated Bernoulli vector.

1: Is there any example of correlation structure that cannot be obtained this way ?

2: Any easy example of correlation matrix $C$ that cannot be the correlation matrix of a $\{0,1\}^n$ valued random vector ?

-
Not sure this is important, but I guess your Bernoulli random variables are $\{0,1\}$-valued. Do you want them to have mean 1/2? Also, out of curiosity, why is this community wiki? –  Mark Meckes Mar 26 '10 at 13:29
Oh, you said correlation matrix, not covariance matrix. So it doesn't matter whether you assume $B_i$ are uniform in $\{0,1\}$, or have a more general distribution supported on two values. –  Mark Meckes Mar 26 '10 at 13:33

Here's a pretty general construction. Take unit vectors $v_1,\dots,v_n$ in $\mathbb{R}^n$ and let $u$ be a random unit vector (chosen with the uniform probability measure on the unit sphere). Define $B_i$ to be 1 if the inner product of $u$ and $v_i$ is positive and -1 otherwise. Then the correlation between $B_i$ and $B_j$ is the inner product of $v_i$ and $v_j$. (I haven't checked that carefully but I think it's true.)
A more general-looking construction is this. Take any probability space and let $A_1,...,A_n$ be sets of measure 1/2. Pick a random point x and let $B_i$ be 1 if x is in $A_i$ and -1 otherwise. But that becomes trivial, because if you have any set of Bernoulli variables taking the values $\pm 1$ with probability 1/2, then you can set $A_i$ to be the set where $B_i=1$.
you mean that if a Gaussian vector $G = (\xi_1, \ldots, \xi_n)$ has correlation matrix C then the Bernoulli vector $B = (sgn(\xi_1), \ldots, sgn(\xi_n))$ also has C$as correlation matrix ? It does not seem to be true. – Alekk Mar 26 '10 at 16:22 This is de Finetti's construction right? Or what is called his "angle theorem". Google brought up this article www.emis.de/journals/JEHPS/Decembre2008/Lawrence.pdf – Gjergji Zaimi Apr 7 '10 at 6:08 thanks for the reference: this paper is pretty much what I was looking for. – Alekk Apr 7 '10 at 9:04 Re 1: Not quite sure that I understand your construction but apparently it can never yield negative correlations? Re 2: Consider the matrix$C_3=\pmatrix{1&-1/2&-1/2\cr -1/2&1&-1/2\cr -1/2&-1/2&1}$. This is a legitimate correlation matrix (for instance of the Gaussian vector$(N,-N/2+N'\sqrt3/2,-N/2-N'\sqrt3/2)$with$(N,N')$i.i.d. and Gaussian) but neither$C_3$nor any matrix whose$C_3$is a submatrix are correlation matrices of Bernoulli vectors. To see this, assume that$C_3$is the correlation matrix of a random vector$X=(X_1,X_2,X_3)$with values in$\{0,1\}^3$and for every$i$let$x_i^2=E(X_i)=E(X_i^2)$. Then$X_1/x_1+X_2/x_2+X_3/x_3$is almost surely constant because the sum of the coefficients of$C_3$is$0$. Hence$X_1/x_1+X_2/x_2$takes exactly two values. For non degenerate$\{0,1\}$valued random variables$X_1$and$X_2$, this means that$x_1=x_2$. Likewise,$x_1=x_3$, hence$S=X_1+X_2+X_3$is almost surely constant. Now$S=0$or$S=3$means that$X=(0,0,0)$or that$X=(1,1,1)$, respectively, hence these cases are excluded. By the symmetry$X_i\to1-X_i$, one can assume that$S=1$almost surely. This means that$X$is concentrated on the three points$(1,0,0)$,$(0,1,0)$and$(0,0,1)$and, furthermore (recalling the relations$x_1=x_2=x_3$), that$X$is uniformly distributed on these three points. Thus the correlation of$X_1$and$X_2$is$-1/3$and not$-1/2$as it should be. Edit: I guess the same reasoning excludes every$n\times n$matrix$C_n$with diagonal entries$1$and off-diagonal entries$-1/(n-1)$, for$n\ge3$. By the way, one sees that$C_3$cannot be obtained through Gaussian random variables and hyperplanes as in Gowers' answer because, if it was, it would be produced by the$3\times3$matrix with diagonal entries$\sin(1\cdot\pi/2)=1$and off-diagonal entries$\sin((-1/2)\cdot\pi/2)=-1/\sqrt2$, which is not definite positive. (The same applies to$C_n$for every$n\ge3$.) Correlation matrices$C=(C_{i,j})$of Bernoulli random vectors might be exactly those such that the matrix$(\sin(C_{i,j}\pi/2))$is definite positive, in which case the Gaussian-cut-by-hyperplanes construction would yield them all. - I have a question about Didier Piau's answer: Why does it follow that "the correlation of$X_1$and$X_2$is$−1/3$and not$−1/2$as it should be"? Perhaps I misunderstood the setting, but if$X$is uniformly distributed over the points$(1,0,0)$,$(0, 1, 0)$and$(0,0,1)$, then$E(X_i) = 1/3$,$E(X_iX_j)=0$, and hence$Var(X_i) = 2/9$and$Cov(X_iX_j) = -1/9$. Therefore, the correlation between$X_i$and$X_j$is$(-1/9)/(2/9) = -1/2$, as it should be. In fact I think that, in this setting, the correlation matrix of$X_1, X_2, X_3$is exactly the matrix$C_3$. - Here's a generalization of gowers's construction that is practical for Bernoulli RVs with$p\ne1/2$. You want to generate$n$Bernoulli RVs, each taking on value 0 or 1, each with mean$p<1/2$. (For$p>1/2$, do as described below for$1-p$, then complement the results.) Let$d=\sqrt{2}\text{ erfc}^{-1}\left(2p\right)$. (This is just the inverse survival function for the standard normal distribution.) Take unit vectors$v_1,...v_n$as before. Generate a random$n$-vector$z$whose components are IID standard normal RVs. Let$B_i=1$iff$z\cdot v_i>d$.$z\cdot v_i$is standard normal, so obviously gives the desired mean of$p$. What about correlations? As in gowers's construction, these depend uniquely on the angle between vectors$v_i$and$v_j$. Let$c_{ij}$be the coincidence frequency between$B_i$and$B_j$, i.e., the frequency with which both are 1, which is related to the correlation. If$\theta_{ij}=\cos^{-1}\left(v_i\cdot v_j\right)$, then $$c_{ij}=\int_d^\infty \Phi\left(\frac{u\cos\theta_{ij}-d}{\sin\theta_{ij}}\right)\phi\left(u\right)du$$ where$\Phi(z)$and$\phi(z)$are the standard normal CDF and PDF, respectively.$c$decreases monotonically from$p$at$\theta=0$to 0 at$\theta=\pi$. In a practical problem you'd probably want the inverse: you'd know$p$and$c$and want to get$\theta$. I doubt that can be done other than numerically, but$c$is a single function of two bounded variables$p$and$\theta$, so you can tabulate it numerically once and invert the interpolated function if you're going to be doing a lot of this. Now you know what all dot products$v_i\cdot v_j=\cos{\theta_{ij}}$need to be, it is simple to construct vectors at these angles. Let$v_1=\left(1,0,...,0\right)$. Then$v_2=\left(\cos\theta_{12},\sin\theta_{12},0,...,0\right)$. For$v_3$, solve $$\pmatrix{v_{11}&v_{12}\cr v_{21}&v_{22}}\pmatrix{v_{31}\cr v_{32}}=\pmatrix{1&0\cr \cos\theta_{12}&\sin\theta_{12}}\pmatrix{v_{31}\cr v_{32}}=\pmatrix{\cos\theta_{13}\cr\cos\theta_{23}}$$ ... then let$v_{33}=\sqrt{1-v_{31}^2-v_{32}^2}$. Continue to generate the rest of the$v_i$. Since the matrix at every stage is lower triangular, the solution is unique as long as the diagonal is positive. The construction fails only if the norm of the first$i-1$components of$v_i$is$\ge1$. I'm going to speculate that that occurs only if you give it a set of impossible coincidence frequencies (for instance,$c_{12}=c_{13}=p$,$c_{23}=0$), but I haven't attempted to show that. Edit: Nope, I was too optimistic. For instance, if you have three mutually exclusive Bernoulli RVs with$p\le1/3\$, which is clearly possible, this construction fails. Alas.