Drzewa losowe i algorytmy Monte Carlo

U podstaw algorytmów Monte Carlo leżą dwie ogólne idee: losowanie ważone i generowanie łańcuchów Markowa. Sekwencyjne Monte Carlo (SMC) opiera się na losowaniu ważonym w połączeniu z czymś przypominającym zasadę doboru naturalnego. Markowowskie Monte Carlo (MCMC) wykorzystują łańcuchy Markowa zbieżne do docelowego rozkładu prawdopodobieństwa. Pomysłowym połączeniem SMC i MCMC są "cząsteczkowe algorytmy MCMC (PMCMC)", które pojawiły się w pracy opublikowanej w 2010 r. Postaram się pokazać jak i dlaczego działa PMCMC na przykładzie nowych algorytmów, które nazwaliśmy "Poisson Tree Monte Carlo". W istocie, konstruujemy łańcuchy Markowa na przestrzeni znakowanych drzew. Stojąca za tym matematyka jest elementarna, ale w moim przekonaniu interesująca. Zasadnicza część mojego wystąpienia będzie oparta na nieopublikowanej jeszcze, wspólnej pracy z Tomaszem Cąkałą i Błażejem Miasojedowem (obaj MIM UW).

There are two general ideas behind Monte Carlo algorithms: importance sampling and generating Markov chains. Sequential Monte Carlo (SMC) is based on importance sampling combined with something like the "survival of the fittest" principle. Markov chain Monte Carlo (MCMC) uses Markov chains which converge to the target probability distribution. An ingenious fusion of SMC and MCMC are "particle MCMC (PMCMC)" algorithms, introduced in a paper published in 2010. I will try to show how and why PMCMC works on the example of new algorithms named "Poisson Tree Monte Carlo". We construct Markov chains on the space of marked trees. The underlying mathematics is elementary but, in my view, interesting. The main part of my talk will be based on an unpublished joint work with Tomasz Cąkała and Błażej Miasojedow (both MIM UW).