Speaker: Marek Grabowski (UW)

Title of the talk: Computing steady state of Markov Chain by combinatorial aggregation

Abstract: Probabilistic model checking is receiving quite a lot of attention around the world recently (i.e. DARPA is funding PRISMATIC project). Unlike 'normal' model checking which was research for nearly 30 years, probabilistic model checking is still a young discipline.
Most common framework for modeling probabilistic processes are Markov Chains, both discrete and continuos time and Markov Decision Processes. One of interesting questions one can ask about DTMCs and CTMCs is 'to what distribution given chain converges' (what's the steady state of it).
Theory of Markov Chains has over 100 years now and analytic solutions of all interesting questions are well known. Problem with such solutions is that they're usually untraceable for real-life models, because of their size. This is the reason why iterative methods are most commonly used. Unfortunately they also fail for some examples.
I'll show an algorithm which was proposed by Pokarowski in his PhD thesis and implemented by me just recently, which for some class of models gives huge speedup in return for some precision. I'll describe theory behind this algorithm, show how it works in general and some test results. I'll also tell what modifications are on the way and what we hope to achieve in the end.