Duality in complex stochastic boolean systems

Chapter 1 DUALITY IN COMPLEX STOCHASTIC BOOLEAN SYSTEMS LUIS GONZÁLEZ Research Institute IUSIANI, Department of Mathematics, University of Las Palmas de Gran Canaria, Campus Universitario de Tafira, 35017 Las Palmas de Gran Canaria, Spain Email: [email protected] Abstract Many different complex systems depend on a large number nof mutually independent random Boolean variables. The most useful representation for these systems –usually called complex stochastic Boolean systems (CSBSs)– is the intrinsic order graph. This is a directed graph on 2n vertices, corresponding to the 2nbinary n-tuples (u1,...,un)∈ {0,1}n of 0s and 1s. In this paper, different duality properties of the intrinsic order graph are rigorously analyzed in detail. The results can be applied to many CSBSs arising from any scientific, technical or social area. Keywords: Complex stochastic Boolean systems, intrinsic order, intrinsic order graph, complementary n-tuples, duality 1. Introduction The study of complex systems is at present one of the most relevant research areas in Computer Science and Engineering. In this paper, we focus our attention on the complex stochastic Boolean systems (CSBSs), that is, those complex systems which depend on a certain number nof random Boolean variables. These systems can appear in any knowledge area, since the assumption “random Boolean variables” is satisfied very often in practice. Using the statistical terminology, a CSBS can be modeled by the ndimensional Bernoulli distribution. As is well known (see, e.g., [Stuart, 2ELECTRICAL ENGINEERING AND INTELLIGENT SYSTEMS et al, 1998]), this distribution consists of nrandom variables x1, . . . , xn, which only take two possible values, 0 or 1, with probabilities Pr {xi= 1}=pi,Pr {xi= 0}= 1 −pi(1 ≤i≤n). In the following, we assume that the marginal Bernoulli variables x1, . . . , xnare mutually independent, so that the probability of occurrence of each binary n-tuple, u= (u1, . . . , un)∈ {0,1}n, can be computed as the product Pr {(u1, . . . , un)}= n Y i=1 Pr {xi=ui}= n Y i=1 pui i(1 −pi)1−ui,(1.1) that is, Pr {(u1, . . . , un)}is the product of factors piif ui= 1, 1-piif ui= 0. Throughout this paper, the binary n-tuples (u1, . . . , un) of 0s and 1s will be also called binary strings or bitstrings, and the parameters p1, . . . , pnof the n-dimensional Bernoulli distribution will be also called basic probabilities. Example 1.1 Let n= 3 and u= (1,0,1) ∈ {0,1}3. Let p1= 0.1, p2= 0.2, p3= 0.3. Then, using Eq. (1.1), we have Pr {(1,0,1)}=p1(1 −p2)p3= 0.024. One of the most relevant questions in the analysis of CSBSs consists of ordering the binary strings (u1, . . . , un) according to their occurrence probabilities. Of course, the theoretical and practical interest of this question is obvious. For instance, in [Gonz´alez, 2002; Gonz´alez, et al, 2004] the authors justify the convenience of using binary n-tuples with occurrence probabilities as large as possible, in order to solve, with a low computational cost, some classical problems in Reliability Theory and Risk Analysis. Of course, computing and ordering all the 2nbinary n-tuple probabilities (in decreasing or increasing order) is only feasible for small values of n. For large values of the number nof basic Boolean variables (the usual situation in practice), we need an alternative strategy. For this purpose, in [Gonz´alez, 2002] we have established a simple, positional criterion that allows one to compare two given binary n-tuple probabilities, Pr {u},Pr {v}, without computing them, simply looking at the positions of the 0s and 1s in the n-tuples u, v. We have called it the intrinsic order criterion, because it is independent of the basic probabilities piand it intrinsically depends on the positions of the 0s and 1s in the binary strings. Duality in Complex Stochastic Boolean Systems 3 The intrinsic order, denoted by “”, is a partial order relation on the set {0,1}nof all binary n-tuples. The usual representation of this kind of binary relations is the Hasse diagram [Stanley, 1997]. In particular, the Hasse diagram of the partially ordered set ({0,1}n,) is referred to as the intrinsic order graph for nvariables. In this context, the main goal of this paper is to state and rigorously prove some properties of the intrinsic order graph. Some of these properties can be found in [Gonz´alez, 2011]. In particular, we focus our attention on several duality properties of this graph. For this purpose, this paper has been organized as follows. In Section 2, we present some previous results on the intrinsic order relation and the intrinsic order graph, enabling non-specialists to follow the paper without difficulty and making the presentation self-contained. Section 3 is devoted to provide different duality properties of the intrinsic order graph. Finally, conclusions are presented in Section 4. 2. The Intrinsic Order Relation and its Graph The Intrinsic Order Relation In the context of the CSBSs defined in Section 1, the following simple question arises: Given a certain n-dimensional Bernoulli distribution, how can we order two given binary n-tuples, u, v ∈ {0,1}n, by their occurrence probabilities, without computing them? Of course, the ordering between Pr (u) and Pr (v) depends, in general, on the parameters piof the Bernoulli distribution, as the following simple example shows. Example 2.1 Let n= 3, u = (0,1,1) and v= (1,0,0). Using Eq. (1.1) for p1= 0.1, p2= 0.2, p3= 0.3, we have: Pr {(0,1,1)}= 0.054 <Pr {(1,0,0)}= 0.056, while for p1= 0.2, p2= 0.3, p3= 0.4, we have: Pr {(0,1,1)}= 0.096 >Pr {(1,0,0)}= 0.084. However, for some pairs of binary strings, the ordering between their occurrence probabilities is independent of the basic probabilities pi, and it only depends on the relative positions of their 0s and 1s. More precisely, the following theorem [Gonz´alez, 2002; Gonz´alez, 2003] provides us with an intrinsic order criterion –denoted from now on by the acronym IOC– to compare the occurrence probabilities of two given n-tuples of 0s 1s without computing them. 4ELECTRICAL ENGINEERING AND INTELLIGENT SYSTEMS Theorem 2.2 Let n≥1. Let x1, . . . , xnbe nmutually independent Bernoulli variables whose parameters pi= Pr {xi= 1}satisfy 0< p1≤p2≤. . . ≤pn≤1 2.(2.1) Then the probability of the n-tuple v= (v1, . . . , vn)∈ {0,1}nis intrinsically less than or equal to the probability of the n-tuple u= (u1, . . . , un)∈ {0,1}n(that is, for all set {pi}n i=1satisfying (2.1)) if and only if the matrix Mu v:= u1. . . un v1. . . vn either has no 1 0columns, or for each 1 0column in Mu vthere exists (at least)one corresponding preceding 0 1column (IOC). Remark 2.3 In the following, we assume that the parameters pialways satisfy condition (2.1). Note that this hypothesis is not restrictive for practical applications because, if for some i:pi>0.5, then we only need to consider the variable xi= 1 −xi, instead of xi. Next, we order the n Bernoulli variables by increasing order of their probabilities. Remark 2.4 The 0 1column preceding to each 1 0column is not required to be necessarily placed at the immediately previous position, but just at previous position. Remark 2.5 The term corresponding, used in Theorem 2.2, has the following meaning: For each two 1 0columns in matrix Mu v, there must exist (at least) two different 0 1columns preceding to each other. In other words: For each 1 0column in matrix Mu v, the number of preceding 0 1columns must be strictly greater than the number of preceding 1 0 columns. Remark 2.6 IOC can be equivalently reformulated in the following way, involving only the 1-bits of uand v(with no need to use their 0-bits). Matrix Mu vsatisfies IOC if and only if either uhas no 1-bits (i.e., uis the zero n-tuple) or for each 1-bit in uthere exists (at least) one corresponding 1-bit in vplaced at the same or at a previous position. In other words, either uhas no 1-bits or for each 1-bit in u, say ui= 1, the number of 1-bits in (v1, . . . , vi) must be greater than or equal to the number of 1-bits in (u1, . . . , ui). The matrix condition IOC, stated by Theorem 2.2 or by Remark 2.6, is called the intrinsic order criterion, because it is independent of the basic probabilities piand it only depends on the relative positions of the Duality in Complex Stochastic Boolean Systems 5 0s and 1s in the binary n-tuples u, v. Theorem 2.2 naturally leads to the following partial order relation on the set {0,1}n[Gonz´alez, 2003]. The so-called intrinsic order will be denoted by “”, and we shall write uv (uv) to indicate that uis intrinsically greater (less) than or equal to v. The partially ordered set (from now on, poset, for short) ({0,1}n,) on nBoolean variables, will be denoted by In. Definition 2.7 For all u, v ∈ {0,1}n vuiff Pr {v} ≤ Pr {u}for all set {pi}n i=1 s.t. (2.1) iff Mu vsatisfies IOC. Example 2.8 Neither (0,1,1) (1,0,0), nor (1,0,0) (0,1,1) because the matrices 1 0 0 0 1 1 and 0 1 1 1 0 0  do not satisfy IOC (Remark 2.5). Therefore (0,1,1) and (1,0,0) are incomparable by intrinsic order, i.e., the ordering between Pr {(0,1,1)} and Pr {(1,0,0)}depends on the basic probabilities pi, as Example 2.1 has shown. Example 2.9 (1,1,0,1,0,0) (0,0,1,1,0,1) because matrix 001101 110100 satisfies IOC (Remark 2.4). Thus, for all {pi}6 i=1 s.t. (2.1) Pr {(1,1,0,1,0,0)} ≤ Pr {(0,0,1,1,0,1)}. Example 2.10 For all n≥1, the binary n-tuples 0,n ^ . . ., 0≡0 and 1,n ^ . . ., 1≡2n−1 are the maximum and minimum elements, respectively, in the poset In. Indeed, both matrices 0. . . 0 u1. . . unand u1. . . un 1. . . 1 satisfy IOC, since they have no 1 0columns! Thus, for all u∈ {0,1}nand for all {pi}n i=1 s.t. (2.1) Pr n1,n ^ . . ., 1o≤Pr {(u1, . . . , un)} ≤ Pr n0,n ^ . . ., 0o. 6ELECTRICAL ENGINEERING AND INTELLIGENT SYSTEMS Many different properties of the intrinsic order can be immediately derived from its simple matrix description IOC [Gonz´alez, 2002; Gonz´alez, 2003; Gonz´alez, 2007]. For instance, denoting by wH(u) the Hamming weight –or weight, simply– of u(i.e., the number of 1-bits in u), by u(10 the decimal representation of u, and by ≤lex the usual lexicographic (truth-table) order on {0,1}n, i.e., wH(u) := n X i=1 ui, u(10 := n X i=1 2n−iui, u ≤lex viff u(10 ≤v(10 then we have the following two necessary (but not sufficient) conditions for intrinsic order (see [Gonz´alez, 2003] for the proof). Corollary 2.11 For all n≥1and for all u, v ∈ {0,1}n uv⇒wH(u)≤wH(v), uv⇒u(10 ≤v(10 . A Hasse Diagram: The Intrinsic Order Graph Now, the graphical representation of the poset In= ({0,1}n,) is presented. The usual representation of a poset is its Hasse diagram (see [Stanley, 1997] for more details about these diagrams). Specifically, for our poset In, its Hasse diagram is a directed graph (digraph, for short) whose vertices are the 2nbinary n-tuples of 0s and 1s, and whose edges go upward from vto uwhenever ucovers v, denoted by u.v. This means that uis intrinsically greater than vwith no other elements between them, i.e., u . v ⇔uvand @w∈ {0,1}ns.t. uwv. A simple matrix characterization of the covering relation for the intrinsic order is given in the next theorem; see [Gonz´alez, 2006] for the proof. Theorem 2.12 (Covering relation in In)Let n≥1and let u, v ∈ {0,1}n. Then uBvif and only if the only columns of matrix Mu vdifferent from 0 0and 1 1are either its last column 0 1or just two columns, namely one 1 0column immediately preceded by one 0 1column, i.e., either Mu v=u1. . . un−10 u1. . . un−11(2.2) or there exists i(2 ≤i≤n)s.t. Mu v=u1. . . ui−20 1 ui+1 . . . un u1. . . ui−21 0 ui+1 . . . un.(2.3) Duality in Complex Stochastic Boolean Systems 7 Example 2.13 For n= 4, we have 6.7 since M6 7=0 1 1 0 0 1 1 1 has the pattern (2.2), 10 .12 since M10 12 =1 0 1 0 1 1 0 0 has the pattern (2.3). The Hasse diagram of the poset Inwill be also called the intrinsic order graph for nvariables, denoted as well by In. For small values of n, the intrinsic order graph Incan be directly constructed by using either Theorem 2.2 (matrix description of the intrinsic order) or Theorem 2.12 (matrix description of the covering relation for the intrinsic order). For instance, for n= 1: I1= ({0,1},), and its Hasse diagram is shown in Figure 1.1. 0 | 1 Figure 1.1. The intrinsic order graph for n= 1. Indeed I1contains a downward edge from 0 to 1 because (see Theorem 2.2) 0 1, since matrix 0 1has no 1 0columns! Alternatively, using Theorem 2.12, we have that 0 B1, since matrix 0 1has the pattern (2.2)! Moreover, this is in accordance with the obvious fact that Pr {0}= 1 −p1≥p1= Pr {1},since p1≤1/2 due to Eq. (2.1)! However, for large values of n, a more efficient method is needed. For this purpose, in [Gonz´alez, 2006] the following algorithm for iteratively building up In(for all n≥2) from I1(depicted in Figure 1.1), has been developed. Theorem 2.14 (Building up Infrom I1)Let n≥2. The graph of the poset In={0, . . . , 2n−1}(on 2nnodes)can be drawn simply by adding to the graph of the poset In−1=0, . . . , 2n−1−1(on 2n−1 nodes)its isomorphic copy 2n−1+In−1=2n−1, . . . , 2n−1(on 2n−1 nodes). This addition must be performed placing the powers of 2at consecutive levels of the Hasse diagram of In. Finally, the edges connecting one vertex uof In−1with the other vertex vof 2n−1+In−1are given by the set of 2n−2vertex pairs (u, v)≡u(10 ,2n−2+u(10 2n−2≤u(10 ≤2n−1−1. 8ELECTRICAL ENGINEERING AND INTELLIGENT SYSTEMS Figure 1.2 illustrates the above iterative process for the first few values of n, denoting all the binary n-tuples by their decimal equivalents. Basically, we first add to In−1its isomorphic copy 2n−1+In−1. This addition must be performed by placing the powers of two, 2n−2and 2n−1, at consecutive levels in the intrinsic order graph. The reason is simply that 2n−2.2n−1since matrix M2n−2 2n−1has the pattern (2.3). Then, we connect one-to-one the nodes of “the second half of the first half” to the nodes of “the first half of the second half”: A nice fractal property of In! 0 | 1 0 | 1 | 2 | 3 0 | 1 | 2 | 3 4 | 5 | 6 | 7 0 | 1 | 2 | 3 4 | 5 8 || 6 9 || 7 10 | 11 12 | 13 | 14 | 15 Figure 1.2. The intrinsic order graphs for n= 1,2,3,4. Each pair (u, v) of vertices connected in Ineither by one edge or by a longer path, descending from uto v, means that uis intrinsically greater than v, i.e., uv. On the contrary, each pair (u, v) of non-connected vertices in Ineither by one edge or by a longer descending path, means that uand vare incomparable by intrinsic order, i.e., uvand vu. Duality in Complex Stochastic Boolean Systems 9 The edgeless graph for a given graph is obtained by removing all its edges, keeping its nodes at the same positions. In Figures 1.3 & 1.4, the edgeless intrinsic order graphs of I5&I6, respectively, are depicted. 0 1 2 3 4 5 8 6 9 16 7 10 17 11 12 18 13 19 20 14 21 24 15 22 25 23 26 27 28 29 30 31 Figure 1.3. The edgeless intrinsic order graph for n= 5. 0 1 2 3 4 5 8 6 9 16 7 10 17 32 11 12 18 33 13 19 20 34 14 21 24 35 36 15 22 25 37 40 23 26 38 41 48 27 28 39 42 49 29 43 44 50 30 45 51 52 31 46 53 56 47 54 57 55 58 59 60 61 62 63 Figure 1.4. The edgeless intrinsic order graph for n= 6. For further theoretical properties and practical applications of the intrinsic order and the intrinsic order graph, we refer the reader to