Compressing redundant information in Markov chains

Abstract

Given a strongly stationary Markov chain and a finite set of stopping rules, we prove the existence of a polynomial algorithm which projects the Markov chain onto a minimal Markov chain without redundant information. Markov complexity is hence defined and tested on some classical problems.

8 pages, 1 figure

Cited by in corpus (1)

• Approximation of target problems in Blackwell spaces