Titelaufnahme

Titel
Markov Chain Monte Carlo algorithms for the uniform sampling of combinatorial objects / vorgelegt von Steffen Rechner
VerfasserRechner, Steffen
Akademischer Betreuer/InMüller-Hannemann, Matthias ; Brandes, Ulrik
BeteiligtMüller-Hannemann, Matthias ; Brandes, Ulrik
KörperschaftMartin-Luther-Universität Halle-Wittenberg
ErschienenHalle, 2018
Umfang1 Online-Ressource (188 Seiten)
HochschulschriftMartin-Luther-Universität Halle-Wittenberg, Dissertation, 2018
Anmerkung
Tag der Verteidigung: 04.06.2018
SpracheEnglisch
DokumenttypE-Book
URNurn:nbn:de:gbv:3:4-22564 
Zugriffsbeschränkung
 Das Dokument ist frei verfügbar.
Dateien
Markov Chain Monte Carlo algorithms for the uniform sampling of combinatorial objects [14.99 mb]
Links
Nachweis
Klassifikation
Zusammenfassung

In dieser Arbeit untersuche ich die Effizienz von Markov-Chain Monte Carlo (MCMC) Algorithmen zum gleichverteilten Erzeugen zufälliger kombinatorischer Strukturen. Zu diesem Zweck habe ich eine Software namens marathon entwickelt, welche ich zur Berechnung struktureller Eigenschaften von Markov-Ketten einsetze, die rein analytisch schwer zu bestimmen wären. Ich verwende diese Software, um MCMC-Algorithmen aus drei Problemklassen zu untersuchen. Zunächst untersuche ich drei bekannte Methoden zum Erzeugen zufälliger bipartiter Graphen mit festen Knotengraden. Unter anderem zeige ich, welcher Algorithmus am besten für den Einsatz in speziellen ökologischen Anwendungen geeignet ist. Anschließend betrachte ich das Erzeugen zufälliger bipartiter Graphen mit beschränkten Knotengraden. Ich führe zwei neue MCMC-Algorithmen ein und untersuche auf experimentellem Wege deren Effizienz. Schließlich analysiere ich Algorithmen zum zufälligen Erzeugen perfekter Matchings in bipartiten Graphen. Dabei identifiziere ich Initialzustände, die eine polynomielle beziehungsweise exponentielle Mischzeit besitzen.

Zusammenfassung ([])

In this thesis, we discuss a family of sampling methods known as Markov chain Monte Carlo (MCMC) algorithms. To support the analysis of such algorithms,we developed the software tool marathon, designed to determine properties of Markov chains that are usually hard to find analytically. We apply our software to experimentally assess the efficiency of several MCMC algorithms from three sampling applications. First, we address three well-known MCMC algorithms for the uniform sampling of bipartite graphs with fixed degrees. In a set of experiments, we show which sampling algorithm works best in certain types of ecological applications. Motivated by the work with incomplete data, we next address the uniform sampling of bipartite graphs whose degrees lie in prescribed intervals. After introducing two new MCMC algorithms, we give a proof of their correctness and experimentally assess their efficiency. Finally, we address the uniform sampling of perfect matchings in bipartite graphs. In a set of experiments with two special classes of bipartite graphs, we identify initial states that require a polynomial and an exponential number of steps.

Zusammenfassung

Zufallsauswahl; Markov-Chain Monte Carlo; zufällige Graphen; Binärmatrizen mit beschränkten Randsummen; bipartite Graphen mit beschränkten Knotengraden; perfekte Matchings in bipartiten Graphen; Analyse von Zustandsgraphen

Zusammenfassung ([])

random sampling; Markov-Chain Monte Carlo; random graphs; binary matrices with restricted margins; bipartite graphs with restricted degrees; perfect matchings in bipartite graphs; state graph analysis

Keywords
Zufallsauswahl; Markov-Chain Monte Carlo; zufällige Graphen; Binärmatrizen mit beschränkten Randsummen; bipartite Graphen mit beschränkten Knotengraden; perfekte Matchings in bipartiten Graphen; Analyse von Zustandsgraphen
Keywords ([])
random sampling; Markov-Chain Monte Carlo; random graphs; binary matrices with restricted margins; bipartite graphs with restricted degrees; perfect matchings in bipartite graphs; state graph analysis