Muestreo perfecto emparejamiento uniforme al azar

Supongamos que tengo una gráfica con el (desconocido) conjunto de perfectos matchings de . Suponga que este conjunto no está vacío, entonces, ¿qué tan difícil es muestrear uniformemente al azar de ? ¿Qué pasa si estoy de acuerdo con una distribución que es casi uniforme, pero no bastante uniforme, entonces hay un algoritmo eficiente? $G$ $M(G)$ $G$ $M(G)$

algorithms complexity-theory matching sampling Artem Kaznatcheev
fuente

¿Sabes algo más sobre ? O, en otras palabras, ¿te interesaría alguna clase de gráfico restringido?

G

$G$

Juho

@Juho Prefiero resultados para gráficos generales, en particular para gráficos densos (así que lo que Yuval menciona en su respuesta parece prometedor). He visto algunos resultados para gráficos planos antes, creo. Sin embargo, dado que esta es una pregunta general, si tiene una respuesta para algunas familias interesantes de gráficos, entonces probablemente valga la pena responderlas, ya que otras personas que buscan esta pregunta podrían saber.

Artem Kaznatcheev

Para ser claros, supongo que no tienes a la mano.

M (G)

$M(G)$

Raphael

@Raphael Creo que la pregunta sería trivial si lo hicieras. De hecho, creo que la pregunta sería relativamente sencilla si solo tuvieras, ya que generalmente existe una correspondencia entre el conteo y el muestreo. ¿O quiso decir "a mano" de alguna otra manera?

| M (G) |

$|M(G)|$

Artem Kaznatcheev

Veo. Encontré tu fraseo ambiguo, que intenté corregir. ¿Lo entendí bien?

Raphael

Respuestas:

Hay un artículo clásico de Jerrum y Sinclair (1989) sobre el muestreo de coincidencias perfectas de gráficos densos. Otro artículo clásico de Jerrum, Sinclair y Vigoda (2004; pdf) analiza el muestreo de coincidencias perfectas a partir de gráficos bipartitos.

Ambos documentos utilizan cadenas de Markov que se mezclan rápidamente, por lo que las muestras son casi uniformes. Me imagino que el muestreo uniforme es difícil.

Yuval Filmus
fuente

Si supone que su gráfico es plano, entonces hay un procedimiento de tiempo polinómico para este problema de muestreo.

Primero, el problema de contar el número de coincidencias perfectas está en P para los gráficos planos. ( https://en.wikipedia.org/wiki/FKT_algorithm ) (Una buena exposición de este hecho se puede encontrar en el primer capítulo del libro de Jerrum sobre Conteo, muestreo e integración).

Luego, para cada borde de , cuente el número de combinaciones perfectas de . Esto se puede convertir en la probabilidad de que una coincidencia perfecta uniforme contiene - sólo se dividen por el número de apareamientos perfectos en . Muestree una ventaja de acuerdo con esta probabilidad y continúe inductivamente. $e$ $G$ $G \setminus e$ $e$ $G$

(Esto se aprovecha del hecho de que los emparejamientos son una estructura "auto-reducible", por lo que los problemas de conteo y de muestreo uniforme son esencialmente los mismos. Puede ver JVV "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme" para obtener más información sobre esto punto de vista.)

Una prueba simple de que esto da la distribución correcta:

Sea el número de coincidencias perfectas ordenadas en un gráfico , como secuencias ordenadas. (¡Lo cual es Veces el número de coincidencias perfectas desordenadas, ) $c(H)$ $H$ $n!$ $n = H/2$

Deje la secuencia de aristas elegida en este procedimiento. Como cada paso era independiente del primero, la probabilidad de elegir esta secuencia de aristas es: $e_1, \ldots, e_n$

$\frac{ c(G \setminus e_1)}{c(G)} \frac{ c(G \setminus \{e_1, e_2\} )}{c(G \setminus e_1)} \ldots \frac{ c(G \setminus \{e_1, \ldots, e_{n-1} \}) }{c(G \setminus \{ e_1, \ldots, e_{n-2} \} )}$ .

Tenga en cuenta que , ya que es solo el borde . Entonces este producto se telescopía y deja . $c(G \setminus \{e_1, \ldots, e_{n-1} \}) = 1$ $G \setminus \{e_1, \ldots, e_{n-1} \}$ $e_n$ $1 / c(G)$

Lorenzo Najt
fuente