Intuitively, the three properties of complexity, stability, and system performance
are interrelated. For instance, more complex ecological systems tend to be
less stable, and in software engineering, software performance reliability
is directly affected by software complexity. We introduce a new rigorous
framework that shows how these three properties interrelate. We focus on
a specific family of systems that predict input binary Markov chains. A
system’s output is a binary sequence that indicates when it fails to predict the
input. System complexity is the average number of information bits needed to
describe the output per input bit. System stability is the discrepancy between
the system’s output when presented with two random input sequences. A
bound on the prediction error is derived and used as a system’s performance
guarantee. It is shown that as complexity increases, stability decreases, and
performance guarantee becomes more sensitive to changes in the input, making the
system less robust. The analysis taken here is applicable to more general
systems.
Keywords
system complexity, Markov chain prediction, concentration
inequality, entropy
