most recent 30 from http://mathoverflow.net 2013-05-24T23:49:27Z http://mathoverflow.net/feeds/question/73805 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73805/sampling-from-the-birkhoff-polytope S. Sra 2011-08-26T22:25:38Z 2011-08-27T20:24:11Z

<p>The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known <a href="http://en.wikipedia.org/wiki/Birkhoff_polytope" rel="nofollow"><em>Birkhoff polytope</em></a></p> <p>Recently someone asked me if I knew</p> <blockquote> <p>How to sample (in polynomial time) uniformly at random, from the Birkhoff polytope?</p> </blockquote> <p>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).</p>

http://mathoverflow.net/questions/73805/sampling-from-the-birkhoff-polytope/73811#73811 Gjergji Zaimi 2011-08-27T00:03:33Z 2011-08-27T20:24:11Z

<p>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$. <s>This is also equivalent to</s>This 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 <a href="http://arxiv.org/abs/math/0202267" rel="nofollow">The Ehrhart polynomial of the Birkhoff polytope, by Matthias Beck and Dennis Pixton</a>. There are algorithms that sample from distributions that are close to uniform (see the articles below).</p> <p>The problem is quite old, but there has been a revival of interest recently by several authors. I can point you to a few</p> <ul> <li><a href="http://arxiv.org/abs/0806.3910" rel="nofollow">"What does a random contingency table look like?"</a>, by A. Barvinok</li> <li><a href="http://www-stat.stanford.edu/~cgates/PERSI/papers/TriDiag.pdf" rel="nofollow">"On random, doubly stochastic, tri-diagonal matrices"</a>, by P. Diaconis and P. Matchett Wood </li> <li><a href="http://arxiv.org/abs/1010.6136" rel="nofollow">"Properties of Uniform Doubly Stochastic Matrices"</a> by S. Chatterjee, P. Diaconis, A. Sly</li> <li><a href="http://arxiv.org/abs/1104.0749" rel="nofollow">Gibbs/Metropolis algorithms on a convex polytope</a> by P. Diaconis, G. Lebeau, L. Michel</li> </ul>

http://mathoverflow.net/questions/73805/sampling-from-the-birkhoff-polytope/73825#73825 Gil Kalai 2011-08-27T06:48:04Z 2011-08-27T06:48:04Z

<p>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 href="http://research.microsoft.com/en-us/um/people/kannan/Papers/volume.pdf" rel="nofollow">A random polynomial time algorithm for approximating the volume of convex sets</a>. Quite a few improvements were found. See e.g. , <a href="http://research.microsoft.com/en-us/um/people/kannan/Papers/blocking.pdf" rel="nofollow">Blocking Conductance and Mixing in random walks,</a> R. Kannan, L. Lovasz and R. Montenegro, in Combinatorics, Probability and Computing (2005) </p>