Suppose I have a set of random variables ${X_1, X_2, ..., X_n}$. For each of the variables, I have the marginal distribution.

Furthermore, I have the marginal distribution for various sums of subsets of these variables, such as: $X_1+X_2$, $X_1+X_3$, $X_2+X_4+X_7$, etc.

If the variables are independent, the marginal distribution of the sums can be computed from that. If not, it will differ.

My question is: suppose I have an incomplete specification of these marginals, and marginals of sums.

How can I compute a reasonable approximation of the joint distribution from this information, ideally the max-ent distribution consistent with the marginal specification?

I am particularly interested in the discrete, finite case - particularly when each random variable is ${0,1}$-valued (and you can view addition as mod $2$).


1 Answer 1


Consider the specific case of random variables $X\sim$ Bernoulli$\left(p\right)$, $Y\sim$ Bernoulli$\left(q\right)$ and $X\oplus Y= X+Y \bmod 2$ being a Bernoulli$\left(r\right)$ random variable. Then, with $p_{ij}$ denoting $P\{X=i,Y=j\} = p_{X,Y}(i,j)$, we have that \begin{align} p_{11} + p_{10} &= p\\ p_{11} + p_{01} &= q\\ p_{10} + p_{01} &= r \end{align} from which we can deduce that \begin{alignat}{3} p_{00} &= 1 - (p_{11} + p_{10} +p_{01}) &&= 1 - \frac{p+q+r}{2}\\ p_{01} &= (1-p) - p_{00} = (1-p) - \left(1 - \frac{p+q+r}{2}\right)&&= \frac{q+r-p}{2}\\ p_{10} &= (1-q) - p_{00} = (1-q) - \left(1 - \frac{p+q+r}{2}\right) &&= \frac{p+r-q}{2}\\ p_{11} &= p - p_{10} = p - \frac{p+r-q}{2} &&=\frac{p-r+q}{2}\end{alignat} It is, of course, to be hoped that the given value of $r$ is consistent with the known values of $p$ and $q$ and that none of the joint mass function values calculated above turn out to be outside $[0,1]$.

The joint pmf of $m > 2$ Bernoulli random variables cannot be computed from knowledge of the parameters of a subset of the $2^m-1$ Bernoulli random variables $\displaystyle \sum_i a_iX_i \bmod 2, a_i \in \{0,1\}$. For example, suppose that it is given that $X,Y,Z$ all are Bernoulli$\left(\frac 12\right)$ random variables, and so $X\oplus Y, X\oplus Z, Y\oplus Z$ all are Bernoulli$\left(\frac 12\right)$ random variables. (Note the absence of $X\oplus Y \oplus Z$ from the list). Then, it is easily verified via calculations such as the ones above that $X,Y,Z$ are pairwise independent random variables. But,

  • If $X,Y,Z$ are mutually independent random variables, then $p_{111} = \frac 18$.

  • If $p_{000} = p_{110} = p_{101} = p_{011} = \frac 14$, then $p_{111} = 0$.

  • If $p_{100} = p_{010} = p_{001} = p_{111} = \frac 14$, then $p_{111} = \frac 14$.

In fact, for any given value $r \in [0,\frac 14]$ that $p_{111}$ might take on, $p_{110} = p_{101} = p_{011} = \frac 14 -r$ from which we get that $p_{100} + p_{101} = \frac 14 \implies p_{100} = r$ (and similarly $p_{010}$ and $p_{001}$ also have value $r$ too) and finally that $p_{000} = \frac 14 - r$. In short, the best bound that we can have for the $8$ pmf values $p_{ijk}$ is that they all are in $[0,\frac 14]$.

The reason for needing the parameters of all $2^m-1$ Bernoulli random variables $\displaystyle \sum_i a_iX_i \bmod 2, a_i \in \{0,1\}$ is easy to comprehend. Each such parameter gives us a linear equation involving $2^m-1$ joint pmf values ($p_{00\cdots 0}$ is not included anywhere), these equations are linearly independent (in the linear algebra sense of the term), and so all are needed to find the unique solution for the joint pmf. If we don't have all the equations, then we get a parametrized solution as in the example above.

  • $\begingroup$ In a certain sense, for N Bernoulli random variables, you can think of this as the DFT of the joint distribution -- except where each marginal is specified as a number in $[-0.5, 0.5]$, representing the divergence from a fair coin flip. But the question is, suppose you only have a handful of these marginals, rather than the full set. How can you use this to reconstruct a reasonable approximation of the joint distribution? $\endgroup$ Mar 18, 2017 at 17:09
  • $\begingroup$ Many years later: one way to do this is, as I suggested in my question, to look for the maximum entropy distribution that has the required marginal distributions. To do this is not very difficult, and is in fact very easy if we're willing to use the Rényi collision entropy instead of the Shannon entropy, since it turns out that maximizing the Rényi entropy is equivalent to minimizing the L2 norm of the probability vector. $\endgroup$ Apr 11 at 4:10
  • $\begingroup$ Using Dilip's suggestion, we can use this to derive a system of equations which any joint distribution with the required marginals will satisfy, and it turns out that all solutions to this system of equations will be in an affine linear subspace of the space of probability vectors, with the added requirement that all coefficients are positive. Then, because maximizing the Rényi collision entropy is equivalent to minimizing the L2 norm on this set, we have a very easy least squares problem. $\endgroup$ Apr 11 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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