Labeling the nodes in the intrinsic order graph with their weights
Abstract
536
Full text
Chapter 1 LABELING THE NODES IN THE INTRINSIC ORDER GRAPH WITH THEIR WEIGHTS 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 This paper deals with the study of some new properties of the intrinsic order graph. The intrinsic order graph is the natural graphical representation of a complex stochastic Boolean system (CSBS). A CSBS is a system depending on an arbitrarily large number nof mutually independent random Boolean variables. The intrinsic order graph displays its 2nvertices (associated to the CSBS) from top to bottom, in decreasing order of their occurrence probabilities. New relations between the intrinsic ordering and the Hamming weight (i.e., the number of 1-bits in abinaryn-tuple) are derived. Further, the distribution of the weights of the 2nnodes in the intrinsic order graph is analyzed. Keywords: Complex stochastic Boolean systems, Hamming weight, intrinsic order, intrinsic order graph, subgraphs, subposets 1. Introduction Consider a system depending on an arbitrary number nof random Boolean variables. That is, the nbasic variables, x1,...,x n,ofthe system are assumed to be stochastic (non-deterministic), and they only take two possible values (either 0 or 1). We call such a system a complex stochastic Boolean system (CSBS). CSBSs often appear in many different knowledge areas, since the assumption “random Boolean variables” is satisfied very often in practice.
2IAENG TRANSACTIONS ON ENGINEERING TECHNOLOGIES Each one of the possible situations (outcomes) associated to a CSBS is given by a binary n-tuple of 0sand 1s, i.e., u=(u1,...,u n)∈{0,1}n and, from now on, we assume that the nrandom Boolean variables {xi}n i=1 are mutually independent. Hence, denoting Pr {xi=1}=pi,Pr {xi=0}=1−pi(1 ≤i≤n), the occurrence probability of each binary n-tuple, u=(u1,...,u n), can be computed as the product Pr {(u1,...,u n)}= n i=1 Pr {xi=ui}= n i=1 pui i(1 −pi)1−ui,(1.1) that is, Pr {(u1,...,u n)}is the product of factors piif ui=1,1-piif ui= 0. Throughout this paper, the binary n-tuples (u1,...,u n)of0sand 1s will be also called binary strings or bitstrings, and the probabilities p1,...,p nwill be also called basic probabilities. One of the most relevant questions in the analysis of CSBSs consists of ordering the binary strings (u1,...,u n)accordingtotheiroccurrence probabilities. For this purpose, in [Gonz´alez, 2002] we have established a simple, positional criterion (the so-called intrinsic order 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. The usual representation for the intrinsic order relation is the intrinsic order graph. In this context, the main goal of this paper is to state and derive some new properties of the intrinsic order graph, concerning the Hamming weights of the binary strings (i.e., the number of 1-bits in each binary ntuple). Some of these properties can be found in [Gonz´alez, 2012c], where the reader can also find a number of simple examples that illustrate the preliminary results presented in this paper. For this purpose, this paper has been organized as follows. In Section 2, we present some preliminary results about the intrinsic ordering and the intrinsic order graph, in order to make the presentation selfcontained. Section 3 is devoted to present new relations between the intrinsic ordering and the Hamming weight. In Section 4, we study the distribution of the Hamming weights of the 2nnodes in the intrinsic order graph. Finally, conclusions are presented in Section 5.
Labeling the Nodes in the Intrinsic Order Graph with their Weights 3 2. Intrinsic Ordering in CSBSs The Intrinsic Partial Order Relation 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. Theorem 2.1 Let n≥1.Letx1,...,x nbe nmutually independent Boolean variables whose parameters pi=Pr{xi=1}satisfy 0<p 1≤p2≤...≤pn≤1 2.(2.1) Then the probability of the n-tuple v=(v1,...,v n)∈{0,1}nis intrinsically less than or equal to the probability of the n-tuple u=(u1,...,u n)∈ {0,1}n(that is, for all set {pi}n i=1satisfying (2.1)) if and only if the matrix Mu v:= u1... u n v1... v n either has no 1 0columns, or for each 1 0column in Mu vthere exists (at least)one corresponding preceding 0 1column (IOC). Remark 2.2 In the following, we assume that the parameters pialways satisfy condition (2.1). The 0 1column preceding to each 1 0column is not required to be necessarily placed at the immediately previous position, but just at previous position. The term corresponding, used in Theorem 2.1, has the following meaning: For each two 1 0columns in matrix Mu v, there must exist (at least) two different 0 1columns preceding to each other. The matrix condition IOC, stated by Theorem 2.1 is called the intrinsic order criterion, because it is independent of the basic probabilities piand it only depends on the relative positions of the 0s and 1s in the binary n-tuples u, v. Theorem 2.1 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 uv(uv) 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,)onnBoolean variables, will be denoted by In. Definition 2.3 For all u, v ∈{0,1}n vuiff Pr {v}≤Pr {u}for all set {pi}n i=1 s.t. (2.1) iff Mu vsatisfies IOC.
4IAENG TRANSACTIONS ON ENGINEERING TECHNOLOGIES A Picture for the Intrinsic Ordering 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 uv. This means that uis intrinsically greater than vwith no other elements between them, i.e., uv ⇔uvand w∈{0,1}ns.t. uwv. 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.4 (Covering relation in In)Let n≥1and let u, v ∈ {0,1}n. Then uvif and only if the only columns of matrix Mu vdifferent from 0 0and 1 1are either its last column 0 1or just two columns, namely one 1 0column immediately preceded by one 0 1column, i.e., either Mu v=u1... u n−10 u1... u n−11(2.2) or there exists i(2 ≤i≤n)s.t. Mu v=u1... u i−201ui+1 ... u n u1... u i−210ui+1 ... u n.(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.1 (matrix description of the intrinsic order) or Theorem 2.4 (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. Note that 0 1(Theorem2.1). 0 | 1 Figure 1.1. The intrinsic order graph for n=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
Labeling the Nodes in the Intrinsic Order Graph with their Weights 5 building up In(for all n≥2) from I1(depicted in Figure 1.1), has been developed. Theorem 2.5 (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. 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. 0 | 1 0 | 1 | 2 | 3 0 | 1 | 2 | 34 | 5 | 6 | 7 0 | 1 | 2 | 34 | 58 || 69 || 710 | 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,meansthatuis intrinsically greater than v, i.e., uv. 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., uvand vu. The edgeless graph for a given graph is obtained by removing all its edges, keeping its nodes at the same positions [Diestel, 2005]. In Figures 1.3 & 1.4, the edgeless intrinsic order graphs of I5&I6, respectively, are depicted.
6IAENG TRANSACTIONS ON ENGINEERING TECHNOLOGIES 0 1 2 34 58 69 16 710 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 34 58 69 16 710 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 e.g., [Gonz´alez, 2002; Gonz´alez, 2003; Gonz´alez, 2006; Gonz´alez, 2007; Gonz´alez, 2010; Gonz´alez, 2012a; Gonz´alez, 2012b; Gonz´alez, 2012c; Gonz´alez, 2012d; Gonz´alez, et al, 2004]. 3. Weights and Intrinsic Ordering Now, we present some new relations between the intrinsic ordering and the Hamming weight. Let us denote by wH(u) the Hamming weight –or
Labeling the Nodes in the Intrinsic Order Graph with their Weights 7 weight, simply– of u(i.e., the number of 1-bits in u), i.e., wH(u):= n i=1 ui. Our starting point is the following necessary (but not sufficient) condition for intrinsic order (see [Gonz´alez, 2003] for the proof). uv⇒wH(u)≤wH(v) for all v∈{0,1}n.(3.1) However, the necessary condition for intrinsic order stated by Eq. (3.1) is not sufficient. That is, wH(u)≤wH(v)uv, as the following simple counter-example (indeed, the simplest one that one can find!) shows. Example 3.1 For n=3,u=4≡(1,0,0) ,v=3≡(0,1,1) , we have (see the digraph of I3in Figure 1.2) wH(4) = 1 <2=wH(3) . However 4 3,since matrix M4 3=100 011 does not satisfy IOC. In this context, two dual questions naturally arise. They are posed in the two subsections of this section. First, we need to set the following notations. Definition 3.2 For every binary n-tuple u∈{0,1}n,Cu(Cu, respectively) is the set of all binary n-tuples vwhose occurrence probabilities Pr {v} are always less (greater, respectively)than or equal to Pr {u}, i.e., those n-tuples vintrinsically less (greater, respectively)than or equal to u, i.e., Cu={v∈{0,1}n|Pr {u}≥Pr {v},∀{pi}n i=1 s.t. (2.1)} ={v∈{0,1}n|uv}, Cu={v∈{0,1}n|Pr {u}≤Pr {v},∀{pi}n i=1 s.t. (2.1)} ={v∈{0,1}n|uv}.
8IAENG TRANSACTIONS ON ENGINEERING TECHNOLOGIES Definition 3.3 For every binary n-tuple u∈{0,1}n,Hu(Hu, respectively) is the set of all binary n-tuples vwhose Hamming weights are less (greater, respectively)than or equal to the Hamming weight of u, i.e., Hu={v∈{0,1}n|wH(u)≥wH(v)}, Hu={v∈{0,1}n|wH(u)≤wH(v)}. When Greater Weight Corresponds to Less Probability Looking at the implication (3.1), the following question immediately arises. Question 3.1: We try to characterize the binary n-tuples ufor which the necessary condition (3.1) is also sufficient, i.e., uv⇔wH(u)≤wH(v),i.e., Cu=Hu. The following theorem provides the answer to this question, in a very simple way. Theorem 3.4 Let n≥1and u=(u1,...,u n)∈{0,1}nwith Hamming weight wH(u)=m(0 ≤m≤n). Then Cu=Hu if and only if either uis the zero n-tuple (m=0)or the m1-bits of u (m>0) are placed at the mright-most positions, i.e., if and only if u has the general pattern u=0,n−m ...,0,1,m ...,1≡2m−1,0≤m≤n, (3.2) where any (but not both !) of the above two subsets of bits grouped together can be omitted. Proof. Sufficient condition. We distinguish two cases: (i) If uis the zero n-tuple 0 ≡0,n ...,0,thenuis the maximum element for the intrinsic order (see, e.g., [Gonz´alez, 2012c]). Then C0={v∈{0,1}n|0v}={0,1}n ={v∈{0,1}n|wH(0) = 0 ≤wH(v)}=H0. (ii) If uis not the zero n-tuple, then uhas the pattern (3.2) with m>0. Let v∈Hu, i.e., let vlet a binary n-tuple with Hamming weight greater
Labeling the Nodes in the Intrinsic Order Graph with their Weights 9 than or equal to m(the Hamming weight of u). We distinguish two subcases: (ii)-(a) Suppose that the weight of vis wH(v)=m=wH(u). Then vhas exactly m1-bits and n−m0-bits. Call rthe number of 1-bits of vplaced among the mright-most positions (max {0,2m−n}≤ r≤m). Obviously, vhas r1-bits and m−r0-bits placed among the m right-most positions, and also it has m−r1-bits and n−2m+r0-bits placed among the n−mleft-most positions. These are the positions of the r+(m−r)+(m−r)+(n−2m+r)=m+(n−m)=n bits of the binary n-tuple v. Hence, matrix Mu vhas exactly m−r1 0columns (all placed among the mright-most positions) and exactly m−r0 1columns (all placed among the n−mleft-most positions). Thus, Mu vsatisfies IOC and then uv, i.e., v∈Cu. So, for this case (ii)-(a), we have proved that {v∈{0,1}n|wH(v)=wH(u)=m}⊆Cu(3.3) (ii)-(b) Suppose that the weight of vis wH(v)=m+p>m=wH(u)(0<p≤n−m). Then define a new binary n-tuple sas follows. First, select any p1-bits in v(say, for instance, vi1=···=vip= 1). Second, sis constructed by changing these p1-bits of vinto 0-bits, assigning to the remainder n−p bits of sthe same values as the ones of v. Formally, s=(s1,...,s n)is defined by si=0ifi∈{i1,...,i p}, viif i/∈{i1,...,i p}. On one hand, ussince wH(s)=wH(v)−p=m=wH(u) and then we can apply case (ii)-(a) to s. On the other hand, svsince matrix Ms vhas p0 1columns (placed at positions i1,...,i p), while its n−preminder columns are either 0 0 or 1 1. Hence Ms vhas no 1 0columns, so that it satisfies IOC. Finally, from the transitive property of the intrinsic order, we derive usand sv⇒uv, i.e., v∈Cu.