Ranking intervals in complex stochastic Boolean systems using intrinsic ordering

Abstract

Many different phenomena, arising from scientific, technical or social areas, can be modeled by a system depending on a certain number n of random Boolean variables. The so-called complex stochastic Boolean systems (CSBSs) are characterized by the ordering between the occurrence probabilities Pr{u} of the 2 n associated binary strings of length n, i.e., u=(u 1,…,u n ) ∈ {0,1} n . The intrinsic order defined on {0,1} n provides us with a simple positional criterion for ordering the binary n-tuple probabilities without computing them, simply looking at the relative positions of their 0s and 1s. For every given binary n-tuple u, this paper presents two simple formulas – based on the positions of the 1-bits (0-bits, respectively) in u – for counting (and also for rapidly generating, if desired) all the binary n-tuples v whose occurrence probabilities Pr{v} are always less than or equal to (greater than or equal to, respectively) Pr{u}. Then, from these formulas, we determine the closed interval covering all possible values of the rank (position) of u in the list of all binary n-tuples arranged by decreasing order of their occurrence probabilities. Further, the length of this so-called ranking interval for u, also provides the number of binary n-tuples v incomparable by intrinsic order with u. Results are illustrated with the intrinsic order graph, i.e., the Hasse diagram of the partial intrinsic order.