HOROWITZ SEMINAR

PROBABILITY, ERGODIC THEORY and DYNAMICAL SYSTEMS

Zibo Xu (LSE, UK)

will speak on

A Stochastic Ramsey Theorem.

ABSTRACT:
We present and prove a stochastic extension of Ramsey's theorem.

For any Markov chain, we consider any 2-valued colour function defined on every pair consisting of a bounded stopping time and a
finite partial history of the chain truncated before this stopping time.
For any infinite history ω, let ω|θ denote the finite partial history contained in ω up to and including the stopping time θ(ω).
We prove that for every ε>0 , there is an increasing sequence θ₁<θ₂<... of bounded stopping times having the property that,
with probability greater than 1-ε , the history ω is such that the values assigned to all pairs (ω|θ_i, θ_j) , with i< j, are the same.

Just as for the classical Ramsey theorem, we also obtain a finitary stochastic Ramsey theorem:
for any finite L and for long enough partial histories there exists an increasing sequence of bounded stopping times (θ₁,...,θ_L) and,
with appropriate finiteness assumptions, we find that the time one must wait for the last θ_L is uniformly bounded, independently of the probability transitions.

We generalize the results to any finite number of colors.

To suggest a talk (yours, or someone else's), contact Jon. Aaronson: aaro at post dot tau dot ac dot il

Back to: Jon Aaronson's homepage.

Last update on 12/10/08.