2023/04/03 by Budhiraja, Amarjit, Waterbury, Adam, Zoubouloglou, Pavlos · 1 citation
#60F10 (Primary) 93E03 (Secondary) #FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR)
paper · doi:10.48550/arxiv.2304.01384
Let Δo be a finite set and, for each probability measure m on Δo, let G(m) be a transition probability kernel on Δo. Fix x0 ∈ Δo and consider the chain \Xn, n ∈ ℕ0\ of Δo-valued random variables such that X0=x, and given X0, … , Xn, the conditional distribution of Xn+1 is G(Ln+1)(Xn, ⋅), where Ln+1 = (1)/(n+1) ∑i=0n δXi is the empirical measure at instant n. Under conditions on G we establish a large deviation principle for the empirical measure sequence \Ln, n ∈ ℕ\. As one application of this result we obtain large deviation asymptotics for the Aldous-Flannery-Palacios (1988) approximation scheme for quasistationary distributions of irreducible finite state Markov chains. The conditions on G cover various other models of reinforced stochastic evolutions as well, including certain vertex reinforced and edge reinforced random walks and a variant of the PageRank algorithm. The particular case where G(m) does not depend on m corresponds to the classical results of Donsker and Varadhan (1975) on large deviations of empirical measures of Markov processes. However, unlike this classical setting, for the general self-interacting models considered here, the rate function takes a very different form; it is typically non-convex and is given through a dynamical variational formula with an infinite horizon discounted objective function.