# Complex Stochastic Boolean Systems: Comparing Bitstrings with the Same Hamming Weight

Authors: Luis González
Journal: Journal of Complex Systems
 (2014)

---

## Abstract

A complex stochastic Boolean system (CSBS) is a complex system depending on an arbitrarily large numbern of random Boolean variables. CSBSs arise in many different areas of science and engineering. A proper mathematical model for the analysis of such systems is based on the intrinsic order: a partial order relation defined on the set 0,1
n of all binary n-tuples of 0s and 1s. The intrinsic order enables one to compare the occurrence probabilities of two given binary n-tuples with no need to compute them, simply looking at the relative positions of their 0s and 1s. Regarding the analysis of CSBSs, the intrinsic order reduces the complexity of the problem from exponential (2
n binary n-tuples) to linear (n Boolean variables). In this paper, using the intrinsic ordering, we compare the occurrence probabilities of any two  binary n-tuples having the same number of 1-bits (i.e., the same Hamming weight). Our results can be applied to any CSBS with mutually independent Boolean variables.


---

## Body

## 1. Introduction

This paper deals with the mathematical modeling of a special kind of complex systems, namely, those depending on an arbitrary numbern of random Boolean variables. That is, the n basic variables x
1
,
…
,
x
n of the system are assumed to be stochastic and they only take two possible values, 0 or 1, with probabilities
(1)
Pr
{
x
i
=
1
}
=
p
i
,
Pr
{
x
i
=
0
}
=
1
-
p
i
,
where the values {
p
i
}
i
=
1
n will be referred to as the basic probabilities or parameters of the system.We call such a system a complex stochastic Boolean system (CSBS). These systems can be found in many different scientific or engineering areas like mechanical engineering, meteorology and climatology, nuclear physics, complex systems analysis, operations research, and so forth. CSBSs also arise very often when analyzing system safety in reliability engineering and risk analysis; see, for example, [1–3].Each one of the2
n possible outcomes associated with a CSBS is given by a binary n-tuple (or bitstring of length n) u
=
(
u
1
,
…
,
u
n
)
∈
{
0,1
}
n, and it has its own occurrence probability Pr
{
u
}.Throughout this paper, then Boolean variables x
i of the CSBS are assumed to be mutually independent, so that the occurrence probability of a given binary string u of length n can be easily computed as
(2)
Pr
{
u
}
=
∏
i
=
1
n
p
i
u
i
(
1
-
p
i
)
1
-
u
i
∀
u
∈
{
0,1
}
n
;
that is, Pr
{
u
} is the product of factors p
i if u
i
=
1, 1
-
p
i if u
i
=
0.As an example of CSBS, we can consider a technical system like the accumulator system of a pressured water reactor in a nuclear power plant, taken from [4]. This technical system depends on n
=
83 mutually independent basic components x
1
,
…
,
x
83. Assuming that x
i
=
1 if component i fails, x
i
=
0 otherwise; then the failure and working probabilities of component i will be Pr
{
x
i
=
1
}
=
p
i, Pr
{
x
i
=
0
}
=
1
-
p
i, respectively. The probability p
i of failure of each basic component i
(
1
≤
i
≤
83
) is given, so that all basic probabilities p
i are known.Thus, this accumulator system can be considered as a CSBS where each one of its2
83 system binary states (i.e., binary 83-tuple (
u
1
,
…
,
u
83
)
∈
{
0,1
}
83) describes the current situation of its 83 basic components (failing or working). For instance, the binary 83-tuple
(3)
u
=
(
1
,
…
⌣
23
,
1,0
,
…
⌣
60
,
0
)
represents the system state for which the first 23 components fail, while the last 60 components work. Moreover, the occurrence probability of the binary state u can be immediately computed using (2) as follows:
(4)
Pr
{
u
}
=
∏
i
=
1
23
p
i
∏
i
=
24
83
(
1
-
p
i
)
.Real-world CSBSs arising in many different engineering areas, like the above-mentioned accumulator system, are typically analyzed in many works dealing with system safety and reliability theory. In this context, let us mention that formula (2) for computing the binary n-tuple probabilities associated with a CSBS on n-independent Boolean variables (basic components) can be seen as a particular case of Theorem 1 in [5]. In that theorem, the author considers a coherent or noncoherent n component system with dependent or independent failures and proves that the reliability/unreliability function G
(
x
) in the system is a multilinear function of the vector x of all conditional component (success/failure) probabilities. Let us recall that a system is said to be coherent if its structure (Boolean) function ϕ satisfies [5]
(5)
ϕ
(
0
,
…
,
0
)
=
0
,
ϕ
(
1
,
…
,
1
)
=
1
,
and if u
,
v
∈
{
0,1
}
n are such that u
i
≤
v
i for all i
=
1,2
,
…
,
n, and u
i
<
v
i for some i, then
(6)
ϕ
(
u
1
,
…
,
u
n
)
<
ϕ
(
v
1
,
…
,
v
n
)
.Moreover, we must highlight that the assumption of independent failures (an essential hypothesis for formula (2) and for the results presented in our paper), while being classical and advantageous from a calculation point of view, is a bit restrictive for realistic applications. In this respect, in [6] one can find an illustration of the issues when realistic systems are addressed.The behavior of a CSBS is determined by the ordering between the current values of the2
n associated binary n-tuple probabilities Pr
{
u
}. Due to the exponential complexity of the problem, computing all these 2
n probabilities—by using (2)—and ordering them in decreasing or increasing order of their values is only possible in practice for small values of the number n of basic variables. However, for large values of n, it is necessary to use alternative procedures to compare the binary string probabilities. For this purpose, a simple, positional criterion to order binary n-tuple probabilities is used. The so-called intrinsic order criterion (IOC) enables one to compare (to order) the occurrence probabilities Pr
{
u
}, Pr
{
v
} of two given binary n-tuples u, v without the need to compute them, simply looking at the relative positions of their 0s and 1s. IOC was first described in [7], and it naturally leads to a partial order relation on the set {
0,1
}
n of all the binary strings of length n. The so-called intrinsic order provides a unified approach for the analysis and modeling of CSBSs.The most useful representation of a CSBS is the intrinsic order graph: a symmetric directed graph on2
n vertices, displaying all the 2
n binary n-tuples from top to bottom in decreasing order of their occurrence probabilities.In this context, the main goal of this paper is to compare the occurrence probabilities of two binary strings with the same lengthn and containing the same number of 1-bits. Our results will be derived from IOC, as well as from other properties of the intrinsic ordering, and they will be illustrated with the intrinsic order graph.For this purpose, this paper has been organized as follows. Section2 contains all the background about the intrinsic order relation, required to make this paper self-contained. Section 3 is devoted to present our new results concerning the comparison between the occurrence probabilities of two binary strings with the same number of 1-bits. Finally, conclusions are presented in Section 4.


## 2. Preliminaries

Let us start this section with some basic concepts and notations which will be used in the rest of the paper.Definition 1.
Letn
≥
1 and let u
=
(
u
1
,
…
,
u
n
)
∈
{
0,1
}
n be a binary n-tuple. Then we have the following.(i)
The decimal equivalent ofu will be denoted by u
(
10 (to avoid confusion with the 10th component u
10 of the binary vector u); that is,
(7)
u
(
10
=
∑
i
=
1
n
2
n
-
i
u
i
.
In what follows, we indistinctly denote then-tuple u
∈
{
0,1
}
n by its binary representation (
u
1
,
…
,
u
n
) or by its decimal representation u
(
10, and we use the symbol “≡” to denote the conversion between both representations; that is,
(8)
(
u
1
,
…
,
u
n
)
≡
u
(
10
.
(ii)
The Hamming weight (or simply the weight)w
H
(
u
) of u is the number of 1-bits in u; that is,
(9)
w
H
(
u
)
=
∑
i
=
1
n
u
i
.
(iii)
The complementaryn-tuple of u is the n-tuple obtained by changing all its 0s to 1s and vice versa; that is,
(10)
(
u
1
,
…
,
u
n
)
c
=
(
1
-
u
1
,
…
,
1
-
u
n
)
.
Note that two binaryn-tuples are complementary if and only if they sum up to (
1
,
…
⌣
n
,
1
)
≡
2
n
-
1. Then, using the decimal numbering, the complementary n-tuple u
c of a binary n-tuple u is given by
(11)
u
(
10
c
=
(
2
n
-
1
)
-
u
(
10
.Example 2.
Letn
=
5 and u
=
(
0,1
,
1,0
,
1
)
∈
{
0,1
}
5. Then (i)
(
0,1
,
1,0
,
1
)
≡
2
0
+
2
2
+
2
3
=
13
=
u
(
10;
(ii)
w
H
(
0,1
,
1,0
,
1
)
=
3;
(iii)
1
3
c
≡
(
0,1
,
1,0
,
1
)
c
=
(
1,0
,
0,1
,
0
)
≡
18;
13
+
1
3
c
=
13
+
18
=
31
=
2
5
-
1.


### 2.1. The Intrinsic Order Criterion

According to (2), the ordering between two given binary string probabilities Pr
(
u
) and Pr
(
v
) depends, in general, on the parameters p
i, as the following simple example shows.Example 3.
Letn
=
3, u
=
(
0,1
,
1
), and v
=
(
1,0
,
0
). Using (2), we have
(12)
p
1
=
0.1
,
p
2
=
0.2
,
p
3
=
0.3
:
Pr
{
u
}
=
0.054
<
Pr
{
v
}
=
0.056
,
p
1
=
0.2
,
p
2
=
0.3
,
p
3
=
0.4
:
Pr
{
u
}
=
0.096
>
Pr
{
v
}
=
0.084
.However, assuming a simple (but not restrictive in practice) hypothesis on the parametersp
i, we can assure that for some pairs of binary n-tuples, the ordering between their occurrence probabilities is independent of the basic probabilities p
i. More precisely, as mentioned in Section 1, to overcome the exponential complexity in the problem of computing and sorting the 2
n binary string probabilities, the following simple positional criterion has been introduced in [7].Theorem 4 (the intrinsic order theorem).
Letn
≥
1. Let x
1
,
…
,
x
n be n mutually independent stochastic Boolean variables whose parameters p
i
=
Pr
{
x
i
=
1
} satisfy
(13)
0
<
p
1
≤
p
2
≤
⋯
≤
p
n
≤
1
2
.
Then the probability of the binary n-tuple v
=
(
v
1
,
…
,
v
n
) is (intrinsically) less than or equal to the probability of the binary n-tuple u
=
(
u
1
,
…
,
u
n
) (here, “intrinsically” means: for all set {
p
i
}
i
=
1
n satisfying (13)) if and only if either the matrix
(14)
M
v
u
∶
=
(
u
1
⋯
u
n
v
1
⋯
v
n
)
has no (
1
0
) columns or for each (
1
0
) column in M
v
u there exists (at least) one corresponding preceding (
0
1
) column (IOC).Remark 5.
In the following, we assume that the parametersp
i always satisfy condition (13). Note that this hypothesis is not restrictive for practical applications because for any index i such that p
i
>
1
/
2, we only need to consider the variable x
i
-
=
1
-
x
i, instead of x
i. Next, we order the n new Boolean variables in increasing order of their probabilities. This reduces the complexity in sorting tasks from exponential (ordering 2
n binary n-tuple probabilities) to linear (ordering n Boolean variable probabilities).Remark 6.
The(
0
1
) column preceding each (
1
0
) column is not required to be necessarily placed at the immediately previous position, but just at previous position.Remark 7.
The term “corresponding,” used in Theorem4, has the following meaning: for each two (
1
0
) columns in matrix M
v
u there must exist (at least) two different (
0
1
) columns preceding each other. Formally, there must exist (at least) one injective precedence map from the set of (
1
0
) columns of M
v
u onto the set of its (
0
1
) columns that assigns to each (
1
0
) column a (
0
1
) column preceding it. In other words, for each (
1
0
) column in matrix M
v
u, the number of preceding (
0
1
) columns must be strictly greater than the number of preceding (
1
0
) columns.The matrix condition IOC, stated by Theorem4, is called the intrinsic order criterion because it is independent of the basic probabilities p
i, and it only depends on the relative positions of the bits in the binary n-tuples u and v to be compared. Theorem 4 naturally leads to the following partial order relation on the set {
0,1
}
n; see [7]. The so-called intrinsic order will be denoted by “⪯”, and when v
⪯
u we will say that v is intrinsically less than or equal to u.Definition 8.
For allu
,
v
∈
{
0,1
}
n,
(15)
v
⪯
u
iff
Pr
{
v
}
≤
Pr
{
u
}
for
all
set
{
p
i
}
i
=
1
n
set
{
p
i
}
i
=
1
n
s
.
t
.
(
13
)
iff
M
v
u
satisfies
IOC
.
From now on, the partially ordered set (poset, for short) (
{
0,1
}
n
,
⪯
) will be denoted by I
n.Example 9.
Forn
=
3, we have 3
≡
(
0,1
,
1
)
⋠
4
≡
(
1,0
,
0
) and 4
≡
(
1,0
,
0
)
⋠
3
≡
(
0,1
,
1
) because the matrices
(16)
M
3
4
=
(
1
0
0
0
1
1
)
,
M
4
3
=
(
0
1
1
1
0
0
)
do not satisfy IOC (Remark 7). Thus, (
0,1
,
1
) and(
1,0
,
0
) are incomparable by intrinsic order; that is, the ordering between the two probabilities Pr
{
(
0,1
,
1
)
} and Pr
{
(
1,0
,
0
)
} depends on the current values of parameters {
p
i
}
i
=
1
3, as Example 3 has shown.Example 10.
Forn
=
4, we have 3
≡
(
0,0
,
1,1
)
≻
12
≡
(
1,1
,
0,0
) because matrix
(17)
M
12
3
=
(
0
0
1
1
1
1
0
0
)
satisfies IOC (Remark 6). Thus, for all {
p
i
}
i
=
1
4 s.t. (13),
(18)
Pr
{
(
1,1
,
0,0
)
}
≤
Pr
{
(
0,0
,
1,1
)
}
.Example 11.
Forn
=
1007, we have
(19)
86
≡
(
0
,

…
⌣
1000
,

0
,

1
,

0
,

1
,

0
,

1
,

1
,

0
)
⪯
35
≡
(
0
,

…
⌣
1000
,

0
,

0
,

1
,

0
,

0
,

0
,

1
,

1
)
because matrix
(20)
M
86
35
=
(
0
…
⌣
1000
0
0
1
0
0
0
1
1
0
…
⌣
1000
0
1
0
1
0
1
1
0
)
satisfies IOC (Remark 6). Thus, for all {
p
i
}
i
=
1
1007 s.t. (13),
(21)
Pr
{
(
0
,
…
⌣
1000
,
0,1
,
0,1
,
0,1
,
1,0
)
}
≤
Pr
{
(
0
,
…
⌣
1000
,
0,0
,
1,0
,
0,0
,
1,1
)
}
.Example 12.
For alln
≥
1, the binary n-tuples
(22)
(
0
,
…
⌣
n
,
0
)
≡
0
,
(
1
,
…
⌣
n
,
1
)
≡
2
n
-
1
are the maximum and minimum elements, respectively, in the poset I
n. Indeed, for every binary n-tuple (
u
1
,
…
,
u
n
)
∈
{
0,1
}
n, both matrices
(23)
(
0
⋯
0
u
1
⋯
u
n
)
,
(
u
1
⋯
u
n
1
⋯
1
)
satisfy IOC, since they have no (
1
0
) columns! Thus, for all binary n-tuples (
u
1
,
…
,
u
n
)
∈
{
0,1
}
n, and for all {
p
i
}
i
=
1
n s.t. (13),
(24)
Pr
{
(
1
,
…
⌣
n
,
1
)
}
≤
Pr
{
(
u
1
,
…
,
u
n
)
}
≤
Pr
{
(
0
,
…
⌣
n
,
0
)
}
.Many different properties of the intrinsic order relation can be derived from its simple matrix description IOC. For the purpose of this paper, it suffices to recall here the following necessary (but not sufficient) condition for intrinsic order.Note that ifu
≽
v, then there must exist (at least) one injective precedence map from the set of (
1
0
) columns of M
v
u onto the set of its (
0
1
) columns (Remark 7). Then in matrix M
v
u the number of (
1
0
) columns must be less than or equal to the number of (
0
1
) columns. But this is equivalent to saying that the number of 1-bits in u must be less than or equal to the number of 1-bits in v. That isCorollary 13.
The intrinsic order respects the Hamming weight. More precisely, for all,v
∈
{
0,1
}
n,
(25)
u
≽
v
⟹
w
H
(
u
)
≤
w
H
(
v
)
.The converse of Corollary13 is false, as the following two simple counterexamples (indeed, the simplest ones that one can find) show.(i)
Forn
=
2, u
=
2
≡
(
1,0
), and v
=
1
≡
(
0,1
), we have
(26)
w
H
(
u
)
=
1
=
w
H
(
v
)
,
u
⋡
v
since matrix(27)
M
1
2
=
(
1
0
0
1
)
does not satisfy IOC.
(ii)
Forn
=
3 and for u
=
4
≡
(
1,0
,
0
), v
=
3
≡
(
0,1
,
1
), we have (see Example 9)
(28)
w
H
(
u
)
=
1
<
2
=
w
H
(
v
)
,
u
⋡
v
.


### 2.2. The Intrinsic Order Graph

To finish this section, we present the graphical representation of the posetI
n. As it is well known, the usual representation for a poset is its Hasse diagram (see [8] for more details about posets and their diagrams). Let us recall that, for a poset (
P
,
≤
) and for x
,
y
∈
P, we say that y covers x if x
<
y with no other elements between them. The Hasse diagram of a finite poset (
P
,
≤
) is the graph whose vertices are the elements of P and whose edges are the cover relations (with the convention that if y covers x, then y is drawn above x). The Hasse diagram of our poset I
n will be also called the intrinsic order graph for n variables, denoted as well by I
n. So, this is a directed graph (digraph, for short) whose vertices are the 2
n binary n-tuples of 0s and 1s, and whose edges go downward from u to v whenever u covers v (denoted by u
⊳
v); that is,
(29)
u
⊳
v
iff
u
≻
v
and
there
is
no
w
∈
{
0,1
}
n
and
there
is
no
w
∈
{
0,1
}
n
s
.
t
.
u
≻
w
≻
v
.For small values ofn, the intrinsic order graph I
n can be directly constructed by using Theorem 4. For instance, for n
=
1, the Hasse diagram of I
1
=
(
{
0,1
}
,
⪯
) is shown in Figure 1. Indeed, using Theorem 4, we have that 0
≻
1, since matrix (
1
0
) has no (
1
0
) columns! So, I
1 has a downward edge from 0 to 1, and this is in accordance with the fact that
(30)
Pr
{
0
}
=
1
-
p
1
≥
p
1
=
Pr
{
1
}
,
since p
1
≤
1
/
2 due to (13).Figure 1
The intrinsic order graph forn
=
1.However, for large values ofn, a more efficient method is needed. For this purpose, in [9] the following algorithm for iteratively building up I
n (for all n
≥
2) from I
1 (depicted in Figure 1) has been developed.Theorem 14 (building upI
n from I
1).
Letn
≥
2. The graph of the poset I
n
=
{
0
,
…
,
2
n
-
1
} (on 2
n nodes) can be drawn simply by adding to the graph of the poset I
n
-
1
=
{
0
,
…
,
2
n
-
1
-
1
} (on 2
n
-
1 nodes) its isomorphic copy 2
n
-
1
+
I
n
-
1
=
{
2
n
-
1
,
…
,
2
n
-
1
} (on 2
n
-
1 nodes). This addition must be performed by placing the powers of 2 at consecutive levels in the Hasse diagram of I
n. Finally, the edges connecting one vertex u of I
n
-
1 with the other vertex v of 2
n
-
1
+
I
n
-
1 are given by the set of vertex pairs
(31)
{
(
u
,
v
)
=
(
u
(
10
,
2
n
-
2
+
u
(
10
)
∣
2
n
-
2
≤
u
(
10
≤
2
n
-
1
-
1
}
.In Figure2, the iterative process described in Theorem 14 is illustrated by showing the intrinsic order graphs for n
=
1,2
,
3,4 from left to right. Basically, to draw I
n, we first add to I
n
-
1 its isomorphic copy 2
n
-
1
+
I
n
-
1, and 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.” Hence, the intrinsic order graph I
n is a fractal or self-similar graph in the sense that it can be recursively constructed from the previous (
I
1
,
I
2
,
…
,
I
n
-
1
) by some operations which preserve self-similarity; that is, it appears similar at different scales (orders). In Figure 3, the intrinsic order graphs for n
=
3,4 are depicted using the binary representation instead of the decimal representation of their nodes.Figure 2
The intrinsic order graphs forn
=
1
,
2
,
3
,
4 using decimal representation.Figure 3
The intrinsic order graphs forn
=
3
,
4 using binary representation.Note thatI
n has a downward path from u to v if and only if u
≻
v. For instance, looking at the digraph I
4 (the right-most one in Figure 2), we confirm that 3
≻
12, as shown in Example 10.On the contrary, each pair(
u
,
v
) of nonconnected vertices in the digraph of I
n, either by one edge or by a longer downward path, means that u and v are incomparable by intrinsic order; that is, u
⋡
v and v
⋡
u. For instance, looking at the digraph I
3 (the third one from the left in Figure 2), we confirm that 3
⋡
4 and 4
⋡
3, as shown in Example 3 or in Example 9.Also, looking at any of the digraphs in Figure2, we can confirm Corollary 13, as well as the fact that 0 and 2
n
-
1 are the maximum and minimum elements, respectively, in the poset I
n, as shown in Example 12.Recall that two binaryn-tuples are complementary if and only if their decimal equivalents sum up to 2
n
-
1 (see Definition 1-(iii)). Hence, one can observe that any two complementary n-tuples are placed at symmetric positions (with respect to the central point) in the intrinsic order graph I
n. For instance, this is the case in the graph I
4 for the following pairs of binary 4-tuples (see the right-most graphs in Figures 2 and 3):
(32)
u
=
(
0,0
,
1,1
)
≡
3
,
u
c
=
(
1,1
,
0,0
)
≡
12
,
u
+
u
c
=
3
+
12
=
15
=
2
4
-
1
,
u
=
(
0,1
,
1,0
)
≡
6
,
u
c
=
(
1,0
,
0,1
)
≡
9
,
u
+
u
c
=
6
+
9
=
15
=
2
4
-
1
,
u
=
(
0,1
,
1,1
)
≡
7
,
u
c
=
(
1,0
,
0,0
)
≡
8
,
u
+
u
c
=
7
+
8
=
15
=
2
4
-
1
.The edgeless graph associated with a given graph is obtained by removing all its edges, keeping its (isolated) nodes at the same positions. In Figures4 and 5, the edgeless intrinsic order graphs for I
5 and I
6, respectively, are depicted.Figure 4
The edgeless intrinsic order graph forn
=
5.Figure 5
The edgeless intrinsic order graph forn
=
6.For further theoretical properties and practical applications of the intrinsic order and the intrinsic order graph, we refer the reader to [7, 9–13] and to the references therein.


## 2.1. The Intrinsic Order Criterion

According to (2), the ordering between two given binary string probabilities Pr
(
u
) and Pr
(
v
) depends, in general, on the parameters p
i, as the following simple example shows.Example 3.
Letn
=
3, u
=
(
0,1
,
1
), and v
=
(
1,0
,
0
). Using (2), we have
(12)
p
1
=
0.1
,
p
2
=
0.2
,
p
3
=
0.3
:
Pr
{
u
}
=
0.054
<
Pr
{
v
}
=
0.056
,
p
1
=
0.2
,
p
2
=
0.3
,
p
3
=
0.4
:
Pr
{
u
}
=
0.096
>
Pr
{
v
}
=
0.084
.However, assuming a simple (but not restrictive in practice) hypothesis on the parametersp
i, we can assure that for some pairs of binary n-tuples, the ordering between their occurrence probabilities is independent of the basic probabilities p
i. More precisely, as mentioned in Section 1, to overcome the exponential complexity in the problem of computing and sorting the 2
n binary string probabilities, the following simple positional criterion has been introduced in [7].Theorem 4 (the intrinsic order theorem).
Letn
≥
1. Let x
1
,
…
,
x
n be n mutually independent stochastic Boolean variables whose parameters p
i
=
Pr
{
x
i
=
1
} satisfy
(13)
0
<
p
1
≤
p
2
≤
⋯
≤
p
n
≤
1
2
.
Then the probability of the binary n-tuple v
=
(
v
1
,
…
,
v
n
) is (intrinsically) less than or equal to the probability of the binary n-tuple u
=
(
u
1
,
…
,
u
n
) (here, “intrinsically” means: for all set {
p
i
}
i
=
1
n satisfying (13)) if and only if either the matrix
(14)
M
v
u
∶
=
(
u
1
⋯
u
n
v
1
⋯
v
n
)
has no (
1
0
) columns or for each (
1
0
) column in M
v
u there exists (at least) one corresponding preceding (
0
1
) column (IOC).Remark 5.
In the following, we assume that the parametersp
i always satisfy condition (13). Note that this hypothesis is not restrictive for practical applications because for any index i such that p
i
>
1
/
2, we only need to consider the variable x
i
-
=
1
-
x
i, instead of x
i. Next, we order the n new Boolean variables in increasing order of their probabilities. This reduces the complexity in sorting tasks from exponential (ordering 2
n binary n-tuple probabilities) to linear (ordering n Boolean variable probabilities).Remark 6.
The(
0
1
) column preceding each (
1
0
) column is not required to be necessarily placed at the immediately previous position, but just at previous position.Remark 7.
The term “corresponding,” used in Theorem4, has the following meaning: for each two (
1
0
) columns in matrix M
v
u there must exist (at least) two different (
0
1
) columns preceding each other. Formally, there must exist (at least) one injective precedence map from the set of (
1
0
) columns of M
v
u onto the set of its (
0
1
) columns that assigns to each (
1
0
) column a (
0
1
) column preceding it. In other words, for each (
1
0
) column in matrix M
v
u, the number of preceding (
0
1
) columns must be strictly greater than the number of preceding (
1
0
) columns.The matrix condition IOC, stated by Theorem4, is called the intrinsic order criterion because it is independent of the basic probabilities p
i, and it only depends on the relative positions of the bits in the binary n-tuples u and v to be compared. Theorem 4 naturally leads to the following partial order relation on the set {
0,1
}
n; see [7]. The so-called intrinsic order will be denoted by “⪯”, and when v
⪯
u we will say that v is intrinsically less than or equal to u.Definition 8.
For allu
,
v
∈
{
0,1
}
n,
(15)
v
⪯
u
iff
Pr
{
v
}
≤
Pr
{
u
}
for
all
set
{
p
i
}
i
=
1
n
set
{
p
i
}
i
=
1
n
s
.
t
.
(
13
)
iff
M
v
u
satisfies
IOC
.
From now on, the partially ordered set (poset, for short) (
{
0,1
}
n
,
⪯
) will be denoted by I
n.Example 9.
Forn
=
3, we have 3
≡
(
0,1
,
1
)
⋠
4
≡
(
1,0
,
0
) and 4
≡
(
1,0
,
0
)
⋠
3
≡
(
0,1
,
1
) because the matrices
(16)
M
3
4
=
(
1
0
0
0
1
1
)
,
M
4
3
=
(
0
1
1
1
0
0
)
do not satisfy IOC (Remark 7). Thus, (
0,1
,
1
) and(
1,0
,
0
) are incomparable by intrinsic order; that is, the ordering between the two probabilities Pr
{
(
0,1
,
1
)
} and Pr
{
(
1,0
,
0
)
} depends on the current values of parameters {
p
i
}
i
=
1
3, as Example 3 has shown.Example 10.
Forn
=
4, we have 3
≡
(
0,0
,
1,1
)
≻
12
≡
(
1,1
,
0,0
) because matrix
(17)
M
12
3
=
(
0
0
1
1
1
1
0
0
)
satisfies IOC (Remark 6). Thus, for all {
p
i
}
i
=
1
4 s.t. (13),
(18)
Pr
{
(
1,1
,
0,0
)
}
≤
Pr
{
(
0,0
,
1,1
)
}
.Example 11.
Forn
=
1007, we have
(19)
86
≡
(
0
,

…
⌣
1000
,

0
,

1
,

0
,

1
,

0
,

1
,

1
,

0
)
⪯
35
≡
(
0
,

…
⌣
1000
,

0
,

0
,

1
,

0
,

0
,

0
,

1
,

1
)
because matrix
(20)
M
86
35
=
(
0
…
⌣
1000
0
0
1
0
0
0
1
1
0
…
⌣
1000
0
1
0
1
0
1
1
0
)
satisfies IOC (Remark 6). Thus, for all {
p
i
}
i
=
1
1007 s.t. (13),
(21)
Pr
{
(
0
,
…
⌣
1000
,
0,1
,
0,1
,
0,1
,
1,0
)
}
≤
Pr
{
(
0
,
…
⌣
1000
,
0,0
,
1,0
,
0,0
,
1,1
)
}
.Example 12.
For alln
≥
1, the binary n-tuples
(22)
(
0
,
…
⌣
n
,
0
)
≡
0
,
(
1
,
…
⌣
n
,
1
)
≡
2
n
-
1
are the maximum and minimum elements, respectively, in the poset I
n. Indeed, for every binary n-tuple (
u
1
,
…
,
u
n
)
∈
{
0,1
}
n, both matrices
(23)
(
0
⋯
0
u
1
⋯
u
n
)
,
(
u
1
⋯
u
n
1
⋯
1
)
satisfy IOC, since they have no (
1
0
) columns! Thus, for all binary n-tuples (
u
1
,
…
,
u
n
)
∈
{
0,1
}
n, and for all {
p
i
}
i
=
1
n s.t. (13),
(24)
Pr
{
(
1
,
…
⌣
n
,
1
)
}
≤
Pr
{
(
u
1
,
…
,
u
n
)
}
≤
Pr
{
(
0
,
…
⌣
n
,
0
)
}
.Many different properties of the intrinsic order relation can be derived from its simple matrix description IOC. For the purpose of this paper, it suffices to recall here the following necessary (but not sufficient) condition for intrinsic order.Note that ifu
≽
v, then there must exist (at least) one injective precedence map from the set of (
1
0
) columns of M
v
u onto the set of its (
0
1
) columns (Remark 7). Then in matrix M
v
u the number of (
1
0
) columns must be less than or equal to the number of (
0
1
) columns. But this is equivalent to saying that the number of 1-bits in u must be less than or equal to the number of 1-bits in v. That isCorollary 13.
The intrinsic order respects the Hamming weight. More precisely, for all,v
∈
{
0,1
}
n,
(25)
u
≽
v
⟹
w
H
(
u
)
≤
w
H
(
v
)
.The converse of Corollary13 is false, as the following two simple counterexamples (indeed, the simplest ones that one can find) show.(i)
Forn
=
2, u
=
2
≡
(
1,0
), and v
=
1
≡
(
0,1
), we have
(26)
w
H
(
u
)
=
1
=
w
H
(
v
)
,
u
⋡
v
since matrix(27)
M
1
2
=
(
1
0
0
1
)
does not satisfy IOC.
(ii)
Forn
=
3 and for u
=
4
≡
(
1,0
,
0
), v
=
3
≡
(
0,1
,
1
), we have (see Example 9)
(28)
w
H
(
u
)
=
1
<
2
=
w
H
(
v
)
,
u
⋡
v
.


## 2.2. The Intrinsic Order Graph

To finish this section, we present the graphical representation of the posetI
n. As it is well known, the usual representation for a poset is its Hasse diagram (see [8] for more details about posets and their diagrams). Let us recall that, for a poset (
P
,
≤
) and for x
,
y
∈
P, we say that y covers x if x
<
y with no other elements between them. The Hasse diagram of a finite poset (
P
,
≤
) is the graph whose vertices are the elements of P and whose edges are the cover relations (with the convention that if y covers x, then y is drawn above x). The Hasse diagram of our poset I
n will be also called the intrinsic order graph for n variables, denoted as well by I
n. So, this is a directed graph (digraph, for short) whose vertices are the 2
n binary n-tuples of 0s and 1s, and whose edges go downward from u to v whenever u covers v (denoted by u
⊳
v); that is,
(29)
u
⊳
v
iff
u
≻
v
and
there
is
no
w
∈
{
0,1
}
n
and
there
is
no
w
∈
{
0,1
}
n
s
.
t
.
u
≻
w
≻
v
.For small values ofn, the intrinsic order graph I
n can be directly constructed by using Theorem 4. For instance, for n
=
1, the Hasse diagram of I
1
=
(
{
0,1
}
,
⪯
) is shown in Figure 1. Indeed, using Theorem 4, we have that 0
≻
1, since matrix (
1
0
) has no (
1
0
) columns! So, I
1 has a downward edge from 0 to 1, and this is in accordance with the fact that
(30)
Pr
{
0
}
=
1
-
p
1
≥
p
1
=
Pr
{
1
}
,
since p
1
≤
1
/
2 due to (13).Figure 1
The intrinsic order graph forn
=
1.However, for large values ofn, a more efficient method is needed. For this purpose, in [9] the following algorithm for iteratively building up I
n (for all n
≥
2) from I
1 (depicted in Figure 1) has been developed.Theorem 14 (building upI
n from I
1).
Letn
≥
2. The graph of the poset I
n
=
{
0
,
…
,
2
n
-
1
} (on 2
n nodes) can be drawn simply by adding to the graph of the poset I
n
-
1
=
{
0
,
…
,
2
n
-
1
-
1
} (on 2
n
-
1 nodes) its isomorphic copy 2
n
-
1
+
I
n
-
1
=
{
2
n
-
1
,
…
,
2
n
-
1
} (on 2
n
-
1 nodes). This addition must be performed by placing the powers of 2 at consecutive levels in the Hasse diagram of I
n. Finally, the edges connecting one vertex u of I
n
-
1 with the other vertex v of 2
n
-
1
+
I
n
-
1 are given by the set of vertex pairs
(31)
{
(
u
,
v
)
=
(
u
(
10
,
2
n
-
2
+
u
(
10
)
∣
2
n
-
2
≤
u
(
10
≤
2
n
-
1
-
1
}
.In Figure2, the iterative process described in Theorem 14 is illustrated by showing the intrinsic order graphs for n
=
1,2
,
3,4 from left to right. Basically, to draw I
n, we first add to I
n
-
1 its isomorphic copy 2
n
-
1
+
I
n
-
1, and 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.” Hence, the intrinsic order graph I
n is a fractal or self-similar graph in the sense that it can be recursively constructed from the previous (
I
1
,
I
2
,
…
,
I
n
-
1
) by some operations which preserve self-similarity; that is, it appears similar at different scales (orders). In Figure 3, the intrinsic order graphs for n
=
3,4 are depicted using the binary representation instead of the decimal representation of their nodes.Figure 2
The intrinsic order graphs forn
=
1
,
2
,
3
,
4 using decimal representation.Figure 3
The intrinsic order graphs forn
=
3
,
4 using binary representation.Note thatI
n has a downward path from u to v if and only if u
≻
v. For instance, looking at the digraph I
4 (the right-most one in Figure 2), we confirm that 3
≻
12, as shown in Example 10.On the contrary, each pair(
u
,
v
) of nonconnected vertices in the digraph of I
n, either by one edge or by a longer downward path, means that u and v are incomparable by intrinsic order; that is, u
⋡
v and v
⋡
u. For instance, looking at the digraph I
3 (the third one from the left in Figure 2), we confirm that 3
⋡
4 and 4
⋡
3, as shown in Example 3 or in Example 9.Also, looking at any of the digraphs in Figure2, we can confirm Corollary 13, as well as the fact that 0 and 2
n
-
1 are the maximum and minimum elements, respectively, in the poset I
n, as shown in Example 12.Recall that two binaryn-tuples are complementary if and only if their decimal equivalents sum up to 2
n
-
1 (see Definition 1-(iii)). Hence, one can observe that any two complementary n-tuples are placed at symmetric positions (with respect to the central point) in the intrinsic order graph I
n. For instance, this is the case in the graph I
4 for the following pairs of binary 4-tuples (see the right-most graphs in Figures 2 and 3):
(32)
u
=
(
0,0
,
1,1
)
≡
3
,
u
c
=
(
1,1
,
0,0
)
≡
12
,
u
+
u
c
=
3
+
12
=
15
=
2
4
-
1
,
u
=
(
0,1
,
1,0
)
≡
6
,
u
c
=
(
1,0
,
0,1
)
≡
9
,
u
+
u
c
=
6
+
9
=
15
=
2
4
-
1
,
u
=
(
0,1
,
1,1
)
≡
7
,
u
c
=
(
1,0
,
0,0
)
≡
8
,
u
+
u
c
=
7
+
8
=
15
=
2
4
-
1
.The edgeless graph associated with a given graph is obtained by removing all its edges, keeping its (isolated) nodes at the same positions. In Figures4 and 5, the edgeless intrinsic order graphs for I
5 and I
6, respectively, are depicted.Figure 4
The edgeless intrinsic order graph forn
=
5.Figure 5
The edgeless intrinsic order graph forn
=
6.For further theoretical properties and practical applications of the intrinsic order and the intrinsic order graph, we refer the reader to [7, 9–13] and to the references therein.


## 3. Occurrence Probabilities of Bitstrings with the Same Weight

In this section, we present our results about the comparison, by intrinsic order, between the occurrence probabilities of two binaryn-tuples having the same Hamming weight.For the special case that the bitstringsu
,
v
∈
{
0,1
}
n have the same weight, the intrinsic order can be characterized as stated by the following two lemmas.Lemma 15.
Letn
≥
1. Let u
,
v
∈
{
0,1
}
n with w
H
(
u
)
=
w
H
(
v
). Then u
≽
v if and only if the matrix
(33)
M
v
u
=
(
u
1
⋯
u
n
v
1
⋯
v
n
)
has neither (
1
0
) nor (
0
1
) columns, or for each (
1
0
) column in M
v
u there exists exactly one corresponding preceding (
0
1
) column.Proof.
Using Definition8 and Theorem 4, we have that u
≽
v if and only if matrix M
v
u satisfies IOC, if and only if either matrix M
v
u has no (
1
0
) columns or for each (
1
0
) column in matrix M
v
u there exists at least one corresponding preceding (
0
1
) column (IOC). But, under the assumption that u and v have the same number of 1-bits, IOC is actually equivalent to saying that matrix M
v
u has neither (
1
0
) nor (
0
1
) columns (in this case, obviously, u
=
v), or for each (
1
0
) column in matrix M
v
u there exists exactly one corresponding preceding (
0
1
) column.The following lemma characterizes the intrinsic order between binaryn-tuples of the same weight, involving only their 1-bits, with no need to use their 0-bits.Lemma 16.
Letn
≥
1. Let u
,
v
∈
{
0,1
}
n with w
H
(
u
)
=
w
H
(
v
). Then u
≽
v if and only if for each 1-bit in u there exists exactly one corresponding 1-bit in v placed at the same or at a previous position.Proof.
Using Lemma15, we have that u
≽
v if and only if matrix M
v
u has neither (
1
0
) nor (
0
1
) columns, or each (
1
0
) column in M
v
u is preceded by exactly one corresponding (
0
1
) column. On one hand, each (
1
1
) column in M
v
u (say (
u
i
v
i
)
=
(
1
1
)) corresponds to a 1-bit placed at the same position in both binary n-tuples u and v (u
i
=
v
i
=
1). On the other hand, each column (
u
i
v
i
)
=
(
1
0
) in M
v
u preceded by its corresponding column (
u
j
v
j
)
=
(
0
1
) (j
<
i) corresponds to a 1-bit v
j
=
1 in v placed at a previous position than the 1-bit u
i
=
1 in u.Now, we introduce the following notation for binaryn-tuples.Definition 17.
Letn
≥
1 and let u
∈
{
0,1
}
n with Hamming weight w
H
(
u
)
=
m. Then(i)
the vector of positions of1s of u is the vector of positions of its m
1-bits, displayed in increasing order from the left-most position to the right-most position, and it will be denoted by
(34)
u
=
[
i
1
,
i
2
,
…
,
i
m
]
n
1
,
(35)
1
≤
i
1
<
i
2
<
⋯
<
i
m
≤
n
,
0
<
m
≤
n
;
(ii)
the vector of positions of0s of u is the vector of positions of its (
n
-
m
)
0-bits, displayed in increasing order from the left-most position to the right-most position, and it will be denoted by
(36)
u
=
[
i
¯
1
,
i
¯
2
,
…
,
i
¯
n
-
m
]
n
0
,
(37)
1
≤
i
¯
1
<
i
¯
2
<
⋯
<
i
¯
n
-
m
≤
n
,
0
≤
m
<
n
.We also use the symbol “≡” to denote the conversion between any of these vector notations and the binary or decimal representation of the bitstrings.Example 18.
Letn
=
7 and u
=
43
≡
(
0,1
,
0,1
,
0,1
,
1
). Then we have m
=
w
H
(
u
)
=
4, n
-
m
=
3, and
(38)
u
=
(
0,1
,
0,1
,
0,1
,
1
)
≡
[
i
1
,
i
2
,
i
3
,
i
4
]
7
1
=
[
2,4
,
6,7
]
7
1
,
u
=
(
0,1
,
0,1
,
0,1
,
1
)
≡
[
i
¯
1
,
i
¯
2
,
i
¯
3
]
7
0
=
[
1,3
,
5
]
7
0
.The following theorem characterizes the intrinsic order between binaryn-tuples of the same weight, using the vectors of positions of their 1-bits, introduced in Definition 17-(i).Theorem 19.
Letn
≥
1. Let u
,
v
∈
{
0,1
}
n with w
H
(
u
)
=
w
H
(
v
). Let
(39)
u
=
[
i
1
,
i
2
,
…
,
i
m
]
n
1
,
v
=
[
j
1
,
j
2
,
…
,
j
m
]
n
1
,
(
1
≤
i
1
<
i
2
<
⋯
<
i
m
≤
n
1
≤
j
1
<
j
2
<
⋯
<
j
m
≤
n
)
be the vectors of positions of 1-bits of u and v, respectively. Then
(40)
u
≽
v
⟺
v
⪯
u
⟺
j
1
≤
i
1
,
j
2
≤
i
2
,
…
,
j
m
≤
i
m
.Proof.
Using Lemma16, we have that u
≽
v if and only if for each 1-bit in u there exists exactly one corresponding 1-bit in v placed at the same or at a previous position. Now, according to Definition 17-(i), sweeping the m
1-bits of u from left to right, the last assertion is clearly equivalent to saying that
(41)
j
1
≤
i
1
,
j
2
≤
i
2
,
…
,
j
m
≤
i
m
and the proof is concluded.Example 20.
Letn
=
9 and let
(42)
u
=
(
0,0
,
0,1
,
1,0
,
1,1
,
1
)
≡
[
i
1
,
i
2
,
i
3
,
i
4
,
i
5
]
9
1
=
[
4,5
,
7,8
,
9
]
9
1
,
v
=
(
1,1
,
0,0
,
1,1
,
0,0
,
1
)
≡
[
j
1
,
j
2
,
j
3
,
j
4
,
j
5
]
9
1
=
[
1,2
,
5,6
,
9
]
9
1
.
Using Theorem 4, we have that v
⪯
u since matrix
(43)
M
v
u
=
(
0
0
0
1
1
0
1
1
1
1
1
0
0
1
1
0
0
1
)
satisfies
IOC
.
Now, since w
H
(
u
)
=
w
H
(
v
)
=
5, then alternatively, we can apply Theorem 19. In this way, we also conclude that v
⪯
u, since
(44)
j
1
<
i
1
,
j
2
<
i
2
,
j
3
<
i
3
,
j
4
<
i
4
,
j
5
=
i
5
.Given a fixed binaryn-tuple u
∈
{
0,1
}
n with weight m, the following theorem provides us with the set and with the number of all the binary n-tuples v
∈
{
0,1
}
n with weight m that are intrinsically less than or equal to u (i.e., v
⪯
u). That is, it provides the set and the number of all the binary n-tuples v with the same weight as u, and whose occurrence probabilities are always (i.e., intrinsically) less than or equal to the occurrence probability of u.Theorem 21.
Letu
∈
{
0,1
}
n, u
≠
0, with (nonzero) Hamming weight w
H
(
u
)
=
m
(
0
<
m
≤
n
). Let u
=
[
i
1
,
i
2
,
…
,
i
m
]
n
1 be the vector of positions of 1s of u. Then the set of the binary n-tuples v with weight m, which are intrinsically less than or equal to u, is given by
(45)
{
v
∈
{
0,1
}
n
∣
w
H
(
v
)
=
w
H
(
u
)
,
v
⪯
u
}
=
{
v
=
[
j
1
,
j
2
,
…
,
j
m
]
n
1
∣
j
1
≤
i
1
,
j
2
≤
i
2
,
…
,
j
m
≤
i
m
[
j
1
,
j
2
,
…
,
j
m
]
n
1
}
.
Moreover, the number of the binary n-tuples v with weight m, that are intrinsically less than or equal to u, is given by
(46)
|
{
v
∈
{
0,1
}
n
∣
w
H
(
v
)
=
w
H
(
u
)
,
v
⪯
u
}
|
=
∑
j
1
=
1
i
1
∑
j
2
=
j
1
+
1
i
2
⋯
∑
j
m
=
j
m
-
1
+
1
i
m
1
.Proof.
Using Theorem19, we have that
(47)
v
⪯
u
⟺
j
p
≤
i
p
∀
p
=
1,2
,
…
,
m
and this proves (45). Finally, (46) immediately follows from the fact that 1
≤
j
1
<
j
2
<
⋯
<
j
m (see Definition 17-(i)) and from (45).Now, we establish the dual result of Theorem21. For this purpose, we need the following lemma.Lemma 22.
Letn
≥
1 and let u
,
v
∈
{
0,1
}
n. Then v
⪯
u if and only if u
c
⪯
v
c.Proof.
Clearly, the(
0
0
), (
1
1
), (
0
1
), and (
1
0
) columns in matrix M
v
u, respectively, become (
1
1
), (
0
0
), (
0
1
), and (
1
0
) columns in matrix M
u
c
v
c. Hence, using Definition 8 and Theorem 4, we have that v
⪯
u if and only if matrix M
v
u satisfies IOC if and only if matrix M
u
c
v
c satisfies IOC if and only if u
c
⪯
v
c.Given a fixed binaryn-tuple u
∈
{
0,1
}
n with weight m, the following theorem provides us with the set and with the number of all the binary n-tuples v
∈
{
0,1
}
n with weight m that are intrinsically greater than or equal to u (i.e., v
≽
u). That is, it provides the set and the number of all the binary n-tuples v with the same weight as u, and whose occurrence probabilities are always (i.e., intrinsically) greater than or equal to the occurrence probability of u.Theorem 23.
Letu
∈
{
0,1
}
n, u
≠
2
n
-
1, with (nonzero) Hamming weight w
H
(
u
)
=
m
(
0
≤
m
<
n
). Let u
=
[
i
¯
1
,
i
¯
2
,
…
,
i
¯
n
-
m
]
n
0 be the vector of positions of 0s of u. Then the set of the binary n-tuples v with weight m, which are intrinsically greater than or equal to u, is given by
(48)
{
v
∈
{
0,1
}
n
∣
w
H
(
v
)
=
w
H
(
u
)
,
v
≽
u
}
=
{
v
=
[
j
¯
1
,
j
¯
2
,
…
,
j
¯
n
-
m
]
n
0
∣
j
¯
1
≤
i
¯
1
,
j
2
≤
i
¯
2
,
…
,
j
¯
n
-
m
≤
i
¯
n
-
m
[
j
¯
1
,
j
¯
2
,
…
,
j
¯
n
-
m
]
n
0
}
.
Moreover, the number of the binary n-tuples v with weight m, which are intrinsically greater than or equal to u, is given by
(49)
|
{
v
∈
{
0,1
}
n
∣
w
H
(
v
)
=
w
H
(
u
)
,
v
≽
u
}
|
=
∑
j
¯
1
=
1
i
¯
1
∑
j
¯
2
=
j
¯
1
+
1
i
¯
2
⋯
∑
j
¯
n
-
m
=
j
¯
n
-
m
-
1
+
1
i
¯
n
-
m
1
.Proof.
It suffices to use Lemma22, Theorem 21, and the obvious fact that the 0-bits and 1-bits in u and v become the 1-bits and 0-bits, respectively, in u
c and v
c.Example 24.
Letn
=
5 and let u
=
13
≡
(
0,1
,
1,0
,
1
). Then m
=
w
H
(
u
)
=
3.
On one hand, the vector of positions of 1-bits inu is
(50)
u
=
(
0,1
,
1,0
,
1
)
≡
[
i
1
,
i
2
,
i
3
]
5
1
=
[
2,3
,
5
]
5
1
.
Then, using (45) in Theorem 21, we have that the binary 5-tuples v with weight m
=
3, which are intrinsically less than or equal to u
=
13, are the following:
(51)
v
=
[
1,2
,
3
]
5
1
≡
(
1,1
,
1,0
,
0
)
≡
28
,
v
=
[
1,2
,
4
]
5
1
≡
(
1,1
,
0,1
,
0
)
≡
26
,
v
=
[
1,2
,
5
]
5
1
≡
(
1,1
,
0,0
,
1
)
≡
25
,
v
=
[
1,3
,
4
]
5
1
≡
(
1,0
,
1,1
,
0
)
≡
22
,
v
=
[
1,3
,
5
]
5
1
≡
(
1,0
,
1,0
,
1
)
≡
21
,
v
=
[
2,3
,
4
]
5
1
≡
(
0,1
,
1,1
,
0
)
≡
14
,
v
=
[
2,3
,
5
]
5
1
≡
(
0,1
,
1,0
,
1
)
≡
13
.
Moreover, using (46) in Theorem 21, we can confirm that the cardinality of this set is
(52)
|
{
13,14,21,22,25,26,28
}
|
=
∑
j
1
=
1
i
1
=
2
∑
j
2
=
j
1
+
1
i
2
=
3
∑
j
3
=
j
2
+
1
i
3
=
5
1
=
7
.
On the other hand, the vector of positions of 0-bits in u is
(53)
u
=
(
0,1
,
1,0
,
1
)
≡
[
i
¯
1
,
i
¯
2
]
5
0
=
[
1,4
]
5
0
.
Then, using (48) in Theorem 23, we have that the binary 5-tuples v with weight m
=
3, which are intrinsically greater than or equal to u
=
13, are the following:
(54)
v
=
[
1,2
]
5
0
≡
(
0,0
,
1,1
,
1
)
≡
7
,
v
=
[
1,3
]
5
0
≡
(
0,1
,
0,1
,
1
)
≡
11
,
v
=
[
1,4
]
5
0
≡
(
0,1
,
1,0
,
1
)
≡
13
.
Moreover, using (49) in Theorem 23, we can confirm that the cardinality of this set is
(55)
|
{
7,11,13
}
|
=
∑
j
¯
1
=
1
i
¯
1
=
1
∑
j
¯
2
=
j
¯
1
+
1
i
¯
2
=
4
1
=
3
.The following corollary characterizes the binaryn-tuples u for which the number of binary n-tuples v intrinsically less than or equal to u is maximum (minimum, resp.).Corollary 25.
Letn
≥
1 and u
∈
{
0,1
}
n with Hamming weight w
H
(
u
)
=
m
(
0
<
m
≤
n
). Then(i)
the set of binaryn-tuples v with weight m (the same as u) which are intrinsically less than or equal to u is the set of all the (
n
m
) binary n-tuples v with weight m if and only if the m
1-bits of u are placed at the m right-most positions; that is, if and only if u has the general pattern
(56)
u
=
(
0
,
…
⌣
n
-
m
,
0,1
,
…
⌣
m
,
1
)
≡
2
m
-
1
,
0
<
m
≤
n
;
(ii)
the set of binaryn-tuples v with weight m (the same as u) which are intrinsically less than or equal to u is reduced to the n-tuple u if and only if the m
1-bits of u are placed at the m left-most positions; that is, if and only if u has the general pattern
(57)
u
=
(
1
,
…
⌣
m
,
1,0
,
…
⌣
n
-
m
,
0
)
≡
2
n
-
2
n
-
m
,
0
<
m
≤
n
.Proof.
(i) Letu
=
[
i
1
,
i
2
,
…
,
i
m
]
n
1 be the vector of positions of 1s of u. Using (46) in Theorem 21, we have that
(58)
|
{
v
∈
{
0,1
}
n
∣
w
H
(
v
)
=
w
H
(
u
)
,
v
⪯
u
}
|
=
∑
j
1
=
1
i
1
∑
j
2
=
j
1
+
1
i
2
⋯
∑
j
m
=
j
m
-
1
+
1
i
m
1
=
(
n
m
)
if and only if i
1
=
n
-
m
+
1, i
2
=
n
-
m
+
2
,
…, i
m
=
n if and only if u has the pattern (56).
(ii) Using again (46) in Theorem 21, we have that
(59)
|
{
v
∈
{
0,1
}
n
∣
w
H
(
v
)
=
w
H
(
u
)
,
v
⪯
u
}
|
=
∑
j
1
=
1
i
1
∑
j
2
=
j
1
+
1
i
2
⋯
∑
j
m
=
j
m
-
1
+
1
i
m
1
=
1
if and only if i
1
=
1, i
2
=
2
,
…, i
m
=
m if and only if u has the pattern (57).Finally, we establish the dual result of Corollary25.The following corollary characterizes the binaryn-tuples u for which the number of binary n-tuples v intrinsically greater than or equal to u is maximum (minimum, resp.).Corollary 26.
Letn
≥
1 and u
∈
{
0,1
}
n with Hamming weight w
H
(
u
)
=
m
(
0
<
m
≤
n
). Then(i)
the set of binaryn-tuples v with weight m (the same as u) which are intrinsically greater than or equal to u is the set of all the (
n
m
) binary n-tuples v with weight m if and only if the m
1-bits of u are placed at the m left-most positions; that is, if and only if u has the general pattern
(60)
u
=
(
1
,
…
⌣
m
,
1,0
,
…
⌣
n
-
m
,
0
)
≡
2
n
-
2
n
-
m
,
0
<
m
≤
n
;
(ii)
the set of binaryn-tuples v with weight m (the same as u) which are intrinsically less than or equal to u is reduced to the n-tuple u if and only if the m
1-bits of u are placed at the m right-most positions; that is, if and only if u has the general pattern
(61)
u
=
(
0
,
…
⌣
n
-
m
,
0,1
,
…
⌣
m
,
1
)
≡
2
m
-
1
,
0
<
m
≤
n
.Proof.
Using Lemma22 and Corollary 25, the proof is straightforward.


## 4. Conclusions

Given a fixed binaryn-tuple u
∈
{
0,1
}
n, we have provided the set and the number of all the binary n-tuples v with the same weight as u, and whose occurrence probabilities are always (i.e., intrinsically) less than or equal to the occurrence probability of u. Also, we have provided the set and the number of all the binary n-tuples v with the same weight as u, and whose occurrence probabilities are always (i.e., intrinsically) greater than or equal to the occurrence probability of u. The special patterns of those binary strings u for which the above numbers of binary strings v are maximum and minimum have been identified. For future research, new relations between the intrinsic ordering and the Hamming weights of the binary n-tuples (arising in CSBSs) are worth to be studied.



---

*Source: 428418-2014-03-24.xml*