Discrete-Time Conversion for Simulating Semi-Markov Processes

B. L. Fox and P. W. Glynn

Operations Research Letters, Vol. 5, 191-196 (1986)

We simulate long-run averages of time integrals of a recurrent semi-Markov process efficiently. Converting to discrete-time by simulating only an imbedded chain and computing the conditional expectations of everything else needed given the sequence of studies visited reduces asymptotic variance, eliminates generating holding-time variates, and (when advantageous) gets rid of the future event schedule. In this setting, uniformizing continuous-time Markov chains is not worthwhile. We generalize beyond semi-Markov processes and cut ties to regenerative simulation methodology. Implementation of discrete-time conversion is discussed. It often requires no more work or even less work than the naive method. We give sufficient conditions for work savings. Continuous-time Markov chains, for example, satisfy them.