TY - JOUR

T1 - Input-output maps are strongly biased towards simple outputs

AU - Dingle, Kamaludin

AU - Camargo, Chico Q.

AU - Louis, Ard A.

N1 - Publisher Copyright:
© 2018 The Author(s).

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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)K(x) of that output. These input-output maps are biased towards simplicity. We derive an upper bound P(x)2K(x)-b2- A K(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.

AB - 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)K(x) of that output. These input-output maps are biased towards simplicity. We derive an upper bound P(x)2K(x)-b2- A K(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.

UR - http://www.scopus.com/inward/record.url?scp=85042555212&partnerID=8YFLogxK

U2 - 10.1038/s41467-018-03101-6

DO - 10.1038/s41467-018-03101-6

M3 - Article

C2 - 29472533

AN - SCOPUS:85042555212

SN - 2041-1723

VL - 9

JO - Nature Communications

JF - Nature Communications

IS - 1

M1 - 761

ER -