An Isaac Newton Institute Workshop

Logic and Databases

Concentration Bounds for Markov Processes of Metafinite Models

Author: James F. Lynch (Clarkson University)

Abstract

A formal model of discrete dynamical systems with probabilistic updates is presented. States of a system are metafinite models, and update rules are essentially Abstract State Machine rules augmented with a random function. Given an initial state, a sequence of updates generates a trajectory in the phase space of the system. It is shown that if the states in the trajectory satisfy certain locality conditions, then logically definable random variables of the states are concentrated around their expectation. That is, with high probability, their values are close to their average value.