Generating the states of a binary stochastic system

An important aspect of planning a communication or distribution system is assessing its performance when the components are subject to random failure. Since exact calculation of stochastic performance measures is usually difficult, the behavior of the system can instead be approximated by generating a subset of all system states. Specifically, the authors consider here the generation of states of a binary stochastic system in order of nonincreasing probability. Such an ordering ensures that maximum coverage of the state space (in terms of probability) will be obtained for a specified number of generated states. The authors identify a particular discrete structure, a distributive lattice, underlying this generation problem, and use this structure to guide an algorithm for generating in order the states of the given system. Computational results suggest that the proposed method improves on existing algorithms for this generation problem.