Abstract

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

Mathematical Subject Classification

Milestones

Authors