Statistic Analysis for Probabilistic Processes
Michel de Rougemont, Mathieu Tracol · 2009
We associate a statistical vector to a trace and a geometrical embedding to a Markov decision process, based on a distance on words, and study basic membership and equivalence problems. The membership problem for a trace w and a Markov decision process S decides if there exists a strategy on S which generates with high probability traces close to w. We prove that membership of a trace is testable and equivalence of MDPs is polynomial time approximable. For probabilistic automata, membership is not testable, and approximate equivalence is undecidable. We give a class of properties, based on results concerning the structure of the tail sigma-field of a finite Markov chain, which characterizes equivalent Markov decision processes in this context.