# 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

# Descriptors:

# Subject Categories:

- Statistics and Probability
- Computer Programming and Software