State space partition algorithms for stochastic systems with applications to minimum spanning trees

We investigated state space partition methods for computing probability measures related to the operation of stochastic systems and present new theoretical results concerning their efficiency. These methods iteratively partition the system state space, producing at each step progressively tighter bounds that can be used for constructing simple and efficient Monte Carlo routines for estimating the probabilities of interest. We apply our findings to the evaluation of measures related to minimum spanning trees in graphs whose edges have independent discrete random weights. Specifically, we seek to compute the distribution of the weight of a minimum spanning tree and the probability that a given edge belongs to a minimum spanning tree. Both of these unsolved problems are shown to be #P-hard. The algorithms for the minimum spanning tree problems are immediately applicable to other matroid problems with randomly weighted elements.