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

Cristobal Rojas, Michael Yampolsky

Abstract

We consider the simplest non-linear discrete dynamical systems, given by the logistic maps $f_{a}(x)=ax(1-x)$ of the interval $[0,1]$. We show that there exist real parameters $a\in (0,4)$ for which almost every orbit of $f_a$ 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.
BibTeX
@inproceedings{rojas2019how,
  author = {Cristobal Rojas and Michael Yampolsky},
  title = {{How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non computable}},
  booktitle = {STOC},
  year = {2019},
  doi = {10.1145/3357713.3384237},
}
Figure