Books to Read While the Algae Grow in Your Fur, January 2015

MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} }); Attention conservation notice: I have no taste.

Jin Feng and Thomas G. Kurtz, Large Deviations for Stochastic Processes

\[ \newcommand{\Expect}[1]{\mathbb{E}\left[ #1 \right]} \newcommand{\Prob}[1]{\mathbb{P}\left( #1 \right)} \]

Kurtz is best known for work in the 1970s and 1980s on how sequences of Markov processes converge on a limiting Markov process, especially on how they converge on a limiting deterministic dynamical system. This book is an extension of those ideas, and best appreciated in that context.

As every school-child knows, we ordinarily specify a Markov process by its transition probabilities or transition kernels, say \[ \kappa_t(x,B) = \Pr(X_{t}\in B \mid X_0=x) ~. \] The transition kernels form a semi-group: $\kappa_{t+s}(x,B) = \int{\kappa_t(y,B) \kappa_s(x,dy)}$. For analytical purposes, however, it is more convenient to talk about transition operators, which give us conditional expectations: \[ T_t f(x) = \Expect{f(X_{t})\mid X_0=x} = \int{f(y)\kappa_t(x,dy)} ~. \] (It's less obvious, but if we're given all the transition operators, they fix the kernels.) These, too, form a semi-group: $T_{t+s} f(x) = T_t T_s f(x)$. The generator $A$ of the semi-group $T_t$ is, basically, the time-derivative of the transition operators, the limit \[ A f(x) = \lim_{t\rightarrow 0}{\frac{T_t f(x) - f(x)}{t}} ~. \] so \[ \frac{d}{dt}{T_t f} = A T_t f \] A more precise statement, however, which explains the name "generator", is that \[ T_t f = e^{t A}f = \sum_{m=0}^{\infty}{\frac{(tA)^m f}{m!}} ~. \] Notice that the transition operators and their generator are all linear operators, no matter how nonlinear the state-to-state transitions of the Markov process may be. Also notice that a deterministic dynamical system has a perfectly decent transition operator: writing $g(x,t)$ for the trajectory beginning at $x$ at time $h$, $T_t f(x) = f(g(x,t))$, and \[ A f(x) = {\left.\frac{d T_t f(x)}{dt}\right|}_{t=0} ~. \]

Suppose we have a sequence of Markov processes, $X^{(1)}, X^{(2)}, \ldots$. What Kurtz and others showed is that these converge in distribution to a limiting process $X$ when their semi-groups $T^{(n)}_h$ converges to the limiting semi-group $T_h$. This in turn happens when the generators $A^{(n)}$ converge on the limiting generator $A$. To appreciate why this is natural, remember that a sequence of distributions $P^{(n)}$ converges on a limiting distribution $P$ if and only if $\int{f(x) dP^{(n)}(x)} \rightarrow \int{f(x) dP(x)}$ for all bounded and continuous "test" functions $f$; and $A^{(n)}$ and $A$ generate the semi-groups which give us conditional expectations. (Of course, actually proving a "natural" assertion is what separates real math from mere hopes.) In saying this, naturally, I gloss over lots of qualifications and regularity conditions, but this is the essence of the thing. In particular, such results give conditions under which Markov processes converge on a deterministic dynamical system, such as an ordinary differential equation. Essentially, the limiting generator $A$ should be the differential operator which'd go along with the ODE. These results are laws of large numbers for sequences of Markov processes, showing how they approach a deterministic limit as the fluctuations shrink.

Large deviations theory, as I've said elsewhere, tries to make laws of large numbers quantitative. The laws say that fluctuations around the deterministic limit decay to zero; large deviations theory gives an asymptotic bound on these fluctuations. Roughly speaking, a sequence of random variables or processes $X^{(n)}$ obeys the large deviations principle when \[ n^{-1} \log{\Prob{X^{(n)} \in B}} = -\inf_{x \in B}{I(x)} \] for some well-behaved "rate function" $I$. (Again, I gloss over some subtleties about the distinctions between open and closed sets.) The subject of this book is, depending on your point of view, either strengthening Kurtz's previous work on convergence of Markov processes to large deviations, or extending the large deviations theory of stochastic processes, as the title says.

In dealing with large deviations, it's very common to have to deal with