Article ISI SCOPUS
Proceedings of the Annual ACM Symposium on Theory of Computing  (2020)

How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable

Makarychev, K; Makarychev, Y; Tulsiani, M; Kamath, G; Chuzhoy, J

Abstract

We consider the simplest non-linear discrete dynamical systems, given by the logistic maps fa(x)=ax(1-x) of the interval [0,1]. We show that there exist real parameters ag (0,4) for which almost every orbit of fa has the same statistical distribution in [0,1], but this limiting distribution is not Turing computable. In particular, the Monte Carlo method cannot be applied to study these dynamical systems.

Más información

Título según WOS: How to Lose at Monte Carlo: A Simple Dynamical System Whose Typical Statistical Behavior Is Non-computable
Título según SCOPUS: How to lose at Monte Carlo: A simple dynamical system whose typical statistical behavior is non-computable
Título de la Revista: Proceedings of the Annual ACM Symposium on Theory of Computing
Editorial: Association for Computing Machinery
Fecha de publicación: 2020
Página final: 1072
Idioma: English
DOI:

10.1145/3357713.3384237
Notas: ISI, SCOPUS