Large Deviations for Empirical Measures of Self-Interacting Markov Chains
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913939269353472 |
|---|---|
| author | Budhiraja, Amarjit Waterbury, Adam Zoubouloglou, Pavlos |
| author_facet | Budhiraja, Amarjit Waterbury, Adam Zoubouloglou, Pavlos |
| contents | 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 $x_0 \in Δ^o$ and consider the chain $\{X_n, \; n \in \mathbb{N}_0\}$ of $Δ^o$-valued random variables such that $X_0=x$, and given $X_0, \ldots , X_n$, the conditional distribution of $X_{n+1}$ is $G(L^{n+1})(X_n, \cdot)$, where $L^{n+1} = \frac{1}{n+1} \sum_{i=0}^{n} δ_{X_i}$ is the empirical measure at instant $n$. Under conditions on $G$ we establish a large deviation principle for the empirical measure sequence $\{L^n, \; n \in \mathbb{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_01384 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Large Deviations for Empirical Measures of Self-Interacting Markov Chains Budhiraja, Amarjit Waterbury, Adam Zoubouloglou, Pavlos Probability Optimization and Control 60F10 (Primary) 93E03 (Secondary) 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 $x_0 \in Δ^o$ and consider the chain $\{X_n, \; n \in \mathbb{N}_0\}$ of $Δ^o$-valued random variables such that $X_0=x$, and given $X_0, \ldots , X_n$, the conditional distribution of $X_{n+1}$ is $G(L^{n+1})(X_n, \cdot)$, where $L^{n+1} = \frac{1}{n+1} \sum_{i=0}^{n} δ_{X_i}$ is the empirical measure at instant $n$. Under conditions on $G$ we establish a large deviation principle for the empirical measure sequence $\{L^n, \; n \in \mathbb{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. |
| title | Large Deviations for Empirical Measures of Self-Interacting Markov Chains |
| topic | Probability Optimization and Control 60F10 (Primary) 93E03 (Secondary) |
| url | https://arxiv.org/abs/2304.01384 |