×

zbMATH — the first resource for mathematics

On discrete inhomogeneous exit problems. (Sur les problèmes de sortie discrets inhomogènes.) (French) Zbl 0870.60062
Summary: Let \((X^{(t)})_{t\geq 0}\) be a family of inhomogeneous Markov processes on a finite set \(M\), whose jump intensities at the time \(s\geq0\) are given by \(\exp(-\beta^{(t)}_sV(x,y))q(x,y)\) for all \(x\neq y\in M\), where the evolutions of the inverse of the temperature \(\mathbb{R}_+\ni s\mapsto\beta^{(t)}_s\in\mathbb{R}_+\) take in some ways greater and greater values with \(t\). We study by using semigroup techniques the asymptotic behavior of the couple consisting of the renormalized exit time and exit position from sets which are a little more general than the cycles associated with the cost function \(V\). We obtain a general criterion for weak convergence, for which we describe explicitly the limit law. Then we are interested in the particular case of evolution families satisfying \(\forall t,s\geq 0\), \(\beta^{(t)}_s= \beta^{(0)}_{t+s}\), for which we show there are only three kinds of limit laws for the renormalized exit time (this is relevant for the limit theorems satisfied by renormalized occupation times of generalized simulated annealing algorithms, but this point will not be developed here).

MSC:
60J05 Discrete-time Markov processes on general state spaces
60F10 Large deviations
60J35 Transition functions, generators and resolvents
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bakry, D. (1994). L’hy percontractivité et son utilisation en théorie des semigroupes. Lectures on Probability Theory. Ecole d’Eté de Probabilités de Saint-Flour XXII-1992. Lecture Notes in Math. 1581. Springer, Berlin. · Zbl 0856.47026
[2] Catoni, O. (1991). Applications of sharp large deviations estimates to optimal cooling schedules. Ann. Inst. H. Poincaré Probab. Statist. 27 463-518. · Zbl 0752.60025 · numdam:AIHPB_1991__27_4_463_0 · eudml:77414
[3] Chiang, T. S. et Chow, Y. (1988). On the convergence rate of annealing processes. SIAM J. Control Optim. 26 1455-1470. · Zbl 0665.60090 · doi:10.1137/0326084
[4] Concordet, D. (1994). Estimation de la densité du recuit simulé. Ann. Inst. H. Poincaré Probab. Statist. 30 265-302. · Zbl 0802.60092 · numdam:AIHPB_1994__30_2_265_0 · eudml:77483
[5] Dellacherie, C. et Meyer, P. A. (1980). Probabilités et potentiel; théorie des martingales. Hermann, Paris. · Zbl 0464.60001
[6] Freidlin, M. I. et Wentzell, A. D. (1984). Random Perturbations of Dy namical Sy stems. Springer, New York. · Zbl 0522.60055
[7] Gantert, N. (1990). Laws of large numbers for the annealing algorithm. Stochastic Process. Appl. 3 309-313. · Zbl 0715.60089 · doi:10.1016/0304-4149(90)90009-H
[8] Geman, S. et Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restauration of images. IEEE Trans. Pattern Analy sis and Machine Intelligence 6 721- 741. · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[9] Gidas, B. (1985). Nonstationary Markov chains and convergence of the annealing algorithm. J. Statist. Phy s. 39 73-131. · Zbl 0642.60049 · doi:10.1007/BF01007975
[10] G ötze, F. (1991). Rate of convergence of simulated annealing processes. Préprint.
[11] Hajek, B. (1988). Cooling schedules for optimal annealing. Math. Oper. Res. 13 311-329. JSTOR: · Zbl 0652.65050 · doi:10.1287/moor.13.2.311 · links.jstor.org
[12] Holley, R. et Stroock, D. (1988). Annealing via Sobolev inequalities. Comm. Math. Phy s. 115 553-569. · Zbl 0643.60092 · doi:10.1007/BF01224127
[13] Hwang, C. R. et Sheu, S. J. (1992). Singular perturbed Markov chains and exact behaviors of simulated annealing processes. J. Theoret. Probab. 5 223-249. · Zbl 0755.60047 · doi:10.1007/BF01046734
[14] Kirkpatrick, S., Gelatt, C. D. et Vecchi, M. P (1983). Optimization by simulated annealing. Science 220 621-680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[15] Mathieu, P. (1995). Spectra, exit times and long time asy mptotics in the zero-white-noise limit. Préprint. · Zbl 0886.60055
[16] Miclo, L. (1992). Recuit simulé sans potentiel sur un ensemble fini. Séminaire de Probabilités XXVI. Lecture Notes in Math. 1526 47-60. Springer, Berlin. · Zbl 0770.60090 · numdam:SPS_1992__26__47_0 · eudml:113815
[17] Miclo, L. (1995). Remarques sur l’ergodicité des algorithmes de recuit simulé sur un graphe. Stochastic Process. Appl. 58 329-360. · Zbl 0829.60024 · doi:10.1016/0304-4149(95)00022-Y
[18] Miclo, L. (1995). Probl eme de sortie discret et théor emes limites pour les temps d’occupations du recuit simulé. Prépublication 08-96, Laboratoire de Statistique et Probabilités, Univ. Toulouse III.
[19] Miclo, L. (1995). Sur les temps d’occupations des processus de Markov finis inhomog enes a basse température. Préprint. · Zbl 1002.60565
[20] Miclo, L. (1996). Remarques sur l’hy percontractivité et l’évolution de l’entropie pour des cha ines de Markov finies. Seminaire de Probabilités XXXI. Lecture Notes in Math. Springer, Berlin. A para itre.
[21] Rockafellar, R. T (1970). Convex Analy sis. Princeton Univ. Press. · Zbl 0193.18401
[22] Stroock, D. W (1993). Logarithmic Sobolev inequalities for Gibbs states. Dirichlet Forms. Lecture Notes in Math. 1563 194-228. Springer, Berlin. · Zbl 0801.60056 · doi:10.1007/BFb0074094
[23] Trouvé, A. (1993). Parallélisation massive du recuit simulé. Th ese de doctorat, Univ. Paris 11.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.