TY - GEN
T1 - How to lose at Monte Carlo
T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
AU - Rojas, Cristobal
AU - Yampolsky, Michael
N1 - Funding Information:
The authors would like to thank the anonymous referees for their valuable comments and helpful suggestions. C.R. was partially supported by the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No. 731143, by project FONDECYT Regular No. 1190493 and project Basal PFB-03 CMM-Universidad de Chile. M.Y. was partially supported by NSERC Discovery grant.
Publisher Copyright:
© 2020 ACM.
PY - 2020/6/8
Y1 - 2020/6/8
N2 - 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.
AB - 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.
KW - Logistic family
KW - Monte Carlo simulation
KW - Non-computability
KW - Physical measures
UR - http://www.scopus.com/inward/record.url?scp=85086766980&partnerID=8YFLogxK
U2 - 10.1145/3357713.3384237
DO - 10.1145/3357713.3384237
M3 - Conference contribution
AN - SCOPUS:85086766980
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1066
EP - 1072
BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Makarychev, Konstantin
A2 - Makarychev, Yury
A2 - Tulsiani, Madhur
A2 - Kamath, Gautam
A2 - Chuzhoy, Julia
PB - Association for Computing Machinery
Y2 - 22 June 2020 through 26 June 2020
ER -