Min-Plus Linearity and Statistical Mechanics

J.P. Quadrat

1997, v.3, Issue 4, 565-587

ABSTRACT

We revisit some results obtained recently in min-plus algebra following the ideas of statistical mechanics. Computation of geodesics in a graph can be done by min-plus matrix products. A min-plus matrix is seen as a kind of finite states mechanical system. The energy of this system is the eigenvalue of its min-plus matrix. The graph interpretation of the eigenvalue may be seen as a kind of Mariotte law. The Cramer transform is introduced by statistics on populations of independent min-plus linear systems seen as a kind of perfect gas. It transforms probability calculus in what we call decision calculus. Then, dynamic programming equations, which are min-plus linear recurrences, may be seen as min-plus Kolmogorov equations for Markov chains. An ergodic theorem for Bellman chains, analogue of Markov chains, is given. The min-plus counterparts of aggregation, coherency, and reversibility of Markov chains are then studied. They provide new decomposition results to compute solutions of dynamic programming equations. Finally, some links between Wentzell-Freidlin asymptotics and min-plus algebra are described.

Keywords: min-plus algebra,statistical mechanics,decision theory,large deviations,aggregation,reversibility

COMMENTS

Please log in or register to leave a comment