Date: 2 Apr 1987 04:46:54 EST (Thu)
From: Dan Hoey <hoey@nrl-aic.ARPA>
Subject: Randomness with 4 RV's
To: KFL@ai.ai.mit.edu

Here's the answer for four RV's X0,X1,X2,X3 on {-1,1}, with correlation
coefficients Cij.  Consider the eight quantities

LH1 = C02 + C03 + C12 + C13  }    {  C12 + C13 + C23 + 1 = RH0
LH2 = C01 + C03 + C12 + C23  } <= {  C01 + C02 + C12 + 1 = RH3
LH4 = C01 + C02 + C13 + C23  }    {  C01 + C03 + C13 + 1 = RH5
LH7 = 0                      }    {  C02 + C03 + C23 + 1 = RH6

The <= means that the MAX of the LHi must not exceed the MIN of the RHi.

A set of RV's with the desired correlations can be constructed by
taking a value M between the MAX of the LHi and the MIN of the RHi.
Then choosing X0 equiprobable on {-1, 1}, choose

  X0=-X1=-X2=-X3 with probability (RH0-M)/4
  X0= X1=-X2=-X3 with probability (M-LH1)/4
  X0=-X1= X2=-X3 with probability (M-LH2)/4
  X0= X1= X2=-X3 with probability (RH3-M)/4
  X0=-X1=-X2= X3 with probability (M-LH4)/4
  X0= X1=-X2= X3 with probability (RH5-M)/4
  X0=-X1= X2= X3 with probability (RH6-M)/4
  X0= X1= X2= X3 with probability (M-LH7)/4

I got this result from Macsyma.  Basically, you take the six equations
defining the correlations in terms of the probabilities, and the
equation that says the probabilities sum to 1.  That's seven equations,
you solve for seven of the probabilities.  The eighth probability, M/4,
shows up in all 7 solutions, and you isolate that probability.  The
inequalities arise from assuming that all the probabilities are
nonnegative.

Any problem of this form could be cast as a linear programming problem
using this method.  The equations state the correlation coefficients in
terms of the probabilites, and that the probabilities sum to 1.  The
inequalities state that the probabilites are nonnegative.  Put it in
your favorite LP solver and you get the probabilities, if any.

Unfortunately, this still only answers the question for discrete random
variables.