A stochastic Ramsey theorem

We establish a stochastic extension of Ramsey's theorem. Any Markov chain generates a filtration relative to which one may define a notion of stopping times. A stochastic colouring is any k-valued (k<∞) colour function defined on all pairs consisting of a bounded stopping time and a finite partial history of the chain truncated before this stopping time. For any bounded stopping time θ and any infinite history ω of the Markov chain, let ω|θ denote the finite partial history up to and including the time θ(ω). Given k=2, for every ϵ>0, we prove that there is an increasing sequence θ1<θ2<⋯ 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