Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope

Recently someone asked me if I knew

How to sample (in polynomial time) uniformly at random, from the Birkhoff polytope?

Clearly, modulo a few hacks, I did not have a good answer, so am repeating the above question here (the hacks included trying to exploit that every doubly stochastic matrix is a convex combination of permutation matrices).

share|improve this question
    
I'm have trouble deciding whether I can accept an answer to this question or not, because this has turned out to be an open problem. Does MO have some protocol for such cases? –  Suvrit Aug 27 '11 at 19:56
    
If it's a known open problem, and you get an answer saying so and pointing to the literature on it, accepting the answer seems like a reasonable thing to do. You don't have to and probably shouldn't wait for someone to solve it. –  David Eppstein Aug 27 '11 at 22:30
    
Thanks; I asked because previously I have done the same on MO by pointing out that a problem was open including pointers to the literature, but the answer was never "accepted", so I was not sure what the MO protocol is. However, I agree with your reasoning, so am clicking on accept! –  Suvrit Aug 27 '11 at 23:25
add comment

2 Answers

up vote 14 down vote accepted

This is, to my knowledge, still open. It is connected to the problem of computing the volume of the Birkhoff polytope (or computing the volume of its faces), which is known in closed form only for $n\le 14$. This is also equivalent toThis could be approached by counting non-negative integer matrices with equal row and column sums (because you can read the volume from the leading coefficient of the Ehrhart polynomial, like it is done in the paper The Ehrhart polynomial of the Birkhoff polytope, by Matthias Beck and Dennis Pixton. There are algorithms that sample from distributions that are close to uniform (see the articles below).

The problem is quite old, but there has been a revival of interest recently by several authors. I can point you to a few

share|improve this answer
2  
It would seem that Persi Diaconis might be a good person to ask. –  Gerry Myerson Aug 27 '11 at 0:25
    
Until recently, the maximum determinant among all order n 0-1 matrices was also only known for all n < 14 and for some n greater than 14. Coincidence? Or is there a connection between polytope volume and such determinants that I don't see yet? Gerhard "Ask Me About System Design" Paseman, 2011.08.26 –  Gerhard Paseman Aug 27 '11 at 4:21
1  
"This is also equivalent to counting non-negative integer matrices with equal row and column sums" This does not seem to be quite true. Probably you mean something slightly different. –  Gil Kalai Aug 27 '11 at 7:47
    
Equivalent was too strong, I merely wanted to point out a closely related problem. I am reminded of this slogan mathoverflow.net/questions/36735/… –  Gjergji Zaimi Aug 27 '11 at 8:14
    
Dear Gjergji, The equivalence between sampling and counting/computing volume is fairly ok. But the equivalence between computing volume and computing integer points is problematic... –  Gil Kalai Aug 27 '11 at 9:04
show 4 more comments

There is a polynomial time algorithm based on random walks to approximately samlpe from any n dimensional convex body which also applies to the Bikhoff polytope. This is an alforithm by Dyer Frieze and Kannan A random polynomial time algorithm for approximating the volume of convex sets. Quite a few improvements were found. See e.g. , Blocking Conductance and Mixing in random walks, R. Kannan, L. Lovasz and R. Montenegro, in Combinatorics, Probability and Computing (2005)

share|improve this answer
    
Thanks a lot for these pointers Gil. –  Suvrit Aug 27 '11 at 19:53
add comment

Your Answer

 
discard

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.