We have $N$ independent discrete finite random variables (RVs) $X_1,\dots,X_i,\dots,X_N$ where RV $X_i$ has $M_i$ finite number of elements. We are free to choose any distribution $f_i$ for RV $X_i$ $\forall i=\{1,\dots,N\}$. Then consider the product set $Y = X_1\times\dots\times X_i\times\dots\times X_N$ and say we are interested in a particular distribution $f_Y$, which is in the set of all possible distributions on $Y$. Note $f_Y$ is not the product of $f_i$s.

How close can we come to $f_Y$ by manipulating the independent distributions $f_i$ $\forall i=\{1,\dots,N\}$ ? Which I believe (not sure) is same as asking how close is $\prod_i^Nf_i$ to $f_Y$?

There is a set of real numbers $\boldsymbol{a}=\{a(y)\}_{y\in Y}$. The objective is to make the expectation of the set $\boldsymbol{a}$ over $f_i$s as close as possible to the expectation of $\boldsymbol{a}$ over $f_Y$.

I tried writing an optimization problem to minimize $\mid \sum_{y\in Y}[\prod_i^Nf_i(y)-f_Y(y)]a(y)\mid$, but it is non convex. And I am not sure if this is the optimization problem I should solve.

What does it mean to be "close" when we have two distributions?

Note that just expectations being close is not sufficient, the probability $\prod_i^Nf_i(y)$ has to be close to the true probability $f_Y(y)$ $\forall y \in Y$.

The question Distance between the product of marginal distributions and the joint distribution is bit similar but in there marginals come from the joint but in my question no marginals are compared.

Would be very grateful for any clue. Thanks.

PS. Not homework. Part of research work.


(This is discussion rather than answer)

Measures of distribution distance do exist - Kullback-Leibler divergence (or "relative entropy") and Hellinger distance are just two that come immediately to mind. But from what you write, you seek to minimize the distance between two expected values - the "true" expected value, that is taken with respect to the true joint probability mass function $p(Y)$ of non-independent random variables, and some approximation of it, which uses a joint probability mass function $q(Y)$ which assumes independence, something like

$$d = \left|E_p\left[a(Y)\right] - E_q\left[a(Y)\right]\right| = \left|\sum_{S_Y}a(y)p(y) - \sum_{S_Y}a(y)q(y) \right|$$

or square or ..., where the $y$ is an $N$-dimensional vector and sums are to be understood as appropriately multiple.

It may seem that your problem falls into the field of "density estimation", but it doesn't: density estimation methods start with a sample and try to estimate from this sample the density that best describes it. Your problem on the other hand does not include a sample of realizations of the random variables involved. It's an abstract theoretical problem. Perhaps this is why you phrase it in mathematical rather than in statistical terms.

For example you write about "manipulation of the individual densities". This could mean anything, not just the use of a joint distribution of independent variables (=product of individual densities) -it could mean any combination of the individual densities (a weighted sum, whatever), viewed as a mathematical approximation of the true joint distribution -and not as a stochastic estimation (this answer of mine deals to some degree with the differences between the two although in another context).

So it appears that there are two important aspects that perhaps need distinguishing and deciding upon: First, are you after "minimizing distance from true distribution" or "minimizing estimation error of true expected value"? Two, are you going to attempt it in a mathematical approximation framework (where anything goes), or in a statistical framework, where your approximation function should be a proper density?

I hope these comments are useful to you.

ADDENDUM (following discussion with the OP in comments).

it would be interesting to apply a measure of "distribution distance" to the expected value. Assume you are using the Hellinger distance. So, you choose $q(y)$ so that

$$q(y): H(a(y)p(y),a(y)q(y)) = \frac {1}{\sqrt 2} \left(\sum_i\left[\sqrt {a(y_i)p(y_i)}-\sqrt {a(y_i)q(y_i)}\right]^2\right)^\frac 12 =\min$$

$$\Rightarrow \frac {1}{\sqrt 2} \left(\sum_ia(y_i)\left[\sqrt {p(y_i)}-\sqrt {q(y_i)}\right]^2\right)^\frac 12 =\min $$

One should explore the properties of such a measure.

  • $\begingroup$ First of all, thanks a lot. Very helpful. One of these questions are very clear. I am after minimizing estimation error of the true expected value. The answer to second question is not clear because mathematical approximation framework was not in my mind when I formulated this problem. But for now I think I have to go down the path of statistical framework where the approximation function is a proper density. Because in the end I will need each $f_i$ to be a proper densities over each $X_i$. $\endgroup$ – triomphe Oct 18 '13 at 3:16
  • $\begingroup$ It is not just the expectation that matters. Of course the expectation has to be close to the true expectation but the probability distribution of the product of $f_i$s should also be close to the true distribution $f_Y$. I mean the expectation is close as a result of the distributions being close. When I mean distributions close I mean the probability $\prod_if_i(y)$ has to be close to $f_Y(y)$ $\forall i$, i.e, $\prod_if_i(y)$ is in some ball $\epsilon$ around $f_Y(y)$. $\endgroup$ – triomphe Oct 18 '13 at 3:37
  • $\begingroup$ I asked for a metric of distance between distributions because I can't minimize distance of each mass point $\mid f_Y(y)- \prod_if_i(y) \mid $ $y\in Y$ simultaneously. And if I minimize sum difference $\mid \sum_y [f_Y(y)- \prod_if_i(y)] \mid$, that won't be good I think as some points may be very far and others very close. $\endgroup$ – triomphe Oct 18 '13 at 3:39
  • $\begingroup$ From my discussion on comments do you think I should just try to minimize the distance between the two distributions and disregard the expectation? Since if the two distributions are close as it can be then the expectation is too by linearity. Thanks $\endgroup$ – triomphe Oct 18 '13 at 13:22
  • 1
    $\begingroup$ I added an idea. $\endgroup$ – Alecos Papadopoulos Oct 18 '13 at 19:43

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.