← All problems
Unverified

Is Markov reachability problem Skolem-Hard for Ergodic Markov chains?

Given a Markov chain MM, an initial distribution uu and target distribution vv, and a rational number rr, consider the problem of checking if there exists an nn such that uMnv=ru M^n v =r. This problem is known to be as hard as the Skolem problem of LRS. However, the reduction requires the Markov chain to be non-ergodic, in particular it is reducible and periodic. If we now assume the Markov chain to be irreducible and aperiodic (a natural assumption that is often used since forever!), does it remain hard?! Both yes or no answers would be very interesting and have consequences to model checking of probabilistic linear dynamical systems.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu