# Sampling from the Birkhoff polytope

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).

• 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

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).