# 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
• Here is a related problem. Choose $r$ $n\times n$ permutation matrices uniformly at random and add them. This gives a probability distribution on $n\times n$ nonnegative integer matrices with line sum $r$. What does this distribution look like as $r,n\to\infty$? – Richard Stanley Jul 31 '19 at 1:27

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

• 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
• "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

There is a polynomial time algorithm based on random walks to approximately sample from any $$n$$-dimensional convex body which also applies to the Birkhoff polytope. This is an algorithm by Dyer, Frieze, and Kannan: A random polynomial time algorithm for approximating the volume of convex bodies. 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)

Maybe not completely uniformly random, but recently we have proposed an algorithm to sample from the Birkhoff Polytope using a Riemannian-MCMC algorithm, specifically by simulating the Langevin dynamics on the manifold using first order retraction maps. Thought it would be related to share it here:

Birdal, Tolga, and Umut Simsekli. "Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019. https://arxiv.org/abs/1904.05814