Idea metod Monte Carlo opartych na teorii łańcuchów Markowa (Markov Chain Monte Carlo), w skrócie MCMC, polega na tym, że chcąc losować liczby według ustalonego rozkładu dyskretnego \((\{x_i\}, \{p_i\})\), budujemy taki ergodyczny łańcuch Markowa na przestrzeni stanów, którymi są punkty \(x_i\), że jego stan stacjonarny \(\pi \) ma współrzędne \(p_i\). Symulując zachowanie się tego łańcucha, możemy mieć niemal pewność, że po odpowiedniej liczbie kroków uzyskiwane elementy będą pochodzić z rozkładu \(\pi \). Największym problemem jest tutaj dobranie odpowiedniego łańcucha. Dużą pomoc stanowi tu teoria grafów.
Jeżeli graf, po którym odbywa się spacer, jest skończony, spójny, a łańcuch Markowa jest nieokresowy, to na podstawie twierdzenia ergodycznego istnieje dokładnie jeden stan stacjonarny, a więc musi to być ten sam stan, co w Twierdzeniu 17.18 udowodnionym powyżej. Jeżeli więc dla danego rozkładu \((\{x_i\}, \{p_i\})\}\) potrafimy zbudować taki graf o wierzchołkach \(x_i\), że określone w twierdzeniu liczby \(\pi _i\) są równe liczbom \(p_i\), to podczas symulowania spaceru losowego będziemy po pewnym czasie otrzymywać punkty z rozkładu \((\{x_i\}, \{p_i\})\). Omówimy zagadnienie, tak zwany problem plecakowy, gdzie taka metoda może z powodzeniem być zastosowana.
Zagadnienie plecakowe stanowi klasyczny problem optymalizacji dyskretnej, który w sensie informatycznym jest równoważny wielu innym klasycznym zagadnieniom.
Mamy \(d\) przedmiotów, powiedzmy \(1,2,\dots , d\), i znamy wartość każdego z nich, powiedzmy \(c_1, \dots , c_d\), oraz ich wagi, powiedzmy \(w_1, \dots , w_d\). Chcemy tak załadować plecak, aby wartość zabranych przedmiotów była największa.
Problem w tym, że waga plecaka nie może przekroczyć ustalonej liczby \(B\).
Matematyczny model:
\[ V = \{v = (v_1, \dots v_d) \in \{0,1\}^d: \sum _{i = 1}^d v_i w_i \le B\} \]
oraz niech \(\di f(v) = \sum _{i=1}^d v_i c_i\) dla \(v \in V\). Szukamy \(\arg \max f\).
W dalszym ciągu będziemy zakładać, że zadanie jest nietrywialne, czyli że \(\sum _{i = 1}^d w_i > B\).
Stosujemy PRS. W tym celu chcemy generować punkty ze zbioru \(V\) według rozkładu jednostajnego. To może być bardzo duży zbiór i ciężko jest nawet ustalić liczbę jego elementów.
Aby jednak wykonać to zadanie, modyfikujemy opisany poprzednio spacer po grafie o wierzchołkach z \(V\), który jest naturalnym zacieśnieniem \(d\)-wymiarowej kostki dyskretnej.
W kolejnym kroku przechodzimy ze stanu \(v = (v_1,\dots , v_d) \in V\) do stanu sąsiedniego w sposob następujący: losujemy wskaźnik \(j\) spośród liczb \(1,2, \dots , d\) zgodnie z rozkładem jednostajnym i dokonujemy zmiany \(j\)-tej współrzędnej \(v_j\) na \(v'_j = 1- v_j\), dzięki czemu otrzymujemy wierzchołek
\[v' =(v_1, \dots , v_{i-1},v'_j, v_{j+1}, \dots , v_d).\]
Jeżeli \(v' \in V\), to przenosimy się do \(v'\).
Jeżeli \(v' \notin V\) (waga plecaka jest za duża), to pozostajemy w \(v\).
Zaczynamy w chwili 0 z pustym plecakiem (\(X_0 = 0, \dots ,0) \in V\)), generujemy w powyższy sposób kolejne wierzchołki \(X_t\)
Otrzymany w ten sposób spacer oznaczamy przez \(\{X_t\}\).
Widać, że:
1. \(X_t\) jest łańcuchem Markowa.
2. \(X_t\) jest nieredukowalny (bo każdy stan komunikuje się ze stanem zerowym).
3. \(X_t\) jest nieokresowy, gdyż istnieją stany \(v\), w których spacer z dodatnim prawdopodobieństwem może przystanąć (gdy \(v' \notin V\)).
Istnieje więc dokładnie jeden rozkład stacjonarny \(\pi \).
Co więcej, \(\{X_t\}\) ma własność symetrii: \(\P (u,v) = \P (v,u)\) dla wszystkich \(u, v \in V\).
Ale to oznacza, że wektor \(\hat {\pi }\) o wszystkich współrzędnych równych \(\hat {\pi }_v = \frac {1}{\sharp V}\) jest rozkładem stacjonarnym Rzeczywiście:
\[\sum _{u \in V}\P (u,v)\frac {1}{\sharp V} = \sum _{u \in V}\P (v,u)\frac {1}{\sharp V} = 1 \cdot \frac {1}{\sharp V} = \frac {1}{\sharp V}.\]
Z jednoznaczności gwarantowanej przez twierdzenie ergodyczne otrzymujemy, że \(\pi = \hat {\pi }\).
Wniosek. Dla dużych \(t\) zmienne losowe \(X_t\) mają rozkład niemal identyczny co rozkład jednostajny na \(V\).
Opisana metoda jest mało efektywna. Istnieją dużo lepsze (szybsze) metody MCMC rozwiązywania problemu plecakowego oraz podobnych problemów. Wiele z nich opartych jest jednak na podobnej metodologii, co opisana powyżej.