Information fluctuation complexity

Information fluctuation complexity is an information-theoretic quantity defined as the fluctuation of information about entropy. It is derivable from fluctuations in the predominance of order and chaos in a dynamic system and has been used as a measure of complexity in many diverse fields. It was introduced in a 1993 paper by Bates and Shepard.
Definition.
The information fluctuation complexity of a discrete dynamic system is a function of the probability distribution of its states when it is subject to random external input data. The purpose of driving the system with a rich information source such as a random number generator or a white noise signal is to probe the internal dynamics of the system much the same as a frequency-rich impulse is used in signal processing. 
If a system has formula_1 possible states and the "state probabilities" formula_2are known, then its information entropy is
where formula_4 is the information content of state formula_5.
The information fluctuation complexity of the system is defined as the standard deviation or fluctuation of formula_6 about its mean formula_7:
or
The "fluctuation of state information" formula_10 is zero in a maximally disordered system with all formula_11; the system simply mimics its random inputs. formula_10 is also zero when the system is perfectly ordered with just one fixed state formula_13, regardless of inputs. formula_10 is non-zero between these two extremes with a mixture of both higher-probability states and lower-probability states populating state space.
Fluctuation of information allows for memory and computation.
As a complex dynamic system evolves in time, how it transitions between states depends on external stimuli in an irregular way. At times it may be more sensitive to external stimuli (unstable) and at other times less sensitive (stable). If a particular state has several possible next-states, external information determines which one will be next and the system gains that information by following a particular trajectory in state space. But if several different states all lead to the same next-state, then upon entering the next-state the system loses information about which state preceded it. Thus, a complex system exhibits alternating information gain and loss as it evolves in time. The alternation or fluctuation of information is equivalent to remembering and forgetting — temporary information storage or memory — an essential feature of non-trivial computation. 
The gain or loss of information associated with transitions between states can be related to state information. The "net information gain" of a transition from state formula_15 to state formula_16 is the information gained when leaving state formula_15 less the information lost when entering state formula_16:
Here formula_20 is the "forward conditional probability" that if the present state is formula_15 then the next state is formula_16 and formula_23 is the "reverse conditional probability" that if the present state is formula_16 then the previous state was formula_25. The conditional probabilities are related to the "transition probability" formula_26, the probability that a transition from state formula_25 to state formula_16 occurs, by:
Eliminating the conditional probabilities:
Therefore the net information gained by the system as a result of the transition depends only on the increase in state information from the initial to the final state. It can be shown that this is true even for multiple consecutive transitions.
formula_31 is reminiscent of the relation between force and potential energy. formula_32 is like potential formula_33 and formula_34 is like force formula_35 in formula_36. External information “pushes” a system “uphill” to a state of higher information potential to accomplish memory storage, much like pushing a mass uphill to a state of higher gravitational potential stores energy. The amount of energy storage depends only on the final height, not the path up the hill. Likewise, the amount of information storage does not depend on the transition path between two states in state space. Once a system reaches a rare state with high information potential, it may "fall" to a more common state, losing the previously stored information.
It may be useful to compute the standard deviation of formula_34 about its mean (which is zero), namely the "fluctuation of net information gain" formula_38, but formula_39 takes into account multi-transition "memory loops" in state space and therefore should be a better indicator of the computational power of a system. Moreover, formula_39 is easier to calculate because there can be many more transitions than states. 
Chaos and order.
A dynamic system that is sensitive to external information (unstable) exhibits chaotic behavior whereas one that is insensitive to external information (stable) exhibits orderly behavior. A complex system exhibits both behaviors, fluctuating between them in dynamic balance when subject to a rich information source. The degree of fluctuation is quantified by formula_39; it captures the alternation in the predominance of chaos and order in a complex system as it evolves in time.
Example: rule 110 variant of the elementary cellular automaton.
The rule 110 variant of the elementary cellular automaton has been proven to be capable of universal computation. The proof is based on the existence and interactions of cohesive and self-perpetuating cell patterns known as gliders or spaceships, emergent phenomena, that imply the capability of groups of automaton cells to remember that a glider is passing through them. It is therefore to be expected that there will be memory loops in state space resulting from alternations of information gain and loss, instability and stability, chaos and order.
Consider a 3-cell group of adjacent automaton cells that obey rule 110: . The next state of the center cell depends on the present state of itself and the end cells as specified by the rule: 
To calculate the information fluctuation complexity of this system, attach a "driver cell" to each end of the 3-cell group to provide a random external stimulus like so, , such that the rule can be applied to the two end cells. Next determine what the next state is for each possible present state and for each possible combination of driver cell contents, to determine the forward conditional probabilities. 
The state diagram of this system is depicted below, with circles representing the states and arrows representing transitions between states. The eight states of this system, to are labeled with the decimal equivalent of the 3-bit contents of the 3-cell group: 7 to 0. The transition arrows are labeled with forward conditional probabilities. Notice that there is variability in the divergence and convergence of arrows corresponding to a variability in chaos and order, sensitivity and insensitivity, gain and loss of external information from the driver cells. 
The forward conditional probabilities are determined by the proportion of possible driver cell contents that drive a particular transition. For example, for the four possible combinations of two driver cell contents, state 7 leads to states 5, 4, 1 and 0 so formula_42, formula_43, formula_44, and formula_45 are each 1/4 or 25%. Likewise, state 0 leads to states 0, 1, 0 and 1 so formula_46and formula_47are each 1/2 or 50%. And so forth.
The state probabilities are related by
These linear algebraic equations can be solved manually or with the aid of a computer program for the state probabilities, with the following results:
Information entropy and complexity can then be calculated from the state probabilities:
Note that the maximum possible entropy for eight states is formula_52 which would be the case if all eight states were equally likely with probabilities of 1/8 (randomness). Thus rule 110 has a relatively high entropy or state utilization at 2.86 bits. But this does not preclude a substantial fluctuation of state information about entropy and thus a substantial value of complexity. Whereas, maximum entropy "would" preclude complexity.
An alternative method can be used to obtain the state probabilities when the analytical method used above is unfeasible. Simply drive the system at its inputs (the driver cells) with a random source for many generations and observe the state probabilities empirically. When this is done via computer simulation for 10 million generations the results are as follows:
Since both formula_53 and formula_39 increase with system size, their dimensionless ratio formula_55, the "relative information fluctuation complexity", is included to better compare systems of different sizes. Notice that the empirical and analytical results agree for the 3-cell automaton.
In the paper by Bates and Shepard, formula_39 is computed for all elementary cellular automaton rules and it was observed that the ones that exhibit slow-moving gliders and possibly stationary objects, as rule 110 does, are highly correlated with large values of formula_39. formula_39 can therefore be used as a filter to select candidate rules for universal computation, which is tedious to prove.
Applications.
Although the derivation of the information fluctuation complexity formula is based on information fluctuations in a dynamic system, the formula depends only on state probabilities and so is also applicable to any probability distribution, including those derived from static images or text.
Over the years the original paper has been referred to by researchers in many diverse fields: complexity theory, complex systems science, chaotic dynamics, environmental engineering, ecological complexity, ecological time-series analysis, ecosystem sustainability, air and water pollution, hydrological wavelet analysis, soil water flow, soil moisture, headwater runoff, groundwater depth, air traffic control, flow patterns and flood events, topology, market forecasting of metal and electricity prices, health informatics, human cognition, human gait kinematics, neurology, EEG analysis, speech analysis, education, investing, and aesthetics.