The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

LAA

Seminar

Concentration bounds for Markov processes of metafinite models

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

Seminar Room 1, Newton Institute

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.

Presentation

[dvi ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧