Empirical measure large deviations for reinforced chains on finite spaces

Let A be a transition probability kernel on a finite state space increment o = {1, ... , d} such that A(x, y) > 0 for all x, y is an element of increment o. Consider a reinforced chain given as a sequence {Xn, n is an element of N0} of increment o-valued random variables, defined recursively according to,1 Ln = n n- n-ary sumation i=0 1 delta Xi, P(Xn is an element of middot | X0, ... ,Xn-1)= LnA(middot).We establish a large deviation principle for {Ln, n is an element of N}. The rate function takes a strikingly different form than the Donsker-Varadhan rate function associated with the empirical measure of the Markov chain with transition kernel A and is described in terms of a novel deterministic infinite horizon discounted cost control problem with an associated linear controlled dynamics and a nonlinear running cost involving the relative entropy function. Proofs are based on an analysis of time-reversal of controlled dynamics in representations for log-transforms of exponential moments, and on weak convergence methods.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article investigates a reinforced chain and establishes a large deviation principle for it. The rate function, which is different from the traditional Donsker-Varadhan rate function associated with the empirical measure of the Markov chain, is described in terms of a novel discounted cost control problem involving the relative entropy function.