Simulating a Markov Chain with a Superefficient Sampling Method.

This paper describes an algorithm and a FORTRAN subprogram, CHAIN, for simulating the behavior of an (n+1) state Markov chain using a variance reducing technique called rotation sampling. The simulation of k microreplications is carried out in parallel at a mean cost or = O(1n k) and with variances of sample quantities of interest or = O((1n k squared)/k squared). The program allows for independent macroreplications, each of k microreplications, in order to faciliate estimation of the variances of sample quantities of interest. The paper describes theoretical results that underlie the algorithm and program in Section 1 and presents applications of interest for first passage time and steady-state distributions in Section 2. Section 3 describes the algorithm and CHAIN and an example in Section 4 illustrates how CHAIN works in practice. Section 5 describes the options available for restarting the simulation. (Author)