### 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 ∈, 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 δ in space polynomial in log 1/∈ + log log 1/δ. 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 × n)-matrix to an exponentially large power in space polylogarithmic in n. Bibliography: 25 titles.

Original language | English (US) |
---|---|

Pages (from-to) | 1758-1783 |

Number of pages | 26 |

Journal | Sbornik Mathematics |

Volume | 208 |

Issue number | 12 |

DOIs | |

State | Published - Jan 1 2017 |

### All Science Journal Classification (ASJC) codes

- Algebra and Number Theory

### Keywords

- dynamical systems
- space-bounded computations

## Fingerprint Dive into the research topics of 'Tight space-noise tradeoffs in computing the ergodic measure'. Together they form a unique fingerprint.

## Cite this

*Sbornik Mathematics*,

*208*(12), 1758-1783. https://doi.org/10.1070/SM8884