Concentration Inequalities for Markov Jump Processes

Georg-August-Universität Göttingen

Bachelor Thesis

A thesis submitted in partial fulfillment of the requirements for the degree of

Bachelor of Science in Mathematics

Prof. Dr. Anja Sturm

Second Assessor:

Dr. Aljaz Godec

Date of submission:

Santiago Carrero Ibanez

§ INTRODUCTION

What are  'concentration inequalities'? In general, concentration inequalities refer to inequalities that provide bounds on the probability that a random variable deviates from some characteristic value, e.g. the mean value. For example, one may consider a random variable $Z$ and may look at probabilities such as (see e.g. <cit.>)

\begin{equation}
\F{P}(Z \geq u), \; \F{P}(Z \leq u),  \F{P}(\abs{Z} \geq u).
\end{equation}

Concentration inequalities  are of the form

\begin{equation}
P(u) \leq B(u),
\end{equation}

where $B(u) $ is some bound and $P(u)$ is one of the aforementioned probabilities. In other words, concentration inequalities provide bounds on how much the (probability) distribution of a random variable is 'concentrated' around some characteristic value. The Markov  and Chebychev inequalities are simple, well known examples of concentration inequalities.
There are many areas of applications of concentration inequalities including statistical mechanics, statistics, information theory, and high-dimensional geometry <cit.>.
Several methods have been developed to prove such inequalities, e.g. martingale methods, information theoretic methods, 'the entropy method', the transportation method, etc. For an extensive, general presentation of different methods and concentration inequalities see <cit.>.

What are 'concentration inequalities for Markov jump processes'? In this work we consider concentration inequalities for functionals of a special class of Markov processes, namely Markov jump processes (MJP) on finite sets. More precisely, our main goal is to derive bounds for the probability

\begin{equation}
\label{eq: first_probability}
\mathbb{P}_\nu \left (\frac{1}{t}\int_{0}^{t}f(X_s)ds - \pi(f)  \geq u \right ),
\end{equation}

where $u \geq 0$ and $\pi(f) = \int f d\pi $, $\F{X} = (X_t)_{t \geq 0}$ is an irreducible Markov jump process on a finite state space $E$, with invariant distribution $\pi$, $\nu $ denotes the initial distribution, and $f : E \rightarrow \F{R} $ is some function  of interest (see Section 2 for the definition of these notions). The inquiry of the above probability is very natural, as by the well known ergodic theorem

\begin{equation}
\frac{1}{t}\int_{0}^{t}f(X_s)ds \xrightarrow[]{t \to \infty} \pi(f) \quad \F{P}_\nu- \text{a.s.}
\end{equation}

Of course, the deviation probability $\mathbb{P}_\nu \left (t^{-1}\int_{0}^{t}f(X_s)ds - \pi(f)  \geq u \right )$ is of equal interest, however, it is sufficient to consider (<ref>) as we can replace $f \to -f$. It is important to note that the ergodic theorem is asymptotic in nature and it does not provide any information about about the rate of convergence or deviations at finite time. However, in many areas of application, e.g. Monte-Carlo simulation or non-equilibrium statistical physics, it is of interest to examine the fluctuations of (finite time) averages $t^{-1}\int_0^t f(X_s) ds$, and to approximate $\int f d \pi$ by the (finite time) average  $t^{-1}\int_0^t f(X_s) ds$ (see also Section <ref>). Consequently, the study of concentration inequalities is of fundamental and practical interest, as they provide some insight to the fluctuations of time averages and provide quantitative bounds for times, where time averages $t^{-1}\int_0^t f(X_s) ds$ are 'close' to $\pi(f) $ .

To derive concentration inequalities  we will use the so called Cramér-Chernoff method, a general technique which is used to provide bounds for probabilities of the form $\F{P}(Z \geq u)$. The application of the Cramér-Chernoff method to derive concentration inequalities for (<ref>) in the context of Markov processes is well established, and  this work is based on <cit.>, <cit.>, <cit.>, <cit.>; works that derive concentration inequalities for (<ref>) based on the explicit or implicit use of the Cramér-Chernoff method . These works all consider more general Markov processes, and in this work we present, summarize and extend some selected concentration inequalities (<cit.>, <cit.>, <cit.> and <cit.>) in the context of Markov jump processes. The present work can be read independently of the works just mentioned, in particular we present full proofs of the main results (contained in Section <ref>). Nonetheless, it is advisable for the reader to inspect also the mentioned works as these provide additional context and we sometimes explain the connections in the notation, the results and proofs of the present work with respect to the corresponding notation, results and proofs of <cit.>, <cit.>, <cit.>, <cit.>. The main results of this work are summarized in Section <ref>.

This thesis is divided in three main parts. First, Section <ref> presents the general framework and the most important background information on which this thesis is based on. Hereby, Section <ref> treats MJPs (Markov jump processes) —the general framework of this thesis. Here we provide basic definitions and results about MJPs, including invariant distributions, infinitesimal generators and long term behavior. In Section <ref>  we present additional tools and background information concerning  linear algebra, perturbation theory and convex analysis. Overall, Section <ref> contains frameworks, definitions and results, which are used in Section <ref> in the derivation of concentration inequalities. Then, in Section <ref> —the core of this thesis —we present the Cramér-Chernoff method and  apply it to functionals of MJPs to derive concentration inequalities for the probability (<ref>). Hereby, in Section <ref> we explain how the Cramér Chernoff method may be used  to derive general concentration inequalities for tail probabilities $\F{P}(Z \geq u)$. Then,  in Section <ref>, based on the Cramér-Chernoff method we derive concentration inequalities for functionals of (irreducible) MJPs;  we first  derive a general concentration inequality  and then based on this inequality we derive further, more concrete concentration inequalities by using three different approaches: perturbation theory, functional inequalities  and information inequalities. A detailed outline of Section <ref> is given in Section <ref>.
Finally, in Section <ref> we summarize our results, give an outlook to further theory and discuss the application in physics.

To comprehend this thesis the reader should have a solid understanding of basic probability theory; including stochastic processes and conditional expectations, basic linear algebra and some functional analysis; in particular, basic knowledge about Hilbert spaces. Knowledge about Markov processes is useful but not necessary to understand the core of this thesis.

§ PRELIMINARIES

§.§ Markov Jump Processes

Markov jump processes are a special type of Markov processes —stochastic processes  defined by the Markov property, which states that given the present the future is independent of the past. Markov processes find applications in many areas including physics, population dynamics, financial markets, etc. If the state space $E$ of the process is countable, the term 'continuous time Markov chain' is also frequently used (see  <cit.>, <cit.>,<cit.>,<cit.>). We shall use the term Markov jump process (MJP) and consider only finite state spaces.

This section is structured as follows. First, in Section <ref>  we present basic definitions and results, providing a general framework and introducing notation. Then, in Section <ref> we consider invariant distributions and present a central result about the existence and uniqueness. Afterwards, in Section <ref> we present the Markov semigroup of an MJP and compute the infinitesimal generator and its properties. Finally, in Section <ref> we present two results about the long term behavior, including  the ergodic theorem.

It should be mentioned that not everything covered in Section <ref> will be necessary for
our purposes. Nevertheless, it is still worthwhile covering all these topics as they provide  solid background information. The most important notions and results of this section, which should be kept in mind when reading the main part of this work, are: The basic framework and notions —irreducible MJPs (Definitions <ref>, <ref>) and invariant distributions (Definition <ref>), the existence and uniqueness of invariant distributions (Theorem <ref>), infinitesimal generators of (irreducible) MJPs  and its properties (Section <ref>) and the ergodic Theorem (Theorem <ref>). A reader who is mainly interested in the core of this work  (Section <ref>) and is  familiar with basic concepts and notation of MJPs may skim through the definitions and results of Sections <ref>, <ref> and <ref>, focus on Section <ref> and on the results and definitions just mentioned.

§.§.§ Basic Theory

In the following let $E$ be a finite set endowed with the $\sigma$-algebra $ \mathcal{E} = \mathcal{P}(E)$. Furthermore, endow $E^{[0,\infty)}$ with the product $\sigma$-algebra $\mathcal{E}^{[0,\infty)}$.  Following <cit.> we define:

Let $\F{X} = (X_t)_{ t \geq 0}$ be an $E$-valued stochastic process, defined on an underlying measure space $(\Omega, \mathcal{F})$  and let $(\F{P}_x)_{x \in E}$ be a family of probability measures on $(\Omega,\mathcal{F})$. We call $\F{X}$ (or more precisely $(\F{X}, (\F{P}_x)_{ x \in E})$) an MJP if

* $\F{X}$ is a jump process, i.e. for all $\omega \in \Omega$ and all $t \geq 0$ there is a $\varepsilon > 0$ such that

\begin{equation*}
X_{t+h}(\omega) = X_{t}(\omega) \: \text{for all} \: h \in [t,t+
\varepsilon].
\end{equation*}

* $\F{P}_x(X_0 = x) = 1$ for all $x \in E$

* The Markov property holds, i.e.  for all $x \in E$, all $t \geq 0$ and all bounded and measurable $A : E^{[0,\infty)} \rightarrow \F{R}$

\begin{equation}
\label{eq: Markov_property}
\F{E}_x[A((X_{t+s})_{ s \geq 0}) | (X_r)_{ 0 \leq r \leq t}] = \F{E}_x[
A((X_{t+s})_{ s \geq 0}) |X_t] =  \F{E}_{X_t}[A((X_s)_{s \geq 0})],
\end{equation}

where $\F{E}_x$ denotes the (conditional) expectation under the measure $\F{P}_x$. Define for $t \geq 0$

\begin{equation}
P(t) := (p_{xy}(t))_{x,y \in E},
\end{equation}

\begin{equation}
p_{xy}(t) := \F{P}_x(X_t = y).
\end{equation}

The family $(P(t))_{t \geq 0}$ of matrices is called transition function of the MJP.

(Right continuity)
As $E$ is countable, note that condition $(a)$ above, which states that the paths of the process are piecewise constant, is equivalent to the right continuity of the paths of $\F{X}$. In this work we are only interested in processes with right continuous (i.e. piecewise constant) paths. Furthermore, as the term 'jump process' is usually defined as a right continuous process with piecewise constant paths (see e.g.  <cit.>, <cit.>, <cit.>), we decided to use the term Markov jump process (MJP) for the stochastic process of our interest. That we assume right continuity of the paths of the stochastic process has the following reasons:

* Right continuity ensures directly that for any $f : E \rightarrow \F{R}$ our time average of interest $t^{-1}\int_0^t f(X_s) ds$ is well defined, measurable  and can be approximated by Riemann sums.

* In applications, in order  to characterize the distribution of the process, one specifies the so called   $Q$-matrix $Q = (q_{xy})_{x,y \in E}$ which characterizes the transition probabilities $p_{xy}(t) = \F{P}(X_t = y | X_0 = x) $ for 'small' times:

* $p_{xy}(h) = q_{xy}h + o(h)$ as $ h \to 0$ for $x \neq y$

* $p_{xx}(h) = 1 + q_{xx} h + o(h)$ as $h \to 0$

Given such a matrix $Q$, one can construct explicitly a continuous time Markov chain with right continuous paths whose transition probabilities satisfy $(a)$ and $(b)$  (see Theorem <ref>$(b)$).

* Right continuity ensures that the so called infinitesimal generator $L$ —a linear operator acting on functions $f : E \rightarrow \F{R}$ —of the Markov process exists, and $Lf$ is defined for all $f : E \rightarrow \F{R} $ (for details see Lemma <ref>). This property allows us to derive concentration inequalities that hold for all $f : E \rightarrow \F{R}$ ($f$ is the function used in the time average $t^{-1} \int_0^tf(X_s)ds$).

(Equivalent definitions)

It should be remarked that there  are many different (equivalent) ways to define an MJP or, respectively  a 'continuous time Markov chain'. One may use a definition that describes the process via an underlying Markov chain and exponentially distributed  random variables (see  <cit.>, Theorem <ref>$(b)$). Alternatively, one may use a definition that describes an MJP as a special case of a Markov process (see <cit.>). One may include the Markov property (<ref>)
directly in the definition (see e.g.<cit.>), or one may use the fact that when considering a stochastic process $\F{X}$ on a countable space $E$ the Markov property
follows also from the statement

\begin{equation}
\label{eq: alternative_to_markov}
\F{P}( X_{t+s} = y | X_s = x, X_{s_1} = x_1,..., X_{s_k} = x_k ) = \F{P}( X_{t+s} = y| X_s = x) = \F{P}( X_t = y | X_0 = x)
\end{equation}

for all $x,y, x_1,..x_k \in E$, all $t,s \geq 0$, and all $0 \leq s_1 \leq ....\leq s_k \leq s $, and then just require in the definition that (<ref>) holds (see e.g. <cit.>, <cit.>). Furthermore, one may include a family $(\F{P}_x)_{x \in E}$ of ”starting measures” , where $(\F{X},\F{P}_x)$ describes the process started at $x$, directly in the definition (see <cit.>) or define them via $\F{P}_x = \F{P}(\: \cdot \: | X_0 = x) $ (see <cit.>). As we shall later use the Markov property (see e.g. Lemma <ref>) in the form (<ref>), we directly included it in the definition. Furthermore, we want to also work with the measures $(\F{P}_x)_{x \in E}$, so we also included them directly in the definition.

To define the concept of an MJP with starting distribution $\nu$, define for any probability measure $\nu = (\nu_x)_{x \in E}$ on $E$ the probability measure

\begin{equation}
\label{eq: def_P_nu}
\F{P}_\nu := \sum_{x \in E} \nu_x \F{P}_x.
\end{equation}

Denote by $\F{E}_\nu$ the expectation under  $\F{P}_\nu$ and by $\mathscr{L}_\nu(Z)$ the distribution of a random element $Z$ under $\F{P}_\nu$, i.e. $\mathscr{L}_\nu(Z) = \F{P}_\nu Z^{-1}$. Notice that because of property $(b)$ in Definition <ref> of an MJP we have that $\mathscr{L}_\nu(X_0) = \nu$, thus we refer to $(\F{X}, \F{P}_\nu)$ as an MJP with initial distribution $\nu$.
Notice that the initial distribution $\nu $ and the transition function $(P(t))_{t \geq 0}$ uniquely determine the distribution of $\F{X}$ under $\F{P}_\nu$ (on the path space $(E^{[0, \infty)}, \mathcal{E}^{[0,\infty)}$)). Indeed, using the Markov property (<ref>) with $A((x_s)_{s \geq 0}) = 1_{\{ x_h = y\}}$ for $h \geq 0$, $y \in E$ and $(x_s)_{s\geq 0} \in E^{[0,\infty)}$ yields for any $x_1,...,x_n \in E$ , $0 \leq t_1 \leq ... \leq t_n$ and any $h \geq 0$ that

\begin{align*}
&\F{P}_x(X_{t_1} = x_1,...,X_{t_n} = x_n , X_{t_n + h} = y) = \F{E}_x[\F{E}_x(1_{ \{X_{t_n+h} = y \}}| (X_r)_{ 0 \leq r \leq t_n})1_{ \{X_{t_1} = x_1 ,...,X_{t_n} = x_n \}} ] \\
&=\F{E}_x[\F{E}_{X_{t_n}}(1_{ \{ X_h = y \}}) 1_{ \{X_{t_1} = x_1 ,...,X_{t_n} = x_n \}}] = p_{x_ny}(h)\F{P}_x(X_{t_1} = x_1,...,X_{t_n} = x_n ).
\end{align*}

\begin{equation*}
\F{P}(X_{t_n+h} = y | X_{t_1}= x ,..., X_{t_{n}} = x_{n}) = p_{x_ny}(h),
\end{equation*}

and thus for any $0 \leq t_1 ... \leq t_n$ and any $x_1,...,x_n \in E$

\begin{align}
\label{eq: fidi_distributions}
\begin{split}
&\F{P}_\nu(X_{t_n} = x_n,..., X_{t_1} = x_1) \\
&= \sum_{ x \in E} \nu_x  \F{P}_x(X_{t_1} = x_1 | X_0 = x) ...\, \F{P}_x(X_{t_n} = x_n | X_0 = x , X_{t_1} = x_1,..., X_{t_{n-1}} = x_{n-1}) \\
&=\sum_{x \in E} \nu_x  p_{xx_1}(t_1)...\,p_{x_{n-1}x_n}(t_n - t_{n-1}).
\end{split}
\end{align}

Thus, the finite dimensional distributions $\mathscr{L}_\nu(X_{t_1},...,X_{t_n})$ are determined by $\nu $ and $(P(t))_{ t \geq 0}$,  so by the uniqueness theorem for stochastic processes  $\mathscr{L}_\nu(\F{X}) $ is uniquely determined. It is straightforward to check that the transition function has the following properties:

* $P(t)$ is a stochastic matrix, i.e $p_{xy}(t) \geq 0$ and $\sum_{y \in E}p_{xy}(t) = 1$ for all $x,y \in E$ and all $t \geq 0$.

* $\lim_{t \downarrow 0} p_{xy}(t) = p_{xy}(0) = \delta_{xy}$ for all $x,y \in E$

* $P(s+t) = P(t)P(t)$, i.e. for all $t,s \geq 0$ and all $x,y \in E$

\begin{equation}
\label{eq: chapman_kolmogorov_equation}
p_{xy}(t+s) = \sum_{z \in E}p_{xz}(t)p_{zy}(s)
\end{equation}

Here 2. follows from the dominated convergence theorem and the right continuity of $\F{X}$, and (<ref>) follows from the Markov property  <cit.>.
The equations (<ref>) are called Chapman-Kolmogorov equations. Generally, any family $(P(t))_{t \geq 0}$ of matrices indexed by $E$ satisfying the above three properties is called a transition function <cit.>. Not every transition function (in the case of infinite $E$) is given by an MJP (for a counterexample see <cit.>). Because of the Chapman-Kolmogorov equations for the transition function  one could hope that it is possible to find a matrix $Q = (q_{xy})_{x,y \in E}$ such that $P(t) = \exp(tQ)$. This would make it possible to characterize the infinite family $(P(t))_{t\geq 0}$ (and thus the distribution of $\F{X})$  via just one matrix. If $P(t) = \exp(tQ) $, then in particular $\frac{d}{dt}P(t)|_{t = 0} = Q$. Because $\sum_{y \in E} p_{xy}(t) = 1$ and $p_{xy}(t) \geq 0 = p_{xy}(0)$ (for $x \neq y$), this implies (using finiteness of $E$ and interchanging sum and derivative)

* $q_{xy} \geq 0$ for all $ x,y \in E$, $x \neq y$

* $\sum_{y \in E} q_{xy} = 0$ for all $x \in E$.

This motivates the following definition (we follow the definition of <cit.>)

Let $Q = (q_{xy})_{x,y \in E}$ be a matrix of real numbers. $Q$ is called a $Q$-matrix if

* $q_{xy} \geq 0$ for all $ x,y \in E$, $x \neq y$

* $\sum_{y \in E} q_{xy} = 0$ for all $x \in E$

For any $Q$-matrix $Q$ define $q_x := - q_{xx} = \sum_{ y \neq x} q_{xy}$.

As we will see in Theorem <ref>, transition functions of MJPs are exactly those that are given by $P(t) = \exp(tQ)$ for some $Q$-matrix $Q$. Before characterizing MJPs and the corresponding transition functions let us state the following result, which generalizes the Markov property (<ref>) and will be used to prove the characterization result (Theorem <ref>).

An MJP satisfies the strong Markov property, i.e. for any stopping time $\tau$, any $B \in \mathcal{E}^{[0,\infty)}$ and any $x \in E$

\begin{equation}
\F{P}_x( (X_{t+\tau})_{t \geq 0} \in B, \tau < \infty | \mathcal{F}_\tau ) = 1_{\{\tau < \infty \} } \F{E}_{X_\tau}( (X_t)_{t \geq 0} \in B),
\end{equation}

where $\mathcal{F_\tau} = \{ A \in \mathcal{F} \, | \, A \cap \{ \tau \leq t \} \in \sigma( (X_s)_{0 \leq s \leq t}) \} $ denotes the $\sigma$-algebra of $\tau$-past.

Let us explain intuitively how an MJP may be characterized. For that consider the path $t \mapsto X_t$ of an MJP. If the process is in state $x $ at time $t$, i.e. $X_t = x$, then because of right continuity,  $X_t$ stays at $x$ for a positive time and then $X_t$ 'jumps'  to another state $y \in E$ (or $X_t$ stays forever at $x$). The total time of staying in $x$ before making a jump is called the holding time. Because of the Markov property, if the process is in state $x$ at time $t$ the future process $(X_s)_{ s \geq t }$ should behave (in distribution) like an MJP (with same transition function) started at $x$ at time $t = 0$. Thus one expects the following properties of the holding time:

* The distribution of the holding time just depends on the state $x$

* The distribution of the holding time should be memoryless, i.e. if $T$ denotes the holding time then $\F{P}(T > t +s | T > t) = \F{P}( T > s)$

This would imply that $T \sim \mathrm{Exp}(q_x)$ for some $q_x \geq 0$. This is indeed the case (see proof of Theorem <ref>). Furthermore, if $\tau_n$ denotes the time of the $n$-th jump by the strong Markov property one expects $(X_{\tau_n})_{ n \in \F{Z}_+}$ to be a Markov chain. Thus, an MJP should be characterized by a Markov chain —describing the jumps, and exponentially distributed holding times —describing the time the MJP stays at some state. More precisely, we have:

* Let $(\F{X},(\F{P}_x)_{x \in E})$ be an MJP with transition function $(P(t))_{t \geq 0}$. Define recursively the stopping times $\tau_0 := 0$ and

\begin{equation}
\tau_n := \inf \{ t \geq \tau_{n-1} | X_t \neq X_{\tau_{n-1}} \}
\end{equation}

for $n \in \F{N}$, where $\inf \emptyset = \infty$. Furthermore, define a stochastic process $\F{Y} = (Y_n)_{n \in \F{Z}_+}$ on $E$ (recursively) via  $Y_0 := X_{\tau_0} = X_0$ and

\begin{equation}
Y_n :=
\begin{cases}
X_{\tau_n} \; ; \; \tau_n < \infty \\
Y_{n-1} \; ; \; \tau_n = \infty
\end{cases}.
\end{equation}

* There is a unique $Q$-matrix $Q$ such that $P(t) = \exp(tQ)$, and it is given by

\begin{equation}
\label{eq: def_Q_matrix_of_MJP}
q_{xy} = (\F{E}_x(\tau_1))^{-1} (\F{P}_x(X_{\tau_1} = y) - \delta_{xy}),
\end{equation}

where $q_{xy} = 0 $ if $\F{E}_x(\tau_1) = \infty $.

* Let $q_{xy}$ be defined as above and $q_x = -q_{xx}$. Then,  $(\F{Y}, (\F{P}_x)_{x \in E})$ is a Markov chain with transition probabilities given by

\begin{equation}
\label{eq: def_underlying_MC_1}
p_{xx} = 1 \quad and \quad p_{xy} = 0 \quad  for \,\, y \neq x
\end{equation}

if $q_x = 0$, and by

\begin{equation}
\label{eq: def_underlying_MC_2}
p_{xx} = 0 \quad and \quad p_{xy} =  \frac{q_{xy}}{q_x} \quad  for \,\, y \neq x
\end{equation}

if $q_x > 0$.

* There is a sequence of random variables $(R_k)_{k \in \F{N}}$ such that for all $x \in E$ and all $n \in \F{Z}_+$

\begin{equation}
\label{eq: tau_n}
\tau_n = \sum_{k = 1}^n \frac{R_k}{q_{Y_{k-1}}} \quad \F{P}_x\text{- }a.s.
\end{equation}

Hereby, for all $x \in E$, with respect to $\F{P}_x$, the sequence $(R_k)_{k \in \F{N}}$ is independent of $\F{Y}$ and i.i.d. with

\begin{equation}
\mathscr{L}_x(R_k) = Exp(1),
\end{equation}

where $Exp(1)$ denotes the exponential distribution with expectation $1$. In other words, for all $x \in E$ it holds that given $\F{Y}$ the  holding times $(\tau_n - \tau_{n-1})_{n \in \F{N}}$ are independent and exponentially distributed with respect to $\F{P}_x$, i.e. for all $n \in \F{N}$ and $r \geq 0$

\begin{equation}
\F{P}_x(\tau_{n}-\tau_{n-1} > r \,| \, \F{Y}) = e^{-q_{Y_{n-1}}r}.
\end{equation}

* Conversely, let $Q$ be a $Q$-matrix, $(\F{Y}, (\F{P}_x)_{x \in E})$ a Markov chain with transition probabilities as above $($see (<ref>) and (<ref>)$)$, and  $(R_n)_{n \in \F{N}}$  a sequence of  random variables such that for all $x$, with respect to $\F{P}_x$, the sequence is independent of the Markov chain $\F{Y}$ and i.i.d. with $\mathscr{L}_x(R_1) = Exp(1)$. Furthermore, let  $\tau_n$ be defined as in (<ref>) and define the stochastic process $\F{X} = (X_t)_{t \geq 0}$ by

\begin{equation}
\label{eq: def_MJP_holding_times}
X_t = Y_n \quad for \,\, t \in [\tau_n, \tau_{n+1}).
\end{equation}

Then after removing a common nullset of all $\F{P}_x$'s,  the process  $(\F{X}, (\F{P}_x)_{x \in E})$ is a well defined MJP on $E$ with transition function $P(t) = \exp(tQ)$ and $P(t)$ is the unique transition function satisfying $Q = \frac{d}{dt}P(t)|_{t = 0}$.

Part ($a$):

* Note that if $P(t) = \exp(tQ)$ then $Q = \frac{d}{dt}|_{t = 0}P(t)$, so there is at most one $Q$ matrix such that $P(t) = \exp(tQ)$. Thus, it suffices to show that $Q$ defined in (<ref>) satisfies $P(t) = \exp(tQ)$. By the existence and uniqueness theorem for differential equations ($E$ is finite) it is sufficient to show that the equation

\begin{equation*}
\frac{d}{dt}P(t) = QP(t)
\end{equation*}

is satisfied. It can be shown (<cit.>) that this equation is equivalent to the integral equations

\begin{equation}
\label{eq: integral_equation}
p_{xy}(t)= \delta_{xy}e^{-q_x t} + \int_0^t e^{-q_x s}\sum_{z \neq x}q_{xz}p_{zy}(t-s) ds.
\end{equation}

Moreover, using the Markov property it can be shown that for any $x \in E$ (<cit.>)

* $\mathscr{L}_x(\tau_1) = Exp(q_x)$, where $Exp(0) = \delta_\infty$. Here $Exp$ denotes the exponential distribution and $\delta$ the Dirac-distribution.

* Under $\F{P}_x$ the process $(X_{t+\tau_1})_{t \geq 0}$ is independent of $\tau_1$ (for $q_x > 0)$.

To show  (<ref>) we follow the idea of <cit.>. Assume $q_x > 0$, otherwise (<ref>) is trivially satisfied. We get (using the disintegration theorem)

\begin{align*}
&\F{P}_x(X_t = y) =  \F{P}_x(X_t = y, \tau_1 > t) + \F{P}_x(X_t = y, \tau_1 \leq  t)\\
&= \delta_{xy}e^{-q_x t} + \int_0^t\F{P}_x( X_t = y | \tau_1 = s) \F{P}_x(\tau_1 \in ds) \\
&= \delta_{xy}e^{-q_x t}+ \int_0^t\F{P}_x( X_{t-s + \tau_1} =   y | \tau_1 = s) \F{P}_x(\tau_1 \in ds) \\
&= \delta_{xy}e^{-q_x t}+ \int_0^t\F{P}_x( X_{t-s + \tau_1} =   y) \F{P}_x(\tau_1 \in ds) \\
&= \delta_{xy}e^{-q_x t}+ \int_0^t \sum_{z \neq x}\F{P}_x(X_{\tau_1} = z)p_{zy}(t-s)q_x e^{-q_xs}ds.
\end{align*}

Whereby in the fourth line we used the independence of $\tau_1$ and $(X_{t+\tau_1})_{t \geq 0}$ and in the fifth line we used the strong Markov property (Lemma <ref>).
Consequently (<ref>) is satisfied and the transition function of the MJP is given by $P(t) = \exp(tQ)$

2. and 3.: This is exactly the statement of <cit.>. Let us explain the connection between the notation of <cit.> and our notation. Let $\mu$ be the kernel defined via $\mu(x,B) = \F{P}_x( X_{\tau_1} \in B)$ and $c$ be the function defined via $c(x) = \F{E}_x(\tau_1)^{-1}$, this is the notation of <cit.>. Using the definition (<ref>) of the $Q$-matrix  and the definitions of the transition probabilities $p_{xy}$ it is easy to check that

\begin{equation}
q_x = c(x)  \quad \text{and} \quad \mu(x,{y}) = p_{xy}
\end{equation}

for all $x,y \in E$. Thus, statements 2. and 3. are a reformulation of <cit.>.

Part ($b$):
Finally, for part $(b)$ note that $\F{X}$ defined via (<ref>) is a well defined, right continuous process (after removing a common nullset of all $\F{P}_x$'s). Indeed, as  the $R_k$'s are exponentially distributed we may assume $R_k > 0$ and thus  $\tau_{n+1} > \tau_{n}$ whenever $\tau_n < \infty $. Consequently, $\F{X}$ has right continuous paths (as they are piecewise constant) and is well defined on $\cup_{n \in \F{Z}_+}[\tau_n,\tau_{n+1})$. Moreover, the finiteness of $E$ implies
$C := \sup_{x \in E} q_x < \infty$, so

\begin{equation}
\tau_n \geq \frac{1}{C} \sum_{k = 1}^n R_k .
\end{equation}

But the right hand side goes to infinity $\F{P}_x$- a.s. by the Borel-Cantelli lemma. Thus, $\F{P}_x$ - a.s. we have $ \F{R} =\dot{\cup}_{n \in \F{Z}_+}[\tau_n, \tau_{n+1})$ (disjoint union) and $\F{X}$ is a well defined, right continuous process (after removing a common nullset of all $\F{P}_x$) with $\F{P}_x(X_0 = x) = \F{P}_x( Y_0 = x) = 1$ for all $x \in E$. It remains to show that $\F{X}$ satisfies the Markov property of Definition <ref>. We invoke <cit.>. By construction of $\F{X}$ the conditions of <cit.> are satisfied and thus

\begin{equation}
\label{eq: pf_alternative_markov_property}
\F{P}( X_{t+s} = y | X_s = x, X_{s_1} = x_1,..., X_{s_k} = x_k ) = \F{P}( X_{t+s} = y| X_s = x)   = p_{xy}(t)
\end{equation}

for all $x,y, x_1,..x_k \in E$, all $t,s \geq 0$, and all $0 \leq s_1 \leq ....\leq s_k \leq s $, where $(p(t))_{x,y \in E} = P(t) = \exp(tQ)$. But (<ref>) is equivalent to the Markov property of Definition <ref>, which follows by a standard $\pi-\lambda$ argument (see also Remark <ref>).

* Theorem <ref>$(b)$ gives an algorithm for the simulation of an  MJP with $Q$-matrix $Q$.

* In the above proof  we implicitely proved, that any MJP on a finite state space is non-explosive, i.e.

\begin{equation}
\F{P}_x \left ( \lim_{n \to \infty} \tau_n = \infty \right ) = 1
\end{equation}

for all $x$. In other words, $\F{P}_x$ - almost surely there are just finitely many jumps in finite time.

The $Q$ matrix, defined by (<ref>) or the relation $P(t) = \exp(tQ)$ is called the $Q$-matrix of the MJP.

The Markov chain $\F{Y} = (Y_n)_{n \in \F{Z}_+}$ is called the underlying chain of the MJP

Finally, as a direct consequence we obtain the well known Kolmogorov equations.

Let $(P(t))_{t \geq 0}$ be the transition function of an MJP with $Q$-matrix $Q$. Then
$(P(t))_{t \geq 0}$ satisfies the Kolmogorov equations

\begin{align}
&\text{Kolmogorov Backward Equation: } \frac{d}{dt}P(t) = QP(t)  \label{eq: KBE}\\
& \text{Kolmogorov Forward Equation: } \frac{d}{dt}P(t) = P(t)Q
\end{align}

Follows directly from $P(t) = \exp(tQ)$.

§.§.§ Invariant Distributions

We now discuss the concept of invariant distributions, which play a central role in describing the limit behavior (e.g. the ergodic theorem) of an MJP. We define (c.f. <cit.>).

A nontrivial probability measure $\mu = (\mu_x)_{x \in E}$ is called invariant (or stationary) distribution if for all $t \geq 0$

\begin{equation}
\label{eq: def_invariant_measure}
\mu^T P(t) = \mu^T.
\end{equation}

Notice that $\mu$ is a stationary distribution if and only if  $\mu = \mathscr{L}_\mu(X_t)$ for all $t \geq 0$. By the  Markov property this is equivalent to

\begin{equation*}
\mathscr{L}_\mu((X_{t+s})_{t \geq 0}) = \mathscr{L}_\mu((X_t)_{t \geq 0})
\end{equation*}

for all $ s \geq 0$, i.e. the process is strongly stationary.
As $E$ is finite, we can interchange summation over $E$ and the differentiation, so using the Kolmogorov backward equation (Corollary <ref>) yields

\begin{equation*}
\frac{d}{dt}\mu^TP(t) = \mu^T\frac{d}{dt}P(t) = \mu^T Q P(t).
\end{equation*}

It follows that $\mu$ is an invariant distribution if and only if

\begin{equation}
\label{eq: def_invariant_measure_infinitesimal}
\mu^TQ = 0 ,
\end{equation}

which reduces the infinite system of equations (<ref>) to just one equation in terms of the $Q$-matrix. Using that  $\sum_{ y \in E, y \neq x} q_{xy} = -q_{xx}$ for all $x \in E$, we can write (<ref>) equivalently as
\begin{equation}
\label{eq: prepariation_for_detailed_balance}
0 = \sum_{ y \in E, y \neq x}\mu_y q_{yx} - \sum_{ y \in E, y \neq x}\mu_x q_{xy}  = \sum_{y \in E, y \neq x}\mu_y q_{yx} - \mu_x q_{xy}.
\end{equation}

Intuitively, if we interpret $\mu_x q_{xy}$ as the 'probability flow' from $ x$ to $y$, then $\sum_{ y \in E, y \neq x}\mu_x q_{xy}$ is the total 'probability outflow' from $ x $ and $\sum_{ y \in E, y \neq x} \mu_y q_{yx}$ is the total 'probability inflow' to $x$. Using  (<ref>) we can interpret (<ref>) as  'the net probability flow vanishes'. Intuitively, the 'net probability flow' would vanish if for all $ x \neq y$ the flow from $x $ to $y$ is equal to the flow from $y$ to $x$ i.e. $\mu_x q_{xy} = \mu_y q_{yx}$, then also the equivalent condition (<ref>) for $\mu$ to be an invariant distribution would be satisfied , as each summand on the right hand side  vanishes. This observation motivates the following definition.

We say a probability measure $\mu = (\mu_x)_{x \in E}$ on $E$ satisfies the detailed balance condition if for all $x,y \in E$

\begin{equation}
\label{def: detailed_balance}
\mu_x q_{xy} = \mu_y q_{yx}.
\end{equation}

Thus, the detailed balance condition is an 'easier' set of equations that are sufficient for $\mu$ to be an invariant distribution. However, these equations are not always solvable, the following remark gives a brief insight on when a measure satisfying the detailed balance condition exists.
(Kolmogorov cycle criterion)
A natural question to ask is when a probability measure satisfying the detailed balance condition exists. The so called Kolmogorov cycle criterion provides information about the existence of a measure satisfying the detailed balance condition. The Kolmogov cycle criterion states that for all closed paths $x, x_1,...,x_n, x $ in $E$

\begin{equation}
q_{xx_1}q_{x_1x_2}.....q_{x_nx} = q_{xx_n}q_{x_nx_{n-1}}.....q_{x_1x}.
\end{equation}

This criterion is essentially equivalent to the existence of an measure that satisfies detailed balance (see <cit.> for details of this equivalence). However, for our purposes this criterion is not relevant and we shall not discuss it further. For a more detailed presentation of the Kolmogorov cycle criterion see <cit.>

Not every MJP admits an invariant distribution. The following condition guarantees the  existence and uniqueness an invariant distribution for an MJP (c.f. Theorem <ref>).

For an MJP the following statements are equivalent :

* The underlying Markov chain $\F{Y}$ is irreducible, i.e. for all $x,y \in E$

\begin{equation*}
\F{P}_x(\exists \; n \in \F{Z}_+ : Y_n = y) > 0.
\end{equation*}

* For all $x,y \in E$

\begin{equation*}
\F{P}_x(\exists \; t \geq 0 : X_t = y) > 0.
\end{equation*}

* For all $x,y \in E$ and all $t  > 0$

\begin{equation*}
p_{xy}(t) > 0.
\end{equation*}

* For all $x \neq y$ there is a $n \in \F{N}$ and a sequence $ x_0 := x,x_1,...,x_n := y$ such that

\begin{equation}
q_{x_0x_1}...q_{x_{n-1}x_n} > 0.
\end{equation}

If any of the above conditions are satisfied we call an MJP irreducible.

The equivalence of statements $(a), (c)$ and $(d)$ is shown in <cit.>. It should be remarked that although <cit.> shows the equivalence of $(a), (c), (d)$ for  $P(t) = F(t)$, where $F(t)$ is the minimal solution of the backward equation (<ref>) (see <cit.> for a definition of the minimal solution $F(t)$), the theorem can still be applied to our setting because by the uniqueness theorem for differential equations and Theorem <ref> we automatically have $F(t) = \exp(tQ) = P(t)$. Finally, statements $(a)$ and $(b)$ are equivalent because by definition of the underlying jump chain $\F{Y}$ (see Theorem <ref>) we have

\begin{equation*}
\{\,Y_n \,|\, n \in \F{Z}_+\,\} = \{ \,X_t\, |\, t \geq 0\,\}
\end{equation*}

(for all $\omega \in \Omega$) and consequently

\begin{equation*}
\F{P}_x(\exists \; t \geq 0 : X_t = y) = \F{P}_x( \exists \; n \in \F{Z}_+ : Y_n = y).
\end{equation*}

Thus, irreducibility means that starting from any state $x \in E$, the chain  can always reach any other state $y \in E$ with positive probability. For irreducible MJPs on a finite state space we have the following theorem on the existence and uniqueness of invariant distributions.

Let $\F{X}$ be an irreducible MJP on $E$. Then there is a unique strictly positive  invariant distribution $\pi = (\pi_x)_{x \in E}$, i.e. $\pi_x > 0 $ for all $x \in E$.

Follows applying <cit.> to an irreducible MJP on a finite state space $E$. The conditions of <cit.> are satisfied, because  $\F{X}$ is irreducible in the sense of definition <cit.> by assumption. Furthermore,  any irreducible Markov chain on a finite state space is recurrent (see <cit.>) and consequently $\F{X}$ is recurrent in the sense of definition <cit.>. Moreover, any invariant measure $\mu$ on $E$ defines a invariant distribution $\pi$ by setting $\pi = \frac{\mu}{\mu(E)}$ and thus <cit.> yields the uniqueness and existence of a unique strictly positive invariant distribution.

§.§.§ Infinitesimal Generators

In this section we present a brief overview of the concept of infinitesimal generators and explain how the situation simplifies for a finite state space $E$. Later, to derive concentration inequalities, the  infinitesimal generator of the MJP will be of central importance. We start with a more general concept of infinitesimal generators of semigroups on Banach spaces and then analyze the situation for an (irreducible) MJP. We start by defining (c.f. <cit.>)

Let $(V, \norm{\cdot})$ be a (real) Banach space. A family $(P_t)_{t \geq 0}$ of operators on $V$ is called a  semigroup of operators if

* $P_{s+t} =P_sP_t$ for all $s,t \geq 0$

* $P_0 = 1$.

If furthermore  $\norm{P_t} \leq 1$ for all $ t \geq 0$, then $(P_t)_{t \geq 0}$ is called a contraction semigroup.
A semigroup is called continuous if for any  $v \in V$ $\norm{P_hv-v} \to 0$ as $h \to 0$.

Let $(P_t)_{t \geq 0}$ be a   semigroup on $V$. Define

\begin{equation*}
D = \left \{ v \in V \middle  | \; \lim \limits_{ h \to 0} \frac{P_hv-v}{h} \; \text{exists in V} \right \}
\end{equation*}

and for $v \in D$ define

\begin{equation}
\label{eq: def_infinitesimal_generator}
Lv =  \lim \limits_{ h \to 0}  \frac{P_hv-v}{h}.
\end{equation}

Then $L : D \rightarrow V$ is called infinitesimal generator of $(P_t)_{t\geq 0}$. Denote by $D(L) = D$ the domain of $L$.

(Finite dimensional $V$)

If $V$ is finite dimensional then given any operator $L : V \rightarrow V$ there is a unique semigroup $(P_t)_{t \geq 0}$ having infinitesimal generator $L$, that is given by $P_t = \exp(tL)$. We call $(P_t)_{ t \geq 0}$ the semigroup generated by $L$.

A general Markov process (see <cit.> or <cit.> for a definition of general Markov processes) $(\F{X}, (\F{P}_x)_{x \in E})$ on some general (polish) space $E$  defines in a natural way a semigroup of operators $(P_t)_{t \geq 0}$ on the Banach space of bounded, measurable real-valued functions $(\mathcal{B}(E), \norm{\cdot}_\infty)$ by

\begin{equation}
\label{eq: contraction_semigroup_Markov_process}
(P_tf)(x) :=  \F{E}_x(f(X_t)),
\end{equation}

where the semigroup property $P_{s+t} = P_sP_t$ follows from the Markov property. If $\pi $ is an invariant distribution of the Markov process (see  <cit.> for a general definition of invariant distributions), then $(P_t)_{t \geq 0}$ can be seen as a (well defined) contraction semigroup on $L^p(\pi)$ for all $p \geq 1$ (see Remark <ref>). The works <cit.>, <cit.>, <cit.>, <cit.> considered here that derive concentration inequalities for more general Markov processes (than MJPs) consider $(P_t)_{t \geq 0}$ on the function space $L^2(\pi)$ and not directly on $\mathcal{B}(E)$. This has the reason that in order to derive concentration inequalities these works use the inner product on $L^2(\pi)$. In our setting we consider an irreducible MJP with invariant distribution $\pi$ on a finite state space $E$ and we can directly identify (see Remark <ref>) $L^2(\pi) = \mathcal{B}(E)$, thus it does not depend whether we formally treat $(P_t)_{ t \geq 0}$ as a semigroup on $L^2(\pi)$ or $\mathcal{B}(E)$. Remark <ref> explains in more detail how the situation simplifies in our setting.

Using Jensen's inequality (Theorem <ref>) it can be shown (see <cit.>) that if $\pi$ is an invariant distribution of a general Markov Process $(\F{X}, (\F{P}_x)_{x \in E})$, then  $(P_t)_{ t \geq 0}$ is  a well defined contraction semigroup on $L^p(\pi)$, where well-definedness means that for an equivalence class $[f] \in L^p(\pi)$ definition (<ref>) does not depend on the member of $[f]$ (up to a $\pi$ nullset) and $\abs{P_tf}^p$ is  integrable with respect to $\pi$.

(Simplification in our setting)

More generally, if one considers a general Markov process on a Polish space $E$ (see <cit.> for a definition of a Markov process), the Banach space $\mathcal{B}(E)$ may be 'too big' and $(P_t)_{ t \geq 0}$ may not have desirable properties like strong continuity  ($\norm{P_hf -f}_\infty \xrightarrow[]{h \to 0} 0 )$. Furthermore, one may be interested in using the scalar product of $L^2(\pi)$, where $\pi$ is an invariant measure of the Markov process. Thus, in general one can consider $(P_t)_{ t \geq 0}$ on the following (real) Banach spaces (for a precise definition of these Banach spaces see <cit.>)

* $\mathcal{B}(E)$

* $\mathcal{C}_b(E)$ := { $f : E \rightarrow \F{R}$ | $f$ is bounded and continuous }

* $\mathcal{C}_0(E)$ := { $f : E \rightarrow \F{R}$ | $f$ is continuous and vanishes at infinity }

* $L^2(\pi)$,

where the spaces $\mathcal{B}(E), \mathcal{C}_b(E) $ and $\mathcal{C}_0(E)$ are endowed with the sup-norm $\norm{f}_\infty = \sup_{x \in E}\abs{f(x)} $, and $L^2(\pi)$ is endowed with the usual $L^2$-norm. In general, these spaces are not equal and not isomorphic (as Banach spaces). Consequently, in a general setting one has to be precise when referring to 'the  infinitesimal generator of the Markov process' as  Definition <ref> depends on the Banach space, on which one analyses the semigroup $(P_t)_{ t \geq 0}$. However, in our case $E$ is just a finite discrete space (endowed with the discrete topology), $\pi$ is the invariant measure of an irreducible MJP, and all above function spaces coincide in the following way.

Denote by $\F{R}^E$ the vector space of all functions $f : E \rightarrow \F{R}$. Notice that as $E$ is endowed with the discrete topology and $E$ is finite, all $f \in \F{R}^E$ are bounded, continuous and vanish at infinity. So $\F{R}^E = \mathcal{B}(E) = \mathcal{C}_b(E) = \mathcal{C}_0(E)$. Furthermore $\pi_x > 0$ for any $x \in E$ (see Theorem <ref>) so $\mathscr{L}^2(\pi) = L^2(\pi)$, where $\mathscr{L}^2(\pi)$ denotes the space of measurable $\pi$ - square integrable functions (recall that elements of $L^2(\pi)$ are equivalence classes).  But by finiteness of $E$,  for any $f \in \F{R}^E$ we have  $\sum_{x \in E} f(x)^2 \pi_x < \infty   $, so $L^2(\pi) = \mathscr{L}^2(\pi) = \F{R}^E $. Furthermore as $\F{R}^E$ is finite dimensional all norms on $\F{R}^E$ are equivalent and pointwise convergence coincides with convergence in norm: for any sequence $(f_n)_{n \in \F{N}}$ and any $f$ in $\F{R}^E$  we have $ \norm{f_n - f} \xrightarrow[]{n \to \infty } 0 $ if and only if $f_n(x) \xrightarrow[]{n \to \infty}f(x)$ for all $x \in E$ (where $\norm{\cdot }$ is some arbitrary norm). In particular, for the definition of the infinitesimal generator of $(P_t)_{ t \geq 0}$ it does not matter on which function space one considers $(P_t)_{ t \geq 0}$, and in Definition <ref> the convergence in norm may be replaced by pointwise convergence.

The above remark shows that  in our setting, where we consider an irreducible MJP on a finite set, the semigroup $(P_t)_{ t \geq 0}$ defined in  (<ref>) is  also a (well defined) semigroup  on $L^2(\pi)$ (without having to refer to Remark <ref>) as we can identify $L^2(\pi) = \mathcal{B}(E)$. Moreover, the definition of the infinitesimal generator is independent of the function space considered (on which $(P_t)_{t \geq 0}$ is defined), thus we will use the notion the infinitesimal generator of an irreducibleMJP with invariant distribution $\pi$. From now on (unless stated otherwise), $L$ always denotes the infinitesimal generator of an (irreducible) MJP. Mostly we will consider $L$, to be treated as an operator on $L^2(\pi)$, but for the rest of this work we make the identification $L^2(\pi) = \mathcal{B}(E) = \mathcal{C}_b(E) = \mathcal{C}_0(E) = \F{R}^E$, whenever needed. Using Theorem <ref>$(a)$ we can directly compute the infinitesimal generator $L$ in terms of the $Q$-matrix of the MJP. We have

Let $L$ be the infinitesimal generator and $(P_t)_{ t \geq 0} $ the semigroup of an irreducible MJP. Then, $(P_t)_{ t \geq 0}$ is a continuous contraction semigroup on $L^2(\pi)\rb$ and  $D(L)  = L^2(\pi)  = \mathcal{B}(E)$. Furthermore, for all $f \in \mathcal{B}(E)$ and all $x \in E$

\begin{equation}
\label{eq: contraction_semigroup_MJP}
(P_tf)(x) = \sum_{y \in E}p_{xy}(t) f(y)
\end{equation}

\begin{equation}
\label{eq: infinitesimal_generator_MJP}
(Lf)(x) = \sum_{y \in E}q_{xy}f(y).
\end{equation}

In other words, if $(e_x)_{x \in E}$ denotes the basis of $\mathcal{B}(E) = L^2(\pi)$ given by $e_x(y) = \delta_{xy}$, then the transformation matrices of $P_t$ and $L$ in this basis are given by $P(t)$ and $Q$, where $P(t)$ and $Q$ denote the transition function and $Q$-matrix of the MJP.

* The works <cit.>, <cit.>, <cit.>, <cit.> considered here treat $(P_t)_{ t \geq 0}$ as a contraction semigroup on $L^2(\pi)$ (for more general Markov processes than MJPs) and consequently in these works the notion of $L^2$-infinitesimal generator (defined as in Definition <ref>) is used. Note that for general Markov processes we may not have $D(L) = L^2(\pi)$.

* The above Lemma can be quite easily generalized (using a similar proof) to general (not necessarily irreducible) MJPs on a finite state space, where $\pi$ is replaced by some invariant distribution  $\mu$, and we would have the identification $L^2(\mu) = \mathcal{B}(\text{supp}(\mu))$, where $\text{supp}(\mu)$ denotes the support of $\mu$. Furthermore, in  (<ref>) and (<ref>) the summation over $x,y \in E$ would be replaced by a summation over $x,y \in \text{supp}(\mu)$.

In the following proof we will throughout use  the identification  $\mathcal{B}(E) = L^2(\pi)$ and that the convergence with respect to $\norm{\cdot}_\infty$ and $\norm{\cdot}_2$ respectively, is equivalent to pointwise convergence (Remark <ref>). Equality (<ref>) follows directly from the definitions.
Thus, using (<ref>), finiteness of $E$ and continuity of $p_{xy}(t) $ we obtain the continuity of $(P_t)_{ t \geq 0}$. Furthermore, $(P_t)_{t \geq 0}$ is a contraction semigroup, because by Jensen's inequality (Theorem <ref>) for all $f \in L^2(\pi)$ and $x \in E$ we have $(P_tf)(x)^2= \F{E}_x(f(X_t))^2 \leq \F{E}_x( f^2(X_t)) $. Thus,

\begin{equation}
\norm{P_tf}_2^2 =  \F{E}_\pi( (P_tf)^2) \leq \F{E}_\pi(f^2(X_t)) = \norm{f}_2^2,
\end{equation}

where we used that $\pi$ is a stationary distribution.
Furthermore for all $f \in \mathcal{B}(E)$  and $x \in E$ it holds

\begin{equation*}
\frac{d}{dt}\Bigr|_{t = 0}(P_tf)(x) = \frac{d}{dt}\Bigr|_{t = 0} \sum_{y \in E}p_{xy}(t)f(y) = \sum_{y \in E}\frac{d}{dt}\Bigr|_{t = 0}p_{xy}(t)f(y) = \sum_{y \in E}q_{xy}f(y),
\end{equation*}

where Theorem <ref>.1$(a)$ and finiteness of $E$ (to interchange sum and derivative) were used.
So $D(L) =  \mathcal{B}(E) = L^2(\pi)$ and (<ref>) holds.

The above lemma shows that in our setting (of an irreducible MJP) we can identify $L \; \widehat{=} \; Q$.
We will now discuss some properties of the infinitesimal generator $L$, that will be used later to derive concentration inequalities.
Let $\textbf{1} : E \rightarrow \{1 \}$ denote the constant $1$-function, and denote by $L^*$ the adjoint of the infinitesimal generator $L : L^2(\pi) \rightarrow L^2(\pi)$ of an irreducible MJP with invariant distribution $\pi$. Moreover, denote by $\langle \cdot, \cdot \rangle$ the scalar product on $L^2(\pi)$ and by $\norm{\cdot}_2$ the $L^2$ norm (for functions and operators).

Let $L$ be the infinitesimal generator of an irreducible MJP and denote by $\sigma(\cdot)$ the spectrum of an operator. Then,

* $\mathrm{Ker}(L) = \mathrm{Ker}(L+ L^*) = \mathrm{span}( \textup{\textbf{1}} )$, in particular $0$ is a simple eigenvalue.

* $\mathrm{Im}(L) = \mathrm{Im}(L + L^*) = \{ \textup{\textbf{1}} \}^{\perp}  = \{ f \in L^2(\pi) | \pi(f) = \langle \textup{\textbf{1}}, f \rangle_{L^2(\pi)} = 0 \}$

* $-L, -( L+L^*)$ are positive semidefinite.

* $\sigma(L+ L^*) \subset \F{R}_{\leq 0} $

Let $L(x,y) = (Le_y)(x) = q_{xy}$ and $L^*(x,y) = (L^*e_y)(x) $, where $(e_x)_{x \in E}$ denotes the basis given by $e_x(y) = \delta_{xy}$, i.e. $(L(x,y))_{x,y \in E}$ and $(L^*(x,y))_{x,y \in E}$ are the transformation matrices of $L$ and $L^*$ with respect to that basis. A calculation using  $\langle f, g \rangle = \sum_{x \in E} f(x)g(x)\pi_x$ and Lemma <ref>, shows  $L^*(x,y) = \frac{L(y,x) \pi_y}{\pi_x} = \frac{q_{yx} \pi_y}{\pi_x}$. Furthermore, using  invariance of $\pi$, $\sum_{y \in E} q_{xy} = 0$, $L^*(x,y) \geq 0$ for $x \neq y$, and Lemma <ref>$(d)$ it is easily checked that the matrix $\Tilde{Q}$ defined via $\Tilde{q}_{xy} = L(x,y) + L^*(x,y)$ is a $Q$-Matrix (Definition <ref>) defining an irreducible MJP  with (unique) invariant distribution $\pi$. Thus, it suffices to prove statements $(a) - (c)$ just for $L$, which we identify with the $Q$-matrix $Q$. We start by proving statement $(a)$. For all $\lambda \in \sigma(Q)$ we have $\Re \lambda \leq 0$. Indeed, by the Gershgorin disc theorem <cit.> for all $\lambda \in \sigma(Q)$ there is a $x \in E$ such that

\begin{equation*}
\abs{\lambda + q_x} =  \abs{\lambda - q_{xx}} \leq \sum_{y \neq x}q_{xy} = q_x.
\end{equation*}

It follows that

\begin{equation*}
\Re \lambda + q_x \leq  \abs{\Re \lambda + q_x} \leq \abs{ \lambda + q_x} \leq q_x
\end{equation*}

and thus

\begin{equation}
\label{eq: Real_part_eigenvalue_Q}
\text{Re} \lambda \leq 0
\end{equation}

for any $\lambda \in \sigma(Q)$. Let $ t > 0$, note that  $P(t) = \exp(tQ)$ (Theorem <ref>.1$(a)$) has spectrum $\exp(t\sigma(Q))$, which follows, for example, by using the Jordan normal form of $Q$ to calculate $\exp(tQ)$. Thus, by (<ref>)  we have $\rho(P(t)) \leq 1$, where $\rho$ denotes the spectral radius. But clearly $ 1 \in \sigma(P(t))$ (as $L\textbf{1} = 0$) so $\rho(P(t)) = 1$. By irreducibility we have    $p_{xy}(t) > 0$ for all $x,y \in E$ (Lemma <ref>), so by Perrons theorem <cit.> $1 = \rho(P(t))$ is a simple eigenvalue. As any $v \in \mathrm{Ker}(Q)$ satisfies $P(t)v = v$, this implies that $\dim \mathrm{Ker}(L) = \dim \mathrm{Ker}(Q) \leq 1$. But $L\textbf{1} = 0$ and  consequently $\mathrm{Ker}(L) = \mathrm{span}(\textbf{1})$, which is statement $(a)$. As by the rank-nullity theorem $\dim \mathrm{Im}(L) = \dim L^2(\pi)- \dim \mathrm{Ker}(L) = \dim L^2(\pi) - 1 = \dim \{ \textbf{1} \}^{\perp}$, in order to show $(b)$ it suffices to show that $\mathrm{Im}(L) \subset \{ \textbf{1} \}^{\perp}$. This follows from $\pi^TQ = 0 $. Indeed, for any $f = Lg$ we have that

\begin{equation*}
\langle \textbf{1}, f \rangle  = \langle \textbf{1}, Lg \rangle = \sum_{x \in E}\pi_x \sum_{y \in E} q_{xy}g(y) = \sum_{y \in E}g(y) \sum_{x \in E}\pi_x q_{xy} = 0,
\end{equation*}

which proves $\text{Im}(L) \subset \{\textbf{1}\}^\perp$ and thus $(b)$. To prove $(c)$, note that
for any $f \in L^2(\pi)$ we have

\begin{equation}
\langle f , P_t f \rangle \leq \norm{f}_2^2 = \langle f, P_0f \rangle,
\end{equation}

where we used the Cauchy-Schwartz inequality and the fact that $P_t$ is a contraction (see Lemma <ref> or Remark <ref>. Consequently
\begin{equation}
\langle f, Lf \rangle = \frac{d}{dt} \langle f, P_tf \rangle |_{t = 0}  \leq 0
\end{equation}

for any $f \in L^2(\pi)$, i.e. $-L$ is positive semidefinite. Finally, statement $(d)$ follows from the selfadjointness of $L+L^*$ and the negative semidefiniteness of $L+L^*$.

We finish this section by analyzing the special case if the detailed balance condition (Definition <ref>) is satisfied. We have

Let $\mu = (\mu_x)_{x \in E}$ be a probability measure on $E$ and $(\F{X}, (\F{P}_x)_{x \in E})$ an MJP. The following statements are equivalent:

* $\mu$ satisfies the detailed balance condition.

* The process $(\F{X}, \F{P}_\mu)$ is reversible i.e.

\begin{equation*}
\mathscr{L}_\mu((X_t)_{0 \leq t \leq s }) = \mathscr{L}_\mu((X_{s-t})_{0 \leq t \leq s})
\end{equation*}

for any $s \geq 0$.

* $P_t$ is $\mu$ symmetric, i.e. for all $A, B \subset E$

\begin{equation*}
\int_A (P_t 1_{B})(x) \mu(dx) = \int_B (P_t 1_A)(x) \mu(dx).
\end{equation*}

* $\mu$ is an invariant distribution and the infinitesimal generator on $L^2(\mu)$ (defined as in Definition <ref>) is selfadjoint, i.e.

\begin{equation*}
\langle Lf, g \rangle_{L^2(\mu)} = \langle f, Lg \rangle_{L^2(\mu)}
\end{equation*}

for all $f, g \in L^2(\mu)$.

We follow the proof idea of <cit.>. We show $(d) \to (c) \to (b) \to (a) \to (d)$. Assume $(d)$, then $(P_t)_{ t \geq 0}$ can be seen as a contraction semigroup on $L^2(\mu)$ (Remark <ref>) and $D(L) = L^2(\mu)$ (Remark <ref>$(b)$), so by finite dimensionality of $L^2(\mu)$ (see Remark <ref>) we have $P_t = \exp(tL)$, as  operators on $L^2(\mu)$. Consequently, by selfadjointness of $L$, $P_t$ is also selfadjoint. In particular for $A,B \subset E$

\begin{equation}
\int_A (P_t 1_{B})(x) \mu(dx) = \langle 1_A, P_t1_B \rangle_{L^2(\mu)} = \langle P_t1_A, 1_B \rangle_{L^2(\mu)} = \int_B (P_t 1_A)(x) \mu(dx),
\end{equation}

which proves $(c)$. Now assume $(c)$ and let $P(t) = (p_{xy}(t))_{x,y \in E}$ denote the transition function of the MJP, then in particular (set $A = \{x \}, B = \{y\}$)

\begin{equation}
\label{eq: detailed_balance_p_t}
\mu_x p_{xy}(t) = \mu_y p_{yx}(t).
\end{equation}

Note that by summing over $y \in E$, this implies invariance of $\mu$, in particular $\mu = \mathscr{L}_\mu (X_t)$ for all $t \geq 0$.
As finite dimensional distributions uniquely determine the distribution of a stochastic process, to show $(b)$ it is sufficient to show that  for all $n \in \F{N}$ all $x_1,...,x_n \in E$ and all $0 \leq t_1 .... \leq t_n \leq s$

\begin{equation}
\F{P}_\mu(X_{t_1} = x_1,..., X_{t_n} = x_n) = \F{P}_\mu ( X_{s - t_n } = x_n,...., X_{s - t_1} = x_1 ),
\end{equation}

which is equivalent to (we use (<ref>) and invariance of $\mu$)

\begin{equation}
\mu_{x_1} p_{x_1x_2}(t_2-t_1) ... p_{x_{n-1}x_n}(t_n-t_{n-1}) =  \mu_{x_n} p_{x_nx_{n-1}}(t_n - t_{n-1}) ... p_{x_2x_1}(t_2 - t_1) .
\end{equation}

But the above equality follows from applying repeatedly  (<ref>) with $x = x_j, y = x_{j+1}$ for $j = 1,...,n-1$ (from left to right). Assume $(b)$, then  in particular $\mu$ is invariant (as $(\F{X},\F{P}_\mu)$ is strongly stationary), and for all $s \geq 0$, $x,y \in E$

\begin{equation}
\mu_x p_{xy}(s) = \F{P}_\mu(X_0 = x, X_s = y) = \F{P}_\mu( X_s = x, X_0 = y) = \mu_y p_{xy}(s).
\end{equation}

Thus, taking the derivative at $s = 0$ yields the detailed balance condition $(a)$. Finally, assume $(a)$. In particular, $\mu$ is an invariant distribution. Denote by $\text{supp}(\mu)$ the support of $\mu$ and let $f,g \in L^2(\mu)$. By Lemma <ref> and Remark <ref> we have  (using the detailed balance condition $(a)$)

\begin{equation}
\langle f, Lg \rangle_{L^2(\mu)} = \sum_{x,y \in \text{ supp}(\mu)} f(x) g(y) \mu_x q_{xy} = \sum_{x, y \in \text{ supp}(\mu)} g(y) f(x) \mu_y q_{yx} =  \langle Lf, g \rangle_{L^2(\mu)},
\end{equation}

which proves self adjointness of $L$.

The equivalence of the above statements is not explicitly used in this work. However, since the works <cit.>, <cit.>, <cit.>, <cit.>  use (equivalent) notions of  'reversible' and 'symmetric' Markov processes, we decided to include the above lemma in order to clarify  these notions.

§.§.§ Limit Behavior

We present here two central theorems that describe the limit behavior of an irreducible MJP. In this thesis we focus mainly on the ergodic theorem, the central limit theorem serves as background information, as for reversible MJPs the so called asymptotic variance (see Theorem <ref>) will appear as a parameter in a bound of $\mathbb{P}( \frac{1}{t}\int_{0}^{t}f(X_t)dt  \geq u)$.

Let $(\F{X}, (\F{P}_x)_{x \in E})$ be an irreducible MJP with unique invariant distribution $\pi$ and let $f \in \mathcal{B}(E)$. Then for any probability measure $\nu$ on $E$

\begin{equation}
\frac{1}{t}\int_0^t f(X_s) ds \xrightarrow[]{t \to \infty} \pi(f)
\end{equation}

$\F{P}_\nu $ almost surely, where $\pi(f) = \int_E f d\pi$.

Follows from <cit.>. The requirement of <cit.> that $\F{X}$ is ergodic is satisfied (see <cit.> for a definition of ergodicity) because of <cit.> and the alternative characterization (<ref>) of invariance of $\pi$.

* Note that the ergodic theorem is a asymptotic result which does not state anything about the rate of convergence or the deviation probability $\F{P} \left( \abs{\frac{1}{t}\int_0^t f(X_s) ds - \pi(f) } \geq u \right)$.

* There are more general versions of the above theorem considered in the context of so called ergodic theory. In the the context of ergodic theory a general probability space $(\mathcal{X}, \mathcal{A}, \F{P})$ with a product measurable map $\Theta : [0,\infty) \cross \Omega \rightarrow \Omega $, satisfying $\Theta_0 = \text{Id}_\Omega$ and $\Theta_t(\omega)\Theta_s(\omega) = \Theta_{s+t}(\omega)$ is considered (see <cit.> for details). Then for any $F \in L^p(\Omega, \mathcal{F}, \F{P})$ (c.f. <cit.>)

\begin{equation}
\frac{1}{t}\int_0^t F \circ \Theta_s ds \xrightarrow[]{t \to \infty} \F{E}(F | \mathcal{I}),
\end{equation}

$\F{P}$ - almost surely and in $L^p$, where $\mathcal{I} = \{ A \in \mathcal{A} | \Theta_t^{-1}(A) = A \text{ for all $t \geq 0$} \}$ is the $\sigma$-algebra of invariant sets.
In our context $\mathcal{X}$ can be chosen to be the space of right continuous functions $(x_t)_{t \geq 0} : \F{R}_{\geq 0} \rightarrow E$, $\mathcal{A}$ is the $\sigma$-Algebra generated by the evaluation maps $(x_t)_{t \geq 0} \mapsto x_s $ for $s \geq 0$, $\F{P}$ is defined by $\F{P}(A) = \F{P}_\pi (\F{X} \in A)$ (where $(\F{P}_\pi, \F{X})$ is an MJP with invariant distribution $\pi$) and $F((x_t)_{t \geq 0}) = f(x_0)$.

Let $\F{X}$ be an irreducible MJP with stationary initial distribution $\pi$ and $f \in L^2(\pi)$ with $\pi(f) = 0$. Then

\begin{equation}
\frac{1}{\sqrt{t}} \int_0^t f(X_s) ds  \xrightarrow[]{\mathcal{D}} \mathcal{N}(0, \sigma^2),
\end{equation}

\begin{equation}
\sigma^2 = - 2\langle g, Lg \rangle = - 2 \langle g, f \rangle ,
\end{equation}

for (all) $g \in L^2(\pi)$ with $Lg = f$. Furthermore, if $\F{X}$ is reversible then $\sigma^2$ is called asymptotic variance and

\begin{equation}
\label{eq: asymptotic variance}
\sigma^2  = -2 \langle Sf, f \rangle  = \lim_{t \to \infty}t^{-1}\mathrm{Var}_\pi\left ( \int_0^tf(X_s) ds \right ),
\end{equation}

where $S$ is the reduced resolvent of $L$ with respect to the eigenvalue $0$.

Note that as $0 = \pi(f) = \langle f, \textbf{1} \rangle$ by Lemma <ref> $f \in \text{Im}(L)$. So the first statement follows by
<cit.>. The second statement follows by applying the first statement with $g = Sf$ and <cit.>

The reduced resolvent is defined in Section <ref>

§.§ Additional Tools

In this short Section we provide additional notions and tools used later to derive concentration inequalities. In Section <ref> we present the concept of Fenchel conjugate; an important concept which will be used throughout the main part  of this work. Hereby, we also consider an important example (Example <ref>) which is relevant later for Bernstein-type concentration inequalities (see Lemma <ref>). In Section <ref> we present some formulas and identities of linear algebra and perturbation theory, that will be needed later in the context of the vector space $L^2(\pi)$ ($\pi $ is the invariant distribution of an irreducible MJP). Here, we also define the concept of reduced resolvent and present a result about the perturbation of a simple eigenvalue.

§.§.§ Fenchel Conjugate

Later, when deriving concentration inequalities with the Cramér-Chernoff method, we shall need the notion of the so called Fenchel conjugate. This section is based on <cit.>. In the following we always use the convention $r \pm \infty = \pm \infty$ for all $r \in \F{R}$. We define (c.f. <cit.>)

(Fenchel conjugate)

Let $D \subset \F{R}$ and $F : D \rightarrow [-\infty, \infty]$ be a function. Define $F^* : \F{R} \rightarrow [-\infty, \infty]$ as

\begin{equation}
F^*(u) := \sup_{r \in D}(ru - F(r))
\end{equation}

We call $F^*$ the Fenchel conjugate of $F$ (with respect to $D$).

Furthermore, as we will work with functions that may possibly attain the value $\infty$, we clarify the notion of convexity. We define  (c.f. <cit.>)

We say a function $F : D \rightarrow (-\infty, \infty]$ is convex if

\begin{equation}
\label{eq: def_convexity}
F(s_1 r_1 + s_2 r_2) \leq s_1 F(r_1) + s_2 F(r_2)
\end{equation}

for all $r_1, r_2  \in \{ F < \infty \}$ and all $s_1, s_2 \geq 0$ such that $s_1 + s_2 = 1$, where we define $F(r) := \infty $ for $r \not \in D$.

* If $F$ is convex, then $F^*$ is also called the Legendre transform.

* In <cit.> the Fenchel conjugate is defined for functions $F : \F{R} \rightarrow \F{R}$, i.e. $D = \F{R}$. However, for our purposes we want to take Fenchel conjugates with respect to subsets $D \subset \F{R}$ (e.g. in Example <ref>) and thus we use the above Definition <ref>.

Let $D,D' \subset \F{R} $ be some subsets with $D' \subset D$ and let  $F: D \rightarrow (-\infty, \infty]$, $G : D' \rightarrow (-\infty, \infty]$ be some functions. Then, the following statements hold

* $F^*$ is convex.

* Suppose that $D = [a,b]$ for some $a <  b$, $F$ is continuous, and continuously differentiable on $(a,b)$ with strictly increasing derivative $F'$. Then,

\begin{equation}
F^*(u) = u \cdot (F')^{-1}(u) - F((F')^{-1}(u))
\end{equation}

for all $u \in F'((a,b))$.

* Fenchel Biconjugation TheoremSuppose that $D$ is a closed set, and $F$ is convex and lower semicontinuous on $D$. Hereby, lower semicontinuity means that

\begin{equation}
\liminf_{n \to \infty } F(r_n) \geq F(r)
\end{equation}

for all $r \in D$ and all sequences $(r_n)_{n\in \F{N}}$ converging to $r$.

\begin{equation}
F^{**} = F\;,
\end{equation}

where the convention $F(r) = \infty $ if $r \not \in D$ is used.

* If $F \leq G$ on $D'$, then $ F^* \geq G^*$

In this work we will only make direct use of part $(c)$ and $(d)$, part $(a)$ and $(b)$ are included for completeness.

Statements $(a),(d)$ are standard results found in <cit.>  and  $(b)$ follows from an elementary calculation , so we just show $(c)$. Let $F$ be  convex and lower semicontinuous on $D$.
Extend $F$ to $F : \F{R} \rightarrow [- \infty, \infty]$ by defining $F(r) = \infty$ whenever $r \not \in D$. Note that the Fenchel conjugate is remains unchanged by this extension, because

\begin{equation}
\sup_{ r \in D}(ru - F(r)) = \sup_{ r \in \F{R}}(ru - F(r))
\end{equation}

by the convention $ru - \infty = -\infty$.
Furthermore it is straightforward to check that  $F : \F{R} \to (-\infty, \infty ]$ is  lower semicontinous (follows from the closedness of $D$) and convex on $\F{R}$ (follows from Definition <ref>). Consequently, by the Fenchel-Biconjugation theorem <cit.>

\begin{equation*}
F = F^{**}.
\end{equation*}

Finally, it should be remarked that although <cit.> requires that $F$ is closed (see <cit.> for a definition), this requirement is equivalent to lower semi-continuity of $F$ (see <cit.>).

The following example of a Fenchel conjugate will become important later, when we treat sub-gamma random variables (see Definition <ref>).
Let $v,c > 0$ and define

\begin{equation}
F(r) := \frac{r^2v}{2(1-rc)}
\end{equation}

for $r \in [0, \frac{1}{c})$. Let $u \geq  0$ ,

\begin{equation}
r_0 := \frac{1}{c} \left ( 1-  \left ( 1 + \frac{2 u c}{v} \right )^{-\frac{1}{2}} \right)
\end{equation}

\begin{equation}
H(r) := ru - F(r)
\end{equation}

for $r \in [0, \frac{1}{c})$. Then $H'$ has a unique root in $[0, \frac{1}{c})$, which is given by $r_0$ and  $H'' < 0$ on $[0, \frac{1}{c})$. Consequently

\begin{equation}
\label{eq: Legendre_transform_subgamma}
F^*(u) = \sup_{r \in [0, \frac{1}{c})} H(r) =  H(r_0) = \frac{v}{c^2}\left (1 + \frac{uc}{v} - \sqrt{1 + \frac{2uc}{v}} \right)  = \frac{2u^2}{v(1+ \sqrt{1 + \frac{2uc}{v}})^2}
\end{equation}

for all $u \geq 0$.

That $H'$ has a unique root on $[0, \frac{1}{c})$, given by $r_0$ and $H'' < 0$ is checked by an elementary calculation. Thus, it follows that $H$ reaches at $r_0$ a unique maximum on $[0,\frac{1}{c})$ , and consequently

\begin{equation}
\sup_{r \in [0, \frac{1}{c})} H(r) =  H(r_0) = \frac{v}{c^2}\left (1 + \frac{uc}{v} - \sqrt{1 + \frac{2uc}{v}} \right)  = \frac{2u^2}{v(1+ \sqrt{1 + \frac{2uc}{v}})^2} ,
\end{equation}

where the last two equalities may also be checked by elementary calculations (c.f. <cit.>).

§.§.§ Linear Algebra and Perturbation Theory

In the following (unless otherwise stated) let $V$ denote a vector space and $H$ a   Hilbert space. All vector spaces are assumed to be real and finite dimensional. Denote by $\langle \cdot , \cdot \rangle$ the inner product on $H$ and by $\norm{\cdot}$ the induced norm (for vectors and operators). We call a linear map $T: V \rightarrow V$ an operator on V. This section is mainly based on Appendix <ref>, which considers a setting of complex vector spaces. However, we consider just real vector spaces as in our context later we will just work with the real vector space  $V = H = L^2(\pi)$ ($\pi$ is the invariant measure of an irreducible MJP). Furthermore, as an extensive rigorous presentation and proof of some of the corresponding results (in the case of complex vector spaces) is long and involves technicalities which are not important for our purposes, the more detailed and general presentation is found in Appendix <ref>.

Let $T : H \rightarrow H$ be a selfadjoint operator. Then, the largest eigenvalue $\lambda_0$ is given by

\begin{equation*}
\lambda_0  = \max  \left \{ \frac{\langle Tv, v \rangle }{\norm{v}^2} \middle | v \in H, v \neq 0 \right \}.
\end{equation*}

It is a well known fact that any selfadjoint operator on $H$ is orthogonally diagonalizable (see <cit.>) with real eigenvalues, so let $(e_i)_{i = 1,...n}$ be an orthonormal basis of $H$, diagonalizing $T$ with corresponding eigenvalues $\lambda_i \in \F{R}$. The statement follows directly by using

\begin{equation}
\langle Tv, v \rangle = \sum_{i = 1}^n\lambda_i v_i^2,
\end{equation}

where $v = \sum_{i=1}^n v_i e_i$.

(Reduced resolvent)

Let $T: V \rightarrow V$ be a diagonalizable operator (with real eigenvalues) and $\sigma(T)$ denote the spectrum. For $\lambda \in \sigma(T)$ let $\text{pr}_\lambda$ denote the eigenprojection onto the eigenspace $\text{Ker}(T-\lambda)$ according to the decomposition $V = \bigoplus_{ \lambda \in \sigma(T)} \text{Ker}( T - \lambda )$. For $\lambda \in \sigma(T)$ define an operator $S_\lambda$ by

\begin{equation}
\label{eq: reduced_resolvent}
S_\lambda v =
\begin{cases}
(T - \lambda)|_{ \mathrm{Im}(1- \text{pr}_\lambda)}^{-1}v  \;; \; v \in \mathrm{Im}(1 - \text{pr}_\lambda) \\
0 \;;\; v \in \mathrm{Im}(\text{pr}_\lambda)
\end{cases}
\end{equation}

$S_\lambda$ is called the reduced resolvent of $T$ (with respect to $\lambda$).

Note that $S_\lambda$ is well defined. Indeed, this is easily seen by writing $T = \sum_{\mu \in \sigma(T)} \mu \text{pr}_\mu $, then an elementary calculation shows that Definition <ref> is equivalent to

\begin{equation}
S_\lambda = \sum_{ \mu \in \sigma(T)\backslash \{\lambda \}} \frac{\text{pr}_\mu}{\mu - \lambda }
\end{equation}

We just consider the reduced resolvent of a diagonalizable operator as we will just work with the reduced resolvent of the selfadjoint, diagonalizable operator $\frac{L+L^*}{2}$ ($L$ is the infinitesimal generator of an (irreducible) MJP). See Appendix <ref> for a more extensive presentation of reduced resolvents.

Perturbation theory is a widely used tool  that enables the calculation of eigenvalues and eigenvectors of a perturbed operator of the form

\begin{equation*}
T (r) = T + r T',
\end{equation*}

where $r \in \F{R}$ is some 'small' parameter. More generally, one can consider an analytic operator valued function $T(r) = \sum_{n=0}^\infty r^n T^{(n)}$ and ask how the eigenvalues  of $T(r)$ may be computed in terms of $( T^{(n)} )_n$ and $r$. We now give two results (Lemma <ref> and Theorem <ref>) about the eigenvalues of $T(r)$. These results follow from the corresponding results  in the case of complex vector spaces (Lemma <ref> and Theorem <ref>). The results of Appendix <ref> transfer to our setting of real vector spaces essentially by applying these results to the complexification  (c.f. Lemma <ref>) of the vector spaces and operators.

Let $T(r)$ be a continuous operator-valued function on $V$defined on some interval $I \subset \F{R}$. Furtheremore, let $N = \dim V$. Then, there are continuous functions $\lambda_k : I \rightarrow \F{C}$, $k = 1,...,n$ such that the $N$-tuple

\begin{equation*}
(\lambda_1(r), ... , \lambda_N(r)).
\end{equation*}

represents the eigenvalues of $T(r)$, where the eigenvalues are repeated according to their algebraic multiplicity.

Follows from the corresponding complex version Lemma <ref>. For a more detailed explanation see Remark <ref>.

Let $T : H \rightarrow H$ be a self adjoint operator. Assume that $0$ is a simple eigenvalue of $T$. Let $\lambda_1 := \min_{\lambda \in \sigma(T) \backslash \{0\}} \abs{\lambda}$ be the spectral gap, $\mathrm{pr}$ the orthogonal projection onto the eigenspace with eigenvalue $0$ and $S = S_0$ the corresponding reduced resolvent. Furthermore, let $ T' : H \rightarrow H$ be some operator and define $ T(r) := T + r T'$ for $r \in \F{R}$. Then for all $\abs{r} < \frac{\lambda_1}{2 \norm{T}}$ the ball  $B_{\frac{\lambda_1}{2}}(0) \subset \F{C}$  contains exactly one simple eigenvalue $\mu_0(r)$ of $T(r)$ and we have

\begin{equation}
\label{eq: mu_0(r)}
\mu_0(r) = \sum_{n = 1}^\infty \mu_0^{(n)}r^n,
\end{equation}

\begin{equation}
\mu_0^{(n)} =  \frac{(-1)^n}{n} \sum\limits_{\substack{k_1,..k_n \in \F{Z}_+ \\ k_1 + ... k_n = n-1}} \Tr( T'S^{(k_1)} ... T'S^{(k_n)}),
\end{equation}

\begin{equation}
S^{(0)} = - \mathrm{pr} \quad \text{and} \quad S^{(k)} = S^k
\end{equation}

for $ k \geq 1$.

Follows from the corresponding complex analogue <ref>. For a detailed transfer to the real setting see Remark <ref>.

§ CONCENTRATION INEQUALITIES

§.§ Outline and Goal

The ergodic theorem (Theorem <ref>) states that for an irreducible  MJP $(X_t)_{t \geq 0}$ with invariant distribution $\pi$ and any initial distribution $\nu$

\begin{equation}
\label{eq: ergodic_jump}
\frac{1}{t}\int_{0}^{t}f(X_t)dt \xrightarrow[]{t \rightarrow \infty} \pi(f)  \quad \mathbb{P}_\nu \text{ - a.s.}
\end{equation}

holds for any $f \in \mathcal{B}(E)$.
The main goal of this section will be to give bounds for the deviation of the (finite) time average in the above equation from the long term limit $\pi(f)$ for irreducible MJPs. In more precise mathematical terms: For any $t >0 $ we want to bound the tail probabilities

\begin{equation}
\label{eq: probability_deviation}
\mathbb{P}_\nu \left (\frac{1}{t}\int_{0}^{t}f(X_s)ds - \pi(f)  \geq u \right )
\end{equation}

for $u \geq 0$,

\begin{equation}
\label{eq: lower_tail}
\mathbb{P}_\nu \left (\frac{1}{t}\int_{0}^{t}f(X_s)ds - \pi(f)  \leq  u \right )
\end{equation}

for $u \leq 0$, in terms of some function of $u$. Since we consider a general $f \in \mathcal{B}(E)$ and the replacement of $f$ by $-f$ in the upper tail probability (<ref>) yields the lower tail probability  (<ref>) we consider without loss of generality just the upper tail probability (<ref>). To derive concentration inequalities for this probability  we will apply the Cramér-Chernoff method, a method that can be quite generally used to bound upper tail  probabilities

\begin{equation}
\F{P}( Z \geq u).
\end{equation}

This section consists of two main parts —Section <ref> and Section <ref>. First, the general Cramér-Chernoff method is introduced in Section <ref>.   Here, the most important results are the Chernoff inequality and the application of it, which is the basis for all concentration inequalities of this thesis, and  Bernstein's inequality, which is an example of Chernoff's inequality. In the second part —Section <ref>, based on the established Cramér-Chernoff method, we derive concentration inequalities for (irreducible) MJPs. Hereby, we summarize and combine results of the works <cit.>, <cit.>, <cit.>, and  <cit.>, which  use the Cramér-Chernoff method to derive concentration inequalities for (<ref>). More precisely, in Section <ref> we apply directly the Cramér-Chernoff method to the setting of MJPs and obtain a general concentration inequality (see Theorem <ref>). Then, in Sections <ref> - <ref> based on this general concentration inequality we derive more explicit concentration inequalities using three different approaches:  perturbation theory (Section <ref>), functional inequalities (Section <ref>) and information inequalities (Section <ref>).

Finally, some reading advice: Throughout Section <ref> we will make use of (certain) results, which are presented in Section <ref>. Thus, we pointed out at the beginning of many (sub)sections the most relevant results and notions of Section <ref> (and also Section <ref>) used, so that the reader might have again a look at the mentioned results, before engaging with the material of the subsection. Furthermore, throughout Section <ref> we will explain connections and give references to the works <cit.>, <cit.>, <cit.> and <cit.>, which are denoted by Reference. These remarks are not essential for the content and can be skipped if the reader is not interested in putting this work into the context of <cit.>, <cit.>, <cit.>, <cit.>.

§.§ Cramér-Chernoff Method

The Cramér-Chernoff method is a very general way of bounding tail probabilities of the form $ \F{P}(Z \geq u) $. The bounds represent 'exponential' decay inequalities and are usually sharper than  polynomial decay inequalities, like the Chebychev inequality. Furthermore, the  Cramér-Chernoff method is the starting point to derive many concentration inequalities (c.f. <cit.>) e.g. Hoeffding's inequality, Bernstein's inequality, and Benett's inequality, which are applicable in large deviation theory (c.f. <cit.>), learning theory  (c.f. <cit.>), randomized algorithms (c.f. <cit.>) to name but a few, and in this work the Cramér-Chernoff method is the basis for all concentration inequalities derived.

In this section we first derive the Cramér-Chernoff method by motivating it via the optimization of the Markov inequality and we arrive at a general concentration inequality; Chernoff's inequality. Then, we explain how the method may be used to derive more explicit concentration inequalities and consider an important example; Bernstein's inequality. Finally, we also briefly discuss the application of the method to sums of i.i.d. random variables. The most relevant notion of Section <ref> is the Fenchel conjugate (defined in Section <ref>).

§.§.§ Motivation

In the following  assume that all random variables in this section are defined on an underlying probability space $(\Omega, \mathcal{F}, \F{P})$. Recall two well known basic inequalities:

Let $H : D \rightarrow [0,\infty)$ be a nondecreasing nonnegative function, where $D \subset \F{R} $ is some measurable subset. Let $Z$ be a $D$-valued random variable. Then for all $u \in D$ such that $H(u) > 0$

\begin{equation}
\label{eq: markov_inequality}
\F{P}(Z \geq u) \leq \frac{\F{E}(H(Z))}{H(u)}.
\end{equation}

As $H$ is nondecreasing and nonnegative we have

\begin{equation*}
H(u)1_{\{ Z \geq u\}} \leq H(Z) 1_{\{ Z \geq u\}} \leq H(Z).
\end{equation*}

Taking the expectation on both sides and then dividing by $H(u)$ yields the statement.

Let $I \subset \F{R}$ be some interval and $Z$ an $I$-valued random variable with $\F{E}(\abs{Z}) < \infty$. Furthermore let $H: I \rightarrow \F{R}$ be some convex function. Then $\F{E}(H(Z)^{-}) < \infty$ and

\begin{equation*}
\F{E}(H(Z)) \geq H(\F{E}(Z)),
\end{equation*}

where $H(Z)^{-} = \max(0, - H(Z))$ denotes the nonpositive part of $H(Z)$.

See <cit.>.

Although the Markov inequality is quite simple, we can use it to obtain sharper bounds on the tail probability $\F{P}(Z \geq u)$ as follows. Let $(H_r)_{r \in I} $ be a family of nondecreasing nonnegative functions (defined on a common domain), parametrized by some parameter $r \in I$, where $I$ is some index set. Suppose that $H_r(u) > 0$ for any $r $, so that the Markov inequality implies

\begin{equation}
\F{P}(Z \geq u) \leq \frac{\F{E}(H_r(Z))}{H_r(u)}
\end{equation}

for all $H_r $. Then, we can optimize  the bound in the Markov inequality  by minimizing over $r \in I$, i.e.

\begin{equation}
\label{eq: Markov_minimum_tail}
\F{P}(Z \geq u) \leq \inf\limits_{r \in I} \frac{\F{E}(H_r(Z))}{H_r(u)}.
\end{equation}

The Cramér-Chernoff method consists of applying this principle using the family $H_r(u) =e^{r u}$ for $r \geq 0 $. This family  has a useful property: Notice that for all $u_1,...,u_n \in \F{R}$ we have $H_r(u_1 + ... + u_n) = H_r(u_1) H_r(u_2)...H_r(u_n)$, so if $Z_1,...Z_n$ are i.i.d.  then the bound in (<ref>) for $Z = Z_1 + ... + Z_n$ factorizes via $\F{E}(H_r(Z) ) = \F{E}(H_r(Z_1))^n $.

§.§.§ General Cramér-Chernoff Method

The following presentation of the Cramér-Chernoff method is based on <cit.>.
The Cramér-Chernoff method gives the optimal bound for the tail probability $\F{P}(Z \geq u)$ that can be obtained by minimizing the Markov inequality over the family $H_r(u) =e^{r u}$ for $r \geq 0$ as in  (<ref>).  In the following we use the conventions $\log(\infty) = \infty$, $\exp(-\infty) = 0$, $\exp(\infty) = \infty $ , $r \cdot \infty = \infty $ for any $r \in \F{R}\backslash \{0\}$, $r \pm \infty = \pm \infty $ for any $r \in \F{R}$ and $\infty^n = \infty$ for any $n \in \F{N}$. This avoids having to make a case distinction whether $\F{E}(e^{rZ}) = \infty$. The Cramér-Chernoff method is summarized in the following theorem:

Let Z be a  random variable and  $u \in \F{R}$. Furthermore, let $\Psi_Z(r) := \log \F{E}(e^{r Z})$ for $r \in \F{R}$ be the cumulant generating function and  $\Psi_Z^*(u) := \sup \limits_{r \geq 0}(r u - \Psi_Z(r))$ the Fenchel conjugate with respect to $\F{R}_{\geq 0}$. Then, Chernoff's inequality

\begin{equation}
\label{eq: Chernoff_inequality}
\F{P}(Z \geq u) \leq e^{-\Psi_Z^*(u)}
\end{equation}

holds. If furthermore $\F{E}(Z)$ exists and $ u \geq \F{E}(Z)$, then

\begin{equation*}
\Psi_Z^*(u) = \sup \limits_{r \in \F{R}}(u r - \Psi_Z(r)).
\end{equation*}

* Note that we always have $\Psi_Z^*(u) \geq 0 \cdot u - \Psi_Z(0) = 0$, so the bound in Chernoff's inequality is always $\leq 1$.

* Chernoff's inequality is trivial whenever $\Psi_Z^*(u) = 0$. If $\F{E}(Z) $ exists this happens for $u \leq \F{E}(Z)$, because then by Jensen's inequality (Theorem <ref>) we have that $r \F{E}(Z) \leq \Psi_Z(r)$  and consequently $ur - \Psi_Z(r) \leq 0$ for any $r \geq 0$. Furthermore, if $\F{E}(e^{r Z}) = \infty$ for all $ r > 0$, then also $\Psi_Z^*(u) = 0$.

Chernoff's inequality can be proved via Markov's inequality as already described in Section <ref>.
Applying Markov's inequality  with   $u \mapsto e^{ur}$ yields

\begin{equation*}
\F{P}(Z \geq u) \leq e^{-r u} \F{E}(e^{r Z}) = e^{-(ru - \Psi_Z(r))}
\end{equation*}

for all $r \geq 0$. Taking the infimum yields

\begin{equation*}
\F{P}(Z \geq u) \leq  \inf_{r \geq 0} e^{- (ru - \Psi_Z(r))} = e^{\inf_{r \geq 0}- (ru - \Psi_Z(r))} = e^{- \sup_{r \geq 0}(ru - \Psi_Z(r))} = e^{-\Psi_Z^*(u)},
\end{equation*}

where in the first equality the infimum can be pulled into the exponential function, as the  exponential function is nondecreasing and continuous.
If $\F{E}(Z)$ exists, then by the convexity of the exponential function and Jensen's inequality, for all $r \in \F{R}$ it holds that $e^{r \F{E}(Z)} \leq \F{E}(e^{rZ})$ and thus $ r \F{E}(Z)  \leq \Psi_Z(r)$. But then for any $r \leq 0$ and $u \geq \F{E}(Z)$ it holds that

\begin{equation*}
r u - \Psi_Z(r) \leq r \F{E}(Z) - \Psi_Z(r) \leq 0.
\end{equation*}

But $\Psi_Z^*(u) \geq 0\cdot u - \Psi_Z(0) = 0$, so $\Psi_Z^*(u) = \sup \limits_{r \in \F{R}}( r t - \Psi_Z(r))$ for any $ u \geq \F{E}(Z)$.

The Fenchel conjugate $\Psi_Z^*$ is called the Cramér transform of $Z$.
In other words, the Cramér-Chernoff method consists of computing the Cramér transform $\Psi_Z^*$ and then applying Chernoff's inequality.
In general, the cumulant generating function $\Psi_Z$ is not directly computable (as in the exact distribution of $Z$ is not known or too complicated) and thus the Cramér transform $\Psi_Z^*$ cannot be computed explicitly. However, the following lemma describes a method on how more explicit concentration inequalities can be obtained. We have

Let $D \subset \F{R}_{\geq 0}$ and $\Phi : D \rightarrow \F{R}$ some function such that

\begin{equation}
\Psi_Z(r)\leq \Phi(r)
\end{equation}

for all $r \in D$, and denote by $\Phi^*$ its Fenchel conjugate with respect to $D$. Then, $\Psi_Z^* \geq \Phi^*$ and consequently

\begin{equation}
\label{eq: concentration_inequality_with_Phi}
\F{P}(Z \geq u) \leq e^{-\Psi_Z^*(u)} \leq e^{-\Phi^*(u)}.
\end{equation}

for all $u \in \F{R}$

The bound $\Psi_Z \leq \Phi$ (on $D$) implies by Lemma <ref>$(d)$ $\Psi_Z^*(u) \geq \Phi^*(u)$ for all $u \in \F{R}$. Thus, (<ref>) follows directly by Chernoff's inequality

For applications $\Phi$ must be such that $\Phi^*$ can be computed. The following example of a bound $\Phi$ will be relevant for our later discussion. We define (c.f.<cit.>) :

We call a random variable $Z$ sub-gamma (on the right tail) with variance factor $v$ and scale parameter $c$ if

\begin{equation}
\Psi_Z(r) \leq \frac{r^2v}{2(1-cr)}
\end{equation}

for all $0 \leq r < \frac{1}{c}$.

We will show later that for an irreducible MJP the integral
$\int_0^t (f(X_s) - \pi(f)) ds$ is sub-gamma (on the right tail) with respect to stationary initial conditions, i.e. with respect to $\F{P}_\pi$. For details see Remarks <ref>$(b)$ and <ref>$(a)$.

As an immediate consequence of Lemma <ref>  we obtain for sub-gamma random variables the concentration inequality, which will appear later again (e.g. in Theorems <ref>, <ref>).

Suppose $Z$ is sub-gamma on the right tail with variance factor $v$ and scale parameter $c$. Then,

\begin{equation}
\label{eq: Bernstein_inequality}
\F{P}(Z \geq u) \leq \exp(-\frac{v}{c^2}\left (1 + \frac{uc}{v} - \sqrt{1 + \frac{2uc}{v}} \right))  = \exp(-\frac{2u^2}{v(1+ \sqrt{1 + \frac{2uc}{v}})^2})
\end{equation}

for all $ u \geq 0$.

This follows immediately by Lemma <ref> with $\Phi(r) = \frac{r^2v}{2(1-cr)}$ and Example <ref>.

It should be remarked that although the works considered here (i.e.  <cit.>, <cit.>, <cit.>, <cit.>) do not all explicitly mention or state the Cramér-Chernoff method, all these works are based on the Cramér-Chernoff method as follows. To prove <cit.> (concentration inequality in <cit.>) Wu <cit.>  refers to the Cramér-Theorem (see <cit.>) and then uses it in <cit.>. Furthermore, the works <cit.> and <cit.> are based on <cit.> (which is based on the Cramér-Chernoff method) and refer to it (see <cit.> and <cit.>). Finally, Lezaud <cit.> does not directly refer to <cit.> but to prove his concentration inequality <cit.> he proceeds as in the proof of the Cramér-Chernoff method (Theorem <ref>) as follows. His proof is based on  the Markov inequality

\begin{equation}
\F{P}_\nu \left( \frac{\int_0^t f(X_s)ds }{t} - \pi(f)  \geq u \right)  \leq e^{-tu r} \F{E}_\nu \left( e^{r(t^{-1}\int_0^t f(X_s)ds - \pi(f))} \right)
\end{equation}

which is a reformulation of <cit.> (using (<ref>)). Then, he derives further upper bounds of the above Markov inequality (see <cit.>) before finally computing a Fenchel conjugate by maximizing (see <cit.>) a function of the form

\begin{equation}
r \mapsto ru - F(r).
\end{equation}

Thus, our presentation here, which emphasizes the Cramér-Chernoff method, is a reformulation of the proofs and results contained in these works, which puts these results on a common footing.

§.§.§ Cramér-Chernoff Method for Sums of independent Variables

As already mentioned in Section 3.3.1, for $H_r(u) = e^{r u}$ and $Z_1,...,Z_n$ i.i.d.,  we have that $\F{E}(H_r(Z_1+...+Z_n)) = \F{E}(H_r(Z_1))^n $, so Chernoff's inequality generalizes quite easily to sums of i.i.d. random variables. More precisely we have the following corollary.

Let $Z_1,...Z_n$ be i.i.d. random variables and define $ Z := \sum_{i=1}^n Z_i$. Then, the Cramér transform $\Psi_Z^*$ of $Z$ is given by

\begin{equation*}
\Psi_Z^*(u) = n\Psi_{Z_1}^*\left( \frac{u}{n} \right),
\end{equation*}

where $u \in \F{R}$ and $\Psi_{Z_1}^*$ is the Cramér transform of $Z_1$. Consequently,

\begin{equation}
\label{eq: chernoff_for_iid}
\F{P}( Z \geq u) \leq e^{-n \Psi_{Z_1}^*(\frac{u}{n})}.
\end{equation}

As $Z_1,...,Z_n$ are i.i.d. we have

\begin{equation*}
\Psi_Z(r ) = \log ( \F{E}\left(\prod_{i=1}^n  e^{r  Z_i} \right)) = \log (\F{E}(e^{r  Z_1})^n) = n\Psi_{Z_1}(r ),
\end{equation*}

\begin{equation*}
\Psi_Z^* (u)=    \sup \limits_{r \geq 0}  ( r u - \Psi_Z(r)) = \sup \limits_{r \geq 0}  n \left (r \frac{u}{n}- \Psi_{Z_1}(r) \right) = n\Psi_{Z_1}^*\left (\frac{u}{n} \right).
\end{equation*}

Finally, the inequality (<ref>) follows by an application of Chernoff's inequality.

§.§ Application of the Cramér-Chernoff Method to Functionals of MJPs

§.§.§ Setting and Notation

Throughout Section <ref> we consider  the following setting.  Let $E$ be a finite set, and  all functions on $E$ are considered to be real valued. For any probability measure $\mu $ on $E$ and any $f \in \mathcal{B}(E)$  let

\begin{equation}
\mu(f) := \int f d\mu
\end{equation}

Furthermore, let $(\F{X}, (\F{P}_x)_{x \in E})$ be an irreducible  MJP on  $E$ with unique invariant distribution $\pi$ (according to Theorem <ref>).  Fix some $f \in \mathcal{B}(E) = \F{R}^E$ (c.f. Remark <ref>),
some probability measure $\nu = (\nu_x)_{x \in E} $ on $E$, and define $A_t := \int_0^t (f(X_s) - \pi(f))ds$. By centering $f$ if needed, we may also assume

\begin{equation}
\label{eq: pi(f) = 0}
\pi(f) = 0,
\end{equation}

so in particular

\begin{equation}
\label{eq: A_t}
A_t = \int_0^t f(X_s) ds.
\end{equation}

To avoid trivialities we assume that $\# E \geq 2$ and $f$ is not constant (i.e. $f \neq 0$). Finally, denote by $\norm{\cdot}_2$ the $L^2(\pi)$-norm or the operator norm induced by the $L^2(\pi)$-norm, and by $\langle \cdot, \cdot \rangle  $ the inner product on $L^2(\pi)$. Furthermore, let $\Psi_{A_t}(r) = \log \F{E}_\nu(e^{rA_t})$.

§.§.§ A general Concentration Inequality

In this section based on the Cramér-Chernoff method we derive a general concentration inequality; Theorem <ref>, which is our version of <cit.>.
The most relevant notions and results of Sections <ref> and <ref> are infinitesimal generator (of an MJP) (Section <ref>) and Cramér-Chernoff method; in particular Lemma <ref> (Section <ref>).  This section is based on <cit.>  and <cit.>, in particular  <cit.> and <cit.>.We proceed as follows. We use the Cramér-Chernoff method, more precisely Lemma <ref>, i.e. we want to find a bound $\Phi(r) \geq \Psi_{A_t}(r)$ to obtain  a concentration inequality

\begin{equation}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right) = \F{P}_\nu (A_t \geq tu) \leq e^{-\Phi^*(tu)} .
\end{equation}

To find a bound $\Phi(r)$  we use a so called Feynman-Kac semigroup $(P_t^{rf})_{ t \geq 0}$ on $L^2(\pi)$ to rewrite $\Psi_{A_t}(r)$ in terms of this semigroup. Then, by bounding $\norm{P_t^{rf}}_2$ we obtain a  bound $\Phi(r)$ and by computing $\Phi^*(tu)$ a concentration inequality.

Define for $t \geq 0$, $h \in L^2(\pi)$ an operator $P_t^h$ on $L^2(\pi)$ via (c.f. <cit.>)

\begin{equation}
\label{eq: def_P_t^h}
(P_t^hg)(x) := \F{E}_x \left (e^{\int_0^th(X_s) ds}g(X_t) \right )
\end{equation}

for $g \in L^2(\pi)$ and $x \in E$.  Recall that in our context  $L^2(\pi) = \mathcal{B}(E)$ (see Remark <ref>) and $\pi_x > 0$ for all $x \in E$ (see Theorem <ref>), so the above operator is clearly well defined. We will see in Lemma <ref> that $(P_t^h)_{t \geq 0}$ is indeed a semigroup. This semigroup is usually referred to as a Feynman-Kac semigroup (see e.g. <cit.>, <cit.>). Let  $\textbf{1} : E \rightarrow \{ 1 \}$ denote the constant 1-function. To rewrite $\Psi_{A_t}(r) = \log \F{E}_\nu (e^{rA_t})$ we can rewrite (by using directly the Definition (<ref>))

\begin{equation}
\label{eq: E_nu_rewriting}
\F{E}_\nu(e^{rA_t}) =\sum_{x \in E}\nu_x (P_t^{rf}\textbf{1})(x)  =  \sum_{x \in E}\frac{\nu_x}{\pi_x} (P_t^{rf}\textbf{1})(x) \pi_x = \left \langle \frac{d \nu}{d \pi} ,P_t^{rf}\textbf{1} \right  \rangle ,
\end{equation}

where $\frac{d \nu}{d \pi}(x) = \frac{\nu_x}{\pi_x}$ denotes the Radon-Nikodym derivative of $\nu$ with respect to $\pi$ (note that $\frac{d \nu}{d \pi}$ is well defined, because by Theorem <ref> $\pi_x > 0$ for all $x \in E$).
Applying the Cauchy-Schwartz inequality to the above equality yields the bound

\begin{equation}
\label{eq: bound_E_nu}
\F{E}_\nu(e^{rA_t}) \leq \norm{\frac{d\nu}{d\pi}}_2 \norm{P_t^{rf}}_2
\end{equation}

and consequently

\begin{equation}
\label{eq: bound_Psi_Z_prefinal}
\Psi_{A_t}(r) \leq \log \norm{\frac{d\nu}{d\pi}}_2 + \log \norm{P_t^{rf}}_2.
\end{equation}

We will now derive the announced bound

\begin{equation*}
\Phi(r) \geq \log \norm{\frac{d\nu}{d\pi}}_2 + \log \norm{P_t^{rf}}_2 \geq \Psi_{A_t}(r)
\end{equation*}

by bounding  $\norm{P_t^{rf}}_2$. For that we will prove and use that $(P_t^h)_{ t \geq 0}$ is a continuous semigroup on $L^2(\pi)$ with infinitesimal generator $L + M_h$, where $L$ is the infinitesimal generator of the MJP and $M_h$ is the multiplication with $h$, i.e. $(M_hg)(x) = h(x)g(x)$  for $x \in E$, $g \in L^2(\pi)$. We have the following lemma:

Let $(P_t^h)_{t \geq 0} $ be the family of operators defined as in (<ref>) and define $L_h = L + M_h$. Then $(P_t^h)_{t \geq 0} $ is a continuous semigroup on $L^2(\pi)$ with generator $L_h$, i.e.

\begin{equation}
\label{eq: semigroup of tilted generator}
P_t^h = \exp(tL_h).
\end{equation}

* We decided to include here our own proof of Lemma <ref>, as <cit.> uses  this Lemma (see <cit.>) but does not provide a proof.

* The above lemma can also be proved by using the proof idea of <cit.>: Using the Markov property it can be shown that  for any $g \in L^2(\pi)$, $k \in \F{N}$, $x \in E$ and any $t \geq 0$

\begin{equation}
\left( \left[\exp(\frac{t}{k}L)\exp(\frac{t}{k}M_h)\right]^k g \right)(x) = \F{E}_x \left ( e^{\sum_{i=1}^k h\left(X_{j\cdot \frac{t}{k}}\right) \frac{t}{k}} g(X_t)\right).
\end{equation}

Then, a combination of the Trotter-product formula (<cit.>)

\begin{equation}
\lim_{k \to \infty} \left[\exp(\frac{t}{k}L)\exp(\frac{t}{k}M_h)\right]^k = \exp(t(L+M_h))
\end{equation}

and the dominated convergence theorem yields Lemma <ref>

* In the context of the Feynman-Kac semigroup $(P_t^h)_{ t \geq 0}$ the operator $L_h = L + M_h$ is also frequently called  'tilted generator' (see e.g. <cit.>)

* As $M_{rf} = r M_f$, the generator of $(P_t^{rf})_{t \geq 0}$ is $L + rM_f$

* (Feynman-Kac formula) The above lemma implies the so called Feynman-Kac formula (c.f <cit.>), which states that the function

\begin{equation*}
u(t,x) := \F{E}_x \left (e^{\int_0^th(X_s) ds}g(X_t) \right ) = (P_t^hg)(x)
\end{equation*}

is a probabilistic solution of the differential equation

\begin{equation*}
\frac{d}{dt}u(t,x) = Lu(t,x) + h(x)u(x), \, u(0,x) = g(x)
\end{equation*}

As we are treating an MJP on a finite state space, $L^2(\pi)$ is finite dimensional and we can prove the claim by direct computation as follows.
In any finite dimensional vector space any two semigroups having the  same infinitesimal generator are identical (see Remark <ref>). So to prove that $P_t^h = \exp(tL_h)$, we prove that $(P_t^h)_{t \geq 0}$ is a semigroup with generator $L_h$. Let $g \in L^2(\pi) $, $I_t = \int_0^th(X_s)ds$ and define $B_t : E^{[0,\infty)} \rightarrow \F{R}$ by

\begin{equation}
\label{eq: def_A_t}
B_t((y_s)_{s \geq 0}) = \exp(\limsup_{k \to \infty }\sum_{i = 1}^k\frac{t}{k}h\left( y_{\frac{t i}{k}}\right))g(y_t).
\end{equation}

Note that we have $B_t((X_s)_{s \geq 0}) = e^{I_t}g(X_t)$ for all $t \geq 0$, because the Riemann sums in (<ref>) converge to $I_t$ by the right continuity of the paths of $\F{X}$ and boundedness of $h$.
Thus, for all $x \in E$ and $s,t \geq 0$ we have

\begin{align*}
&(P_{t}^hP_{s}^hg)(x) = \F{E}_x \left [e^{I_t}(P_s^hg)(X_t) \right] = \F{E}_x \left [e^{I_t}\F{E}_{X_t}[e^{I_s}g(X_s)]\right] = \F{E}_x \left[ e^{I_t} \F{E}_{X_t} [ B_s((X_h)_{h \geq 0})] \right] \\
&= \F{E}_x \left [e^{I_t}\F{E}_x[ B_s((X_{h+t})_{h \geq 0}) | (X_h)_{0 \leq h \leq t}] \right ] = \F{E}_x \left [\F{E}_x[ e^{I_t}B_s((X_{h+t})_{h \geq 0}) | (X_h)_{0 \leq h \leq t}] \right ] \\
&= \F{E}_x\left [ e^{I_t}B_s((X_{h+t})_{h \geq 0})\right ] = \F{E}_x \left[e^{\int_0^th(X_u)du+\int_t^{t+s}h(X_u)du}g(X_{s+t})\right] = (P^h_{s+t}g)(x),
\end{align*}

where in the second line the Markov property (<ref>) of the MJP and the pullout-property of the conditional expectation were used.
Furthermore, as $\F{P}_x(X_0 = x) = 1$ and $S_0 \equiv 0$ we have $P_0^hg = g$, so $(P_t^h)_{t \geq 0}$ is a semigroup of operators. We now calculate the generator of $(P_t^h)_{t \geq 0}$. Let $x \in E$ and $ t > 0$, then

\begin{equation}
\label{eq: lemma_tilted_generator}
\frac{(P_t^hg)(x) - g(x)}{t} =  \F{E}_x \left ( \frac{e^{I_t}-1}{t} g(X_t) \right) + \frac{\F{E}_x( g(X_t)) - g(x)}{t}.
\end{equation}

We now consider the limit for $t \downarrow 0$ in the above expression.
The paths $ t \mapsto X_t$ are right continuous and $\F{P}_x(X_0 = x) = 1$ so $\F{P}_x$-a.s there is an $\varepsilon > 0$ such that $ I_t = t h(x)$ on $ [0, \varepsilon)$. It follows that $\F{P}_x$- a.s.

\begin{equation*}
h(x) = \lim \limits_{ t \downarrow 0 } \frac{e^{ t h(x)}-1}{t} = \lim \limits_{ t \downarrow 0 }\frac{e^{I_t}-1}{t}.
\end{equation*}

But as $\abs{I_t} \leq t \norm{h}_\infty$ by the monotonicity of the exponential function we have

\begin{equation*}
\abs{\frac{e^{I_t}-1}{t}} \leq \max \left (\frac{e^{t \norm{h}_\infty}-1}{t},\frac{1-e^{-t\norm{h}_\infty}}{t} \right).
\end{equation*}

As the exponential function is differentiable at $0$, the right hand side of the above equation is bounded (for $t \to 0$). Furthermore, $g$ is bounded and $\lim_{t \downarrow 0}g(X_t) = x$ $\F{P}_x$-a.s., so using the dominated convergence theorem for the left term in (<ref>) and the definition of $L$ for the right term in (<ref>), it follows that

\begin{equation*}
\lim \limits_{t \downarrow 0}  \frac{(P_t^hg)(x) - g(x)}{t} = h(x)g(x) + (Lg)(x) = (M_hg)(x) + (Lg)(x)
\end{equation*}

for all $x \in E$. As pointwise convergence coincides with convergence in $L^2(\pi)$ (Remark <ref>) the claim follows.

Using the above lemma we can bound $\norm{P_t^{rf}}_2$ in terms of the operators $L, M_{f}$. The following bound holds:

For all $r \in \F{R}$

\begin{equation}
\label{eq: bound_2_norm_feynman_kac}
\norm{P_t^{rf}}_2 \leq \exp(t \lambda_0(r)),
\end{equation}

where $\lambda_0(r)$ is the largest eigenvalue of the selfadjoint operator $\tilde{L}(r) := \frac{L+L^*}{2} + r M_f$.

* The bound  (<ref>) is also found in <cit.>, <cit.> and <cit.>. In <cit.> the bound is stated as

\begin{equation}
\label{eq: wu_bound_feynman_kac_1}
\norm{P_t^{V}}_2 \leq \exp(t \Lambda(V)),
\end{equation}

and in <cit.>

\begin{equation}
\label{eq: wu_bound_feynman_kac_2}
\norm{P_t^{V}}_2 \leq \exp(t \Lambda_0(V)),
\end{equation}

where (see <cit.>)

\begin{equation}
\Lambda(V) = \sup \{- \mathcal{E}^{\sigma}(g,g) + \langle V, g^2 \rangle \, |\, \norm{g}_2 = 1, g \in D(\mathcal{E}^\sigma) \cap L^2(\abs{V}\cdot \mu)\},
\end{equation}

and (see <cit.>)

\begin{equation}
\Lambda_0(V) = \sup \{\langle Lg,g \rangle + \langle V, g^2 \rangle \, |\, \norm{g}_2 \leq  1, g \in D(L) \} .
\end{equation}

$(\mathcal{E}^\sigma, D(\mathcal{E}^\sigma))$ denotes the closure (see <cit.> for the definition of the closure of a bilinear form) of the symmetrized Dirichlet form $(\mathcal{E}^\sigma, D(L))$ ($D(L)$ denotes the domain of the $L^2$-infinitesimal generator)

\begin{equation}
\label{eq: symmetrized_dirichlet}
\mathcal{E}^\sigma (g,h) = - \frac{1}{2} ( \langle Lg,h \rangle + \langle g, Lh \rangle ).
\end{equation}

In our setting $\mu = \pi$, $V = rf$, $D(L) = L^2(\pi)$, and $L$ is a bounded operator. Thus, $(\mathcal{E}^\sigma, D(L)) = (\mathcal{E}^\sigma, L^2(\pi))$ is (already) a closed symmetric form. Furthermore, $V$ is bounded (by finiteness of $E$), consequently $D(\mathcal{E}^\sigma) \cap L^2(\abs{V}\cdot \mu) = L^2(\mu)$ and

\begin{align}
\begin{split}
\Lambda(V) &= \sup \{- \mathcal{E}^{\sigma}(g,g) + \langle V, g^2 \rangle \, |\, g \in L^2(\mu), \norm{g}_2 = 1 \} \\
&= \sup \left \{\left \langle  \left (\frac{L+L^*}{2}+r M_f \right) g, g  \right \rangle \, \middle |\, g \in L^2(\mu), \norm{g}_2 = 1 \right \}  \\
&= \lambda_0(r),
\end{split}
\end{align}

where we used $\langle g, Lg \rangle = \langle L^*g, g \rangle$ and Lemma <ref>. Similarly one obtains

\begin{equation}
\Lambda_0(V) = \lambda_0(r)
\end{equation}

and consequently the bounds (<ref>) and (<ref>) coincide with the bound of Lemma <ref>.

* In <cit.>, not the operator $\tilde{L}(r)$ is considered but instead the operator $\tilde{\Lambda}(r) = - \tilde{L}(r)$ (see <cit.>). Furthermore, $\lambda_0(r)$ is defined as the smallest eigenvalue of $\tilde{\Lambda}(r)$ (see <cit.>), consequently <cit.> obtains  <cit.>

\begin{equation}
\norm{P_t(r)}_2 \leq \exp(-t\lambda_0(r)),
\end{equation}

where $P_t(r) = P_t^{rf}$ as <cit.> defines $P_t(r)$ as the semigroup generated by $L + rM_f$ (see <cit.>)

* The above lemma follows also from the Lumer-Phillips theorem (following  <cit.>). By writing $\lambda_0(r)$ as a supremum as Lemma <ref> and using the identity

\begin{equation*}
\langle Lg, g \rangle = \langle g, L^*g \rangle = \langle L^*g, g \rangle,
\end{equation*}

it is easy to see that

\begin{equation*}
\langle (L+r M_f - \lambda_0(r)) g, g \rangle = \left \langle  \left (\frac{L+L^*}{2}+r M_f - \lambda_0(r) \right) g, g  \right \rangle \leq 0
\end{equation*}

for any $g \in L^2(\pi)$, so the operator $L + rM_f - \lambda_0(r)$ is dissipative (see <cit.> for a characterization of dissipativity). Furthermore, as the spectrum of any finite dimensional operator is bounded, for $\lambda > 0$ big enough the operator

\begin{equation*}
\lambda - (L + rM_f - \lambda_0(r))
\end{equation*}

is surjective
and consequently by the Lumer-Phillips theorem (<cit.>), the semigroup generated by $L + rM_f - \lambda_0(r)$ is a contraction semigroup, i.e.

\begin{equation*}
\norm{P_t^{rf}e^{-t\lambda_0(r)}}_2 = \norm{\exp [ t (L + rM_f - \lambda_0(r))]}_2 \leq 1,
\end{equation*}

which is the statement of Lemma <ref>.

* We will later (see Section <ref>) justify the notation $\lambda_0(r)$ by proving that $\lambda_0(r)$ is the perturbation of the eigenvalue $0$ for the perturbed operator $\tilde{L}(r) = \frac{L+L^*}{2} + rM_f$ (recall by Lemma <ref>$(a)$ that $\lambda_0(0) = 0$ is an eigenvalue of the unperturbed operator $\Tilde{L}(0) = \frac{L+L^*}{2}$).

* If $L$ is self adjoint, then $  L + r M_f$ is also selfadjoint (for $r \in \F{R})$ and it follows (e.g. by diagonalization of $\exp(t(L + rM_f))$ in an orthonormal basis) that

\begin{equation*}
\norm{P_t^{rf}}_2 = \norm{\exp(t(L + rM_f))}_2= \exp(t\lambda_0(r)),
\end{equation*}

so the bound is exact in the detailed balance case (by Theorem <ref> $L$  is selfadjoint in the detailed balance case).

We follow the proof of <cit.> (but use our notation). Let $g  \in  L^2(\pi)$, define $\phi(t) = \norm{P_t^{rf}g}_2^2 = \langle P_t^{rf}g P_t^{rf}g\rangle $, and let $L(r) = L + rM_f$ be the generator of $(P_t^{rf})_{t \geq 0}$ . Using the usual product rule (for scalar products on finite vector spaces) yields

\begin{align}
\begin{split}
\label{eq: lemma2_derivative_phi}
\frac{d}{dt}\phi(t) &=  \langle \frac{d}{dt}P_t^{rf}g, P_t^{rf}g\rangle + \langle P_t^{rf}g, \frac{d}{dt}P_t^{rf}g \rangle =  \langle L(r)P_t^{rf}g, P_t^{rf}g\rangle + \langle P_t^{rf}g, L(r)P_t^{rf}g \rangle \\
&= \langle (L(r) + L(r)^*)P_t^{rf}g, P_t^{rf}g\rangle  =  2 \left \langle \left  (\frac{L+L^*}{2}+ rM_f \right )P_t^{rf}g, P_t^{rf}g \right \rangle  \\
&= 2\langle \Tilde{L}(r)P_t^{rf}g, P_t^{rf}g \rangle,
\end{split}
\end{align}

where in the first line Lemma <ref> and in the second line the selfadjointness of $M_f$ were used. The operator $\Tilde{L}(r)$ is selfadjoint, so  by  Lemma <ref>

\begin{equation}
\label{eq: lemma2_minimax}
\lambda_0(r) = \sup \left \{ \frac{\langle \Tilde{L}(r)g, g \rangle }{\norm{g}_2^2} \middle | g \in L^2(\pi), g \neq 0 \right \}.
\end{equation}

Using (<ref>)  and (<ref>) we get

\begin{equation*}
\frac{d}{dt}\phi(t) =  2\langle \Tilde{L}(r)P_t^{rf}g, P_t^{rf}g \rangle \leq 2 \lambda_0(r) \norm{P_t^{rf}g}_2^2 = 2\lambda_0(r) \phi(t).
\end{equation*}

It follows that $\frac{d}{dt}(e^{-2\lambda_0(r)t}\phi(t)) \leq 0$, which means that $t \mapsto e^{-2\lambda_0(r)t}\phi(t) $ is nonincreasing and thus

\begin{align*}
&e^{-2\lambda_0(r)t}\phi(t) \leq \phi(0) = \norm{g}_2^2 \\
&\Longleftrightarrow \phi(t) \leq e^{2\lambda_0(r)t}\norm{g}_2^2 \\
&\Longleftrightarrow \norm{P_t^{rf}g}_2 \leq e^{\lambda_0(r)t}\norm{g}_2
\end{align*}

Finally, by using the above lemma to bound $\norm{P_t^{rf}}_2$ and  recalling (<ref>) we get the announced bound

\begin{equation}
\label{eq: final_bound_Phi}
\Phi(r) := \log(\norm{\frac{d\nu}{d\pi}}_2) + t\lambda_0(r) \geq \Psi_{A_t}(r),
\end{equation}

which holds even for all $r \in \F{R}$. We can now take the Fenchel conjugate of $\Phi$ with respect to $\F{R}_{\geq 0}$ (as the Cramér transform is a Fenchel conjugate taken with respect to $\F{R}_{ \geq 0}$) to derive the
following  concentration inequality (c.f. <cit.>).

In our setting the following concentration inequality holds.
For all $u \geq 0$

\begin{equation}
\label{eq: main_conc_inequality}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d\nu}{d \pi}}_2 e^{- t \lambda_0^*(u)},
\end{equation}

\begin{equation*}
\lambda_0^*(u)  = \sup_{ r \in \F{R}}(r u - \lambda_0(r)) = \sup_{r \geq 0}(r u - \lambda_0(r))
\end{equation*}

is the Fenchel conjugate of $\lambda_0$ with respect to $\F{R}$for $u \geq 0$. Furthermore, define

\begin{equation}
I(u) := \inf \{ - \langle Lg, g \rangle \; | \, \norm{g}_2 = 1, \langle M_fg, g \rangle = u \}
\end{equation}

for $u \in \F{R}$. Then,  we have

\begin{equation}
\label{eq: fenchel_dual_lambda_0(r)}
\lambda_0^*(u) = \sup_{ r \in \F{R}}(r u - \lambda_0(r)) = I(u)
\end{equation}

for all $u \in \F{R}$.

The above theorem is a reformulation of <cit.> and <cit.>: Using the notation of <cit.> let $V = f$, $\mu = \pi $ and define (as in <cit.>)

\begin{equation}
J_V(u) = \inf \{ \mathcal{E}^\sigma(g,g) \, | \, \norm{g}_2 = 1, g \in  D(\mathcal{E}^\sigma) \cap L^2(\abs{V}\cdot  \mu), \langle V, g^2 \rangle = u \},
\end{equation}

\begin{equation}
J_0(u) = \inf \{ \mathcal{E}^\sigma(g,g) \, | \, \norm{g}_2 = 1, g \in D(L), \langle V, g^2 \rangle = u \},
\end{equation}

where $(\mathcal{E}^\sigma, D(\mathcal{E}^\sigma))$ denotes the closure of the symmetrized Dirichlet form (defined in (<ref>)). Furthermore, let $I_V(u)$, respectively $I_0(u)$, denote the lower semi-continuous regularization of $J_V$, respectively $J_0$, defined in <cit.>. Then, <cit.>, respectively <cit.> states that

\begin{equation}
\label{eq: wu_theorem1}
\F{P}_\nu \left (\frac{A_t}{t} > u \right ) \leq \norm{\frac{d\nu}{d \mu}}_2 e^{- t I_V(u)}
\end{equation}

\begin{equation}
\F{P}_\nu \left (\frac{A_t}{t} > u \right ) \leq \norm{\frac{d\nu}{d \mu}}_2 e^{- t I_0(u)}
\end{equation}

However, as already explained in Remark <ref>, in our setting  $D(L) = D(\mathcal{E}^\sigma) \cap L^2(\abs{V}\cdot  \mu) = L^2(\mu)$ and thus

\begin{equation}
J_V(u) = J_0(u) = I(u) = \lambda_0^*(u),
\end{equation}

where in the last equality we used (<ref>). But $\lambda_0^* = J_V  = J_0$  is continuous on the interval $\{ \lambda_0^* < \infty \}$ (see the remark below) so $ I_V(u) = I_0(u) = J_V(u) = \lambda_0^*(u)$ (using the definition of the lower semi-continuous regularization; stated for example in <cit.>).

* (Properties of $\lambda_0^*$) The Fenchel conjugate $\lambda_0^*$ has the following properties (see Appendix, Lemma <ref>)

* $\lambda_0^*\geq 0$

* $\{ \lambda_0^* < \infty \} = [\min_{x \in E} f(x), \max_{x \in E}f(x)]$

* $\lambda_0^*$ is  convex, continuous on $\{ \lambda_0^* < \infty \}$, and nondecreasing on $[0,\infty)$.

Hereby, property 1. follows from $\lambda_0(0) = 0$, property 2. is a consequence of (<ref>), and property 1. follows from lower semicontinuity  of $\lambda_0^*$.

* (Triviality of the inequality)
The concentration inequality is trivial whenever

\begin{equation*}
H(u) := \norm{\frac{d\nu}{d\pi}}_2e^{-t\lambda_0^*(u)} \geq 1.
\end{equation*}

Let $K := \sup \{ u \geq 0 \; | \; H(u) \geq 1 \}$. Then
if $\nu \neq \pi$, we have $K  > 0$, $K \geq t^{-1}\F{E}_\nu(A_t)$ and the concentration inequality is trivial for $ u \in [0,K]$. This can be seen as follows. As $\nu \neq \pi$, $\frac{d\nu}{d\pi}$ is not equal to the constant 1-function $\mathbf{1}$ $\pi$- almost surely, so

\begin{equation}
0 <  \text{Var}_\pi \left ( \frac{d \nu}{d \pi} \right )  =  \norm{\frac{d\nu}{d\pi}}_2^2 - 1,
\end{equation}

and thus $\norm{\frac{d\nu}{d\pi}}_2 > 1$. Furthermore, $\lambda_0^*(0) = 0$, which implies $H(0) > 1 $. But $\lambda_0^*$ is continuous on $\{ \lambda_0^* < \infty \}$  and nondecreasing on $[0,\infty)$, so $K > 0$ and $H(u) \geq 1$ for $ u \in [0,K]$. Furthermore, because  Theorem <ref> is based on Chernoff's inequality (c.f. Lemma <ref>), which is always trivial  for $u \leq t^{-1}\F{E}_\nu(A_t) $ by Remark <ref>, we have $K \geq t^{-1}\F{E}_\nu(A_t)$.

* (Scale invariance of the bound)
As $sM_f = M_{sf}$ the bound is invariant under the replacements $f \to sf$, $u \to su$ for $s > 0$. This is consistent with the invariance of $\F{P}_\nu \left (\frac{A_t}{t} \geq u \right )$ under those replacements.

* (Bound for $\norm{\frac{d \nu}{d \pi}}_2)$
We have

\begin{equation*}
\max_{\nu \in \mathcal{M}_1(E)}\norm{\frac{d\nu}{d\pi}}_2 = \frac{1}{\sqrt{\min_{x \in E}\pi_x}},
\end{equation*}

where $\mathcal{M}_1(E)$ denotes the set of probability measures on $E$. The above inequality is checked by
using $\norm{\frac{d \nu}{d \pi}}_2^2 = \sum_{x \in E} \frac{\nu_x^2}{\pi_x}$  and $\norm{\frac{d\delta_x}{d\pi}}_2 = \frac{1}{\sqrt{\pi_x}}$.

* (Optimality and Cramér's Theorem in the detailed balance case)
In the case where $\pi$ satisfies the detailed balance condition, or equivalently $(\F{P}_\pi, \F{X})$ is reversible or $P_t$ is $\pi$-symmetric (see Theorem <ref>), then (<ref>) is asymptotically sharp; we have

\begin{equation}
\label{eq: asymptotic_sharp}
\lim_{ t \to \infty} \frac{ \log \F{P}_\nu  \left (\frac{A_t}{t} >  u \right )}{t} = - \lambda_0^*(u)
\end{equation}

for all $u \neq \max_{x \in E} f(x)$. The above result is a continuous time analogue of Cramérs theorem (c.f. <cit.>) for sums of i.i.d. random variables. The above equality  implies that if $\alpha : [0, \infty) \rightarrow \F{R}_{\geq 0}$ is a function such that a concentration inequality

\begin{equation*}
\F{P}_\nu  \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d\nu}{d\pi}}_2 e^{-\alpha(u)t}
\end{equation*}

holds for all $u \geq 0$, then $\alpha(u) \leq \lambda^*(u)$ for all $u \geq 0$.  Thus, the concentration inequality (<ref>) is optimal in this sense. The asymptotic sharpness (<ref>) is mentioned  in <cit.> and <cit.>, and both works refer to  <cit.>. However, as these works do not directly prove or explain how <cit.> implies (<ref>) we included our own proof of (<ref>) (based on <cit.>), see Lemma <ref>.

We first show that

\begin{equation}
\sup_{r \geq 0} (ru- \lambda_0(r)) = \sup_{r \in \F{R}}( ru -\lambda_0(r))
\end{equation}

for $u \geq 0$. Let $\textbf{1}$ denote the constant 1-function on $E$.  Recall $0 = (L+L^*)\textbf{1}$, $\lambda_0(0) = 0$ (c.f. Lemma <ref>) and $\pi(f) = 0$ (by our assumption (<ref>)). Consequently

\begin{equation}
\label{eq: lambda_0^*_bigger_0}
\lambda_0^*(u) = \sup_{ r \in \F{R}} ( ru - \lambda_0(r)) \geq 0 \cdot u - \lambda_0(0) = 0
\end{equation}

\begin{equation}
\lambda_0(r) \geq r \langle M_f \textbf{1}, \textbf{1} \rangle + \frac{1}{2}\langle (L+L^*)\textbf{1}, \textbf{1} \rangle = r \pi(f) +  0 =  0
\end{equation}

for all $r \in \F{R}$, where the second inequality follows from Lemma <ref>. Thus,

\begin{equation*}
ru - \lambda_0(r) \leq 0
\end{equation*}

for all $u \geq 0$ and $ r \leq 0$, which together with (<ref>) implies

\begin{equation*}
\sup_{r \geq 0} (ru- \lambda_0(r)) = \sup_{r \in \F{R}}( ru -\lambda_0(r)) = \lambda_0^*(u)
\end{equation*}

for $u \geq 0$.
As already explained in  Lemma <ref>, the bound (<ref>)

\begin{equation}
\Phi(r) = \log(\norm{\frac{d\nu}{d\pi}}_2) + t\lambda_0(r) \geq \Psi_{A_t}(r),
\end{equation}

implies the concentration inequality

\begin{equation*}
\F{P}_\nu  \left (\frac{A_t}{t} \geq u \right ) \leq \exp (-\Phi^*(tu))  = \norm{\frac{d\nu}{d\pi}}_2e^{- t \sup_{r \geq 0}(ur - \lambda_0(r))} =  \norm{\frac{d\nu}{d\pi}}_2 e^{-t\lambda_0^*(u)},
\end{equation*}

proving (<ref>).
It remains to prove (<ref>). We follow the proof idea of <cit.> and add details. Note that

\begin{equation}
I(u) =  \min \{ - \langle Lg, g \rangle \; | \; \norm{g}_2 = 1, \langle M_fg, g \rangle = u \},
\end{equation}

i.e. the infimum is attained (we set $\min \emptyset = \inf \emptyset  = \infty$). Indeed, finite dimensionality of $L^2(\pi)$ implies that  the set $\{ g \in L^2(\pi) \; | \; \norm{g}_2 = 1, \langle M_fg,g \rangle = u \} $ is compact,  and $g \mapsto - \langle Lg,g \rangle$ is a continuous map. Consequently the infimum is attained as the infimum of a continuous function over a compact set is always attained. By definition of $\lambda_0(r)$, Lemma <ref> and the identity (which follows from the symmetry of the inner product)

\begin{equation}
\left \langle \left ( \frac{L+L^*}{2} \right )g, g \right \rangle = \langle Lg, g \rangle
\end{equation}

we have

\begin{align}
\begin{split}
\label{eq: lambda_0(r)_is_Legendre_transform_of_I(u)}
\lambda_0(r) &= \sup \{ r\langle M_f g, g \rangle +  \langle Lg, g \rangle \; | \; g \in L^2(\pi), \norm{g}_2 = 1 \}\\
&= \sup \{  ru - (-  \langle Lg, g \rangle) \; | \; g \in L^2(\pi),u \in \F{R}, \norm{g}_2 = 1, \langle M_f g, g \rangle = u \} \\
&= \sup \{ ru - \inf \{ -  \langle Lg, g \rangle \; | \; g \in L^2(\pi) , \norm{g}_2 =1 , \langle M_f g, g \rangle = u \} \; | \; u \in \F{R} \}\\
&= I^*(r)
\end{split}
\end{align}

for all $r \in \F{R}$
where $I^*(r) = \sup_{ u \in \F{R}} (ur - I(u)) = \sup_{u \in \F{R} : I(u)< \infty }(ur - I(u))$ is the Fenchel conjugate of $I$. To finish the proof we show now  that the conditions of the Fenchel-Biconjugation theorem (Lemma <ref>$(c)$) are satisfied, i.e. $\{ I < \infty \} = [a,b]$ for some $a < b$, $I$ is convex, and  $I$ is lower semicontinuous on $[a,b]$. Then, by the Fenchel-Biconjugation theorem
and (<ref>)

\begin{equation*}
I(u) =  I^{**}(u) = \sup_{ r \in \F{R}} (ru - \lambda_0(r) ) = \lambda_0^*(u)
\end{equation*}

for all $u \in \F{R}$. We first show $\{ I < \infty \} = [a,b]$. The sphere $S_1 := \{ g \in L^2(\pi) \; | \; \norm{g}_2 = 1 \} $ is compact and connected. Furthermore, the function $D : S_1 \rightarrow \F{R} $ defined via $D(g) := \langle M_f g, g \rangle$ is continuous  ($L^2(\pi)$ is finite dimensional), so the image $\text{Im}(D) \subset \F{R}$ is connected and compact, i.e.  $\text{Im}(D) = [a,b]$, where $a < b$  as $D$ is not constant (because $f$ is not constant). Thus, by definition of $I$ we have

\begin{equation}
\label{eq: I_smaller_infty}
\{I < \infty \} = \text{Im}(D) = [a,b].
\end{equation}

That $I$ is convex on $[a,b]$ can be seen as follows. Notice that for all $g_1, g_2 \in L^2(\pi)$, all $s_1, s_2 \geq 0$ and all $x,y \in E$ we have that

\begin{equation}
\label{eq: inequality1_for_convexity_of_I}
s_1 g_1(y) g_1(x) + s_2 g_2(y) g_2(x) \leq \sqrt{s_1g_1(y)^2 + s_2 g_2(y)^2}\sqrt{s_1g_1(x)^2 + s_2 g_2(x)^2},
\end{equation}

which is easily checked by squaring the above inequality. Let $g := \sqrt{s_1g_1^2+s_2g_2^2}$, then  (<ref>) implies (by setting $y = X_t$, $x = X_0$ and taking the expectation $\F{E}_x$)

\begin{equation*}
s_1 \F{E}_x(g_1(X_t))g_1(x) + s_2 \F{E}_x(g_2(X_t))g_2(x)  \leq \F{E}_x(g(X_t))g(x),
\end{equation*}

which  implies  (by multiplying with $\pi_x$ and summing over $x \in E$)

\begin{equation}
\label{eq: inequality2_for_convexity_of_I}
s_1 \langle P_tg_1, g_1 \rangle + s_2 \langle P_tg_2, g_2 \rangle \leq \langle P_tg, g \rangle ,
\end{equation}

for all $t \geq 0$. Now we use the above equation to prove the convexity of $I$. For that
let $u_1, u_2 \in [a,b]$, $s_1 + s_2 = 1$ (with $s_1, s_2 \geq 0$), and choose $g_1,g_2 \in S_1$ such that $D(g_i) = u_i$ and $- \langle Lg_i, g_i \rangle = I(u_i)$ for $i = 1,2$ (this is possible as $I(u_i)$ is attained). For the convexity we have to show $I(s_1u_1 + s_2u_2) \leq s_1 I(u_1) + s_2 I(u_2)$. Define $g = \sqrt{s_1g_1^2+s_2g_2^2} $ as before. Then,  $g \in S_1$ and $D(g) = s_1u_1 + s_2u_2$. In particular  $I(s_1u_1+s_2u_2) \leq - \langle Lg, g \rangle$ as $I$ is the infimum. As both  sides of (<ref>) equal $1$ at $t = 0$, the inequality holds also for the derivatives at $t = 0$ of both  sides, obtaining

\begin{equation*}
- s_1 I(u_1) - s_2 I(u_2) = s_1 \langle Lg_1 ,g_1\rangle + s_2 \langle Lg_2,g_2\rangle  \leq \langle Lg ,g \rangle \leq - I(s_1u_1+s_2u_2),
\end{equation*}

which proves convexity of $I$. Finally, the lower-semicontinuity of $I$ is checked as follows.  Let $ u \in [a,b]$ and $(u_n)_n$ be a sequence in $[a,b]$ converging to $u$. Furthermore let $(g_n)_n$ be a corresponding sequence in $S_1$ such that $D(g_n) = u_n$ and $ - \langle Lg_n ,g_n \rangle = I(u_n)$. Define $I_{-} := \lim \inf_{n \to \infty} I(u_n) $. We can choose a subsequence $(u_{n_k})_k$ such that $I(u_{n_k}) \to I_{-}$ as $k \to \infty $ and such that $g_{n_k}$ converges  to some $g \in S_1$ (as $k \to \infty $, by compactness of $S_1$). Continuity implies $D(g) = \lim_{k \to \infty} D(g_{n_k}) = \lim_{k \to \infty} u_{n_k} = u$ and $ - \langle Lg, g \rangle = \lim_{k \to \infty}- \langle Lg_{n_k}, g_{n_k} \rangle = \lim_{k \to \infty} I(u_{n_k}) = I_{-}$. But as $I(u)$ is defined as an infimum we have $I_{-} =  - \langle Lg, g \rangle  \geq I(u)$. Thus, $I$ is lower semicontinuous and all conditions for the Fenchel-Biconjugation theorem (Lemma <ref>$(c)$) are satisfied.

§.§.§ Further concentration Inequalities for MJPs

As we typically do not have the information about $L$ or $f$, we cannot compute the largest eigenvalue $\lambda_0(r)$ explicitly and thus Theorem <ref>, which gives a bound containing

\begin{equation*}
\lambda_0^*(u) =  \sup_{ r \geq 0} (r u - \lambda_0(r)) = \sup_{r \in \F{R}}(r u - \lambda_0(r)),
\end{equation*}

is not directly applicable.
In the following we will derive more explicit concentration inequalities based on Theorem <ref> by finding a lower bound for $ \alpha(u) \leq \lambda_0^*(u) $, thus obtaining

\begin{equation}
\F{P}_\nu \left ( \frac{A_t}{t} \geq u  \right) \leq \norm{\frac{d\nu}{d\pi}}_2 e^{- t\alpha(u)}
\end{equation}

For that we present three different approaches following the works <cit.>, <cit.>, <cit.>. All these works use implicitly or explicitly Theorem <ref> to derive concentration inequalities. The three approaches we present are

* Perturbation theory: We follow <cit.> and arrive at our version of <cit.>; Theorem <ref>.

* Functional Inequalities: Poincaré-Inequality, $F$-Sobolev inequality. We follow  <cit.> and arrive at our versions of <cit.> and <cit.>; Theorems <ref> and <ref>.

* Information inequalities:
We follow <cit.> and arrive at our versions of <cit.> and <cit.>; Theorems <ref> and <ref>. We also extend Theorem <ref> (c.f. Theorem <ref>)

In approach 3 we derive a lower bound on $\lambda_0^*(u)$ by using the expression (Theorem <ref>)

\begin{equation}
\lambda_0^*(u) = I(u) = \inf \{ - \langle Lg, g \rangle \; | \, \norm{g}_2 = 1, \langle M_fg, g \rangle = u \}.
\end{equation}

In approaches 1 and 2 we will make use of the following lemma:

Let $D \subset \F{R}$ and let $G$ be a function, defined on $D$ such that $G(r) \geq \lambda_0(r)$ for all $r \in D$. Then, for all $u \geq 0$

\begin{equation}
\label{eq: concentration_via_bound_on_lambda_0(r)}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq  \norm{\frac{d\nu }{ d \pi}}_2 \exp( - tG^*(u)),
\end{equation}

where  $G^*(u) = \sup_{r\in D}(ru- G(r))$ denotes the Fenchel conjugate of $G$ with respect to $D$.

As $D \subset \F{R}$ and $G(r) \geq \lambda_0(r)$ for all $r \in D$, by Lemma <ref>$(d)$
we have

\begin{equation}
G^*(u) \leq \lambda_0^*(u)
\end{equation}

for all $u \geq 0$. Applying this inequality to the  concentration inequality (<ref>) (Theorem <ref>) yields

\begin{equation}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d\nu}{d \pi}}_2 e^{- t \lambda_0^*(u)} \leq \norm{\frac{d\nu}{d \pi}}_2 e^{-tG^*(u)}
\end{equation}

for all $u \geq 0$.

§.§.§ Concentration Inequalities via Perturbation Theory

In this section we use Lemma <ref> and bound $\lambda_0(r)$ using perturbation theory; based on <cit.>. The main result of this section is Theorem <ref>, which is our version of <cit.>. The most relevant notions and results of Section <ref> are: Example <ref>, perturbation theory (Section <ref>); in particular reduced resolvent and Theorem <ref>, and properties of the infinitesimal generator (Lemma <ref>).

We proceed as follows. The basic idea is to see $\lambda_0(r)$ as the perturbation of the eigenvalue $0$ of $L$, then use the formulae of Theorem <ref> (which yields an expression for $\lambda_0(r)$ in terms of a perturbation series) to compute a bound $G(r) \geq \lambda_0(r)$ and apply Lemma <ref>.

Let us now explain more precisely in the following lemma how Theorem <ref> applies in our setting (defined in Section <ref>).

Refering to our setting, let $\lambda_1 = \min_{ \lambda \in \sigma \left (\frac{L+L^*}{2} \right) } \abs{\lambda}$ be the spectral gap of $\frac{L+L^*}{2}$. Then, for all $r \in [0, \frac{\lambda_1}{2 \norm{f}_\infty})$ the ball $B_{\frac{\lambda_1}{2}}(0)$ contains exactly one simple eigenvalue of $\tilde{L}(r)$ and this eigenvalue is $\lambda_0(r)$, the largest eigenvalue of $\tilde{L}(r)$. Furthermore,

\begin{equation}
\label{eq: lambda_0(r)_perturbation_series}
\lambda_0(r) = \sum_{n = 1}^{\infty}\lambda_0^{(n)}r^n
\end{equation}

\begin{equation}
\lambda_0^{(n)} = \frac{(-1)^n}{n} \sum\limits_{\substack{k_1,..k_n \in \F{Z}_+ \\ k_1 + ... k_n = n-1}} \Tr( M_fS^{(k_1)} ... M_fS^{(k_n)})
\label{eq: lambda_0^(n)}
\end{equation}

for all $ r \in  [0, \frac{\lambda_1}{2 \norm{f}_\infty}) $. Hereby,

\begin{equation}
\label{eq: S^(k)}
S^{(0)} = - \textup{pr} \;, \; S^{(k)} = S^k \text{\space for $k \geq 1$,}
\end{equation}

where $S$ is the reduced resolvent of $\frac{L+L^*}{2}$ with respect to the eigenvalue $0$ and $\textup{pr}$ is the orthogonal projection onto the eigenspace corresponding to the eigenvalue 0, i.e.

\begin{equation}
\label{eq: projection_P}
\textup{pr}(g) = \langle g, \textup{\textbf{1}} \rangle \textup{\textbf{1}} = \pi(g) \textup{\textbf{1}}
\end{equation}

for all $g \in L^2(\pi)$.

The above lemma is not explicitly stated as a  lemma in <cit.>, so we include our own proof. In particular, we include the proof of the statement that $\lambda_0(r)$ is the perturbation of the eigenvalue $0$, i.e.  the unique, simple eigenvalue of $\tilde{L}(r)$ contained in $B_{\frac{\lambda_1}{2}}(0)$.

For $n = 1$ we get

\begin{equation*}
\lambda_0^{(1)} = \Tr(M_f\textup{pr}) = \sum_{x \in E}(M_f\text{pr}(e_x))(x) = \sum_{x \in E}(M_f\textbf{1})(x)\pi_x =  \sum_{x \in E} \pi_x f(x) =  \pi(f) = 0,
\end{equation*}

where the trace was evaluated in the basis $e_x(y) = \delta_{xy}$ and $\text{pr}(e_x) = \langle \textbf{1}, e_x \rangle \textbf{1} = \pi_x \textbf{1}$ was used.

Using the notation of Theorem <ref> set $T = \frac{L+L^*}{2}$ and $T' = M_f$. Note that $\norm{M_f}_2 = \norm{f}_\infty$. Furthermore, let

\begin{equation}
I = \left[0, \frac{\lambda_1}{2 \norm{M_f}_2}\right ) = \left[0, \frac{\lambda_1}{2 \norm{f}_\infty}\right ) \text{\space and \space } B = B_{\frac{\lambda_1}{2}}(0).
\end{equation}

Note that $0$ is a simple eigenvalue of $T = \frac{L+L^*}{2}$ (Lemma <ref>$(a)$) and $T = \frac{L+L^*}{2}$ is self adjoint, so the conditions of Theorem <ref> are satisfied.  According to this theorem, for all $ r \in I $ the ball $B$ contains exactly one eigenvalue of $\tilde{L}(r)$ and this eigenvalue is simple. We now show that for $r \in I$, this eigenvalue contained in $B$ is exactly $\lambda_0(r)$, the largest eigenvalue of $\tilde{L}(r)$, making it possible to express $\lambda_0(r)$ using the perturbation series of Theorem <ref>. Let $N = \#E = \dim L^2(\pi)$. By a combination of Lemma <ref>$(a),(d)$ and Lemma <ref>, there are continuous (real valued) functions $\mu_0,...,\mu_{N-1}$ defined on $I$, representing the repeated eigenvalues of $\tilde{L}(r)$ such that (after relabeling) $\max\{\mu_1(0),...,\mu_{N-1}(0)\} < \mu_0(0) = 0$. We have that $\mu_0(r) \in B$ for all $r \in I $. Indeed, suppose there is an $r \in I$ such that $\mu_0(r) \not \in B$. Let $s \in I$ be the infimum of all such $r \in I$ with $\mu_0(r) \not \in B$, so that $\mu_0(r) \in B$ for all $r \in [0,s)$. Then, as $\mu_0(0) \in B$ and $B$ is open, the continuity of $\mu_0$ implies $ s > 0 $ and $\mu_0(s) \not \in B$. But, as $B$ always contains a simple eigenvalue of $\tilde{L}(r)$ for $r \in I$, there is a $\mu_k$ (with $ k \neq 0$) such that $\mu_k(s) \in B$. Because of continuity of $\mu_k$ it follows that $\mu_0(s-\varepsilon), \mu_k(s-\varepsilon) \in B$ for small enough $\varepsilon > 0$, contradicting the fact that $B$ contains exactly one simple eigenvalue of $\tilde{L}(r)$ for $r \in I$. Thus, for all $r \in I$, $\mu_0(r)$ is the unique, simple eigenvalue of $\Tilde{L}(r)$ contained in $B$. But $\mu_0(r)$ is also the largest eigenvalue of $\tilde{L}(r)$, i.e. $\mu_0(r) = \lambda_0(r)$. Indeed, because the functions $\mu_1,...,\mu_{N-1}$ are continuous, $\max \{\mu_1(0),...,\mu_{N-1}(0)\} < \mu_0(0) = 0$ and $\mu_0(r)$ is the unique, simple eigenvalue contained in $B$, it follows that $\max \{\mu_1(r),...,\mu_{N-1}(r)\} < \mu_0(r)$  for all $r \in I$ and consequently $\mu_0(r)$ is also the largest eigenvalue of $\tilde{L}(r)$. Thus, the formulae (<ref>), (<ref>) and (<ref>) follow from the formulae of Theorem <ref>. Finally, (<ref>) follows from Lemma <ref>$(a)$ and the computation of orthogonal projections in Hilbert spaces.

As the above expression of $\lambda_0(r)$ as an infinite series in $r$ is not practical for computing $\lambda_0^*$, we derive an upper bound $G(r) \geq \lambda_0(r)$  using the above series representation of $\lambda_0(r)$ to obtain a explicit concentration inequality (invoking Lemma <ref>). The derivation of the upper bound $G(r)$ we will involve algebraic manipulations with the reduced resolvent $S$. We will make use of the following lemma, which summarizes the most important properties of the reduced resolvent.

Let $L$ be the infinitesimal generator of an irreducible $MJP$. Let $S $ be the reduced resolvent of $\frac{L + L^*}{2}$ with respect to the eigenvalue $0$ (see Definition <ref>). Let $\hat{S} := - S$ and let $\lambda_1 :=  \min \limits_{\lambda \in \sigma(\frac{L+L^*}{2}) \backslash \{0\}} \abs{\lambda }$ be the spectral gap. Then, the following statements hold:

* $S$ is selfadjoint and negative semidefinite.

* $\norm{S}_2 = \frac{1}{\lambda_1}$ and $\textup{Ker}(S) = \textup{span}(\textup{\textbf{1}})$.

* For all $r \in \F{R}$, a unique selfadjoint operator $\hat{S}^r$ can be defined such that for any eigenvector $h \in L^2(\pi)$, with eigenvalue $\mu \geq 0$, of $\hat{S}$ we have

\begin{equation}
\label{eq: definition_S_hat}
\hat{S}^rh =  \begin{cases}
\mu^r \cdot h \; \mathrm{for} \; \mu > 0 \\
0 \; \mathrm{for} \; \mu = 0.
\end{cases}
\end{equation}

* Furthermore,

\begin{equation}
\norm{\hat{S}^r}_2 = \frac{1}{\lambda_1^r},\text{\,} \hat{S}^{r_1 + r_2} = \hat{S}^{r_1}\hat{S}^{r_2},
\end{equation}

and for all $f \in \{\textup{\textbf{1}\}}^\perp $ we have $\hat{S}^{-r}\hat{S}^rf = f$.

We prove all statements by diagonalizing $\frac{L+L^*}{2}$. Let  $(b_k)_{k = 1,...,N}$ be an orthonormal basis that diagonalizes $\frac{L+L^*}{2}$, where $N = \#E = \dim L^2(\pi)$. Furthermore, let $\mu_k$ denote the corresponding eigenvalues and let $\text{pr}_k$ denote the orthogonal projections onto $\text{span}(b_k)$, i.e. $\text{pr}_k(f) = \langle b_k, f \rangle b_k$ for all $f \in L^2(\pi)$. Using Lemma <ref>$(a)$ and $(d)$ we can assume  $\mu_1 = 0$ and $\mu_k < 0$ for $k \geq 2$, in particular

\begin{equation}
\frac{L+L^*}{2} = \sum_{k = 2}^N \mu_k \text{pr}_k
\end{equation}

and $\text{pr}_1$ is the projection onto the eigenspace corresponding to the eigenvalue $0$.
Using the expression of Remark <ref>  for the reduced resolvent $S$ we get

\begin{equation}
S = \sum_{k = 2}^N \frac{1}{\mu_k} \text{pr}_k.
\end{equation}

This equation implies immediately statements $(a)$ and $(b)$. Moreover, it also implies that

\begin{equation}
\hat{S} = \sum_{k = 2}^N \frac{1}{-\mu_k}\text{pr}_k.
\end{equation}

As $\frac{1}{-\mu_k} > 0$ for all $k \geq 2$ the operator $\hat{S}^r$ defined via

\begin{equation}
\hat{S}^r = \sum_{k = 2}^N \frac{1}{(-\mu_k)^r} \textup{pr}_k
\end{equation}

is well defined, selfadjoint and satisfies (<ref>) by definition. Moreover, as $(b_k)_{k = 1,...,N}$ is a basis diagonalizing $\hat{S}$, (<ref>) uniquely determines $\hat{S}^r$ and thus statement $(c)$ is proved. The first two statements of $(d)$ follow directly from the above representation of $\hat{S}^r$, Finally by Lemma <ref>$(a)$ we have $\text{span}(b_1) = \text{span}(\textup{\textbf{1}})$, so $f \in \{\textbf{1}\}^\perp$ implies that $f = \sum_{k = 2}^N \text{pr}_k f$. The equality $\hat{S}^{-r}\hat{S}^rf = f$ then follows directly from the above representation of $\hat{S}^r$, respectively $\hat{S}^{-r}$.

Notice that $Sf$ can also be written as (c.f. <cit.>, <cit.>)

\begin{equation}
Sf = \int_{0}^\infty \exp(t\frac{L+L^*}{2})f dt
\end{equation}

for any $f \in \{\textbf{1} \}^\perp$.

Using the above lemma we can now derive the following bound on $\lambda_0(r)$.

\begin{equation}
\Phi(x) := \left ( \frac{1-x}{2} \right) \left( 1-  \sqrt{1-\frac{4x^2}{(1-x)^2}} \right)
\end{equation}

for $ -1 \leq x \leq \frac{1}{3}$. Then, for all $ 0 \leq r \leq \frac{\lambda_1}{3 \norm{f}_\infty}$

\begin{equation}
\label{eq: lezaud_bound_lambda_0(r)}
\lambda_0(r) \leq  \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right) \Phi\left (\frac{\norm{f}_{\infty}r}{\lambda_1} \right) \leq \frac{r^2\frac{\hat{\sigma}_f^2}{2}}{1-2\left(\frac{\norm{f}_{\infty}}{\lambda1}\right) r},
\end{equation}

where  $S$ denotes the reduced resolvent of $\frac{L+L^*}{2}$ with respect to the eigenvalue $0$ and $\hat{\sigma}_f := - 2 \langle f, Sf \rangle $.

As <cit.> defines $\lambda_0(r)$ as the smallest eigenvalue of $- \frac{L+L^*}{2}$ the corresponding bound of <cit.> is stated as

\begin{equation}
- \lambda_0(r) \geq - \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right) \Phi\left (\frac{\norm{f}_{\infty}r}{\lambda_1} \right) \geq  -\frac{r^2\frac{\hat{\sigma}_f^2}{2}}{1-2\left(\frac{\norm{f}_{\infty}}{\lambda1}\right) r}.
\end{equation}

* Although the presented proof below just works for
$0 \leq r \leq \frac{\lambda_1}{3 \norm{f}_\infty}$ (see Remark <ref>) the bound

\begin{equation*}
\lambda_0(r)  \leq \frac{r^2\frac{\hat{\sigma}_f^2}{2}}{1-2\left(\frac{\norm{f}_{\infty}}{\lambda1}\right) r}
\end{equation*}

actually holds also for $0 \leq r < \frac{\lambda_1}{2 \norm{f}}$ (see Theorem <ref>).

* If the   process starts with stationary initial conditions, i.e. $\nu = \pi$, then  using that this lemma holds also for $0 \leq r < \frac{\lambda_1}{2 \norm{f}}$ and the upper bound $\Phi(r) = t \lambda_0(r)$  on $\Psi_{A_t}$ (see (<ref>)), it follows immediately that $A_t$ is sub-gamma (on the right tail) with variance $t \hat{\sigma}_f^2$ and scale parameter $\frac{2 \norm{f}_\infty}{\lambda_1}$.

We follow the proof idea of <cit.> and add computational details. To simplify the notation and for enhanced readability of the proof we adopt the following notation for the product of operators. Let $m \geq l$, define for operators $A_{l},A_{l+1},...,A_{m}$ (defined on a common vector space)

\begin{equation}
\prod_{i=l, \curvearrowright}^{m} A_i := A_lA_{l+1} ... A_m.
\end{equation}

If $m < l$ define

\begin{equation}
\prod_{i = l, \curvearrowright}^m A_i := 1.
\end{equation}

To get an upper bound for $\lambda_0(r)$ we bound each coefficient $\lambda_0^{(n)}$ in the series (c.f. Lemma <ref>)

\begin{equation}
\lambda_0(r) = \sum_{n = 1}^\infty \lambda_0^{(n)}.
\end{equation}

Recall  that $\lambda_0^{(1)} = 0$ (see Remark <ref>), so we only have to consider $n \geq 2$. Fix  some $n \geq 2$. We rewrite the expression for $\lambda_0^{(n)}$ (c.f. Lemma <ref>)

\begin{equation}
\lambda_0^{(n)} = \frac{(-1)^n}{n} \sum\limits_{\substack{k_1,..k_n \in \F{Z}_+ \\ k_1 + ... k_n = n-1}} \Tr( M_fS^{(k_1)} ... M_fS^{(k_n)})
\label{eq: lambda_0^(n)_proof}
\end{equation}