Skip to content



Concentration bounds for Markov processes of metafinite models

Lynch, J (Clarkson)
Monday 27 February 2006, 16:15-17:00

Seminar Room 1, Newton Institute


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.


[dvi ]


MP3MP3 Real AudioReal Audio

Back to top ∧