Maximal coupling rare perturbation analysis with a random horizon (Q1902497)

The paper presents extensions of the maximal coupling rare perturbation analysis (RPA), introduced by, among others, the first author of the current paper. The essence of the extension is the treatment of the random horizon case. The introduction gives a brief overview of perturbation analysis (PA) techniques (infinitesimal PA, smoothed PA, linear ratio method and the recently developed rare PA). One considers cost functions of the form \(J (\theta) = E_\theta \Psi_\theta\), with respect to the parameter \(\theta\) and one is interested in its sensitivity w.r.t. \(\theta\), i.e. \({d(J (\theta)) \over d \theta}\). The basic idea of RPA is to consider a class of families \(\{\Psi_\theta\}\) such that a small perturbation in \(\theta\) leads, with high probability, to no perturbation in \(\Psi_\theta\), but when such a perturbation does occur, it is no longer infinitesimal. Two possible applications are sketched briefly: one in queueing theory and one as a routing problem. The introduction ends with a relationship with the so-called weak derivability concept. In section 2 the idea of maximum coupling of two random variables is presented, as well as two schemes for the generation of such variables. These schemes are subsequently used in section 3 to obtain RPA gradient estimates. Section 3 is divided into two subsections: first the deterministic horizon case is treated and subsequently the stochastic horizon one. In section 4 some existing results for generalized semi Markov processes (GSMP) are extended also to the random case.