as follows. Call a permutation $\sigma : \{1,...,n \} \rightarrow \{1,...,n \} $ circular if it is a multiple of the permutation $(1 \; 2 \;... \; n)$ (in cycle notation). Then using the well known trace identity  for finite dimensional operators $A_1,A_2 $, i.e.  $\Tr(A_1A_2) = \Tr(A_2A_1)$, it follows that

\begin{equation}
\label{eq: Tr_invariance_circular_permutation}
\Tr( \prod_{i = 1,   \curvearrowright}^{k} A_i) = \Tr( \prod_{i = 1, \curvearrowright}^{k}A_{\sigma(i)})
\end{equation}

where $A_1,...A_k$ are arbitrary operators and $\sigma$ is some circular permutation. Rewriting (<ref>) yields

\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( \prod_{i=1,\curvearrowright}^nM_fS^{(k_i)}) .
\end{equation}

To sum over the  Tr-terms having the same value in the above expression of $\lambda_0^{(n)}$ (due to invariance with respect to circular permutations), we define an equivalence relation on the set of all $\F{Z}_+$ valued sequences $(k_1,...,k_n)$ with $k_1 + ... + k_n = n-1$ by $(k_1,...,k_n) \sim  (m_1,...,m_n)$ if and only if there is a circular permutation $\sigma $ such that $(m_1,..., m_n) = (k_{\sigma(1)},...,k_{\sigma(n)})$. It can be shown (see Lemma <ref>) that all equivalence classes $[k_1,...,k_n]$ contain exactly $n$ elements. Furthermore, because $m_1 + ... +m_n = n-1$, at least one $m_i$ is zero, so the equivalence class $[m_1,...,m_n]$ of $(m_1,...,m_n)$ always has a representation $[k_1,..k_{n-1},0]$, where $k_1,...,k_{n-1} \in \F{Z}_+$ and $k_1 + ...+ k_{n-1} = n -1 $. Thus, combining the aforementioned facts with (<ref>) yields  that  $\lambda_0^{(n)}$ can be rewritten as

\begin{align}
\begin{split}
\label{eq: lemma3_lambda_0(n)_2}
\lambda_0^{(n)} &= (-1)^n \sum_{[k_1,...,k_{n-1},0]}\Tr(\left(\prod_{i = 1, \curvearrowright}^{n-1}M_fS^{(k_i)}\right)M_fS^{(0)}) \\
&= (-1)^n\sum_{[k_1,...,k_{n-1},0]}\Tr(M_f\left(\prod_{i=1,\curvearrowright}^{n-1}S^{(k_i)}M_f\right)S^{(0)}),
\end{split}
\end{align}

where the sum is taken over all equivalence classes. To bound $\abs{\lambda_0^{(n)}}$ we will now bound the traces in (<ref>). Define

\begin{equation}
\Tr([k_1,...,k_{n-1},0]) := \Tr(M_f\left(\prod_{i=1,\curvearrowright}^{n-1}S^{(k_i)}M_f\right)S^{(0)}).
\end{equation}

Note that only the equivalence classes $[k_1,...,k_{n-1},0]$ without two consecutive zeros lead to nonzero traces in (<ref>). This can be seen as follows.  Let $(e_x)_{x \in E}$ be the basis of $L^2(\pi)$ defined via $e_x(y) := \delta_{xy}$ for $x,y \in E$. In this basis the trace $\Tr([k_1,...,k_{n-1},0])$ is given by

\begin{align}
\label{eq: lemma_3_lambda_0^(n)_3}
\begin{split}
&\Tr([k_1,...,k_{n-1},0]) =
\sum_{x \in E}-\left (M_f \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \text{pr}(e_x) \right )(x) \\
&= \sum_{x\in E}-  \left(M_f \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \textbf{1} \right)(x) \cdot \pi_x = \sum_{x\in E}-f(x) \cdot  \left( \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \textbf{1} \right)(x) \cdot \pi_x\\
&= - \left \langle f,  \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \textbf{1}  \right\rangle ,
\end{split}
\end{align}

where we used  the identities
(c.f. Lemma <ref>)

\begin{equation}
S^{(0)}e_x = - \text{pr}(e_x) = -\langle e_x, \mathbf{1} \rangle \textbf{1}= -\pi_x \textbf{1}
\end{equation}

\begin{equation}
( M_fg)(x) = f(x) g(x) .
\end{equation}

If $[k_1,..k_{n-1},0]$ has two consecutive zeros, then by applying a circular permutation, we can assume that $k_{n-1} = 0$. But if $k_{n-1} = 0$, then using (<ref>) and $S^{(0)}M_f\textbf{1} = -PM_f\textbf{1} = -\pi(f) \mathbf{1} = 0$  yields $\Tr([k_1,...,k_{n-1},0]) =   0$. Thus it is sufficient to bound the traces in (<ref>) described by equivalence classes $[k_1,...,k_{n-1},0]$ with no adjacent zeros. In the following  let $[k_1,...k_{n-1},0]$ be such an equivalence class and let $m \geq 1$ be the number of (non adjacent) zeros in $[k_1,...,k_{n-1},0]$. We will now derive an upper bound for $\abs{\Tr([k_1,...,k_{n-1},0])}$, leading via (<ref>) to a upper bound for $\abs{\lambda_0^{(n)}}$. We first rewrite the last term in (<ref>)

\begin{equation}
- \left \langle f,  \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \textbf{1}  \right\rangle
\end{equation}

as follows. Let $1 \leq j_1 < ... < j_m \leq n$ be the positions of the zeros in $(k_1,...,k_{n-1},0)$. In particular, $j_m = n$ and $k_{j_l} = 0$ for $l = 1,...,m$. Furthermore, because there are no consecutive zeros we have $k_1 \neq 0$ and $k_{j_l \pm 1} \neq 0$ for all $l = 1,...,m$. Then, using $j_1,...,j_m$ and $k_{j_l} = 0$
we rewrite

\begin{align}
\begin{split}
&- \left \langle f,  \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \textbf{1}  \right\rangle =  - \left \langle f, \left (\prod_{i = 1, \curvearrowright}^{j_1 -1}S^{(k_i)}M_f \right ) \left (\prod_{l = 1, \curvearrowright}^{m-1}  \left ( \prod_{i = j_{l}, \curvearrowright}^{j_{l+1}-1} S^{(k_i)}M_f \right ) \right ) \textbf{1} \right \rangle  \\
&= - \left \langle f, \left (\prod_{i = 1, \curvearrowright}^{j_1 -1}S^{(k_i)}M_f \right ) \left (\prod_{l = 1, \curvearrowright}^{m-1}  S^{(0)}M_f \left ( \prod_{i = j_{l}+1, \curvearrowright}^{j_{l+1}-1} S^{(k_i)}M_f \right ) \right ) \textbf{1} \right \rangle .
\label{eq: scalar_product_with_f}
\end{split}
\end{align}

Now for all $m \in \F{N}$ and all operators $A_1,...,A_{m-1}$ (on $L^2(\pi)$) it holds that

\begin{equation}
\label{eq: iterated_product}
\left ( \prod_{l = 1, \curvearrowright}^{m-1} S^{(0)}M_f A_l\right )\textbf{1} = (-1)^{m-1} \left (\prod_{l = 1}^{m-1} \langle f, A_l \textbf{1} \rangle \right ) \textbf{1},
\end{equation}

which follows by induction on $m$, using

\begin{equation*}
S^{(0)}M_fg = - \text{pr}(fg) = - \langle \textbf{1},fg \rangle \textbf{1} = - \langle f, g \rangle \textbf{1}
\end{equation*}

for $g \in L^2(\pi)$.
Applying (<ref>) to the product $\prod_{l = 1, \curvearrowright}^{m-1} ...$ in the last line of (<ref>), setting $A_l = \left ( \prod_{i = j_{l}+1, \curvearrowright}^{j_{l+1}-1} S^{(k_i)}M_f \right )  $ and $j_0 := 0$, gives (continuing the chain of equalities in (<ref>))

\begin{align}
\begin{split}
\label{eq: lemma3_expression_Tr}
& - \left \langle f,  \left(\prod_{i=1, \curvearrowright}^{n-1}S^{(k_i)}M_f \right) \textbf{1}  \right\rangle \\
&=  (-1)^m\left \langle f , \left (\prod_{i = 1, \curvearrowright}^{j_1 -1}S^{(k_i)}M_f \right ) \left (\prod_{l = 1}^{m-1} \left \langle f, \left ( \prod_{i = j_{l}+1, \curvearrowright}^{j_{l+1}-1} S^{(k_i)}M_f \right) \textbf{1} \right \rangle \right ) \textbf{1} \right \rangle  \\
&= (-1)^m \prod_{l = 1}^m \left \langle f, \left ( \prod_{i = j_{l-1}+1, \curvearrowright}^{j_l-1} S^{(k_i)}M_f \right) \textbf{1} \right \rangle
= (-1)^m \prod_{l = 1}^m \left \langle f, \left ( \prod_{i = j_{l-1}+1, \curvearrowright}^{j_l-1} S^{k_i}M_f \right) \textbf{1} \right \rangle,
\end{split}
\end{align}

where in the last equality  $S^{(k)} = S^k$ for $k \geq 1$ was used (by definition of $j_1,...j_m$ we have that $k_i \geq 1 $ for all $i \in \{1,...,n\} \backslash \{j_1,...,j_m \}$). Thus, we obtain (recalling (<ref>))

\begin{equation}
\label{eq: Tr[k_1,...,k_n]_absolute_value}
\abs{ \Tr([k_1,...,k_{n-1},0])} =  \prod_{l = 1}^m \abs{\left \langle f, \left ( \prod_{i = j_{l-1}+1, \curvearrowright}^{j_l-1} S^{k_i}M_f \right) \textbf{1} \right \rangle}.
\end{equation}

The next objective is to bound each of the $m$ factors in the above equation to get a bound for the trace. We show the following bound for each factor:

\begin{equation}
\label{eq: bound_for_each_factor}
\abs{\left \langle f, \left ( \prod_{i = j_{l-1}+1, \curvearrowright}^{j_l-1} S^{k_i}M_f \right) \textbf{1} \right \rangle} \leq \frac{\hat{\sigma}_f^2 \lambda_1}{2} \left (\frac{1}{\lambda_1} \right)^{ \sum_{i = j_{l-1}+1}^{j_l -1}k_i} \norm{f}_\infty^{j_{l}-j_{l-1}-2}.
\end{equation}

To show this bound we will use results of Lemma <ref>.
Notice that the product $\prod_{i = j_{l-1}+1, \curvearrowright}^{j_l-1}...$ in each factor is nonempty, i.e. $j_{l-1}+1 \leq j_l -1$ for all $l = 1,..., m$, because we consider equivalence classes $[k_1,...,k_{n-1},0]$ with no adjacent zeros.  Let $l \in \{1,...,m \}$ and define $\hat{S} = - S$ as in Lemma <ref>. Then,

\begin{align}
\begin{split}
&\abs{\left \langle f, \left ( \prod_{i = j_{l-1}+1, \curvearrowright}^{j_l-1} S^{k_i}M_f \right) \textbf{1} \right \rangle} = \abs{ \left \langle \hat{S}^{k_{j_{l-1}+1}}f , \left ( \prod_{i = j_{l-1} + 2, \curvearrowright}^{j_l -1}M_f S^{k_i} \right) f \right \rangle } \\
&= \abs{ \left \langle \hat{S}^{k_{j_{l-1}+1}-\frac{1}{2}}\hat{S}^{\frac{1}{2}}f , \left ( \prod_{i = j_{l-1} + 2, \curvearrowright}^{j_l -1}M_f S^{k_i} \right) \hat{S}^{-\frac{1}{2}}\hat{S}^{\frac{1}{2}} f \right \rangle }  \\
&\leq \norm{\hat{S}^{k_{j_{l-1}+1}-\frac{1}{2}}}_2 \norm{\hat{S}^{\frac{1}{2}}f}_2 \left (\prod_{i = j_{l-1}+2}^{j_l-1}\norm{M_f}_2 \norm{S^{k_i}}_2  \right) \norm{\hat{S}^{-\frac{1}{2}}}_2 \norm{\hat{S}^{\frac{1}{2}}f}_2 \\
&= \norm{\hat{S}^{\frac{1}{2}}f}_2^2\lambda_1  \left (\frac{1}{\lambda_1} \right)^{\sum_{i = j_{l-1}+1}^{j_l - 1}k_i} \norm{f}_\infty^{j_{l}-j_{l-1}-2}.
\end{split}
\end{align}

In the first line we used selfadjointness of $S$ (Lemma <ref>$(a)$), and $M_f\textbf{1} = f$. In the second line we used Lemma <ref>$(d)$ (the conditions are satisfied because $\langle f, \textbf{1} \rangle = \pi(f) =  0$). Finally, in the last two lines we used the Cauchy-Schwartz inequality, submultiplicativity of the operator norm $\norm{\cdot}_2$, and Lemma <ref>$(b),(d)$ (to replace $\norm{S^r}$ respectively $\norm{\hat{S}^r}$ by $\left (\frac{1}{\lambda_1}\right )^r$),  and $\norm{M_f}_2 = \norm{f}_\infty $. Because $\hat{S}^{\frac{1}{2}}$ is selfadjoint, $\hat{S}^{\frac{1}{2}}\hat{S}^{\frac{1}{2}} = \hat{S}$ (see Lemma <ref>) and $\hat{\sigma}_f^2 = - 2 \langle f, Sf \rangle  $ (by definition) we have

\begin{equation*}
\norm{\hat{S}^{\frac{1}{2}}f}_2^2 = \langle \hat{S}^{\frac{1}{2}}f,\hat{S}^{\frac{1}{2}}f \rangle = \langle f, \hat{S}f \rangle = \frac{\hat{\sigma}_f^2}{2},
\end{equation*}

which proves the desired bound (<ref>).
Multiplying these $m$ bounds in (<ref>) yields (recalling (<ref>))

\begin{align}
\begin{split}
&|\Tr([k_1, ...,k_{n-1},0])| \leq \left(\frac{\hat{\sigma}_f^2\lambda_1}{2}\right)^m\left(\frac{1}{\lambda_1}\right)^{\sum_{i = 1}^n k_i}\norm{f}_{\infty}^{\sum_{l = 1}^m( j_l - j_{l-1} -2)} \\
&= \left(\frac{\hat{\sigma}_f^2\lambda_1}{2}\right)^{m-1}\left(\frac{1}{\lambda_1}\right)^{n-1}\norm{f}_{\infty}^{n-2m} \frac{\hat{\sigma}_f^2\lambda_1}{2} = \left(\frac{\hat{\sigma}_f^2 \lambda_1}{2 \norm{f}_\infty^2} \right )^{m-1}\left (\frac{\norm{f}_{\infty}^n}{\lambda_1^{n}} \right) \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right),
\end{split}
\end{align}

where in the first line we used $k_{j_l} = 0$ for all $l = 1,...,m $ and in the second line we used $j_0 = 0 $ and $j_m = n$.
But by using the Cauchy-Schwartz inequality and $\norm{S} = \frac{1}{\lambda_1}$ (Lemma <ref>$(b)$) it is easily checked that $ \frac{\hat{\sigma}_f^2 \lambda_1}{2 \norm{f}_\infty^2}  \leq 1$, so the above inequality implies the bound

\begin{equation}
\label{eq: bound_Tr[k_1,...,k_n]}
|\Tr([k_1,...,k_{n-1},0])| \leq \left (\frac{\norm{f}_{\infty}^n}{\lambda_1^{n}} \right) \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right),
\end{equation}

which is independent of $m$, the number of zeros in $[k_1,...,k_{n-1},0]$.
At last, using the above inequality we can now bound $\abs{\lambda_0^{(n)}}$ by bounding each trace in (<ref>);

\begin{equation}
\lambda_0^{(n)} = (-1)^n\sum_{[k_1,...,k_{n-1},0]}\Tr([k_1,...,k_{n-1}])
\end{equation}

and counting the number of equivalence classes $[k_1,...k_{n-1},0]$ that contribute to the sum in (<ref>). To count the number of contributing summands we group the equivalence classes with no adjacent zeros according to the number $m$ of zeros. Recall that these are the only equivalence classes that contribute to the sum and that necessarily $m\geq 1$. Let $\beta(n,m)$ be the number of equivalence classes $[k_1,...,k_n]$ with $m$ non-adjacent zeros. Let $\lfloor \cdot \rfloor $ denote the floor function. Then for $ m  > \lfloor \frac{n}{2} \rfloor $  there must exist two adjacent zeros and consequently $\beta(n,m) = 0$. For $1 \leq  m \leq \lfloor \frac{n}{2} \rfloor$ it can be shown  that (Lemma <ref>)

\begin{equation}
\label{eq: beta(n,m)}
\beta(n,m) = \frac{1}{n-1} \binom{n-1}{m} \binom{n-1-m}{n-2m}.
\end{equation}

So the total number $\beta_n$ of summands that contribute in (<ref>) is given by

\begin{equation}
\label{eq: beta_n}
\beta_n =\sum_{m = 1}^{\lfloor \frac{n}{2} \rfloor} \beta(n,m).
\end{equation}

Applying the bound (<ref>) on $\abs{\Tr([k_1,...,k_{n-1},0])}$ to (<ref>) yields

\begin{equation}
\abs{\lambda_0^{(n)}} \leq  \beta_n\left (\frac{\norm{f}_{\infty}^n}{\lambda_1^{n}} \right) \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right).
\end{equation}

Let $x := \frac{r \norm{f}_\infty}{\lambda_1}$, then the above inequality implies that (by summing over $n \geq 2$, recall that $\lambda_0^{(1)} = 0$)

\begin{equation}
\label{eq: lezaud_final_bound_lambda_0(r)}
\lambda_0(r) \leq  \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right) \sum_{n = 2}^\infty \beta_n x^n,
\end{equation}

which implies the first inequality of  (<ref>),  because

\begin{equation}
\Phi(x) = \sum_{n = 2}^\infty \beta_n x^n
\end{equation}

for $0 \leq x \leq \frac{1}{3}$ (Lemma <ref>). Finally, the second inequality of (<ref>) follows by the fact that

\begin{equation}
\Phi(x) \leq \frac{x^2}{1-2x}
\end{equation}

for $0 \leq x \leq \frac{1}{3}$
which is easy to check by noting that $\Phi(0) = 0$ and calculating that $\Phi'(x) \leq \frac{d}{dx}(\frac{x^2}{1-2x})$ for $0 \leq x \leq \frac{1}{3}$.

* An elementary calculation using factorials shows that $\beta(n,m)$ (defined in (<ref>)) can also be written as

\begin{equation}
\label{eq: def_beta(n,m)_lezaud}
\beta(n,m) = \frac{1}{m} \binom{n-m-1}{m-1} \binom{n-2}{n-m-1},
\end{equation}

which is the definition used by <cit.>. Thus, we have (c.f. (<ref>))

\begin{equation}
\label{eq: def_beta_n_lezaud}
\beta_n = \sum_{i = 1}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{m} \binom{n-m-1}{m-1} \binom{n-2}{n-m-1},
\end{equation}

which is the definition in <cit.>. However, in <cit.> the sum ends at $\lceil \frac{n}{2} \rceil $ ($\lceil \cdot \rceil $ denotes the ceil function, which is not correct; the sum should end at $\lfloor \frac{n}{2} \rfloor$, because if the number $m$ of  zeros in $[k_1,...k_n]$ is bigger than $\lfloor \frac{n}{2} \rfloor$ then there must exist two adjacent zeros and consequently $\beta(n,m) = 0$.

* In contrast to  <cit.>, which states that the bound (<ref>) even holds for $0 \leq r < \frac{\lambda_1}{2 \norm{f}}$, the proof presented in <cit.> just shows that the bound
(<ref>) holds for $0 \leq r < \frac{\lambda_1}{3 \norm{f}}$, because the series  $\sum_{n = 2} \beta_n x^n$ has convergence radius $\frac{1}{3}$ (Lemma <ref>), and consequently the bound (<ref>)

\begin{equation}
\lambda_0(r) \leq  \left( \frac{\hat{\sigma}_f^2\lambda_1^2}{2 \norm{f}_{\infty}^2} \right) \sum_{n = 2}^\infty \beta_n x^n,
\end{equation}

is trivial for $ \frac{r \norm{f}_\infty}{\lambda_1} = x > \frac{1}{3} $.

By computing the Fenchel conjugate of the above bound for $\lambda_0$ we get the following concentration inequalities.

Let $u \geq 0$, define

\begin{equation}
r_0 := \frac{\lambda_1}{2 \norm{f}_\infty} \left ( 1 -\left ( 1 + \frac{4 u \norm{f}_\infty
}{\lambda_1 \hat{\sigma}_f^2} \right )^{-\frac{1}{2}} \right ).
\end{equation}

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

for $0 \leq r < \frac{\lambda_1 }{2 \norm{f}_\infty }$. The following concentration inequalities hold:

* If $r_0 \leq \frac{\lambda_1}{3 \norm{f}_\infty} $, or equivalently $u \leq  \frac{2\hat{\sigma}_f^2\lambda_1}{\norm{f}_\infty}$, then

\begin{equation*}
G^*(u) :=  \sup_{ r \in \left [0, \frac{\lambda_1}{3 \norm{f}_\infty} \right ]} (r u - G(r)) = r_0 u - G(r_0)
\end{equation*}

and consequently

\begin{equation}
\label{eq: concentration_via_perturbation_a}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d \nu}{d \pi}}_2 \exp\left(-\frac{2tu^2}{\hat{\sigma}_f^2(1+ \sqrt{1+ \frac{4\norm{f}_\infty u}{\lambda_1 \hat{\sigma}_f^2}})^2} \right)
\end{equation}

* If $r_0  > \frac{\lambda_1}{3 \norm{f}_\infty}$, or equivalently $u >  \frac{2\hat{\sigma}_f^2\lambda_1}{\norm{f}_\infty}$,  then

\begin{equation*}
G^*(u) =  \sup_{ r \in \left [0, \frac{\lambda_1}{3 \norm{f}_\infty} \right ]} (r u - G(r)) = \frac{\lambda_1}{3 \norm{f}_\infty} u - G\left (\frac{\lambda_1}{3 \norm{f}_\infty} \right )
\end{equation*}

and consequently

\begin{equation}
\label{eq: concentration_via_perturbation_b}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq  \norm{\frac{d\nu }{ d \pi}}_2 \exp \left(- t \frac{\lambda_1}{3 \norm{f}_\infty} \left (u - \frac{\lambda_1 \hat{\sigma}_f^2}{2 \norm{f}_\infty} \right ) \right )
\end{equation}

As the bound (<ref>) of Lemma <ref> just was proven for
$0 \leq r < \frac{\lambda_1 }{3 \norm{f}_\infty }$ (and the presented proof just works for this range) we had to make a case distinction (whether $r_0 \leq \frac{\lambda_1}{3 \norm{f}_\infty})$ and obtain a weaker statement (but with a legitimate proof) than stated in <cit.>.

* For $\nu = \pi$ Theorem <ref>$(a)$ is exactly  Bernstein's inequality (Lemma <ref>) for $A_t$, which is sub-gamma on the right tail with variance $t \hat{\sigma}_f^2$ and scale parameter $\frac{2 \norm{f}_\infty}{\lambda_1}$ (Remark <ref>)

* We will later show in Theorem <ref> that Theorem <ref>$(a)$ actually holds for all $u \geq 0$ and obtain a sharper Bernstein-type  bound.

An elementary calculation shows that we have $r_0 \leq \frac{\lambda_1}{3 \norm{f}_\infty}$ if and only if
$u \leq  \frac{2\hat{\sigma}_f^2\lambda_1}{\norm{f}_\infty}$.
Recall that $G(r)$ is a bound for $\lambda_0(r)$ (Lemma <ref>), i.e. we have

\begin{equation}
G(r) \geq \lambda_0(r)
\end{equation}

for all $r \leq \frac{\lambda_1}{3 \norm{f}_\infty }$. Consequently, by Lemma <ref> the concentration inequality

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

holds for all $u \geq 0$.
To calculate $G^*(u) = \sup_{ r \in \left [0, \frac{\lambda_1}{3\norm{f}_\infty}\right]}(ur - G(r))$, we use Example <ref> with scale parameter $c = \frac{2 \norm{f}_\infty}{\lambda_1}$ and variance $v = \hat{\sigma}_f^2$. Let $u \geq 0$ and define

\begin{equation}
H(r) = ur - G(r)
\end{equation}

as in Example <ref>. By Example <ref> we have

\begin{equation}
\sup_{r \in \left [0, \frac{\lambda_1}{2 \norm{f}_\infty}\right)}H(r) = H(r_0).
\end{equation}

If $r_0 \leq \frac{\lambda_1}{3\norm{f}_\infty }$ then clearly

\begin{equation}
H(r_0) = \sup_{r \in \left [0, \frac{\lambda_1}{2 \norm{f}_\infty}\right)}H(r) =  \sup_{r \in \left [0, \frac{\lambda_1}{3\norm{f}_\infty}\right ]} H(r) = G^*(u).
\end{equation}
The desired concentration inequality (<ref>) of part $(a)$  follows by  plugging  the formula for $H^*(u) = H(r_0)$ from Example <ref> (see (<ref>)) into (<ref>). Thus, part $(a)$ is proved. Part $(b)$ can be proved as follows. We have $H'(0) = u \geq 0$ and by Example <ref>, the derivative $H'$ has a unique root in $[0, \frac{\lambda_1}{2 \norm{f}_\infty})$ located at $r_0$. Consequently $H' \geq 0$ in $[0,r_0]$ and $H$ is nondecreasing on $[0,r_0]$. So if $r_0 > \frac{\lambda_1}{3 \norm{f}_\infty}$, then $H$ is nondecreasing on $ \left [0 , \frac{\lambda_1}{3 \norm{f}_\infty} \right]$ and

\begin{equation}
G^*(u) = \sup_{r \in \left [0 , \frac{\lambda_1}{3 \norm{f}_\infty}\right ]} H(r) = H \left( \frac{\lambda_1}{3 \norm{f}_\infty}\right).
\end{equation}

Finally, the concentration inequality (<ref>) of part $(b)$ follows by explicitly computing $G^*(u) = H\left (\frac{\lambda_1}{3 \norm{f}_\infty} \right )$ and plugging it into (<ref>).

§.§.§ Concentration Inequalities via functional Inequalities

In this section we follow <cit.> and bound $\lambda_0(r)$ using a Poincaré and $F$-Sobolev inequality  to obtain concentration inequalities (invoking Lemma <ref>) . For a more general presentation on how functional inequalities (like the aforementioned) relate to the theory of Markov processes see e.g. <cit.>. The concentration inequalities of this section are formulated  in Theorems <ref> and <ref>, which are our versions of <cit.> and <cit.>. The most relevant material of Section <ref> is  Lemma <ref> and Example <ref>.
We now define the inequalities of interest:
(Poincaré inequality)
We say that $L$ satisfies a Poincaré inequality with constant $C > 0$ if for all $g \in L^2(\pi)$ (c.f. <cit.>)

\begin{equation}
\label{eq: poincare_inequality}
\text{Var}_\pi(g)  \leq - C \langle Lg, g \rangle = - C \left \langle \frac{L+L^*}{2}g, g  \right \rangle .
\end{equation}

Here $\text{Var}_\pi(g) = \pi(g^2) - \pi(g)^2$ denotes the variance of $g$ with respect to $\pi$.

($F$-Sobolev inequality)
Let $F : (0, \infty) \rightarrow \F{R}$ be a strictly increasing, continuous, concave function satisfying $F(1) = 0$ and $\lim_{t \to \infty } F(t) = \infty$. Then $F^{-1}$ exists and is defined on $(F(0), \infty)$, where $F(0) := \lim_{t \downarrow 0}F(t)$ (note that this limit exists in $[-\infty, 0)$). In addition, assume that

\begin{equation}
\label{eq: F-sobolev_multiplicative_condition}
F(st) \leq F(t) + F(s)
\end{equation}

for all $s, t > 0$. We say $L$ satisfies a $F$-Sobolev inequality (c.f. <cit.>) if

\begin{equation}
\label{eq: F-sobolev_inequality}
\pi( g^2 F(g^2)) \leq  - \langle Lg, g \rangle = - \left \langle \frac{L+L^*}{2}g, g \right \rangle
\end{equation}

for all $g \in L^2(\pi)$ with $\norm{g}_2 = 1$, where $ 0 \cdot F(0) = 0$.

* (Poincaré inequality and spectral gap) By writing $g = h + a\textbf{1}$ with $h \in \{\textbf{1}\}^{\perp}$, using $\text{Var}_\pi(g) = \text{Var}_\pi(h) = \norm{h}_2^2$, and Lemma <ref>$(a)$ it is easily seen that the Poincaré inequality holds if and only if

\begin{equation}
\label{eq: poincare_1}
\norm{h}_2^2 \leq - C \left \langle \frac{L+L^*}{2}h, h \right \rangle
\end{equation}

for all $h \in \{\textbf{1}\}^{\perp}$. But by diagonalizing $\frac{L+L^*}{2}$ and using Lemma <ref>$(a),(c)$ it is straightforward to check that (<ref>) is equivalent to

\begin{equation}
\label{eq: spectral_gap_inequality}
C \geq \frac{1}{\lambda_1}
\end{equation}

where $\lambda_1 = \min \limits_{\lambda \in \sigma \left( \frac{L+L^*}{2} \right) \backslash \{0\}} \abs{\lambda}$ is the spectral gap. Thus, the Poincaré inequality with constant $C$ is equivalent to the above  inequality for the spectral gap.

* (Log-Sobolev inequality) If $F = C \log$ for some $C > 0 $, the $F$-Sobolev inequality is called log-Sobolev inequality with constant $\frac{1}{C}$ (c.f. <cit.>).

Using  the above inequalities we can derive upper bounds for $\lambda_0(r)$ to then apply Lemma <ref> and obtain concentration inequalities. The following two bounds hold:

Denote by   $\lambda_1$ the spectral gap of $\frac{L+L^*}{2}$ and let $C \geq \frac{1}{\lambda_1}$, i.e. $L$ satisfies a Poincaré inequality with constant $C$. Then,

for all $0 \leq r < \frac{1}{C \norm{f}_\infty}$

\begin{equation}
\label{eq: poincare_bound_lambda_0(r)}
\lambda_0(r) \leq \frac{r^2\mathrm{Var}_\pi(f)C}{1 - r C\norm{f}_\infty}.
\end{equation}

The above bound is found in <cit.>. There this bound is stated as

\begin{equation}
\label{eq: guillin_bound_lambda_0(r)}
\Lambda(\lambda V) \leq \frac{\lambda^2\text{Var}_\mu(V)}{\frac{1}{C_P} - \lambda} = \frac{\lambda^2C_P\text{Var}_\mu(V)}{1 - C_P\lambda},
\end{equation}

where (see <cit.>) $\mu$ denotes the invariant measure,

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

and $C_P$ is the constant in the Poincaré inequality <cit.>. Furthermore, <cit.> assumes that $\norm{V}_\infty = 1 $. In our case $V = f$, $\mu = \pi$, $\lambda = r$, $C_P = C$ and consequently (as $\norm{f}_\infty = 1$ is assumed)  (<ref>) is exactly the bound of Lemma <ref>.

* Note the similarity of this bound to the bound obtained using perturbation theory in Lemma <ref> . In particular, this bound implies (as in Remark <ref>) that for $\nu = \pi$ $A_t$ is sub-gamma (on the right tail) with variance $2t C \text{Var}_\pi(f)$ and scale parameter $\frac{1}{C\norm{f}_\infty}$.

* The best bound (i.e. the sharpest) is obtained for $C = \frac{1}{\lambda_1}$, consistent with the fact that  the Poincaré inequality is also the sharpest for $C = \frac{1}{\lambda_1}$. This follows because if $C_1 \leq C_2$, then

\begin{equation}
\frac{r^2\mathrm{Var}_\pi(f)C_1}{1 - r C_1\norm{f}_\infty} \leq \frac{r^2\mathrm{Var}_\pi(f)C_2}{1 - r C_2\norm{f}_\infty}
\end{equation}

for all $ 0 \leq r < \frac{1}{C_2 \norm{f}_\infty}$.

To bound $\lambda_0(r)$
we follow the proof of <cit.> but modify it to make it applicable to a general $f \in L^2(\pi)$ with $\pi(f) = 0$ (<cit.> assumes that $\norm{f}_\infty = 1)$. Let $K := \frac{1}{C}$, then by applying the Poincaré inequality (<ref>) to Lemma <ref> we obtain

\begin{align}
\begin{split}
\label{eq: bound_lambda_0(r)_with_poincare}
\lambda_0(r) &\leq \sup\{ \langle rM_fg,g \rangle - K \text{Var}_\pi(g) \;| \; g \in L^2(\pi) , \norm{g} = 1 \} \\
&= \sup  \left \{ \frac{1}{1+\varepsilon^2} \langle rf, \textbf{1} + 2 \varepsilon h + \varepsilon^2 h^2 \rangle - K \frac{\varepsilon^2}{1+ \varepsilon^2}  \;| \; h \in \{ \textbf{1} \}^{\perp}, \norm{h} = 1, \varepsilon \geq 0 \right \} \\
&= \sup  \left \{ \frac{\varepsilon}{1+\varepsilon^2}( 2 r \langle f, h \rangle + \varepsilon \langle rf - K \textbf{1}, h^2 \rangle ) \;| \; h \in \{ \textbf{1} \}^{\perp}, \norm{h} = 1, \varepsilon \geq 0 \right \} \\
&\leq \sup \{ \varepsilon ( 2r \norm{f}_2 + \varepsilon ( r \norm{f}_\infty - K) \;| \; \varepsilon \geq 0 \}.
\end{split}
\end{align}

In the second line we wrote $g = \frac{\textbf{1}+ \varepsilon h}{\sqrt{1+\varepsilon^2}}$ with $h \in \{\textbf{1} \}^{\perp}, \norm{h}_2 = 1$ and used $\text{Var}_\pi(g) = \frac{\varepsilon^2}{1+ \varepsilon^2} $. In the third line we used $\langle f, \textbf{1} \rangle = 0$ and $ \langle \textbf{1}, h^2 \rangle = 1$. Finally, in the last line we used the Cauchy-Schwartz inequality  $\langle f, h \rangle \leq \norm{f}_2 \cdot 1$ and the estimates $\frac{1}{1+\varepsilon^2} \leq 1$, and

\begin{equation*}
\langle rf - K \textbf{1}, h^2 \rangle  = \pi((rf - K \textbf{1})h^2) \leq \pi((r\norm{f}_\infty - K)h^2) = r\norm{f}_\infty - K.
\end{equation*}

Notice that if $r \geq \frac{K}{\norm{f}_\infty}$, then (<ref>) is the trivial estimate $\lambda_0(r) \leq \infty $. So assume that $r < \frac{K}{\norm{f}_\infty}$. Then, to calculate the supremum in (<ref>)  note that (by an elementary calculation)  the quadratic polynomial

\begin{equation*}
P(\varepsilon) = \varepsilon^2(r \norm{f}_\infty -K) + \varepsilon 2 r \norm{f}_2
\end{equation*}

reaches a maximum at $\varepsilon_0 = \frac{r \norm{f}_2}{K- r \norm{f}_\infty }$. Finally, the desired bound on $\lambda_0(r)$ (<ref>) follows by (<ref>), as

\begin{equation}
\label{eq: maximum_quadratic_polynomial_poincare}
\lambda_0(r) \leq P(\varepsilon_0) =  P \left( \frac{r \norm{f}_2}{K- r \norm{f}_\infty }\right) = \frac{r^2 \norm{f}_2^2}{K- r \norm{f}_\infty } = \frac{r^2\frac{\text{Var}_\pi(f)}{K}}{1 - r \frac{\norm{f}_\infty}{K}}.
\end{equation}

Suppose $L$ satisfies an F-Sobolev inequality.
Let $r_f := \frac{F(0)}{\min_{x \in E}f(x)}$, so that $F^{-1}(rf)$ is defined for all $0 \leq r < r_f $. Then for all $0 \leq r < r_f$ we have

\begin{equation}
\label{eq: bound_lambda_0(r)_F-sobolev}
\lambda_0(r) \leq F( \pi( F^{-1}( rf))).
\end{equation}

The above bound is stated in <cit.> as

\begin{equation}
\label{eq: guillin_bound_F_sobolev}
\Lambda(\lambda V) \leq F \left ( \int F^{-1}(\lambda V) d\mu \right ).
\end{equation}

Recall (see Remark <ref>) $ V = f, \lambda = r,  \Lambda(\lambda V) = \lambda_0(r)$ so  this is exactly the bound of Lemma <ref>.

Notice that $r_f > 0$ because $F(0) < 0 $ and $ \min_{x \in E}f(x) < 0$. Indeed, $F$ is strictly increasing and $F(1) = 0$, so $F(0) = \lim_{ t \downarrow 0}F(t)  < 0$. Furthermore, $\sum_{x \in E }f(x) \pi_x = 0$ and $f$ is not constant, so $\min_{x \in E}f(x) < 0$.

We follow the proof of <cit.> and add computational details. Use  Lemma <ref> and the $F$-Sobolev inequality (<ref>) to obtain

\begin{align}
\begin{split}
\label{eq: bound_lambda_0(r)_F_sobolev_prototype}
& \lambda_0(r) \leq \sup \{ \langle rM_fg, g \rangle - \pi( g^2 F(g^2)) \; | \; \norm{g}_2 = 1 \}\\
&= \sup \{ \pi((rf - F(g^2))g^2) \; | \; \norm{g}_2 = 1 \}.
\end{split}
\end{align}

The desired bound on $\lambda_0(r)$ (<ref>) follows now from the above equation and the following estimate:
If $\norm{g}_2 = 1$ and $0 \leq r < r_f$, then

\begin{align}
\begin{split}
\label{eq: estimate_F_sobolev}
& \pi((rf- F(g^2))g^21_{\{ g \neq 0 \}}) \leq \pi \left ( F \left (\frac{F^{-1}(rf)}{g^2} \right) g^2 1_{\{ g \neq 0 \}} \right )  \\
&\leq F \left ( \pi \left ( \frac{F^{-1}(rf)}{g^2} g^2 1_{\{ g \neq 0 \}} \right) \right ) = F ( \pi( F^{-1}(rf) 1_{\{ g \neq 0 \}})) \\
&\leq F( \pi( F^{-1}(rf)),
\end{split}
\end{align}

where the first line we used the inequality

\begin{equation*}
(rf - F(g^2))1_{\{ g \neq 0 \}} \leq F \left (\frac{F^{-1}(rf)}{g^2} \right) 1_{\{ g \neq 0 \}},
\end{equation*}

which follows from (<ref>)

\begin{equation}
F(st) \leq F(s) + F(t)
\end{equation}

with $t = \frac{F^{-1}(rf)}{g^2} $ and $s = g^2$. In the second line we used Jensen's inequality with the concave function $F$ and with respect to integration with the probability measure $g^2 \pi$. In the last line the monotonicity of $F$ and $F^{-1}(rf) > 0$ were used. We conclude by plugging the estimate (<ref>) into (<ref>).

Similarly as in Section <ref> we use the above bounds for $\lambda_0(r)$ to obtain the following concentration inequalities.

Let $\tilde{\sigma}_f^2 := 2 \frac{Var_\pi(f)}{\lambda_1 }$ In our setting the following concentration inequality holds:

\begin{equation}
\label{eq: concentration_via_poincare}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d \nu}{d \pi}}_2 \exp\left(-\frac{2tu^2}{\tilde{\sigma}_f^2(1+ \sqrt{1+ \frac{2\norm{f}_\infty}{\lambda_1 \tilde{\sigma}_f^2}})^2} \right).
\end{equation}

The above result is a generalization and reformulation of <cit.>: The proposition <cit.> states that  (<cit.> used the notation $V = f$, $R = u$, $\mu = \pi$, $C_P = C$)

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

for $\norm{f}_\infty = 1$ and $0 < u \leq 1$,

\begin{equation}
A(u) = \frac{1}{C} \left ( 1 - \sqrt{1- \frac{u}{u+ \text{Var}_\pi(f)}} \right ) \left( u - \frac{\text{Var}_\pi(f) \left (1- \sqrt{1- \frac{u}{u + \text{Var}_\pi(f)}} \right)}{\sqrt{1- \frac{u}{u+ \text{Var}_\pi(f)}}} \right)
\end{equation}

and  $C = \frac{1}{\lambda_1}$ (we choose $C$ to be the optimal constant for the Poincaré inequality). As the above bound (<ref>) is quite intricate it is not directly clear how Theorem <ref> implies <cit.> as a special case. However, this follows from the proof (found in <cit.>) of <cit.>: We have
(see <cit.>: 'The supremum is attained for ... and is equal to $A$')

\begin{equation}
A(u) = \sup_{r \in [0, \frac{1}{C})} \left (ur - \frac{r^2 \text{Var}_\pi(f)}{\frac{1}{C}- r}\right ) = \sup_{r \in [0, \frac{1}{C})}\left ( ur - \frac{r^2 C\text{Var}_\pi(f)}{1- Cr} \right) ,
\end{equation}

where $C = \frac{1}{\lambda_1}$. This implies (by using Example <ref> with variance $v = \tilde{\sigma}_f^2$ and scale parameter $c =  \frac{1}{\lambda_1}$) that

\begin{equation}
A(u) = -\frac{2u^2}{\tilde{\sigma}_f^2(1+ \sqrt{1+ \frac{2}{\lambda_1 \tilde{\sigma}_f^2}})^2}.
\end{equation}

Thus, <cit.> is a special case of Theorem <ref>.

* For $\nu = \pi$ Theorem <ref> is exactly  Bernstein's inequality (c.f. Lemma <ref>) for $A_t$, which is sub-gamma on the right tail with variance $t \Tilde{\sigma}_f^2$ and scale parameter $\frac{ \norm{f}_\infty}{\lambda_1}$ (Remark <ref>)

* We will later obtain in Theorem <ref> a sharper Bernstein-type  bound.

* The used constant for the Poincaré inequality is $C = \frac{1}{\lambda_1}$, as this yields the sharpest bound (c.f. Remark <ref>)

The proof is similar to the proof of Theorem <ref>. Let

\begin{equation}
G(r) := \frac{r^2\frac{\text{Var}_\pi(f)}{\lambda_1}}{1 - r \frac{\norm{f}_\infty}{\lambda_1}}   =\frac{r^2\tilde{\sigma}_f^2}{2(1 - r \frac{\norm{f}_\infty}{\lambda_1})}
\end{equation}

for $r \in \left [ 0, \frac{\lambda_1}{\norm{f}_\infty} \right)$ be the bound for $\lambda_0(r)$ of Lemma <ref> for $C = \frac{1}{\lambda_1}$. Then, invoking Lemma <ref> yields

\begin{equation}
\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 the Fenchel conjugate is taken with respect to $\left [0, \frac{\lambda_1}{\norm{f}_\infty}\right)$.
The claim now follows by computing $G^*(u)  $ using Example <ref> with variance $v = \Tilde{\sigma}_f^2$ and scale factor $c = \frac{\norm{f}_\infty}{\lambda_1}$.

Suppose that the MJP satisfies an $F$-Sobolev inequality. Then,

\begin{equation}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d \nu}{d \pi}}_2 \exp( - t \sup_{ r \in [0, r_f)} (ru -F(\pi( F^{-1}(rf)))))
\end{equation}

The corresponding Theorem in <cit.> is the second part of <cit.>. Using the notation of <cit.> we have

\begin{equation}
H_c^*(a) = \sup_{ r \in [0, r_f)} (ra -F(\pi( F^{-1}(rf)))).
\end{equation}

* Unlike for the Poincaré inequality, which is satisfied in our setting for $C \geq \frac{1}{\lambda_1}$ , for a general $F$ the $F$-Sobolev inequality may not be satisfied, thus we need the extra assumption.

* If $\nu = \pi$ and $F = C \log $ (for $C > 0$), we get a continuous time analogue of Chernoff's inequality for sum of i.i.d random variables (see Corollary <ref>). Indeed, an elementary calculation shows that

\begin{align}
\begin{split}
&\sup_{ r \in [0, r_f)} (ru -F(\pi( F^{-1}(rf)))) = C \sup_{r \geq 0}(ru - \log \pi(e^{rf})) \\
&=  C \sup_{r \geq 0}(ru - \log \F{E}_\pi(e^{rf(X_0)})) =  C \Psi_{f(X_0)}^*(u),
\end{split}
\end{align}

\begin{equation}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq e^{-tC \Psi_{f(X_0)}^*(u) }
\end{equation}

Follows immediately by recalling (see Lemma <ref>).

\begin{equation}
\lambda_0(r) \leq F(\pi( F^{-1}(rf)))
\end{equation}

for all $ r \in [0, r_f)$ and then applying Lemma <ref> with $G(r) = F(\pi( F^{-1}(rf))) $.

§.§.§ Concentration Inequalities via Information Inequalities

In this section we follow <cit.> and use a inequality for the so called Donsker-Varadhan information to  derive a concentration inequality. Finally, we use this inequality to extend Theorem <ref>, Lemma <ref>, and sharpening the Bernstein-type bounds Theorem <ref>$(a)$ and Theorem <ref>. The main results of this section are Theorems <ref> and  <ref>, which are our versions of <cit.> and <cit.>. The most relevant background knowledge for this section is Theorem <ref>, Example <ref> and the notion of reduced resolvent (Section <ref>).

Denote by $\mathcal{M}_1(E)$ the set of all probability measures on $E$. The  Donsker-Varadhan information $ I(\beta | \mu)$ for $\beta,\mu \in \mathcal{M}_1(E)$ is defined as (c.f. <cit.>)

\begin{equation}
\label{eq: def_donsker_varadhan_info}
I(\beta | \mu) :=
\begin{cases}
- \left \langle L \left(\frac{d\beta}{d\mu} \right)^{\frac{1}{2}}, \left (\frac{d\beta}{d\mu} \right)^{\frac{1}{2}} \right\rangle \; &; \; \beta << \mu \\
\infty \; &; \; \text{otherwise}, \\
\end{cases}
\end{equation}

where $\beta << \mu$ means that $\beta$ is absolutely continuous with respect to $\mu$.

In our case, where $\pi$ is the invariant measure of an irreducible MJP
we always have $I(\nu | \pi) < \infty $ for all $\nu \in \mathcal{M}_1(E)$, because the Radon-Nikodym derivative $\frac{d\nu}{d\pi}(x) = \frac{\nu_x}{\pi_x}$ always exists as $\pi_x > 0$ for all $x \in E$ (by Theorem <ref>).

We start by proving

Let $I$ be defined as in Theorem <ref>, i.e.

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

\begin{equation}
I(u) = \inf \{ I(\beta | \pi) \; | \; \beta \in \mathcal{M}_1(E), \beta(f) = u \}
\end{equation}

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

The above lemma is not directly stated in <cit.> but implicitly used as follows. To prove <cit.>, <cit.> uses <cit.> (which is Theorem <ref>), which states (in our case)

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

However, this theorem is formulated in <cit.> as (<cit.> used the notation $g = f, \beta = \nu , \mu = \pi, r = u$)

\begin{equation}
\label{eq: bernstein_theorem_2.1}
\F{P}_\nu \left (\frac{A_t}{t} > u \right ) \leq \norm{\frac{d\nu}{d \pi}}_2 e^{- t \tilde{I}(u-)}
\end{equation}

for $ t,u > 0$, where  $\tilde{I}(u) = \inf \{ I(\beta | \pi) \; | \; \beta \in \mathcal{M}_1(E), \beta(f) = u \}$ and $\tilde{I}(r-) = \lim_{\varepsilon \downarrow 0}I(r-\varepsilon) $. The authors do not explain further how (<ref>) implies (<ref>) and it is not directly clear that $I(u) = \tilde{I}(u-)$. Thus, we decided to formulate and prove the above lemma.

Our starting point is (<ref>) (see Theorem <ref>):

\begin{equation}
\label{eq: infimum_over_smaller_set_1}
\lambda_0^*(u) = \sup_{ r \in \F{R}}(r u - \lambda_0(r)) = \inf \{ - \langle Lg, g \rangle \; | \, \norm{g}_2 = 1, \langle M_fg, g \rangle = u \}.
\end{equation}

Furthermore, the following inequality holds for all $g \in L^2(\pi)$:

\begin{equation}
\label{eq: infimum_over_smaller_set_2}
- \langle L g, g \rangle \geq -  \langle L \abs{g}, \abs{g} \rangle.
\end{equation}

This can be seen as follows.
Using the definition of the contraction semigroup $(P_t)_{t \geq 0}$ of the MJP (see (<ref>)), it follows that

\begin{equation}
\label{eq: inequality_semigroup}
P_t\abs{g} \geq \abs{P_tg}
\end{equation}

for all $t \geq 0$.
Consequently, for all $ t \geq 0$

\begin{equation*}
\langle P_tg, g \rangle  = \pi(P_tg g) \leq  \pi(P_t\abs{g}\abs{g}) = \langle P_t\abs{g}, \abs{g} \rangle,
\end{equation*}

with equality for $t = 0$. Thus, the above inequality (<ref>) extends to the derivative at  $t = 0$, i.e.

\begin{equation*}
\langle Lg, g \rangle \leq \langle L\abs{g}, \abs{g} \rangle,
\end{equation*}

which implies (<ref>). Notice that $\norm{g}_2 = \norm{\abs{g}}_2$ and $\langle M_fg,g \rangle = \langle M_f \abs{g}, \abs{g} \rangle $. Combining these facts with
(<ref>) and (<ref>) yields

\begin{align}
\begin{split}
\lambda_0^*(u) &= \inf \{ - \langle Lg, g \rangle \; | \, \norm{g}_2 = 1, \langle M_fg, g \rangle = u \} \\
&= \inf \{ - \langle L g, g \rangle \; | \; \norm{g}_2 = 1, \langle M_fg,g \rangle = u, g \geq 0 \} .
\end{split}
\end{align}

To complete the proof note that there is a one to one correspondence of
$\{ \beta \in \mathcal{M}_1(E) \; | \; \beta(f) = u \}$ with $ \{ g \in L^2(\pi) \; | \; \norm{g}_2 = 1, \langle M_fg,g \rangle = u, g \geq 0 \} $ via the two functions

\begin{equation*}
\mathcal{M}_1(E)\rightarrow L^2(\pi); \; \beta \mapsto \left ( \frac{d\beta}{d\pi} \right)^{\frac{1}{2}} \; \text{and} \;  L^2(\pi) \rightarrow \mathcal{M}_1(E); \; g \mapsto g^2\pi  .
\end{equation*}

Furthermore, by the definition of the Donsker-Varadhan information  for the corresponding $\beta$ and $g$ by we have

\begin{equation*}
I(\beta | \pi) = - \langle L g, g \rangle.
\end{equation*}

Finally, using  this correspondence we get

\begin{align}
\begin{split}
& \inf \{ I(\beta | \pi) \; | \; \beta \in \mathcal{M}_1(E), \beta(f) = u \} \\
&= \inf \{ - \langle L g, g \rangle \; | \; \norm{g}_2 = 1, \langle M_fg,g \rangle = u, g \geq 0 \} \\
&= \lambda_0^*(u).
\end{split}
\end{align}

Now, using the above expression for $\lambda_0^*(u)$

\begin{equation}
\lambda_0^*(u) = \inf \{ I(\beta | \pi) \; | \; \beta \in \mathcal{M}_1(E), \beta(f) = u \},
\end{equation}

and assuming additionally an inequality involving the Donsker-Varadhan information one
can derive concentration inequalities using the following theorem.

Let $\alpha : [0, \infty) \rightarrow [0, \infty]$ be some function satisfying

\begin{equation}
\label{eq: condition_concentration_via_information}
\alpha(\beta(f)) \leq I (\beta | \pi)
\end{equation}

for all $\beta \in \mathcal{M}_1(E)$ such that $\beta(f) \geq 0$.

\begin{equation}
\label{eq: concenration_inequality_information}
\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}

\begin{equation}
\label{eq: bound_lambda_0(r)_information}
\lambda_0(r) \leq \alpha^*(r)
\end{equation}

for all $r \geq 0$, where $\alpha^*$ denotes the Fenchel conjugate of $\alpha$ with respect to $\F{R}_{ \geq 0}$.

A similar theorem as Theorem <ref> is stated  in <cit.>. Hereby, statements <cit.>$(a),(c),(e)$ correspond to (<ref>), (<ref>),(<ref>). However, we reformulated <cit.> as follows:  <cit.> considers a symmetric Markov process, assumes left continuity and convexity of $\alpha$, and states equivalence of (<ref>), (<ref>) and (<ref>). For our purposes just the implications $\eqref{eq: condition_concentration_via_information} \Rightarrow \\ \eqref{eq: concenration_inequality_information}, \eqref{eq: bound_lambda_0(r)_information}$ are of interest as we use Theorem <ref> to obtain a Bernstein-type  bound (c.f. Theorem <ref>). Furthermore, the proof of the implication $\eqref{eq: concenration_inequality_information} \Rightarrow \eqref{eq: condition_concentration_via_information}$ uses large deviation theory for symmetric Markov processes (c.f. <cit.>; cited in <cit.>), so we can not generalize directly this proof to the general, non-symmetric case. Furthermore, for the implications of interests we do not  need to assume that $\alpha$ is convex and left continuous.

Combining the assumption (<ref>)

\begin{equation}
\alpha(\beta(f)) \leq I (\beta | \pi)
\end{equation}

for all $\beta \in \mathcal{M}_1(E)$ such that $\beta(f) \geq 0$
with Lemma <ref>, which states that

\begin{equation}
\lambda_0^*(u) = \inf \{ I(\beta | \pi) \; | \; \beta \in \mathcal{M}_1(E), \beta(f) = u \},
\end{equation}

yields  $\alpha(u) \leq \lambda_0^*(u)$ for all $u \geq 0$. Thus, the concentration inequality (Theorem <ref>)

\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)}.
\end{equation}

\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 all $u \geq 0 $.
To prove the second statement; $\lambda_0(r) \leq \alpha^*(r)$ for all $r \geq 0$, recall that (Remark <ref>$(a)$)
$\lambda_0^*(u) \geq 0$ for all $u \in \F{R}$. Furthermore, by the proof of Theorem <ref> (see (<ref>) and use $I(u) = \lambda^*_0(u)$) we have

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

for all $r \in \F{R}$. Now, if $r \geq 0$, then, because $\lambda_0^*(u) \geq 0$, it follows that the above supremum can be taken over $u \in \F{R}_{\geq 0}$, i.e.

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

for $r \geq 0$. Thus, the inequality $\alpha(u) \leq \lambda_0^*(u)$ for $u \geq 0 $ implies   (c.f. Lemma <ref>$(d)$)

\begin{equation}
\lambda_0(r) \leq \alpha^*(r)
\end{equation}

for all $r \geq 0$.

Now, using  the above theorem  we can extend Theorem <ref>, Lemma <ref> and Theorem <ref> by choosing

\begin{equation*}
\alpha(u) = -\frac{2u^2}{\hat{\sigma}_f^2 \left (1+ \sqrt{1+ \frac{2\norm{f^+}_\infty u}{\lambda_1\hat{\sigma}_f^2}}\right)^2},
\end{equation*}

where $\Hat{\sigma}_f^2 = - \langle Sf, f \rangle$ and $\lambda_1 = \min_{\lambda \in \sigma \left ( \frac{L+L^*}{2} \right)\backslash \{0 \} }$ are defined as in Theorem <ref>, and $f^+ = \max \{0, f \}$ denotes the nonnegative part of $f$.

The following  concentration inequality holds. For all $u \geq 0$

\begin{equation}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d \nu}{d \pi}}_2 \exp\left(-\frac{2tu^2}{\hat{\sigma}_f^2 \left (1+ \sqrt{1+ \frac{2 \norm{f_+}_\infty u}{\lambda_1 \hat{\sigma}_f^2}} \right )^2} \right),
\end{equation}

where $\Hat{\sigma}_f^2 = - \langle Sf, f \rangle$ and $\lambda_1 = \min_{\lambda \in \sigma \left ( \frac{L+L^*}{2} \right)\backslash \{0 \} } \abs{\lambda} $ are defined as in Theorem <ref> and $f^+ = \max \{0, f \}$ denotes the nonnegative part of $f$. Furthermore,

\begin{equation}
\label{eq: extension_lezaud_bound_lambda_0(r)}
\lambda_0(r)  \leq \frac{r^2\frac{\hat{\sigma}_f^2}{2}}{1-\left(\frac{\norm{f_+}_{\infty}}{\lambda1}\right) r}
\end{equation}

for all $0 \leq r < \frac{\lambda_1}{ \norm{f_+}_\infty}$.

* The above theorem implies that Lemma <ref> holds for $0\leq r < \frac{\lambda_1}{2 \norm{f}_\infty }$.

* The above Bernstein-type concentration inequality is sharper than the previous Bernstein-type concentration inequalities; Theorem <ref>$(a)$ and Theorem <ref>. Indeed, this follows by direct comparison using $\norm{f^+}_\infty \leq \norm{f}_\infty$ and $\hat{\sigma}_f^2 \leq \Tilde{\sigma}_f^2$, where the latter inequality follows from the Cauchy-Schwartz inequality.

We follow the proof idea of <cit.>, add computational details and generalize it for the non-symmetric case. Let

\begin{equation*}
\alpha(u) = \frac{2u^2}{\hat{\sigma}_f^2 \left (1+ \sqrt{1+ \frac{2\norm{f^+}_\infty u}{\lambda_1\hat{\sigma}_f^2}}\right )^2}.
\end{equation*}

The claim follows by Theorem <ref> if we
show that $\alpha $
satisfies the condition (<ref>) of Theorem <ref>, i.e.

\begin{equation}
\label{eq: condition_alpha}
\alpha(\beta(f)) \leq I (\beta | \pi)
\end{equation}

for all $\beta \in \mathcal{M}_1(E)$ with $\beta(f) \geq 0$. An elementary calculation shows that $\alpha $ is strictly increasing and its inverse is given by (c.f. <cit.>)

\begin{equation*}
\alpha^{-1}(s) = \sqrt{2 \hat{\sigma}_f^2 s} + \frac{\norm{f^+}_\infty}{\lambda_1} s
\end{equation*}

for $s \geq 0$. Thus, the condition (<ref>) is equivalent to

\begin{equation}
\label{eq: conditition_beta(f)}
\beta(f) \leq \sqrt{2 \hat{\sigma}_f^2 I (\beta | \pi)} + \frac{\norm{f^+}_\infty}{\lambda_1} I (\beta | \pi)
\end{equation}

for all $\beta \in \mathcal{M}_1(E)$ with $\beta(f) \geq 0$.
Let $\beta \in \mathcal{M}_1(E)$ and let $g := (\frac{d\beta}{d\pi})^{\frac{1}{2}}$. We use $\pi(f) = 0$ to  rewrite

\begin{equation}
\label{eq: beta(f)}
\beta(f) = \pi(fg^2) = \pi(f [(g - \pi(g))^2 + 2 g \pi(g)]) = 2 \pi(g) \langle f, g \rangle + \pi( f(g - \pi(g))^2) .
\end{equation}

We show (<ref>)  by bounding both summands of the right hand side of the above equation. Let $K_1 := 2 \pi(g) \langle f, g \rangle$ and $K_2 := \pi( f(g - \pi(g))^2)$.
The first summand $K_1$ can be bounded by the two inequalities

\begin{equation}
\label{eq: first_inequality}
\pi(g) \leq \pi(g^2)^{\frac{1}{2}} = 1,
\end{equation}

\begin{equation}
\label{eq: second_inequality}
\langle f, g\rangle  \leq \sqrt{\frac{\Hat{\sigma}_f^2}{2}I (\beta | \pi)},
\end{equation}

\begin{equation}
K_1 \leq \sqrt{2\Hat{\sigma}_f^2I (\beta | \pi)}.
\end{equation}

Hereby (<ref>)
follows from Jensens inequality and  (<ref>) can be the derived as follows. As $- (L + L^*)$ is positive semidefinite (Lemma <ref>$(d)$),

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

defines a symmetric, positive semidefinite, bilinear form on $L^2(\pi)$. Furthermore, we have  $f = \frac{L+L^*}{2}Sf = S\frac{L+L^*}{2}f  $ (by Definition <ref>). Consequently, using the Cauchy-Schwartz inequality for $b$ yields

\begin{align*}
\begin{split}
\langle f, g\rangle &= \left \langle -S f,-\frac{L+L^*}{2} g \right \rangle  = b(-Sf, g) \\
&\leq \sqrt{\langle -Sf, f \rangle \left   \langle -\frac{L+L^*}{2}g, g \right \rangle } = \sqrt{\frac{\Hat{\sigma}_f^2}{2}I (\beta | \pi)},
\end{split}
\end{align*}

which proves (<ref>).
Finally, the second term $K_2$ can be bounded using the Poincaré-inequality (<ref>) with constant $C = \frac{1}{\lambda_1}$,  yielding

\begin{align*}
K_1 &=  \pi( f(g - \pi(g))^2) \leq \pi( f^+(g - \pi(g))^2)  \leq   \norm{f^+}_\infty \mathrm{Var}_\pi(g) \\
&\leq \frac{\norm{f^+}_\infty}{\lambda_1} \langle - Lg,g \rangle = \frac{\norm{f^+}_\infty}{\lambda_1} I (\beta | \pi).
\end{align*}

Combining the bounds for both summands $K_1$ and $K_2$ of the right hand side of (<ref>) yields the desired inequality (<ref>).

We extended the proof of <cit.> (found on <cit.>) to the nonsymmetric case. The central 'trick' was to replace $L$ by $\frac{L+L^*}{2}$ in scalar products (which is easily possible because of the finite dimensionality of $L^2(\pi)$) and work with the reduced resolvent of $\frac{L+L^*}{2}$.

§ SUMMARY, FURTHER THEORY AND APPLICATIONS IN PHYSICS

§.§ Summary

In this thesis we derived bounds in Theorems <ref>, <ref>, <ref>, <ref>, <ref>, <ref>  of the form

\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}

based on the Cramér-Chernoff method. First, we introduced the general Cramér-Chernoff method, which can be applied to arbitrary random variables $Z$ to obtain bounds  (c.f. Section <ref>)

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

Moreover, as a special case of the above Chernoff inequality we obtained Bernstein's inequality for sub-gamma random variables. Then, we applied the Cramér-Chernoff method to to functionals of MJPs, i.e. $ Z = \int_0^t f(X_s) ds$. More precisely, we considered the setting:

Consider an irreducible MJP $(\F{X}, (\F{P}_x)_{x \in E})$ on a finite state space $E$ with invariant distribution $\pi$ and infinitesimal generator $L$, some arbitrary, nonconstant $f \in \mathcal{B}(E) = \F{R}^E$ with $\pi(f) = 0$, some arbitrary initial distribution $\nu \in \mathcal{M}_1(E)$, and let $\lambda_0(r)$ (for $r \in \F{R})$ be the largest eigenvalue of the selfadjoint operator $\frac{L+L^*}{2} + r M_f$ (defined on $L^2(\pi)$), where $M_f$ is the multiplication with $f$.  Furthermore, let $A_t = \int_0^t. f(X_s)ds$, $\Psi_{A_t}(r) = \log \F{E}_\nu (e^{rA_t})$, and $\Psi_{A_t}^*(u) = \sup_{ r \geq 0} (ru - \Psi_{A_t}(r))$.

First we followed Wu <cit.>, and starting from the general Chernoff inequality (<ref>) for $Z = A_t$ and using a Feynman Kac semigroup $P_t^{rf} = \exp(t(L+rM_f))$ to bound $\Psi_{A_t}(r)$ we obtained a general concentration inequality

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

depending on $\lambda_0^*$, the Fenchel conjugate of $\lambda_0$. We noted that for $\nu \neq \pi$ the above bound is trivial for $u \in [0, K]$ (where $K > 0$), and that if $\pi$ obeys the detailed balance condition, then this bound is asymptotically sharp (see Remark <ref> for details). Afterwards, based on this (general) concentration inequality we used three different approaches to get more explicit bounds $ \alpha(u) \leq \lambda_0^*(u) $, thus obtaining

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

In the first (Section <ref>) approach we followed Lezaud <cit.> and applied perturbation theory to express $\lambda_0(r)$ as a perturbation series and derived (after a lengthy computation, see proof of Lemma <ref>) a sub-gamma type bound (c.f. Definition <ref> and Lemma <ref>)

\begin{equation}
\label{eq: summary_sub_gamma_bound}
G(r) =  \frac{r^2v}{2(1-\frac{2r}{\epsilon})} \geq \lambda_0(r),
\end{equation}

which implied by computing the Fenchel conjugate $G^*(u) \geq \lambda_0^*(u)$ the concentration inequality of Theorem <ref>. Hereby, we corrected the claim of <cit.> as we noted that the proof (presented in <cit.>) of the sub-gamma type bound (<ref>)  just proves this bound  for  $r \in [0, \frac{\epsilon}{3}]$ and not for $r \in [0, \frac{\epsilon}{2}] $ (as claimed in <cit.>). As a result of this correction, the above sub-gamma type bound just implied a Bernstein-type concentration inequality for small $u$ (Theorem <ref>(a)) and a weaker inequality for larger $u$ (Theorem <ref>(b)).  In the second approach (Section <ref>) we followed Guillin <cit.> and used functional inequalities; the Poincaré inequality and the F-Sobolev inequality, which give bounds for $\langle g, L g \rangle$. Hereby, in our setting, the Poincaré inequality 'automatically' holds whereas a general $F$-Sobolev inequality may not hold in general. Using these inequalities we derived again bounds $G(r) \geq \lambda_0(r)$, and by computing $G^*(u) \leq \lambda_0^*(u) $ we obtained Theorems <ref> and <ref>. Herewith, we generalized, reformulated <cit.> and noted that the Poincaré inequality implies a Bernstein-type concentration inequality; Theorem <ref>. Furthermore, we noted that if an $\log$-Sobolev inequality holds, one obtains a continuous time analogue of Chernoff's inequality for sums of i.i.d. random variables. Finally, in the third approach (Section <ref>) we followed Gao <cit.> and used the Donsker-Varadhan information. First, we expressed $\lambda_0^*(u)$ in terms of the Donsker-Varadhan information. Then, using this expression we arrived at Theorem <ref>; a concentration inequality  (<ref>) holds for a function $\alpha : [0,\infty) \rightarrow [0,\infty]$ if

\begin{equation*}
\alpha(\beta(f)) \leq I( \beta | \pi)
\end{equation*}

for all $\beta \in \mathcal{M}_1(E)$ with $\beta(f) \geq 0$. Afterwards, we showed that for a Bernstein-type

\begin{equation*}
\alpha(u) = \frac{2u^2}{v(1+ \sqrt{1 + \frac{2uc}{v}})^2}
\end{equation*}
the above condition is automatically satisfied in our setting, thus obtaining a general Bernstein-type bound; Theorem <ref>, which is a strengthening and extension of the previous obtained Bernstein-type bounds; Theorem <ref>(a) and Theorem <ref>. Herewith, we proved the expression of $\lambda_0^*(u)$ in terms of the Donsker-Varadhan information (a fact which is just stated in <cit.>) and extended the results of <cit.> to the general, non-symmetric case.

Thus, summarizing the (central, nonredundant) results, we get: Assume the above Setting. Then, the following general concentration inequality holds
<ref>[A general inequality]
For any $u \geq 0$

\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)},
\end{equation*}

where $\lambda_0^*(u)$ denotes the Fenchel conjugate of $\lambda_0(r)$ and we also have

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

Based on this inequality  more explicit concentration inequalities follow (by using bounds on $\lambda_0$ or $\lambda_0^*$): The following Bernstein-type bound holds without further assumptions (than made in the above setting)
<ref>[A general Bernstein-type bound]
Let $S$ denote the reduced resolvent of $\frac{L+L^*}{2}$ with respect to the eigenvalue $0$, $\hat{\sigma}_f^2 = - 2 \langle f, Sf \rangle$, $\lambda_1 = \min_{\lambda \in \sigma \left ( \frac{L+L^*}{2} \right)\backslash \{0 \} } \abs{\lambda} $ the spectral gap, and $f^+ = \max \{ 0, f \}$ the nonnegative part of $f$. For all $u \geq 0$

\begin{equation*}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d \nu}{d \pi}}_2 \exp\left(-\frac{2tu^2}{\hat{\sigma}_f^2 \left (1+ \sqrt{1+ \frac{2 \norm{f_+}_\infty u}{\lambda_1 \hat{\sigma}_f^2}} \right )^2} \right).
\end{equation*}

Furthermore, if one assumes further conditions one gets:
<ref>[A bound assuming an $F$-Sobolev inequality] Assume additionally that an $F$-Sobolev inequality holds and let $r_f = \frac{F(0)}{\min_{x \in E}f(x)}$. Then, for all $ u \geq 0$

\begin{equation*}
\F{P}_\nu \left (\frac{A_t}{t} \geq u \right ) \leq \norm{\frac{d \nu}{d \pi}}_2 \exp( - t \sup_{ r \in [0, r_f)} (ru -F(\pi( F^{-1}(rf))))) .
\end{equation*}

<ref>[A bound assuming an information inequality] Let $I (\cdot | \pi)$ denote the Donsker-Varadhan information, and assume additionally that $\alpha : [0, \infty) \rightarrow [0, \infty]$ is some function satisfying

\begin{equation*}
\alpha(\beta(f)) \leq I (\beta | \pi)
\end{equation*}

for all probability measures $\beta$ on $E$ such that $\beta(f) \geq 0$.
Then, for all $u \geq 0$

\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*}

Furthermore, it should be remarked that although we focused on upper tail probabilities, by replacing $f$ by $-f$ one obtains bounds for the lower tail probabilities, i.e.

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

Finally, by subbaditivity one obtains bounds of the form

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

§.§ Outlook: Further Theory

Let us present a brief outlook into further theory related to concentration inequalities for MJPs, which was not covered in this thesis.

In this work, we applied the Cramér-Chernoff method to functionals of irreducible MJPs on finite state spaces and obtained bounds

\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*}

A question that was not covered (in detail), is the question on the sharpness of these bounds. It is not clear that these bounds are automatically  sharp; we even have seen that for $\nu \neq \pi$ the above bound is trivial for small $u$ (see Remark <ref>$(b)$). However, the question of sharpness is particularly of interest for the application of such concentration inequalities, where one is interested to approximate $\pi(f) $ by $t^{-1} \int_0^t f(X_s)ds$, and consequently sharp estimates for the deviation probabilities $\F{P}_\nu \left( \frac{A_t}{t} \geq u \right )$ are desired. A possible approach to discuss the sharpness is large deviation theory; the study of the asymptotic limit

\begin{equation}
\limsup_{t \to \infty} \frac{\log(\F{P}_\nu \left ( \frac{A_t}{t} \geq u \right))}{t}.
\end{equation}

One then could compare the above limit to the asymptotic limit

\begin{equation}
-\alpha(u) = \limsup_{t \to \infty} \frac{\log(\norm{\frac{d\nu}{d\pi}}_2 e^{-t \alpha(u)})}{t}
\end{equation}

of the bound. This comparison would yield a first impression of the (asymptotic) sharpness of the concentration inequality. We have already seen such a result briefly in Remark <ref>$(e)$, for an extensive presentation of large deviation theory for Markov processes see <cit.>. Another aspect which limits the sharpness of the concentration inequalities of this work is the sharpness of Chernoff's inequality: All concentration inequalities in this work are based on this inequality, and are not sharper than it. So, to analyze the sharpness of the concentration inequalities of this work, it may be also of interest to have a look at (general) theory concerning the sharpness of the Chernoff inequality. Furthermore, recall that our general concentration inequality (Theorem <ref>) was based on the Cauchy Schwartz inequality (c.f. Section <ref>)

\begin{equation}
\F{E}_\nu( e^{rA_t}) = \langle \frac{d\nu}{d\pi}, P_t^{rf}\textbf{1} \rangle \leq \norm{\frac{d\nu}{d\pi}}_2 \norm{P_t^{rf}}_2,
\end{equation}

which is in general not an equality. Another possible approach to bound $\F{E}_\nu(e^{rA_t})$ may be by using a Dyson identity to get an exact series representation of $P_t^{rf}\textbf{1} = \exp(L+rM_f)\textbf{1}$ and then using this series representation to obtain a bound for $\F{E}_\nu( e^{rA_t})$, c.f. for example <cit.>.
Finally, a more pragmatic, direct approach to study the sharpness, is to consider concrete examples of MJPs, where one can calculate (analytically or computationally) $\F{P}_\nu \left( \frac{A_t}{t} \geq u \right )$ and then to directly compare this (exact) result to the bound given by the concentration inequality.

Another aspect that was not covered here, is the generalization of the present results to more general Markov processes on (uncountably) infinite state spaces. One can extend the presented approach to more general Markov Processes on (uncountably) infinite state spaces, in fact the works <cit.>, <cit.>, <cit.>, <cit.> on which this thesis is based on, work with more general Markov processes and the qualitative form of these results (and the corresponding proofs) are quite similar. Formally, the presented approach, i.e. the application of the Cramér-Chernoff method,  can be directly transfered to more general Markov processes. However, a rigorous generalization of the results of this work leads to technical subtleties due to the infiniteness of the state space. Let us discuss briefly some changes and technicalities that have to be considered for a (rigorous) generalization of the results.
For a general Markov process the existence of an invariant measure is not guaranteed and even if such a measure exists, asymptotic properties of the Markov process may not be given by the invariant measure. Furthermore, one still needs some form of regularity of the paths $t \to X_t$, otherwise the time average $\int_0^t f(X_s) ds$ is not well defined. Thus, in more general settings (considered in <cit.>, <cit.>, <cit.>, <cit.>) one considers a càdlàg Markov process $(\F{X}, (\F{P}_x)_{x \in E})$  on  a polish space $E$, where càdlàg (continue à droite, limite à gauche) means that it's paths $t \mapsto X_t)$ are right continuous and have everywhere existing left limits. Furthermore, one assumes the existence of an invariant measure $\pi$ such that $\pi$ is ergodic with respect to the Markov semigroup $(P_t)_{t \geq 0}$ (defined as in (<ref>)). Here ergodic means that $\mathscr{L}_\nu(X_t)$ converges to 'fast enough' $\pi$ for all initial distributions. Moreover, note that the function $f$ over which the time average is taken can not be as general as in our case (where $f \in \F{R}^E$ was arbitrary); as $\int f d\pi$ has to be defined one must have at least $f \in L^1(\pi)$. Furthermore, for unbounded $f$ many of our results and proofs can not be applied;  all computations involving $\norm{f}_\infty$ are invalid and also the Feynman-Kac semigroup $P_t^f$ must be treated differently; e.g. by approximating $f$ with bounded functions (c.f. <cit.>). Also, in a general setting not for all $\nu \in \mathcal{M}_1(E)$ a density $\frac{d\nu}{d\pi} \in L^2(\pi)$ might exist (whereas in our setting a density always exists); for example if $\nu$ is a delta distribution and $\pi$ is a measure with density with respect to the Lebesgue measure. However, the basic starting point stays the same; one considers  the Markov semigroup $(P_t)_{t \geq 0}$ on $L^2(\pi)$ (c.f. Remark <ref>), its infinitesimal generator $L: D(L) \rightarrow L^2(\pi)$ with domain $D(L)$, a Feynman Kac semigroup $(P_t^{rf})_{ t \geq 0}$ and bounds the cumulant generating function $\Psi_{A_t}$ by $ \Psi_{A_t}(r) \leq \log \norm{\frac{d\nu}{d\pi}}_2 + \log \norm{P_t^{rf}}_2 $.  Based on this bound one derives concentration inequalities by bounding $\norm{P_t^{rf}}_2$ (c.f. <cit.>). Here  it has to be made sure, that $L$ still has the properties used in the proofs, like the simplicity of the eigenvalue $0$, a spectral gap, the Poincaré-inequality or other properties of Lemma <ref>, which may be in general not given. For example <cit.> assumes a spectral gap to be able to generalize the applied perturbation theory (see <cit.>). Furthermore, in expressions involving the infinitesimal generator, such as $\langle g_1, Lg_2 \rangle, \langle g_1, \frac{L+L^*}{2}g_2 \rangle$ or $\langle g_1 , Sg_2 \rangle$ the functions $g_1,g_2$ must always be contained in the domain of the operators, which does not hold for all $g_1,g_2 \in L^2(\pi)$ as operators such as $L, L^*$ are just densely defined. Finally, $\lambda_0(r)$ may not be defined as the largest eigenvalue, but defined as a supremum (c.f. Lemma <ref>, Reference <ref>).

§.§ Digression: Markov  Processes and Concentration Inequalities in Physics

The present section may be of interest for the reader who is interested in application of concentration inequalities in a physical context. First, we  briefly explain how stochastic processes and Markov (jump) processes arise in physical systems and then explain how concentration inequalities for MJPs may be applied in a physical context. For a more detailed  discussion of how stochastic processes arise in physics see <cit.>.
Often one considers a physical system (with many degrees of freedom) that is observed in time, for example a colloidal particle in water  or a protein in a biological system (these two systems will be used as  examples throughout this section). One  is interested in the time evolution of the the state of some specific physical object or observable. Refering to the two aforementioned examples, this could be the position of  the colloidal particle or the conformation of the protein. Mathematically, the state (of the physical object of interest) at time $t$ is described as some $x_t \in E$, where $E$ is a set, which contains all possible states of the object of interest. In the case of the colloidal particle we would have (in three dimensions) $E = \F{R}^3$, in the case of the protein, $E$ could be some discrete finite set, where each $x \in E$ would represent some concrete conformation of the protein. In many particle systems (e.g. a biological system) the state space $E$ does not describe the whole physical system (classically the whole system would be completely described by the momentum and position of all particles). Consequently, as the physical object (described by $E$) of interest is coupled to the rest of the system (e.g. the colloidal particle collides with the surrounding water molecules), whose specific state is not known, the observed trajectory $(x_t)_{t \geq 0} \in E^{[0,\infty)}$, appears to be 'irregular' and 'non-deterministic'. Thus, the observed 'randomness' of the trajectory comes from the 'ignorance' of the rest of the physical system. For example,  in the case of the colloidal particle  the momenta and positions of the water molecules are unknown, consequently one cannot predict the movement of the colloidal particle (as the particle collides with the water molecules) and the observed motion of the particle seems random and irregular. This suggest, that for the description of the time evolution, the observed trajectory $(x_t)_{t \geq 0}$ should be considered as a 'random' trajectory, which is mathematically exactly a stochastic process. Thus, one transitions from a description considering a single trajectory $(x_t)_{t \geq 0}$ to an 'ensemble' $\{(X_t)_{t \geq 0}(\omega) |  \omega \in \Omega \}$ of trajectories, described by a stochastic process $(X_t)_{t \geq 0}$ on $E$, defined on some underlying probability space $(\Omega, \mathcal{F}, \F{P})$. Intuitively, $\omega \in \Omega$ can be thought of parametrizing the 'uncertainty' (or 'randomness'), due to the 'random' interaction of the rest of the (unknown) physical system with the physical object of interest. Physically, a concrete realization $X_t(\omega)$ corresponds to  one concrete observation (i.e. performing an experiment) of the physical object and doing $n$ observations would correspond to drawing $\omega_1,...,\omega_n$ from $\Omega$, independently according to $\F{P}$ (the observations would correspond to $(X_t)_{t \geq 0}(\omega_1),..., (X_t)_{t \geq 0}(\omega_n)$). The  distribution of the stochastic process depends on the physical system and the description of it. One may impose certain (physically or practically justified) conditions like Markovianity or continuity of paths. In our example of a protein with certain conformations, if one assumes Markovianity and right continuity, then $(X_t)_{t \geq 0}$ is just exactly an MJP (examples where biomolecules are modeled by an MJP are found in <cit.>, <cit.>). Often also the 'random' influences of the surrounding system are modeled (e.g. the force on the colloidal particle resulting from collisions with water molecules may be modeled as white noise) or they are obtained by projection of the high dimensional many particle dynamics (including the object of interest and the surrounding system) onto the dynamics of the object of interest (see e.g. <cit.>), and in doing this one obtains stochastic differential equations (e.g. the Langevin equation, see  <cit.>), which then determine the distribution of the stochastic process. As already mentioned, MJPs (on a finite state space) arise in physics always directly when one assumes Markovianity of the system. Markovianity is  justified when one has a time scale separation between the time scale of the dynamics of the physical object of interest and the hidden dynamics of the surrounding system, more precisely when the time scale governing the surrounding system is much smaller than of the physical object. The intuitive argument on why this implies Markovianity is as follows. Without the (local) interaction of the object with the surrounding system, the system is at an equilibrium state. Now, when the physical object interacts with its surrounding, the surrounding system gets perturbed out of equilibrium. However, because of the much smaller time scale, the surrounding system quickly again reaches the equilibrium state, whereas the state of the object does not change significantly, and thus, the surrounding system 'forgets' its past interaction with the object. Consequently, given the present state of the object, the future interaction of the object with its surrounding, determining the future time evolution of the state of the object, is independent of the past, which corresponds exactly to the Markov property. Moreover, MJPs also arise in the context  when one examines the time evolution of so called 'site populations' (see <cit.>).

Let us now discuss the possible applications of concentration inequalities for MJPs. Nowadays it is experimentally possible to probe individual trajectories $ t \mapsto X_t(\omega)$ (e.g. single particle tracking <cit.>, <cit.>, single molecule spectroscopy <cit.>, <cit.>) and  one is interested to deduce properties  of the physical system by the observed individual trajectories. A possible approach is the study of time averages

\begin{equation}
\frac{A_t}{t} =  \frac{1}{t}\int_0^t f(X_s) ds,
\end{equation}

discussed in this work. Functionals of this form arise  for example in the context of chemical inference  <cit.>, time average statistical mechanics <cit.> and stochastic thermodynamics <cit.>.  In the analysis of these time averages it is of particular interest to establish relations between the fluctuations (of the time average) and physical properties and quantities (c.f. <cit.>, <cit.>, <cit.>). Although the asymptotic analysis of those time averages (and fluctuations) by application of asymptotic results, like the ergodic theorem or large deviation theory is already well established in the physics literature (see e.g. <cit.>, <cit.>), a general approach
to the non-asymptotic study of the statistics of the above time averages remains elusive (c.f. <cit.>). Moreover, in single molecule experiments ergodic time scales (i.e. time scales where $\mathscr{L}(X_t)$ is close to $\pi$ and $t^{-1}A_t$ is close to $\pi(f)$) frequently cannot be reached  (see e.g. <cit.>, <cit.>), thus the
correspondence between time and ensemble averages breaks down and the typical behavior of time-averaged
observables is frequently found to be very different from ensemble-averages. Furthermore, from a practical point of view, the quantitative analysis of the rate of convergence of $t^{-1}A_t \to \pi(f)$ is of interest, as this yields quantitative results on the time scales when the time average $t^{-1}A_t$ (obtained in experiments) is a 'good' approximation for the  ensemble average $\pi(f)$.  Consequently, the study of concentration inequalities is natural, as they provide some insight to the fluctuations of time averages and  a quantitative bound for the time scales, where time averages become ensemble averages. Let us illustrate this idea in an example (c.f. <cit.>). One may be interested in establishing results about the energies $H(x)$ of the states $x \in E$, which are related (for systems which obey detailed balance) to $\pi$ by the Boltzmann distribution $\pi_x \propto \exp(\frac{-H(x)}{k_B T})$. Thus, to estimate the energies, one approximates $\pi(f)$ by  $t^{-1}A_t$ (which can be measured). However, the ergodic theorem (Theorem <ref>) just yields the asymptotic result $t^{-1}A_t \to \pi(f)$ and consequently it is not clear that this strategy gives a 'good' approximation. Concentration inequalities

\begin{equation}
\F{P}(t^{-1}A_t \geq u) \leq B(u)
\end{equation}

provide quantitative results on time scales when '$A_t$ is close to $\pi(f)$ with a high probability' and thus yield sufficient conditions on when the above strategy (to estimate energies) yields a 'good approximation with a high probability'. Furthermore, if one applies the concentration inequalities of this work, which are exponential concentration inequalities ($B(u) = \exp(-\Phi(u))$ derived by the Cramér-Chernoff method, the concentration inequalities for the observation of a single trajectory (i.e. measuring once), directly generalize to concentration inequalities for $n$ independent observations by using Corollary <ref> to obtain

\begin{equation}
\label{eq: conc_ineq_sum}
\F{P} \left ( \frac{1}{n}\sum_{i = 1}^n t^{-1}A_t^{(i)} \geq u \right) \leq \exp(-n \Phi(u)),
\end{equation}

where $t^{-1}A_t^{(i)}$ are the independent time averages, obtained by independent MJPs. Practically, (<ref>) gives an sufficient condition on the number of times an experiment has to be conducted to obtain 'good approximation for $\pi(f)$ with  high probability'.

§ APPENDIX

§.§ Perturbation Theory

This section is devoted to proof Lemma <ref> and Theorem <ref> for complex vector spaces and transfer them to real vector spaces (see Remarks <ref>, <ref>, <ref>). For proving the results in the complex case ; Lemma <ref> and Theorem <ref>, we combine results of <cit.>.

To rigorously transfer the results to real vector spaces, we need

Let $V$ be a real vector space, and $\langle \cdot, \cdot \rangle$ an inner product on $V$. Then, the complexification $V^{\F{C}} = \{ v_1 + iv_2 \, | \, v_1, v_2 \in V \}$ has the following properties:

* For every operator $T : V \rightarrow V$, there is a unique complexification $T^{C}$, i.e. a unique $\F{C}$ - linearoperator $T^{\F{C}}: V^{\F{C}} \rightarrow V^{\F{C}}$ that extends $T$, i.e. $T = T^\F{C} |_{V}$. For all $v_1, v_2 \in V$ we have

\begin{equation}
\label{eq: app_T^C}
T^\F{C}(v_1 + iv_2) = Tv_1 + i Tv_2.
\end{equation}

* There is a unique complexinner product $\langle \cdot , \cdot \rangle^\F{C}$ on $V^\F{C}$ that extends $\langle \cdot , \cdot \rangle$. We have

\begin{equation}
\label{eq: app_complex_inner_product}
\langle (v_1 + iv_2), (v_1' + iv_2') \rangle^\F{C} = \langle v_1,v_1' \rangle + \langle v_2, v_2' \rangle + i ( \langle v_1, v_2' \rangle - \langle v_2, v_1' \rangle  )
\end{equation}

* We have $(T_1T_2)^\F{C} = T_1^\F{C} T_2^\F{C}$ and the operation $T \mapsto T^\F{C}$ preserves properties of $T$, we have

* $T$ and $T^\F{C}$ have the same characteristic polynomials   and $\Tr (T) = \Tr(T^\F{C})$, in particular $T$ and $T^\F{C}$ have the same eigenvalues and algebraic multiplicities of eigenvalues.

* If $\textup{pr}$ is a(n) (orthogonal) projection, $\textup{pr}^\F{C}$ is also a(n) (orthogonal) projection

* If $T$ is selfadjoint with respect to $\langle \cdot , \cdot \rangle$, $T^\F{C}$ is selfadjoint with respect to $\langle \cdot, \cdot \rangle^\F{C}$

* If $T$ is diagonalizable with real eigenvalues, i.e. $T = \sum_{\lambda \in \sigma(T)} \lambda \textup{pr}_\lambda$, where $\textup{pr}_\lambda$ is the projection onto $\textup{Ker}(T - \lambda)$ according to the decomposition $V = \bigoplus_{\lambda \in \sigma(T)} \textup{Ker}(T-\lambda)$, then $T^\F{C}$ is diagonalizable with $T^\F{C} = \sum_{\lambda \in \sigma(T)} \lambda \textup{pr}_\lambda^\F{C}$ and $\textup{pr}_\lambda^\F{C}$ is the projection onto $ \textup{Ker}(T - \lambda)^\F{C} = \textup{Ker}(T^\F{C} - \lambda)$ according to the decomposition $V^\F{C} = \bigoplus_{\lambda \in \sigma(T)} \textup{Ker}(T-\lambda)^\F{C} $

The proofs are elementary, so we omit the computations. Statement $(a)$ and  $(b)$ follow directly from the $\F{C}$ linearity for operators and  the sesquilinearity for complex inner products. Statement $(c)$.1 follows  by using that if $(v_i)_{i = 1,..., \dim V}$ is a basis of $V$, then it is also a basis of $V^{C}$ and that the matrix representations of $T$ and $T^\F{C}$ under this basis are the same. Statements $(c)$.2 - $(c)$.4 follow by direct computation using (<ref>) and (<ref>).

In the following (unless otherwise stated) let $V$ be a complex vector space, $H$ a complex Hilbert space and let $\sigma(T)$ denote the spectrum of an operator $T: V  \rightarrow V$.  We first present some basic definitions and concepts required for  proving Theorem <ref>.

Let $T : V \rightarrow V$ be an operator. The operator-valued function $R$ defined on $\F{C} \backslash \sigma(T)$ via

\begin{equation*}
R(\zeta) = (T - \zeta )^{-1}
\end{equation*}

is called the resolvent of $T$.

For $\lambda \in \sigma(T)$ it can be shown that the Laurent series expansion of $R(\zeta)$ at $\lambda$ takes the following form <cit.>

\begin{equation}
\label{eq: resolvent_laurent_series}
R(\zeta) = - (\zeta - \lambda)^{-1}\text{pr}_\lambda - \sum_{n = 1}^{m_\lambda-1}(\zeta - \lambda)^{-n-1}D_\lambda^n + S_\lambda(\zeta),
\end{equation}

where $\text{pr}_\lambda$ is a projection, i.e. $\text{pr}_\lambda^2 = \text{pr}_\lambda$, $D_\lambda$ is a nilpotent operator with $D_\lambda^{m_\lambda} = 0$, $m_\lambda = \mathrm{dim }\mathrm{Im}(\text{pr}_\lambda)$, and $S_\lambda(\zeta)$ is a holomorphic operator-valued function. Kato <cit.> defines the projection $\text{pr}_\lambda$ as the eigenprojection for the eigenvalue $\lambda$, the integer $m_\lambda$ as  the algebraic multiplicity of $\lambda$, and the holomorphic operator valued function $S_\lambda(\zeta)$ as  the reduced resolvent of $T$ with respect to the eigenvalue $\lambda$ <cit.>. An eigenvalue $\lambda$ is called simple if $m_\lambda = 1$ <cit.>. A straightforward application of the residue theorem shows that for any positively oriented circle $\Gamma $ in $\F{C}$ containing exactly one eigenvalue $\lambda \in \sigma(T)$ we have

\begin{equation}
\label{eq: eigenprojection_integral_definition}
\text{pr}_\lambda = \frac{-1}{2 \pi i}\int_\Gamma R(\zeta) d\zeta.
\end{equation}

Furthermore, the eigenprojections satisfy <cit.>

\begin{align}
\label{eq: properties_pr_lambda}
\begin{split}
&\sum_{\lambda \in \sigma(T)} \text{pr}_\lambda = \text{Id}_V, \\
& \text{pr}_\lambda \text{pr}_\mu = \delta_{\lambda \mu} \text{pr}_\lambda,\\
& \text{pr}_\lambda T = T \text{pr}_\lambda  ,
\end{split}
\end{align}

where $\delta_{\lambda \mu}$ denotes the Kroenecker delta. Thus, the eigenprojections define a decomposition $V = \bigoplus_{\lambda \in \sigma(T)} M_\lambda$, with $M_\lambda = \mathrm{Im}(\text{pr}_\lambda)$ and $TM_\lambda \subset M_\lambda$. To clarify Kato's notions we state and prove

Kato's notions of eigenprojection, algebraic multiplicity , and the decomposition $V = \bigoplus_{\lambda \in \sigma(T)}M_\lambda $ defined as above by the Laurent series expansion (<ref>) coincide  with  the 'usual' notions of eigenprojection and algebraic multiplicity, defined by the Jordan decomposition and the characteristic polynomial. In other words, if $m(\lambda)$ denotes the multiplicity of the root $\lambda$ in the characteristic polynomial of $T$, and

\begin{equation}
\label{eq: jordan_decomposition}
T = \sum_{\lambda \in \sigma(T)} \lambda \hat{\textup{pr}}_\lambda + \hat{D}
\end{equation}

denotes the Jordan decomposition, where $\hat{\textup{pr}}_\lambda$  denotes the projection onto the generalized eigenspace $V_\lambda = \mathrm{Ker}(T - \lambda)^{m(\lambda)}$ according to the decomposition $V = \bigoplus_{\lambda \in \sigma(T)}V_\lambda$ and $\hat{D}$ denotes the nilpotent operator belonging to the Jordan decomposition,  then $\textup{pr}_\lambda = \hat{\textup{pr}}_\lambda$, $m_\lambda = m(\lambda)$ and $M_\lambda = V_\lambda $

And as a result we obtain immediately

In particular,  if $T$ is diagonalizable, i.e. $T = \sum_{ \lambda \in \sigma(T)} \lambda \textup{pr}_\lambda$, then $\textup{pr}_\lambda$ is the projection onto the eigenspace $\mathrm{Ker}( T -\lambda)$ according to the decomposition $V = \bigoplus_{ \lambda \in \sigma(T)} \mathrm{Ker}( T -\lambda) $, and if $T $ is a self adjoint operator on a Hilbert space $H$, then $\textup{pr}_\lambda = \hat{\textup{pr}}_\lambda $ is the orthogonal projection onto the eigenspace $\mathrm{Ker}(T-\lambda)$

The 'usual' definitions and the Jordan decomposition that we refer to are found for example in <cit.> or <cit.>.

It can be shown that <cit.>

\begin{equation*}
T = \sum_{\lambda \in \sigma(T)}\lambda \text{pr}_\lambda + D,
\end{equation*}

where $D = \sum_{\lambda \in \sigma(T)} D_\lambda $ is a nilpotent operator that commutes with $\sum_{\lambda \in \sigma(T)}\lambda \text{pr}_\lambda$. Furthermore, the representation $T = S  +  D$, where $S$ is diagonalizable and $D$ is nilpotent and commutes with D is unique <cit.> and the Jordan decomposition (<ref>) is also such a representation of $T$ <cit.>. Thus, by the uniqueness of the representation $T = S + D$ it follows that $\hat{\textup{pr}}_\lambda = \text{pr}_\lambda$, consequently   $ m_\lambda = \dim \text{Im}(\text{pr}_\lambda) = m(\lambda)$ and $M_\lambda = \text{Im}(\text{pr}_\lambda) = V_\lambda$.

In this work  we will only work with $S_\lambda = S_\lambda(\lambda)$ and we  simply refer to $S_\lambda$ as the reduced resolvent. We can give a more explicit representation of $S_\lambda$, we have

The reduced resolvent $S_\lambda = S_\lambda(\lambda)$ is given by

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

The reduced resolvent has the following properties  <cit.>

\begin{align}
&S_\lambda \text{pr}_\lambda = \text{pr}_\lambda S_\lambda = 0  \label{eq: reduced_res_property_1}\\
& (T - \lambda )S_\lambda = S_\lambda(T-\lambda) = 1 - \text{pr}_\lambda \label{eq: reduced_res_property_2}.
\end{align}

Furthermore, note that $T(1- \text{pr}_\lambda) =(1- \text{pr}_\lambda) T$ (follows from (<ref>)), thus

\begin{equation}
\label{eq: T_preserves_Im(1-pr_lambda)}
\text{Im}((T- \lambda)|_{\text{Im}(1-\text{pr}_\lambda)}) \subset \text{Im}(1-\text{pr}_\lambda)
\end{equation}

Moreover, (<ref>) implies

\begin{equation}
\label{eq: S_preserves_Im}
\text{Im}(S_\lambda|_{\text{Im}(1-\text{pr}_\lambda)}) \subset \text{Im}(1-\text{pr}_\lambda)
\end{equation}

Combining (<ref>) and (<ref>) with the restriction of (<ref>) to $\text{Im}(1 - \text{pr}_\lambda)$ yields

\begin{equation}
S_\lambda(\lambda)|_{\text{Im}(1-\text{pr}_\lambda)} = (T - \lambda)|_{ \mathrm{Im}(1- \text{pr}_\lambda)}^{-1}.
\end{equation}

Finally, (<ref>) implies that $S_\lambda |_{\text{Im}(\text{pr}_\lambda)} = 0 $.

(Real reduced resolvent)

If $T = \sum_{\lambda \in \sigma(T)} \lambda \text{pr}_\lambda$ is a diagonalizable operator on a real vector space (with real eigenvalues). And $S_\lambda  $ denotes its reduced resolvent  (with respect to $\lambda$) in the sense of Definition <ref>, then the reduced resolvent of $T^\F{C}$ with respect to $\lambda$ (in the sense of Lemma <ref>) is just the complexification $S_\lambda^\F{C}$ of $S_\lambda$. Indeed, this is easily checked by using Lemma <ref>$(c)$.

After we have now given and clarified the basic definitions and notions that are used in <cit.> to analyze the perturbed operator $T(\chi) = T + \chi T',$ we present two results that will be needed for our later purposes.

Let $T(r)$ be a continuous operator-valued function on $V$defined on some interval $I \subset \F{R}$. Furthermore, 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 by  a combination of <cit.> and  <cit.>.

As $V$ is finite dimensional the notion of continuity of $T(r)$ does not depend on the underlying operator norm.

(Real case, Lemma <ref>)

Consider the setting of Lemma <ref>. As $r \mapsto T(r)$ is continuous $r \mapsto T(r)^{\F{C}}$ is also continuous. Furthermore as $T(r)$ and $T(r)^\F{C}$ have the same spectral properties (Lemma <ref>$(c)$) the statement of Lemma <ref> follows directly.

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, $\textup{pr}$ the orthogonal projection onto the eigenspace with eigenvalue $0$ and $S$ the corresponding reduced resolvent. Furthermore, let $ T' : H \rightarrow H$ be some operator and define $ T(\chi) := T + \chi T'$ for $\chi \in \F{C}$. Then for all $\abs{\chi} < \frac{\lambda_1}{2 \norm{T}}$ the ball $B_{\frac{\lambda_1}{2}}(0)$ contains exactly one simple eigenvalue $\mu_0(\chi)$ of $T(\chi)$ and we have

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

\begin{equation}
\label{eq: theorem_perturbation_mu_0_2}
\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}
\label{eq: theorem_perturbation_S^(n)}
S^{(0)} = - \textup{pr} \quad \text{and} \quad S^{(k)} = S^k
\end{equation}

for $ k \geq 1$.

As the result is specifically formulated for our later use and <cit.> considers a more general setting we give a short argument for the above theorem by  combining results of <cit.>.

Kato treats the more general case of a perturbed operator of the form $T(\chi) = \sum_{n=0}^\infty T^{(n)} \chi^n$ ,  in our case $T^{(0)} = T, T^{(1)} = T'$ and $T^{(k)} = 0$ for $k \geq 2$. In the following let  $\norm{\cdot} = \norm{\cdot}_2 $ denote the operator norm induced by the norm on the Hilbert space $H$. The formula for $\lambda_0(\chi)$ is based on the following formula for the resolvent $R(\zeta, \chi) = (T(\chi)-\zeta)^{-1}$ of $T(\chi)$. Let $R(\zeta)$ denote the resolvent of $T$, and $\zeta \in \F{C} \backslash \sigma(T)$ such that $\norm{\chi T' R(\zeta)} < 1$ (this condition is found in <cit.>). Then, $R(\zeta, \chi) $ exists and is given by <cit.>

\begin{equation}
\label{eq: perturbation_resolvent}
R(\zeta, \chi) = R(\zeta) \sum_{n=0}^\infty (- \chi T' R(\zeta))^n.
\end{equation}

Furthermore,   using an orthonormal basis that diagonalizes $T$, it is easy to see that $\norm{R(\zeta)} =  \norm{R(\zeta)}_2 = \max _{ \lambda \in \sigma(T)} \abs{\lambda - \zeta}^{-1}$. Thus, invoking submultiplicativity of $\norm{\cdot}$  we get for any $ \abs{\zeta} = \frac{\lambda_1}{2}$

\begin{equation*}
\norm{T' R(\zeta)}\leq \norm{T'} \frac{2}{\lambda_1}
\end{equation*}

Consequently  for all $\abs{\chi}  < \frac{\lambda_1}{2 \norm{T'}}$ and $\abs{\zeta} = \frac{\lambda_1}{2}$ we have $\norm{\chi T' R(\zeta)} < 1$,  and $R(\chi,\zeta)$ is given by (<ref>). Let $\Gamma$ be the circle with radius $\frac{\lambda_1}{2}$ around 0 , then for $\abs{\chi} < \frac{\lambda_1}{2\norm{T}}$ the operator

\begin{equation}
\label{eq: perturbation_projection}
\text{pr}(\chi) := \frac{-1}{2 \pi i} \int_\Gamma R(\zeta, \chi) d\zeta
\end{equation}

depends holomorphically on $\chi$ as the series (<ref>) converges uniformly on $\Gamma$. So by <cit.>  we have $\mathrm{dim}\mathrm{Im}(\text{pr}(0)) = \mathrm{dim}\mathrm{Im}(\text{pr}(\chi)) = 1 $ for all $\abs{\chi} < \frac{\lambda_1}{2 \norm{T'}}$. Furthermore, $\text{pr}(\chi)$ is the sum of all eigenprojections  for all eigenvalues of $T(\chi)$ lying in $B_{\frac{\lambda_1}{2}}(0)$ (c.f. <cit.>), so $1 = \dim \text{pr}(\chi)$  implies that the ball $B_\frac{\lambda_1}{2}(0)$ contains exactly one simple eigenvalue $\lambda_0(\chi)$ of $T(\chi)$ for all  $\abs{\chi} < \frac{\lambda_1}{2\norm{T}}$. Finally, Eqs.(<ref>), (<ref>) and (<ref>) can be proved by noticing that hat $\lambda_0(\chi) = \Tr(T(\chi)\text{pr}(\chi))$, and using equations (<ref>), (<ref>) to calculate $\Tr(T(\chi)\text{pr}(\chi))$. For details of this computation see <cit.>. Here, formula (<ref>) is stated in <cit.>, formula (<ref>) is obtained by using <cit.> and $T^{(k)} = 0 $ for $k \geq 2$ (we only treat a linear perturbation $T(\chi) = T + \chi T'$) and formula (<ref>) is stated in <cit.>, where we also use $\text{pr}(0) = \text{pr}$ (Corollary <ref>).

(Transfer to real operators, Theorem <ref>)

Consider the setting and notation of Theorem <ref>. Transfer the result of Theorem <ref> to the real case by using the complexification $T^\F{C}(r) = T^\F{C} + r T'^{\F{C}}$: Because of the properties of the complexification (Lemma <ref>$(c)$), $T^\F{C}$ satisfies the requirements of  Theorem <ref>. Furthermore, because the spectral properties of $T$ and $T^\F{C}$ are the same (Lemma <ref>$(c)$), it does not matter whether we consider the eigenvalues of $T(r)^\F{C}$ or $T(r)$. Thus, Theorem <ref> implies 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 (<ref>) with

\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')^\F{C}\tilde{S}^{(k_1)} ... (T')^\F{C}\tilde{S}^{(k_n)}),
\end{equation}

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

for $k \geq 1$.
Here $\widetilde{\textup{pr}}$ denotes the (complex) orthogonal projection onto $\text{Ker}( T^\F{C})$ and $\tilde{S}$ denotes the (complex) reduced resolvent  (see Lemma <ref>) of $T^\F{C}$ with respect to the eigenvalue $0$. But as the complexification respects orthogonal projections and diagonalizations (Lemma <ref>$(c)$), and also reduced resolvents (Remark <ref>) we have

\begin{equation}
\widetilde{\text{pr}} = \text{pr}^\F{C} \quad \text{and} \quad \tilde{S} = S^{\F{C}}.
\end{equation}

Consequently, $\tilde{S}^{(k)} = (S^{(k)})^\F{C}$ and
\begin{align}
\begin{split}
\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')^\F{C}(S^{(k_1)})^{\F{C}} ... (T')^\F{C}(S^{(k_n)})^{\F{C}}) \\
&= \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'^{(k_n)}),
\end{split}
\end{align}

where we used Lemma <ref>$(c)$. Thus, Theorem <ref> is a consequence of the corresponding complex version Theorem <ref>.

§.§ Remark <ref>

Consider the setting of Theorem <ref>. The Fenchel conjugate
$\lambda_0^*(u) = \sup_{ r \in \F{R}} (ru - \lambda_0(r))$ has the following properties :

* $\lambda_0^* \geq 0$

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

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

Part $(a)$ follows directly from  $\lambda_0(0) = 0$ (Lemma <ref>) and $\lambda_0^*(u) \geq 0 \cdot u - \lambda_0(0) = 0$. For part $(b)$ recall that by Theorem <ref> we have
\begin{equation}
\lambda_0^*(u) = I(u) =  \inf \{ - \langle Lg, g \rangle \; | \, \norm{g}_2 = 1, \langle M_fg, g \rangle = u \}.
\end{equation}

Furthermore, recall the proof of Theorem <ref>: Let $D : S_1 \rightarrow \F{R}$ be defined by

\begin{equation}
D(g) = \langle M_fg, g \rangle = \sum_{y \in E} g(y)^2 f(y) \pi_y,
\end{equation}

where $S_1 = \{ g \in L^2(\pi) \, | \, \norm{g}_2 = 1 \}$. By (<ref>) we have

\begin{equation}
\{ \lambda_0^* < \infty \} = \{ I < \infty \}  = \text{Im}(D) = [a,b],
\end{equation}

for some $a < b $. Note that for $g \in S_1$ we have

\begin{align}
\begin{split}
\min_{x \in E} f(x) &= \sum_{y \in E} \min_{x \in E} f(x) g(y)^2 \pi_y \leq \sum_{y \in E} f(y) g(y)^2 \pi_y  \\
&\leq \sum_{y \in E}  \max_{ x \in E}f(x) g(y)^2 \pi_y = \max_{x \in E} f(x).
\end{split}
\end{align}

Furthermore, if $g(x) = \delta_{yx} \frac{1}{\sqrt{\pi_y}}$ for some $y \in E$, then $f(y) = \langle g, M_f g \rangle$, so

\begin{equation}
\text{Im}(D) = [\min_{x \in E}f(x) , \max_{x \in E}f(x)],
\end{equation}

which proves part $(b)$. As a Fenchel conjugate, $\lambda_0^*$ is convex (Lemma <ref>$(a)$). Moreover, $\lambda_0^* = I$ is bounded on $\{ \lambda_0^* < \infty \}$ because by the Cauchy Schwartz inequality $I(u) \leq \norm{L}_2$ for any $u \in \{ \lambda_0^* < \infty \} $. To show the continuity of $\lambda_0^*$ on $ \{ \lambda_0^* < \infty \} = [a,b]$ let $u \in [a,b]$ and let $(u_n)_{n \in \F{N}}$ be a sequence in $[a,b]$ converging to $u$. Recall from the proof of Theorem <ref> that $I = \lambda_0^*$ is lower semicontinuous, so

\begin{equation}
\label{eq: appendix_lower_semicont}
\lambda_0^*(u)  \leq \liminf_{n \to \infty } \lambda_0^*(u_n) \leq \limsup_{n \to \infty } \lambda_0^*(u_n).
\end{equation}

Choose a subsequence $(u_{n_k})_{k \in \F{N}}$ such  that $\lim_{k \to \infty }\lambda_0^*(u_{n_k}) = \limsup_{n \to \infty} \lambda_0^*(u_n)$ and  $(u_{n_k})_{k \in \F{N}}$ is monotonous. Then, every $u_{n_k}$ can be expressed as $u_{n_k} = (1-s_k) u + s_ku_{n_1}$ for some $s_k \in [0,1]$. As $u_{n_k} \to u$, we have $s_k \to 0$. Consequently convexity and $\lambda_0^*(u_{n_1}) < \infty $ implies

\begin{equation}
\limsup_{n \to \infty } \lambda_0^*(u_n) =  \lim_{k \to \infty} \lambda_0^*(u_{n_k}) \leq \lim_{k \to \infty } (1-s_k) \lambda_0^*(u) + s_k \lambda_0^*(u_{n_1})  = \lambda_0^*(u).
\end{equation}

Combining this with (<ref>) implies $\lambda_0^*(u) = \lim_{n \to \infty} \lambda_0^*(u_n)$, which proves continuity. Finally, we show that $\lambda_0^*$ is nondecreasing on $[0,\infty)$. Let $0 \geq u_1 < u_2$ and let $\varepsilon > 0 $. By Theorem <ref> we have

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

so there is some $r \geq 0$ with $ (ru_1 - \lambda_0(r)) \geq \lambda_0^*(u_1) - \varepsilon$. This implies

\begin{equation}
\lambda_0^*(u_2) \geq r(u_2-u_1) + ru_1 - \lambda_0(r) \geq  \lambda_0^*(u_1) - \varepsilon.
\end{equation}

As the above inequality holds for all $\varepsilon > 0$, we have $\lambda_0^*(u_2) \geq \lambda_0^*(u_1)$ and the proof is complete.

Assume the setting of Section <ref>. Furthermore, assume that $\pi$ satisfies the detailed balance condition. Then,

\begin{equation}
\label{eq: appendix_exact_asymptotic}
\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 \geq 0$ and $u \neq \max_{x \in E} f(x)$.

If $u > \max_{x \in E} f(x)$, then the claim follows directly by the  estimate
$A_t \leq t \max_{x \in E} f(x)$ and $\lambda_0^*(u) = \infty $ (Lemma <ref>). So assume $0 \leq u < \max_{x \in E } f(x) $. We apply <cit.>. The context and notation of this theorem are the following: We endow the set of probability measures  $\mathcal{M}_1(E)$ on $E$ with the so called $\tau$-topology (see <cit.> for a definition), i.e. the topology generated by the maps

\begin{equation}
\nu \mapsto \nu(g)
\end{equation}

for $g \in \mathcal{B}(E)$ and $\nu \in \mathcal{M}_1(E)$. Furthermore, $L_t = t^{-1}\int_0^t \delta_{X_s} ds = \sum_{x \in E} \delta_x \cdot  t^{-1} \int_0^t 1_{\{ X_s = x\}}ds$ denotes the 'empirical measure', $m$ denotes the invariant measure $\pi$ and $J_{\mathcal{E}}(\nu)  $ denotes the Donsker-Varadhan information $I(\nu | \pi)$ defined in (<ref>). Notice that $L_t(f) = t^{-1}A_t$ and $J_{\mathcal{E}}(\nu) =  - \left \langle L \left(\frac{d\nu}{d\pi} \right)^{\frac{1}{2}}, \left (\frac{d\nu}{d\pi} \right)^{\frac{1}{2}} \right\rangle$ (as we always have $\nu << \pi$). Furthermore, set $\Gamma = \{ \nu \in \mathcal{M}_1(E) \; | \; \nu(f) >  u \}$. Now, we prove that all requirements of <cit.> are satisfied, i.e. we show that $J_\mathcal{E}$ is a good rate function (in the sense of <cit.>), $J_\mathcal{E}(\nu) = 0$ if and only if $\nu = m = \pi$, and $\nu$ is not singular to $m$. By using the canonical identifications

\begin{equation}
\mathcal{M}_1(E) \Tilde{=} \left \{ \nu \in \F{R}^E \; | \; \nu_x \in [0,1] \text{ for all }x \in E, \sum_{x \in E} \nu_x = 1 \right \}  =: M
\end{equation}

\begin{equation}
\mathcal{B}(E) = \F{R}^E
\end{equation}

it is straightforward to see that the $\mathcal{M}_1(E)$ endowed with the $\tau$-topology is homeomorphic to $M \subset \F{R}^E$, endowed with the subspace topology of the standard topology on $\F{R}^E \Tilde{=} \F{R}^N$, where $N = \# E$. Using this homeomorphism  and $\frac{d\nu}{d\pi}(x) = \frac{\nu_x}{\pi_x}$, it is straightforward to check that $\nu \mapsto J_{\mathcal{E}}(\nu)$ is continuous and $\mathcal{M}_1(E)$ is compact. Thus, $J_{\mathcal{E}} $ is a good rate function (see <cit.> for a definition). Furthermore, using that $-L$ is positive semidefinite (Lemma <ref>) and selfadjoint (Theorem <ref>) with $\text{Ker}(L) = \text{span}(\textbf{1})$ (Lemma <ref>), by diagonalizing $-L$, it is straightforward to check  that $J_{\mathcal{E}}(\nu) = 0$ if and only if $\nu = m = \pi$. Finally, $\nu$ is not singular to $m$ as $\nu << m$ and consequently all requirements are satisfied. As $u < \max_{x \in E} f(x)$, $\Gamma$ is open (with respect to the $\tau$-topology) and non-empty. By the continuity of $J_{\mathcal{E}}$ we have

\begin{equation}
\label{eq: appendix_same_infima}
\inf_{\nu \in \Gamma } J_{\mathcal{E}}(\nu) =  \inf_{\nu \in \overline{\Gamma} } J_{\mathcal{E}}(\nu).
\end{equation}

Using <cit.>

\begin{equation}
- \inf_{\nu \in \Gamma} I(\nu|\pi) \leq    \liminf_{ t \to \infty} \frac{ \log \F{P}_\nu  \left (\frac{A_t}{t} \geq u \right )}{t} \leq \limsup_{ t \to \infty} \frac{ \log \F{P}_\nu  \left (\frac{A_t}{t} \geq u \right )}{t} \leq  - \inf_{\nu \in \overline{\Gamma}} I(\nu|\pi)
\end{equation}

and (<ref>) it follows that

\begin{equation}
- \inf_{\nu \in \Gamma} I(\nu|\pi) =   \lim_{ t \to \infty} \frac{ \log \F{P}_\nu  \left (\frac{A_t}{t} \geq u \right )}{t} = - \inf_{\nu \in \overline{\Gamma }} I(\nu|\pi).
\end{equation}

To finish the proof, note that

\begin{equation}
\label{eq: appendix_sandwich_prep}
- \inf_{\nu \in \overline{\Gamma} } I(\nu|\pi) =   \lim_{ t \to \infty} \frac{ \log \F{P}_\nu  \left (\frac{A_t}{t} \geq u \right )}{t} \leq - \lambda_0^*(u) = -\inf \{  I(\nu|\pi) \; | \; \nu(f) = u \},
\end{equation}

where we used Theorem <ref> and Lemma <ref>.
Finally, note that (by definition) $\overline{\Gamma} = \{ \nu \in \mathcal{M}_1(E) \,| \nu(f) \geq u \}$, thus  $-\inf \{  I(\nu|\pi) \; | \; \nu(f) = u \} \leq  - \inf_{\nu \in \overline{\Gamma} } I(\nu|\pi)$ (the infimum over a bigger set is smaller), which together with (<ref>) implies the desired result (<ref>).

§.§ Proof of Lemma <ref>

Let $n ,k \in \F{N}$, $M = \{ (k_1,...,k_n) \in \F{Z}_+^n \;|\; k_1 + ... + k_n = k \}$ and let $G = \{ (1 \; 2 \;... \; n),..., (1 \; 2 \;... \; n)^{n-1}, \text{Id} \} $ be the abeliangroup of all circular permutations of $n$ elements we used cycle notation. Furthermore, define a  rightgroup action via $(k_1,...,k_n) \cdot \sigma  = (k_{\sigma(1)},...,k_{\sigma(n)})$ and let $G_{(k_1,...,k_n)}$ denote the stabilizer of $(k_1,...,k_n)$, i.e.

\begin{equation}
G_{(k_1,...,k_n)} = \{ g \in G \; |  \ (k_1,...,k_n) \cdot g = (k_1,...,k_n) \}
\end{equation}

Then, $\# G_{(k_1,...,k_n)} \leq \textup{GCD}(n,k) $, where $\textup{GCD}(n,k) $ denotes the greatest common divisor. Moreover, if $ \textup{GCD}(n,k) = 1$ then all the equivalence classes defined by the orbits of the group action$[k_1,...,k_n] = (k_1,...,k_n) \cdot G$  contain exactly $n$ elements.

The statement $\# G_{(k_1,...,k_n)} \leq \text{GCD}(n,k) $ is equivalent to: $\# G_{(k_1,...,k_n)} | n $ and
$\# G_{(k_1,...,k_n)} | k$. Let $H \subset G$ be some subgroup. By Lagrange's theorem (<cit.>) $\# H | \#G = n$. Furthermore, as $G $ is a cyclic group (it is  generated by $(1 \; 2 \;... \; n)$), every subgroup $H$ is also cyclic: It is generated by some $(1 \; 2 \;... \; n)^{j}$ where $j | n$, $j \in \{ 1,..., n \}$ and $\#H = \frac{n}{j}$ (c.f. <cit.> and <cit.> for a solution). Let  $G_{(k_1,...,k_n)}$ be generated by $(1 \; 2 \;... \; n)^{j}$. By the definition of the stabilizer, this implies $k_i = k_{i\;\text{mod}\;j}$  for any $i \in \{1,...,n\}$, where $i\;\text{mod}\;j $ is chosen such that $i\;\text{mod}\;j \in \{1,...,j\}$. Consequently, using $j | n$ we obtain

\begin{equation*}
k = \sum_{i = 1}^n k_i = \frac{n}{j} \sum_{i=1}^{j}k_j = \# G_{(k_1,...,k_n)} \cdot \sum_{i=1}^{j}k_j.
\end{equation*}

Thus, we also have $\#G_{(k_1,...,k_n)} | k$. Finally, the other statement $\#G_{(k_1,...,k_n)} | n$ follows from the orbit stabilizer theorem (see <cit.>): We have

\begin{equation*}
\#[k_1,...,k_n] = \# (k_1,...,k_n) \cdot G = \frac{\#G}{\#G_{(k_1,...,k_n)}} = \frac{n}{\#G_{(k_1,...,k_n)}}.
\end{equation*}

For the second part of the Lemma, note that if $\text{GCD}(n,k) =  1$, then $\#G_{(k_1,...,k_n)} = 1$ and thus $\#[k_1,...,k_n] = n$ (by the first part and the orbit stabilizer theorem).

Let $n \in \F{N}$. Consider the same setup as in Lemma <ref> with $n = n$ and $k = n-1$, i.e. $M = \{ (k_1,...,k_n) \in \F{Z}_+^n \;|\; k_1 + ... + k_n = n-1 \}$. Furthermore, let $1 \leq m \leq \lfloor \frac{n}{2} \rfloor$. Then, the number $\beta(n,m)$ of equivalence classes $[k_1,...,k_n] \in M/G$ with exactly $m$ non-adjacent zeros is given by

\begin{equation}
\label{eq: appendix_lemma_beta(n,m)}
\beta(n,m) = \frac{1}{n-1} \binom{n-1}{m} \binom{n-1-m}{n-2m}.
\end{equation}

As a formal, detailed proof tedious and not the main focus of this work, we leave some technical details to the reader and use intuitive arguments.
Let $A = \{ [k_1,...,k_n] \in M/G \, | \, [k_1,...,k_n] \text{ has exactly $m$ non-adjacent zeros} \}$. Note that by definition $\beta(n,m) = \# A$. Let $\rho = \exp(\frac{2 \pi i}{n-1})$, so that $1, \rho,..., \rho^{n-2} \in S^1$ denote the $n-1$-th primitive roots, where $S^1$ denotes the unit circle. To calculate $\#A$ we  identify uniquely and element $[k_1,...,k_n] \in A$ with a partition of the circle $S^1$ (more precisely a partition modulo  $\frac{2\pi}{n-1}$ rotation) into $n$ boxes as follows: Denote by $(1, \circ, \rho, \circ , ..., \rho^{n-2}, \circ , \rho^{n-1})$ the circle, where $\circ $ refer to the (curved) intervals $(\rho^k, \rho^{k+1})$ and by definition $\rho^{n-1} = 1$. For intuition, it is useful to imagine that the tuple is glued together at both ends. Using this notation we now define the partition of $S^1$ into boxes that contain the primitive roots. Denote by $|$ the edges of the boxes, and let $(1,b_1, \rho,b_2 , ...,\rho^{n-2},b_{n-1} ,\rho^{n-1})$ for $b_i \in \{\circ, |, ||, |||, ....\} \cong \F{N}_0$ denote a partition of $S^1$ into $\sum_{i = 1}^{n-1}b_i$ boxes  (the number of boxes equals the total number of edges $\sum_{i = 1}^{n-1} b_i$). These boxes contain in total the $n-1$ primitive roots $1,\rho,...,\rho^{n-2}$. Hereby, $||$ is interpreted as an empty box. For sake of notation we identify $(1,b_1, \rho,b_2 , ...,\rho^{n-2},b_{n-1} ,\rho^{n-1}) = (b_1,...,b_{n-1})$. Recall that for $[k_1,...,k_n] \in A$ we have $\sum_{i = 1}^n k_i = n-1$, so we want to identify $[k_1,...,k_n]$  with a partition of $S^1$ into $n$ boxes, where the corresponding boxes contain  exactly $k_i$ of the $n-1$ primitive roots. As $[k_1,...,k_n]$ is invariant under circular permutations this identification should by invariant, with respect to the $\frac{2\pi}{n-1}$ rotation of $S_1$ (which corresponds to a circular shifting of the boxes). Thus, we define equivalence classes $[b_1,...,b_{n-1}]$ via the (right) group action

\begin{equation}
(b_1,...,b_{n-1}) \cdot \sigma = (b_{\sigma(1)},...,b_{\sigma(n-1)}),
\end{equation}

where $\sigma \in  \{ (1 \; 2 \; ... \; n-1),..., (1 \; 2 \;... \; n -1)^{n-2}, \text{Id} \} $ is a circular permutation of $n-1$ elements. This corresponds to a circular shifting of the boxes. As $[k_1,...,k_n]$ has exactly $m$ non-adjacent zeros, the corresponding partition $[b_1,....,b_{n-1}]$ must satisfy $b_i \in \{\circ,|,|| \} \cong \{0,1,2\} $ (otherwise there would be at least two adjacent empty boxes) and $m = \#\{ b_i \, |\,  b_i = ||, \, i = 1,...,n-1 \} $ (which corresponds to the $m$ zeros). Thus, we just consider

\begin{equation}
B =  \{(b_1,...,b_n) \in \{0,1,2\}^{n-1} \, | \,\sum_{i=1}^{n-1}b_i = n, \#\{ b_i \, |\,  b_i = ||, \, i = 1,...,n-1 \} = m\}
\end{equation}

\begin{equation}
B/H = \{[b_1,...,b_{n-1}] \, | \, (b_1,...,b_{n-1}) \in B \},
\end{equation}

where $H = \{ (1 \; 2 \; ... \; n-1),..., (1 \; 2 \;... \; n -1)^{n-2}, \text{Id} \} $. Note that there is a one to one correspondence between $B/H$ and $A$: Each $[k_1,...,k_n] \in A$ defines a unique $[b_1,...,b_{n-1}] \in B/H$ and vice versa (we leave the detailed proof of this intuitive statement to the reader). Intuitively, this is seen by imagining the boxes and the primitive roots $\rho^k$ on a circle and using the invariance with respect to circular shifts of the boxes. Hereby a box containing $l$ primitive roots corresponds to some $k_i = l$. Thus,

\begin{equation}
\#A = \#B/H.
\end{equation}

Finally, (<ref>) follows by the above identification and Lemma <ref>: Let $(b_1,...,b_{n-1}) \in B$, then  $ \#\{ b_i \, |  b_i = 2, \, i = 1,...,n-1 \} = m$ and $\sum_{i = 1}^{n-1}b_i = n$ implies also $ \#\{ b_i \, |  b_i = 1, \, i = 1,...,n-1 \} = n-2m$ . Thus, a simple combinatorial argument shows (there are $\binom{n-1}{m}$ positions to choose the zeros and $\binom{n-1-m}{n-2m}$ remaining positions to chose the ones)

\begin{equation}
\#B = \binom{n-1}{m} \binom{n-1-m}{n-2m}
\end{equation}

Furthermore, we always have $\text{GCD}(n,n-1) = 1$ so Lemma <ref> (with $n = n-1$ and $k = n$) implies that $\# [b_1,...,b_{n-1}] = n-1 = \# H$ for any $[b_1,...,b_{n-1}] \in B/H$ so

\begin{equation}
\beta(n,m) = \#B/H = \frac{1}{n-1} \#B = \frac{1}{n-1} \binom{n-1}{m} \binom{n-1-m}{n-2m}.
\end{equation}

Let $\beta(n,m)$ be defined as in Lemma <ref> and define

\begin{equation}
\beta_n =\sum_{m = 1}^{\lfloor \frac{n}{2} \rfloor} \beta(n,m).
\end{equation}

Then, the series

\begin{equation}
\sum_{n = 2}^\infty \beta_n x^n
\end{equation}

has convergence radius $\frac{1}{3}$ and

\begin{equation}
\sum_{n = 2}^\infty \beta_n x^n = \Phi(x),
\end{equation}

where $\Phi(x) = \left ( \frac{1-x}{2} \right) \left( 1-  \sqrt{1-\frac{4x^2}{(1-x)^2}} \right) $.

Let $(m_n)_{n \in \F{Z}_+}$ be the Motzkin numbers defined by the quadratic equation (c.f <cit.>)

\begin{equation}
\label{eq: appendix_motzkin_quadratic_eq}
m(x) = 1 + xm(x) + (xm(x))^2 = \sum_{n=0}^\infty m_n x^n,
\end{equation}

more precisely defined by the analytic branch of the two branches of solution of the above equation. An elementary calculation shows that

\begin{equation}
m(x) = \frac{1-x - \sqrt{(1-x)^2 - 4 x^2}}{2x^2},
\end{equation}

for $x \in [-1,\frac{1}{3}]$ (the range where the quadratic equation (<ref>) has real solutions). Note that the function $m(x)$ is analytic at $0$ ; we have

\begin{equation}
\label{eq: app_motzkin_series}
m(x) = \sum_{n = 0}^\infty m_n x^n,
\end{equation}

where the convergence radius of the above series is $\frac{1}{3}$. This can be seen as follows. It is well known, that the root function $\sqrt{y}$ has a holomorphic extension onto the sliced plane $\F{C}\backslash \F{R}_{\leq 0}$. Furthermore, an elementary calculation shows that the complex polynomial $p(z) = (1- z)^2 - 4 z^2$, satisfies $\text{Re}(p(z)) > 0$ for $\abs{z} < \frac{1}{3}$, thus the numerator $F(x) = 1- x - \sqrt{p(x)}$ has a holomorphic extension onto the open ball $B_{\frac{1}{3}}(0) \subset \F{C}$  with radius $\frac{1}{3}$ (using the holomorphic extension of the root). Thus, as all holomorphic functions are analytic we can write $F(x) = \sum_{n = 0}^\infty F_n x^n$ for $\abs{x} < \frac{1}{3}$. But , $F(0) = F'(0) = 0$, so $F_0 = F_1 = 0$ and consequently  we can write $m(x) = \frac{F(x)}{2x^2}$ as in (<ref>) for $\abs{x} < \frac{1}{3}$. The convergence radius of the series (<ref>) cannot be bigger than $\frac{1}{3}$, because otherwise the function $x^2 m(x) - 1 + x = \sqrt{p(x)}$ would have an holomorphic extension onto some ball $B_{\frac{1}{3}+\varepsilon}(0)$, which is not possible. That this is not possible follows for example from the fact that $\lim_{x \uparrow \frac{1}{3}} \frac{d}{dx} \sqrt{p(x)} = \infty$ (which would have to exists if $\sqrt{p(x)}$ had an holomorphic extension). We show now that

\begin{equation}
\beta_{n+2} = m_n
\end{equation}

for all $n \in \F{Z}_+$. For that we use the identity (see <cit.>):

\begin{equation}
m_n =  \sum_{m = 0}^\infty \binom{n}{2m} \frac{(2m)!}{m! (m+1)!}.
\end{equation}

As $\binom{n}{k} = 0$ if $k> n$ it follows that

\begin{equation}
\label{eq: appendix_m_n}
m_n = \sum_{m = 0}^{\lfloor \frac{n}{2} \rfloor } \binom{n}{2m} \frac{(2m)!}{m! (m+1)!}
\end{equation}

By definition

\begin{equation}
\label{eq: appendix_beta_n+2}
\beta_{n+2} = \sum_{m = 1}^{\lfloor \frac{n+2}{2} \rfloor} \beta(n+2, m) = \sum_{m = 1}^{\lfloor \frac{n}{2} \rfloor + 1} \beta(n+2, m)
= \sum_{m = 0}^{\lfloor \frac{n}{2} \rfloor} \beta(n+2, m+1)
\end{equation}

and (c.f (<ref>))

\begin{align}
\begin{split}
&\beta(n+2,m+1) = \frac{1}{n+1} \binom{n+1}{m+1} \binom{n -m}{n - 2m } \\
&= \frac{n!}{(m+1)!m! (n-2m)!}
= \binom{n}{2m} \frac{(2m)!}{m! (m+1)!},
\end{split}
\end{align}

where in the last two equalities $\binom{l}{k} =  \frac{l!}{k! (l-k)!}$ was used. Combining the above equality  with (<ref>)  and (<ref>) yields $\beta_{n+2} = m_n$, which implies

\begin{equation}
\sum_{n = 2}^\infty \beta_n x^n = \sum_{n = 0}^\infty m_nx^{n+2} = x^2 m(x)^2.
\end{equation}

Thus, these series have the same convergence radius  $\frac{1}{3}$. Finally, an elementary calculation shows that $\Phi(x) = x^2m(x)$ for $0 \leq x \leq \frac{1}{3}$.

$E$finite state space; i.e. some finite set
$\F{X} = (X_t)_{t \geq 0}$Markov jump process def: Markov_jump_process
$(\F{P}_x)_{x \in E}$family of probability measures of an MJP  def: Markov_jump_process
$\nu, \mu, \beta $ probability measures on $E$
$f, g, h$real valued functions on $E$
$\F{P}_x( \text{\,} \cdot \text{\,} \vert \text{\,}  \cdot \text{\,} ) , \F{E}_x( \text{\,} \cdot \text{\,}   \vert \text{\,} \cdot \text{\,} ) $conditional probability, conditional expectation
$\pi$invariant probability measure of an irreducible MJP th: uniqueness_existence_invariant_measure
$(P_t)_{t \geq 0}$semigroup of operators; corresponding to an MJP  eq: contraction_semigroup_Markov_process
$L, L^*$infinitesimal generator, adjoint of infinitesimal generator; of an (irreducible) MJP lem: contraction_semigroup_MJP
$\mathbf{1}$constant $1$-function on $E$
$\norm{\cdot}_2, \langle \cdot , \cdot \rangle $$L^2(\pi)$ norm  of functions and operators, scalar product on $L^2(\pi)$
$S$reduced resolvent of $\frac{L+L^*}{2}$ with respect to $0$ def: reduced_resolvent
$\F{R}^E,\,\mathcal{B}(E),\,L^2(\pi)$real function spaces: all functions $f : E \rightarrow \F{R}$, bounded and measurable, $\pi$-square-integrable
$\pi(f), \mu(f)$short notation for $\int_E f d\pi, \int_E f d\mu $
$F,G,H$real valued functions defined on some subset $D \subset \F{R}$
$(P_t^h)_{t \geq 0}$Feynman-Kac semigroup eq: def_P_t^h
$\mathcal{M}_1(E)$set of probability measures on $E$
$A_t$integral $\int_0^t f(X_s) ds$
$M_f$multiplication with $f$
$\lambda_0(r)$largest eigenvalue of $\frac{L+L^*}{2} + rM_f$
$F^*, G^*, \lambda_0^*$ Fenchel conjugates def: fenchel_conjugate
$\Psi_Z(r), \Psi_{A_t}(r)$cumulant generating function of $Z$ resp. $A_t$; i.e. $\log \F{E} (e^{rZ}) $ resp. $\log \F{E}_\nu(e^{rA_t})$
$\Psi_Z^*$Cramér transform of a random variable $Z$ th: cramer_chernoff
$\F{P}_\nu, \F{E}_\nu$probability measure $\sum_{x \in E} \nu_x \F{P}_x$, expectation with respect to $\F{P}_\nu$ eq: def_P_nu

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

Berlin Heidelberg

Springer Science
Business Media

titleFrom Classical to Modern Probability - Cimpa Summer School 2001

Berlin, Heidelberg

titleIntelligence for Embedded Systems - A Methodological Approach

Berlin Heidelberg New York

titleContinuous-time Markov Chains - An Applications-oriented Approach

American Physical Society

journaltitlePhys. Rev. Lett.
titleThermodynamic Uncertainty Relation for Biomolecular Processes

journaltitleJournal of Computational Physics
titleEfficient estimation of free energy differences from Monte Carlo data

journaltitleBiophysical Journal
titlePhysics of chemoreception

Berlin Heidelberg

Springer Science
Business Media

titleConvex Analysis and Nonlinear Optimization - Theory and Examples

Berlin Heidelberg New York

titleAlgebra -

Berlin, Heidelberg

titleLévy Matters III - Lévy-Type Processes: Construction, Approximation and Sample Path Properties

New York, London

OUP Oxford

titleConcentration Inequalities - A Nonasymptotic Theory of Independence

Berlin Heidelberg

Springer Science
Business Media

titleMarkov Chains - Gibbs Fields, Monte Carlo Simulation, and Queues

EDP Sciences

journaltitleESAIM: Probability and Statistics
titledeviation bounds for additive functionals of markov processes

journaltitlePhysica D: Nonlinear Phenomena
titleOptimal prediction with memory

Springer Berlin Heidelberg

titleLarge Deviations Techniques and Applications -

American Mathematical Soc.

titleLarge Deviations -

journaltitleJournal of Combinatorial Theory, Series A
titleMotzkin numbers

titleLecture notes-Markov processes

Berlin Heidelberg

Springer Science
Business Media

titleA Short Course on Operator Semigroups -

The Royal Society of Chemistry

journaltitlePhys. Chem. Chem. Phys.
titleProbing the type of anomalous diffusion with single-particle tracking

Springer Berlin Heidelberg

titleLineare Algebra - Eine Einführung für Studienanfänger

journaltitleTheory of Probability and Its Applications
titleBernstein-type Concentration Inequalities for Symmetric Markov Processes

American Physical Society

journaltitlePhys. Rev. Lett.
titleDissipation Bounds All Steady-State Current Fluctuations

journaltitleProbability Theory and Related Fields
titleTransportation-information inequalities for Markov processes

Berlin, Heidelberg

titleLie Groups, Lie Algebras, and Representations - An Elementary Introduction

Cambridge University Press

titleMatrix Analysis, Second Edition

journaltitleRep. Prog. Phys.
titleThe physics of pulling polyproteins: a review of single molecule force spectroscopy using the AFM to study protein unfolding

journaltitleJournal of Statistical Physics
titleCanonical Structure and Orthogonality of Forces and Currents in Irreversible Markov Chains

Berlin Heidelberg

Springer Science
Business Media

titleFoundations of Modern Probability -

titleStochastic processes in physics and chemistry -

Berlin Heidelberg

Springer Science
Business Media

titlePerturbation Theory for Linear Operators

MIT Press

titleAn Introduction to Computational Learning Theory -

Universitätsverlag Göttingen

titleAnalytische Geometrie und lineare Algebra 2

Berlin Heidelberg New York

American Physical Society (APS)

journaltitlePhysical Review Research
titleSpectral theory of fluctuations in time-average statistical mechanics of reversible and driven systems

journaltitleESAIM: Probability and Statistics
titleChernoff and Berry-Esséen inequalities for Markov processes

American Mathematical Soc.

titleContinuous Time Markov Processes - An Introduction

IOP Publishing

journaltitleEPL (Europhysics Letters)
titleCanonical structure of dynamical fluctuations in mesoscopic nonequilibrium steady states

titleMatrix Analysis and Applied Linear Algebra -

journaltitleThe Journal of Chemical Physics
titleKinetic equations for site populations from the Fokker–Planck equation

journaltitleNature Methods
titleSingle-molecule force spectroscopy: optical tweezers, magnetic tweezers and atomic force microscopy

Cambridge University Press

titleMarkov Chains -

Society for Industrial
Applied Mathematics

journaltitleMultiscale Modeling & Simulation
titleOn the Approximation Quality of Markov State Models

journaltitleNature Methods
titleSingle-particle tracking: connecting the dots

journaltitleThe European Physical Journal Special Topics
titleA critical appraisal of Markov state models

IOP Publishing

journaltitleReports on Progress in Physics
titleStochastic thermodynamics, fluctuation theorems and molecular machines

titleFunctional Inequalities Markov Semigroups and Spectral Theory -

journaltitleAnnales de l'I.H.P. Probabilités et statistiques
titleA deviation inequality for non-reversible Markov processes

journaltitleProceedings of the National Academy of Sciences of the United States of America
titleSingle-molecule studies highlight conformational heterogeneity in the early folding steps of a large ribozyme

American Chemical Society

journaltitleNano Letters
titleConformational Dynamics of a Single Protein Monitored for 24 h at Video Rate

Springer New York

titleContinuous-Time Markov Chains and Applications - A Singular Perturbation Approach

New York

OUP USA

titleNonequilibrium Statistical Mechanics -