Knowledge that Transforms

An influence diagram is a network representation for probabilistic and decision analysis models. The nodes correspond to variables which can be constants, uncertain quantities, decisions, or objectives. The arcs reveal the probabilistic dependence of the uncertain quantities and the information available at the time of the decisions. The detailed data about the variables are stored within the nodes, so the diagram graph is compact and focuses attention on the relationships among the variables. Influence diagrams are effective communication tools and recent developments also allow them to be used for analysis. We develop algorithms to address questions of inference within a probabilistic model represented as an influence diagram. We use the conditional independence implied by the diagram's structure to determine the information needed to solve a given problem. When there is enough information we can solve it, exploiting that conditional independence. These same results are applied to problems of decision analysis. This methodology allows the construction of computer tools to maintain and evaluate complex models.

This paper considers the problem of determining the mean and distribution of the length of a minimal spanning tree (MST) on an undirected graph whose arc lengths are independently distributed random variables. We obtain bounds and approximations for the MST length and show that our upper bound is much tighter than the naive bound obtained by computing the MST length of the deterministic graph with the respective means as arc lengths. We analyze the asymptotic properties of our approximations and establish conditions under which our bounds are asymptotically optimal. We apply these results to a network provisioning problem and show that the relative error induced by using our approximations tends to zero as the graph grows large.