Blog
About

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

      Read this article at

      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.

          Related collections

          Most cited references 25

          • Record: found
          • Abstract: not found
          • Article: not found

          On the Complexity of Finite Sequences

           A. Lempel,  J Ziv (1976)
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Fast folding and comparison of RNA secondary structures

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              A formal theory of inductive inference. Part I

                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
                © The Author(s) 2018

                Open Access 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/.

                Categories
                Article
                Custom metadata
                © The Author(s) 2018

                Uncategorized

                Comments

                Comment on this article