
Computer Science 2014
First Passage ValueAbstract: For many stochastic dynamic systems, the Mean First Passage Time (MFPT) is a useful concept, which gives expected time before a state of interest. This work is an extension of MFPT in several ways. (1) We show that for some systems the systemwide MFPT, calculated using the second largest eigenvalue only, captures most of the fundamental dynamics, even for quite complex, highdimensional systems. (2) We generalize MFPT to Mean First Passage Value (MFPV), which gives a more general value of interest, e.g., energy expenditure, distance, or time. (3) We provide bounds on First Passage Value (FPV) for a given confidence level. At the heart of this work, we emphasize that for our goals, many hybrid systems can be approximated as Markov Decision Processes. So, many systems can be controlled effectively using this framework. However, our framework is particularly useful for metastable systems. Such systems exhibit interesting longliving behaviors from which they are guaranteed to inevitably escape (e.g., eventually arriving at a distinct failure or success state). Our goal is then either minimizing or maximizing the value until escape, depending on the application.
