5
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Input–output maps are strongly biased towards simple outputs

, 1 , 2 , 3 , 1 , 2 , , 1

Nature Communications

Nature Publishing Group UK

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tilde K(x)$$\end{document} of that output. These input–output maps are biased towards simplicity. We derive an upper bound P( x) ≲  \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{ - a\tilde K(x) - b}$$\end{document} , 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.

### Abstract

Algorithmic information theory measures the complexity of strings. Here the authors provide a practical bound on the probability that a randomly generated computer program produces a given output of a given complexity and apply this upper bound to RNA folding and financial trading algorithms.

### Most cited references25

• Record: found

### On the Complexity of Finite Sequences

(1976)
Bookmark
• Record: found

### Fast folding and comparison of RNA secondary structures

(1994)
Bookmark
• Record: found

### A formal theory of inductive inference. Part I

(1964)
Bookmark

### Author and article information

###### Contributors
dingle.k@gust.edu.kw
ard.louis@physics.ox.ac.uk
###### Journal
Nat Commun
Nat Commun
Nature Communications
Nature Publishing Group UK (London )
2041-1723
22 February 2018
22 February 2018
2018
: 9
###### Affiliations
[1 ]ISNI 0000 0004 1936 8948, GRID grid.4991.5, Rudolf Peierls Centre for Theoretical Physics, , University of Oxford, ; Oxford, OX1 3NP UK
[2 ]ISNI 0000 0004 1936 8948, GRID grid.4991.5, Systems Biology DTC, , University of Oxford, ; Oxford, OX1 3QU UK
[3 ]GRID grid.448933.1, International Centre for Applied Mathematics and Computational Bioengineering, Department of Mathematics and Natural Sciences, , Gulf University for Science and Technology, ; P.O. Box 7207, Hawally 32093, Mubarak Al-Abdullah, Kuwait
###### Article
3101
10.1038/s41467-018-03101-6
5823903
29472533