As there are 
such partitions (there are 
ways of choosing a nonempty proper subset 
and, as the partition 
is the same as 
, we must divide by 2) there are therefore this number of minimal cut sets.
To determine the minimal path sets, we must characterize a minimal set of arcs that results in a connected graph. The graph in Figure 9.13 is connected but it would remain connected if any one of the arcs from the cycle shown in Figure 9.14 were removed. In fact it is not difficult to see that the minimal path sets are exactly those sets of arcs that result in a graph being connected but not having any cycles (a cycle being a path from a node to itself). Such sets of arcs are called spanning trees (Figure 9.15). It is easily verified that any spanning tree contains exactly 
arcs, and it is a famous result in graph theory (due to Cayley) that there are exactly 
of these minimal path sets.
Because of the large number of minimal path and minimal cut sets (
and 
, respectively), it is difficult to obtain any useful bounds without making further restrictions. So, let us assume that all the 
equal the common value 
. That is, we suppose that each of the possible arcs exists, independently, with the same probability 
. We shall start by deriving a recursive formula for the probability that the graph is connected, which is computationally useful when 
is not too large, and then we shall present an asymptotic formula for this probability when 
is large.
Let us denote by 
the probability that the random graph having 
nodes is connected. To derive a recursive formula for 
we first concentrate attention on a single node—say, node 1—and try to determine the probability that node 1 will be part of a component of size 
in the resultant graph. Now, for a given set of 
other nodes these nodes along with node 1 will form a component if
(i) there are no arcs connecting any of these 
nodes with any of the remaining 
nodes;
(ii) the random graph restricted to these 
nodes (and 
potential arcs—each independently appearing with probability 
) is connected.
The probability that (i) and (ii) both occur is
where 
. As there are 
ways of choosing 
other nodes (to form along with node 1 a component of size 
) we see that
Now, since the sum of the foregoing probabilities as 
ranges from 1 through 
clearly must equal 1, and as the graph is connected if and only if node 1 is part of a component of size 
, we see that
(9.9)
Starting with 
, Equation (9.9) can be used to determine 
recursively when 
is not too large. It is particularly suited for numerical computation.
To determine an asymptotic formula for 
when 
is large, first note from Equation (9.9) that since 
, we have
As it can be shown that for 
and 
sufficiently large,
we have that for 
large
(9.10)
To obtain a bound in the other direction, we concentrate our attention on a particular type of minimal cut set—namely, those that separate one node from all others in the graph. Specifically, define the minimal cut set 
as
and define 
to be the event that all arcs in 
are not working (and thus, node 
is isolated from the other nodes). Now,
since, if any of the events 
occur, then the graph will be disconnected. By the inclusion–exclusion bounds, we have
As 
and 
are just the respective probabilities that a given set of 
arcs and a given set of 
arcs are not in the graph (why?), it follows that
and so
Combining this with Equation (9.10) yields that for 
sufficiently large,
and as
as 
, we see that, for large 
,
Thus, for instance, when 
and 
, the probability that the random graph will be connected is approximately given by
9.4.2 Second Method for Obtaining Bounds on r(p)
Our second approach to obtaining bounds on 
is based on expressing the desired probability as the probability of the intersection of events. To do so, let 
denote the minimal path sets as before, and define the events, 
by
Now since the system will have failed if and only if at least one component in each of the minimal path sets has failed we have
(9.11)Now it is quite intuitive that the information that at least one component of 
is down can only increase the probability that at least one component of 
is down (or else leave the probability unchanged if 
and 
do not overlap). Hence, intuitively
To prove this inequality, we write
(9.12)and note that
Hence, from Equation (9.12) we see that
or
By the same reasoning, it also follows that
and so from Equation (9.11) we have
or, equivalently,
To obtain a bound in the other direction, let 
denote the minimal cut sets and define the events 
by
Then, since the system will function if and only if all of the events 
occur, we have
where the last inequality is established in exactly the same manner as for the 
. Hence,
and we thus have the following bounds for the reliability function:
(9.13)
It is to be expected that the upper bound should be close to the actual 
if there is not too much overlap in the minimal path sets, and the lower bound to be close if there is not too much overlap in the minimal cut sets.
Example 9.19
For the three-out-of-four system the minimal path sets are 
, and 
; and the minimal cut sets are 
, 
, and 
. Hence, by Equation (9.13) we have
where 
. For instance, if 
for all 
, then the preceding yields
The exact value for this structure is easily computed to be
9.5 System Life as a Function of Component Lives
For a random variable having distribution function 
, we define 
to be the probability that the random variable is greater than 
.
Consider a system in which the 
th component functions for a random length of time having distribution 
and then fails. Once failed it remains in that state forever. Assuming that the individual component lifetimes are independent, how can we express the distribution of system lifetime as a function of the system reliability function 
and the individual component lifetime distributions 
?
To answer this we first note that the system will function for a length of time 
or greater if and only if it is still functioning at time 
. That is, letting 
denote the distribution of system lifetime, we have
But, by the definition of 
we have
where
Hence, we see that
(9.14)Example 9.20
In a series system, 
and so from Equation (9.14)
which is, of course, quite obvious since for a series system the system life is equal to the minimum of the component lives and so will be greater than 
if and only if all component lives are greater than 
. ■
Example 9.21
In a parallel system 
and so
The preceding is also easily derived by noting that, in the case of a parallel system, the system life is equal to the maximum of the component lives. ■
For a continuous distribution 
, we define 
, the failure rate function of 
, by
where 
. In Section 5.2.2, it is shown that if 
is the distribution of the lifetime of an item, then 
represents the probability intensity that a 
-year-old item will fail. We say that 
is an increasing failure rate (IFR) distribution if 
is an increasing function of 
. Similarly, we say that 
is a decreasing failure rate (DFR) distribution if 
is a decreasing function of 
.
Example 9.22
The Weibull Distribution
A random variable is said to have the Weibull distribution if its distribution is given, for some 
, by
The failure rate function for a Weibull distribution equals
Thus, the Weibull distribution is IFR when 
, and DFR when 
; when 
, the exponential distribution, which is both IFR and DFR. ■
Example 9.23
The Gamma Distribution
A random variable is said to have a gamma distribution if its density is given, for some 
, by
where
For the gamma distribution,
With the change of variables 
, we obtain
Hence, 
is IFR when 
and is DFR when 
. ■
Suppose that the lifetime distribution of each component in a monotone system is IFR. Does this imply that the system lifetime is also IFR? To answer this, let us at first suppose that each component has the same lifetime distribution, which we denote by 
. That is, 
. To determine whether the system lifetime is IFR, we must compute 
, the failure rate function of 
. Now, by definition,
where
Hence,
(9.15)
Since 
is a decreasing function of 
, it follows from Equation (9.15) that if each component of a coherent system has the same IFR lifetime distribution, then the distribution of system lifetime will be IFR if 
is a decreasing function of 
.
Example 9.24
The k 
-out-of-n 
System with Identical Components
Consider the 
-out-of-
system, which will function if and only if 
or more components function. When each component has the same probability 
of functioning, the number of functioning components will have a binomial distribution with parameters 
and 
. Hence,
which, by continual integration by parts, can be shown to be equal to
Upon differentiation, we obtain
Therefore,
Letting 
yields
Since 
is increasing in 
, it follows that 
is decreasing in 
. Thus, if a 
-out-of-
system is composed of independent, like components having an increasing failure rate, the system itself has an increasing failure rate. ■
It turns out, however, that for a 
-out-of-
system, in which the independent components have different IFR lifetime distributions, the system lifetime need not be IFR. Consider the following example of a two-out-of-two (that is, a parallel) system.
Example 9.25
A Parallel System That Is Not IFR
The life distribution of a parallel system of two independent components, the 
th component having an exponential distribution with mean 
, is given by
Therefore,
It easily follows upon differentiation that the sign of 
is determined by 
, which is positive for small values and negative for large values of 
. Therefore, 
is initially strictly increasing, and then strictly decreasing. Hence, 
is not IFR. ■
Remark
The result of the preceding example is quite surprising at first glance. To obtain a better feel for it we need the concept of a mixture of distribution functions. The distribution function 
is said to be a mixture of the distributions 
and 
if for some 
,
(9.16)
Mixtures occur when we sample from a population made up of two distinct groups. For example, suppose we have a stockpile of items of which the fraction 
are type 1 and the fraction 
are type 2. Suppose that the lifetime distribution of type 1 items is 
and of type 2 items is 
. If we choose an item at random from the stockpile, then its life distribution is as given by Equation (9.16).
Consider now a mixture of two exponential distributions having rates 
and 
where 
. We are interested in determining whether or not this mixture distribution is IFR. To do so, we note that if the item selected has survived up to time 
, then its distribution of remaining life is still a mixture of the two exponential distributions. This is so since its remaining life will still be exponential with rate 
if it is type 1 or with rate 
if it is a type 2 item. However, the probability that it is a type 1 item is no longer the (prior) probability 
but is now a conditional probability given that it has survived to time 
. In fact, its probability of being a type 1 is
As the preceding is increasing in 
, it follows that the larger 
is, the more likely it is that the item in use is a type 1 (the better one, since 
). Hence, the older the item is, the less likely it is to fail, and thus the mixture of exponentials far from being IFR is, in fact, DFR.
Now, let us return to the parallel system of two exponential components having respective rates 
and 
. The lifetime of such a system can be expressed as the sum of two independent random variables, namely,
The first random variable whose distribution is exponential with rate 
represents the time until one of the components fails, and the second, which is a mixture of exponentials, is the additional time until the other component fails. (Why are these two random variables independent?)
Now, given that the system has survived a time 
, it is very unlikely when 
is large that both components are still functioning, but instead it is far more likely that one of the components has failed. Hence, for large 
, the distribution of remaining life is basically a mixture of two exponentials—and so as 
becomes even larger its failure rate should decrease (as indeed occurs). ■
Recall that the failure rate function of a distribution 
having density 
is defined by
By integrating both sides, we obtain
Hence,
(9.17)
where
The function 
is called the hazard function of the distribution 
.
Definition 9.1
A distribution 
is said to have increasing failure on the average (IFRA) if
(9.18)
increases in 
for 
.
In other words, Equation (9.18) states that the average failure rate up to time 
increases as 
increases. It is not difficult to show that if 
is IFR, then 
is IFRA; but the reverse need not be true.
Note that 
is IFRA if 
whenever 
, which is equivalent to
But by Equation (9.17) we see that 
, and so the preceding is equivalent to
or equivalently,
which, since log 
is a monotone function of 
, shows that 
is IFRA if and only if
(9.19)
For a vector 
we define 
. We shall need the following proposition.
Proposition 9.2
Any reliability function 
satisfies
Proof
We prove this by induction on 
, the number of components in the system. If 
, then either 
. Hence, the proposition follows in this case.
Assume that Proposition 9.2 is valid for all monotone systems of 
components and consider a system of 
components having structure function 
. By conditioning upon whether or not the 
th component is functioning, we obtain
(9.20)
Now consider a system of components 1 through 
having a structure function 
. The reliability function for this system is given by 
; hence, from the induction assumption (valid for all monotone systems of 
components), we have
Similarly, by considering the system of components 1 through 
and structure function 
, we obtain
Thus, from Equation (9.20), we obtain
which, by using the lemma to follow (with 
, 
), implies that
which proves the result. ■
Lemma 9.3
If 
, then
for all 
.
We are now ready to prove the following important theorem.
Proof
The distribution of system lifetime 
is given by
Hence, since 
is a monotone function, and since each of the component distributions 
is IFRA, we obtain from Equation (9.19)
which by Equation (9.19) proves the theorem. The last inequality followed, of course, from Proposition 9.2. ■
9.6 Expected System Lifetime
In this section, we show how the mean lifetime of a system can be determined, at least in theory, from a knowledge of the reliability function 
and the component lifetime distributions 
.
Since the system’s lifetime will be 
or larger if and only if the system is still functioning at time 
, we have
where 
. Hence, by a well-known formula that states that for any nonnegative random variable 
,
we see that*
(9.21)
Example 9.26
A Series System of Uniformly Distributed Components
Consider a series system of three independent components each of which functions for an amount of time (in hours) uniformly distributed over (
). Hence, 
and
Therefore,
and so from Equation (9.21) we obtain
Example 9.27
A Two-out-of-Three System
Consider a two-out-of-three system of independent components, in which each component’s lifetime is (in months) uniformly distributed over (
). As was shown in Example 9.13, the reliability of such a system is given by
Since
we see from Equation (9.21) that