1. Introduction
The study of coherent systems is vital in reliability theory. A system with structure function
$ \Phi (x_1, \ldots, x_n) = \Phi (\mathbf{x})$
,
$x_i \in \{0, 1\}$
, is said to be coherent if each of its components is relevant and
$\Phi$
is monotone (see Barlow and Proschan [Reference Barlow and Proschan2]). To study coherent systems, Samaniego [Reference Samaniego28] introduced the concept of system signatures. For a coherent system with independent and identically distributed (i.i.d.) component lifetimes
$X_i$
with support in
$\mathbb{R}^+ = (0, \infty)$
,
$i = 1, \ldots, n$
, and system lifetime T, the system signature
$\mathbf{s}$
is a probability vector in
$[0, 1]^n$
whose ith element
\begin{align*}s_i &= \mathbb{P}(T = X_{i:n}),\\*&= \dfrac{\# \text { of orderings for which the} \textit{i}\text{th failure causes system failure }}{n !}, \quad i=1, \ldots, n,\end{align*}
where
$X_{i:n}$
is the ith order statistic of
$X_i$
,
$i = 1, \ldots, n$
. For instance, if we consider the three-component coherent system,
$\max(X_1$
,
$ \min(X_2, X_3))$
, one can easily see that the system signature
$ \mathbf{s} = (0, 2/3, 1/3)$
. Thus it is evident that when component lifetimes are i.i.d., the system signature provides a way to measure how a component’s failure affects the system failure. Note that more than one system can have the same signature (see Samaniego [Reference Samaniego29, Table 3.2]). For a comprehensive discussion of system signatures one may refer to Kochar et al. [Reference Kochar, Mukerjee and Samaniego16], Boland [Reference Boland3], Boland and Samaniego [Reference Boland and Samaniego4], Samaniego [Reference Samaniego29], Navarro et al. [Reference Navarro, Ruiz and Sandoval22, Reference Navarro, Ruiz and Sandoval23, Reference Navarro, Samaniego, Balakrishnan and Bhattacharya24], Samaniego and Navarro [Reference Samaniego and Navarro30], and Navarro [Reference Navarro19], and to identify potential research areas for future study on system signatures, one may look at the review article by Naqvi et al. [Reference Naqvi, Chan and Mishra18].
In the literature, various methods have been proposed for the computation of the system signature for a given coherent system. For instance, Navarro and Rubio [Reference Navarro and Rubio20] proposed an algorithm to compute the signatures of all coherent systems of order n by generating their families of minimal path sets (see Section 2 for a definition), Da et al. [Reference Da, Zheng and Hu9, Reference Da, Xia and Hu10] derived some formulas for computing signatures of systems consisting of modules, Marichal and Mathonet [Reference Marichal and Mathonet17] showed that the signature can be computed more efficiently from the diagonal section of the reliability function, and Reed [Reference Reed25] proposed an algorithm for the computation of system signatures using binary decision diagrams. Now an important question that leads to the converse of this concept is: Can we construct a coherent system when the system signature is given? We believe that this is an equally important research direction that has not yet been explored. Moreover, even if a probability vector is given, one should be able to verify if it is a signature, and then find out the corresponding coherent system(s). To understand this, let us consider the following discussion: we know that the signature of a coherent system is a probability vector, but not every probability vector is a signature of a coherent system. Rather, every probability vector of size n can be treated as a signature of a mixed coherent system of order n (see Boland and Samaniego [Reference Boland and Samaniego4], Samaniego [Reference Samaniego29]), which is a superset of the class of all coherent systems of order n. In other words, there exist probability vectors that are not signatures of coherent systems but belong to the larger set of mixed signatures (see Boland and Samaniego [Reference Boland and Samaniego4], Samaniego [Reference Samaniego29]). For instance, consider probability vectors
${\mathbf{p}}_1 = (0, 1/5, 3/5, 1/5, 0)$
and
${\mathbf{p}}_2 = (0, 0, 1/5, 1/5, 3/5)$
. It is well known that
${\mathbf{p}}_1$
is the signature of the bridge system (see Example 3.2 in Barlow and Proschan [Reference Barlow and Proschan2]), and
${\mathbf{p}}_2$
can be thought of as the signature of a mixed coherent system of order 5. However,
${\mathbf{p}}_2$
is not a signature of a coherent system of order 5. This is evident from the work of Navarro and Rubio [Reference Navarro and Rubio20] and the same will also be justified in Section 4 of this paper. For further illustration, let us consider the following scenario.
Suppose a reliability engineer is working with a two-component series system with i.i.d. components, and the lifetimes of the components are denoted by
$X_1$
and
$X_2$
. Since the signature of a two-component series system is (1, 0), the average lifetime of the system is
$\mathbb{E}(X_{1:2})$
. Here
$\mathbb{E}(X_{1:2})$
denotes the expectation of the random variable
$X_{1:2}$
. Now suppose the engineer wishes to create a new system that will have a better average lifetime. For this purpose he wishes to consider the probability vector
$(1/2, 1/2)$
, anticipating that the system’s average lifetime,
${\mathbb{E}(X_{1:2} + X_{2:2})}/{2}$
, would exceed
$\mathbb{E}(X_{1:2})$
. However, in reality, it is not possible to construct a coherent system with two components in which each component failure has an equal influence on the system failure. Consequently, the probability vector
$(1/2, 1/2)$
does not qualify as a valid signature. In a similar vein, suppose the reliability engineer wishes to create a three-component coherent system by assuming the probability vector
$(1/3, 0, 2/3)$
is the signature of the coherent system. Using Corollary 2.1(ii) (see Section 2), we know that the coherent system has one cut set of size 1 and one cut set of size 2. However, in reality, constructing such a coherent system is not possible, since if a three-component coherent system has a cut set of size 1, then it has at least two cut sets of size 2. Therefore
$(1/3, 0, 2/3)$
is not a signature vector. Thus it is important to verify whether the given probability vector of size n is a signature of a coherent system(s) of order n or a signature of a mixed system.
We make an attempt in this direction by proposing an algorithm that verifies whether the given probability vector of size n belongs to the class of system signatures of order n or it falls outside this class and belongs to the class of mixed signatures of order n. More simply, we propose an algorithm to check whether a given probability vector is a signature, and construct the corresponding coherent system(s) if it is a signature.
The rest of the paper is organized as follows. In Section 2 we provide auxiliary results that will serve as the foundation for the algorithm we propose. Section 3 outlines the algorithm itself and provides a discussion of computational complexity of the algorithm. Section 4 focuses on the practical applications, specifically the identification of all three and four-dimensional signature vectors using the algorithm. Finally, we end the article with a conclusion section.
2. Auxiliary results
In this section we provide some results which will be helpful in writing the algorithm proposed in this paper. Specifically, we define minimal cut sets, minimal path sets, maximal signature, system signature, survival signature, failure signature, internal zeros property, dual signature, and their corresponding results in the form of lemmas.
It is well known that associated with every coherent system, there exist sets of indices, denoted by C and P, known as a cut set and a path set, respectively, such that if the components in C fail (P work) then the system fails (works). A cut set (path set) is said to be a minimal cut set (minimal path set) if no proper subset of it is a cut set (path set). The following lemma by Barlow and Proschan [Reference Barlow and Proschan2] characterizes the minimal cut sets (minimal path sets) of a coherent system.
Lemma 2.1.
If
$C_1, \ldots, C_r$
$(P_1, \ldots, P_s)$
are subsets of
$\{1, \ldots, n\}$
, then they are the minimal cut sets (minimal path sets) of a coherent system with n components if and only if
$C_i \not\subseteq C_j$
$(P_i \not\subseteq P_j)$
for all
$i \neq j$
and
$C_1 \cup \cdots \cup C_r\: (P_1 \cup \cdots \cup P_s) = \{1, \ldots, n\}$
.
Note that from now on we call
$\{C_1, \ldots, C_r\}$
$(\{P_1, \ldots, P_s\})$
the family of minimal cut sets (minimal path sets) of the coherent system. Using the family of minimal cut sets (minimal path sets), the lifetime T of the coherent system with structure function
$\Phi$
and component lifetimes
$X_1, \ldots, X_n$
can be written as
\begin{align*}T = \Phi (X_1, \ldots, X_n) = \min_{u = 1, \ldots, r}\max_{i \in C_u}X_i = \max_{v = 1, \ldots, s}\min_{i \in P_v}X_i\end{align*}
(Barlow and Proschan [Reference Barlow and Proschan2, p. 12]). Furthermore, we also know that the maximal signature (denoted by
$M = (m_1, \ldots, m_n)$
) of the coherent system can be obtained using minimal cut sets (see Navarro [Reference Navarro19]), and the system lifetime distribution can be written as
\begin{align}F_{T}(t) = \sum_{k = 1}^{n}m_k [F(t)]^k\end{align}
for all
$t>0$
, where
$m_1, \ldots, m_n$
are integer coefficients such that
$m_1 + \cdots + m_n = 1$
, and F(t) is the components life distribution. To understand this, consider a coherent system with lifetime
$T = \text{min}(\text{max}(X_1, X_2), \text{max}(X_1, X_3), \text{max}(X_1$
,
$ X_4))$
and the family of minimal cut sets
$$g =\{C_1 = \{1, 2\}, C_2 = \{1, 3\}, C_3 = \{1, 4\} \}.$$
Then
\begin{align*}F_{T}(t) &= \sum_{r=1}^{3} F_{C_{r}}(t) - F_{C_{1}\cup C_{2} }(t) - F_{C_{1}\cup C_{3} }(t) - F_{C_{2}\cup C_{3} }(t) + F_{C_{1}\cup C_{2}\cup C_{3}}(t),\\&= F_{\{1,\: 2\}}(t)+F_{\{1,\: 3\}}(t)+F_{\{1,\: 4\}}(t)-F_{\{1,\: 2,\: 3\}}(t)-F_{\{1,\: 2,\: 4\}}(t)-F_{\{1,\: 3,\: 4\}}(t)\\&\quad +F_{\{1,\: 2,\: 3,\: 4\}}(t),\quad t \gt 0.\end{align*}
If the component lifetimes are i.i.d. with common life distribution F, then we get
\begin{align*}F_{T}(t) &= 3 F^2(t) - 3F^3(t) + F^4(t),\quad t \gt 0,\end{align*}
since
$F_{C}(t) = \mathbb{P}(\text{max}_{i \in C} X_i \leq t ) = [F(t)]^{|C|}$
, for all
$ t \gt 0$
. Hence the maximal signature of the coherent system is
$M_{g} = (0,\, 3,\, -3,\, 1)$
. Here, (2.1) shows that system lifetime distribution
$F_T(t)$
can be expressed using the maximal signature (see Navarro [Reference Navarro19]). We also know from the literature (see Samaniego [Reference Samaniego28]) that the system lifetime distribution can also be expressed as a finite mixture using its system signature
$\mathbf{s} = (s_1, \ldots, s_n)$
, as shown in the following lemma.
Lemma 2.2.
Let
$X_{1}, \ldots, X_{n}$
, be i.i.d. component lifetimes of an n-component coherent system with signature
$\boldsymbol{s}=(s_{1}, \ldots, s_{n})$
. Let F be the distribution of component lifetimes and let T be the system’s lifetime. Then
\begin{align*}F_{T}(t) = \sum_{i = 1}^{n}s_iF_{i:n}(t) \quad \ for\ all\ \ t \gt 0,\end{align*}
where
$F_{i:n}$
is the distribution of the ith order statistic of
$X_{1}, \ldots, X_{n}$
.
Thus it is intuitive to think about a relation between the maximal signature and the system signature of a coherent system. Navarro and Rubio [Reference Navarro and Rubio20, p. 77] showed that there exists a non-singular upper triangular matrix, say
$U_n$
, such that
\begin{align}M = (m_1, \ldots, m_n) = (s_1, \ldots, s_n). U_n,\quad n \geq 2,\end{align}
where the (i, j) (ith row and jth column) element of
$U_n$
is
u_{ij}=\begin{cases}\displaystyle ({-}{1})^{j-i}\binom{j-1}{i-1}\binom{n}{j}, & \text{if $ i \leq j$,} \\0, & \text{if $ i \gt j$,}\end{cases}
$i, j \in \{1, \ldots, n\}$
. Using this representation, one can easily find
$U_n$
, for
$n \geq 2$
.
Moreover, the notion of system signature has been generalized to survival signature and failure signature to deal with systems with heterogeneous components (see Coolen and Coolen-Maturi [Reference Coolen and Coolen-Maturi5, Reference Coolen and Coolen-Maturi6], Coolen-Maturi et al. [Reference Coolen-Maturi, Coolen and Balakrishnan7], Ding et al. [Reference Ding, Fang and Zhao12], Eryilmaz et al. [Reference Eryilmaz, Coolen and Coolen-Maturi13], Feng et al. [Reference Feng, Patelli, Beer and Coolen14], and Samaniego and Navarro [Reference Samaniego and Navarro30]). Consider an n-component coherent system with E different types of components such that the components are independent and the components of the same type are i.i.d.; then the survival signature of the coherent system is an E variable function and is defined as
$$\phi (i_1,\ldots,i_E) = \mathbb{P}(\text{system works}\mid \text{$i_e$ components of type } \textit{e} \text{ work}),$$
and the failure signature is
$$\phi^{*} (i_1,\ldots,i_E) = \mathbb{P}(\text{system fails}\mid \text{$i_e$ components of type } \textit{e} \text{ fail}),$$
$i_e = 0, \ldots, n_e, $
where
$n_e$
is the number of components of type e,
$e = 1, \ldots, E$
. Ding et al. [Reference Ding, Fang and Zhao12], in their equation (6), established a relation between survival signature
$\phi (i_1,\ldots,i_E)$
and the number of working path sets for a coherent system. Using a similar logic, we present the following lemma to build a connection between the survival signature and number of path sets, as well as the failure signature and number of cut sets.
Lemma 2.3. If there exists a coherent system with E different types of components such that the components are independent and the components of the same type are i.i.d., then:
-
(i)
$ \phi (i_{1}, \ldots, i_{E}) \prod_{e = 1}^{E}\binom{n_e}{i_e} = \# \textit{path sets of size}\ (i_{1}+\cdots+i_{E})$
containing
$i_e$
components of type e, -
(ii)
$ \phi^{*} (i_{1}, \ldots, i_{E}) \prod_{e = 1}^{E}\binom{n_e}{i_e} = \# \textit{cut sets of size}\ (i_{1}+\cdots+i_{E})$
containing
$i_e$
components of type e,
where
$i_e = 0, \ldots, n_e, $
$n_e$
is the total number of components of type e,
$e = 1, \ldots, E$
, and
$ \sum_{e = 1}^{E}n_e = n$
.
For the case when
$E = 1$
and
$n_1 = n$
, then we have the following corollary as an immediate consequence to Lemma 2.3.
Corollary 2.1.
Let
$\mathbf{s} = (s_1, \ldots, s_n)$
be the signature of a coherent system whose n components have i.i.d. lifetimes. Then the following holds true:
-
(i)
$\binom{n}{j}\sum_{i=n-j+1}^{n}s_i = \# \textit{ path sets of size } j,\ j = 1, \ldots, n$
, -
(ii)
$ \binom{n}{j}\sum_{i=1}^{j}s_i =\# \textit{ cut sets of size } j,\ j = 1, \ldots, n$
.
The proof of Corollary 2.1(i) is given in Boland [Reference Boland3], and Corollary 2.1(ii) can also be proved on the same lines. Thus, using Corollary 2.1, we can say that in a coherent system whose n components have i.i.d. lifetimes, for
$j = 1, \ldots, n$
,
\begin{align*}\# \text { path sets of size } j + \# \text { cut sets of size } (n-j) = \binom{n}{j}.\end{align*}
The following lemma is from Navarro and Samaniego [Reference Navarro and Samaniego21], and it is commonly referred to as the ‘No internal zeros property’ of a system signature. This property of a signature holds significant importance in the algorithm we are presenting.
Lemma 2.4.
Let
$\mathbf{s} = (s_1, \ldots, s_n)$
be the signature of a coherent system whose n components have i.i.d. lifetimes. Then there exist no integers
$i \in\{1, \ldots, n-2\}$
and
$j \in\{2, \ldots, n-i\}$
for which
$s_{i} \gt 0$
and
$s_{i+j} \gt 0$
while
$s_{i+1}= \ldots =s_{i+j-1}=0$
.
Further, we know that given a coherent structure
$\Phi$
, its dual structure can be defined as
$$\Phi^D (x_1, \ldots, x_n) =\Phi^D (\mathbf{x}) = 1 - \Phi(\mathbf{1} - \mathbf{x}),\quad x_i \in \{0, 1\},$$
where
$\mathbf{1}$
is the vector of all 1s. Note that the minimal cut sets of
$\Phi$
are the minimal path sets of
$\Phi^D$
, and vice versa (see Barlow and Proschan [Reference Barlow and Proschan2, p. 15]). In order to establish a connection between the signature of a coherent system and the signature of its dual coherent system, Kochar et al. [Reference Kochar, Mukerjee and Samaniego16] showed that if
$\mathbf{s} = (s_1, \ldots, s_n)$
is the signature of a fixed coherent system
$\Phi$
whose n components have i.i.d. lifetimes and
$\mathbf{s}^D = (s^D_1, \ldots, s^D_n)$
is the signature of its dual coherent system
$\Phi^{D}$
, then
$$s_{i}=s_{n-i+1}^{D} \quad \text{for $i=1, \ldots, n $.}$$
In a similar way, one can establish a relation between probability vector
${\mathbf{p}} = (p_1, \ldots, p_n)$
and its dual probability vector
${\mathbf{p}}^{D} = (p_n, \ldots, p_1)$
. It is mentioned below in the form of Lemma 2.5.
Lemma 2.5.
A probability vector
${\mathbf{p}} = (p_1, \ldots, p_n)$
is the signature of ‘l’ coherent systems, say
$\Phi_1, \ldots, \Phi_l$
, each composed of n components whose lifetimes are i.i.d. if and only if its dual probability vector
${\mathbf{p}}^{D} = (p_n, \ldots, p_1)$
is the signature of ‘l’ coherent systems
$\Phi^D_1, \ldots, \Phi^D_l$
, where
$\Phi^D_j$
is the dual coherent system of
$\Phi_j$
,
$j = 1, \ldots, l$
.
3. Main results
Now we present the following theorem and algorithm, which enable us to distinguish system signatures from probability vectors. We make use of Corollary 2.1 and Lemma 2.4, which give two very important properties of the signature vectors, and the final conclusion about any given probability vector is made using the maximal signature and Lemma 2.5.
Theorem 3.1.
Let
${\mathbf{p}} = (p_1, \ldots, p_n)$
be a given probability vector. Using the algorithm, one can verify whether
${\mathbf{p}}$
is a signature, and if it is a signature, the algorithm will give the corresponding coherent system(s).
Algorithm.
-
Step 1. If
$\binom{n}{j}\sum_{i = 1}^{j}p_i$
for
$j = 1, \ldots, n$
are integer then go to Step 2. Else, both
${\mathbf{p}}$
and
${\mathbf{p}}^{D} = (p_n, \ldots, p_1)$
are not signatures. -
Step 2. If there exist integers
$i \in\{1, \ldots, n-2\}$
and
$j \in\{2, \ldots, n-i\}$
such that
$p_{i} \gt 0$
and
$p_{i+j} \gt 0$
while
$p_{i+1}=\cdots=p_{i+j-1}=0$
, then both
${\mathbf{p}}$
and
${\mathbf{p}}^{D}$
are not signatures. Else, go to Step 3. -
Step 3. Assume that the vector
${\mathbf{p}}$
is a signature of a coherent system. Let the vector
$c = (c_1, \ldots, c_n)$
be such that the jth element
$c_j = \binom{n}{j}\sum_{i = 1}^{j} p_i$
is the number of cut sets of size j,
$j = 1, \ldots, n$
, of the coherent system. -
Step 4. Write the possible families of cut sets
$f_1, \ldots, f_K$
, where
$K = \prod_{j = 1}^{n}\binom{K_j}{c_j}$
and
$K_j = \binom{n}{j}$
,
$j = 1, \ldots, n$
. -
Step 5. For any two sets
$A_1$
and
$A_2$
$\in f_k$
, if
$A_1 \subseteq A_2$
, then remove
$A_2$
from
$f_k$
,
$k = 1, \ldots, K$
. Further, consider those
$f_k$
such that
$ \bigcup_{A_i \in f_k}^{} A_i = \{1, \ldots, n\}$
, and denote these families of minimal cut sets as
$g_1, \ldots, g_R$
,
$R \leq K$
. Next, choose only those
$g_r$
,
$r = 1, \ldots, R$
that are different up to permutation, and denote them by
$h_1, \ldots, h_Q$
,
$Q \leq R$
. -
Step 6. Corresponding to the
$h_q$
,
$q = 1, \ldots, Q$
, obtained in Step 5, we calculate the maximal signatures
$M_{h_q}$
. In addition, calculate the maximal signature
$M_{{\mathbf{p}}} = {\mathbf{p}}.U_n$
(using (2.2)) of the coherent system. -
Step 7. If
$M_{{\mathbf{p}}} \neq M_{h_{q}}$
, for
$q = 1, \ldots, Q$
, then we can conclude that
${\mathbf{p}}$
is not a signature. Without loss of generality, suppose
$M_{{\mathbf{p}}} = M_{h_1} = \cdots = M_{h_L}$
,
$1 \leq L \leq Q$
; then the vector
${\mathbf{p}} = (p_1, \ldots, p_n)$
is the signature of L coherent systems and the corresponding families of minimal cut sets are
$h_1, \ldots, h_L$
.
Note that vector
${\mathbf{p}}^{D} = (p_n, \ldots, p_1)$
is the signature of L coherent systems (using Lemma 2.5) and the corresponding families of minimal path sets are
$h_1, \ldots, h_L$
. If
$X_1, \ldots, X_n$
, are the i.i.d. component lifetimes, then the lth coherent systems corresponding to the signatures
${\mathbf{p}}$
and
${\mathbf{p}}^D$
are, respectively,
\begin{align*}\Phi_{{\mathbf{p}}, l}(X_1, \ldots, X_n) = \min_{j = 1, \ldots, r_l}\max_{i \in C_j}X_i \quad \text{and} \quad\Phi_{{\mathbf{p}}^D, l}(X_1, \ldots, X_n) = \max_{j = 1, \ldots, r_l}\min_{i \in C_j}X_i,\end{align*}
where
$C_j \in h_l$
and
$r_l$
is the cardinality of
$h_l$
,
$l = 1, \ldots, L$
. Thus, for a given probability vector of order n, the algorithm can be utilized to first verify whether it is a signature, and then employ minimal cut set (or minimal path set) representation to find out the corresponding coherent system(s).
Note that, given a probability vector that is not a signature, it is very likely that the algorithm can identify it in Step 1 or Step 2. These initial steps encompass two necessary properties of a signature vector and are easy to verify. If it fails to be identified in the first two steps, it will certainly be identified in Step 7 of the algorithm. This is because Step 7 is a characterization of system signatures, guaranteeing the convergence of the algorithm, as elaborated in the corollary below.
Corollary 3.1.
Let the probability vector
${\mathbf{p}} = (p_1, \ldots, p_n)$
be a candidate signature and let
$M_{{\mathbf{p}}} = {\mathbf{p}}.U_n$
(see (2.2)) be the maximal signature associated with it. For
$q = 1, \ldots, Q$
, define
$h_q$
as the family of minimal cut sets which are different up to permutation (see Steps 3, 4, and 5 of the algorithm), and let
$M_{h_q}$
be the maximal signature associated with
$h_q$
. Then
${\mathbf{p}}$
is the signature of a coherent system if and only if
$$M_{{\mathbf{p}}} = M_{h_q} \quad\textit{for at least one}\ h_q, q = 1, \ldots, Q.$$
Note that D’Andrea and De Sanctis [Reference D’Andrea and De Sanctis11, Theorem 5.1] also gave a characterization of system signatures using the Kruskal–Katona theorem, which is a number-theoretic approach. However, the characterization we have provided is based on the relation between system signatures and maximal signatures, and the relation between minimal cut sets and maximal signatures. Further, note that we can also have a similar characterization of system signatures using the relation between system signatures and minimal signatures, and the relation between minimal path sets and minimal signatures.
We would like to emphasize that the algorithm can also be utilized to construct the coherent system(s) in the scenario where its signature is known. To do so, one can exclusively employ Steps 3 to 7, as a signature vector fulfils the requirements outlined in Steps 1 and 2 of the algorithm. Additionally, it is worth mentioning that in Step 7, the situation where
$M_{{\mathbf{p}}} \neq M_{h_{q}}$
for
$q = 1, \ldots, Q$
never arises, as there is always at least one coherent system with the given signature.
3.1. Computational complexity of the algorithm
In this section we discuss the computational complexity of our proposed algorithm. It is a critical aspect of algorithmic design, determining the efficiency and feasibility of the algorithm’s execution. This analysis allows us to understand how the algorithm’s performance scales with larger n, which is the dimension of the given probability vector. It can be seen that the first two steps of the algorithm play a crucial role in determining if a given probability vector is a signature. When we apply the algorithm to identify all coherent systems with
$ n = 3 $
and
$ n = 4 $
components (details provided in Section 4), we observe the following: for
$ n = 3 $
, we begin with a total of 28 probability vectors (see Section 4 for details). Step 1 of the algorithm reveals that 18 of these vectors are not signature vectors, and Step 2 identifies two additional non-signature vectors. Thus, Steps 1 and 2 together eliminate approximately 86.95% of the non-signature vectors. For
$ n = 4 $
, we start with 2925 probability vectors (refer to Section 4 for details). Step 1 of the algorithm shows that 2886 of these vectors are not signature vectors, and Step 2 identifies five more non-signature vectors. Therefore, Steps 1 and 2 together eliminate approximately 99.41% of the non-signature vectors. For
$ n = 5 $
, in Step 1 itself we eliminate 99.99% of the non-signature vectors. Hence the first two steps of the algorithm are essential for efficiently eliminating non-signature probability vectors.
Furthermore, note that all the steps except Step 5 in the algorithm can be performed in polynomial time (refer to Cormen et al. [Reference Cormen, Leiserson, Rivest and Stein8] for a definition). In Step 5 we check whether or not families of minimal cut sets are equivalent up to permutation. To understand the complexity of Step 5 of the algorithm, we utilize some concepts from graph theory (see Cormen et al. [Reference Cormen, Leiserson, Rivest and Stein8], Rosen [Reference Rosen26]). A graph G is an ordered pair (V, E), where V is called the vertex set and E is called the edge set. For each
$e \in E$
we associate two vertices
$u, v \in V$
, which we call the ends of e. In this study we associate a graph to a family of minimal cut sets, which is defined as follows.
Definition 3.1. Let
$f = \{C_1, \ldots, C_r\}$
be a family of minimal cut sets such that
$\bigcup_{i = 1}^{r} C_i= \{1, \ldots, n\}$
. The graph associated with f is denoted by
$G_f(V, E)$
, where V is the set of vertices,
$V = \{1, \dots, n\}$
, and E is the set of edges. For each
$C_i$
with
$|C_i| \geq 2$
, there is a simple circuit in
$G_f$
which connects the elements of
$C_i$
,
$i = 1, \ldots, r$
, and if
$C_i = \{j\}$
for some i, then the vertex j is an isolated vertex in
$G_f$
.
The following example illustrates how we associate a graph to a family of minimal cut sets.
Example 3.1. Consider a family of minimal cut sets corresponding to a coherent system with four components
$f = \{C_1 = \{1, 2\}$
,
$C_2 = \{1, 3, 4\}$
,
$C_3 = \{2, 3, 4\}\}$
. The graph associated with f is shown in Figure 1. Here,
$V = \{1, 2, 3, 4\}$
and
$$ E = \{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{3, 4\}\}. $$
Note that there are two edges between vertices 3 and 4.
Figure 1. Graph associated with f.
Now, to check whether two families of minimal cut sets are equivalent up to permutation, we define isomorphism of graphs.
Definition 3.2. Two graphs
$G_1 (V, E_1)$
and
$G_2(V, E_2)$
are isomorphic if there exists a bijection
$\sigma$
on V with the property that there is an edge connecting
$v_1$
and
$v_2$
in
$G_1$
if and only if there is an edge connecting
$\sigma(v_1)$
and
$\sigma(v_2)$
in
$G_2$
, for all
$v_1$
and
$v_2$
belonging to V.
In the following theorem we provide a necessary and sufficient condition for two families of minimal cut sets to be equivalent up to permutation using the corresponding associated graphs.
Theorem 3.2.
Let
$f_1 = \{C_{11}, \ldots, C_{1r}\}$
and
$f_2 = \{C_{21}, \ldots, C_{2r}\}$
be two families of minimal cut sets such that
$\bigcup_{k = 1}^{r} C_{jk}= \{1, \ldots, n\}$
,
$j = 1, 2$
. Also,
$N_{f_1}(i) = N_{f_2}(i)$
, where
$N_{f_j}(i)$
is the number of minimal cut sets in
$f_j$
of size i,
$j = 1, 2$
, and
$i = 1, \ldots, n-1$
. The sets
$f_1$
and
$f_2$
are equivalent up to permutation if and only if
$G_{f_1}(V, E_1)$
is isomorphic to
$G_{f_2}(V, E_2)$
.
Proof. Suppose
$f_1$
and
$f_2$
are equivalent up to permutation, i.e. there exists a bijection, say
$\sigma$
on
$\{1, \dots, n\}$
, such that
$$\sigma(f_1) = \{ \sigma(C_{11}), \ldots, \sigma(C_{1r})\} = f_2. $$
Thus, using the definition of
$G_{f_j}(V, E_j)$
,
$j = 1, 2$
, it can be seen that
G_{f_1}(V, \sigma(E_1)) = G_{f_2}(V, E_2).
Therefore,
$G_{f_1}(V, E_1)$
is isomorphic to
$G_{f_2}(V, E_2)$
. Similarly, one can obtain the proof of the converse.
Theorem 3.2 proves that checking whether two families of minimal cut sets are equivalent up to permutation is the same as checking whether the associated graphs are isomorphic.
Note that the most efficient algorithms currently available for determining the isomorphism of two graphs exhibit exponential worst-case time complexity (refer to Cormen et al. [Reference Cormen, Leiserson, Rivest and Stein8] for a definition). The enquiry into whether any two graphs are isomorphic holds particular significance as it stands among the NP problems not definitively classified as either solvable in polynomial time or NP-complete (see Babai [Reference Babai1]). However, there are algorithms available for assessing the isomorphism of graphs under specific constraints; for instance, the isomorphism of graphs of bounded degree (refer to Cormen et al. [Reference Cormen, Leiserson, Rivest and Stein8] for a definition) can be tested in polynomial time (Furst et al. [Reference Furst, Hopcroft and Luks15]). Thus there is a degree of optimism regarding the possibility of discovering an algorithm with polynomial worst-case time complexity for determining the isomorphism of two graphs.
Note that the most effective and widely applicable software for isomorphism testing, named NAUTY, is capable of establishing the isomorphism of two graphs with up to 100 vertices in less than a second on a PC (Rosen [Reference Rosen26, p. 674]). Thus we believe that the algorithm we propose can be utilized for the probability vectors of dimension less than 100 using the currently available computational facilities.
4. Applications: Finding all coherent systems of order
$\boldsymbol{n}$
To begin with, let us consider the class of mixed signatures of order n (denoted by
$\mathit{MS}_{n}$
). We know that
$\mathit{MS}_{n}$
is uncountable (Samaniego [Reference Samaniego29]), and any probability vector
${\mathbf{p}} = (p_1, \ldots, p_n)$
in the simplex
\begin{align*}\Biggl\{{\mathbf{p}} \in [0, 1]^n\colon \sum_{i = 1}^{n} p_i = 1\Biggr\}\end{align*}
is a signature of a mixed coherent system. Further, we also know that
$\mathit{MS}_{n}$
includes the class of signatures of coherent systems of order n (denoted by
$\mathit{CS}_{n}$
). To find
$\mathit{CS}_{n}$
, one must be able to define a new class of probability vectors (denoted by
$\mathit{PV}_{n}$
), such that
$$\mathit{CS}_{n} \subseteq \mathit{PV}_{n} \subseteq \mathit{MS}_{n},\quad n \in \mathbb{N},$$
and any probability vector
${\mathbf{p}}$
must satisfy
\begin{align*}{\mathbf{p}} = \biggl(\dfrac{x_1}{n!}, \ldots, \dfrac{x_n}{n!}\biggr),\quad x_1 + \cdots + x_n = n!,\ x_j \geq 0, \ x_j \in \mathbb{Z},\ j = 1, \ldots, n\end{align*}
to belong to the class
$\mathit{PV}_{n}$
. The cardinality of
$\mathit{PV}_{n}$
is finite and is equal to the number of non-negative integer solutions to the n-variable polynomial equation
\begin{align}x_1 + \cdots + x_n = n!.\end{align}
Using Proposition 6.2 of Ross [Reference Ross27, p. 21], we can see that the number of non-negative integer solutions to (4.1) is
$ N_n =\binom{n!+n-1}{n-1}$
. Thus, for a given n, we get a finite number of probability vectors
$N_n$
. Consequently, the cardinality of
$\mathit{CS}_{n}$
is also finite. So, on applying the algorithm on
$\mathit{PV}_{n}$
(i.e. on the class of
$N_n$
probability vectors), one can obtain
$\mathit{CS}_{n}$
(i.e. the class of n-dimensional signature vectors) and simultaneously find the coherent systems with n components. It can be seen that the cardinality of
$\mathit{PV}_{n}$
is equal to
$\mathit{CS}_{n}$
when
$n = 1$
, since there is only one coherent system with one component. Further, when
$n = 2$
,
$\mathit{PV}_{n} = \{(0, 1), (1/2, 1/2), (1, 0)\}$
, whereas
$\mathit{CS}_{n}$
=
$\{(0, 1), (1, 0)\}$
, since there are two coherent systems with two components, namely the series system and parallel system, with the probability vectors (1, 0) and (0, 1) as their respective signatures. Unfortunately, if
$n \gt 2$
, then
$|\mathit{PV}_n| = N_n \gt {\mathrm{e}}^n$
, and this is the reason why we consider n = 3 and 4 (as shown below) in this article. For the case
$n = 5$
, we explore two scenarios in which the algorithm can be applied. This highlights the importance of the algorithm’s utility, particularly when dealing with larger values of n.
4.1. Three-dimensional signature vectors
When
$n = 3$
, the cardinality of
$\mathit{PV}_{3}$
is 28. In Table 2 (see the Appendix) we list all 28 probability vectors of
$\mathit{PV}_{3}$
,
$\mathit{PV}_{3} = \{{\mathbf{p}}_1, \ldots, {\mathbf{p}}_{28}\}$
, and we apply the algorithm to find the signature vectors of order 3 (
$\mathit{CS}_{3}$
) and their corresponding coherent system(s).
-
Step 1. For every
${\mathbf{p}}_i = (p_{i,1},\: p_{i,2},\: p_{i,3}),\:i = 1, \ldots, 28$
, check whether
$ \binom{3}{j}\sum_{k = 1}^{j}p_{i,k}$
is integer for
$j = 1, 2, 3$
. It is evident that for the vectors
${\mathbf{p}}_i$
,
$i = 2, 4, 6, 8, 9, 11, 12, 15$
,
$ \binom{3}{j}\sum_{k = 1}^{j}p_{i,k}$
,
$j = 1, 2, 3$
, are not all integers. As a result, the vectors
${\mathbf{p}}_i$
for
$i = 2, 4, 6, 8, 9, 11, 12$
, and 15, along with their corresponding dual probability vectors
${\mathbf{p}}_i$
for
$i = 27, 23, 13, 26, 24, 17, 21$
, and 20, do not qualify as signatures. Further, note that the self-dual vectors
${\mathbf{p}}_{10}$
and
${\mathbf{p}}_{18}$
are also not signatures. -
Step 2. Since the vector
${\mathbf{p}}_{14}$
and its dual vector
${\mathbf{p}}_{22} $
have internal zeros, we eliminate both of them.Thus the number of probability vectors which can be signatures reduces to 8 from 28, listed as follows:
${\mathbf{p}}_{1}$
,
${\mathbf{p}}_{3}$
,
${\mathbf{p}}_{5}$
,
${\mathbf{p}}_{7}$
,
${\mathbf{p}}_{16}$
,
${\mathbf{p}}_{19}$
(=
${\mathbf{p}}^D_5$
),
${\mathbf{p}}_{25}$
(=
${\mathbf{p}}^D_3$
), and
${\mathbf{p}}_{28}$
(=
${\mathbf{p}}^D_1$
). Further, note that
${\mathbf{p}}_{7}$
and
${\mathbf{p}}_{16}$
are self-dual. -
Step 3. Assume that
${\mathbf{p}}_{1}$
,
${\mathbf{p}}_{3}$
,
${\mathbf{p}}_{5}$
,
${\mathbf{p}}_{7}$
, and
${\mathbf{p}}_{16}$
are signatures of three-component coherent systems. We do not consider
${\mathbf{p}}_{19}$
(=
${\mathbf{p}}^D_5$
),
${\mathbf{p}}_{25}$
(=
${\mathbf{p}}^D_3$
) and
${\mathbf{p}}_{28}$
(=
${\mathbf{p}}^D_1$
), as we know that a vector
${\mathbf{p}}$
is a signature if and only if
${\mathbf{p}}^D$
is a signature (see Lemma 2.5).The vector
$c_i = (c_{i,1}, c_{i,2}, c_{i,3})$
is such that
$c_{i,j}$
is the number of cut sets of size j in the coherent system(s) whose signature is
${\mathbf{p}}_{i}$
and
$ c_{i,j} = \binom{3}{j}\sum_{k = 1}^{j}p_{i,k}$
,
$j = 1, 2, 3$
. Thus we have
$$ c_1 = (0, 0, 1), \quad c_3 = (0, 1, 1),\quad c_5 = (0, 2, 1), \quad c_7 = (0, 3, 1),\quad c_{16} = (1, 2, 1) $$
-
Step 4. Using
$c_i$
, generate the possible families of cut sets corresponding to the coherent system(s) whose signature is
${\mathbf{p}}_{i}$
. For example, consider signature
${\mathbf{p}}_{5}$
, and from
$c_5$
we see that the corresponding coherent system(s) has zero cut sets of size 1, two cut sets of size 2, and one cut set of size 3. The number of possible families of minimal cuts is
$K = 3$
, listed as follows: Similarly, for the other signature vectors, one can easily see the possible families of cut sets, which are are listed in Table 3 (see the Appendix).
\begin{align*}f_{5,1} &= \{\{1, 2\}, \{1, 3\}, \{1, 2, 3\}\},\\f_{5,2} &= \{\{1, 2\}, \{2, 3\}, \{1, 2, 3\}\}, \\f_{5,3} &= \{\{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}.\end{align*}
-
Step 5. From each family of cut sets, remove the supersets to form families of minimal cut sets (see Lemma 2.1). Consider, for example, signature
${\mathbf{p}}_{5}$
. Here, the possible families of minimal cut sets are denoted by
$g_{5, j}$
, as listed below: Note that
\begin{align*}g_{5, 1} =\{\{1, 2\}, \{1, 3\}\}, \quad g_{5, 2} =\{\{1, 2\}, \{2, 3\}\}, \quad g_{5, 3} =\{\{1, 3\}, \{2, 3\}\}.\end{align*}
$ \bigcup_{A_i \in g_{5, r}} A_i = \{1, 2, 3\}$
,
$r = 1, 2, 3$
. Similarly, one can obtain the families of minimal cut sets for
${\mathbf{p}}_{1}$
,
${\mathbf{p}}_{3}$
,
${\mathbf{p}}_{7}$
, and
${\mathbf{p}}_{16}$
, as listed in Table 4 (see the Appendix).
Note that there exists no family of minimal cut sets for
${\mathbf{p}}_3$
. Hence, both
${\mathbf{p}}_3$
and
${\mathbf{p}}_{25}$
(
$= {\mathbf{p}}^D_3$
) are not signatures (assumed in Step 3). Next, corresponding to each
${\mathbf{p}}_{i}$
, consider only those
$g_{i,r}$
which are different up to permutation and denote them by
$h_{i,q}$
, as listed in Table 5 (see the Appendix). Also, corresponding to each
${\mathbf{p}}_{i}$
, there is only one
$h_{i,q}$
, but in general there can be more than one
$h_{i,q}$
. -
Step 6. Using the
$h_{i,q}$
, calculate the maximal signatures
$M_{h_{i, q}}$
. Also, calculate the maximal signature using
${\mathbf{p}}_i$
, i.e.
$M_{{\mathbf{p}}_i} = {\mathbf{p}}_i.U_3$
, for
$i = 1, 5, 7, 16$
. -
Step 7. It can be seen from Table 5 that for
${\mathbf{p}}_{16}$
,
$M_{{\mathbf{p}}_{16}} \neq M_{h_{16, 1}}$
, and hence it is not a signature. However,
$M_{{\mathbf{p}}_{i}} = M_{h_{i, 1}}$
for
$i = 1, 5, 7$
. Thus we conclude that
${\mathbf{p}}_1$
,
${\mathbf{p}}_5$
,
${\mathbf{p}}_7$
are signatures. Further,
${\mathbf{p}}_{19} $
(
$={\mathbf{p}}^D_5$
) and
${\mathbf{p}}_{28}$
(
$ ={\mathbf{p}}^D_1$
) are also signatures (using Lemma 2.5). For the systems whose signatures are
${\mathbf{p}}_1$
,
${\mathbf{p}}_5$
, and
${\mathbf{p}}_7$
, the family of minimal cut sets are, respectively,
$h_{1, 1}, h_{5,1}$
, and
$h_{7, 1}$
, and for the systems whose signatures are
${\mathbf{p}}_{19} $
$({=}{\mathbf{p}}^D_5)$
and
${\mathbf{p}}_{28}$
$ ({=}{\mathbf{p}}^D_1)$
, the family of minimal path sets are, respectively,
$h_{5, 1}$
and
$h_{1, 1}$
.
Table 1. Three-component coherent systems.
Let
$X_1, X_2, X_3$
, be i.i.d. component lifetimes of the three-component coherent systems. The signatures and their coherent systems with three components are listed in Table 1. Thus, using the algorithm, we have obtained
$$\mathit{CS}_{3} = \{{\mathbf{p}}_{1}, {\mathbf{p}}_{5}, {\mathbf{p}}_{7}, {\mathbf{p}}_{19}, {\mathbf{p}}_{28}\}$$
from
$\mathit{PV}_{3}$
, where each of these signatures corresponds to a unique coherent system. This is also supported by the literature, as Shaked and Suarez-Llorens [Reference Shaked and Suarez-Llorens31] mentioned that there exist five coherent systems with three components.
4.2. Four-dimensional signature vectors
When n = 4, the cardinality of
$\mathit{PV}_{4}$
is
$ \binom{27}{3} = 2925$
. Since there are 2925 probability vectors in
$\mathit{PV}_{4}$
, we do not list them the way we did in the previous section. Using the algorithm, we find all four-dimensional signature vectors (
$\mathit{CS}_{4}$
) and the corresponding coherent system(s).
On applying Step 1 of the algorithm, we find that 2886 probability vectors of
$\mathit{PV}_{4}$
are not signatures, and further, using Step 2, we eliminate five more probability vectors of
$\mathit{PV}_{4}$
. Thus, after the first two steps of the algorithm, we eliminate 2891 probability vectors. The remaining 34 probability vectors are listed in Table 6 (see the Appendix).
-
Step 3. Assume that
${\mathbf{p}}_i$
,
$i = 1, \ldots, 15, 19, 20$
, and 22 are signatures of four-component coherent systems. We do not consider their respective dual vectors since a vector
${\mathbf{p}}$
is a signature if and only if
${\mathbf{p}}^D$
is a signature (see Lemma 2.5). Note that
${\mathbf{p}}_{14}$
and
${\mathbf{p}}_{22}$
are self-dual vectors so we also assume they are signatures.The vector
$c_i = (c_{i,1}, c_{i,2}, c_{i,3}, c_{i,4})$
is such that
$c_{i,j}$
is the number of cut sets of size j in the coherent system(s) whose signature is
${\mathbf{p}}_{i}$
and
$ c_{i,j} = \binom{4}{j}\sum_{k = 1}^{j}p_{i,k}$
,
$j = 1, 2, 3, 4$
. We calculate
$c_i$
corresponding to each
${\mathbf{p}}_i$
that we are assuming as a signature (see column 2 of Table 7 in the Appendix). -
Step 4. Using
$c_i$
, generate the possible families of cut sets corresponding to the coherent system(s) whose signature is
${\mathbf{p}}_i$
,
$i = 1, \ldots, 15, 19, 20$
, and 22. Here we have not listed all the
$f_{i,j}$
, since they are very large in number and easy to find. -
Step 5. From each family of cut sets (
$f_{i,j}$
), remove the supersets to form families of minimal cut sets
$g_{i,r}$
corresponding to each signature vector
${\mathbf{p}}_i$
. Next, corresponding to each
${\mathbf{p}}_{i}$
, consider only those
$g_{i,r}$
which are different up to permutation and denote them by
$h_{i,q}$
(see column 3 of Table 7 in the Appendix). -
Step 6. Using the
$h_{i,q}$
, calculate the maximal signatures
$M_{h_{i, q}}$
(see column 4 of Table 7 in the Appendix). Also, calculate the maximal signature using
${\mathbf{p}}_i$
, i.e.
$M_{{\mathbf{p}}_i} = {\mathbf{p}}_i.U_4$
(see column 5 of Table 7 in the Appendix). -
Step 7. It can be seen from Table 7 (see the Appendix) that for
${\mathbf{p}}_{6}$
,
${\mathbf{p}}_{7}$
,
${\mathbf{p}}_{10}$
,
${\mathbf{p}}_{11}$
,
${\mathbf{p}}_{15}$
,
${\mathbf{p}}_{19}$
,
${\mathbf{p}}_{20}$
, and
${\mathbf{p}}_{22}$
,
$M_{{\mathbf{p}}_i} \neq M_{h_{i, q}}$
and hence they are not signatures. Further,
${\mathbf{p}}_{21}$
$( = {\mathbf{p}}^D_{15})$
,
$ {\mathbf{p}}_{24}$
$( = {\mathbf{p}}^D_{20})$
,
${\mathbf{p}}_{25}$
$( = {\mathbf{p}}^D_{11})$
,
${\mathbf{p}}_{28}$
$( = {\mathbf{p}}^D_{19})$
,
${\mathbf{p}}_{30}$
(
$ = {\mathbf{p}}^D_{7}$
), and
${\mathbf{p}}_{32}$
(
$ = {\mathbf{p}}^D_{6}$
) are also not signatures (see Lemma 2.5).
The vectors
${\mathbf{p}}_{1}$
,
${\mathbf{p}}_{3}$
,
${\mathbf{p}}_{4}$
,
${\mathbf{p}}_{5}$
,
${\mathbf{p}}_{8}$
,
${\mathbf{p}}_{9}$
,
${\mathbf{p}}_{12}$
,
${\mathbf{p}}_{13}$
, and
${\mathbf{p}}_{14}$
are signature vectors since there exists at least one q such that
$M_{{\mathbf{p}}_i} = M_{h_{i, q}}$
. Further,
${\mathbf{p}}_{16}$
(
$= {\mathbf{p}}^D_{12}$
),
${\mathbf{p}}_{17}$
(
$={\mathbf{p}}^D_{9}$
),
${\mathbf{p}}_{18}$
(
$= {\mathbf{p}}^D_{5}$
),
${\mathbf{p}}_{26}$
$(={\mathbf{p}}^D_{8})$
,
${\mathbf{p}}_{23}$
$(={\mathbf{p}}^D_{13}$
)
${\mathbf{p}}_{27}$
(
$ ={\mathbf{p}}^D_{4}$
),
${\mathbf{p}}_{31}$
(
$={\mathbf{p}}^D_{3}$
), and
${\mathbf{p}}_{34}$
(
$= {\mathbf{p}}^D_{1}$
) are also signatures (see Lemma 2.5). For the systems whose signatures are
${\mathbf{p}}_{1}$
,
${\mathbf{p}}_{3}$
,
${\mathbf{p}}_{4}$
,
${\mathbf{p}}_{5}$
,
${\mathbf{p}}_{8}$
,
${\mathbf{p}}_{9}$
,
${\mathbf{p}}_{12}$
,
${\mathbf{p}}_{13}$
, and
${\mathbf{p}}_{14}$
, the family of minimal cut sets are, respectively,
$h_{1, 1}$
,
$h_{3, 1}$
,
$h_{4, 1}$
,
$h_{5, 1}$
,
$h_{8, 1}$
,
$h_{9, 1}$
,
$\{h_{12, 1}, h_{12, 2}\}$
,
$h_{13, 1}$
, and
$\{h_{14, 1}, h_{14, 2}\}$
. For the systems whose signatures are
${\mathbf{p}}_{16}$
(
$= {\mathbf{p}}^D_{12}$
),
${\mathbf{p}}_{17}$
(
$ ={\mathbf{p}}^D_{9}$
),
${\mathbf{p}}_{18}$
(
$= {\mathbf{p}}^D_{5}$
),
${\mathbf{p}}_{26}$
(
$ ={\mathbf{p}}^D_{8}$
),
${\mathbf{p}}_{23}$
(
$ ={\mathbf{p}}^D_{13}$
)
${\mathbf{p}}_{27}$
(
$ ={\mathbf{p}}^D_{4}$
),
${\mathbf{p}}_{31}$
(
$ ={\mathbf{p}}^D_{3}$
), and
${\mathbf{p}}_{34}$
(
$= {\mathbf{p}}^D_{1}$
), the family of minimal path sets are, respectively,
$\{h_{12, 1}, h_{12, 2}\}$
,
$h_{9, 1}$
,
$h_{5, 1}$
,
$h_{8, 1}$
,
$h_{13, 1}$
,
$h_{4, 1}$
,
$h_{3, 1}$
, and
$h_{1, 1}$
.
Let
$X_1, X_2, X_3, X_4$
, be i.i.d. component lifetimes of the four-component coherent systems. We list the signatures and the corresponding coherent system(s) in Table 8 (see the Appendix).
Thus, using the algorithm, we have obtained
$$ \mathit{CS}_{4} = \{{\mathbf{p}}_{1}, {\mathbf{p}}_{3}, {\mathbf{p}}_{4}, {\mathbf{p}}_{5}, {\mathbf{p}}_{8}, {\mathbf{p}}_{9}, {\mathbf{p}}_{12}, {\mathbf{p}}_{13}, {\mathbf{p}}_{14}, {\mathbf{p}}_{16}, {\mathbf{p}}_{17}, {\mathbf{p}}_{18}, {\mathbf{p}}_{23}, {\mathbf{p}}_{26}, {\mathbf{p}}_{27}, {\mathbf{p}}_{31}, {\mathbf{p}}_{34}\} $$
from
$\mathit{PV}_{4}$
, where each of the signatures
${\mathbf{p}}_{12}$
,
${\mathbf{p}}_{16}$
(
$ = {\mathbf{p}}^D_{12}$
), and
${\mathbf{p}}_{14}$
corresponds to two different coherent systems, while 14 other signatures each correspond to a unique coherent system. This is also supported by the literature, as Shaked and Suarez-Llorens [Reference Shaked and Suarez-Llorens31] mentioned that there exist 20 coherent systems with four components. Note that the cardinality of
$\mathit{CS}_{4}$
is 17 and that of (
$\mathit{PV}_{4}$
$\setminus$
$\mathit{CS}_{4}$
) is 2908.
4.3. Five-dimensional signature vectors
We found all the coherent systems of order
$n = 3$
and 4, i.e.
$\mathit{CS}_{3}$
and
$\mathit{CS}_{4}$
. Furthermore, we believe that the algorithm can be extended to cases where
$n \gt 4$
. To substantiate this assertion, although we were unable to explore all the probability vectors within
$\mathit{PV}_{5}$
due to the computational complexity involved, we have considered two specific scenarios. We consider probability vectors
${\mathbf{p}} = (0, 0, 0, 2/5, 3/5)$
(in Scenario 4.1) and
$\mathbf{q} = (3/5, 1/5, 1/5, 0, 0)$
(in Scenario 4.2) belonging to
$\mathit{PV}_{5}$
. The reason for considering them is that while finding all coherent systems of order 5 and their signatures, Navarro and Rubio [Reference Navarro and Rubio20] listed
${\mathbf{p}}$
as the signature of system 179, and its dual
${\mathbf{p}}^D$
for system 2. However,
$\mathbf{q}$
does not appear in their list and the same will be verified below by showing that it is not a signature.
Figure 2. Coherent systems corresponding to the signatures
$\textbf{p}$
and
$\textbf{p}^D$
.
Scenario 4.1. Consider the five-dimensional probability vector
${\mathbf{p}} = (0, 0, 0, 2/5, 3/5)$
.
-
Step 1. Here we see that
$ \binom{5}{j}\sum_{k = 1}^{j}p_{k}$
is an integer for
$j = 1, \ldots, 5$
. Hence we consider
${\mathbf{p}}$
for the next step. -
Step 2. Since
${\mathbf{p}}$
has no internal zeros, we consider
${\mathbf{p}}$
for Step 3. -
Step 3. Assume that
${\mathbf{p}}$
is a system signature of a five-component coherent system. Then the vector
$c = (c_1, c_2, c_3, c_4, c_5) = (0, 0, 0, 2, 1)$
is such that
$c_j$
is the number of cut sets of size j and
$c_j = \binom{5}{j}\sum_{k = 1}^{j}p_{k}$
,
$ j = 1, \ldots, 5$
. -
Step 4. Using c, generate the possible families of cut sets corresponding to the coherent system (s) whose signature is
${\mathbf{p}}$
. The coherent system(s) has two cut sets of size 4 and one cut set of size 5. Hence there are
$K = 10$
possible families of cut sets (
$f_j$
). -
Step 5. From each family of cut sets, remove the supersets to form the possible families of minimal cut sets (see Lemma 2.1). Here the possible families of minimal cut sets are denoted by
$g_r$
. Note that
$ \bigcup_{A_i \in g_r}^{} A_i = \{1, 2, 3, 4, 5\}$
,
$r = 1, \ldots, 10$
. Further, the families of minimal cut sets
$g_1, \ldots, g_{10}$
, are all equivalent up to permutation. So, we consider only one of them and denote it by
$h_1$
. Without loss of generality, we take
$h_1$
=
$\{\{1, 2, 3, 4\}, \{1, 2, 3, 5\}\}$
. -
Step 6. Using
$h_1$
, calculate the maximal signature
$M_{h_{1}}$
;
$M_{h_{1}} = (0, 0, 0, 2, -1)$
. Also, calculate the maximal signature using
${\mathbf{p}}$
, i.e.
$M_{{\mathbf{p}}} = {\mathbf{p}}.U_5$
$ = (0, 0, 0, 2, -1)$
. -
Step 7. It can be seen that
$M_{h_{1}} = M_{{\mathbf{p}}}$
, and hence
${\mathbf{p}}$
is a signature (as assumed in Step 3). Further,
${\mathbf{p}}^D = (3/5, 2/5, 0, 0, 0)$
is also a signature (using Lemma 2.5).
It is evident that
${\mathbf{p}}$
is a signature of only one coherent system. Similarly,
${\mathbf{p}}^D$
also corresponds to only one coherent system (using Lemma 2.5). For the system (say
$\Phi$
) whose signature is
${\mathbf{p}}$
, the family of minimal cut sets is
$h_{1}$
, and for the system (say
$\Phi^D$
) whose signature is
${\mathbf{p}}^D$
, the family of minimal path sets is
$h_{1}$
.
Let
$X_i$
,
$i = 1, \ldots, 5$
be the component lifetimes. Then the coherent system corresponding to
${\mathbf{p}}$
is
\begin{align*}\Phi(X_1, X_2, X_3,& X_4, X_5) = \min(\max(X_1, X_2, X_3, X_4 ),\max(X_1, X_2, X_3, X_5 )),\end{align*}
and the coherent system corresponding to
${\mathbf{p}}^D$
is
\begin{align*}\Phi^{D}(X_1, X_2, X_3,& X_4, X_5) = \max(\min(X_1, X_2, X_3, X_4 ),\min(X_1, X_2, X_3, X_5 )).\end{align*}
See Figure 2.
Scenario 4.2. Consider the five-dimensional probability vector
$\mathbf{q} = (3/5, 1/5, 1/5, 0, 0)$
.
-
Step 1. Here we see that
$ \binom{5}{j}\sum_{k = 1}^{j}q_{k}$
is an integer for
$j = 1, \ldots, 5$
. Hence we consider
$\mathbf{q}$
for the next step. -
Step 2. Since
$\mathbf{q}$
has no internal zeros, we consider
$\mathbf{q}$
for Step 3. -
Step 3. Assume that
$\mathbf{q}$
is a system signature of a five-component coherent system. Then the vector
$c = (c_1, c_2, c_3, c_4, c_5) = (3, 8, 1, 1, 1)$
is such that
$c_j$
is the number of cut sets of size j and
$c_j = \binom{5}{j}\sum_{k = 1}^{j}q_{k}$
,
$ j = 1, \ldots, 5$
. -
Step 4. Using c, generate the possible families of cut sets corresponding to the coherent system(s) whose signature is
$\mathbf{q}$
. The coherent system(s) has three cut sets of size 1, eight cut sets of size 2, one cut set of size 3, one cut set of size 4, and one cut set of size 5. Hence there are
$22\,500$
possible families of cut sets, say
$f_1, \ldots, f_{22\,500}$
. Here we have not listed the
$f_{j}$
, since they are very large in number and easy to find. -
Step 5. From each family of cut sets, remove the supersets to form families of minimal cut sets. The possible families of minimal cut sets are denoted by
$g_{r}$
, and note that
$ \bigcup_{A_i \in g_{r}} A_i = \{1, 2, 3, 4, 5\}$
. Here we have not listed the
$g_{r}$
's, since they are very large in number and one can easily obtain them from the
$f_{j}$
's. We observe that the
$g_{r}$
's are all equivalent up to permutation to
$ h_1 = \{\{1\}, \{2\}, \{3\}$
,
$ \{4, 5\}\}$
. -
Step 6. Using
$h_1$
, calculate the maximal signature
$M_{h_{1}}$
;
$M_{h_{1}} = (3, -2, -2, 3, -1)$
. Also, calculate the maximal signature using
$\mathbf{q}$
, i.e.
$M_{\mathbf{q}} = \mathbf{q}.U_5$
$ = (3, -4, 4, -3, 1)$
. -
Step 7. It can be seen that
$M_{h_1} \neq M_{\mathbf{q}}$
, and hence
$\mathbf{q}$
is not a signature (using Corollary 3.1). Further,
$\mathbf{q}^D = (0, 0, 1/5, 1/5, 3/5)$
is also not a signature (using Lemma 2.5).
Thus we have shown that
${\mathbf{p}}$
and
${\mathbf{p}}^D$
are signatures, while
$\mathbf{q}$
and
$\mathbf{q}^D$
are not signatures as they do not satisfy the conditions of the algorithm. Note that although
$\mathbf{q}$
satisfies the first two steps, it fails while comparing maximal signatures that are obtained using
$h_1$
and
$\mathbf{q}$
(i.e. Step 6). This highlights the significance of this particular step in our algorithm and justifies its inclusion.
5. Conclusion
For a given a coherent system with i.i.d. components, there exists a probability vector known as the system signature (Samaniego [Reference Samaniego28]). In the literature there are algorithms to compute the signature of a given system. It is also very well known in the literature (Navarro and Rubio [Reference Navarro and Rubio20]) that there exists a relation between the system signature and the maximal signature. Further, it is also known that the maximal signature can be obtained using the family of minimal cut sets of a given coherent system (Navarro [Reference Navarro19]). Using these notions, we introduced an algorithm that uses the important properties of the signature in order to differentiate between a probability vector and a system signature. Thus we provide necessary and sufficient conditions for a probability vector to be a system signature. Our proposed algorithm, and the associated Corollary 3.1, is not only a perfect tool to check whether a given probability vector of size n is a signature, but it also assists in finding all the signature vectors of order n and the corresponding coherent system(s), as discussed in Section 4.
We would also like to point out that to verify whether a given probability vector is a signature, one can also directly apply Steps 3–7 of the algorithm to get the answer. However, we emphasize that if we are given all the probability vectors
${\mathbf{p}} = (p_1, \ldots, p_n)$
$\in$
$\mathit{PV}_{n}$
,
$n \geq 3$
, one should first check Step 1 of the algorithm, i.e. whether
$\binom{n}{j}\sum_{i = 1}^{j}p_i$
for
$j = 1, \ldots, n$
are integers. The reason for saying this is because Step 1 gives the maximum reduction in number of probability vectors and is also easy to verify. For instance, when
$n = 3$
and 4, Step 1 eliminates 78.26% and 99.35% of the probability vectors that are not signatures. Similarly, when
$n = 5$
,
$\mathit{PV}_{n}$
has
$N_n = 93\,81\,251$
probability vectors. However, after the application of Step 1, we are left with only 336 probability vectors i.e. 99.99% of elimination is achieved. Thus Step 1 is crucial in the elimination process. Moreover, Step 2 is also significant because it focuses on the ‘No internal zeros property’, which is of practical importance in reliability. Note that when
$n = 3$
, Step 2 (in combination with Step 1) facilitates elimination of 87% of the probability vectors that are not signatures.
We also observe that the cardinality of
$\mathit{PV}_{3}$
is 28, whereas the cardinality of
$\mathit{CS}_{3}$
is 5. It indicates that there are 23 probability vectors in
$\mathit{PV}_{3}$
that are not signatures of coherent systems of order 3. Similarly, in
$\mathit{PV}_{4}$
and
$\mathit{PV}_{5}$
are, respectively, 2908 and
$93\,81\,172$
probability vectors that are not signatures of coherent systems of order 4 and 5, respectively. Hence the cardinality of
$\mathit{CS}_{4}$
and
$\mathit{CS}_{5}$
, respectively, is 17 and 79 (as shown in Navarro and Rubio [Reference Navarro and Rubio20]). Thus, via this study, we have been able to get some insight into how large
$\mathit{PV}_{n} \subseteq \mathit{MS}_{n}$
,
$n \geq 2$
can be.
Although the above discussion provides an intuition that our proposed algorithm will be applicable to large n
$(n \gt 4)$
, we have not been able to list them due to computational difficulty since the cardinality of
$\mathit{PV}_{n}$
,
$ N_n =\binom{n!+n-1}{n-1}$
grows faster than
${\mathrm{e}}^n$
,
$n \geq 2$
. Furthermore, as n grows large, the main computational difficulty occurs in Step 5 of the algorithm, as discussed in Section 3.1. In Step 5 of the algorithm we try to find suitable families of minimal cut sets from the set of all possible families of minimal cut sets, which is very tedious. However, we believe that studying some more properties of the signature vector would reduce the size of the set of all possible families of minimal cut sets. A study to explore some more nuanced properties of system signatures would be an interesting research direction.
Appendix
Table 2. Three-dimensional candidate signature vectors (
$\mathit{PV}_{3}$
).
Table 3. Possible families of cut sets.
Table 4. Possible families of minimal cut sets.
Table 5. Maximal signatures.
Table 6. Four-dimensional candidate signature vector (
$PV_4$
).
Table 7. Minimal cut sets and maximal signatures.
Table 8. Four-component coherent systems.
Acknowledgements
The authors would like to thank the Editor-in-Chief, the Associate Editor, and the anonymous reviewers for several helpful suggestions which have significantly improved the manuscript.
Funding information
T. V. Rao would like to acknowledge the financial support of the Indian Institute of Technology Hyderabad.
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
