The Curse of Dimensionality or the Blessing of Markovianity

The beauty (and the blessing) of Markov processes is that they allow one to do computations on the state space ? of the Markov process as opposed to working in the sample space of this process, which is at least as large as ?ℕ and therefore huge relative to ?. Obviously, the tractability of a problem formulated on ? depends on how big this space is. When ? is a subset of a medium to high dimensional space, problems quickly become intractable. This fact is often referred to as the curse of dimensionality. But, even in high dimensions, ? is small compared to ?ℕ. Hence, it is surprising that some recent papers have claimed to resolve the curse of dimensionality by working instead in the sample space. In this paper, we will review one such example.