An Exponential Lower Bound for Markovian State Augmentation under Minimal Observation

We present a minimal deterministic construction showing that restoring Markovianity via state-space augmentation under coarse observation can require an exponential number of states. Specifically, we construct a family of finite deterministic systems with a binary observation map such that any Markovian augmentation sufficient to predict the future observation process must have cardinality exponential in the size of the underlying microstate space. The result is purely structural, does not rely on stochasticity or noise, and provides a lower bound on the complexity of Markovian representations under partial observation.