Tight space-noise tradeoffs in computing the ergodic measure

Abstract

In this paper we obtain tight bounds on the space-complexity of computing the ergodic measure of a low-dimensional discrete-time dynamical system affected by Gaussian noise. If the scale of the noise is epsilon, and the function describing the evolution of the system is not itself a source of computational complexity, then the density function of the ergodic measure can be approximated within precision delta in space polynomial in log 1/epsilon + log log 1/delta. We also show that this bound is tight up to polynomial factors. In the course of showing the above, we prove a result of independent interest in space-bounded computation: namely, that it is possible to exponentiate an (n x n)-matrix to an exponentially large power in space polylogarithmic in n.