Large deviation principles for Euclidean functionals and other nearly additive processes (Q5945632)

Large deviations in this paper are of Donsker-Varadhan style. One says that a real-valued process \(X=\{X(n)\}\) satisfies a large deviation principle (LDP) with rate function \(I\) and normalization \(n\) if the following inequalities (with \(Q_n(A)=\log P(n^{-1}X(n)\in A)\)) \[ \limsup_{n\to \infty} Q_n(F)\leq -\inf_{x\in F}I(x), \quad \liminf_{n\to \infty} Q_n(O)\leq -\inf_{x\in O}I(x), \] hold for all closed sets \(F\subseteq R\) and open sets \(O\subseteq R.\) The authors prove here a LDP for processes indexed by the so-called multidimensional cubes, under approximate additivity and regularity hypotheses, when the rate function is convex dual of the limiting logarithmic moment generating function. The general result applies to processes in Euclidean combinatorial optimization, statistical mechanics, and computational geometry. That's why the paper contains numerous examples: the length of the minimal tour (also known as the travelling salesman problem), the length of the minimal matching graph, the length of the minimal spanning tree (all on a random set), etc.