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 different scientific, 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 = (u 1 ,…,u n ) ∈ {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 fixed 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.