Conventional and Improved Inclusion-Exclusion Derivations of Symbolic Expressions for the Reliability of a Multi-State Network

This paper deals with an emergent variant of the classical problem of computing the probability of the union of n events, or equivalently the expectation of the disjunction (ORing) of n indicator variables for these events, i.e., the probability of this disjunction being equal to one. The variant considered herein deals with multi-valued variables, in which the required probability stands for the reliability of a multi-state delivery network (MSDN), whose binary system success is a two-valued function expressed in terms of multi-valued component successes. The paper discusses a simple method for handling the afore-mentioned problem in terms of a standard example MSDN, whose success is known in minimal form as the disjunction of prime implicants or minimal paths of the pertinent network. This method utilizes the multi-state inclusion-exclusion (MS-IE) principle associated with a multi-state generalization of the idempotency property of the ANDing operation. The method discussed is illustrated with a detailed symbolic example of a real-case study, and it produces a more precise version of the same numerical value that was obtained earlier. The example demonstrates the notorious shortcomings and the extreme inefficiency that the MS-IE method suffers, but, on the positive side, it reveals the way to alternative methods, in which such a shortcoming is (partially) mitigated. A prominent and well known example of these methods is the construction of a multi-state probability-ready expression (MS-PRE). Another candidate method would be to apply the MS-IE principle to the union of fewer (factored or composite) paths that is converted (at minimal cost) to PRE form. A third candidate method, employed herein, is a novel method for combining the MS-PRE and MS-IE concepts together. It confines the use of MS-PRE to ‘shellable’ disjointing of ORed terms, and then applies MS-IE to the resulting partially orthogonalized disjunctive form. This new method makes the most of both MS-PRE and MS-IE, and bypasses the troubles caused by either of them. The method is illustrated successfully in terms of the same real-case problem used with the conventional MS-IE.