Approximating a Sequence of Observations by a Simple Process

Dinah Rosenberg, Eilon Solan and Nicolas Vieille

Given a sequence s₀,s₁,…,s_N of observations from a finite set S, we construct a process (s_n) that satisfies the following properties:

(i) (s_n) is a piecewise Markov chain with at most S pieces,

(ii) the conditional distribution of s_n given s₀,…, s_n-1 is close to the empirical transition given by the observed sequence, for most n's, and

(iii) under (s_n), with high probability the empirical frequency of the realized sequence is close to the one given by the observed sequence.

We generalize this result to the case that the conditional distribution of s_n given s₀,…, s_n-1 is required to be in some polyhedron V(s_n-1).

This result is used in the paper “Stochastic Games with Imperfect Monitoring”.