Journal article
Input-output maps are strongly biased towards simple outputs
- Abstract:
- Many systems in nature can be described using discrete input–output maps. Without knowing details about a map, there may seem to be no a priori reason to expect that a randomly chosen input would be more likely to generate one output over another. Here, by extending fundamental results from algorithmic information theory, we show instead that for many real-world maps, the a priori probability P(x) that randomly sampled inputs generate a particular output x decays exponentially with the approximate Kolmogorov complexity K˜(x) of that output. These input–output maps are biased towards simplicity. We derive an upper bound P(x) ≲ 2−aK˜(x)−b, which is tight for most inputs. The constants a and b, as well as many properties of P(x), can be predicted with minimal knowledge of the map. We explore this strong bias towards simple outputs in systems ranging from the folding of RNA secondary structures to systems of coupled ordinary differential equations to a stochastic financial trading model.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 861.2KB, Terms of use)
-
- Publisher copy:
- 10.1038/s41467-018-03101-6
Authors
- Publisher:
- Springer Nature
- Journal:
- Nature Communications More from this journal
- Volume:
- 9
- Article number:
- 761
- Publication date:
- 2018-02-22
- Acceptance date:
- 2018-01-19
- DOI:
- ISSN:
-
2041-1723
- Keywords:
- Pubs id:
-
pubs:826743
- UUID:
-
uuid:ea63fb2d-c82b-4009-8049-c27b808cf6c5
- Local pid:
-
pubs:826743
- Source identifiers:
-
826743
- Deposit date:
-
2018-02-26
Terms of use
- Copyright holder:
- Dingle et al
- Copyright date:
- 2018
- Notes:
- This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record