Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T18:34:53.539Z Has data issue: false hasContentIssue false
  • English
  • Français

Tail events of simulated annealing Markov chains

Part of: Markov processes

Published online by Cambridge University Press:  14 July 2016

Wojciech Niemiro
Wojciech Niemiro*
Affiliation:
University of Warsaw
*
∗Postal address: Institute of Applied Mathematics and Mechanics, University of Warsaw, Poland.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider non-homogeneous Markov chains generated by the simulated annealing algorithm. We classify states according to asymptotic properties of trajectories. We identify recurrent and transient states. The set of recurrent states is partitioned into disjoint classes of asymptotically communicating states. These classes correspond to atoms of the tail sigma-field. The results are valid under the weak reversibility assumption of Hajek.

Keywords

NON-HOMOGENEOUS MARKOV CHAINRECURRENCETRANSIENCETAIL SIGMA-FIELD

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces)
Secondary: 90C15: Stochastic programming
Type
Research Papers
Information
Journal of Applied Probability , Volume 32 , Issue 4 , December 1995 , pp. 867 - 876
Copyright
Copyright © Applied Probability Trust 1995 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported by KBN grant no. 21168/91/01.

References

Borkar, V. S. (1992) Pathwise recurrence orders and simulated annealing. J. Appl. Prob. 29, 472–476.Google Scholar
Cohn, H. (1976) Finite non-homogeneous Markov chains: asymptotic behaviour. Adv. Appl. Prob. 8, 502–516.CrossRefGoogle Scholar
Cohn, H. (1982) On a class of non-homogeneous Markov chains. Math. Proc. Camb. Phil. Soc. 92, 527–534.Google Scholar
Connors, D. P. and Kumar, P. R. (1989) Simulated annealing type Markov chains and their balance equations. SIAM J. Control Optim. 27, 1440–1461.CrossRefGoogle Scholar
Durrett, R. (1991) Probability. Theory and Examples. Wadsworth & Brooks/Cole, Pacific Grove.Google Scholar
Hajek, B. (1988) Cooling schedules for optimal annealing. Math. Operat. Res. 13, 311–329.Google Scholar
Iosifescu, M. (1979) The tail structure of nonhomogeneous finite Markov chains: a survey. In Probability Theory, pp. 125–132, Banach Center Publications 5, PWN, Warsaw.Google Scholar
Van Laarhoven, P. J. M. and Aarts, E. H. L. (1987) Simulated Annealing. Theory and Applications. Riedel, Dordrecht.CrossRefGoogle Scholar
Mukherjea, A. (1984) Non-homogeneous Markov chains: tail idempotents, tail sigma-fields and basis. In Proc. 7th Conf. Probability Theory, (Brasov, 1982), ed. Iosifescu, M. et al. pp. 269–282, Publishing House of the Romanian Academy, Bucharest.Google Scholar
Niemiro, W. and Pokarowski, P. (1995) Tail events of some non-homogeneous Markov chains. Ann. Appl. Prob. 5, 1.Google Scholar
Romeo, F. and Sangiovanni-Vincentelli, A. (1991) A theoretical framework for simulated annealing. Algorithmica 6, 302–345.Google Scholar
Tsitsiklis, J. (1989) Markov chains with rare transitions and simulated annealing. Math. Operat. Res. 14, 70–90.Google Scholar