Estimating Network Characteristics in Stochastic Activity Networks

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.