Estimating Network Characteristics in Stochastic Activity Networks
Management Science · 1985 · Volume 31 · Issue 5
Abstract
This paper describes a Monte Carlo method based on the theory of quasirandom points for estimating the distribution functions and means of network completion time and shortest path time in a stochastic activity network. In particular, the method leads to estimators whose absolute errors converge as (log K ) N / K , where K denotes the number of replications collected in the experiment and N is the number of dimensions for sampling. This rate compares favorably with the standard error of estimate O (1/ K 1/2 ) which obtains for experiments that use random sampling. Moreover, since quasirandom points are nonrandom the upper bound (log K ) N / K is deterministic in contrast to the random sampling rate O (1/ K 1/2 ) which is probabilistic. The paper demonstrates how the use of a cutset of the network reduces N in the bound when estimating the distribution functions. Two examples illustrate the benefits and costs of using quasirandom points.
Keywords
Monte Carlo method, networks, quasirandom points, variance reduction
Enable JavaScript for citation tools and additional paper interactions.