DISCRETE-TIME INVERSION AND DERIVATIVE ESTIMATION FOR MARKOV-CHAINS

被引:1
作者
GLASSERMAN, P
机构
[1] AT and T Bell Laboratories, Holmdel
关键词
gradient estimation; likelihood ratios; Markov chains; perturbation analysis; simulation;
D O I
10.1016/0167-6377(90)90024-Y
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:305 / 313
页数:9
相关论文
共 6 条
[1]  
FOX B, 1990, IN PRESS SIAM J APPL
[2]   DISCRETE-TIME CONVERSION FOR SIMULATING SEMI-MARKOV PROCESSES [J].
FOX, BL ;
GLYNN, PW .
OPERATIONS RESEARCH LETTERS, 1986, 5 (04) :191-196
[3]  
GLASSERMAN P, 1989, UNPUB OPER RES
[4]   DISCRETE-TIME METHODS FOR SIMULATING CONTINUOUS TIME MARKOV-CHAINS [J].
HORDIJK, A ;
IGLEHART, DL ;
SCHASSBERGER, R .
ADVANCES IN APPLIED PROBABILITY, 1976, 8 (04) :772-788
[5]  
Pollard D., 1984, CONVERGENCE STOCHAST
[6]  
[No title captured]