Constructing Bernoulli random variables with prescribed correlation

Question

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 ?

Answer 1

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

Answer 2

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.

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