8
$\begingroup$

Suppose I want to generate a nonnegative $n \times n$ matrix $\mathbf A$ for an odd $n$ (say, $n=5$ for a good enough example), such that

  • the individual elements are drawn from a uniform distribution

but with the equality constraints

  • the sum of all the elements in the rows above the mid row = the sum of all the elements in the rows below the mid row

  • the sum of all the elements in the columns left of the middle column = the sum of all the elements in the columns right of the middle column

  • the sum of all elements = 1.0

That is, in effect I want to generate matrices "balanced" in a specific way (I intend to use them as convolution matrices and I don't care about translation).

For my current purposes I think I have a good enough ad hoc (not entirely correctly distributed) solution that generates a uniform matrix and then enforces the equality constraints by correcting the individual elements using a least squares approach.

However I'm curious, mainly for the learning experience, if there would be some easy-ish way to sample the resulting conditional distribution. So far I've had a quick peek on Wikipedia into the Bates distribution (mean of uniform random variables) and into Monte Carlo Markov Chain models, but I'm not sure if they help here or if there would be an easier solution.

I'm not necessarily looking for a complete solution; pointers to insightful or helpful material are also appreciated.

Edit: I'm looking for the conditional probability distribution, i.e. the elements do not need to be uniformly distributed; rather, I'm looking for a distribution where each sample that satisfies the equality constraints has the same probability (hence conditional uniform distribution given the equalities).

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Your two conditions (1) individual elements uniformly distributed and (2) your equality constraints are mutually incompatible. So, it's not entirely clear what you're aiming for. $\endgroup$
    – cardinal
    Commented Nov 30, 2011 at 17:42
  • 1
    $\begingroup$ The Sinkhorn-Knopp algorithm is somewhat similar in that the goal there is to generate a matrix of nonnegative elements that satisfy individual row and column sum constraints. Quite a lot is known about its convergence properties. $\endgroup$
    – cardinal
    Commented Nov 30, 2011 at 17:43
  • 1
    $\begingroup$ Related: stats.stackexchange.com/questions/17633/… $\endgroup$
    – cardinal
    Commented Nov 30, 2011 at 17:51
  • 1
    $\begingroup$ What I'm thinking about is, if I'm not mistaken about the terminology, sampling the conditional probability distribution of uniformly distributed values conditioned with the given equations hold. Sure, the conditioned distribution is not necessarily uniform, but that's not a problem. Or in even other words, is there an efficient algorithm to replace the following: 1. Generate such a uniformly random matrix 2. If the equations do hold to within a difference of $\epsilon$, return the matrix; else goto 1 What I'm looking for is essentially this with $\lim \epsilon$ -> 0. $\endgroup$
    – Sami Liedes
    Commented Nov 30, 2011 at 20:20
  • 3
    $\begingroup$ Ah, then @Cardinal is (as usual) correct: the marginals will no longer be uniform and you're not requiring that they be so. In fact, they can be far from uniform. (But for medium to large $n$ they ought to be pretty close, because the constraints are so mild.) What you're asking is this: the constraints along with the bounds of the uniform distributions describe a polytope of $n^2-3$ dimensions; you would like to sample this polytope uniformly. $\endgroup$
    – whuber ♦
    Commented Nov 30, 2011 at 23:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.