Muestreo del politopo de Birkhoff

Question

El conjunto de $n\times n$ matrices reales y no negativas cuyas filas y columnas suman uno forman la conocida Politopo de Birkhoff

Hace poco alguien me preguntó si sabía

¿Cómo muestrear (en tiempo polinómico) uniformemente al azar, a partir del politopo de Birkhoff?

Evidentemente, tras unos cuantos trucos, no tuve una buena respuesta, así que repito la pregunta anterior aquí (los trucos incluyen intentar explotar que toda matriz doblemente estocástica es una combinación convexa de matrices de permutación).

Answer 1

Por lo que sé, esto sigue abierto. Está relacionado con el problema de calcular el volumen del politopo de Birkhoff (o calcular el volumen de sus caras), que se conoce de forma cerrada sólo para $n\le 14$ . Esto también equivale a Esto podría abordarse contando matrices enteras no negativas con sumas iguales de filas y columnas (porque se puede leer el volumen a partir del coeficiente principal del polinomio de Ehrhart, como se hace en el documento El polinomio de Ehrhart del politopo de Birkhoff, por Matthias Beck y Dennis Pixton . Existen algoritmos que muestrean a partir de distribuciones cercanas a la uniforme (véanse los artículos siguientes).

El problema es bastante antiguo, pero recientemente se ha reavivado el interés de varios autores. Puedo indicarle algunos

• "¿Qué aspecto tiene una tabla de contingencia aleatoria?" por A. Barvinok
• "Sobre matrices aleatorias, doblemente estocásticas y tri-diagonales" por P. Diaconis y P. Matchett Wood
• "Propiedades de las matrices uniformes doblemente estocásticas" por S. Chatterjee, P. Diaconis, A. Sly
• Algoritmos de Gibbs/Metrópolis en un politopo convexo por P. Diaconis, G. Lebeau, L. Michel

Answer 2

Existe un algoritmo de tiempo polinómico basado en paseos aleatorios para muestrear aproximadamente cualquier $n$ -cuerpo convexo de dimensiones que también se aplica al politopo de Birkhoff. Se trata de un algoritmo de Dyer, Frieze y Kannan: Un algoritmo aleatorio de tiempo polinómico para aproximar el volumen de cuerpos convexos . Se han encontrado bastantes mejoras. Véase, por ejemplo, , Conductancia de bloqueo y mezcla en paseos aleatorios, R. Kannan, L. Lovasz y R. Montenegro, en Combinatoria, Probabilidad y Computación (2005)

Answer 3

Tal vez no sea completamente aleatorio, pero recientemente hemos propuesto un algoritmo para muestrear desde el Politopo de Birkhoff usando un algoritmo Riemannian-MCMC, específicamente simulando la dinámica de Langevin en la variedad usando mapas de retracción de primer orden. Pensamos que estaría relacionado con el tema para compartirlo aquí:

Birdal, Tolga, y Umut Simsekli. "Probabilistic Permutation sincronización utilizando la estructura riemanniana del politopo de Birkhoff". Politopo de Birkhoff". Actas de la Conferencia del IEEE sobre visión por ordenador y Pattern Recognition. 2019. https://arxiv.org/abs/1904.05814