Pengambilan sampel cocok sempurna secara seragam secara acak

Misalkan saya memiliki grafik dengan M ( G ) yang (tidak diketahui) set matching sempurna G . Misalkan set ini tidak kosong, lalu seberapa sulitkah untuk mengambil sampel secara acak dari M ( G ) ? Bagaimana jika saya baik-baik saja dengan distribusi yang dekat dengan seragam, tetapi tidak cukup seragam, lalu apakah ada algoritma yang efisien?$G$$M(G)$$G$$M(G)$

Ada makalah klasik Jerrum dan Sinclair (1989) tentang pengambilan sampel kecocokan sempurna dari grafik padat. Makalah klasik lain dari Jerrum, Sinclair dan Vigoda (2004; pdf) membahas contoh kecocokan sempurna dari grafik bipartit.

Kedua makalah ini menggunakan rantai Markov yang cepat, sehingga sampelnya hampir seragam. Saya membayangkan pengambilan sampel yang seragam itu sulit.

Jika Anda menganggap bahwa grafik Anda adalah planar, maka ada prosedur waktu polinomial untuk masalah pengambilan sampel ini.

Pertama, masalah penghitungan jumlah pencocokan sempurna ada di P untuk grafik planar. ( https://en.wikipedia.org/wiki/FKT_algorithm ) (Eksposisi yang baik dari fakta ini dapat ditemukan di bab pertama buku Jerrum tentang Menghitung, Menyampel, dan Mengintegrasikan.)

$e$$G$$G \setminus e$$e$$G$

(Ini mengambil keuntungan dari fakta bahwa pencocokan adalah struktur "dapat direduksi sendiri", sehingga menghitung masalah dan masalah pengambilan sampel yang seragam pada dasarnya sama. Anda dapat melihat JVV "Pembuatan Struktur Kombinatorial Secara Acak dari Distribusi Seragam" untuk informasi lebih lanjut tentang ini sudut pandang.)

Bukti sederhana bahwa ini memberikan distribusi yang benar:

$c(H)$$H$$n!$$n = H/2$

$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} \} )}$.

Catat itu $c(G \setminus \{e_1, \ldots, e_{n-1} \}) = 1$, sejak $G \setminus \{e_1, \ldots, e_{n-1} \}$ hanya ujung $e_n$. Jadi teleskop dan daun produk ini$1 / c(G)$.