Approximating
a Sequence of Observations by a Simple Process

Dinah
Rosenberg, Eilon Solan and Nicolas Vieille

Given a sequence *s*_{0},*s*_{1},…,*s _{N}*

(i)
(*s** _{n}*) is a
piecewise Markov chain with at most

(ii)
the conditional
distribution of* s** _{n}* given

(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

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