Skip to main content

A maximal entropy stochastic process for a timed automaton

Nicolas Basset ( University of Oxford )
We consider the following question: what is the least biased stochastic process over the runs of a given timed automaton? By "least biased", we mean the one that generates runs with a distribution which is closest to uniform (wrt. volume measure). The solution is based on a lifting to the timed setting of Shannon's theory about the maximal entropy Markov chain of a finite graph. We will recall this theory at the beginning of the talk (aka. Parry measure). Then we define stochastic processes over runs of timed automata and their entropy the definition of which is inspired by Shannon's differential entropy rate. We describe an ergodic stochastic process which maximizes the entropy and explain how (with an asymptotic equipartition property) the runs can be sampled quasi uniformly according to that process. This process is defined in an analogous way to the Shannon Parry Markov chain described at the beginning of the talk.

Share this: