21
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – Suvrit
    Aug 27, 2011 at 19:56
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2011 at 22:30
  • $\begingroup$ 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! $\endgroup$
    – Suvrit
    Aug 27, 2011 at 23:25
  • 2
    $\begingroup$ 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$? $\endgroup$ Jul 31, 2019 at 1:27

3 Answers 3

17
$\begingroup$

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

$\endgroup$
8
  • 4
    $\begingroup$ It would seem that Persi Diaconis might be a good person to ask. $\endgroup$ Aug 27, 2011 at 0:25
  • $\begingroup$ 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 $\endgroup$ Aug 27, 2011 at 4:21
  • 1
    $\begingroup$ "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. $\endgroup$
    – Gil Kalai
    Aug 27, 2011 at 7:47
  • $\begingroup$ Equivalent was too strong, I merely wanted to point out a closely related problem. I am reminded of this slogan mathoverflow.net/questions/36735/… $\endgroup$ Aug 27, 2011 at 8:14
  • $\begingroup$ 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... $\endgroup$
    – Gil Kalai
    Aug 27, 2011 at 9:04
15
$\begingroup$

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)

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is the method for sampling from the Birkhoff polytope implemented somewhere? I don't quite follow the paper itself. $\endgroup$ Dec 3, 2021 at 0:24
  • $\begingroup$ For further information, the project page is here: synchinvision.github.io/probsync. You could use GeoOpt for implementing Riemannian Langevin/Hamiltonian sampler on the Birkhoff polytope: github.com/geoopt/geoopt. (We have implemented the Birkhoff Polytope there) $\endgroup$ Jan 6, 2022 at 12:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.