Recurrence and transience for finite probabilistic tables

A Finite Probabilistic Table, or FPT, consists of a finite state space S, an initial distribution on S, and a finite set of Markov matrices on S, labeled by an alphabet Σ. An infinite word on Σ induces a non-homogeneous Markov chain (NHMC) on S.In the context of finite homogeneous Markov chains, a state s is recurrent if with probability one a run initialized on s visits s infinitely often. Equivalently, s is recurrent if with probability one, the proportion of time a run initialized on s spends on s converges to a non-zero limit.In this paper we introduce two natural notions of recurrence for non-homogeneous Markovian processes: a state s is weakly recurrent (resp. strongly recurrent) if with positive probability the process visits s infinitely often (resp. spends a non-zero proportion of time on s).These notions do not coincide in the context of NHMCs, and we study the related computational problem on FPTs: given an FPT and a state s, is there w∈Σ∞ such that s is weakly (resp. strongly) recurrent for the associated NHMC?We prove that the strong recurrence problem is PSPACE-complete, along with other complexity results, which contrast with previous results which showed for instance the undecidability of the weak recurrence problem.