Empirical measure large deviations for reinforced chains on finite spaces

DOI10.1016/J.SYSCONLE.2022.105379MaRDI QIDQ2107618zbMATH OpenOpenAlexFDO

Authors Amarjit Budhiraja, Adam Waterbury

Publication date 2 December 2022

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

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

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)

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.

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

Cites work

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

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)