Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
add comment

3 Answers

up vote 7 down vote accepted

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.)

Added in the light of the comment below: OK, I should have checked. It's actually not the inner product but π minus twice the angle between the two vectors all over π. I.e., it depends linearly on the angle between the two vectors, is 1 when that angle is zero and -1 when it is π. The angle is the inverse cos of the inner product, which gives us a formula.

So it gives us a fairly big supply of matrices -- I can't quite decide whether it gives us all (or rather all for which the variables take two values, each with probability 1/2).

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$.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

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

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