Markov Chains with Rare Transitions and Simulated Annealing.

Abstract

This document considers Markov chains in which the entries of the one-step transition probability matrix are known to be of different orders of magnitude and whose structure (that is, the orders of magnitude of the transition probabilities) does not change with time. For such Markov chains the author presents a method for generating order of magnitude estimates for the t-step transition probabilities, for any t. He than notices the algorithms of the simulated annealing type may be represented by a Markov chain which is approximately stationary over fairly long time intervals. Using the results he obtains a characterization of the convergent cooling schedules for the general class of algorithms of the simulated annealing type.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1985
Accession Number
ADA161598

Entities

People

  • John N. Tsitsiklis

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Annealing
  • Artificial Intelligence
  • Classification
  • Coefficients
  • Electrical Engineering
  • Engineering
  • Inequalities
  • Intervals
  • Markov Chains
  • Markov Processes
  • Mathematics
  • Probability
  • Security
  • Sequences
  • Stationary
  • Time Intervals

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Mathematical Modeling and Probability Theory.
  • Thermal Physics or Thermal Science.