Probability and Recursion

Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science at Columbia University. Prior to joining Columbia, he was Director of the Computing Principles Research Department at Bell Labs (1991-2001) and at Avaya Labs (2001-2002), and Professor of Computer Science at Stanford University (2002-2003). Dr. Yannakakis received his PhD from Princeton University in 1979. His research interests include algorithms, complexity, optimization, databases, testing and verification. He has served on the editorial boards of several journals, including as the past editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems. Dr. Yannakakis is a Fellow of the ACM and of Bell Labs, and a recipient of the Knuth Prize.
Abstract: We discuss recent work on the modeling and algorithmic analysis of systems involving recursion and probability. Recursive Markov chains extend ordinary finite state Markov chains with the ability to invoke other Markov chains in a potentially recursive manner. They offer a natural abstract model of probabilistic programs with procedures, and generalize other classical well-studied stochastic models, eg. Branching Processes and Stochastic Context-free Grammars, that have been used in a variety of areas. Recursive Markov Decision Processes and Stochastic Games similarly extend ordinary finite decision processes and games, and they are natural models for recursive systems involving both probabilistic and nonprobabilistic (controlled) actions. In a series of recent papers with Kousha Etessami (U. of Edinburgh), we have introduced these models and studied central algorithmic problems regarding questions of termination, reachability, and analysis of the properties of their executions. In this talk we will present some of the basic theory and algorithms.