Description
Abstract:
A 2000-es évek elején egy népszerű ötlet volt a Markov lánc Monte Carlo metódusokkal foglalkozó közösségben, hogy érdemes néha nagyot lépni egy Markov láncban, mert az ilyen nagy lépések a keveredést javíthatják. Ez azonban csak egzakt, bizonyított tételek nélküli feltételezés volt. Egy korábbi munkánkban (Miklos et al, 2010) rámutattunk arra, hogy a nagy ugrásokhoz tipikusan kis Metropolis-Hastings hányadosok tartozhatnak, és ha a nagy ugrások nélkül a Markov lánc nem irreducibilis, akkor ez a Markov lánc lassú keveredését okozhatja.
Az előadásomban három olyan Markov láncot mutatok be, ahol a nagy ugrások nélkülözhetetlenek, mégis a Metropolis- Hasting hányados reciprokára polinom felső korlátot tudunk adni. Ez a három lánc a teljes páros gráfok félig reguláris faktorizációin, páros gráfok élszínezésein valamint a legtakarékosabb reverziós rendezésesen bolyong (Aksen et al., 2017, Hong & Miklos, 2023, Bixby et al, 2016). Ezekről a Markov láncokról azt sejtjük, hogy gyorsan keverednek, de a bízonyításhoz valószínűleg eddig nem ismert technikák kellenek.
Referenciák:
Miklós, I., Mélykúti, B., Swenson, K. (2010) The Metropolized Partial Importance Sampling MCMC mixes slowly on minimum reversal rearrangement paths ACM/IEEE Transactions on Computational Biology and Bioinformatics, 4(7):763-767.
Bixby, E, Flint, T, Miklós, I., (2016) Proving the Pressing Game Conjecture on Linear Graphs Involve, 9(1):41-56.
Aksen, M. Miklós, I., Zhou, K. (2017) Half-regular factorizations of the complete bipartite graph Discrete Applied Mathematics, 230:21-33.
Hong, L., Miklós, I. (2023) A Markov chain on the solution space of edge-colorings of bipartite graphs., Discrete Applied Mathematics, 332:7-22.