DISCRETE-TIME INVERSION AND DERIVATIVE ESTIMATION FOR MARKOV-CHAINS

In estimating functions of continuous-time Markov chains via simulation, one may reduce variance and computation by simulating only the embedded discrete-time chain. To estimate derivatives (with respect to transition probabilities) of functions of discrete-time Markov chains, we propose embedding them in continuous-time processes. To eliminate the additional variance and computation thereby introduced, we convert back to discrete time. For a restricted class of chains, we may embed in a continuous-time Markov chain and apply perturbation analysis estimation. Embedding, instead, in a certain non-Markovian process yields an unbiased perturbation analysis estimate for general chains (but may have higher variance). When this last estimate is converted to discrete time, it turns into a likelihood ratio derivative estimate for the original, discrete-time chain, revealing a surprising connection between the two methods. © 1990.