Parowanie łańcuchów Markowa w losowych kolorowaniach grafu.

Praca prezentuje technikę parowania łańcuchów Markowa stosowaną w analizie zbieżności rozkładu próbek zwracanych przez algorytm Monte Carlo do rozkładu jednostajnego. Metoda została zilustrowana przykładem losowania kolorowań grafu z maksymalnym stopniem wierzchołka ograniczonym odpowiednio przez liczbę kolorów.

In this paper we present the Markov Chain Coupling technique used in the analysis of the convergence of a Markov chain sampler to a uniform sampler. We show an application of this method in colorings of graphs with maximum vertex degree bounded by the number of colors.