Importance sampling techniques for the multidimensional ruin problem for general Markov additive sequences of random vectors. (English) Zbl 1021.65003

Collamore, J. F.

Ann. Appl. Probab. 12, No. 1, 382-421 (2002).

Let \(\{S_n\}\) be a sequence of \(\mathbb{R}^n\)-valued random variables and let \(A\subset\mathbb{R}^n\) be open. Consider the hitting probability of a region \(A/\varepsilon: \{x/\varepsilon: x\in A\}\), by \(\{S_n\}\) as \(\varepsilon\to 0\). It is assumed that the mean drift of \(\{S_n\}\) is directed away from \(A\) so that this probability tends to zero as \(\varepsilon\to 0\). The aim of this paper is to use importance sampling for simulating it. For any fixed \(\varepsilon\), an efficient estimate is obtained which has certain optimality properties as \(\varepsilon\to 0\).

Reviewer: Radu Theodorescu (Quebec)

MSC:

65C05	Monte Carlo methods
60J05	Discrete-time Markov processes on general state spaces
62D05	Sampling theory, sample surveys
62M05	Markov processes: estimation; hidden Markov models
60F10	Large deviations

Keywords:

multidimensional ruin problem; Monte Carlo methods; rare event simulation; hitting probabilities; large deviations; importance sampling

References:

[1]	ASMUSSEN, S. (1989). Risk theory in a Markovian environment. Scand. Actuar. J. 69-100. · Zbl 0684.62073 · doi:10.1080/03461238.1989.10413858
[2]	ASMUSSEN, S. (1999). Stochastic simulation with a view towards stochastic processes. Univ. Aarhus. · Zbl 0981.65013
[3]	ASMUSSEN, S. and RUBINSTEIN, R. Y. (1995). Steady-state rare events simulation in queueing models and its complexity properties. In Advances in Queueing: Models, Methods and Problems (J. Dshalalow, ed.) 429-461. CRC Press, Boca Raton, FL. · Zbl 0848.60085
[4]	ATHREYA, K. B. and NEY, P. (1978). A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245 493-501. · Zbl 0397.60053 · doi:10.2307/1998882
[5]	BOROVKOV, A. A. (1997). Limit theorems for time and place of the first boundary passage by a multidimensional random walk. Doklady 55 254-256. · Zbl 0974.60034
[6]	BOROVKOV, A. A. and MOGULSKII, A. A. (1996). Large deviations for stationary Markov chains in a quarter plane. In Probability Theory and Mathematical Statistics. World Scientific, River Edge, NJ. · Zbl 0970.60029
[7]	BROCKWELL, P. J. and DAVIS, R. A. (1991). Time Series: Theory and Methods, 2nd ed. Springer, New York. · Zbl 0709.62080
[8]	BUCKLEW, J. (1998). The blind simulation problem and regenerative processes. IEEE Trans. Inform. Theory 44 2877-2891. · Zbl 0931.65004 · doi:10.1109/18.737519
[9]	BUCKLEW, J. A., NEY, P. and SADOWSKY, J. S. (1990). Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Probab. 27 44-59. JSTOR: · Zbl 0702.60028 · doi:10.2307/3214594
[10]	CHEN, J.-C., LU, D., SADOWSKY, J. S. and YAO, K. (1993). On importance sampling in digital communications. I. Fundamentals. II. Trellis-coded modulation. IEEE J. Selected Areas Comm. 11 289-308.
[11]	COLLAMORE, J. F. (1996a). Hitting probabilities and large deviations. Ann. Probab. 24 2065-2078. · Zbl 0879.60021 · doi:10.1214/aop/1041903218
[12]	COLLAMORE, J. F. (1996b). Large deviation techniques for the study of the hitting probabilities of rare sets. Ph.D. dissertation, Univ. Wisconsin-Madison.
[13]	COLLAMORE, J. F. (1998). First passage times of general sequences of random vectors: a large deviations approach. Stochastic Process. Appl. 78 97-130. · Zbl 0934.60025 · doi:10.1016/S0304-4149(98)00056-8
[14]	COTTRELL, M., FORT, J.-C. and MALGOUYRES, G. (1983). Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Automat. Control 28 907-920. · Zbl 0531.93064 · doi:10.1109/TAC.1983.1103345
[15]	CRAMÉR, H. (1930). On the mathematical theory of risk. In Scandinavian Jubilee Volume. Stockholm. · JFM 56.1100.03
[16]	DE ACOSTA, A. (1988). Large deviations for vector-valued functionals of a Markov chain: lower bounds. Ann. Probab. 16 925-960. · Zbl 0657.60037 · doi:10.1214/aop/1176991670
[17]	DE ACOSTA, A. and NEY, P. (1998). Large deviation lower bounds for arbitrary additive functionals of a Markov chain. Ann. Probab. 26 1660-1682. · Zbl 0936.60022 · doi:10.1214/aop/1022855877
[18]	DEMBO, A. and ZEITOUNI, O. (1998). Large Deviations Techniques and Applications, 2nd ed. Springer, New York. · Zbl 0896.60013
[19]	DONSKER, M. D. and VARADHAN, S. R. S. (1975, 1976, 1983). Asymptotic evaluation of certain Markov process expectations for large time, I, II, III, IV. Comm. Pure Appl. Math. 28 1-47; 28 279-301; 29 389-461; 36 183-212. · Zbl 0512.60068 · doi:10.1002/cpa.3160360204
[20]	FREIDLIN, M. I. and WENTZELL, A. D. (1984). Random Perturbations of Dynamical Systems. Springer, New York. · Zbl 0522.60055
[21]	GLASSERMAN, P. and KOU, S. (1995). Analysis of an importance sampling estimator for tandem queues. ACM Trans. Modeling Comp. Simul. 4 22-42. · Zbl 0841.62083 · doi:10.1145/203091.203093
[22]	GLASSERMAN, P. and WANG, Y. (1997). Counterexamples in importance sampling for large deviations probabilities. Ann. Appl. Probab. 7 731-746. · Zbl 0892.60043 · doi:10.1214/aoap/1034801251
[23]	HAMMERSLEY, J. M. and HANDSCOMB, D. C. (1964). Monte Carlo Methods. Chapman and Hall, London. · Zbl 0121.35503
[24]	ISCOE, I., NEY, P. and NUMMELIN, E. (1985). Large deviations of uniformly recurrent Markov additive processes. Adv. in Appl. Math. 6 373-412. · Zbl 0602.60034 · doi:10.1016/0196-8858(85)90017-X
[25]	LEHTONEN, T. and NYRHINEN, H. (1992a). On asymptotically efficient simulation of ruin probabilities in a Markovian environment. Scand. Actuar. J. 60-75. · Zbl 0755.62080 · doi:10.1080/03461238.1992.10413897
[26]	LEHTONEN, T. and NYRHINEN, H. (1992b). Simulating level-crossing probabilities by importance sampling. Adv. Appl. Probab. 24 858-874. JSTOR: · Zbl 0779.65003 · doi:10.2307/1427716
[27]	LUNDBERG, F. (1909). Zur Theorie der Rückversicherung. In Verhandl. Kongr. Versicherungsmath. Wien.
[28]	MEYN, S. P. and TWEEDIE, R. L. (1993). Markov Chains and Stochastic Stability. Springer, London. · Zbl 0925.60001
[29]	NEY, P. (1983). Dominating points and the asymptotics of large deviations for random walk on Rd. Ann. Probab. 11 158-167. · Zbl 0503.60035 · doi:10.1214/aop/1176993665
[30]	NEY, P. and NUMMELIN, E. (1984). Some limit theorems for Markov additive processes. In Proceedings of the Symposium on Semi-Markov Processes, Brussels. · Zbl 0625.60027
[31]	NEY, P. and NUMMELIN, E. (1987a). Markov additive processes. I. Eigenvalue properties and limit theorems. Ann. Probab. 15 561-592. · Zbl 0625.60027 · doi:10.1214/aop/1176992159
[32]	NEY, P. and NUMMELIN, E. (1987b). Markov additive processes. II. Large deviations. Ann. Probab. 15 593-609. · Zbl 0625.60028 · doi:10.1214/aop/1176992160
[33]	NUMMELIN, E. (1978). A splitting technique for Harris recurrent Markov chains. Z. Wahrsch. Verw. Gebiete 43 309-318. · Zbl 0364.60104 · doi:10.1007/BF00534764
[34]	NUMMELIN, E. (1984). General Irreducible Markov Chains and Non-negative Operators. Cambridge Univ. Press. · Zbl 0551.60066
[35]	REVUZ, D. (1975). Markov Chains. North-Holland, Amsterdam. · Zbl 0332.60045
[36]	ROCKAFELLAR, R. T. (1970). Convex Analysis. Princeton Univ. Press. · Zbl 0193.18401
[37]	SADOWSKY, J. S. (1993). On the optimality and stability of exponential twisting in Monte Carlo estimation. IEEE Trans. Inform. Theory 39 119-128. · Zbl 0766.62018 · doi:10.1109/18.179349
[38]	SADOWSKY, J. S. (1996). On Monte Carlo estimation of large deviations probabilities. Ann. Appl. Probab. 6 399-422. · Zbl 0855.60031 · doi:10.1214/aoap/1034968137
[39]	SIEGMUND, D. (1976). Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4 673-684. · Zbl 0353.62044 · doi:10.1214/aos/1176343541
[40]	ETH ZENTRUM, HG F 42.2 CH-8092 ZÜRICH SWITZERLAND E-MAIL: [e-mail]