×

zbMATH — the first resource for mathematics

Nonstationary Markov chains and convergence of the annealing algorithm. (English) Zbl 0642.60049
We study the asymptotic behavior as time \(t\to +\infty\) of certain nonstationary Markov chains, and prove the convergence of the annealing algorithm in Monte Carlo simulations. We find that in the limit \(t\to +\infty\), a nonstationary Markov chain may exhibit “phase transitions”. Nonstationary Markov chains in general, and the annealing algorithm in particular, lead to biased estimators for the expectation values of the process.
We compute the leading terms in the bias and the variance of the sample- means estimator. We find that the annealing algorithm converges, if the temperature T(t) goes to zero no faster than \(C/\log (t/t_ 0)\) as \(t\to +\infty\), with a computable constant C and \(t_ 0\) the initial time. The bias and the variance of the sample-means estimator in the annealing algorithm go to zero like \(O(t^{-1+\epsilon})\) for some \(0\leq \epsilon <1\), with \(\epsilon =0\) only in very special circumstances.
Our results concerning the convergence of the annealing algorithm, and the rate of convergence to zero of the bias and the variance of the sample-means estimator, provide a rigorous procedure for choosing the optis, from those presented at the Congress mentioned in the title. The volume is divided into five sections.
Section I is on complex system modelling, simulation and identification (7 papers). Environmental system, production engineering, turboset control systems and mechanical vibration test benches are considered.
Section II is on bond graph analysis and modelling (15 papers). Bond graph theory is applied to rigid body systems, a fluid filled pipe, unsteady state heat conduction, an adaptive vehicle air suspension, a feel force system, a dynamic robotic model and manipulator control systems. Section III is on nonlinear oscillators and chaotic systems (6 papers).
Section IV is on distributed parameter systems (13 papers). Stability analysis, identification by Walsh functions, parameter and state identification, adaptive state estimation and computational methods for an optimal control problem are discussed. A literature overview of the last two decades is given.
Section V is on control of complex systems (8 papers).
This volume represents five major areas of system theory, and shows the modern trend in the growing field of complex and distributed parameter system theory.
Reviewer: T.Kobayashi

MSC:
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
82B05 Classical equilibrium statistical mechanics (general)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K. Binder and D. Stauffer, Monte-Carlo studies of random systems: Spin glasses, percolation, etc., preprint.
[2] E. Coddington and N. Levinson,Theory of Ordinary Differential Equations (McGrawHill, New York, 1955). · Zbl 0064.33002
[3] H. Cohn, On a paper by Doeblin on non-homogeneous Markov chains,Adv. Appl. Prob. 13:388-401 (1981). · Zbl 0469.60065 · doi:10.2307/1426690
[4] M. Creutz, L. Jacobs, and C. Rebbi, Experiments with a gauge-invariant Ising model,Phys. Rev. Lett. 42:1390-1393 (1979). · doi:10.1103/PhysRevLett.42.1390
[5] M. Creutz, L. Jacobs, and C. Rebbi, Monte Carlo study of Abelian lattice gauge theories,Phys. Rev. D 20:1915-1922 (1979). · doi:10.1103/PhysRevD.20.1915
[6] R. L. Dobrushin, Central limit theorem for non-stationary Markov chains, I, II,Theo. Prob. Appl. 1:65-80 (1956);Theor. Prob. Appl. 1:329-383 (1956). · Zbl 0093.15001 · doi:10.1137/1101006
[7] W. Feller,An Introduction to Probability Theory and Its Applications, Vol. I (John Wiley and Sons, New York, 1968). · Zbl 0155.23101
[8] S. Geman and D. Geman, Stochastic relaxation, Gibbs distributions, and Bayesian restoration of images,IEEE transactions PAMI (1984). · Zbl 0573.62030
[9] D. Griffeath, Uniform coupling of non-homogeneous Markov chains,J. Appl. Prob. 12:753-762 (1975). · Zbl 0322.60061 · doi:10.2307/3212726
[10] W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications,Biometrika 57:97-109 (1970). · Zbl 0219.65008 · doi:10.1093/biomet/57.1.97
[11] D. L. Isaacson and R. W. Madsen,Markov Chains Theory and Applications (John Wiley and Sons, New York, 1976). · Zbl 0332.60043
[12] S. Karlin and H. M. Taylor,A First Course in Stochastic Processes, Vols. I and II (Academic Press, New York, 1975). · Zbl 0315.60016
[13] J. Kemeny and J. L. Snell,Finite Markov Chains (Van Nostrand, New York, 1960). · Zbl 0089.13704
[14] R. Kindermann and J. L. Snell,Markov Random Fields and Their Applications, Contemporary Mathematics, Vol. 1 (American Mathematical Society, Providence, Rhode Island, 1980). · Zbl 1229.60003
[15] S. Kirkpatric and D. Sherrington, Infinite-ranged models of spin-glasses,Phys. Rev. B 17:4384-4403 (1978). · doi:10.1103/PhysRevB.17.4384
[16] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing,Science 220:621-680 (13 May 1983). · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[17] N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, Equations of state calculations by fast computing machines,J. Chem. Phys. 21:1087-1091 (1953). · doi:10.1063/1.1699114
[18] K. Binder, ed.Monte Carlo Methods in Statistical Physics (Springer, New York, 1979).
[19] E. Seneta,Non-Negative Matrices and Markov Chains (Springer, New York, 1981). · Zbl 0471.60001
[20] G. Toulouse, Frustrations et desordres: problemes nouveaux en mecanique statistique. Histoire des verres de spin,Proceedings of the 1981 Conference of French Physical Society (Editions de Physique, Paris, 1982).
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.