MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we are given a probability distribution over a finite discrete product space $p(x,y)$ with marginals $p(x), p(y) > 0$ for each $x,y$ respectively. We are given two more marginal distributions $r(x), r(y)>0,$ for each $x,y$ respectively. Can we always find functions $f(x), g(y)$ such that

$\sum_y p(x,y)f(x)g(y) = r(x)$

$\sum_x p(x,y)f(x)g(y) = r(y)$?

It appears that we should always be able to do this, but I would like an explicit expression for a solution $f,g$ in terms of $r(x), r(y).$ Thanks.

share|cite|improve this question
up vote 2 down vote accepted

This is called the generalized matrix scaling problem and several other names. Both the theory and associated algorithmic problems have been studied. I suggest you start with this paper and the papers it cites.

share|cite|improve this answer

There are some notational issues. The two different marginals and the joint distribution for X and Y need to be distinguished by different choice of symbols. My suggestions are: $p(x,y), p_X(x), p_Y(y)$, and similarly $r_X(x), r_Y(y)$. Now your question is existence of $f(x), g(y)$ such that $\sum_y p(x,y) p_X(x) g(y) = r_X(x),$ and similarly the other one. As the LHS is a summation over $y$, it must be a function purely one $x$.

Now using your hypothesis that you are in finite discrete space the existence of $f(x), g(y)$ can be interpreted as a question of existence of solutions to two linear system of equations.

share|cite|improve this answer
The question appears to generalize the problem of scaling the rows and columns of a nonnegative matrix in order to make the matrix doubly-stochastic. That can always be done under some weak conditions, but it certainly cannot be done by solving linear equations. It is much harder than that. – Brendan McKay Jul 27 '13 at 1:00
Looks like I have not given the problem much thought. – P Vanchinathan Jul 28 '13 at 5:07

Your Answer


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.