Empirical measure large deviations for reinforced chains on finite spaces

DOI10.1016/J.SYSCONLE.2022.105379zbMATH Open1505.93251arXiv2205.09291OpenAlexW4297330031MaRDI QIDQ2107618FDOQ2107618

Authors: Amarjit Budhiraja, Adam Waterbury 

Publication date: 2 December 2022

Published in: Systems \& Control Letters (Search for Journal in Brave)

Abstract: Let $A$ be a transition probability kernel on a finite state space $Delt{a}^o=1,ldots,d$ such that $A(x,y)>0$ for all $x,yinDelt{a}^o$. Consider a reinforced chain given as a sequence $X_n,;ninmathbb{N}_0$ of $Delt{a}^o$-valued random variables, defined recursively according to, ${\displaystyle }$L^n = frac{1}{n}sum_{i=0}^{n-1} delta_{X_i}, ;; P(X_{n+1} in cdot mid X_0, ldots, X_n) = L^n A(cdot).${\displaystyle }$ We establish a large deviation principle for $L^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.

Full work available at URL: https://arxiv.org/abs/2205.09291

Recommendations

• Large deviations for Markov chains with random transitions
• Large deviations for additive functionals of Markov chains
• On the large deviation rate function for the empirical measures of reversible jump Markov processes
• From level 2.5 to level 2 large deviations for continuous time Markov chains
• Occupation measures for chains of infinite order

zbMATH Keywords

stochastic approximationlarge deviation principlereinforced random walkstime-reversalempirical measureinfinite horizon discounted cost

Mathematics Subject Classification ID

Large deviations (60F10) Sums of independent random variables; random walks (60G50) Stochastic systems in control theory (general) (93E03)

Cites Work

• Asymptotic evaluation of certain markov process expectations for large time, I
• Title not available (Why is that?)
• 75.9 Euler’s Constant
• 3295. Approximate evaluation of Euler’s constant
• Large deviation asymptotics for occupancy problems.
• Asymptotic evaluation of certain Markov process expectations for large time—III
• Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
• The Large Deviation Principle for a General Class of Queueing Systems I
• On nonlinear Markov chain Monte Carlo
• The sampling theory of neutral alleles and an urn model in population genetics
• Partition structures, Polya urns, the Ewens sampling formula, and the ages of alleles
• Central limit theorems for stochastic approximation with controlled Markov chain dynamics
• Self-Interacting Markov Chains
• Analysis and Approximation of Rare Events
• Performance of a Distributed Stochastic Approximation Algorithm
• Asymptotic behavior of stochastic approximation and large deviations
• A stochastic approximation approach to quasi-stationary distributions on finite spaces
• On the stability of some controlled Markov chains and its applications to stochastic approximation with Markovian dynamic

Cited In (1)

• Current fluctuations of a self-interacting diffusion on a ring

This page was built for publication: Empirical measure large deviations for reinforced chains on finite spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107618)