The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known [*Birkhoff polytope*](http://en.wikipedia.org/wiki/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).



Sampling from the Birkhoff polytope
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 to~~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 [The Ehrhart polynomial of the Birkhoff polytope, by Matthias Beck and Dennis Pixton](http://arxiv.org/abs/math/0202267). 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


* ["What does a random contingency table look like?"](http://arxiv.org/abs/0806.3910), by A. Barvinok
* ["On random, doubly stochastic, tri-diagonal matrices"](http://www-stat.stanford.edu/~cgates/PERSI/papers/TriDiag.pdf), by P. Diaconis and P. Matchett Wood
* ["Properties of Uniform Doubly Stochastic Matrices"](http://arxiv.org/abs/1010.6136) by S. Chatterjee, P. Diaconis, A. Sly
* [Gibbs/Metropolis algorithms on a convex polytope](http://arxiv.org/abs/1104.0749) by P. Diaconis, G. Lebeau, L. Michel


