Próbkowanie idealne dopasowanie równomiernie losowo

Załóżmy, że ma wykres o do (brak danych) zestawu doskonałych skojarzeń z . Załóżmy, że ten zestaw nie jest pusty, to jak trudne jest jednorodne losowe pobieranie próbek z ? Co się stanie, jeśli nie mam nic przeciwko rozkładowi zbliżonemu do jednorodnego, ale niezupełnie jednorodnemu, to czy istnieje skuteczny algorytm? $G$ $M(G)$ $G$ $M(G)$

— Artem Kaznatcheev
źródło

Czy wiesz coś więcej o

? Innymi słowy, czy byłbyś zainteresowany jakąkolwiek ograniczoną klasą graficzną?

G

$G$

— Juho,

@Juho Wolę wyniki dla grafów ogólnych, w szczególności dla grafów gęstych (więc to, o czym wspomina Yuval w swojej odpowiedzi, wydaje się obiecujące). Wydaje mi się, że widziałem już wcześniej niektóre wykresy płaskie. Ponieważ jednak jest to pytanie ogólne, jeśli masz odpowiedź na kilka interesujących rodzin wykresów, prawdopodobnie nadal warto na nie odpowiedzieć, ponieważ inni, którzy szukają tego pytania, chcieliby wiedzieć.

— Artem Kaznatcheev,

Żeby było jasne, zakładam, że nie masz pod ręką

M (G)

$M(G)$

— Raphael

@ Rafael Myślę, że pytanie byłoby trywialne, gdybyś to zrobił. Właściwie myślę, że pytanie byłoby stosunkowo proste, gdybyś tylko

miał

, ponieważ zwykle istnieje zgodność między liczeniem a próbkowaniem. A może miałeś na myśli „pod ręką” w inny sposób?

| M (G) |

$|M(G)|$

— Artem Kaznatcheev

Widzę. Uznałem twoje sformułowania za dwuznaczne, które próbowałem poprawić. Czy dobrze to zrozumiałem?

— Raphael

Odpowiedzi:

Istnieje klasyczny artykuł Jerruma i Sinclaira (1989) na temat pobierania idealnych dopasowań z gęstych wykresów. Kolejna klasyczna praca Jerruma, Sinclaira i Vigody (2004; pdf) omawia próbkowanie idealnych dopasowań z dwustronnych grafów.

Oba te papiery używają szybkiego mieszania łańcuchów Markowa, więc próbki są prawie jednolite. Wyobrażam sobie, że jednolite pobieranie próbek jest trudne.

— Yuval Filmus
źródło

Jeśli założysz, że twój wykres jest płaski, istnieje procedura wielomianowa dla tego problemu z próbkowaniem.

Po pierwsze, problem zliczania liczby idealnych dopasowań leży w P dla grafów płaskich. ( https://en.wikipedia.org/wiki/FKT_alameterm ) (Dobra prezentacja tego faktu znajduje się w pierwszym rozdziale książki Jerrum o liczeniu, próbkowaniu i integracji).

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

(Wykorzystuje to fakt, że dopasowania są strukturą „samoregenerowalną”, więc problemy z liczeniem i problemy z jednolitym próbkowaniem są zasadniczo takie same. Możesz zobaczyć JVV „Losowe generowanie struktur kombinatorycznych z jednolitego rozkładu”, aby uzyskać więcej informacji na ten temat punkt widzenia.)

Prosty dowód, że daje to prawidłową dystrybucję:

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

$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
źródło