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

4 Answers 4

up vote 8 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

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

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

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.

share|improve this answer

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.