How to lose at Monte Carlo: A simple dynamical system whose typical statistical behavior is non-computable

Cristobal Rojas, Michael Yampolsky

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Pages1066-1072
Number of pages7
ISBN (Electronic)9781450369794
DOIs
Publication statusPublished - 8 Jun 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: 22 Jun 202026 Jun 2020

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/TerritoryUnited States
CityChicago
Period22/06/2026/06/20

Keywords

  • Logistic family
  • Monte Carlo simulation
  • Non-computability
  • Physical measures

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'How to lose at Monte Carlo: A simple dynamical system whose typical statistical behavior is non-computable'. Together they form a unique fingerprint.

Cite this