Article ID: | iaor20124092 |
Volume: | 24 |
Issue: | 2 |
Start Page Number: | 295 |
End Page Number: | 310 |
Publication Date: | Mar 2012 |
Journal: | INFORMS Journal on Computing |
Authors: | Ghosh Soumyadip, Pasupathy Raghu |
Keywords: | heuristics |
We propose C‐NORTA, an exact algorithm to generate random variates from the tail of a bivariate NORTA random vector. (A NORTA random vector is specified by a pair of marginals and a rank or product–moment correlation, and it is sampled using the popular NORmal‐To‐Anything procedure.) We first demonstrate that a rejection‐based adaptation of NORTA on such constrained random vector generation problems may often be fundamentally intractable. We then develop the C‐NORTA algorithm, relying on strategic conditioning of the NORTA vector, followed by efficient approximation and acceptance/rejection steps. We show that, in a certain precise asymptotic sense, the sampling efficiency of C‐NORTA is exponentially larger than what is achievable through a naïve application of NORTA. Furthermore, for at least a certain class of problems, we show that the acceptance probability within C‐NORTA decays only linearly with respect to a defined rarity parameter. The corresponding decay rate achievable through a naïve adaptation of NORTA is exponential. We provide directives for efficient implementation.