Accession Number:

ADA099287

Title:

Accelerated Accuracy in the Simulation of Markov Chains.

Descriptive Note:

Technical rept.,

Corporate Author:

NORTH CAROLINA UNIV AT CHAPEL HILL

Personal Author(s):

Report Date:

1981-01-01

Pagination or Media Count:

45.0

Abstract:

This paper describes a method of obtaining results from the simulation of a finite state positive recurrent aperiodic Markov chain at a cost considerably below the cost required to achieve the same accuracy with pure random sampling. By reorganizing k independent epochs or tours simulated serially into k replications simulated in parallel, one can induce selected joint distributions across replications that produce the cost-saving benefits. The joint distributions follow from the use of rotation sampling, a special case of the antithetic variate method. For a finite state nearest neighbor chain the paper shows that even for independent parallel replications the cost of achieving a specified accuracy with serial simulation relative to the cost for parallel simulation has a lower bound 0 sq. rt. of k as k approaches infinity. When rotation sampling is used this bound is 0k squared1n k cubed. This lower bound also holds for the more general finite state chains. A simulation of the MM1 queueing model with finite capacity n is used to illustrate the effectiveness of the technique for selected values of k, n and activity level rho. Author

Subject Categories:

  • Statistics and Probability
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE