RATE OF CONVERGENCE FOR DERIVATIVE ESTIMATION OF DISCRETE-TIME MARKOV-CHAINS VIA FINITE-DIFFERENCE APPROXIMATION WITH COMMON RANDOM NUMBERS

The scheme of common random numbers (CRN) is a very popular method for variance reduction in simulation. Finite difference (FD) is a convent ional technique for derivative estimation. In this paper, we examine t he effectiveness of CRN for improving the rates of convergence for FD estimates over infinite horizon for homogeneous discrete-time Markov c hains. For direct FD estimates, we give sufficient conditions for the effectiveness of CRN. Based on these conditions, we also suggest sever al simulation schemes with guaranteed effectiveness. For ratio estimat es based on regenerative structures, we prove that the use of CRN is a lways advantageous.