,

# Exploring simplicity bias in 1D dynamical systems

Kamaludin Dingle1,2, Mohammad Alaskandarani1, Boumediene Hamzi3,4, Ard A.
Louis2 1Centre for Applied Mathematics and Bioinformatics, Department of
Mathematics and Natural Sciences, Gulf University for Science and Technology,
Kuwait<EMAIL_ADDRESS>2Rudolf Peierls Centre for Theoretical Physics,
University of Oxford, Parks Road, Oxford, OX1 3PU, UK
<EMAIL_ADDRESS>3 Department of Computing and Mathematical
Sciences, Caltech, CA, USA.  4 The Alan Turing Institute, London, UK.
<EMAIL_ADDRESS>
###### Abstract.

Arguments inspired by algorithmic information theory predict an inverse
relation between the probability and complexity of output patterns in a wide
range of input-output maps. This phenomenon is known as _simplicity bias_. By
viewing the parameters of dynamical systems as inputs, and resulting
(digitised) trajectories as outputs, we study simplicity bias in the logistic
map, Gauss map, sine map, Bernoulli map, and tent map. We find that the
logistic map, Gauss map, and sine map all exhibit simplicity bias upon
sampling of map initial values and parameter values, but the Bernoulli map and
tent map do not. The simplicity bias upper bound on output pattern probability
is used to make _a priori_ predictions for the probability of output patterns.
In some cases, the predictions are surprisingly accurate, given that almost no
details of the underlying dynamical systems are assumed. More generally, we
argue that studying probability-complexity relationships may be a useful tool
in studying patterns in dynamical systems.

_Keywords:_ Dynamical systems; algorithmic probability; simplicity bias; time
series; machine learning

##  1\. Introduction

Predicting the behaviour and trajectories of dynamical systems is a research
goal relevant to many fields, including in financial, meteorological, medical,
and numerous other applications. Such predictions often rest on a detailed
analysis of the underlying model, but recent years have seen machine learning
advances provide powerful tools for the prediction and analysis of physical
phenomena, including dynamical systems. These machine learning predictions
rely on data observations rather than details of the model [1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,
27, 28, 29, 30, 31, 32, 33, 34].

An open and important question, then, is the extent to which machine learning
methods are applicable in dynamical systems problems, and what kinds of
limitations or advantages this relatively novel approach may have. Since
information theory and machine learning are inextricably linked and have even
been referred to as “two sides of the same coin” [35], one perspective on
these questions is to consider whether computation and information processing
— fundamental components of machine learning — themselves might have limits of
applicability, or in some other way constrain or inform dynamical behaviours.

Some fascinating examples of such limits are known in relation to
uncomputability of trajectories, meaning that some properties of dynamical
trajectories may not be possible to calculate, even in principle. In a seminal
paper, Moore [36] proved that the motion of a single particle in a potential
can (in some specific settings) be sufficiently complex as to simulate a
Turing machine, and thereby yield trajectories with uncomputable quantitative
properties. More recently, Watson et al. [37] proved for an example many-body
system that even if the exact initial values of all system parameters were
known, the renormalisaton group trajectory and resultant fixed point is
impossible to predict. This kind of unpredictability is stronger than the
unpredictability of (merely) chaotic dynamics, in which the limiting factor is
the accuracy with which initial conditions can be measured. See also Wolfram
[38, 39], Svozil [40], Lloyd [41], and Aguirre et al. [42] for more discussion
of (un)computability and (un)predictability in physical systems. Naturally, if
the dynamics of some system cannot be computed even in principle, machine
learning approaches to prediction in these settings will by definition also be
severely limited.

As another potential limitation of machine learning methods for the analysis
of dynamical systems, also derived from theoretical computer science, consider
the work of Cubitt et al. [43] who showed that extracting dynamical equations
from data is NP-hard. This means that there is no efficient way to do this in
general (assuming that $P\neq NP$, as is widely believed). How significant a
limitation this is in practice is debatable, because as they note, the
experimental datasets we typically encounter in practice seem to be fairly
easy to analyse (while the reason for this is an open question). Regardless,
the findings illustrate how fundamental limitations, derived from computer
science, may shed light on challenges which face machine learning methods.

These intriguing studies cited above motivate more exploration of the
application of theoretical computer science to physics and dynamics [44]. With
this broader goal in mind, we consider here another branch of theoretical
computer science, _algorithmic information theory_ [45, 46, 47] (AIT), and
specifically _algorithmic probability_ , and how arguments inspired by these
might facilitate the prediction or at least bounding the behaviour of
dynamical systems.

In recent years several studies of _simplicity bias_ have been made in input-
output maps, in which a general inverse relationship between the complexity of
outputs and their respective probabilities has been observed [48, 49]. More
specifically, using arguments based on AIT an upper bound on the probability
$P(x)$ of observing output pattern $x$ was presented [48], with the bound
depending on the estimated Kolmogorov complexity of $x$. The upper bound
implies that complex output patterns must have low probabilities, while high
probability outputs must be simple. Example systems where simplicity bias has
been observed include RNA structures [48, 50], differential equation solutions
[48], finite state transducers [49], time series patterns in natural data
[51], natural protein structures [52], among others.

There may also be deep connections between deep neural networks (DNNs) and
_simplicity bias_. Indeed, upon random sampling of parameters, DNNs exhibit an
exponential bias towards functions with low complexity [53, 54, 55]. This
property implies that they can learn Kolmogorov simple data fairly well, but
will not generalise well on complex data. Interestingly, by changing the
initialization over parameters towards a more artefactual chaotic regime of
DNNs, this simplicity bias becomes weaker [56]. It has been recently shown
that in this regime, DNNs no longer generalise well on both simple and complex
data [57], and tend to overfit. This is not unexpected, because DNNs are
highly expressive, and classical bias-variance arguments suggest that they
should be highly prone to overfitting. The big question is why standard DNNs
don’t fall prey to this problem. It was argued that the Occam’s razor like
_simplicity bias_ toward simple functions observed in standard DNNs
compensates the exponential growth of the number of possible functions with
complexity, and that this compensation explains why such DNNs can be highly
expressive without overfitting [57]. These principles imply that if a
dynamical system exhibits some form of simplicity bias then the inbuilt
Occam’s razor inductive bias of DNNs should make it much easier to learn by
DNNs than in the opposite case where the dynamical system does not have
simplicity bias.

A full understanding of exactly which systems will, and will not, show
simplicity bias is still lacking, but the phenomenon is expected to appear in
a wide class of input-output maps, under fairly general conditions. Some of
these conditions were suggested in ref. [48], including (1) that the number of
inputs should be much larger than the number of outputs, (2) the number of
outputs should be large, and (3) that the map should be ‘simple’ (technically
of $O(1)$ complexity) to prevent the map itself from dominating over inputs in
defining output patterns. Indeed, if an arbitrarily complex map was permitted,
outputs could have arbitrary complexities and probabilities, and thereby
remove any connection between probability and complexity. Finally (4), because
many AIT applications rely on approximations of Kolmogorov complexity via
standard lossless compression algorithms [58, 59] (but see [60, 61] for a
fundamentally different approach), another condition proposed is that the map
should not generate pseudo-random outputs like $\pi=3.1415...$ which standard
compressors cannot handle effectively. The presence of such outputs may yield
high probability outputs which appear ‘complex’ hence apparently violating
simplicity bias, but which are in fact simple.

To explore further the presence of simplicity bias in dynamical systems and
physics, and also in maps which test the boundaries of the conditions for
simplicity bias described above, we examine the output trajectories of a
selection of 1D maps from chaos theory, namely the logistic map, the Gauss
(“mouse”) map, the sine map, the Bernoulli map, and the tent map. Starting
with its popularisation by Robert May [62] in the 1970’s, the logistic map has
been heavily studied. The map is a textbook example of a simple system which
can produce simple, complex, and chaotic patterns via iterations of the map
[63]. This map is related to a very wide range of nonlinear models with
applications in epidemiology, economics, physics, time series, etc. [64]. Due
to the popularity of the logistic map, and because its trajectory outputs can
depict simple as well as complex, chaotic, and even pseudo-random patterns, we
focus primarily on the logistic map, but we also analyse the other mentioned
maps.

Although not restricted to studying binary strings, most AIT results are
framed in the context of binary strings and hence applications are easier in
the same framework. Thus in this work we will study simplicity bias in
digitised binary trajectories of these example 1D dynamical systems. Our main
conclusions are that simplicity bias appears the logistic map, the Gauss
(“mouse”) map, and the sine map, and hence we suggest that simplicity bias may
also appear in natural dynamical systems more generally.

##  2\. Background and problem set up

###  2.1. Background theory and pertinent results

####  2.1.1. AIT and Kolmogorov complexity

We give some basic background regarding AIT now, and describe simplicity bias
in more detail. Note that the current work will not involve detailed AIT or
related theory, so we only give a brief survey of relevant results without
giving many formal details here. There are many standard texts which the
interested reader can refer to if needed, e.g., refs. [65, 66, 67, 68].

Within computer science, _algorithmic information theory_ [45, 46, 47] (AIT)
directly connects computation, computability theory, and information theory.
The central quantity of AIT is _Kolmogorov complexity_ , $K(x)$, which
measures the complexity of an individual object $x$ as the amount of
information required to describe or generate $x$. $K(x)$ is more technically
defined as the length of a shortest program which runs on an (optimal prefix)
_universal Turing machine_ (UTM) [69], generates $x$, and halts. More
formally, the Kolmogorov complexity $K_{U}(x)$ of a string $x$ with respect to
$U$, is defined [45, 46, 47] as

$K_{U}(x)=\min_{p}\\{|p|:U(p)=x\\}$ (1)

where $p$ is a binary program for a prefix optimal UTM $U$, and $|p|$
indicates the length of the program $p$ in bits. Due to the invariance theorem
[65] for any two optimal UTMs $U$ and $V$, $K_{U}(x)=K_{V}(x)+O(1)$ so that
the complexity of $x$ is independent of the machine, up to additive constants.
Hence we conventionally drop the subscript $U$ in $K_{U}(x)$, and speak of
‘the’ Kolmogorov complexity $K(x)$. Informally, $K(x)$ can be defined as the
length of a shortest program that produces $x$, or simply as the size in bits
of the compressed version of $x$ (assuming a perfect compressor). If $x$
contains repeating patterns like $x=1010101010101010$ then it is easy to
compress, and hence $K(x)$ will be small. On the other hand, a randomly
generated bit string of length $n$ is highly unlikely to contain any
significant patterns, and hence can only be described via specifying each bit
separately without any compression, so that $K(x)\approx n$ bits. Other more
expressive names for $K(x)$ are _descriptional complexity_ , _algorithmic
complexity_ , and _program-size complexity_ , each of which highlight the idea
that $K(x)$ is measuring the amount of information to describe or generate $x$
precisely and unambiguously. Note that Shannon information and Kolmogorov
complexity are related [70], but differ fundamentally in that Shannon
information quantifies the information or complexity of a random source, while
Kolmogorov complexity quantifies the information of individual sequences or
objects.

An increasing number of studies show that AIT and Kolmogorov complexity can be
successfully applied in physics, including thermodynamics [71, 72, 73, 74],
quantum physics [75], and entropy estimation [76, 77]. Further, applications
to biology [78, 52, 79], other natural sciences [80], and engineering, are
also numerous [81, 65, 82].

####  2.1.2. The coding theorem and algorithmic probability

An important result in AIT is Levin’s [83] coding theorem, establishing a
fundamental connection between $K(x)$ and probability predictions.
Mathematically, it states that

$P(x)=2^{-K(x)+O(1)}$ (2)

where $P(x)$ is the probability that an output $x$ is generated by a (prefix
optimal) UTM fed with a random binary program. Thus, high complexity outputs
have exponentially low probability, and simple outputs must have high
probability. This is a profound result which links notions of data compression
and probability in a direct way. $P(x)$ is also known as the _algorithmic
probability_ of $x$. Given the broad reaching and striking nature of this
theorem, it is somewhat surprising that it is not more widely studied in the
natural sciences. The reason in part for this inattention is that AIT results
are often difficult to apply directly in real-world contexts, due to a number
of issues including the fact that $K(x)$ is formally uncomputable and the
ubiquitous use of UTMs.

####  2.1.3. The simplicity bias bound

Coding theorem-like behaviour in real-world input-output maps has been studied
recently, leading to the observation of a phenomenon called _simplicity bias_
[48] (see also ref. [84]). Simplicity bias is captured mathematically as

$P(x)\leq 2^{-a\tilde{K}(x)-b}$ (3)

where $P(x)$ is the (computable) probability of observing output $x$ on random
choice of inputs, and $\tilde{K}(x)$ is the approximate Kolmogorov complexity
of the output $x$: complex outputs from input-output maps have lower
probabilities, and high probability outputs are simpler. The constants $a>0$
and $b$ can be fit with little sampling and often even predicted without
recourse to sampling [48]. We will assume that $b=0$ in Eq. (3) throughout
this work, which is a default assumption as argued and discussed in ref. [48].
There is also a conditional version of the simplicity bias equation [85].

The ways in which simplicity bias differs from Levin’s coding theorem include
that it does not assume UTMs, uses approximations of complexities, and for
many outputs $P(x)\ll 2^{-K(x)}$. Hence the abundance of low complexity, low
probability outputs [49, 86] is a signature of simplicity bias.

####  2.1.4. Estimating pattern complexity

To estimate complexity, we follow ref. [48] and use

$C_{LZ}(x)=\begin{cases}\log_{2}(n),&\text{$x=0^{n}$ or $1^{n}$}\\\
\log_{2}(n)[N_{w}(x_{1}...x_{n})+N_{w}(x_{n}...x_{1})]/2,&\text{otherwise}\end{cases}$
(4)

where $N_{w}(x)$ comes from the 1976 Lempel and Ziv complexity measure [58],
and where the simplest strings $0^{n}$ and $1^{n}$ are separated out because
$N_{w}(x)$ assigns complexity $K=1$ to the string 0 or 1, but complexity 2 to
$0^{n}$ or $1^{n}$ for $n\geq 2$, whereas the true Kolmogorov complexity of
such a trivial string actually scales as $\log_{2}(n)$ for typical $n$,
because one only needs to encode $n$. Having said that, the minimum possible
value is $K(x)\approx 0$ for a simple set, and so e.g. for binary strings of
length $n$ we can expect $0\leq K(x)\leq n$ bits. Because for a random string
of length $n$ the value $C_{LZ}(x)$ is often much larger than $n$, especially
for short strings, we scale the complexity so that $a$ in Eq. (3) is set to
$a=1$ via

$\tilde{K}(x)=\log_{2}(M)\cdot\frac{C_{LZ}(x)-\min_{x}(C_{LZ})}{\max_{x}(C_{LZ})-\min_{x}(C_{LZ})}$
(5)

where $M$ is the maximum possible number of output patterns in the system, and
the min and max complexities are over all strings $x$ which the map can
generate. $\tilde{K}(x)$ is the approximation to Kolmogorov complexity that we
use throughout. This scaling results in $0\leq\tilde{K}(x)\leq n$ which is the
desirable range of values.

Figure 1. An example of a real-valued (orange) and digitised (blue) trajectory
of the logistic map, with $\mu=3.8$ and $x_{0}=0.1$. The discretisation is
defined by writing 1 if $x_{k}\geq 0.5$ and 0 otherwise, resulting in the
pattern $x=$ 0101011011111011010110111 which has length $n=$ 25 bits.

###  2.2. Digitised map trajectories

The AIT coding theorem is framed in terms of random inputs or ‘programs’ and
resultant output strings or patterns. The core idea of the simplicity bias
bound is that for a large range of systems, uniformly sampling input parameter
values (‘programs’) yields an exponential variation in output pattern
probabilities, with high probability patterns having low complexities. While
dynamical systems may not appear to fit this input-output framework, they can
be viewed as input-output functions if the initial values and parameters are
considered input ‘programs’ which are then computed to generate ‘output’
dynamical system trajectories. Because output pattern complexities and
probabilities are more easily calculated if outputs are binary strings (and as
above, AIT is mainly framed in terms of binary strings), we will digitise the
real-valued trajectories into binary strings.

To illustrate this input-output framework, consider binary sequence
trajectories resulting from digitised realisations of the logistic map

$x_{k+1}=\mu x_{k}(1-x_{k})$ (6)

where the inputs are the pair of values $x_{0}\in$(0.0, 1.0) and $\mu\in$
(0.0, 4.0]. For the outputs, the map is first iterated to obtain a sequence of
$n$ real values $x_{1},x_{2},x_{3},\dots,x_{n}$ in [0,1]. Similar to the field
of symbolic dynamics [87], the real-valued trajectory is digitised to become a
binary string output sequence $x$ by applying a threshold, and writing 1 if
$x_{k}\geq 0.5$ and 0 otherwise [88]. Hence a binary sequence output $x$ of
$n$ bits is generated for each input pair $\mu$ and $x_{0}$.

By way of example, consider choosing $\mu=3.8$ and $x_{0}=0.1$ with $n=25$,
then from iterating Eq. (6) with $k=1,2,...,25$ we obtain the real-valued
trajectory

$x_{1},x_{2},\dots,x_{25}=0.34,0.86,\dots,0.25,0.72,0.77,0.67$

which after digitisation becomes the binary string

$x=0101011011111011010110111$

Figure 1 illustrates the trajectory and digitisation procedure. The choice of
$n$ is a balance between being long enough that many different patterns can
emerge, and short enough that decent frequency and probability estimates can
be made without the need for excessive sampling. Different $\mu$ and $x_{0}$
inputs can yield different binary strings $x\in\\{0,1\\}^{n}$.

Note that throughout the paper, we will ignore the first 50 iterations of a
map, so as to discard the transient dynamics of the iterated maps. This step
of ignoring the initial iterations is common practice [89].

Figure 2. Bifurcation diagram for the logistic map. In (a), the diagram for
parameters $\mu\in$(0, 4.0]; and in (b), for values $\mu\in$(2.9, 4.0]. The
value 0.5 has been highlighted in red, to indicate the threshold cut off used
to digitise trajectories by a value o $0$ if the output is below the
threshold, and a value of $1$ if it is greater than or equal to the threshold.

##  3\. Results

###  3.1. Logistic map

The logistic map in Eq. (6) is possibly the best known and most iconic 1D maps
studied in dynamical systems and chaos theory. To our knowledge, there have
not been many studies of the complexity of digitised trajectories of the
logistic map. A notable exception is the work by Kaspar and Schuster [90] who
also studied the estimated complexity of resulting binary string trajectories.
However their work was fundamentally different in that it was not concerned
with simplicity bias or in estimating the probability of different outputs.

####  3.1.1. Parameter intervals

The intervals $x_{0}\in$(0.0, 1.0) and $\mu\in(0.0,4.0]$ are standard ranges
in which the logistic map is studied and it can be shown [89], for example,
that for $\mu>4.0$ almost all trajectories are not confined to [0,1];
similarly if $x_{0}\notin(0,1)$ the behaviour can be unbounded or trivial. For
some large values of $\mu$ (e.g., $\mu=4.0$), almost all initial values
$x_{0}$ yield complex and chaotic outputs [63], and the distribution over
digitised trajectories is roughly uniform, with little bias. Note that we use
the word ‘bias’ to describe a strongly non-uniform distribution of the
probability to obtain a given binary string output.

In Figure 2(a) the bifurcation diagram of the logistic map is shown, in which
for different values of $\mu$ the asymptotic $x_{k}$ values are depicted. The
diagram shows fixed points, oscillations, and non-period behaviour. Also added
is the value $0.5$ as a red line, highlighting the digitising threshold. It is
known [63] that if $\mu\in[0.0,1.0]$, then the trajectories tend to 0. Because
we truncate at 0.5, therefore the corresponding binary string would be
$x=...0000$. If $\mu\in(1.0,2.0]$ then the trajectories tend to $1-(1/\mu)$,
which means that we expect to see binary strings $x=...0000$. For
$\mu\in(2.0,3.0]$, the resulting pattern would be or $x=...1111$ because
$1-(1/\mu)$ is greater than 0.5. For $\mu$ from 3.0 to $\approx$3.3, we still
expect $x=...1111$ because although the first bifurcation appears at
$\mu=$3.0, and oscillations with period two begin, until about 3.3 both values
of the oscillations are larger than 0.5. Figure 2(b) shows the same
bifurcation diagram, but zoomed in on the larger values of $\mu$. From about
3.3 to about 3.5, oscillations between two or four values appear, and larger
values of $\mu$ can yield oscillation periods of 8, 16, etc., which will yield
patterns such as $x=0101...$. Chaotic trajectories do not occur until [63]
$\mu\geq 3.56994567...\approx 3.57$ (https://oeis.org/A098587), and so the
$\mu$ interval 3.0 to about 3.5699 contains period-doubling bifurcations, in
which oscillations of exponentially increasing frequency occur but no truly
chaotic trajectories. Finally, for $\mu$ between $\approx$3.57 and 4.0, more
complex and chaotic patterns can emerge, but also ‘islands’ of stability
appear in this interval, as can be observed in Figure 2(b).

In our numerical simulations, we will separately investigate various intervals
for $\mu$, namely $\mu$ sampled uniformly from (0, 4.0], [3.0, 4.0], [3.57,
4.0], and finally also fixing $\mu=4.0$. The motivation for choosing these
intervals is as follows: Given that the interval $\mu\in(0.0,4.0]$ is the
standard range in which the map is studied, the most ‘natural’ sampling
strategy is to sample uniformly across this interval. As for choosing
intervals [3.0, 4.0] and [3.57, 4.0], these are interesting test cases because
we can expect to see complex patterns appearing more frequently in these
intervals. Finally, when fixing $\mu=4.0$ most trajectories will be highly
complex, and so we might expect simplicity bias to disappear.

####  3.1.2. Connection of simplicity and probability

Reflecting on the bifurcation diagram and above related comments, it is easily
seen that by uniformly sampling $\mu$ from (0.0, 4.0], some simple binary
patterns will have high probability, and highly complex patterns will have low
probability just because most of the interval (0.0, 4.0] yields fixed points
or low period oscillations. Hence, some general form of bias towards
simplicity is expected for the logistic map. However, what is not _a priori_
obvious is whether or to what extend the simplicity bias bound in Eq. (3) will
be followed or have predictive value.

Figure 3. Simplicity bias in the digitised logistic map from random samples
with $x_{0}\in(0,1)$ and $\mu$ sampled in different intervals. Each blue
datapoint corresponds to a different binary digitised trajectory $x$ of length
25 bits. The black line is the upper bound prediction of Eq. (3). (a) Clear
simplicity bias for $\mu\in$(0, 4.0] with $P(x)$ closely following the upper
bound, except for low frequency and high complexity outputs which suffer from
increased sampling noise; (b) simplicity bias is still present for
$\mu\in$[3.0, 4.0]; (c) the distribution of $P(x)$ becomes more flat (less
biased) and simplicity bias is much less clear when $\mu\in$[3.57, 4.0] due to
constraining the sampling to $\mu$-regions more likely to show chaos; (d) the
distribution of $P(x)$ is roughly uniform when using $\mu=4.0$, with almost no
bias, and hence no possibility of simplicity bias.

####  3.1.3. Simplicity bias appears when bias appears

Following the protocol for generating binary strings via logistic map
trajectories described above, we now examine the probability $P(x)$ that the
digitised trajectory $x$ is produced on random sampling of input parameters
$\mu$ and $x_{0}$, done here with $10^{6}$ samples over uniformly chosen
random parameters. Using Eq. (3), we can make an _a-priori_ prediction for the
upper bound decay upon sampling of the input parameters. (Recall that we
ignore the first 50 iterations of the map, in order to exclude the transient
dynamics.)

Figure 3(a) shows that the upper bound prediction (black line) agrees
remarkably well with the probability and complexity data for different binary
string output (blue dots); we see that the logistic map displays simplicity
bias when uniform sampling $\mu\in(0.0,4.0]$, such that high probability
outputs have low complexities, and complex outputs have low probability. The
gradient prediction ($a=1$) of the black line used no information about the
map, except that we assumed that almost all $2^{n}$ outputs of length $n$ bits
are realisable. Note that many output strings fall below the upper bound
prediction as we expected from earlier studies [48, 86], but nonetheless it is
known that randomly generated outputs tend to be close to the bound [49]. Put
differently, even though many output strings (blue dots) appear to be far
below the bound, most of the probability mass for each complexity value is
concentrated close to the bound. Thus, this simple bound predicts $P(x)$ quite
accurately by using the complexity values of output strings yet while
otherwise completely ignoring the details of the underlying dynamical system.

In Figure 3(b) we make a similar plot to panel (a) except that we restrict the
sampling to $\mu\in[3.0,4.0]$. The qualitative pattern in (b) is similar to
(a), although simplicity bias is slightly less clear than in (a). For Figure
3(c) the sampling interval was chosen so that $\mu\in[3.57,4.0]$ which is the
region containing some truly chaotic trajectories [89]. Both bias and
simplicity bias are less clear in this plot. In Figure 3(d) a plot is given in
which $\mu$ is no longer sampled, but is fixed at $\mu=4.0$, so that almost
all $x_{0}$ values yield chaotic trajectories. As expected, there is very
little bias in the distribution, i.e. the distribution of $P(x)$ is roughly
uniform, and hence no simplicity bias can be observed. Figure 3(d) still shows
some very simple strings, which can be understood from the fact that
$x_{i}\approx 0$ $\Rightarrow x_{i+j}\approx 0$ for $j\approx 1$ even if the
trajectories may become much more complex for $j\gg 1$. In other words, if the
trajectory reaches a value close to zero, then it tends to stay close to zero
for several iterations. These initial short trajectories with many 0s will
have very low complexity.

As argued above, the fact that simple patterns occur with high probability
when sampling $\mu$ from (0.0, 4.0] is not in itself remarkable, and can be
rationalised from the bifurcation diagram. However, what is noteworthy in our
investigation is that we don’t just see a vague general inverse relation
between complexity and probability (as the preceding discussion might
predict), but rather that we see an exponential decay in probability with
linearly increasing complexity which follows the upper bound of Eq. (3) quite
closely.

See the Appendix A for an illustration of the effects of using the different
values of $n$.

Figure 4. The distribution $P(\tilde{K}(x)=r)$ of output complexity values,
with $x_{0}\in(0,1)$ and $\mu$ sampled from different intervals. (a) A roughly
uniform complexity distribution for $\mu\in$(0.0, 4.0], with some bias towards
lower complexities; (b) Close to uniform distribution of complexities for
$\mu\in$[3.0, 4.0]; (c) the distribution leans to higher complexities when
$\mu\in$[3.57, 4.0]; (d) the distribution is biased to higher complexities
values when $\mu=4.0$; (e) for comparison, purely random binary strings of
length 25 bits were generated. The distributions of complexity values in (d)
and (e) are very similar, but (a-c) show distinct differences. Calculating and
comparing $P(K)$ is an efficient way of checking how simplicity biased a map
is.

####  3.1.4. Distribution of complexities

By itself, simplicity bias does not necessarily imply that the distribution of
complexity values, $P(K(x)=r)$, will be skewed towards low complexities
values. Rather, simplicity bias means that the individual probability of some
simple strings will be higher than that of more complex strings. Because the
probability of observing a given complexity $r$ depends on the product of the
number of strings of complexity $r$ and their individual probabilities, the
distribution $P(K(x)=r)$ may in fact peak at high complexities, or low
complexities, or have no peak at all possibly.

To investigate this distribution in the logistic map, in Figure 4 we plot the
distribution of complexities for the different sampling intervals of $\mu$. As
can be seen in Figure 4(a), when sampling from [0.0, 4.0] there is a bias
towards lower complexities. As for (b), when $\mu$ is sampled from [3.0, 4.0]
the distribution of complexities is roughly uniform (at least on a log scale).
In Figure 4(c), the distribution is also somewhat uniform but peaks around
medium complexity values. In (d), there is a bias towards higher complexity
values. For comparison, in (e) we also plot the distribution of complexities
resulting from sampling purely random binary strings, and this distribution is
very similar to that in (d) obtained when $\mu=4.0$. It is noteworthy that in
some of these cases, while there is some evidence of bias toward higher or
lower complexities, the distributions still display spread and are not
narrowly peaked (at least on a log scale). We note that if the logistic map
produced binary output strings with a uniform probability over strings, in
theory the frequency would exponentially with complexity $r$, however, for
Lempel-Ziv complexity with short strings, the distribution is not quite
exponential, see [48, 57].

The appearance of a distribution that is much less peaked towards high
complexity than that of randomly chosen strings can be rationalised from AIT
arguments. To first order there are $\sim 2^{r}$ strings of complexity $r$,
each with probability $\sim 2^{-r}$, such that the product $2^{r}2^{-r}=O(1)$
is independent of $r$, and presumably uniform. For prefix complexity, the
number of strings with complexity $r$ is slightly less than $2^{r}$, and hence
for a prefix UTM the distribution would be biased to lower $r$ values to some
extent. Nonetheless, the brief rough argument outlined is still valid as a
first order approximation for distributions with large spread, as we see in
Figure 4. See also ref. [52] for similar arguments and results regarding the
distribution of complexities in a biological setting, as well as ref. [57] for
the setting of machine learning.

Finally, we note that in practice, far fewer samples are needed to produce a
$P(\tilde{K}(x)=r)$ distribution than a $P(x)$ distribution, because many
strings have the same $\tilde{K}$. Comparing the sampled distribution to a
null-model of random strings may be the quickest and easiest way to diagnose
simplicity bias in a dynamical system.

####  3.1.5. Complex and pseudo-random outputs

The occurrence of complex patterns may prompt a question: since the logistic
map in Eq. (6) is itself simple with low Kolmogorov complexity, it might be
supposed that any output $x$ it generates should be simple as well. So, how
can we obtain large variations in complexity which would lead to large
variations in probability? Or are all the apparently complex outputs merely
pseudo-random patterns? We can address these analytically via bounding the
complexity $K(x)$ of a discretised trajectory written as an $n$-bit binary
string $x$ using the following inequality

$K(x)\leq K(\text{logistic map})+K(\mu,x_{0})+K(n)+O(1)$ (7)

This bound follows from the fact that any $x$ can be described precisely by
first describing: (a) the logistic map function in Eq. (6) with only a few
bits because $K(\text{logistic map})$=$O(1)$ bits, (b) a pair of values $\mu$
and $x_{0}$ which yield $x$ with $K(\mu,x_{0})$ bits, and (c) the length of
the string (i.e., the number of iterations to perform) via $n$, which is at
most $\log_{2}(n)$ bits (up to loglog terms). From this upper bound, we see
that if $\mu$ and $x_{0}$ are simple values with short descriptions, then
$K(x)\ll n$ so that $x$ must be simple. However, because $\mu$ and $x_{0}$ are
(truncated) real numbers randomly chosen from their intervals, they need not
be simple — rather the opposite — because almost all decimal numbers sampled
here are given to $d$ decimal places, and so will have high complexity values
of $\sim\log_{2}(10)d$ bits. Therefore, outputs need not be simple just
because the map is simple, due to the presence of the complexity of the inputs
in Eq. (7). Nor are all outputs merely pseudo-random patterns. Indeed, this
argument accords with the fact that in Figure 3 we see that very many outputs
$x$ are realised, most of which must be (truly) complex because it is well
known from AIT that almost all strings of length $n$ are complex and only
relatively few are simple.

Extending the preceding discussion on Eq. (7), it is also interesting to ask
if there are simple input parameters which generate high entropy pseudo-random
outputs. Indeed there are, for example if $\mu=4.0$ then almost all $x_{0}$
lead to chaotic trajectories including some simple initial values like
$x_{0}=1/3$ which can be described with only a few bits, so that
$K(\mu,x_{0})=O(1)$ and so $K(x)\leq\log_{2}(n)+O(1)$ (up to additive loglog
terms), but at the same time $\tilde{K}(x)\approx n$ bits because the Lempel-
Ziv complexity measure cannot compress pseudo-random strings.

On reflection, these pseudo-random strings with $K(x)\ll\tilde{K}(x)$ must be
‘rare’ in the space, and not have individually high probability, otherwise we
would not see simplicity bias, or at least see many points strongly violating
of the upper bound in Figure 3(a), which we do not.

####  3.1.6. Pre-chaotic regime

As discussed above, when $\mu>3.5699...$ some trajectories can be chaotic, but
there are also intermittent ‘islands’ of stability, and in general the pattern
of types of behaviour in the region 3.57 to 4.0 is intricate and complicated.
However, in the region $\mu\in[0.0,3.5699]$ the types of behaviour are more
straightforward, with progressive period-doubling bifurcations but no true
chaos. Feigenbaum [91, 92] famously showed that the distance between
successive bifurcations eventually decreases exponentially, as
$\mu_{q+1}-\mu_{q}\approx 2.069/4.669^{q}$ [89], where $\mu_{q}$ is the value
of the $q^{th}$ bifurcation.

Because this interval $\mu\in[0.0,3.5699]$ is relatively easy to understand,
and to see if simplicity bias appears even without chaos, we also generated a
complexity-probability plot for $\mu\in[0.0,3.5699]$ uniformly sampled: Figure
5(a) shows the decay in probability with increasing complexity. As is
apparent, there are fewer patterns (blue dots) which is because we are
restricting the possible space of patterns by restricting to this interval of
$\mu$. We see that some simplicity bias is observed, but the bound is less
clearly followed as compared to the when sampling across [0.0, 4.0]. For
example, the upper bound on the data points’ decay is less clearly linear.

To get a better understanding of the complexity of trajectories, we can
find111WolframAlpha (https://www.wolframalpha.com/), using command “logistic
map for r=[//number:3.4//] and x=[//number:0.2//]” the oscillation periods for
some chosen values of $\mu$: With $\mu=3.4$, period 2; $\mu=3.5$, period 4;
$\mu=3.56$, period 8; $\mu=3.569$, period 32; $\mu=3.5699$, period 128. So for
the sampled interval [0.0, 3.5699] the highest period is 128. Because we use
$n=25$, any pattern with period 32 or more will not appear as periodic,
because $n$ needs to be large for the periodicity to become plain. From this
brief analysis, we can see how the low-probability and high-complexity
patterns have appeared in Figure 5(a). In conclusion, some simplicity bias is
observed for the interval $\mu\in[0.0,3.5699]$, but it is not as pronounced as
for sampling $\mu\in[0.0,4.0]$, which is presumably due to the presence of
potentially more complex patterns in the interval 3.57 to 4.0.

Figure 5. Simplicity bias in (a) the logistic map with $\mu$ sampled in [0.0,
3.5699], which is the non-chaotic period doubling regime; (b) the Gauss map;
and (c) the sine map.

###  3.2. Gauss map (“mouse map”)

Moving on from the logistic map, we now explore simplicity bias in another 1D
map, namely the _Gauss map_ , which is also known as the _mouse map_ because
the bifurcation diagram is reminiscent of a mouse [93]. The equation defining
the dynamical system is

$x_{k+1}=e^{-\alpha x_{k}^{2}}+\beta$ (8)

The value $\alpha=7.5$ is chosen and will be fixed. For many values of
$\alpha$ the bifurcation diagram is not sufficiently complex as to yield many
varied trajectories; also the value 7.5 has been used previously [94]. The
value $\beta$ is the bifurcation parameter and the map is typically studied
[93, 95] with $\beta\in[-1.0,1.0]$ .

Similar to the logistic map example, we will sample initial values $x_{0}$ and
values of $\beta$, then ignore the first 50 iterations (due to transient
dynamics), and then digitise the real-valued trajectory to form binary string
outputs. Because iterations of Eq. (8) are not confined to [0.0, 1.0] and due
to the form of the bifurcation diagram [93], we will sample
$x_{0}\in[-0.5,0.5]$ uniformly. Also due to the form of the bifurcation
diagram, the digitisation threshold will be set at 0.2 (instead of 0.5, as it
was in the case of the logistic map). Changing the threshold is done merely to
avoid having too many trivial outputs of $x=000\dots 000$. As above, we will
use $n=25$.

In Figure 5(b), we see that there is clear simplicity bias in the Gauss map.
The slope of the decay follows the predicted black line very closely, but the
offset value $b$ is not well approximated by $b=0$. Nonetheless, there is
clear simplicity bias, similar to the logistic map case. Hence, we can predict
the relative log-probability of output strings with quite high accuracy.

###  3.3. Sine map

We now study simplicity bias in the _sine map_. Wolfram [96] described the
sine map

$x_{k+1}=\mu\sin(\pi\sqrt{x_{k}})$ (9)

and further displayed the bifurcation diagram for this map, which is broadly
similar to that of the logistic map, to illustrate Feigenbaum’s discovery of
universality. For this map, we sample $x_{0}\in[0.0,1.0]$ uniformly $10^{6}$
times, and return to the digitisation threshold of 0.5. The parameter $\mu$
will sampled uniformly from [0.0, 1.0]. As before, the first 50 iterates will
be ignored, and we will use $n=25$. Note that there is another form of the
sine map which is sometimes studied in dynamical systems [97, 98], in which
there is no square root on $x_{k}$.

Figure 5(c) shows the complexity-probability plot for the sine map, and
simplicity bias is also present here. However, the upper bound is less clearly
linear (on the log scale), and the black line prediction is not as closely
followed. Also noteworthy is that in the tail of the decay at higher
complexities, the upper bound appears to curve up slightly. It is not clear
why this happens.

###  3.4. Bernoulli map

Moving on to another prototypical chaotic map, the Bernoulli map (also known
as the _dyadic map_ , _bit shift map_ , _doubling map_ , or _sawtooth map_) is
defined via the equation

$x_{k+1}=(2x_{k}\mod 1)$ (10)

with $x_{0}\in(0.0,1.0)$. This map shows sensitive dependence on initial
conditions because the trajectories of two inputs $x_{0}$ and $y_{0}$ which
differ by $|x_{0}-y_{0}|\approx 0$ will eventually diverge for large enough
$k$.

Given that the Bernoulli map is also a 1D chaotic system with a simple ($O(1)$
complexity) map, it is interesting to ask whether it shows simplicity bias
like the logistic map and others do. A little reflection shows that this map
does not show simplicity bias nor bias, even for a digitised version. The
trajectory is defined by multiplying 2 by $x_{0}$ ignoring the integer part,
so if $x_{0}$ is a random real number then the trajectory will be random and
incompressible because $(2x_{0}\mod 1)$ will be another random number,
assuming that $x_{0}$ is defined to a large number of decimal places.
Multiplying a random number by 2 does not remove the randomness. Hence the
binary discretised trajectory sequence would look almost random, with small
and quickly decaying autocorrelation (see also Section 9.4 of ref. [66] for a
similar conclusion). For bias and simplicity bias, it is necessary for random
inputs to be able to lose a lot of their information and complexity (i.e.,
complex inputs must be able to produce simple outputs), but the Bernoulli map
does not allow this. Hence the behaviour of this map is similar to the
logistic map with $\mu=4.0$ in the sense that there is no bias and no
simplicity bias. Indeed, this similarity is quite natural due to the conjugacy
between the logistic map with $\mu=4.0$ and the Bernoulli (doubling) map. This
map does not have a bifurcation parameter $\mu$.

###  3.5. Tent map

The last map we look at is the _tent map_ , which is quite well known and
studied in dynamical systems research [63]. The iterated values follow the
function

$x_{k+1}=\begin{cases}2x_{k}&0\leq x_{k}\leq 0.5\\\ 2-2x_{k}&0.5<x_{k}\leq
1.0\end{cases}$

with $x_{k}\in[0.0,1.0]$, for $k=0,1,2,3,\dots$. This map does not have a
bifurcation parameter $\mu$. Despite being a 1D dynamical system, this map
does will not lead to strong bias in the distribution of digitised binary
string outputs $x$, and hence cannot possibly show simplicity bias.
Intuitively, this can be seen due to the fact that almost all values of
$x_{0}$ will yield complex paths, while simplicity bias arises typically when
most inputs lead to relatively simple paths. Indeed, because the tent map is
topologically conjugate to the logistic map [63] when $\mu=4.0$, and we saw
neither bias nor simplicity bias in the logistic map [63] when $\mu=4.0$, this
helps to understand the absence of simplicity bias in the tent map.

##  4\. Discussion

Arguments inspired by algorithmic information theory (AIT) predict that in
many input-output maps, there will be probabilistic bias with complex patterns
having exponentially low probabilities, and some simple patterns having high
probability; this phenomenon is known as _simplicity bias_ [48]. Here, we
numerically investigated the presence of simplicity bias in digitised
trajectories arising from iterations of the logistic map, Gauss map, sine map,
Bernoulli map, and tent map. By digitising the real-valued trajectories, we
studied the probability and complexity of the resulting binary strings. Our
main conclusions are that (i) we observe simplicity bias in the logistic map,
Gauss map, and sine map, and also that in some cases the probability of
resulting binary strings can be predicted _a priori_ with surprising accuracy;
and (ii) we do not observe simplicity bias in the trajectories of the
Bernoulli map and tent map, nor indeed any bias at all.

Due to the qualitatively different behaviours exhibited by the logistic map
for different $\mu$ values, we separately studied different regimes by
sampling $\mu$ from (0.0, 4.0], (3.0, 4.0], (3.57, 4.0] and also $\mu=4.0$. In
general, simplicity bias and upper bound prediction accuracy was higher for
$\mu$ sampled across the full range (0.0, 4.0] and decreased for smaller
ranges, until completely disappearing for $\mu=4.0$. The logistic map is
perhaps the most iconic example of a dynamical system in chaos theory, and has
been very extensively studied for decades. Here we report a novel finding
relating to this map, and one that is not (merely) a subtle higher-order
effect, but rather a strong effect related to order-of-magnitude variations in
pattern probability. This finding is also interesting given that we did not
necessarily expect to observe simplicity bias when outputs can be pseudo-
random (Cf. ref. [48]). It appears that in this map, pseudo-random outputs are
sufficiently rare that they do not cause strong violations of the simplicity
bias upper bound. Additionally, we found simplicity bias can be ‘tuned’ via
altering the $\mu$ interval: sampling from the full interval (0.0, 4.0] yields
a biased (low entropy) distribution over output strings along with simplicity
bias, while sampling from higher values of $\mu\approx 4.0$ yields low bias
(high entropy) distributions and little or no simplicity bias. While we
observe simplicity bias similar to that predicted by AIT arguments in some of
these maps, we want to clarify that we do not think that we have in any way
proven that these patterns are in fact directly linked to the AIT arguments.
For that much more work is needed. Nevertheless, we argue that studying
probability-complexity relationships, and looking for patterns such as
simplicity bias may be a fruitful perspective for dynamical systems research.

The motivations for this work were to explore new examples of simplicity bias
in physics and specifically dynamical systems, test the boundaries of which
types of maps show simplicity bias, and explore how information theory and
algorithmic probability can inform dynamical systems research. By extension,
this work expands on the project of investigating the interaction between
machine learning and dynamical systems because machine learning is intimately
connected to information theory and algorithmics. Indeed, it may be that
dynamical systems that are easy to learn, are precisely those that exhibit
some kind of simplicity bias which matches the inbuilt Occam’s razor like
inductive bias of DNNs [57].

A weakness of our probability predictions is that they only constitute an
upper bound on the probabilities, and for example Figure 3(a) shows that many
output trajectory patterns $x$ fall far below their respective upper bounds.
Following the hypothesis from [49, 86], these low-complexity low-probability
outputs are presumably patterns which the logistic map finds ‘hard’ to make,
yet are not intrinsically very complex. Further, the presence of these low-
complexity low-probability patterns may indicate the non-universal power of
the map [49]. A potential avenue for future work would be studying what types
of patterns occur far from the bound may, and possible approaches to improving
on their probability predictions [86].

The word “complexity” can take on many meanings [99, 100], and can be vague.
In this work we are precise about what we mean by complexity, which is
Kolmogorov complexity, and in practice using lossless compression methods
which is a standard and theoretically motivated approximation to the true
uncomputable quantity. Bialek et al. [101, 102] discuss complexity in relation
to time series, and argue that Kolmogorov complexity lacks in its intuitive
appeal for a measure of the complexity of these types of sequential patterns.
Many would agree that a series with rich complicated structure and long-range
correlations is truly complex, whereas a random string of bits is merely an
irregular and in a sense trivial pattern. In contrast, Kolmogorov complexity
assigns the highest complexity to such random strings, precisely because they
do not contain any correlations or structure. Having noted this, the
discussion does not directly bear upon our work, because we are not studying
‘complexity’ in a general sense or trying to argue for one or other metric.
Rather, we are studying specifically simplicity bias and AIT inspired
arguments as a mathematical framework for understanding probability and
dynamical systems. AIT allows one to make quantitative bounds and predictions
about various systems, as we illustrate here, regardless of whether or not the
term “complexity” is being used in it truest or most correct sense.

Mathematicians and physicists are fascinated by studying simple systems which
can exhibit complex patterns, even while they are not technically random. In
this context, Wolfram [39] investigated simple automata, and showed that some
have high levels of computing power, leading to his conjecture that many
natural systems can be Turing complete, i.e., that they can implement
arbitrary algorithms, and hence produce complex patterns. Despite this focus
on complexity, we observe in our work here that complexity is in a sense not
actually that common: Even though the logistic map is famous precisely due to
its ability to produce complex behaviour, within the space of possible
parameters, i.e., $\mu,x_{0}\in\mathcal{R}$ and even restricting to
$\mu\in(0.0,4.0]$ and $x_{0}\in(0,1)$, chaos and ‘complexity’ only occur
rarely (assuming uniform sampling of the parameter space). This observation
accords with the fact that while Wolfram highlighted some rule sets that
produce randomness, most of his automata rules sets do not produce complex
pseudo-random patterns [39]. Coe et al. [103] analytically studied the
question of when automata produce ‘random’ and complex dynamics, and also
found that relatively few are random.

The study of random dynamical systems — in which dynamical systems are
randomly perturbed in some way — is quite well established [104], including
specifically dynamical systems with additive noise [105]. While deterministic
dynamical systems have been studied due to their relevance to modelling
problems in e.g., ecology, physics, and economics, randomly perturbed dynamics
are also common in science and hence important to study, and arise naturally
in modelling physical systems (e.g., [106]). This motivates studying
simplicity bias also in such random dynamical systems in future work. As a
separate motivation, in the deterministic logistic map, many sampled $\mu$
values yield trajectories which quickly converge to fixed points or other
fairly trivial patterns. However, by introducing some small random noise these
trajectories may be prevented from converging into trivial patterns, and
therefore may show simplicity bias even while the deterministic counterpart
does not. One potential map to utilise would be the logistic map with small
additive noise, as studied by Sato et al. [107].

In this work we have used 1D maps including the logistic map as toy systems to
explore simplicity bias in dynamical systems. While our work has been an
empirical investigation, the connection between AIT and dynamical systems has
also received some earlier limited attention from an analytical perspective
(e.g., [108, 109, 110]). In future work it may be fruitful to investigate
which, if any, properties of the logistic (or other chaotic) map can be
predicted or bounded using the simplicity bias bound. That is, if we assume
that the simplicity bias bound holds, what other dynamical properties of the
map might follow from this? Even if these properties are already known, it
would still be insightful to see if they could be derived (perhaps more
simply) from AIT arguments. Further, the presence of simplicity bias in some
of the 1D map may lead to using the simplicity bias bound as a trajectory
prediction method. This is related to the _a priori_ prediction of natural
time series patterns attempted by Dingle et al. [51]. More generally,
exploring the use of arguments inspired by AIT in dynamical systems and chaos
research is an attractive and potentially fruitful research avenue.

Acknowledgments: This project has been partially supported by Gulf University
for Science and Technology, including by project code: ISG Case 9. We thank G.
Valle-Perez for valuable discussions.

## References

  * [1] Holger Kantz and Thomas Schreiber.  Nonlinear Time Series Analysis.  Cambridge University Press, USA, 1997.
  * [2] Martin Casdagli.  Nonlinear prediction of chaotic time series.  Physica D: Nonlinear Phenomena, 35(3):335 – 356, 1989.
  * [3] Steven L. Brunton, Joshua L. Proctor, and J. Nathan Kutz.  Discovering governing equations from data by sparse identification of nonlinear dynamical systems.  Proceedings of the National Academy of Sciences, 113(15):3932–3937, 2016.
  * [4] Jaideep Pathak, Zhixin Lu, Brian R. Hunt, Michelle Girvan, and Edward Ott.  Using machine learning to replicate chaotic attractors and calculate lyapunov exponents from data.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 27(12):121102, 2017.
  * [5] A. Nielsen.  Practical Time Series Analysis: Prediction with Statistics and Machine Learning.  O’Reilly Media, 2019.
  * [6] H. Abarbanel.  Analysis of Observed Chaotic Data.  Institute for Nonlinear Science. Springer New York, 2012.
  * [7] Gianluigi Pillonetto, Minh Ha Quang, and Alessandro Chiuso.  A New Kernel-Based Approach for NonlinearSystem Identification.  IEEE Transactions on Automatic Control, 56(12):2825–2840, December 2011.
  * [8] Wen-Xu Wang, Rui Yang, Ying-Cheng Lai, Vassilios Kovanis, and Celso Grebogi.  Predicting Catastrophes in Nonlinear Dynamical Systems by Compressive Sensing.  Physical Review Letters, 106(15):154101, April 2011.
  * [9] Steven L. Brunton, Joshua L. Proctor, and J. Nathan Kutz.  Discovering governing equations from data by sparse identification of nonlinear dynamical systems.  Proceedings of the National Academy of Sciences, 113(15):3932–3937, April 2016.
  * [10] Bethany Lusch, J. Nathan Kutz, and Steven L. Brunton.  Deep learning for universal linear embeddings of nonlinear dynamics.  Nature Communications, 9(1):4950, December 2018.
  * [11] Jared L. Callaham, James V. Koch, Bingni W. Brunton, J. Nathan Kutz, and Steven L. Brunton.  Learning dominant physical processes with data-driven balance models.  Nature Communications, 12(1):1016, December 2021.
  * [12] Alan A. Kaptanoglu, Kyle D. Morgan, Chris J. Hansen, and Steven L. Brunton.  Physics-constrained, low-dimensional models for magnetohydrodynamics: First-principles and data-driven approaches.  Physical Review E, 104(1):015206, July 2021.
  * [13] J. Nathan Kutz and Steven L. Brunton.  Parsimony as the ultimate regularizer for physics-informed machine learning.  Nonlinear Dynamics, January 2022.
  * [14] Simon N. Wood.  Statistical inference for noisy nonlinear ecological dynamic systems.  Nature, 466(7310):1102–1104, August 2010.
  * [15] Matthias Katzfuss, Jonathan R. Stroud, and Christopher K. Wikle.  Ensemble Kalman Methods for High-Dimensional Hierarchical Dynamic Space-Time Models.  Journal of the American Statistical Association, 115(530):866–885, April 2020.
  * [16] Sheng Zhang and Guang Lin.  Robust data-driven discovery of governing physical laws with error bars.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2217):20180305, 2018.
  * [17] Maziar Raissi, Alireza Yazdani, and George Em Karniadakis.  Hidden fluid mechanics: Learning velocity and pressure fields from flow visualizations.  Science, 367(6481):1026–1030, February 2020.
  * [18] Samuel H. Rudy, J. Nathan Kutz, and Steven L. Brunton.  Deep learning of dynamics and signal-noise decomposition with time-stepping constraints.  Journal of Computational Physics, 396:483–506, November 2019.
  * [19] Baolei Wei.  Sparse dynamical system identification with simultaneous structural parameters and initial condition estimation.  Chaos, Solitons & Fractals, 165:112866, 2022.
  * [20] H. Schaeffer, R. Caflisch, C. D. Hauck, and S. Osher.  Sparse dynamics for partial differential equations.  Proceedings of the National Academy of Sciences, 110(17):6634–6639, April 2013.
  * [21] Hayden Schaeffer, Giang Tran, Rachel Ward, and Linan Zhang.  Extracting structured dynamical systems using sparse optimization with very few samples.  Multiscale Modeling & Simulation, 18(4):1435–1461, 2020.
  * [22] B. Haasdonk, B. Hamzi, G. Santin, and D. Wittwar.  Greedy kernel methods for center manifold approximation.  Proc. of ICOSAHOM 2018, International Conference on Spectral and High Order Methods, (1), 2018.  https://arxiv.org/abs/1810.11329.
  * [23] B.Haasdonk ,B.Hamzi , G.Santin , D.Wittwar.  Kernel methods for center manifold approximation and a weak data-based version of the center manifold theorems.  Physica D, 2021.
  * [24] P. Giesl, B. Hamzi, M. Rasmussen, and K. Webster.  Approximation of Lyapunov functions from noisy data.  Journal of Computational Dynamics, 2019.  https://arxiv.org/abs/1601.01568.
  * [25] Boumediene Hamzi and Houman Owhadi.  Learning dynamical systems from data: A simple cross-validation perspective, part i: Parametric kernel flows.  Physica D: Nonlinear Phenomena, 421:132817, 2021.
  * [26] Boumediene Hamzi and Fritz Colonius.  Kernel methods for the approximation of discrete-time linear autonomous and control systems.  SN Applied Sciences, 1(7):674, July 2019.
  * [27] Stefan Klus, Feliks Nuske, and Boumediene Hamzi.  Kernel-based approximation of the koopman generator and schrödinger operator.  Entropy, 22, 2020.  https://www.mdpi.com/1099-4300/22/7/722.
  * [28] Stefan Klus, Feliks Nüske, Sebastian Peitz, Jan-Hendrik Niemann, Cecilia Clementi, and Christof Schütte.  Data-driven approximation of the koopman generator: Model reduction, system identification, and control.  Physica D: Nonlinear Phenomena, 406:132416, 2020.
  * [29] Romeo Alexander and Dimitrios Giannakis.  Operator-theoretic framework for forecasting nonlinear time series with kernel analog techniques.  Physica D: Nonlinear Phenomena, 409:132520, 2020.
  * [30] Andreas Bittracher, Stefan Klus, Boumediene Hamzi, Peter Koltai, and Christof Schutte.  Dimensionality reduction of complex metastable systems via kernel embeddings of transition manifold, 2019.  https://arxiv.org/abs/1904.08622.
  * [31] Jake Bouvrie and Boumediene Hamzi.  Empirical estimators for stochastically forced nonlinear systems: Observability, controllability and the invariant measure.  Proc. of the 2012 American Control Conference, pages 294–301, 2012\.  https://arxiv.org/abs/1204.0563v1.
  * [32] Jake Bouvrie and Boumediene Hamzi.  Kernel methods for the approximation of nonlinear systems.  SIAM J. Control and Optimization, 2017.  https://arxiv.org/abs/1108.2903.
  * [33] Jake Bouvrie and Boumediene Hamzi.  Kernel methods for the approximation of some key quantities of nonlinear systems.  Journal of Computational Dynamics, 1, 2017.  http://arxiv.org/abs/1204.0563.
  * [34] Boumediene Hamzi, Christian Kuehn, and Sameh Mohamed.  A note on kernel methods for multiscale systems with critical transitions.  Mathematical Methods in the Applied Sciences, 42(3):907–917, 2019\.
  * [35] David J. C. MacKay.  Information Theory, Inference, and Learning Algorithms.  Copyright Cambridge University Press, 2003.
  * [36] Cristopher Moore.  Unpredictability and undecidability in dynamical systems.  Physical Review Letters, 64(20):2354, 1990.
  * [37] James D Watson, Emilio Onorati, and Toby S Cubitt.  Uncomputably complex renormalisation group flows.  Nature Communications, 13(1):7618, 2022.
  * [38] Stephen Wolfram.  Undecidability and intractability in theoretical physics.  Physical Review Letters, 54(8):735, 1985.
  * [39] S. Wolfram.  A New Kind of Science.  Wolfram Media, 2002.
  * [40] Karl Svozil.  Randomness & undecidability in physics.  World Scientific, 1993.
  * [41] Seth Lloyd.  Uncomputability and physical law.  The Incomputable: Journeys Beyond the Turing Barrier, pages 95–104, 2017.
  * [42] Anthony Aguirre, Zeeya Merali, and David Sloan.  Undecidability, uncomputability, and unpredictability, 2021.
  * [43] Toby S Cubitt, Jens Eisert, and Michael M Wolf.  Extracting dynamical equations from experimental data is np hard.  Physical review letters, 108(12):120503, 2012.
  * [44] M. Mezard and A. Montanari.  Information, physics, and computation.  Oxford University Press, USA, 2009.
  * [45] R. J. Solomonoff.  A preliminary report on a general theory of inductive inference (revision of report v-131).  Contract AF, 49(639):376, 1960.
  * [46] A.N. Kolmogorov.  Three approaches to the quantitative definition of information.  Problems of information transmission, 1(1):1–7, 1965.
  * [47] Gregory J Chaitin.  A theory of program size formally identical to information theory.  Journal of the ACM (JACM), 22(3):329–340, 1975.
  * [48] Kamaludin Dingle, Chico Q Camargo, and Ard A Louis.  Input–output maps are strongly biased towards simple outputs.  Nature communications, 9(1):761, 2018.
  * [49] Kamaludin Dingle, Guillermo Valle Pérez, and Ard A Louis.  Generic predictions of output probability based on complexities of inputs and outputs.  Scientific reports, 10(1):1–9, 2020.
  * [50] Kamaludin Dingle, Pau Batlle, and Houman Owhadi.  Multiclass classification utilising an estimated algorithmic probability prior.  Physica D: Nonlinear Phenomena, 448:133713, 2023.
  * [51] Kamaludin Dingle, Rafiq Kamal, and Boumediene Hamzi.  A note on a priori forecasting and simplicity bias in time series.  Physica A: Statistical Mechanics and Its Applications, 609:128339, 2023.
  * [52] Iain G Johnston, Kamaludin Dingle, Sam F Greenbury, Chico Q Camargo, Jonathan PK Doye, Sebastian E Ahnert, and Ard A Louis.  Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution.  Proceedings of the National Academy of Sciences, 119(11):e2113883119, 2022.
  * [53] Guillermo Valle-Perez, Chico Q Camargo, and Ard A Louis.  Deep learning generalizes because the parameter-function map is biased towards simple functions.  arXiv preprint arXiv:1805.08522, 2018.
  * [54] Chris Mingard, Joar Skalse, Guillermo Valle-Pérez, David Martínez-Rubio, Vladimir Mikulik, and Ard A Louis.  Neural networks are a priori biased towards boolean functions with low entropy.  arXiv preprint arXiv:1909.11522, 2019.
  * [55] Satwik Bhattamishra, Arkil Patel, Varun Kanade, and Phil Blunsom.  Simplicity bias in transformers and their ability to learn sparse boolean functions.  arXiv preprint arXiv:2211.12316, 2022.
  * [56] Greg Yang and Hadi Salman.  A fine-grained spectral perspective on neural networks.  arXiv preprint arXiv:1907.10599, 2019.
  * [57] Chris Mingard, Henry Rees, Guillermo Valle-Pérez, and Ard A Louis.  Do deep neural networks have an inbuilt occam’s razor?  arXiv preprint arXiv:2304.06670, 2023.
  * [58] A. Lempel and J. Ziv.  On the complexity of finite sequences.  Information Theory, IEEE Transactions on, 22(1):75–81, 1976.
  * [59] Jacob Ziv and Abraham Lempel.  A universal algorithm for sequential data compression.  IEEE Transactions on information theory, 23(3):337–343, 1977.
  * [60] J.P. Delahaye and H. Zenil.  Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of algorithmic randomness.  Appl. Math. Comput., 219:63–77, 2012.
  * [61] Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye, and Nicolas Gauvrit.  Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines.  PloS one, 9(5):e96223, 2014.
  * [62] Robert M May.  Simple mathematical models with very complicated dynamics.  Nature, 261:459–467, 1976.
  * [63] Boris Hasselblatt and Anatole Katok.  A first course in dynamics: with a panorama of recent developments.  Cambridge University Press, 2003.
  * [64] Robert C Hilborn et al.  Chaos and nonlinear dynamics: an introduction for scientists and engineers.  Oxford University Press on Demand, 2000.
  * [65] M. Li and P.M.B. Vitanyi.  An introduction to Kolmogorov complexity and its applications.  Springer-Verlag New York Inc, 2008.
  * [66] C.S. Calude.  Information and randomness: An algorithmic perspective.  Springer, 2002.
  * [67] P. Gács.  Lecture notes on descriptional complexity and randomness.  Boston University, Graduate School of Arts and Sciences, Computer Science Department, 1988.
  * [68] Alexander Shen, Vladimir A Uspensky, and Nikolay Vereshchagin.  Kolmogorov complexity and algorithmic randomness, volume 220.  American Mathematical Society, 2022.
  * [69] Alan Mathison Turing.  On computable numbers, with an application to the entscheidungsproblem.  J. of Math, 58(345-363):5, 1936.
  * [70] Peter Grunwald and Paul Vitányi.  Shannon information and Kolmogorov complexity.  arXiv preprint cs/0410002, 2004.
  * [71] C.H. Bennett.  The thermodynamics of computation – a review.  International Journal of Theoretical Physics, 21(12):905–940, 1982\.
  * [72] Artemy Kolchinsky and David H Wolpert.  Thermodynamic costs of turing machines.  Physical Review Research, 2(3):033312, 2020.
  * [73] W.H. Zurek.  Algorithmic randomness and physical entropy.  Physical Review A, 40(8):4731, 1989.
  * [74] Artemy Kolchinsky.  Generalized zurek’s bound on the cost of an individual classical or quantum computation.  arXiv preprint arXiv:2301.06838, 2023.
  * [75] Markus P Mueller.  Law without law: from observer states to physics via algorithmic information theory.  Quantum, 4:301, 2020.
  * [76] Ram Avinery, Micha Kornreich, and Roy Beck.  Universal and accessible entropy estimation using a compression algorithm.  Physical review letters, 123(17):178102, 2019.
  * [77] Stefano Martiniani, Paul M Chaikin, and Dov Levine.  Quantifying hidden order out of equilibrium.  Physical Review X, 9(1):011031, 2019.
  * [78] P. Ferragina, R. Giancarlo, V. Greco, G. Manzini, and G. Valiente.  Compression-based classification of biological sequences and structures via the universal similarity metric: experimental assessment.  BMC bioinformatics, 8(1):252, 2007.
  * [79] Alyssa Adams, Hector Zenil, Paul CW Davies, and Sara Imari Walker.  Formal definitions of unbounded evolution and innovation reveal universal mechanisms for open-ended evolution in dynamical systems.  Scientific reports, 7(1):1–15, 2017.
  * [80] Sean D Devine.  Algorithmic Information Theory for Physicists and Natural Scientists.  IOP Publishing, 2020.
  * [81] Paul MB Vitányi.  Similarity and denoising.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371(1984):20120091, 2013.
  * [82] R. Cilibrasi and P.M.B. Vitányi.  Clustering by compression.  Information Theory, IEEE Transactions on, 51(4):1523–1545, 2005\.
  * [83] L.A. Levin.  Laws of information conservation (nongrowth) and aspects of the foundation of probability theory.  Problemy Peredachi Informatsii, 10(3):30–35, 1974.
  * [84] Mark Buchanan.  A natural bias for simplicity.  Nature Physics, 14:1154, 2018.
  * [85] Kamaludin Dingle, Javor K Novev, Sebastian E Ahnert, and Ard A Louis.  Predicting phenotype transition probabilities via conditional algorithmic probability approximations.  Journal of the Royal Society Interface, 19(197):20220694, 2022.
  * [86] Mohammad Alaskandarani and Kamaludin Dingle.  Low complexity, low probability patterns and consequences for algorithmic probability applications.  Complexity, 2023, 2023.
  * [87] Douglas Lind and Brian Marcus.  An introduction to symbolic dynamics and coding.  Cambridge university press, 1995.
  * [88] Ali Kanso and Nejib Smaoui.  Logistic chaotic maps for binary numbers generations.  Chaos, Solitons & Fractals, 40(5):2557–2568, 2009.
  * [89] Arno Berger.  Chaos and Chance: An Introduction to Stochastic Apects of Dynamics.  Walter de Gruyter, 2001.
  * [90] F. Kaspar and HG Schuster.  Easily calculable measure for the complexity of spatiotemporal patterns.  Physical Review A, 36(2):842, 1987.
  * [91] Mitchell J Feigenbaum.  The universal metric properties of nonlinear transformations.  Journal of Statistical Physics, 21:669–706, 1979.
  * [92] Mitchell J Feigenbaum.  Universal behavior in nonlinear systems.  Physica D: Nonlinear Phenomena, 7(1-3):16–39, 1983.
  * [93] Houssam Binous.  Bifurcation diagram for the Gauss map from the Wolfram Demonstrations Project.  2011\.
  * [94] Vinod Patidar.  Co-existence of regular and chaotic motions in the gaussian map.  Electronic Journal of Theoretical Physics, 3(13), 2006.
  * [95] MT Suryadi, Yudi Satria, and Luqman N Prawadika.  An improvement on the chaotic behavior of the gauss map for cryptography purposes using the circle map combination.  In Journal of Physics: Conference Series, volume 1490, page 012045\. IOP Publishing, 2020.
  * [96] Stephen Wolfram.  Mitchell Feigenbaum (1944–2019), 4.66920160910299067185320382…  2023\.
  * [97] Jory Griffin.  The sine map.  https://people.maths.bris.ac.uk/ macpd/ads/sine.pdf, 2013.
  * [98] Chunyi Dong, Karthikeyan Rajagopal, Shaobo He, Sajad Jafari, and Kehui Sun.  Chaotification of sine-series maps based on the internal perturbation model.  Results in Physics, 31:105010, 2021.
  * [99] Seth Lloyd.  Measures of complexity: a nonexhaustive list.  IEEE Control Systems Magazine, 21(4):7–8, 2001.
  * [100] Melanie Mitchell.  Complexity: a guided tour.  Oxford University Press, 2009.
  * [101] William Bialek, Ilya Nemenman, and Naftali Tishby.  Complexity through nonextensivity.  Physica A: Statistical Mechanics and its Applications, 302(1-4):89–99, 2001.
  * [102] William Bialek, Ilya Nemenman, and Naftali Tishby.  Predictability, complexity, and learning.  Neural computation, 13(11):2409–2463, 2001.
  * [103] JB Coe, SE Ahnert, and TMA Fink.  When are cellular automata random?  EPL (Europhysics Letters), 84(5):50005, 2008.
  * [104] Ludwig Arnold, Christopher KRT Jones, Konstantin Mischaikow, Geneviève Raugel, and Ludwig Arnold.  Random dynamical systems.  Springer, 1995.
  * [105] Thai Son Doan, Maximilian Engel, Jeroen SW Lamb, and Martin Rasmussen.  Hopf bifurcation with additive noise.  Nonlinearity, 31(10):4567, 2018.
  * [106] Kamaludin Dingle, Jeroen SW Lamb, and Joan-Andreu Lázaro-Camí.  Knudsen’s law and random billiards in irrational triangles.  Nonlinearity, 26(2):369, 2012.
  * [107] Yuzuru Sato, Thai Son Doan, Jeroen SW Lamb, and Martin Rasmussen.  Dynamical characterization of stochastic bifurcations in a random logistic map.  arXiv preprint arXiv:1811.03994, 2018.
  * [108] Homer S White.  Algorithmic complexity of points in dynamical systems.  Ergodic Theory and Dynamical Systems, 13(4):807–830, 1993.
  * [109] AA Brudno.  The complexity of the trajectories of a dynamical system.  Russian Mathematical Surveys, 33(1):197, 1978.
  * [110] Vladimir V V’yugin.  Ergodic theorems for algorithmically random points.  arXiv preprint arXiv:2202.13465, 2022.

##  Appendix A The impact of the number of iterations

In this brief section, we give examples of the impact of changing the length
$n$ of binary strings.

For very small numbers of iterations, simplicity bias is not pronounced. This
is due primarily to the fact that the complexity measure is not very sensitive
to small changes in complexity values. To illustrate, in Figure 6(a) a plot is
shown for $n=5$ iterations only. In this case, there is some evidence of
simplicity bias (i.e., an inverse relation between complexity and
probability), but the relation is not strong. A similar weak connection
between complexity and probability was observed for very short sequences in an
earlier time series study of simplicity bias [51]. In Figure 6(b), clear
simplicity bias is observed with $n=25$. At this length, the complexity
measure is sufficiently sensitive and we have sufficient sampling to reveal
order of magnitude variations in probability.

In theory, for larger output complexities simplicity bias should be more clear
[48], and in fact AIT results in general are typically stated up to $O(1)$
terms, which become irrelevant when pattern complexities become asymptotically
large [65]. However, in this logistic map example we find that for longer
iterations, the pattern of simplicity bias becomes more noisy and less clear;
see Figures 6(c) and (d). For larger $n$ the number of possible patterns
becomes exponentially large and the one million samples produces many patterns
of frequency $\approx$1, yielding a long flat ‘tail’ in the graph.

Figure 6. Simplicity bias with different number of iterations. (a) With $n=5$
iterations, there is some simplicity bias but it is not pronounced; (b) with
$n=25$ iterations, simplicity bias is very clear; with (c) $n=50$ iterations
there is still clear simplicity bias, but a long ‘tail’ begins to emerge, of
low frequency patterns; (d) with $n=100$ iterations, there is still some
simplicity bias but the ‘tail’ has become more dominant and simplicity bias is
less clear.