Algorithm comparing binary string probabilities in complex stochastic boolean systems using intrinsic order graph

Abstract

This paper deals with a special kind of complex systems which depend on an arbitrary (and usually large) number n of random Boolean variables. The so-called complex stochastic Boolean systems often appear in many diff. erent scientifi. c, technical or social areas. Clearly, there are 2(n) binary states associated to such a complex system. Each one of them is given by a binary string u = (u1,..., u(n)) is an element of {0, 1}(n) of n bits, which has a certain occurrence probability Pr{u}. The behavior of a complex stochastic Boolean system is determined by the current values of its 2(n) binary n-tuple probabilities Pr{u} and by the ordering between pairs of them. Hence, the intrinsic order graph provides a useful representation of these systems by displaying (scaling) the 2(n) binary n-tuples which are ordered in decreasing probability of occurrence. The intrinsic order reduces the complexity of the problem from exponential (2(n) binary n-tuples) to linear (n Boolean variables). For any. xed binary n-tuple u, this paper presents a new, simple algorithm enabling rapid, elegant determination of all the binary n-tuples v with occurrence probabilities less than or equal to (greater than or equal to) Pr{u}. This algorithm is closely related to the lexicographic (truth- table) order in {0, 1} n, and this is illustrated through the connections (paths) in the intrinsic order graph.